"Steven M. Bellovin" <[EMAIL PROTECTED]> 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 [EMAIL PROTECTED]