Honderd dollar voor twee priemgetallen

Een weddenschap in Scientific American uit 1977 is gewonnen door de Nederlander Arjen Lenstra met de hulp van een legertje computeramateurs verdeeld over de hele wereld. Hij brak een geheime code: een getal van 129 cijfers.

Een symbolische prijs van honderd dollar stond sinds 1977 op het kraken van een geheime code. Destijds schatte men dat het ontcijferen ervan zeker 40 biljard jaar computertijd zou kosten. Maar door 1700 computers over de hele wereld te laten samenwerken kon de klus nu in een half jaar worden geklaard.

Eergisteren werd het geheim ontsluierd. De Nederlandse wiskundige dr. Arjen K. Lenstra van Bell Communications Research in Morristown in de Verenigde Staten wist de code te breken door de sleutel, een getal van 129 cijfers, in twee priemfactoren te ontbinden. Wat zijn de consequenties voor supergeheime cryptografische systemen?

In 1977 introduceerden de wiskundigen Ronald Rivest, Adi Shamir en Leonard Adleman een nieuw cryptosysteem waarbij geheime boodschappen eerst omgezet worden in getallencode, die daarna wordt vercijferd door de getallen een voor een te onderwerpen aan modulair machtsverheffen, een zekere wiskundige berekening die met behulp van computers snel kan worden uitgevoerd. Het merkwaardige van dit cryptosysteem RSA(zo genoemd naar de initialen van de ontwerpers) is dat vercijferen een soort eenrichtingsberekening is: zelfs als je precies het rekenrecept kent, inclusief de sleutelgetallen waarmee het moet worden uitgevoerd, dan nog is het praktisch onmogelijk om uit een vercijferd getal het oorspronkelijke getal terug te halen. Ontcijferen gaat daarom met behulp van een andere sleutel dan vercijferen, en zolang die andere sleutel maar geheim blijft, kunnen spionnen de boodschap niet achterhalen.

Als sleutelgetal van RSA wordt altijd het produkt gebruikt van twee grote priemgetallen. Dat produkt, de zogenaamde modulus, hoeft niet geheim te blijven, maar de twee priemgetallen waaruit het is samengesteld wèl. Zou een spion namelijk die priemgetallen kennen, dan zou hij daarmee de ontcijfersleutel kunnen fabriceren. Hoe groter de modulus is, hoe meer rekenwerk het ontbinden ervan kost: de benodigde rekentijd groeit exponentieel met het aantal cijfers van het getal. Dat betekent dat vanaf een zekere grootte het ontbinden in factoren praktisch onmogelijk wordt. Omdat er geen andere methoden bekend zijn om RSA te kraken, lijkt het systeem veilig zolang de modulus maar groot genoeg is. Cryptogramgetal

Maar wat is 'groot genoeg'? Grenzen verschuiven. In 1977, toen RSA werd geïntroduceerd, schreef Martin Gardner er een artikel over in Scientific American. Daarin publiceerde hij als uitdaging voor zijn lezers een sleutelgetal van 129 cijfers en een 'cryptogramgetal', dat wil zeggen de vertaling in RSA-geheimschrift met behulp van die sleutel van een stukje Engelse tekst. De vercijfer- en ontcijfermethodes werden in het artikel helemaal uitgelegd, en het enige dat de lezer hoefde te doen om de Engelse tekst terug te vinden, was het ontbinden van het sleutelgetal in priemfactoren. Rivest, Shamir en Adleman, die het cryptogram hadden aangeleverd, zeiden er ook nog bij dat die factoren twee priemgetallen waren van 64 en 65 cijfers, maar de priemgetallen zelf hielden ze geheim. Voor de eerste die het cryptogram zou weten te ontcijferen, loofden ze een symbolisch bedrag van honderd dollar uit.

In 1977 schatte Ronald Rivest de tijd die nodig zou zijn voor het kraken van het sleutelgetal, dat inmiddels bekend staat als RSA-129, op 40 biljard jaar, en velen meenden daarom destijds dat die honderd dollar wel nooit geïnd zouden worden. Maar inmiddels heeft de technologie niet stilgestaan, terwijl ook de wiskundigen niet stil hebben gezeten. Het gevolg is dat Rivest reeds zeventien jaar na dato de honderd dollar van de bank kon halen om ze aan codebreker Arjen Lenstra te overhandigen. Die zal zijn prijs echter moeten delen met ongeveer 1700 computerhobbyisten over de hele wereld die via het internationale computernetwerk Internet allemaal hun steentje aan de ontbinding hebben bijgedragen. Kwadratische zeef

Het project ging vorig jaar van start op initiatief van Paul Leyland van de universiteit van Oxford, Derek Atkins van het Massachusetts Institute of Technology en Michael Graff van de Iowa State University, die via e-mail vrijwilligers begonnen te werven voor een ontbindingsproject. Vooraf hadden zij contact gezocht met Arjen Lenstra, die toen ook al houder van een ontbindingsrecord was: in de zomer van vorig jaar had hij een 'moeilijk' getal van 120 cijfers in factoren ontbonden. Toen Lenstra van de plannen van het drietal hoorde, suggereerde hij een aanval op RSA-291: 'Dan heb je iets dat echt de moeite waard is'. Lenstra leverde het computerprogramma, Leyland, Atkins en Graff verzorgden de organisatie, en in augustus vorig jaar begon het project te lopen.

