Getallenkraker Arjen Lenstra

Bij beveiliging van communicatie over internet  (netwerken) worden priemgetallen gebruikt (getallen die alleen door 1 of zichzelf deelbaar zijn). De truc is daarin gelegen dat het voor een computer simpel is om twee grote priemgetallen te vermenigvuldigen, maar heel lastig is om van grote getallen (dan hebben we het over getallen van honderden cijfers) de factoren te berekenen. Die computers schijnen daar echter steeds minder moeite mee te hebben. Een groep aan de technische hogeschool in het Zwitserse Lausanne onder aanvoering van de Nederlander Arjen Lenstra  heeft een getal gefactoriseerd  van 1024 bits (pdf-bestand), zij het dat ze een iets simpeler getallensysteem onderzochten dan de zogeheten RSA-getallen die bij de beveiliging worden gebruikt. In ieder geval is dat een nieuw record.

Je kunt alle niet-priemgetallen krijgen door priemgetallen met elkaar te vermenigvuldigen, de zogeheten factoren van een getal. Elk RSA-getal is het product van twee priemgetallen. Het factoriseren is het omgekeerde proces: het ‘ontleden’ in priemgetallen. Hoe lang computers moeten knagen wordt uitgeprobeerd op grote zogeheten RSA-getallen. Hoe langer een computer daarmee bezig is, hoe veiliger het door RSA-getallen beschermde systeem.
Het ontbinden in factoren (factoriseren) is voor een computer een gigantische klus.  Arjen Lenstra en collega’s ontwikkelden in Lausanne daarom een factoriseringsfabriek, waarmee getallen tegelijk konden worden ‘gekraakt’. Deze techniek, die in de jaren ’90 is opgezet, bespaart tijd en moeite door een gigantische lijst van vergelijkingen van te voren op te lossen voor alle te kraken getallen en vervolgens verder te rekenen aan één getal. Die techniek op RSA-getallen uitproberen is nu nog te lastig en Lenstra c.s. gingen hun ‘kunsten’ botvieren op de zogeheten Mersenne-getallen (2ⁿ-1: machten van 2 min 1). Als test, want Mersenne-getallen worden niet in de cryptografie gebruikt.
Ze begonnen in 2010 met de factorisering  van 17 getallen. Daarvan hebben ze er nu 10 ontbonden in factoren. Dat zou ongeveer gelijk staan met 2000 jaar rekenen op een geavanceerde pc en het zou in de helft van de tijd zijn gebeurd dan wanneer elk getal apart was gefactoriseerd. Het hoogste getal dat gefactoriseerd werd was 2¹¹⁹³-1. Dat is een record. Dat getal komt ruwweg overeen met een RSA-getal dat bestaat uit 1024 enen en nullen (bits), hoewel RSA-getallen moeilijker te kraken zijn. Begin dit jaar werd aangegeven dat de 1024 bits-getallen worden verlaten. 2048 bits is nu de norm.

Het vorig record stond ook op naam van Lenstra c.s. In 2010 factoriseerden  ze een getal van 768 bits (wat overeenkomt met een getal van 232 cijfers in het tientallig stelsel). In 1990 kraakte hij een 512-bits RSA-getal, reden om de getallen te vergroten tot 1024 bits. Volgens Lenstra is er wel werk aan de winkel, maar er zou geen reden tot zorg zijn.

Bron: New Scientist