Speaking of Security – The RSA Blog and Podcast

Last Thursday, a six-institution team of scientists (Kleinjung et al.) announced the successful factorization of RSA-768. RSA-768 is a 768-bit (232 decimal-digit) RSA public key created in 2001 by RSA Laboratories as a cryptanalytic challenge number. The fall of RSA-768 is a landmark result, but no surprise. It reflects a consistent pace of growth in computing power, and continuing scientific interest in the problem of factoring, not an algorithmic breakthrough.

Still, the team that factored RSA-768 has served the technical community with an important, tangible warning. The U.S. National Institute of Standards and Technology (NIST) published RSA key-length recommendations in 2007 that advise the phasing out of 1024-bit RSA keys by the end of 2010. The factoring of RSA-768 affirms the prudence of this recommendation. Using the best current approach (the Number Field Sieve), successful attack against 1024-bit RSA requires roughly one thousand times the resources required to factor 768-bit RSA. RSA-1024 could well fall to a public effort in the next decade or so. A well-resourced government organization could knock down 1024-bit keys rather sooner. Keys often linger for many years, so now is the time to start retiring 1024-bit RSA in favor of larger RSA key sizes (the standard next step up is 2048-bit).

RSA-768 formed part of the RSA Factoring Challenge, created in 1991 and updated with new challenge numbers in 2001. The Challenge comprised a sequence of RSA moduli of increasing length and difficulty, with cash prizes for successful factoring. RSA Laboratories created the Challenge to stimulate new research into factoring methods and better inform the technical community’s key-length recommendations.

In 2007, RSA Laboratories chose to discontinue the RSA Factoring Challenge. The Challenge was no longer generating new knowledge. Factoring research had matured. Challenge numbers were toppling over the years at a predictable pace.

The factoring of RSA-768 is a case in point. In 2004, Arjen Lenstra (a participant in the RSA-768 factorization) offered a framework for forecasting the computational effort required to factor RSA keys. His work suggested that the computational effort for a 768-bit RSA modulus would be roughly equivalent to that of breaking a 67-bit or 68-bit symmetric key—about 2⁶⁷ computational steps. The Kleinjung et al. paper reports a computational effort of… about 2⁶⁷ operations. (A “step” and “operation” here aren’t interchangeable, but are loosely comparable.)

The Kleinjung et al. paper carries another unmistakable sign of the maturity of factoring research. It’s the first I can recall on the topic that gives the nod to project management. “We… note that larger efforts of this sort would benefit from full-time professional supervision.”

Of course, cryptology is not immune to surprises. An innovation in factoring algorithms or custom factoring hardware or a rapid advance in quantum computing could shake predictions. But amid the eddying pool of uncertainty that is computer security, NIST’s carefully crafted guidelines on RSA key lengths will probably serve as an anchor for many years to come.

[1] Kleinjung et al., Factorization of a 768-bit RSA modulus, v 1.0. IACR ePrint archive. 7 January 2010.
[2] Arjen K. Lenstra, "Key Lengths", Handbook of Information Security. 2004.
[3] NIST Special Publication 800-57 Part 1, Recommendation for Key Management, Special Publication 800-57 Part 1, NIST, 03/2007.
[4] The RSA Factoring Challenge. RSA Laboratories. 1991-.

•