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.
I hardly know 'er...
Seriously, this is interesting stuff. Of course, everytime we come up with a new security mechanism, computing power will overcome it. Fortunately, not everyone can do this sort of thing, and it takes time. But, as a mathematician, it is interesting to see both the methods used to crack this sort of thing, and, at least to me, more interestingly, the methods that are used to come up with new encryption systems. I cannot wait to see what will occur in several years, and even bigger prime numbers are known and usable...
I think that's really cool and would wish them the best of luck, but I would like to know how many processor hours that took them to crack it? Also, with that chunky $30,000 reward, did they turn any profit (after taxes, fees, and such). Second one's a joke, calm down. But it'd be cool to know the processor time it took.
I like suggestions, but I don't like contributing towards them.
While I think your remark was a joke about them breaking into RSA's computers, this is still worth mentioning. Noone in the entire world knows or has ever known the factors of the remaining numbers. Read this for more info.
Regards,
Steve
Let's seriously think about this, the Germans, if anything, lost money on this excursion, they upped an bought 80 opteron processors with the hardware required to run them and the RAM needed, they pumped electricity into the building where this heavy processing was taking place, and they paid the people running the computers... all for $30,000 - fees, customs, taxes and such... if anything, they probably lost a substantial sum.
I like suggestions, but I don't like contributing towards them.
I won't be interested until they do RSA-2048. Then we could factor the Xbox private key and do whatever we want.
Melissa
"Screw Sun, cross-platform will never work. Let's move on and steal the Java language." - Visual J++ Product Manager
What did I write that is inconsistent with the wikipedia entry?
"Integer factorization is widely suspected to be outside both of those classes [NP-complete and co-NP-complete]."
Just because a problem is outside P, doesn't mean it's NP-hard. Which is exactly what I said to start with.
The 212 digit one (RSA-704) won't be cracked for a long, long time yet using current algorithms like the ones the RSA-640 winners did. 640->704 doesn't sound like much, but it is monumental. I did some back-of-the-envelope math. I'm naively assuming that with a 64-bit gain in key size, the problem complexity is 2^32 harder (since one factor is always under the square root). I'm sure that seive algorithm they're using manages to cut that 2^32 down some, but it's not going to make a practical difference I don't think. If you happen to have ~8000 Opteron cpus at your disposal instead of their 80, and you have the same code they cracked RSA-640 in 5 months with, and it scales up to 8000 cpus just fine, it would take somewhere in the neighborhood of hundreds of millions of years to break RSA-704.
11*43+456^2
Here is a very useful site, listing estimates of how long various algorithms will be secure, and at what key sizes. It covers public- and secret-key algorithms, as well as hashes.
http://www.keylength.com/
Signature.
Reminds me of this paper where they argued that large computations can actually be completed faster by slacking off for a few months and then buying a faster computer.
A nice result! Interestingly, the same team factored RSA-200 last May, which is 663 bits long (confusingly, there's two series of RSA challenge numbers with different naming conventions) but for which no prize was given for its solution. RSA-640 is shorter, at 640 bits, but carries a US$20,000 prize. It's not entirely clear why the team went for the larger, prizeless number first.
Maybe there's other factors at work here besides prize money? (ROFL etc).
RSA cost study says "It makes no sense for an adversary to spend (say) $10 million breaking a key if recovering the key will only net (say) $10 thousand." Third party payer negates this asumption. Exceptions to the rule are seen in the everyday spending of U.S. taxpayer's millions by low level government employees and politicians alike for their personal gain or amusement, no matter how minor.
Has anyone publish (theoretical) costs of system capable to break given RSA lenght in one day based on the known systems?
No.
About 1200 years.
Progress in computation of the solution is linear. Moore's law is exponential. By year 3200 the computers will be strong enough to crack it in 6 months.
Anagram("United States of America") == "Dine out, taste a Mac, fries"
So you are trying to compare numebrs that simply cannot be compared.
Well, you can compare them, but you have to factor in the relationship between the complexity of the attack and the keysize in each case. In the case of RC5, brute force search of the keyspace is O(2^n) where n is the size of the key in bits. As a previous post mentions, the GNFS algorithm's complexity is O(e^(1.9229+O(1))*ln(n)^(1/3)*ln(ln(n))^(2/3)), where n is the number to be factored.
So to compare the complexity of these two attacks you just need to see if 2^64 is larger or smaller than e^(1.9229*ln(2^640)^(1/3)*ln(ln(2^640))^(2/3)).
Unless I made a mistake, the complexity of RSA-640 is about 5.5e13, whereas RC5-64 is about 1.8e19, so RC5-64 is approximately 300,000 times harder than RSA-640. I'm not sure that GNFS is as easy to massively parellelize as RC5 searching, though, so in practice RSA-640 may be harder than RC5-64, even though it has lower complexity. Also, big-O complexity ignores constant multipliers, so if each step in the GNFS algorithm is, say, a million times more complex than each RC5 trial encryption, than RSA-640 may actually be three times as hard as RC5.
Okay, so maybe you can't compare them :-)
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
It's like figuring out how many times you'd need to toss a coin before you'd be likely to get 7 heads in a row... and after figuring this out, actually tossing the coin until you get 7 heads. Anybody who actually did that would a moron. It would show nothing... much like these "factor this" challenges.
However, this is not the point. The point is to prove ANYONE (not only cryptanalyst) that it CAN be broken, though it takes some processing, and there is no alternative for doing.