Researchers: 307-digit key crack endangers 1024-bit RSA

A 307-digit composite Mersenne number has been broken down into primes, and 1024-bit RSA keys are next, according to encryption researchers. Researchers from the University of Lausanne, the University of Bonn, and NTT DoCoMo have broken a new record in discovering the prime factors of a "special" 307-digit number this month, which took 11 months and roughly 100 years of computer time. The number was cracked using the special number field sieve method developed by cryptology professor Arjen Lenstra in the 1980s.

The 307-digit number itself was not an RSA key—the number was 2¹⁰³⁹-1, a special-form number called a Mersenne number which permits an efficient variant of the factoring algorithm in question, the so called Special Number Field Sieve (SNFS) to be used. RSA keys are typically generated by multiplying together two very large prime numbers, each at around 150 digits apiece, and require more labor-intensive General Number Field Sieve (GNFS) to factor. But the project shows that given enough time and computer power, the 1024-bit encryption keys used on many e-commerce sites could also be cracked in the not-so-distant future.

"Last time, it took nine years for us to generalize from a special to a nonspecial, hard-to-factor number," Lenstra said in a statement, referring to a 155-digit number that his team had broken previously. More recently, a 200-digit non-special number was factored in 18 months and roughly 50 years of computer time. This 307-digit crack took even less (human) time, which Lenstra credits to more powerful computers and improved code. "I will not make predictions [about the future of 1024-bit encryption], but let us just say that it might be a good idea to stay tuned."

Why does anyone care? While your average Joe or Jane on the street will not be able to crack a 1024-bit RSA key anytime soon, experienced attackers might not have such a hard time. Getting the computing power to crack a 1024-bit key could be as easy as employing a decent-sized botnet or two.

When asked whether 1024-bit RSA keys are dead, Lenstra said: "The answer to that question is an unqualified yes." Hopefully, my bank is paying attention to these developments.