Voor een belangrijk deel bestaat de ontbindingsmethode waarmee men thans werkt, de zogenaamde kwadratische zeef, uit gigantisch veel kleine deelberekeningen, die parallel op verschillende computers kunnen worden uitgevoerd. Dat is ook precies wat er het afgelopen half jaar gebeurd is: alle deelnemers aan het project hebben hun computers in de vrije uren laten draaien om gegevens te verzamelen, en die vervolgens via e-mail naar Derek Atkins op MIT gestuurd. Ruim een maand geleden was er genoeg materiaal verzameld. Toen kwam de tweede fase: het in elkaar passen van de puzzel. Dat was werk voor Lenstra alleen: die moest daarvoor een enorm stelsel vergelijkingen oplossen: zo'n 550 duizend vergelijkingen met even zovele onbekenden. Dat stop je niet zo maar even in een computer, zelfs niet als dat de Massively Parallel supercomputer is van Bellcore, die uitgerust is met niet minder dan zestienduizend 4-bits processoren. Zo'n berekening vergt dagen computertijd, en dat moet dus heel zorgvuldig worden voorbereid. Bij zulke grote rekenpartijen moet je bovendien ook nog bedacht zijn op onverklaarbare hardware-storingen die de zaak in het honderd laten lopen zodat je dan weer opnieuw kunt beginnen. De rekenduiveltjes waren het project echter gunstig gezind: toen de operatie eenmaal gestart was, rolde na drie dagen rekenen het resultaat eruit: de twee priemfactoren van RSA 129 waren gevonden. Hoe veilig is RSA?

Wat zegt het nieuwe record nu over de veiligheid van RSA als zodanig? Merkwaardigerwijs toont het eerder de kracht ervan dan de zwakte. We weten nu dat sleutelgetallen van 130 tot 150 cijfers niet meer absoluut veilig zijn, maar ook dat het kraken ervan een enorme hoeveelheid rekentijd kost. Alleen voor geheimen die zeer veel geld waard zijn en die vele jaren geheim moeten blijven, zijn zulke sleutels dus niet meer veilig. Maar het RSA-systeem als zodanig is niet in gevaar: het kan net zo goed met veel grotere sleutelgetallen draaien, alleen neemt de verwerkingssnelheid dan wat af. Volgens dr. Andrew Odlyzko, een expert die werkzaam is op het AT&T Bell laboratorium in Murray Hill, zijn er zeker bedrijven en overheidsinstellingen die de computercapaciteit kunnen opbrengen om sleutels van 150 cijfers te kraken. Hij beveelt daarom thans sleutels aan van minstens 230 cijfers voor topgeheimen. Op Internet wordt door sommige groepen gewerkt met het cryptosysteem Pretty Good Privacy (PGP) van de Amerikaan Philip Zimmermann, waarin RSA een van de componenten is. Deelnemers kunnen daar hun sleutellengte zelf kiezen met een bovengrens van duizend bits, dat wil zeggen sleutelgetallen van zo'n 300 decimale cijfers. Je hebt voor het fabriceren van zulke sleutelgetallen priemgetallen nodig van ongeveer 150 cijfers, maar dat is geen probleem: er zijn snelle methodes beschikbaar om zulke priemgetallen te vinden. Kies twee van die priemgetallen, houd ze geheim maar maak hun produkt, een getal van ongeveer driehonderd cijfers, bekend en je hebt een bouwpakket voor een voorlopig nog onkraakbaar cryptosysteem in handen (zie het kader 'Hoe werkt RSA?' elders op deze pagina). De overheid, die naar het schijnt het liefste alle geheimschriften zou willen verbieden, zal er niet blij mee zijn, maar zo simpel liggen de zaken nu eenmaal. Zij kan slechts hopen dat de mafia geen wiskunde studeert.

Kader 1

Lammergier met zwakke maag

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

=

3490 52951 08476 50949 14784 96199 03898 13341 77646 38493 38784 39908 20577

x

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

Op de basisschool gaat het bij het rekenen meestal andersom: twee getallen zijn gegeven, en je moet hun produkt uitrekenen. Maar hier was de omgekeerde opgave honderd dollar waard: het bovenste getal, een getal van 129 cijfers, was gegeven, en verder was gegeven dat het samengesteld was uit twee priemgetallen van respectievelijk 65 en 64 cijfers. De puzzel was: vind die twee priemgetallen. Zeventien jaar lang was dat niemand gelukt, maar eergisteren heeft dr. Arjen K. Lenstra de ontbinding bekend gemaakt en de honderd dollar opgestreken. Die ontbinding in priemfactoren kon Lenstra gebruiken om een geheime boodschap te ontcijferen die in een ander groot getal, deze keer van 128 cijfers, verborgen was. De vercijferde boodschap luidde:

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

