Het RSA-cryptosysteem

Het RSA-cryptosysteem dateert van 1978 en is genoemd naar de drie uitvinders: Rivest, Shamir en Adleman. Het systeem maakt gebruik van "oude" stellingen uit de getaltheorie en van de reken(on)mogelijkheden van computers. Met computers kun je namelijk "snel" grote priemgetallen bepalen en machtsverheffen maar met computers kun je niet snel een getal factoriseren (de delers ervan bepalen).

De werking van het systeem wordt het duidelijkst aan de hand van een concreet voorbeeld

Voorbereiding

De volgende voorbereidingen moeten door alle deelnemers uitgevoerd worden. Hier laten we alleen zien wat een deelnemer, Bob geheten, doet.

Stap 1: Keuze van de priemgetallen
Deelnemer Bob kiest twee verschillende priemgetallen, zeg p en q. De andere deelnemers kiezen ook hun eigen priemgetallen.

voorbeeld:
p = 99989
q = 99991

Bob rekent ook (met een computer) het product n = p*q uit

voorbeeld
n = p*q = 99989*99991 = 9998000099 

Stap 2: Keuze van de vercijferingsexponent
Bob kiest een willekeurige vercijferingsexponent e uit. Deze mag echter geen factor gemeen hebben met j(n). Dus de ggd van j(n) en e moet 1 zijn. 

voorbeeld:
j(n) = j(p*q) = (p -1)* (q -1) = 99988*99990 =  9997800120
e = 11111357

Opmerking. Er bestaat een " zeer oud" algoritme waarmee je "snel" de ggd van twee getallen kunt bepalen. Met dat algoritme moet je controleren of de ggd (Engels gcd) van j(n) en e gelijk is aan 1.  In de onderstaande  tabel zie je de berekeningen in dit algoritme. Daar heeft een computer weinig moeite mee (controle via internet)

9997800120 

 = 11111357*899 + 8690177

11111357

 = 8690177*1 + 2421180

8690177 

 = 2421180*3 + 1426637

2421180 

 = 1426637*1 + 994543

1426637 

 = 994543*1 + 432094

994543

 = 432094*2 + 130355

432094

 = 130355*3 + 41029

130355

 = 41029*3 + 7268

41029 

 = 7268*5 + 4689

7268

 = 4689*1 + 2579

4689 

 = 2579*1 + 2110

2579 

 = 2110*1 + 469

2110

 = 469*4 + 234

469

 = 234*2 + 1

234 

 = 1*234 + 0

Het bovenstaande algoritme heet het algoritme van Euclides. Uitvoerige uitleg over het hoe en waarom van dit algoritme vind je op de pagina getalbegrippen 

Stap 3:  Berekening van de ontcijferingsexponent
In de bovenstaande tabel kun je ook van beneden naar boven werken. Uit de voorlaatste regel volgt: 1 = 469 - 2*234. Je hebt 1 dan geschreven als een combinatie van 469 en 334. Uit de regel daarboven volgt 234 = 2110 - 4*469. Dat resultaat kun je invullen in 1 = 469 - 2*234. Je krijgt dan 

1 = 469 - 2*234 = 469 - 2*( 2110 - 4*469) = - 2* 2110 + 9*469

Nu heb je 1 geschreven als een lineaire combinatie van 469 en 2110. Op deze manier kun je verder gaan tot je 1 geschreven hebt als een combinatie van e = 11111357 en j(n) = 9997800120. Een karweitje dat je beter kunt uitbesteden aan een computer. (gebruik bijvoorbeeld ggdplus of kijk op controle via internet). Het resultaat is:

1 = 42643373*11111357 + -47393*9997800120

Als je nu modulo j(n) gaat rekenen dan verschijnt er. 

 42643373*11111357 1  (mod 9997800120)

Het getal  42643373 is een belangrijk getal. Het is de ontcijferingsexponent d .Omdat het produkt van dit getal met e gelijk is aan 1 (mod j(n) ) heet dit getal ook wel de inverse van e (modulo j(n) ). Dat getal heb je nodig voor het ontcijferen van geheimschriften, dat zal verderop blijken. Met het bestand modinverse.exe kun je die d - ook voor zeer grote getallen - snel berekenen. Ook via de volgende links kun je d bepalen.

