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.

Publication date: 08-01-2010

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.

Links:
Technische samenvatting: https://documents.epfl.ch/users/l/le/lenstra/public/papers/rsa768.txt
Preprint artikel: http://eprint.iacr.org/2010/006.pdf

Fotografie: Shutterstock