‘The magic words are squeamish ossifrage’ – ‘de magische woorden zijn kleinzerige lammergier’. Die bizarre tekst heeft zeventien jaar lang verborgen gezeten in een geheime boodschap die met het cryptosysteem RSA vercijferd was. Op dinsdag 26 april 1994 maakte de Nederlandse wiskundige Arjen Lenstra in het Bellcore laboratorium in de Amerikaanse stad Morristown deze tekst openbaar. Hij had de sleutel gekraakt en daarmee het symbolische bedrag van honderd dollar verdiend – een schijntje als je bedenkt dat daarvoor niet minder dan 1700 computers, verspreid over de gehele wereld, een half jaar lang hebben moeten rekenen.

De prijs die Arjen Lenstra won was uitgeloofd door de bedenkers van RSA, Ronald Rivest, Adi Shamir en Leonard Adleman (RSA staat voor de beginletters van hun achternamen). In een artikel uit 1977 in het Amerikaanse tijdschrift Scientific American had Martin Gardner de werking van RSA verklaard, en uitgelegd dat je het systeem kunt kraken wanneer je grote getallen in priemfactoren kunt ontbinden. Als uitdaging voor de lezers had Ronald Rivest een geheime tekst vercijferd met behulp van een sleutel van 129 cijfers die hij gemaakt had door twee priemgetallen van 64 en 65 cijfers met elkaar te vermenigvuldigen. De twee priemfactoren hield hij geheim, maar hun product stond in het artikel uitgeschreven. Zou je de twee geheime priemfactoren kunnen achterhalen, dan zou je de geheime boodschap kunnen ontcijferen. Dat is ook precies wat Arjen Lenstra en zijn medewerkers gedaan hebben: met behulp van geavanceerde technieken uit de getallentheorie en een geweldige hoeveelheid rekenkracht op kleine en grote computers wisten ze het sleutelgetal van 129 cijfers in zijn priemfactoren te ontbinden.

Bij geheimschriften gaat het haast altijd om berichten of databestanden die je op een veilige manier van de ene plaats naar de andere plaats wilt transporteren via een onveilig kanaal: de telefoon, de fax, de email, een radioverbinding of wat dan ook. Het cryptosysteem RSA zorgt ervoor dat de boodschap voordat je hem verstuurt onleesbaar wordt voor onbevoegden. Dat onleesbaar maken noemen we vercijferen. Alleen de rechtmatige ontvanger zal de vercijferde boodschap weer kunnen ontcijferen. Daarvoor heeft hij een (natuurlijk geheime) ontcijfersleutel nodig.

Vercijferen niet geheim

Het gekke, en in zekere zin ook revolutionaire van RSA is, dat je de vercijfermethode helemaal niet geheim hoeft te houden. Dat hadden Rivest, Shamir en Adleman dan ook niet gedaan: in het artikel in Scientific American stond precies uitgelegd hoe ze hun boodschap hadden vercijferd, inclusief de vercijfersleutel die ze daarbij gebruikt hadden. Er zijn voor RSA echter altijd twee bij elkaar horende sleutels nodig: een vercijfersleutel en een ontcijfersleutel. Je kunt RSA zien als een soort schatkist waar je een schat in doet. Met de vercijfersleutel draai je de kist op slot. Maar met die vercijfersleutel kun je de kist daarna niet meer openen! Daarvoor is namelijk een andere sleutel nodig, de ontcijfersleutel. Het vreemde is dat zelfs al heb je een vercijfersleutel in je bezit, je daarmee nog geen ontcijfersleutel kunt fabriceren. Kortom, het geheim blijft ontoegankelijk, zelfs als je weet hoe het vercijferen in zijn werk is gegaan! Dat klinkt allemaal volslagen onlogisch, maar toch is het zo.

Ontbinden is kraken

Eigenlijk moeten we dit een beetje nuanceren. Bij RSA is het belangrijkste deel van de vercijfersleutel een getal m, de zogenaamde modulus, die het product is van twee grote priemgetallen p en q. Een beetje slordig gezegd (elders in dit nummer geven we alle details) kun je stellen dat je bij het vercijferen alleen maar de modulus m gebruikt, maar bij het ontcijferen de priemgetallen p en q. Als je die twee priemgetallen kent, kun je de boodschap ontcijferen.

Nu is het ontbinden van een groot getal in principe helemaal niet moeilijk: probeer maar of het deelbaar is door alle kleinere getallen. Dat zijn er eindig veel, dus op zeker moment zul je de ontbinding vinden. Alleen, wat is ‘op zeker moment’? Zelfs met de allerbeste ontbindingsmethoden die er thans bestaan en met de allerkrachtigste supercomputers ter wereld kan het ontbinden van getallen van zo’n tweehonderd cijfers meer tijd kosten dan de leeftijd van het heelal! Als je dus twee priemgetallen p en q van ongeveer honderd cijfers elk kiest en je maakt het product m = p x q bekend zonder p en q zelf te verklappen, kun je er gerust op vertrouwen dat voorlopig niemand die ontbinding kan vinden.

Hoe veilig is RSA?

