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.
640=2*2*2*2*2*2*2*5.
What do I win?
I wish had nothing better to do for five moths than factor numbers...geez...who needs the Internet when there are numbers to factor. :)
The German Federal Government is short on cash, I know, but resorting to funding the "Agency for Information Technology Security" by winning RSA contests? Besides, if they're so up on IT security, why didn't they just cheat by logging onto RSA's computers?
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
My TI-82 was just about to solve that one!
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
I knew that one of the factors ended in a 1 and the other ended in a 9 or that they both ended in 3. Am I eligible to split the prize?
-Not always true. Say I can come up with a 2048 bit encryption, that is just increase the key size from 256 to 2048, I can to that in a second. It is going to take _a lot more time_ for the computing power to overcome that increase.
If quantum computing will come around, I'll just switch to quantum encryption. Then you'll have to break the laws of QM to "break" the scheme. There are already rudimentary quantum encryption devices but there are no quantum computers that can take on even a 64 bit key space.
The best bet instead of brute force is to do "human engineering" and look for other ways to obtain the information. The inherent math of the algorithm is rarely the weakest link, it is the people and then the particular implementations of the algorithms that are exploited the most.
However what if that team had decrypted a banks RSA key. Sure it may have taken 5 months and the bank may well have changed keys since. But what if they captured all the packets sent/recieved using the cracked key. I guarentee there would be a bit of useful information in them. I know I don't change account numbers / credit card numbers every 5 months.
From a security point of view, "less than five seconds on modern hardware" is absolutely unnecessary. After a transmission has been intercepted, and we work under the assumption that essentially all of them are these days, that transmission has to remain secure potentially for a very, very long time (sure, an encrypted radio communication might have no operational significance in two hours -- an encrypted dossier of a field agent had better stay secure until he's dead, and an encrypted report on security breaches in US nuclear command&control protocols better stay unbroken for the better part of the next century). And what takes a beowulf cluster of supercomputers 5 months to do today will be possible to crack on a botneck in less than a week by 2010, I guarantee you (I write distributed applications for a living and worked with a three-letter agency which was rather miffed that a competing TLA had the existence of their own internal distributed cracker leaked to the press back in 2002 or so). A couple years after that it will be a few minutes on dedicated hardware and a few years after that a desktop machine will smash it as a matter of course. Events like this are warning flares to people with serious security needs that you need to start transitioning to harder codes or longer key lengths.
Help poke pirates in the eyepatch, arr.
should be enough for anyone."
And will not be, unless P=NP, or we use some form of new computers.
Factoring is almost certainly not NP-hard. It could very well be that P != NP, and yet factoring is easy.
I wonder how long it would have taken 1.5 million zombie PCs.
To a politician, one email equals one voter.
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
Why don't we just start using 1.44mb encryption keys. We'd finally have a use for all of these floppies.
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.
And in only 5 months... how P Q ular.
...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/
factor:2 72754572016194882320644051808150455634682967172328 67824379162728380334154710731085019195485290073377 24822783525742386454014691736602477652346609' is too large
`310741824049004372135075003588856793003734602284
isomerica.net | Foonetic IRC
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.
Inerestingly enough, there is no proof that encryption is even possible. Presently we do not know of any methods to factor a number in polynomial time while we can create primes in polynomial time, but an algorithm may exist that can factor primes in polynomial time. If one is discovered, encryption as we know it today will be impossible... even with your quantum computer. In fact, a solution to the P NP problem comes with a $1,000,000 prize.
70% of statistics are made up.
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
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.
Bill Gates wrote something similar in The Road Ahead:
The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers.
Sorry to break it to you boys but I know an algorithm that can do that in constant time: the factors of any prime number are 1 and the number itself.
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
For any base b, the sum of the digits (in base b) of a multiple of (b-1) add to a multiple of (b-1). The proof is fairly simple: http://www.pseudorandom.co.uk/2002/maths/divby9/.
For instance, in base 16, 3 * F (45 dec) is 2D, and 2+D=F.
This leads to a (slow) algorithm for primality check. For a given number r, simply (hah!) check all the bases up to about log_b(r) to see if all your base r belong to us.
Raise your children as if you were teaching them to raise your grandchildren, because you are.
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.
Although it's identical to the issue that the UK police claim they currently have. Which is why they want 90 days to lock citizens up without charge while they 'factor' their hard-drives.
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.
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)