Reuzengetal bezwijkt na zeven en worteltrekken

Woensdagavond 10 april brak de wiskundige Marije Elkenbracht-Huizing van het Centrum voor Wiskunde en Informatica (CWI) te Amsterdam het wereldrecord getallen ontbinden.

RSA-130, een getal van 130 cijfers, gaf na een rekenstap van 68 uur op de Cray C90 supercomputer van het Amsterdamse rekeninstituut SARA, gevolgd door worteltrekken op het zeer krachtige Power Challenge werkstation van het CWI, zijn twee samenstellende priemfactoren van elk 65 cijfers prijs. Net als bij RSA-129, dat april 1994 door Arjen Lenstra op de computer van Bell Communications Research (Bellcore) in Morristown werd gekraakt, ging er een 'parallelle' aanloopfase aan vooraf, waarbij iedereen met een workstation via het World Wide Web kon meedoen.

RSA-getallen (genoemd naar de uitvinders Rivest, Shamir en Adleman) vormen het hart van een cryptografisch systeem om informatie onleesbaar te maken voor onbevoegden en zo geheime boodschappen te kunnen verzenden. Het werkt als volgt. Eerst kiest een gebruiker, bijvoorbeeld een bank, twee priemgetallen: getallen die slechts deelbaar zijn door één en door zichzelf. Hun product is openbaar, de priemgetallen zelf blijven geheim. Wie de bank een geheime boodschap wil sturen, 'vercijfert' deze met behulp van het vrijgegeven product. Ontcijferen is voorbehouden aan degene die de priemgetallen kent. Sinds de oprichting in 1978 van RSA Data Security Inc. ruikt ontbinden in factoren, tot dan toe het domein van de zuivere wiskunde, naar geld.

Op dit moment is het snelste algoritme (een stapsgewijze oplosmethode die op een computer kan 'draaien') om een reuzengetal te ontbinden de Number Field Sieve (NSF), waarvoor John Pollard in 1988 het idee leverde. Deze 'zeef' werkt tien keer zo snel als de Multiple Polynomial Quadratic Sieve (MPQS) die Arjen Lenstra bij het kraken van RSA-129 gebruikte. Bij getallen van nog meer cijfers is dat voordeel alleen maar sterker. Marije Elkenbracht-Huizing: “Had ik het NSF-algoritme op één 100 MHz Pentiumprocessor gedraaid, dan was ik 18 jaar rekentijd kwijt geweest. Met tweehonderd verspreide werkstations krimpt dat getal tot een paar maanden. Om een idee van de ontwikkelingen te geven: 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.”

Homepage

Het zeven is op Bellcore geïmplementeerd en door Jim Cowie geschikt gemaakt voor gebruik op het World Wide Web. Marije Elkenbracht-Huizing: “Iedereen kon de afgelopen maanden een http-adres intypen en kreeg dan een homepage voor zijn neus met informatie, elektronische aanmeldingsformulieren en uitleg. Wie zich opgaf kreeg een zeeftaak toegestuurd, inclusief het programma, en het resultaat van zo'n deelberekening ging automatisch retour Bellcore.”

Ongeveer 30 procent van dit voorwerk is verricht op het CWI, Elkenbracht-Huizing's thuisbasis. De promovenda, die wordt begeleid door de getaltheoreticus prof.dr. R. Tijdeman van de Rijksuniversiteit Leiden en dr. H.J.J. te Riele, hoofd numerieke getaltheorie van het CWI, kon in de avonduren en in de weekends over 63 werkstations beschikken. Elkenbracht-Huizing: “In de periode augustus-december 1995 is bij ons 56.600 uur gerekend. Maar ook kleinere instituten leverden werkstations, zoals de Hogeschool Rotterdam. Afgelopen januari heeft Arjen Lenstra 400 megabyte aan nuttige getallenparen uit de totaalverzameling geselecteerd, op band gezet en per post naar ons toegestuurd. Toen kon op de Cray het zware werk beginnen.”

Dat 'zware werk' behelsde het manipuleren van een matrix van 3,5 miljoen keer 3,5 miljoen nullen en enen, die aangeven welke priemgetallen in de gezeefde getallenparen voorkomen. Elkenbracht-Huizing: “Die klus moet op de Cray, en het is maar goed dat die van SARA tot de wereldtop behoort. Er bestond al een algoritme, maar de benodigde programmatuur is door Peter Montgomery tijdens zijn verblijf op het CWI ontwikkeld en geïmplementeerd. Vervolgens heb ik dat programma met hem bijgevijld, zodat het sneller werkt en minder geheugen in beslag neemt.”

Als laatste stap in de ontbinding is volgens een iteratief recept van opnieuw Peter Montgomery twee keer de wortel getrokken uit een reusachtig algebraïsch getal, op de manier zoals (1+3a) de wortel is van 1+6a+9a. Zo'n worteltrekking, die twee dagen in beslag neemt, levert òf de beide priemfactoren op, òf het getal 1 en het uitgangsgetal, beide mogelijkheden met kans 0,5. Na twee mislukte pogingen was het vorige week woensdag raak en gaf RSA-130 zich gewonnen. Resultaat: 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 = 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

Nu de ontbindklus is geklaard - RSA Data Security had een premie van 13.000 dollar uitgeloofd - is het tijd het volgende getal uit de challenge list bij de hoorns te vatten: RSA-140. Nieuwe wiskundige en technische hulpmiddelen zijn daarvoor onontbeerlijk en Marije Elkenbracht-Huizing, die eind dit jaar op haar onderzoek naar factoriseren hoopt te promoveren, durft zich over een termijn niet uit te laten. “Het voorwerk zal wel lukken, World Wibe Web-liefhebbers genoeg. En hoe langer je zeeft, hoe kleiner de matrix waarmee je verder moet. Toch zal de beslissende stap op de Cray problemen geven, daar loop je tegen grenzen op. Een snellere computer met een groter geheugen helpt, maar ook zal het algoritme fundamenteel beter moeten. Het programma kan beter en ik heb al een variant op de NSF gemaakt, dus wie weet.”

Informatie op het internet: http://www.npac.syr.edu/factoring.html