The Cipher on the Wall

by Ari Juels on 5/24/2007

"The writing is on the wall for 1024-bit RSA," one trade publication has declared in response to the recent announcement of the successful factoring of a 307-digit (1017-bit) number. As 1024 bits is the length of many RSA keys used in practice today, a short journalistic leap of fancy raises the specter of imperiled retail transactions on the Web. If there is writing on the wall for 1024-bit RSA, though, what's written is in cipher--and it's wholly unclear how long the cryptanalysis will take. While I'm not a specialist in the area of public-key cryptanalysis, I've written up a short FAQ in an attempt to demystify the recent factoring result.

Q: What is this new record in integer factorization announced by Aoki et al.?

A: On 21 May 2007, Aoki, Franke, Kleinjung, Lenstra and Osvik announced the successful factoring of a number just shy of 1024 bits in length. That number, (2^1039 - 1) / 5080711, was 1017 bits (307 decimal digits) long, and represented the hitherto unfactored portion of the so-called 1039th Mersenne number (2^1039 - 1). The target number had a special form: it was not selected in the same manner as an RSA key. The technique used by the team, the special number field sieve (SNFS), is a special case of state-of-the-art techniques for factoring RSA moduli. This result is an important milestone, and it is conceivable that follow-up work by the scientific community may ultimately suggest some recalibration of key-lifetime recommendations. At this point, however, given the special-purpose nature of the team's effort, and the fact that this effort does not involve fundamentally new techniques, there is no clear impact on the security of RSA keys.

Q: Do I need to revoke my 1024-bit RSA keys?

A: To date there has been no successful factoring of even 768-bit RSA, a bellwether key size used in early computing applications. The difficulty of factoring an RSA key grows very rapidly with the length of the key. For instance, it is generally supposed that factoring a 1024-bit RSA key requires approximately 1000 times as much computation as a 768-bit key. The longest RSA key factored to date is RSA-200, a 663-bit RSA modulus successfully factored in 2005 in the context of the RSA Laboratories Factoring Challenge. (That challenge is no longer active. As the Aoki et al. result shows, prizes are no longer a necessary stimulus for vital work in factoring to proceed.) Thus, 1024-bit RSA keys do not appear to be in imminent jeopardy of attack.

Q: As computers grow faster, doesn't cryptography grow weaker?

A: In general, the opposite is true. The time to perform cryptographic operations grows slowly in proportion to the length of a key, while the time to break a key grows rapidly. For example, performing RSA operations with a 1024-bit key requires about eight times as much computing power as with a 512-bit key. A 1024-bit key, however, is about one million times harder to break than a 512-bit key. As computers grow faster, their agility in performing cryptographic operations with larger keys outpaces their ability to break keys. (Algorithmic breakthroughs or fundamental advances in the physics of computing could change the situation, but in most cases the scientific community has warning of such events well in advance. Despite the cinematic view of invention, it's usually a gradual process.)

Q: What RSA key size should I be using?

A: While effective attacks against 1024-bit RSA keys appear unlikely to emerge in the near term, the community has for some years suggested the prudence of a movement away from 1024-bit key lengths by the end of 2010. The U.S. National Institute of Standards (NIST) recommends in its special publication 800-57, "Recommendation for Key Management--Part I: General" (p. 66), that 1024-bit RSA be used to confer data protection only through 2010. Similarly, in May 2003, RSA Labs published key-size recommendations deprecating the use of 1024-bit RSA keys for protection of data with a lifetime beyond 2010. The general consensus is that 1024-bit RSA keys are roughly equivalent in strength to 80-bit symmetric keys, and that advances in computing power and incremental algorithmic advances could bring such keys within the reach of intensive computational attack in the next decade. It is worth noting, however, that many view the NIST date of 2010 as a conservative "best by" date, selected in part in anticipation of delayed industry adherence to NIST guidelines.

Q: How often will I have to increase the length of RSA keys in my applications?

A: In general, keys should be selected in accordance with the value and lifetime of the data they aim to protect. NIST recommends the use of 2048-bit RSA keys for data-protection lifetimes through 2030, and use of 3072-bit RSA keys beyond that date.

Q: What is the historical relationship between results like that of Aoki et al. and the factoring of RSA keys?

A: In 1990, researchers successfully factored the ninth Fermat number, 2512-1. That work stimulated industry movement away from 512-bit RSA keys (whose use many at the time already deprecated). Nine years later, in 1999, researchers successfully factored a 512-bit RSA key using a generalization of techniques employed in the milestone of 1990. Of course, advances in computing power played a major role in bringing 512-bit RSA keys into reach. The 1990 result also marked a fundamental advance in the development of factoring techniques. The Aoki et al. result does not appear to mark a conceptual advance of the same order. How long will it take to translate this special case into the general case, and thus an attack on 1024-bit RSA? That is a matter of speculation. An important point to appreciate, however, is that the asymptotics of the special number-field sieve (SFNS) and the general number-field sieve (GFNS) suggest that translation from the special to the general case is harder for 1024 bits than for 512 bits, i.e., the ratio of required computational resources is larger. Given the multiple factors that come into play in determining the difficulty of factoring, however, results like that of Aoki et al. are to be applauded for the vital information they bring to the community about advances in factoring capabilities.