Daarmee komen we op de vraag of Arjen Lenstra met zijn ontbinding van de RSA-sleutel van 129 cijfers nu ook het hele cryptosysteem RSA naar de prullenbak verwezen heeft. Dat is allerminst het geval. Integendeel zelfs! Het principe van RSA staat nog steeds fier overeind, alleen weten we inmiddels dat een gebruiker er verstandig aan doet om zijn sleutels niet te klein te kiezen. Als je grote getallen in factoren kunt ontbinden, kun je RSA kraken, maar de hoeveelheid rekentijd die daarvoor nodig is, neemt voor zover we weten exponentieel toe met het aantal cijfers. Op dit moment staat het ontbindingsrecord voor grote willekeurige getallen op naam van onze landgenote Marije Elkenbracht-Huizing die bewezen heeft dat ze getallen tot 130 cijfers aan kan. Op 10 april 1996 maakte zij namelijk de ontbinding bekend van RSA-130, een prijsvraaggetal van 130 cijfers. Dat bleek het product te zijn van twee priemgetallen van 65 cijfers elk. Ook daaraan was vele maanden rekenen op honderden computers voorafgegaan. De volgende uitdaging is een prijsvraaggetal van 140 cijfers, maar die klus lijkt voorlopig nog veel te moeilijk te zijn. Er bestaan grotere getallen die gefactoriseerd kunnen worden, maar die zijn dan wel speciaal, zoals het recordgetal van 180 cijfers uit het decembernummer.

Bij RSA kan iedere gebruiker zijn eigen sleutels kiezen. Het record van Marije heeft aangetoond dat sleutels van hooguit 130 cijfers niet veilig meer zijn, ook al vergt het toch nog steeds een enorme investering om zo’n sleutel te kraken. Maar kies je sleutels van 200 cijfers of meer (en dat is bij RSA geen enkele probleem), dan hoef je je over het ontbinden daarvan niet veel zorgen te maken. Met alle thans bekende methoden is dat namelijk volstrekt ondoenlijk.

Geen garantie

Echter, een waterdichte garantie kunnen we niet geven. Er zijn twee gevaren. Het eerste is dat er een genie opstaat dat een volstrekt nieuwe ontbindingsmethode verzint die veel grotere getallen aan kan. Dan worden de tot nu toe gebruikte sleutels onbruikbaar, maar misschien dat we het systeem dan toch kunnen redden door over te gaan op nog veel grotere sleutelgetallen.

Het tweede gevaar is dat er een totaal andere manier gevonden wordt om RSA te kraken. We weten namelijk wél dat je de geheime sleutel kunt vinden als je het sleutelgetal kunt ontbinden, maar we weten niet of dat de enige manier is. Misschien zijn er ook nog andere methoden om RSA te kraken. Voor zover we weten heeft niemand zo’n manier gevonden, maar we hebben geen bewijs dat zo’n methode niet kan bestaan.

Openbare sleutels

We hebben al gezegd dat vercijferen en ontcijferen bij RSA met verschillende sleutels gebeurt, en dat je de ontcijfersleutel in de praktijk niet af kunt leiden uit de vercijfersleutel. Maar als je de ontcijfersleutel niet uit de vercijfersleutel kunt afleiden, dan is het ook niet nodig om die vercijfersleutel geheim te houden! Wanneer de schatkist op slot is gedaan, helpt de vercijfersleutel immers niet meer om hem te openen. Dat heeft tot gevolg dat het niet nodig is om geheime sleutels op een beveiligde manier van de zender naar de ontvanger te transporteren.

Iedere gebruiker kan zijn eigen sleutels fabriceren, en vervolgens zijn vercijfersleutel gewoon bekend maken, bijvoorbeeld door die op Internet te zetten; de gebruiker hoeft alleen maar zijn eigen ontcijfersleutel geheim te houden.

Wil je bijvoorbeeld een geheim bericht naar de redactie van Pythagoras sturen, dan zoek je onze openbare vercijfersleutel E_pyth op internet op (vercijferen heet in het Engels encryption, vandaar de letter E. Ontcijferen is decryption, en daarvoor gebruiken we dus de letter D). Met behulp van onze openbare vercijfersleutel vercijfer je je boodschap x. Dat vercijferde bericht noemen we E_pyth(x). Als het systeem inderdaad waterdicht is, kan geen enkele spion uit E_pyth(x) weer x afleiden. Geen enkele spion kan de boodschap weer ontcijferen, zelfs de afzender niet als hij de oorspronkelijke tekst vergeten zou zijn! Alleen de bezitter van de bijbehorende ontcijfersleutel D_pyth, en dat is de redactie, is daartoe in staat. Je kunt E_pyth(x) dus veilig per briefkaart, fax, telefoon of email versturen; voor afluisteren hoef je niet bang te zijn. Alleen de redactie kan het bericht ontcijferen door er de geheime ontcijfersleutel D_pyth op los te laten: D_pyth(E_pyth(x)) = x.

Dat lijkt allemaal nog een beetje op een spelletje, maar denk eens aan berichten die rapporteurs van Amnesty International uit dictatoriale gebieden moeten sturen naar het hoofdkwartier van hun organisatie. Daarbij kan het letterlijk van levensbelang zijn dat onbevoegden die berichten niet kunnen ontcijferen!