Persbericht Centrum Wiskunde & Informatica
Amsterdam, 8 januari 2010
Nieuw rekenrecord ontbinden in priemgetallen toont kwetsbaarheid belangrijke cryptografische sleutels
Onderzoekers van de Cryptology and Information Security groep van het
Centrum Wiskunde & Informatica (CWI) in Amsterdam hebben in samenwerking
met groepen uit Duitsland (BSI en de Universiteit van Bonn), Frankrijk
(INRIA Nancy), Japan (NTT) en Zwitserland (EPFL) een RSA-sleutel van
768-bits gebroken door de priemfactoren hiervan te vinden. Het nu
gevestigde nieuwe wereldrecord toont de kwetsbaarheid aan van 768-bits
RSA-sleutels.
In 1999 werd voor het eerst een 512-bits RSA-sleutel gekraakt en in 2005
een 663-bits RSA-sleutel. Als de trend van de afgelopen tien jaar zich
voortzet betekent dit dat de huidige standaard van 1024-bits
RSA-sleutels over tien jaar even kwetsbaar zijn als 768-bits
RSA-sleutels dat nu zijn. Dit resultaat onderstreept het belang om de
1024-bits sleutel geleidelijk te upgraden. Tegelijkertijd laat dit zien
dat bij de stand van de huidige technologie het gebruik van 1024-bits
RSA-sleutels in de komende jaren nog geen onnodige risico's zal opleveren.
Veiligheid van RSA-cryptografische systemen
Cryptografische systemen moeten o.a. op internet de veiligheid van
e-commerce garanderen. Betrouwbaarheid hiervan is een absolute noodzaak.
Het RSA-systeem (genoemd naar zijn ontdekkers Rivest, Shamir en Adleman)
maakt het mogelijk om vertrouwelijke gegevens uit te wisselen en om
elektronische documenten te ondertekenen, van internet tot smartcards.
Om een dergelijk systeem te 'kraken' moet men de priemfactoren van de
corresponderende RSA-sleutel zien te vinden.
Volgens de zogenaamde 'Wet van Moore' verdubbelt iedere achttien maanden
de rekenkracht van computers. Daarom is het noodzakelijk om periodiek de
veiligheid van RSA-sleutels te testen.
Nieuw rekenrecord gevestigd met behulp van gedistribueerde rekenarchitectuur
De 768-bits RSA-sleutel is een getal van 232 (decimale) cijfers.
Gedurende een periode van tweeënhalf jaar is gebruik gemaakt van vele
duizenden computers, op verschillende locaties, om dit getal in
priemfactoren te ontbinden. De totale hoeveelheid rekentijd die hiervoor
gebruikt is, staat gelijk aan het gedurende een heel jaar onafgebroken
op topsnelheid laten rekenen van 1700 2.2GHz cores.
Dit project demonstreert de efficiëntie van gedistribueerd rekenen op
grote aantallen computers en op verschillende locaties.
Het CWI heeft een lange traditie in dit soort rekenprojecten. In 1999
speelde het een belangrijke rol bij het voor het eerst breken van een
512-bits RSA-sleutel en in 2008 werd het MD5
internet-beveiligingssysteem 'gekraakt' waarmee de kwetsbaarheid in de
infrastructuur van digitale certificaten werd aangetoond.
Over het CWI
Het Centrum Wiskunde & Informatica (CWI) is sinds 1946 het nationale
onderzoeksinstituut voor wiskunde en informatica. Het is gevestigd op
het Science Park Amsterdam en is deel van de Nederlandse Organisatie
voor Wetenschappelijk Onderzoek (NWO). Het instituut heeft een sterke
internationale positie. Ruim 160 wetenschappers doen er grensverleggend
onderzoek en dragen de verkregen kennis over aan de maatschappij.
Ongeveer 30 van de onderzoekers zijn hoogleraar aan een universiteit.
Uit het instituut zijn circa twintig spin-off bedrijven voortgekomen.
Links:
Technische samenvatting:
https://documents.epfl.ch/users/l/le/lenstra/public/papers/rsa768.txt
Preprint artikel: http://eprint.iacr.org/2010/006.pdf
Centrum voor Wiskunde en Informatica