The 232-digit number RSA-768 has been factored!

(no votes yet)

Loading...

A paper posted today reports that they have factored the 768-bit number RSA-768 (this is a new record!). It further discusses implications for RSA. Should companies/banks that have data with a high financial value migrate to longer keys?

Highlights:

• They factored the number RSA-768 on December 12th, 2009
• The number RSA-768 is from the RSA Challenge list as a representative 768-bit RSA modulus
• This result sets a new record for factoring general integers
• Math: Method used is the number field sieve factoring method
• 
  Quoted from the paper: “We spent half a year on 80 processors on polynomial selection.
  This was about 3% of the main task, the sieving, which was done on many hundreds of
  machines and took almost two years.”
  

The following quote from the RSA Laboratories website is quite interesting and informative:

“What does it mean when a Challenge Number is factored?

Users
of the RSA public-key cryptosystem may wonder what the factoring of a
challenge number implies about the security of their keys. Should they
immediately replace their keys with larger ones? Should they stop using
RSA altogether?

Clearly, the factoring of a challenge-number of
specific length does not mean that the RSA cryptosystem is “broken.” It
does not even mean, necessarily, that keys of the same length as the
factored challenge number must be discarded. It simply gives us an idea
of the amount of work required to factor a modulus of a given size.
This can be translated into an estimate of the cost of breaking a
particular RSA key pair.

Suppose, for example, that in the year 2010 a
factorization of RSA-768 is announced that requires 6 months of effort
on 100,000 workstations. In this hypothetical situation, would all
768-bit RSA keys need to be replaced? The answer is no. If the data
being protected needs security for significantly less than six months,
and its value is considerably less than the cost of running 100,000
workstations for that period, then 768-bit keys may continue to be
used.

Applications that require longer-term security
or have data with a high financial value should migrate to longer keys
before the factoring of the corresponding challenge number is
announced. In either case, the results of the Factoring Challenge
provide real data to help the cryptosystem user choose the appropriate
key size”

Authors of the paper:
Thorsten Kleinjung; Kazumaro Aoki; Jens Franke; Arjen Lenstra; Emmanuel
Thomé; Joppe Bos; Pierrick Gaudry; Alexander Kruppa; Peter Montgomery;
Dag Arne Osvik; Herman te Riele; Andrey Timofeev and Paul Zimmermann