Hoe werkt RSA?

Via internet kun je cd’s bestellen en ook betalen. Maar handelingen op internet waar geld mee gemoeid is horen beveiligd te zijn. Internetbrowsers gebruiken daarvoor het cryptosysteem RSA. Hoe RSA precies werkt wordt in dit artikel uitgelegd.

1 juni 1998

Als je op internet surft, heb je vast wel eens het logo van RSA gezien. RSA is een cryptosysteem waarmee internetbrowsers, zoals Explorer en Firefox, de communicatie via internet beveiligen. Het logo van RSA bestaat uit twee in elkaar passende sleutels.

Hoe RSA werkt is geen geheim. Om te beginnen moet je een sleutel maken. Daarvoor moet je twee grote priemgetallen p en q kiezen die je verder geheim houdt. Hun product m = p x q is je sleutelgetal. Dat getal, de zogenaamde modulus, maak je aan alle andere gebruikers bekend. Bij de huidige stand van de techniek is het verstandig om voor p en q priemgetallen van minstens honderd cijfers te kiezen, zodat de modulus m minstens tweehonderd cijfers telt. Als je er bovendien voor zorgt dat de getallen p-1 en q-1 niet allebei uitsluitend uit kleine priemfactoren zijn samengesteld, kun je er wel op vertrouwen dat niemand p en q weer uit de modulus m af kan leiden. Bij het inmiddels gekraakte voorbeeld van Ronald Rivest uit Scientific American was m ‘slechts’ een getal van 129 cijfers, namelijk gelijk aan

1143 81625 75788 88676 69235 77997 61466 12010 21829 67212 42362 56256 18429 35706 93524 57338 97830 59712 35639 58705 05898 90751 47599 29002 68795 43541

Rivest kende de twee priemfactoren van m, maar hield ze angstvallig geheim! In die tijd (we schrijven 1977) was ontbinden van zo’n groot getal volslagen ondoenlijk. Het heeft zeventien jaar geduurd voordat allerlei nieuwe wiskundige technieken, plus een enorme toename aan rekensnelheid en geheugencapaciteit van computers, het mogelijk maakten m te ontbinden en zo de code te kraken.

Het coderen van de boodschap

Terug naar de uitleg van de werking van RSA. De eerste stap is dus de constructie van de modulus m als product van twee geheime priemfactoren p en q. De modulus m wordt zowel bij het vercijferen als het ontcijferen van berichten gebruikt. Elk bericht wordt daartoe eerst op een niet-geheime manier in een groot getal omgezet. Als het om een tekst gaat, kun je bijvoorbeeld A = 01, B = 02, C = 03, …, Z = 26 nemen en 00 voor een spatie gebruiken. Wordt het bericht langer dan m, dan splitst je het in blokken die je afzonderlijk vercijfert en ontcijfert. In het voorbeeld van Rivest luidde de geheime tekst: the magic words are squeamish ossifrage. Dat wordt dus het volgende getal x:

20 08 05 00 13 01 07 09 03 00 23 15 18 04 19 00 01 18 05 00 19 17 21 05 01 13 09 19 08 00 15 19 19 09 06 18 01 07 05

waarbij we nog even spaties hebben laten staan tussen de gecodeerde letters. Je ziet dat deze x een getal van 78 cijfers is (het bestaat uit uit 34 letters en 5 spaties).

Hoe gaat vercijferen?

Het vercijferen gaat met machtsverheffen modulo m. In Pythagoras nr. 2 is op de bladzijden 24 en 25 uitgelegd hoe dat in zijn werk gaat, en hoe je dat heel snel door een computer kunt laten uitvoeren, zelfs al zijn de modulus en de exponent hele grote getallen. Zowel het vercijferen als het ontcijferen gebeurt door machtsverheffen modulo m. Voor het vercijferen heb je een vercijferexponent e nodig. De formule luidt: E(x) = x^e mod m. De geheime boodschap wordt dus modulo m tot de macht e verheven. Die vercijferexponent e is niet geheim. Rivest nam in zijn voorbeeld e = 9007. De daarmee vercijferde boodschap E(x) bleek een getal van 128 cijfers te zijn, namelijk het getal

968 69613 75462 20614 77140 92225 43558 82905 75999 11245 74319 87469 51209 30816 29822 51457 08356 93147 66228 83989 62801 33919 90551 82994 51578 15154

Wat Rivest in zijn prijsvraag bekend had gemaakt, was dus de modulus m, de vercijferexponent e en de vercijferde boodschap E(x). Aan de lezer de taak om x te achterhalen; voor de eerste die het lukte was een symbolische prijs van honderd dollar beschikbaar. Pas in 1994 zou Arjen Lenstra die prijs incasseren.

Hoe gaat ontcijferen?

