RSA-640 Factored

gslin writes to tell us MathWorld News is reporting that RSA-640 has been factored. F. Bahr, M. Boehm, J. Franke, and T. Kleinjung, memebers of the German Federal Agency for Information Technology Security (BSI) announced they had cracked the 193-digit number last Friday using the General Number Field Sieve. The team purportedly used 80 opteron CPUs and 5 months to achieve victory.

Comments

Re:Processor time?

[Thundersnatch]

single binary digit doubles the search space needed

We're not talking about symmetric cryptography here. We're dealing with large prime numbers and lots of funny math. The General Number Field Sieve factoring algorithm is not O(2^n) like a brute force search on AES would be. The actual order of growth of the GNFS algorithm is:

O(e^(1.9229+O(1))*ln(n)^(1/3)*ln(ln(n))^(2/3))

This can be found numerous places on the web. So adding one bit to your RSA key does far, far less for you than adding one bit to symmetric cipher like AES. You can do the math yourself, but you'll find that you need to add >>1 bits to an RSA key to double its strength.

WTF is the General Number Field Sieve...

[acidblood]

...many are asking. It's hard to find introductory materials on the NFS, because the number of people who actually understand the algorithm is probably in the hundreds, if not less, and most are worried about research not teaching. For those interested in a high-level view, plus some low-level details, of the (special and general) NFS, you can have a look at the slides for a talk that I gave on exactly this topic at a crypto workshop a couple of months ago. I won't even try to summarize the NFS here, because anything other than a very high level, handwaving, bird's eye view of NFS would take the better part of a page to explain. However, in this thread I can answer specific questions that anyone might have about the talk above.

Now for those with the mathematical maturity to delve into the algorithm, I suggest the book Prime Numbers: A Computational Perspective by R. Crandall and C. Pomerance (link to Amazon.com lifted from Google, no referrals), which is certainly one of the best introductions to the algorithm that I have read.

By the way, if anyone wants to help perform huge factorizations in a distributed computing network, check out the NFSNET, although they mostly apply SNFS on values from the Cunningham tables, no cryptographic targets.

Re:Zombie Cluster - not feasable =(

[iced_tea]

from http://www.rsasecurity.com/rsalabs/node.asp?id=208 8

To put this in perspective, it would require about 1.4 billion 500 MHz machines, each with about 170 Gbytes of memory to do the sieving for a 1024-bit number in the same time as RSA-512. While a hacker might try to steal cycles on the Internet by creating a ?Number Field Sieve Worm? it is hard to see how such an attack could find enough machines with enough memory to make such an attack feasible. Further, such an attack would be detected and shut down rather quickly as with the Robert Morris worm. Of course increasing speed will reduce the required number accordingly. It would take a single Cray with 6 Terabytes of memory approximately 70 million days (192,000 years) to solve the matrix. One could reduce this to a mere 19 years with 10000 Crays each with only 600 Mbytes of memory running perfectly in parallel. It is likely that within 10 years common desktop machines will be as fast or faster than a Cray C90 is now. However, it is unlikely in the extreme that 10000 machines running in parallel will be anywhere close to 10000 times as fast as one machine. It would require 10 million such machines running perfectly in parallel to solve the matrix in about the same time as that for RSA-512.

So basically, according to the article from RSA it's not feasable... but still an interesting IDEA. Maybe a worm that installs something like folding@home that would have immediate benefits. ;)

Re:celeron's

[Anonymous Coward]

celeron's
(Score:1, Funny)
by rufuseddy (781982) on Tuesday November 08, @11:35PM (#13985872)
(http://www.oceighty.net/)
blah, if they would of used 80 celeron's they would have cracked it twice as fast.......

Dude, what's wrong with you? You wrote "would of"[sic] and "would have" in the same sentence! To make matters worse, you didn't capitalize a proper noun ("Celeron"), you used an apostrophe before an "s" in a plural twice, you didn't capitalize the first word of a sentence, and you ended your "sentence" with seven periods. Go back to the fifth grade. Do not pass go. Do not collect 200 dollars.

Re:How does this compare to RC5-64?

[cimetmc]

You are completely off track here and made 2 huge mistakes in your comparison:

1) The number RSA-640 has 193 *decimal* digits, but 640 bits (as the number in RSA-640 indicates).

2) You are comparing symetric key suzes (RC5-64 = 64 bit) with assymetric key sizes (RSA-640 640 bit). You can't compare these key sizes directly. Assymetric key sizes are much bigger than symetric key sizes for the same level of security. So you are trying to compare numebrs that simply cannot be compared.

Marcel

Re:I got part of it

[Pogue Mahone]

well that still rules out 97 out of 100 possibilities.

Not really. Both of the factors are prime, so that means that the last digit cannot be 0, 4, 6 or 8. Its also very unlikely to end in 2 or 5, since there is exactly one prime number ending in each of those digits, and those can be ruled out by simple observation. That leaves 4 digits --- 1, 3, 7 and 9, thus there are 16 possible combinations for the two last digits. You narrowed it down to 4 of those possibilities: 1 and 9, 3 and 3, 7 and 7, 9 and 1. So your elimination rate is a mere 75%. Sorry to disappoint.

Signed:
The Math(s) Nazi