Researchers of the Cryptology and Information Security group of the Centrum Wiskunde & Informatica (CWI) in Amsterdam with partners from Germany (BSI and Bonn University), France (INRIA Nancy), Japan (NTT) and Switzerland (EPFL) have broken a 768-bit RSA key by finding its prime factors. This new record demonstrates the vulnerability of 768-bit RSA keys.
The first 512-bit RSA key was broken in 1999, in 2005 followed by the first 663-bit key. Extrapolating this trend, it is reasonable to expect that 1024-bit keys will exhibit a similar degree of vulnerability within the next decade as 768-bit keys do now. The result underlines the importance to phase out the usage of currently popular 1024-bit RSA keys in the next decade. At the same time the result implies that with the current state of technology, users of 1024-bit RSA keys will not incur undue risks in the coming few years.
Security of the cryptographic system RSA
Cryptographic systems should guarantee the security of e-commerce on internet. Reliability is therefore crucial. RSA (named after its inventors Shamir, Adleman and Rivest) allows users to exchange confidential data and sign electronic documents on internet and smart cards. To break such a system, one has to find the prime factors of the corresponding RSA key. According to Moore's law, computers become twice as powerful every 18 months. Therefore it is important to regularly check the security of the RSA keys used on Internet and in smart cards.
New computing record using a distributed computing architecture
The 768-bit factored key is an integer of 232 digits. During a timeframe of 2.5 years many thousands of CPUs on a large number of different locations were deployed to break this key. The total amount of computing power used is equivalent to 1700 2.2 GHz CPUs during one year.
This project demonstrates the efficiency of distributed computing on many computers at different locations.
CWI has a long tradition in large computing projects. In 1999 it played a major role in breaking the first 512-bit RSA key and in 2008 the MD5 internet security system was broken, demonstrating the vulnerability in the infrastructure of digital certificates.
Links:
Technical summary:
https://documents.epfl.ch/users/l/le/lenstra/public/papers/rsa768.txt
Preprint paper:
http://eprint.iacr.org/2010/006.pdf
Image: Shutterstock