en de ontcijfering ervan is:

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 het getal maar vast in groepjes van twee cijfers hebben verdeeld, want de lettercodering was 01 = A, 02 = B, 03 = C, ....., 26 = Z en 00 is een spatie. De boodschap in letters luidde dus: 'The magic words are Squeamish Ossifrage',waarbij de laatste twee woorden zoveel betekenen als 'lammergier met zwakke maag'. Met opzet hebben de makers van de boodschap enigszins 'bizarre' woorden gekozen, om ieder ontcijfering door gokken of proberen bij voorbaat kansloos te maken.

Kader: Hoe werkt RSA?

kader Het cryptosysteem RSA werkt met twee bij elkaar horende sleutels: een vercijfersleutel en een ontcijfersleutel. Ze worden gefabriceerd met behulp van twee grote priemgetallen p en q die geheim moeten blijven. Hun produkt m = p x q, de modulus, wordt zowel bij het vercijferen als het ontcijferen gebruikt. Daarnaast zijn er nog twee andere getallen nodig, een vercijferexponent e en een ontcijferexponent d, die samen moeten voldoen aan de voorwaarde dat hun product d x e na deling door het getal (p-1)(q-1) rest 1 geeft. Het is niet moeilijk om zulke getallenparen e en d te vinden; de methode daarvoor is al afkomstig van Euclides (300 v. Chr.). Bij het vercijferen wordt de tekst eerst op een standaardmanier (die niet geheim hoeft te zijn) omgezet in een cijferreeks. Deze wordt opgesplitst in blokken, zodat er getallen ontstaan die allemaal kleiner zijn dan de modulus m. Vercijferen geschiedt vervolgens blok voor blok met de formule

y = xe modulo m

waarbij dus een blok x wordt omgezet in een blok y. Dit is het zogenaamde modulaire machtsverheffen, een soort klokrekenen waarbij je telkens de rest neemt bij deling door m. Met de computer kan zo'n berekening zeer snel worden uitgevoerd, zelfs als de modulus m en de exponent e zeer grote getallen zijn. Als m maar groot genoeg is, is het praktisch onmogelijk om x weer terug te vinden uit y, zelfs als m en e bekend zijn. Voor het ontcijferen moet men daarom gebruik maken van een andere formule. Die heeft wel dezelfde vorm, maar maakt gebruik van een andere exponent, de ontcijferexponent d:

x = yd modulo m.

Uit een stelling van de achttiende-eeuwse wiskundige Leonhard Euler volgt dat het resultaat hiervan inderdaad weer de oorspronkelijke x is.

Rivest, Shamir en Adleman hadden voor hun prijsvraag in het artikel van Martin Gardner de modulus m, de vercijferexponent e en de vercijferde boodschap y bekend gemaakt. De modulus m was het getal van 129 cijfers; als vercijferexponent e hadden zij het getal 9007 genomen en hun vercijferde boodschap y, een getal van 128 cijfers, staat elders op deze pagina in een apart kader vermeld. Arjen Lenstra kraakte de code door de priemfactoren p en q van m te achterhalen. Daarmee kon hij het getal (p-1)(q-1) berekenen, en vervolgens (met de methode van Euclides) de ontcijferexponent d. Ten slotte berekende hij hiermee via modulair machtsverheffen de oorspronkelijke boodschap.

RSA als Public Key System

Je kunt RSA op de 'traditionele' manier als geheimschriftsysteem gebruiken: twee gebruikers die geheime boodschappen willen uitwisselen sturen elkaar via een beveiligd kanaal eerst de sleutels, waarna ze elkaar vercijferde berichten kunnen sturen over de radio, de fax, Internet of welk ander openbaar communicatiekanaal ook. Maar omdat vercijferen en ontcijferen met verschillende sleutels gebeurt, is er eigenlijk geen enkele reden om de vercijfersleutel geheim te houden: zelfs een spion die deze sleutel kent, kan daarmee nog geen vercijferde berichten achterhalen. Dat betekent dat er ook geen sleuteltransport via beveiligde kanalen plaats hoeft te vinden als iedereen maar zijn eigen sleutelpaar heeft. Alle vercijfersleutels kunnen gewoon openbaar gemaakt worden. Zo ontstaat een public key cryptosysteem. Correspondenten van de Redactie Wetenschappen van deze krant waar ook ter wereld zouden bijvoorbeeld met behulp van de openbare RSA-sleutelgetallen van de redactie (dat wil zeggen de modulus en de vercijferexponent) hun berichten vercijferd naar Rotterdam kunnen sturen. Alleen met de geheime ontcijferexponent kunnen die berichten daar dan weer worden ontcijferd. In het algemeen moet je dus in zo'n public key system berichten altijd vercijferen met de openbare sleutel van degene voor wie het bericht bestemd is. Alleen hij kan het vercijferde bericht dan met zijn secret key weer ontcijferen.

    • Jan van de Craats