Slashdot Mirror
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.
The CPU time spent on finding these factors by a collection of parallel computers amounted very approximately to the equivalent of 55 years work for a single 2.2 GHz Opteron-based computer. Although that's a rough approximation, it certainly puts the magnitude of effort cracking these numbers involves.
If you want a picture of the future, imagine a boot stamping on a human face forever.
- George Orwell
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:
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.
...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.
Join the NFSNET. Our prime goal is making little numbers out of big ones. http://www.nfsnet.org/
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.
So, an opteron has roughly <8.8 peak GFlops:http://www.amd.com/us-en/Processors/Product Information/0,,30_118_8796_8800~96867,00.html> [amd.com] 60 of them would give around 528 GFlops (theoretical max). Given the fastest super computer in the world, the Blue Gene/L has roughly <183500 GFlops:http://www.top500.org/lists/plists.php?Y=20 05&M=06> [top500.org]. That means the Blue Gene/L can factor it roughly 350 times faster (assuming the algorithm scales linearly) or in roughly 9 hours 45 mins. Scary
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.
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
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
Every bloody emperor has his hand up history's skirt [Peter Hammill/VdGG]
I have a 250 gigabytes encrypted volume that I access all the time - increasing encryption level means more processor intensive disk operations. Of course, there's always a tradeoff when encrypting, but moving up to 2048 bit encryption is *a lot* of difference, performance-wise.
Wow, that was alot of incorrect in one post
1) You factor large COMPOSITE numbers, not large prime numbers.
2) P = NP is almost surely false. I mean, it's not proven, but it's not like anybody believes it to be true. It would just be too damn incredible if it were true.
3) What do you mean "encryption wont be possible"??? Just because you can factor large numbers quickly, doensn't mean you can encrypt stuff. You can't use RSA, that's true, but there are other asymetric ciphers. AES will sure as hell still work. Worst case scenario, we'll just use one time pads and all will be dandy (for those of you who don't know, One time pad-ciphers (also called the Vernam cipher) is impossible to break if used correctly, and when I say impossible, I mean mathematically proved-no way no how-even when the aliens invade earth with super-super-computers will we be able to solve it)