WisFaq!

Stelling van Euler

Ik maak een werkje over RSA en ik begrijp het volgende niet zo goed:

Eerst moet je ervoor zorgen dat d en e elkaars inverse zijn door een modulo van $\phi$(N)te berekenen$\to$ e�d �� 1 (mod $\phi$(N)). Maar waarom berekenen we dan het bericht dat we gaan coderen met modulo N$\to$ c �� b^e (mod N) en b �� c^d (mod N)? Waarom is dit niet c �� b^e (mod $\phi$(N)) of b �� c^d (mod $\phi$(N))?

Miel Van der WIlt
26-3-2014

Antwoord

Beste Miel,
Ik maak er een lang verhaal van, in de hoop dat dit wat duidelijkheid verschaft.

Neem 2 grote priemgetallen p en q
pq = n
$\varphi$n = (p - 1)(q - 1) het aantal getallen a waarvoor geldt:
ggd(a,n) = 1
e = vercijferingsexponent. Er moet gelden ggd(e,$\varphi$n) = 1
controle met algoritme van euclides dan wel software.
1 = e � d - k$\varphi$n$\Rightarrow$e � d$\equiv$ 1 mod ($\varphi$n)
en dus d = e^-1 (inverse)
d = ontcijferingsexponent te vinden met algoritme van euclidus
b = boodschap
c = code
c $\equiv$ b^emod(n)
b $\equiv$ c^dmod(n) $\Rightarrow$ c^d $\equiv$ b^ed mod(n)
Dit laatste is de kern en verdient wat toelichting:
stelling van euler: als ggd(b,n) = 1 $\Rightarrow$ b^$\varphi$n $\equiv$ 1 mod(n)
Welnu:
e � d $\equiv$ 1 mod($\varphi$n) $\Rightarrow$ e � d = k � $\varphi$n + 1
b^ed $\equiv$ b^{k�$\varphi$n+1} $\equiv$ b�b^{k�$\varphi$n} $\equiv$ b mod(n)
Kortom het maakt het ontcijferen gemakkelijk

mvg DvL

DvL
26-3-2014