(12167 +1)/13 door de zeef

Wiskundigen in Amsterdam hebben een getal van 180 cijfers ontbonden in twee priemgetallen. Het vissen in de cijferzee vergde nog geen twee weken....

MARTIJN VAN CALMTHOUT

HET GETAL 35 is het product van 5 en 7, de twee zogeheten priemfactoren omdat ze alleen nog door 1 en zichzelf deelbaar zijn. Maar hoe zit het met, noem eens iets,

12862480745292006410890272858478665047052244641713578041943468 14698101043793016009864587782936724194244003676117518184671309 49025218486854306250248762104794478806532579114244394693 ?

Heeft dit monstrueuze getal van 180 cijfers misschien ook priemfactoren?

Sinds medio vorige week luidt het antwoord bevestigend. Een groep wiskundigen van het Centrum voor Wiskunde en Informatica (CWI) in Amsterdam heeft twee getallen van 75, respectievelijk 105 cijfers lang gevonden die aan het signalement voldoen. Ze zijn priemgetal en met elkaar vermenigvuldigd geven ze het gevraagde monstergetal.

'Twaalf dagen hebben we erover gedaan en eigenlijk was dat wat sneller dan we hadden gehoopt', zegt dr. H. te Riele van het CWI, onder wiens leiding het resultaat werd geboekt. Het snelle kraken van een getal van 180 cijfers is in alle opzichten een record. Het vorige was 'slechts' 167 cijfers lang en vergde bovendien twee maanden rekenen door een legioen onderzoekers die via Internet hun computers koppelden.

Dat lijkt allemaal hobbyisme, maar is het niet. De vorderingen van de wiskundigen geven aan hoe veilig de cryptografische technieken zijn waarmee vertrouwelijke gegevens tegenwoordig worden beschermd, bijvoorbeeld in de bankwereld.

Ditmaal volstond een legertje van 85 krachtige bureaucomputers van CWI-medewerkers, zogeheten workstations, waarop de getallenkrakers via het interne netwerk mochten rekenen als de gebruiker er even niet achter zat. Alleen voor de beslissende laatste stappen was nog een kleine dag rekenen nodig op de Cray C90 supercomputer van het rekencentrum SARA, de buren van het CWI in de Watergraafsmeer in Amsterdam.

Welbeschouwd was de nieuwe kraak een peulenschil, zegt Te Riele. 'Dat ding ziet er wel uit als een willekeurige reeks telefoonnummers uit de gids, maar dat is het in dit geval niet.' Het getal is afkomstig uit een lange lijst van speciale getallen, de zogeheten Cunningham-catalogus, en kan worden geschreven als (12167 +1)/13. Voor getallen van die speciale structuur is het relatief gemakkelijk zoeken naar de grootste priemfactoren, al blijven de finesses voor een leek bijna ondoorgrondelijk.

De eenvoudigste methode om de priemfactoren van een gegeven getal te vinden, is het domweg te proberen. Is het getal deelbaar door 2, het kleinste priemgetal? Zo ja, is de rest deelbaar door 3? En door 5? Door 7, 11, 13, 17 enzovoorts? Maar zelfs met de snelste computers loopt de rekentijd binnen de kortste keren op tot meer dan de leeftijd van het heelal.

In de loop der jaren, maar vooral na de Tweede Wereldoorlog, zijn er geslepen wiskundige technieken bedacht om efficiënter te speuren naar priemfactoren. De getaltheorie wordt daarbij tot het uiterste benut, maar uiteindelijk geven de geheugencapaciteit en de rekensnelheid van de computers de doorslag. De mede door de Nederlander prof. dr. H. Lenstra ontwikkelde Number Field Sieve (NFS) wordt nu gezien als de krachtigste techniek die voorhanden is. De groep in Amsterdam heeft NFS nog aanzienlijk weten te stroomlijnen.

Met de NFS wordt het te kraken getal niet rechtstreeks uit elkaar gepeuterd, maar wordt het gebruikt om een mathematische zeeffunctie op te stellen, die aan elk geheel getal een unieke functiewaarde toekent. Wiskundig is aan te tonen dat er bepaalde priemfactoren aanwezig zijn als de functie welomschreven gedrag vertoont. Op die manier wordt de onmetelijke berg getallen die priemfactoren zouden kunnen zijn, efficiënt 'gezeefd' op geschikte kandidaten.

De speciale structuur van het nieuwe monstergetal 180 dicteert als vanzelf de keuze van de zeeffunctie die het efficiëntst zal werken, zegt Te Riele. 'Als je niets van een getal weet, duurt een kraak bijna zeker veel en veel langer.' Dat is de reden dat de grootste gekraakte cryptografische sleutel tot nog toe, het getal RSA-130, 'slechts' 130 cijfers lang is.

Het grote voordeel van de NFS-zeefmethode, is dat de klus over vele computers kan worden verdeeld. Elke computer onderzoekt de functie voor een deel van de gehele getallen, zonder dat hij daarover met de andere hoeft te communiceren. Uiteindelijk levert elke computer zijn resultaten aan een supercomputer, die ze ordent en met slimme bewerkingen de priemfactoren opspoort.

De Cray C90 supercomputer van SARA had daarvoor een uur of zestien nodig. Vorige week woensdag stonden de antwoorden op het beeldscherm en meldden Te Riele en de zijnen ze ogenblikkelijk via Internet aan collega's over de hele wereld.

Cryptografen zijn, ondanks de indrukwekkende resultaten uit Amsterdam, voorlopig nog veilig, denkt Te Riele. 'RSA-130 was destijds al een zware inspanning, terwijl in de praktijk nu al met getallen van tegen de 300 cijfers wordt versleuteld. Men moet zich vooral zorgen maken over de snelheid waarmee het kraken vordert, denk ik. Vijftien jaar geleden braken we ons nog het hoofd over getallen van twintig cijfers.'

Het grootste schrikbeeld, zegt de wiskundige, is evenwel dat cryptografen en wiskundigen iets cruciaals over het hoofd zien. Te Riele: 'Het is theoretisch niet uitgesloten dat er nog veel snellere kraaktechnieken bestaan die we nog niet hebben ontdekt. Sterker: misschien is zoiets al wel gevonden, maar houdt de ontdekker het geheim. Als hij kwaadwillend is, kan hij een reuzenslag slaan.'

Het CWI, haast hij zich, heeft zoiets niet in huis. 'Wij publiceren alles. Openbaarheid is ons bestaansrecht.'

Martijn van Calmthout

Meer over

Wilt u belangrijke informatie delen met de Volkskrant?

Tip hier onze journalisten


Op alle verhalen van de Volkskrant rust uiteraard copyright.
Wil je tekst overnemen of een video(fragment), foto of illustratie gebruiken, mail dan naar copyright @volkskrant.nl.
© 2022 DPG Media B.V. - alle rechten voorbehouden