Zijn raadsel oplossen kostte 80 biljoen stappen en duurde drieënhalf jaar

Wiskunde De Belg Bernard Fabrot stuitte in 2014 bij toeval op een wiskundepuzzel uit 1999. Met slim programmeerwerk loste hij het raadsel van Ronald Rivest op.

Ronald Rivest stelde het raadsel op in 1999. Hij verwachtte destijds dat het 35 jaar zou duren voor de puzzel zou zijn opgelost.
Ronald Rivest stelde het raadsel op in 1999. Hij verwachtte destijds dat het 35 jaar zou duren voor de puzzel zou zijn opgelost.

Woensdag was het feest op het Massachusetts Institute of Technology (MIT) in het Amerikaanse Cambridge. Ruim twee weken geleden kondigde de persafdeling van het MIT aan dat de zogenoemde LCS35-puzzel uit 1999 is opgelost door de Belg Bernard Fabrot. Deze week reisde Fabrot af naar het MIT, waar hij zijn oplossing presenteerde.

De LCS35-puzzel, bedacht door de Amerikaan Ronald Rivest, is geïnspireerd op het RSA-algoritme, waarvan Rivest een van de uitvinders is. Dit algoritme is wereldwijd de meest gebruikte methode om online communicatie te versleutelen. Het succes van het algoritme is te danken aan het feit dat het eenvoudig is om twee grote priemgetallen met elkaar te vermenigvuldigen, terwijl het praktisch ondoenlijk is om, gegeven het product, de twee priemgetallen te achterhalen waaruit dat product is samengesteld.

Het eerste getal is gigantisch

Om de cryptopuzzel van Rivest te begrijpen is niet meer nodig dan een paar basisrekenvaardigheden. Rivest gaf twee getallen. Het eerste getal is gigantisch: als je het helemaal zou uitschrijven, ligt het aantal cijfers ongeveer in de orde van grootte van 102.400.000.000.000. Het tweede getal, dat het product van twee priemgetallen is, heeft ‘slechts’ 616 cijfers. De bijbehorende opdracht luidde: bereken de rest na deling van het eerste getal door het tweede getal.

Nadat Fabrots computer bijna drieënhalf jaar had gerekend, had hij de oplossing: die rest is een getal van ruim zeshonderd cijfers. Rivests geheime boodschap zat in deze rest verstopt. Fabrot moest nog wat laatste stappen uitvoeren, zoals het omzetten van de rest in het binaire stelsel, om uiteindelijk tot een cijferreeks te komen waarmee via codering een bericht kon worden gevormd. Dat bericht begint met de zin „!!! Happy Birthday LCS !!!”.

Is het voor een computer echt zo moeilijk om die twee getallen van Rivest op elkaar te delen? Ja, sterker nog: het is een helse klus. Alleen al om dat gigantische getal op te slaan, zijn vele terabytes computergeheugen nodig. En dan is er nog geen enkele berekening gedaan. Geen computer die daar aan kan beginnen.

Sneller met priemfactoren

Er is echter nog een andere methode om tot de oplossing te komen. Eén waarbij je stapje voor stapje, rekenend met relatief kleine getallen, tot de oplossing komt. Het reuzengetal in Rivests puzzel kun je schrijven als ‘2 tot de macht 2 tot de macht 79.685.186.856.218’. In plaats van dit getal door Rivests 616-cijferige getal te delen, kun je het probleem ook opdelen in 79.685.186.856.218 stappen. Elke stap bestaat uit het berekenen van een kwadraat en het bepalen van de rest na deling door het 616-cijferige getal.

Voor het veel kleinere deeltal ‘2 tot de macht 2 tot de macht 4’ en de deler 33 is het stappenplan uitgevoerd in de illustratie hiernaast. Er bestaat een wiskundige techniek – gebruikmakend van onder meer de zogeheten ‘Bézout-identiteit’ en de ‘Chinese reststelling’ – om die stappen snel uit te voeren. Echter: om die techniek toe te passen, moet bekend zijn uit welke priemgetallen de deler bestaat.

