New crypto-cracking record reached, with less help than usual from Moore’s Law

Enlarge (credit: Mike Myers)

Researchers have reached a new milestone in the annals of cryptography with the factoring of the largest RSA key size ever computed and a matching computation of the largest-ever integer discrete logarithm. New records of this type occur regularly as the performance of computer hardware increases over time. The records announced on Monday evening are more significant because they were achieved considerably faster than hardware improvements alone would predict, thanks to enhancements in software used and the algorithms it implemented.

Many public-key encryption algorithms rely on extremely large numbers that are the product of two prime numbers. Other encryption algorithms base their security on the difficulty of solving certain discrete logarithm problems. With sufficiently big enough key sizes, there is no known way to crack the encryption they provide. The factoring of the large numbers and the computing of a discrete logarithm defeat the cryptographic assurances for a given key size and force users to ratchet up the number of bits of entropy it uses.

The new records include the factoring of RSA-240, an RSA key that has 240 decimal digits and a size of 795 bits. The same team of researchers also computed a discrete logarithm of the same size. The previous records were the factoring in 2010 of an RSA-768 (which, despite its digit is a smaller RSA key than the RSA-240, with 232 decimal digits and 768 bits) and the computation of a 768-bit prime discrete logarithm in 2016.

Read 11 remaining paragraphs | Comments