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!
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."
I wonder how long it would have taken 1.5 million zombie PCs.
To a politician, one email equals one voter.
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.
p.s. all your xbox is belong to us.
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/
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.
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.