Skip to comments.RSA-640 Factored
Posted on 11/09/2005 4:44:53 AM PST by zeugma
November 8, 2005--A team at the German Federal Agency for Information Technology Security (BSI) recently announced the factorization of the 193-digit number
310 7418240490 0437213507 5003588856 7930037346 0228427275 4572016194 8823206440 5180815045 5634682967 1723286782 4379162728 3803341547 1073108501 9195485290 0733772482 2783525742 3864540146 9173660247 7652346609
known as RSA-640. The team responsible for this factorization is the same one that previously factored the 174-digit number known as RSA-576 (MathWorld headline news, December 5, 2003) and the 200-digit number known as RSA-200 (MathWorld headline news, May 10, 2005).
RSA numbers are composite numbers having exactly two prime factors (i.e., so-called semiprimes) that have been listed in the Factoring Challenge of RSA Security®.
While composite numbers are defined as numbers that can be written as a product of smaller numbers known as factors (for example, 6 = 2 x 3 is composite with factors 2 and 3), prime numbers have no such decomposition (for example, 7 does not have any factors other than 1 and itself). Prime factors therefore represent a fundamental (and unique) decomposition of a given positive integer. RSA numbers are special types of composite numbers particularly chosen to be difficult to factor, and they are identified by the number of digits they contain.
While RSA-640 is a much smaller number than the 7,816,230-digit monster Mersenne prime known as M42 (which is the largest prime number known), its factorization is significant because of the curious property that proving or disproving a number to be prime ("primality testing") seems to be much easier than actually identifying the factors of a number ("prime factorization"). Thus, while it is trivial to multiply two large numbers p and q
together, it can be extremely difficult to determine the factors if only their product pq is given. With some ingenuity, this property can be used to create practical and efficient encryption systems for electronic data.
RSA Laboratories sponsors the RSA Factoring Challenge to encourage research into computational number theory and the practical difficulty of factoring large integers and also because it can be helpful for users of the RSA encryption public-key cryptography algorithm for choosing suitable key lengths for an appropriate level of security. A cash prize is awarded to the first person to factor each challenge number.
RSA numbers were originally spaced at intervals of 10 decimal digits between one and five hundred digits, and prizes were awarded according to a complicated formula. These original numbers were named according to the number of decimal digits, so RSA-100 was a hundred-digit number. As computers and algorithms became faster, the unfactored challenge numbers were removed from the prize list and replaced with a set of numbers with fixed cash prizes. At this point, the naming convention was also changed so that the trailing number indicates the number of digits in the binary representation of the number. Hence, RSA-640 has 640 binary digits, which translates to 193 digits in decimal.
While RSA-640 has slightly fewer digits than the previously factored RSA-200, its factorization carries the additional benefit of a cash reward of $20,000 from RSA Laboratories to the team responsible for this feat.
RSA numbers received widespread attention when a 129-digit number known as RSA-129 was used by R. Rivest, A. Shamir, and L. Adleman to publish one of the first public-key messages together with a $100 reward for the message's decryption (Gardner 1977). Despite widespread belief at the time that the message encoded by RSA-129 would take millions of years to break, it was factored in 1994 using a distributed computation that harnessed networked computers spread around the globe performing a multiple polynomial quadratic sieve (Leutwyler 1994). The result of all the concentrated number crunching was decryption of the encoded message to yield the profound plain-text message "The magic words are squeamish ossifrage." (An ossifrage is a rare predatory vulture found in the mountains of Europe.)
Factorization of RSA-129 followed earlier factorizations of RSA-100, RSA-110, and RSA-120. The challenge numbers RSA-130, RSA-140, RSA-150, RSA-155, RSA-160, RSA-200, and RSA-576 were also subsequently factored between 1996 and May of 2005.
The factorization of the latest RSA number to fall involved "lattice" sieving done by J. Franke and T. Kleinjung using hardware at the Scientific Computing Institute and the Pure Mathematics Institute at Bonn University, Max Planck Institute of Mathematics in Bonn, and Experimental Mathematics Institute in Essen. Post-processing of this data to construct the actual factors was then done with the support of the BSI. The factorization of RSA-640 was accomplished using a prime factorization algorithm known as the general number field sieve, and the two 97-digit factors found using this sieve are
1634733 6458092538 4844313388 3865090859 8417836700 3309231218 1110852389 3331001045 0815121211 8167511579
1900871 2816648221 1312685157 3935413975 4718967899 6851549366 6638539088 0271038021 0449895719 1261465571
These numbers can easily be multiplied to verify that their product is indeed equal to the original number.
As the following table shows, RSA-704 to RSA-2048 remain open, carrying awards from $30,000 to $200,000 to whoever is clever and persistent enough to track them down. A list of the open challenge numbers may be downloaded from RSA or in the form of a Mathematica package from the MathWorld package archive.
|RSA-130||130||Apr. 10, 1996|
|RSA-140||140||Feb. 2, 1999|
|RSA-150||150||Apr. 16, 2004|
|RSA-155||155||Aug. 22, 1999|
|RSA-160||160||Apr. 1, 2003|
|RSA-200||200||May 9, 2005|
|RSA-576||174||$10,000||Dec. 3, 2003|
Gardner, M. "Mathematical Games: A New Kind of Cipher That Would Take Millions of Years to Break." Sci. Amer. 237, 120-124, Aug. 1977.
Leutwyler, K. "Superhack: Forty Quadrillion Years Early, a 129-Digit Code Is Broken." Sci. Amer. 271, 17-20, 1994.
NFSNet: Large-Scale Distributed Factoring.
RSA Security®. "The New RSA Factoring Challenge."
RSA Security®. "The RSA Challenge Numbers."
Weisstein, E. W. Mathematica package RSANumbers.m.
Weisstein, E. W. "RSA-576 Factored." MathWorld Headline News. Dec. 5, 2003.
Weisstein, E. W. "RSA-200 Factored." MathWorld Headline News. May 10, 2005.
Here is the text of the email sent by the team that factored the number:
From: "Jens Franke" Date: Fri, 04 Nov 2005 16:53:08 +0100
We have factored RSA640 by GNFS. The factors are
We did lattice sieving for most special q between 28e7 and 77e7 using factor base bounds of 28e7 on the algebraic side and 15e7 on the rational side. The bounds for large primes were 2^34. This produced 166e7 relations. After removing duplicates 143e7 relations remained. A filter job produced a matrix with 36e6 rows and columns, having 74e8 non-zero entries. This was solved by Block-Lanczos.
Sieving has been done on 80 2.2 GHz Opteron CPUs and took 3 months. The matrix step was performed on a cluster of 80 2.2 GHz Opterons connected via a Gigabit network and took about 1.5 months.
Calendar time for the factorization (without polynomial selection) was 5 months.
More details will be given later.
F. Bahr, M. Boehm, J. Franke, T. Kleinjung
The article itself explains a bit on what use may be made of factoring large numbers. Cracking codes is one of the biggest of these and that should be of great interest to those of us who use the internet for any economic activity, as it is cyphers such as RSA which are used to protect your transactions with EBAY, Amazon, and others.
For those not terribly familiar with this stuff, I'd like to point out that this accouncement of a crack of "RSA-640" is not a general "crack" of the code itself, meaning any message that might be created with RSA-640 is now decryptable. Rather, this announcement is the specific decryption of a single message encrypted with RSA-640. What we do know now though, is that someone with 80 2.2 GHz Opteron CPUs can crack such a message in 5 months.
Mathematicians celebrate worldwide with a riots and looting.
I'll take your word for it...........
There goes MY e-mail security. Darn. Thanks for the enlightening post.
No machine can decrypt what Mohammad whispers into Omar's ear.
As long as my tax dollars aren't paying for it...
It is therefore reasonable to assume that the NSA, with its large number of trained cryptanalysis folks, and its large computer budget, could have already cracked everything on that list already.
A team at the German Federal Agency for Information Technology Security (BSI)...
Here's another math thread!
LOL @ your tag.
I wondered about that once. Then I went out for a burger and forgot about it.
Dammit! They got there just an hour ahead of me!
"I'll take RSA-2048 for $200,000, Alex."
When he told me this I laughed out loud. I stopped laughing as I searched his face for signs he was joking.
Absolutlely fascinating. But you lost me at the word "factorization' in the first sentence.
Keep posting articles from Mathworld. Perhaps I'll learn enough to make it through the second sentence.
Hmmm, the awesome power of the AMD Opteron CPU strikes again. :-)
LOL. If I'd known how much I'd be fascinated by things mathematical in nature later in life, I'd take math a lot more seriously in school. Google "Mandelbrot". Stunning display of math at it's most artistic.
I think the list is just a thermometer the NSA uses to judge the speed at which lesser entities evolve in their decoding abilities.
Although I made all "A"s in Algebra and Geometry in high school, I was never a great math lover.
At Columbia college, I took the supposed gut course for liberal artts majors "Math for Poets" (set theory) but ran afoul of a professor who couldn't seem to distinguis between his higher math classes and a bunch of dumbos who were just trying to get through the math requirement. He'd work a set of equasions all across 30' feet of a blackboard, and then turn around with a beatific smile and say, "Okay?"
They had to bring in a tutor to get most of us through.
I'm now 65 and somehow never once had to use an Algebraic equasion to have a successful business career.
I've heard references to the "Cray Acre" before. Given the NSA's black budget, I suspect it's probably true. In fact, I'd be surprised if it wasn't.
Disclaimer: Opinions posted on Free Republic are those of the individual posters and do not necessarily represent the opinion of Free Republic or its management. All materials posted herein are protected by copyright law and the exemption for fair use of copyrighted works.