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.
Does anyone know of something like the GIMPS to factor these RSA numbers? It seems like if 80 Opterons can do it in 5 months, a massive distributed network of computers donating idle time could do this in a much shorter amount of time, such as churning out a new factorization every few weeks. I have a feeling the larger RSA numbers quickly become much more complicated to factor. Does anyone know the complexity class of factorization?
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
No, what about 7 and 7?
Contrary to popular belief a large part of the GNFS (the last most important phase, ~80% of the
algorithms run time) is actually sequential and can not be parallelized in any way shape or form.
Arash Partow
Arash Partow's Philosophy: Be a person who knows what they don't know, and not a person who doesn't know.
Actually, the next one has only 212 digits...
Telltale Games: Bone, Sam and Max
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.
The Wikipedia article on RSA-640 has more info. Check this for easy money ;)
...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.
640! = 64409718565200018055131800965981532721782172857809 35050119769024917912649386556736435990175942482881 50831173208718164630201061409780121407122461364924 58377710508516955614515870499288921594586346123434 33180780170533237643858349983073211205085008177221 23334955489548539613464287113486796254782280386192 42902556432022520662136294311646067063179388639341 64085587743812021695906380070875341161592893857325 43950455135580702163621967540729516434733225112310 19894142562784272396885841079611839890149814550124 39303021946826615046590582495802088225465848653849 49658745367091435175285190031747259785364892724246 44581896134757504721500575093072296641784946756103 72209909854987875605056434890950842087494564950738 50342684518858945589680071711243181514726647615699 31491279455269105452696480012333296289382307693598 92378742869557307887038923609012421597040445457338 74337845037253151897729671908964331393489772603959 59589548517793461330628196613401917126378390242846 93257523202987341241900850720690028543718314179741 21710624363839688427903596832205914168418422225116 58140716647635269032404235004721905438667198590366 48063974166410911515008191851366556055573022807574 25873254919125351231886283164699615743032337296746 10898181081786065982252420557478741130812235511867 87217476385809669846991054271061032324367962162620 83477325316470089765943690841812967664794901526655 17956005888000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000000000. Just so you know.
If you go high enough, people don't know very many primes. In fact, there are lists of the largest known primes. I'd wager that there are less than a few thousand known primes greater than 2^720k, probably a lot less.
Depends on whether you want provable primes or probable primes.
It's a five minute job to generate a few thousand probable primes >2^720k. Don't know what you'd do with them though.
And they will be prime, you can make the probability of them not being prime as small as you like - 1 in 2^100 should be enough.
But if you want to prove them prime then that is a different matter.
Every prime used in a real implementation of public key cryptography is a probable prime. The only reason for proving a number prime is to get yourself on the record books.
Tim.
God said, "div D = rho, div B = 0, curl E = -@B/@t, curl H = J + @D/@t," and there was light.
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)
Surprisingly, lowly Excel was able to handle this math for me.
It looks like a 1024-bit number will take about 73,500 times as long as a 640-bit number to factor using GNFS. Which correlates to about 2.4 million Opteron-years, based on the German factoring of RSA-640.
Here's a table:
bits|GNFS complexity
384| 8.09434E+16
512| 1.75249E+19
640| 1.78448E+21
768| 1.07460E+23
896| 4.37451E+24
1024|1.31176E+26
1536|1.30666E+31
2048|1.52656E+35
3072|5.77594E+41
4096|1.28186E+47
My understanding of GNFS is that only the sieving steps are trivial to parallelize. The final steps must be performed on a single machine with huge memory. So perhaps a 1024-bit RSA number is even safer than my math indicates, as it may be that no machine which can handle the final steps for a 1024-bit number exists.
Nonsense. First of all, factoring per se only affects RSA encryption.
It's likely that a major advance in factoring would also affect the security of Diffie-Hellman key exchange and ElGamal encryption, but it's not an absolute certainty. These are based on discrete logarithms, and while finding discrete logarithms hasn't (TTBOMK) been proven equivalent to factoring, current factoring methods can also be applied to finding discrete logarithms, and there's some theoretical basis for assuming any future ones will as well. For example, here is a paper discussing the relationship between the two (warning: quite mathematical).
Those aren't the only methods of public-key cryptography though -- for example, elliptic curve cryptography might well be unaffected. In particular, both factoring and discrete logarithms display a property called "smoothness" (about which, see the paper above) which is necessary for the various "sieve"-type algorithms to operate correctly. At least so far, nobody has shown that elliptic curves have the property of smoothness (though various mathematicians argue both for and against its likelihood). As a consequence, breaking elliptic curve cryptogaphy uses entirely different methods, and there's little reason to believe that even a major advance in factoring would necessarily have any real effect on elliptical curve cryptography at all.
Then we come to all the symmetric ciphers -- DES, 3DES, IDEA, FEAL, RC4, RC5, RC6, AES, and many, many more. The vast majority of these have little or nothing to do with prime numbers, and even the most amazing advance in factoring would be unlikely to affect any of them at all. The applicable area of mathematics is entirely different -- most symmetric algorithms are based in number theory while most symmetric algorithms are based on group theory.
Since "quantum" has been thrown around a bit, I'll try to add a bit of clarification on that subject as well. Unfortunately, there are two rather different sorts of things related to cryptography that use quantum in their names. As has been noted elsethread, what's generally called quantum cryptography would more accurately be called quantum key exchange. It's basically just a way of sendin some bits over a fiber optic cable, and the receiver can detect whether anybody has tapped into the line to see what was sent.
The second "quantum" thing is quantum computers. The Shor algorithm (due to Peter Shor) does factoring on a quantum computer in polynomial time, which is more or less the holy grail in fast factoring. The problem is that at least at the present time, there's no such thing as a practical quantum computer -- the most "powerful" quantum computers to date haven't even been sufficiently capable to replace a pocket calculator. Worse, the methods used to create quantum computers so far are widely believed to be unscalable, so there's no certainty that quantum computers can ever become practical -- though there's a great deal of research being devoted to the subject, and there's certainly a possibilty that they might.
If quantum computers were to become practical, they would also affect symmetric ciphers. Basically, searching for the key of a symmetric cipher is normally proportional to the size of the key space. For a quantum computer, the search is proportional to the square root of the size of the key space instead.
This, however, has less effect that most people realize. In particular, the size of the key space is squared by doubling the size of the key. In point of fact, many (if not most) current symmetric ciphers already use keys large enough to render attacks by quantum computers
The universe is a figment of its own imagination.
I know you are joking but I have actually had a boss that used this to reason why many security enhancements (like encrypting passwords on the network) were not worth implementing. It is a silly analogy that many people people believe.
Network based attack are far more common that physical attacks for a lot of good reasons. The main ones are:
1. Need for proximity is often removed
2. There is anonimity (much of the time)
3. There are less legal consquenses
4. Culpability is harder to prove (Log files don't stand up as well as DNA)
5. It involves mental rather than physical skill
6. For many people it is an easier moral justification
7. Ability to attack thousands of targets at once
8. Low impact for jobs that don't pan out as expected
9. No messy cleanup.
In the world of data security you cannot draw good comparisons to physical secuirty. Often in the physical world you just need to make sure your car is harder to steal than the one parked next to it but in cyberspace a single car thief can attack a whole parking lot, drive away with all of them at once, not show up on any security cameras and even put a remote control device in your car to take over at their whim later. What's best is he can do this from a wheelchair, from a distant city, can be any age, sex, social position or race so profiling doesn't work to narrow suspects. A lot of time there is no motive (not even a finacnial one) other than just the trill of seeing if you can do it. The analogy of relating cyber security threats to real world examples does great injustice to understanding the real problem. But humans need something concrete within their own experiance to relate the problem to and so everyone ties the cyber world to the physical and many bad decisions result.
Sorry, but I have heard the "they can beat my password out of me easier" a few too many times in complete seriousness to let this pass without comment.
As for traditional social engineering, it is often quite easy to get someone to tell you their password but it is much more complicated to fool someone into telling you their 2048 bit private key.