PGP CTO Blog

New Factoring Record
24 May 2007

A team of people from EPFL (Ecole Polytechnique Fédérale de Lausanne) in Switzerland, the University of Bonn, and NTT in Japan have factored a 1017-bit number, which has been described as a 307-digit number in most articles about it. This is a big step forward, albeit expected.

What does this achievement mean for you? I hope it means very little. I've been saying for some time that you should stop using 1024-bit RSA keys. NIST recommends you stop using them by 2010, and that's fast approaching, particularly if you use them for 2 years in your SSL certificates. It’s also possible you have 1024-bit SSL keys for your website. Check and upgrade them to 2048-bit the next time you renew them.

There’s one thing you don’t have to worry about, however: PGP® software creates 2048-bit keys by default, and those are still plenty secure. Despite the fact that 2048 is only twice as big as 1024, it's a fine key size to use. Either 3072 or 4096 are better numbers, but there's nothing wrong with 2048. I wrote about how exponential growth affects cryptography last November in “The Evil of Scale”. The team that did this factoring includes mathematician Arjen Lenstra, upon whose work many estimates of strong cryptographic keys are based. I referred to http://www.keylength.com/ in my November article as well.

The gory mathematical details of this achievement are as follows. The actual number the team factored was (2^1039)-1. This is a binary number with 1039 1 bits in a row. We already knew this number had a factor of 5080711, which is a relatively small number. The number ((2^1039)-1)/5080711 is a 1017-bit, 307-digit number, which I’ve listed below (see “Really geeky details”).

The technique they used works only for "special" numbers, which are easier to factor. A binary number of all 1 bits is an example of a specially formed number. These are relatively easy to factor, and if you have any 1024-bit RSA keys, they won't be specially formed. The same team factored a 512-bit number in 1999. It took them 6 years to be able to generalize the work for 512-bit special numbers to generic numbers. At the time, Lenstra said, "I won't make predictions, but let's just say it might be a good idea to stay tuned." You've been warned.

If you’re using DSA keys, they’re in a similar position, but somewhat more secure. RSA keys are based on factoring, and DSA keys are based on logarithms. Mathematically, we know that if there’s an efficient way to factor, there’s a corresponding efficient way to compute logarithms. It doesn't guarantee anyone will ever discover it, however. We just know that it exists. Factoring is a much sexier pastime than logarithms, so there hasn't been as much work done on logarithms to date.

As I said before, past predictions warned you to stop using 1024-bit keys. NIST gave 2010 as the “stop-by” date. In 1999, Lenstra and Eric Verheul predicted 2002 as the date when 1024-bit RSA keys become vulnerable and 2009 for 1024-bit DSA keys. In 2006, Lestra revised the estimate for RSA keys to 2006.

Look over your RSA keys now, particularly your SSL certificates. Upgrade them, if necessary. You've been warned—again.

Really geeky details:

The number 2^1039-1 is:

589068086431683676644738724917747624711938696459815017753575689937658432
079465555993259138490065014034006389161562581754376322314451080388584562
460719428810761069833174599222153387113189363201210623862217392146903328
852155899782370013718480620182690736866953411252382072659135491210334387
6844956209126576528293887

The number that was actually factored is:

115942057407257306436980714887689464075389979170201772498686835353882248
385996675660800060954080051794720539932612302048744028604353028619141014
409345351233471273967988850226307575280937916602855510550042581077117617
761009413797078797380618700843777718682868088984471282200293520180607475
5451541370711023817

The additional factors (courtesy of Arjen Lenstra) were:

5585366661993629126074920465831594496864652701848863764801005234631985
3288374753

and
   
2075818194644238276457048137035946951629397080073952098812083870379272
9090324679382343143884144834882534053344769112223028158327696525376091
4101891052419938993341097116243589620659721674811617490048036597355734
09253205425523689

Background Reading: 

"A mighty number falls", May 21, 2007

Lenstra, Arjen K., "Key Lengths", June 30, 2004

Lenstra, Arjen K. and Eric R. Verheul, "Selecting Cryptographic Key Sizes", November 15, 1999

Kleinjung, Thorsten, "Factorization of the 1039th Mersenne number", May 22, 2007