RSA (cryptografie): verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
→Bewijs ontsleutelingsrelatie: Bewijs uitgebreid en hopelijk beter te begrijpen. |
|||
Regel 36:
=== Bewijs ontsleutelingsrelatie ===
Het bewijs gebruikt [[Fermats kleine stelling]]. Die stelt dat voor ''p'' priem, ''n'' geheel en ggd(''p'', ''n'') = 1 geldt dat:
:<math>
: <math> c^d \mathrm{mod}\ N= n^{e \cdot d}\ \mathrm{mod}\ N</math>▼
n^{p-1} \equiv 1 \; \mathrm{mod}\,\ p.
</math>
Gegeven is:
:<math>
</math>
Dus
:<math>
ed - 1 = k(p-1)(q-1)
</math>
voor zekere gehele ''k''. Dan, aannemend dat ggd(''n'', ''p'') = 1,
:<math>
n^{ed} = n^{ed-1}n = n ^{k(p-1)(q-1)}n = (n^{p-1})^{k(q-1)} n \equiv 1^{k(q-1)} n = n \; \mathrm{mod}\, p.
</math>
Als ggd(''n'', ''p'') ≠ 1 dan, omdat ''p'' priem is, geldt ''n'' ≡ 0 mod ''p'' en in totaal
:<math>
n^{ed} \equiv n \; \mathrm{mod}\, p \Longrightarrow n^{ed} -n \equiv 0 \; \mathrm{mod}\, p.
</math>
Evenzo,
:<math>
▲
</math>
Uit ''n''<sup>''ed''</sup> − ''n'' ≡ 0 mod ''p'' volgt dat ''n''<sup>''ed''</sup> − ''n'' een veelvoud van ''p'' is. Voor zekere gehele ''s'':
:<math>
n^{ed} -n = s p.
</math>
Verder is ''n''<sup>''ed''</sup> − ''n'' = ''sp'' een veelvoud van ''q''. Omdat ''p'' geen veelvoud q is moet ''s'' dit wel zijn,
''s'' = ''tq'', en dus geldt
:<math>
n^{ed} -n = t p q \Longrightarrow n^{ed} \equiv n \; \mathrm{mod}\, pq,
</math>
en omdat ''N'' = ''pq'' is de ontsleutelingsrelatie bewezen.
===Voorbeeld===
| |||