- Researchers crack an RSA key that is 795 bits in size and has 240 decimal digits.
- The total computing time is equivalent to running a single computer core for 4,000 years.
- The calculations do not pose any threat to modern computer security.
Encryption is used to protect data you receive, store, and send, using a digital device. The government uses it to secure classified information, corporates use it to protect business secrets, and individuals use it to safeguard private information.
Almost all encryption techniques use long strings to keep online data safe. One of the most popular forms of encryption is RSA cryptography. It is based on the fact that large integers are difficult to factorize.
RSA is an asymmetric cryptography algorithm that involves a public key and a private key. The public key contains a number that is multiplication of two large prime numbers. The private key is derived from the same two prime numbers. The encryption strength increases exponentially as the key size gets doubled or tripled.
In order to show how secure the encryption is against modern hardware, RSA Laboratories published a list of semiprimes (numbers with only two prime factors) and challenged people to find their original prime factors. So far, 20 of the 54 listed RSA numbers have been cracked.
Recently, a research team at French Institute for Research in Computer Science and Automation factored RSA-240, a key with 240 decimal digits that is 795 bits in size. This is the largest encryption key cracked so far.
The previous record was set in 2009, with RSA-768 which is 768 bits in size and has 232 decimal digits. Even though RSA-240 is larger than RSA-768, researchers were able to obtain its prime factors faster than the previous record.
In addition to finding prime factors, researchers also computed the discrete logarithm of RSA-240. This is the first time that two records (integer factorization and discrete logarithm) are broken together with the same software and hardware.
Both computations were carried out with the Number Field Sieve algorithm, using the open-source software called CADO-NFS.
RSA-240 and its prime factors
The integer factorization took nearly 8 million core hours, whereas the computation of discrete logarithm took 27 million core hours. The total computing time is equivalent to running a single computer core (2.1 GHz Intel Xeon Gold 6130) for 35 million hours, or 4000 years.
In terms of computations, cracking RSA-240 is 2.25 times harder than cracking RSA-768. Considering the fact that researchers used identical hardware and got results 3 times faster than expected, the acceleration can be attributed to the improvements made in various algorithms over the last decade. The implementation of CADO-NFS, for example, has been greatly improved.
These calculations do not pose any threat to computer security, as RSA keys used by today’s computer are larger in size, from 1024 to 4096 bits. However, the advent of quantum computers may change things radically.