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?
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
My TI-82 was just about to solve that one!
-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.
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.
p.s. all your xbox is belong to us.
...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.
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.
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.