Stap 4:  Bekendmaking van n en e
Bob maakt nu: n = 9998000099 en e = 11111357 algemeen bekend, maar houdt d = 42643373 geheim. Ook de priemgetallen p = 99989 en q = 99991 mogen niet bekend worden!!.

Boodschappen versturen: vercijfering

Stel nu dat een andere persoon, zeg Alice, een boodschap naar Bob wil sturen. Voor het gemak is de boodschap het getal  101112. Als je afspreekt dat de 10 met de a correspondeert, de 11 met de b etc dan stelt 101112 het "woord" abc voor  Overigens moet het getal wel kleiner zijn dan n want er wordt modulo n  gerekend.

Alice zoekt de openbare waarden van Bob op: e = 11111357 en n = 9998000099. Vervolgens berekent ze met een computer:

boodschape  (mod n) = 10111211111357  (mod  9998000099)

Alice verheft dus de boodschap tot de openbare vercijferingsexponent van Bob, modulo de n van Bob en stuurt het antwoord naar Bob. Het vercijferde getal is gelijk aan m = 3316546434 (de m van message) Ook dat is een berekening die je aan een computerprogramma moet uitbesteden (modmacht). Een machtsverheffing modulo n is daarmee "snel"  uit te voeren.

Afluisteren

De afluisteraar (eavesdropper in het Engels), die Eva heet, onderschept deze waarde m = 3316546434 . Zij kent ook de openbare waarden van Bob e = 11111357 en n = 9998000099

3316546434 = boodschap11111357 (mod  9998000099)

Er zit nu voor haar niet veel meer op dan voor de boodschap 1, 2, 3, 4, .... 9998000098 uit te proberen want er bestaat geen enkel computeralgoritme waarmee dat snel kan. Dit is niet leuk voor haar , maar zeker ondoenlijk als n en de boodschap getallen van zeg 200 cijfers lang zijn.

Boodschappen lezen: Ontcijfering 


Bob kent als enige zijn geheime ontcijferingsexponent d = 42643373, en kan dus het volgende uitrekenen:

331654643442643373 (mod  9998000099)

En dat is nu gelijk aan 101112 = abc. De originele boodschap!!!!!. Dat dit werkt is eenvoudig het gevolg van de stelling van Euler. Immers 

md (mod n) 

 

 (boodschap)e)d (mod  n)

zo heeft Alice de boodschap m gemaakt

 boodschape* d (mod  n)   

regel machtsverheffen

 boodschap1 + k* j (n)  (mod  n)

e en d zijn elkaars inverse mod j(n)  

 boodschap1 . (boodschap j (n) )k  (mod n)

regels machtsverheffen

 boodschap.1k (mod  n)

de stelling van Euler

 boodschap

 

Als Eva d zou kennen dan kan ze die berekening ook kunnen uitvoeren. Maar d kan ze alleen berekenen als ze j(n) of p en q kent. Dus als ze n kan factoriseren kan ze het bericht ook kraken. Maar er bestaat geen snel algoritme voor het factoriseren van grote getallen. Als p en q uit 100 cijfers bestaan dan moet Eva een getal met ongeveer 200 cijfers factoriseren. Onbegonnen werk!! Er bestaan namelijk ongeveer 10100 priemgetallen met 100 cijfers.

De veiligheid van het RSA-systeem wordt bepaald door de stand van zaken op het gebied van factoriseren. De uitvinders van RSA suggereerden indertijd om n ongeveer 200 cijfers lang te nemen om het factoriseren van  onmogelijk te maken. In september 1999 heeft een grote groep rekenaars, die via internet met elkaar verbonden waren, een getal van 512 bits ontbonden. Omgerekend is dit getal ongeveer 154 cijfers lang, want 2512 is ongeveer 10154 . Het RSA systeem met een modulus van 512 bits lang wordt momenteel op een aantal plaatsen in de wereld gebruikt, onder andere voor elektronische betalingen over internet. Dat is dus niet meer aan te raden.


links naar info over RSA
Op het net is zeer veel  informatie over RSA te vinden:

RSA 1 (demo met getallen: je mag priemgetallen p en q < 50 kiezen)
RSA 2 (demo met getallen: je mag priemgetallen p en q < 1000 kiezen)
RSA 3 (zeer veel informatie over RSA en andere cryptosystemen)