Tot nu toe is de enige wiskunde die we tegen zijn gekomen het modulaire machtsverheffen geweest. We hebben ook alleen nog maar vercijferd. Nu komt de vraag hoe de rechtmatige ontvanger uit de vercijferde boodschap y = E(x) weer de oorspronkelijke x terugvindt. Merkwaardigerwijze gaat dat opnieuw met modulair machtsverheffen, alleen nu met een andere exponent, de ontcijferexponent d, die direct met e samenhangt op een manier die we zo dadelijk uit zullen leggen. Het ontcijferrecept is dan D(y) = y^d mod m en als alles goed is, moet dit voor y = E(x) dus weer x opleveren, dat wil zeggen dat modulo m geldt dat D(y) = D(E(x)) = (x^e)^d = x^ed = x.

Dat dit inderdaad zo is, volgt uit de stelling van Euler die we in Pythagoras nr. 3 op pagina 9 hebben bewezen. Die stelling luidde in het geval m = p x q als volgt:

Als ggd(x, m) = 1, dan is x^(p-1)^(q-1) equivalent aan 1 mod m.

Een gevolg hiervan is dat voor ieder geheel getal k geldt dat x^{1 + k(p-1)(q-1)} is equivalent aan x mod m, en dat is het resultaat dat we nodig hebben. Men kan zelfs bewijzen dat deze formule ook geldt als niet aan de voorwaarde ggd(x, m) = 1 is voldaan. Je ziet hieruit dat het enige wat we moeten doen om te bereiken wat we willen, is het vinden van een d en een k waarvoor geldt dat

e x d = 1 + k(p – 1)(q – 1)

Maar dat kun je zien als het bepalen van de inverse van de vercijferexponent e met betrekking tot de modulus n = (p – 1)(q – 1), en dat gaat met het algoritme van Euclides dat in Pythagoras nr. 2 op de bladzijden 12, 13 en 24 is behandeld. Als je die nieuwe modulus n kent, is dat niet veel werk, althans op de computer. Voorwaarde is wel dat die inverse bestaat, en dat betekent dat moet gelden ggd(e, n) = 1. Daar moet je dus bij de keuze van e rekening mee houden. Rivest had dat inderdaad gedaan: e = 9007 heeft geen delers gemeen met n. Alleen, om dat te controleren heb je p en q nodig. Als je p en q kent, ken je ook n = (p – 1)(q – 1), en dan kun je dus met het algoritme van Euclides zowel controleren dat ggd(e, n) = 1, als de bijbehorende geheime ontcijferexponent d berekenen.

Ook Arjen Lenstra heeft die weg bewandeld: hij vond eerst p en q (dat was het moeilijke werk!), berekende vervolgens n = (p – 1)(q – 1). Met deze n vond hij via het algoritme van Euclides de geheime ontcijferexponent d, en ten slotte met deze d de geheime boodschap x = y^d modulo m. De factoren p en q bleken te zijn 3490 52951 08476 50949 14784 96199 03898 13341 77646 38493 38784 39908 20577

32769 13299 32667 09549 96198 81908 34461 41317 76429 67992 94253 97982 88533

en de geheime ontcijferexponent d was gelijk aan

1066 98614 36857 80244 42868 77132 89201 54780 70990 66339 37862 80122 62244 96631 06312 59117 74470 87334 01685 97462 30655 39685 44513 27710 90536 06095

Samenvatting

In het kort luidt het recept om RSA-sleutels te maken als volgt:

1. Kies grote priemgetallen p en q (minstens 100 cijfers elk).
2. Bepaal de modulus m = p x q.
3. Bereken n = (p-1)(q-1).
4. Kies een vercijferexponent e waarvoor ggd(e,n) = 1.
5. Bereken d zo, dat e x d = 1 mod n.
6. Maak de getallen m en e bekend. Samen vormen die de openbare sleutel.
7. Houd d geheim. Dat is de geheime sleutel.
8. Vercijferen: E(x) = x^e mod m
9. Ontcijferen: D(y) = y^d mod m

Een voorbeeld

We illustreren dit alles nog eens met een wat kleiner getallenvoorbeeld. Als priemgetallen nemen we p = 74471 en q = 98773. De modulus m = p x q is dan 7355724083. Het getal n = (p – 1)(q – 1) is nu 7355550840, en voor e nemen we 619. Het algoritme van Euclides leert ons dat e inderdaad geen delers met n gemeen heeft, en bovendien dat de inverse d van e gelijk is aan 4313513659. Neem nu als boodschap PRIEM. In cijfers wordt dat x = 1618090513. Vercijferen levert:

E(x) = 1618090513⁶¹⁹ mod 7355724083 = 633613585

en ontcijferen geeft inderdaad:

D(633613585) = 633613585^4313513659 mod 7355724083 = 1618090513.

Opdracht

Met dezelfde modulus m en vercijferexponent e hebben we een ander woord vercijferd. Het resultaat is y = 1652695548. Kun jij achterhalen welk woord dat was?