Voor mijn profielwerkstuk over encryptie ben ik bezig met de reader kun je die code kraken? (http://www.win.tue.nl/~jessers/aansluiting/krakendownloaden.htm) van de technische universiteit eindhoven.
Volgens die reader moet je het volgende doen om een bericht te coderen:
Stap 1 kies 2 verschillende priemgetallen, p1 en p2, en bereken het product van die twee, n.
Stap 2 kies een vercijferingsexponent, e, met ggd(e,f(n))=1
hierbij geldt dus ook de stelling van Euler:
e^(f(f(n)))º1(modf(n))
Stap 3 bereken de decryptie-exponent, d.
Stap 4 maak n en e bekend en houd d, p1 en p2 geheim.
Mijn vraag is:
Waarom moet in de stelling van Euler, bij stap 2 in de modulo-functie, f(n) genomen worden, en niet gewoon n?
Ik begrijp dat de stelling van Euler zegt dat de macht van e f moet zijn, maar waarom ook in de modulo-functie?
P.S. Mijn vraag heeft met name betrekking tot stap 2, waarin wordt gemoduleerd met de fi-waarde van een getal (functie van Euler). Het getal voor het "identiek-aan-teken" nemen ze tot de macht fi-fi van de eerder genoemde fi-waarde. Ik vraag me af waarom ze dat zo doen. De stelling van Euler zou toch ook gelden als je moduleert met een niet-fi-waarde.
Alain
Leerling bovenbouw havo-vwo - maandag 19 april 2004
Antwoord
Wat in stap 2 staat is helemaal correct. ggd(e,f(n)) moet inderdaad 1 zijn opdat via de stelling van Euler e^(f(f(n)))º1(modf(n)) inderdaad geldt.
Deze uitdrukking moet waar zijn opdat we de decryptie-exponent d, zoals in de reader uitgewerkt staat in stap 3, zouden kunnen berekenen. Voor d moeten we namelijk de inverse van e modulo f(n) kunnen berekenen. n is echter niet priem zodat dit niet altijd kan. d moet behoren tot U(_n) (U is de verzameling van eenheden; dit zijn de elementen die een inverse hebben). Daarvoor moet ggd(e,f(n))=1 (dit is één van de stellingen i.v.m. modulorekenen). Ook voor de uitwerking in stap 3 in de reader is deze voorwaarde nodig. Daar gebruikt men de stelling van Euler zoals je vernoemd hebt.
Op blz 37-38 van de reader staat dan waarom we met deze d inderdaad een gecodeerde boodschap kunnen decoderen. Men vergat daar wel te vermelden dat ggd(m,n)=1 moet zijn opdat Euler zou gelden. In een zeldzaam geval is dat niet zo, maar ook dat zal uiteindelijk geen probleem opleveren...
_n) (U is de verzameling van eenheden; dit zijn de elementen die een inverse hebben). Daarvoor moet ggd(e,f(n))=1 (dit is één van de stellingen i.v.m. modulorekenen). Ook voor de uitwerking in stap 3 in de reader is deze voorwaarde nodig. Daar gebruikt men de stelling van Euler zoals je vernoemd hebt.