Reuzengetal in Amsterdams onderzoekscentrum gekraakt

ROTTERDAM, 12 APRIL. In het Centrum voor Wiskunde en Informatica in Amsterdam is een nieuw record gevestigd op het gebied van het ontbinden van reuzengetallen. RSA-130, een getal van 130 cijfers, blijkt het product te zijn van twee priemfactoren (getallen die slechts deelbaar zijn door één en door zichzelf) van elk 65 cijfers. De slotfase van de ontbinding is gecoördineerd door de wiskundige Marije Elkenbracht-Huizing.

Het eigenlijke 'zware werk' werd voorafgegaan door een aanloopfase van enkele maanden waaraan iedereen met een voldoende krachtig 'werkstation' - en de mogelijkheid daar in de nachtelijke uren op te mogen rekenen - via het World Wide Web een bijdrage kon leveren. Deze 'parallelle' aanpak, die onder leiding stond van Arjen Lenstra van Bell Communications Research in Morristown, leverde een enorme tijdsbesparing op. Uitgaande van dit tussenresultaat (een verzameling ingedikte 'relaties' tussen getallen) is op de grote Cray computer van het Amsterdamse rekeninstituut SARA in totaal 68 uur gerekend, gevolgd door worteltrekkingen van twee dagen per stuk op een krachtig Power Challenge werkstation.

Na twee mislukte pogingen gaf RSA-130 zich afgelopen woensdagavond gewonnen. Zoals 91 geschreven kan worden als 7x13 en 437 als 23 x 19, is het getal 18070 82088 68740 48059 51656 16440 59055 66278 10251 67694 01349 17012 70214 50056 66254 02440 48387 34112 75908 12303 37178 18879 66563 18201 32148 80557 gelijk aan 45534 49864 67359 72188 40368 68972 74408 86435 63012 63205 06960 09990 44599 x 39685 99945 95974 54290 16112 61628 83786 06757 64491 12810 06483 25551 57243.

Altijd is getaltheorie gerekend tot het domein van de zuivere wiskunde. Maar sinds RSA-getallen (genoemd naar hun uitvinders Rivest, Shamir en Adleman) het hart vormen van een geavanceerd cryptografisch systeem om geheime boodschappen te verzenden, en instellingen als banken er dankbaar commercieel gebruik van maken, ligt dat anders. Steeds krachtiger computers, slimmere rekenmethodes, efficiënter beheer van de beschikbare geheugenruimte en vooral een parallelle aanpak zijn er de oorzaak van dat steeds grotere getallen voor kraken in aanmerking komen.

In 1977 loofde Ronald Rivest 100 dollar uit aan degene die RSA-129 zou kraken, in de verwachting dat er 40 biljard jaar rekentijd mee heen zou gaan. Twee jaar geleden werd de klus onder aanvoering van Arjen Lenstra geklaard. De toen gehanteerde methode is nu verbeterd en verfijnd.

Om te zien of de op dit moment gehanteerde priemgetallen van 200 cijfers nog wel voldoende veilig zijn, heeft RSA Data Security Inc. een prijsvraag uitgeschreven om steeds hogere getallen te kraken. De volgende in de reeks is RSA-140.