Functie van Euler

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...

Joeri
woensdag 5 mei 2004

©2001-2024 WisFaq