In het voorbeeld is dat geen probleem: 33 is het product van 3 en 11. Maar de deler in Rivests opgave is met 616 cijfers een véél groter getal. Een efficiënte methode om zo’n groot getal in priemfactoren te ontbinden, is niet bekend. Rivest hield die priemgetallen uiteraard geheim; hij zei alleen dat het er twee waren. Dat maakt het oplossen van de LCS35-puzzel zo moeilijk.

Rivest verwachtte dat de oplossing 35 jaar op zich zou laten wachten

Ook Fabrot kon die twee priemgetallen niet achterhalen. Toch heeft hij die bijna 80 biljoen stappen kunnen uitvoeren, dankzij slim programmeerwerk. „Mijn programma telt maar achttien regels code”, vertelt de 46-jarige Franstalige Belg aan NRC. Hij deed eerst enkele tests, gebruikmakend van verschillende programmeertalen. Fabrot: „Uiteindelijk koos ik voor de taal C en een zeer snelle softwarebibliotheek, GMP geheten, die gespecialiseerd is in grote gehele getallen.”

Van beroep is Fabrot software-ontwikkelaar. Eind 2014 stuitte hij toevallig op de LCS35-puzzel. In 2015 kocht hij een computer met een razendsnelle processor. „Die computer kan 750.000 stappen per seconde uitvoeren”, zegt Fabrot. Het is vervolgens een simpele rekensom om te bepalen hoeveel tijd de computer nodig heeft voor alle benodigde stappen: 79.685.186.856.218 / 750.000 = 106.246.916 seconden, oftewel zo’n 3,37 jaar – mits de computer zonder onderbreking werkt. Fabrot wist vooraf dus exact wanneer zijn computer de monstertaak zou hebben volbracht. Toen Fabrot de oplossing kende, wist hij ook de twee geheime priemgetallen. Rivests boodschap bevatte namelijk informatie waarmee het 616-cijferige getal kon worden gefactoriseerd.

Eerder dan verwacht

Rivest presenteerde zijn puzzel in 1999 ter gelegenheid van het 35-jarig bestaan van het Laboratory for Computer Science (LCS) van het MIT. Een tijdcapsule met curiosa uit de computergeschiedenis werd ergens in het magazijn van het LCS opgeborgen, en zou na nog eens 35 jaar, in 2034 dus, geopend mogen worden. Of eerder, namelijk als iemand erin zou slagen de LCS35-puzzel op te lossen.

Rivest ontwierp zijn puzzel slim. De bijna 80 biljoen stappen moeten na elkaar gedaan worden, omdat voor elke stap het resultaat van de voorgaande stap nodig is. Het is onmogelijk de puzzel op te splitsen in een aantal onafhankelijke deeltaken. Het is daarom uitgesloten sneller tot de oplossing te komen door verschillende computers tegelijkertijd te laten draaien.

Rivest verwachtte destijds dat het zo’n 35 jaar zou duren voordat iemand met de oplossing kwam. Deze schatting was gebaseerd op de verwachte snelheid van toekomstige computers. In 2011 stelde Rivest zijn schatting bij. In het Britse tijdschrift New Scientist, dat toen een artikel aan de puzzel wijdde, zei hij: „De rekenkracht van computers is niet zo snel toegenomen als voorspeld.” De beroemde cryptospecialist en MIT-professor zat er dus naast. „Er zijn hardware- en softwarevooruitgangen geweest die verder gaan dan wat ik in 1999 had voorspeld”, zegt Rivest nu.

Woensdag werd de tijdcapsule op het MIT geopend. De capsule zelf was een sculptuur in de vorm van een gigantische papieren zak, ontworpen door Frank Gehry, de beroemde architect die onder meer het Guggenheim Museum in Bilbao ontwierp. Een greep uit de inhoud van de capsule: een schaakprogramma uit 1962 van Alan Kotok, het X Window System uit 1983, een toolkit uit 1998 voor het opzetten van online communities, en het City Scanning Project van Seth Teller, een pionier op het gebied van driedimensionale reconstructies van gebouwen.