14.2 Het RSA-algoritme

Het RSA-Algoritme

Kies twee grote priemgetallen p en q en bereken n=p*q.
Bereken f(n)=(p-1)*(q-1)= K
Kies een getal dat relatief priem is ten opzichte van K en bereken de inverse d mod K.
Een bericht dat vercijferd is met xe mod n = y 
is nu te ontcijferen met yd mod n = x.
{e,n} heet de publieke sleutel.
{d,n} heet de privé sleutel.

Dat yd mod n = xed mod n is niet moeilijk in te zien. Dat xed mod(n) = x met edmod(K)=1, wordt bewezen voor 0<x<min{p,q} op de subpagina Euler en Fermat met gebruik van de stelling vanEuler. Voor het bestuderen van deze hoofdpagina is het geen bezwaar om met bestudering van deze subpagina tot het eind te wachten.

De RSA-vercijfering werkt als volgt: Alice publiceert het getal n en het getal e. Ze zet het bij wijze van spreken op haar naamkaartje of publiceert het in een encryptiegids waarin Bob het kan vinden. Alice houdt haar sleutel, de priemgetallen p en q, geheim. Bob vercijfert zijn bericht x met de eenwegfunctie xe mod n en verstuurt het resultaat naar Alice. De klare tekst is dus x en de cijfertekst is y=xe mod n. Met haar sleutel en de tabel van Euclides berekent Alice de inverse d en berekent yd mod n. Dit levert haar de klare tekst x.

De vraag is nu wat Eve kan ontdekken als ze het bericht xe mod n voorbij ziet komen. Het is voor haar immers net zo goed mogelijk om in de encryptiegids de publieke sleutel op te zoeken en ze kent dus de waarde van e en n. Het enige wat Eve nog te doen heeft is het opstellen van een tabel bij de cijferfunctie of het vinden van de waarde van d, de inverse van e mod K. Helaas voor Eve kent ze het getal K niet. Alleen door factorisatie van n kan ze K berekenen en dat is iets wat haar niet gaat lukken als de priemgetallen p en erg groot zijn. Dit probleem staat bekend als het factorisatieprobleem.