RSA-640 factored
http://mathworld.wolfram.com/news/2005-11-08/rsa-640/ --Steven M. Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RSA-640 factored
From: http://mathworld.wolfram.com/news/2005-11-08/rsa-640 November 8, 2005--A team at the German Federal Agency for Information Technology Security (BSI) recently announced the factorization of the 193-digit number 310 7418240490 0437213507 5003588856 7930037346 0228427275 4572016194 8823206440 5180815045 5634682967 1723286782 4379162728 3803341547 1073108501 9195485290 0733772482 2783525742 3864540146 9173660247 7652346609 known as RSA-640. The team responsible for this factorization is the same one that previously factored the 174-digit number known as RSA-576 (MathWorld headline news, December 5, 2003) and the 200-digit number known as RSA-200 (MathWorld headline news, May 10, 2005). -Michael Heyman - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: RSA-640 factored
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 7 times as difficult as RSA-640 using GNFS. If you have 80*7 = 560 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*7/1/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]
Re: RSA-640 factored
On Wed, Nov 09, 2005 at 05:27:12PM +0100, Simon Josefsson wrote: I'm not sure translating complexity into running time is reasonable, but pending other ideas, this is a first sketch. It is not reasonable, because the biggest constraint is memory, not CPU. Inverting the matrix requires increasingly prohitive quantities of RAM. Read the DJB hardware GNFS proposal. -- /\ ASCII RIBBON NOTICE: If received in error, \ / CAMPAIGN Victor Duchovni please destroy and notify X AGAINST IT Security, sender. Sender does not waive / \ HTML MAILMorgan Stanley confidentiality or privilege, and use is prohibited. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: RSA-640 factored
Victor Duchovni [EMAIL PROTECTED] writes: On Wed, Nov 09, 2005 at 05:27:12PM +0100, Simon Josefsson wrote: I'm not sure translating complexity into running time is reasonable, but pending other ideas, this is a first sketch. It is not reasonable, because the biggest constraint is memory, not CPU. Inverting the matrix requires increasingly prohitive quantities of RAM. Read the DJB hardware GNFS proposal. Can we deduct a complexity expression from it, that could be used to (at least somewhat reliably) predict the cost of cracking RSA-768 or or RSA-1024, based on the timing information given in this report? The announcement doesn't say how much memory these machines had, though, but perhaps that information can be disclosed. Thanks, Simon - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
