WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

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

Vragen naar aanleiding van dit antwoord? Klik rechts..!
woensdag 5 mei 2004