RSA-640 factored

[Simon Josefsson]

"Steven M. Bellovin" <smb at cs.columbia.edu> writes:

> http://mathworld.wolfram.com/news/2005-11-08/rsa-640/

There are timing details in:

http://www.crypto-world.com/announcements/rsa640.txt

They claim they need 5 months of 80 machines with 2.2GHz processors.

Using these numbers, I think it would be interesting to come up with
an estimate of how expensive it would be to crack larger RSA keys for
someone who used the same software.  I'll make an attempt to do this
below, but I reckon I will make errors...  please correct me.

The complexity for the GNFS is roughly

O(exp(1.9(log n)^.3 * (log log n)^.66)

where n is the number to factor, according to
<http://mathworld.wolfram.com/NumberFieldSieve.html>.

I'm not sure translating complexity into running time is reasonable,
but pending other ideas, this is a first sketch.

Let's input the numbers for 2^640:

octave:26> n=2^640
n =  4.5624e+192
octave:27> a=e^(1.923*(log(n))^(1/3)*(log(log(n)))^(2/3))
a =  1.7890e+21

And let's input them for 2^768:

octave:28> n=2^768
n =  1.5525e+231
octave:29> b=e^(1.923*(log(n))^(1/3)*(log(log(n)))^(2/3))
b =  1.0776e+23

Let's compute the difference:

octave:30> b/a
ans = 60.232

In other words, cracking a RSA-768 key would take 60 times as long,
assuming the running time scale exactly as the complexity (which is
unlikely).

So it seems, if you have 80*60 = 4800 machines, you would be able to
crack a RSA-768 key in 5 months.

Continuing this to 1024 bit keys...  (or rather 1023 since Octave
believe 2^1024=Inf)

octave:40> n=2^1023
n =  8.9885e+307
octave:41> c=e^(1.923*(log(n))^(1/3)*(log(log(n)))^(2/3))
c =  1.2827e+26
octave:42> c/a
ans =  7.1697e+04
octave:43>

I.e., RSA-1024 is about 70000 times as difficult as RSA-640 using
GNFS.  If you have 80*70000 = 5600000 machines, you would be able to
crack a 1024 bit RSA keys in 5 months.  Or put differently, if you had
10.000 CPUs it would take 5*80*70000/10000/12 = 233 years to factor a
RSA-1024 key.

I know there are many hidden assumptions here, and I probably made
mistakes when computing this.  Please point out flaws so we can get
accurate numbers.

Cheers,
Simon

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com