Free Republic Browse · Search News/Activism Topics · Post Article

RSA-640 Factored
MathWorld News ^ | November 8, 2005 | Eric W. Weisstein

Posted on 11/09/2005 4:44:53 AM PST by zeugma

RSA-640 Factored

By Eric W. Weisstein

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
x
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.

number digits prize factored
RSA-100 100   Apr. 1991
RSA-110 110   Apr. 1992
RSA-120 120   Jun. 1993
RSA-129 129 \$100 Apr. 1994
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
RSA-640 193 \$20,000 Nov. 2005
RSA-704 212 \$30,000 open
RSA-768 232 \$50,000 open
RSA-896 270 \$75,000 open
RSA-1024 309 \$100,000 open
RSA-1536 463 \$150,000 open
RSA-2048 617 \$200,000 open

References

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.
http://www.nfsnet.org

RSA Security®. "The New RSA Factoring Challenge."
http://www.rsasecurity.com/rsalabs/challenges/factoring

RSA Security®. "The RSA Challenge Numbers."

http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html

Weisstein, E. W. Mathematica package RSANumbers.m.

Weisstein, E. W. "RSA-576 Factored." MathWorld Headline News. Dec. 5, 2003.

http://mathworld.wolfram.com/news/2003-12-05/rsa

Weisstein, E. W. "RSA-200 Factored." MathWorld Headline News. May 10, 2005.
http://mathworld.wolfram.com/news/2005-05-10/rsa-200

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

16347336458092538484431338838650908598417836700330\ 92312181110852389333100104508151212118167511579

and

19008712816648221131268515739354139754718967899685\ 15493666638539088027103802104498957191261465571

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

KEYWORDS: computers; cryptography; decryption; primes; rsa
While some don't believe there is much point to the challenges put out like the RSA Security, I like to point these out, as they tend to give us a heads up on where the approimate state of the art of such things are. You'll note that this was not just a straight brute-force crack of the 193-digit number, as is being attempted by the Distributed.net folks.

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.

1 posted on 11/09/2005 4:44:55 AM PST by zeugma

To: zeugma

Mathematicians celebrate worldwide with a riots and looting.

/s

2 posted on 11/09/2005 4:57:31 AM PST by IndyInVa (There needs to be less corruption. Or more opportunity for me to participate in it.)

To: zeugma
These numbers can easily be multiplied to verify that their product is indeed equal to the original number.

I'll take your word for it...........

3 posted on 11/09/2005 5:09:35 AM PST by Red Badger (Whatever happened to formulas 1 through 408?.........)

To: zeugma

There goes MY e-mail security. Darn. Thanks for the enlightening post.

4 posted on 11/09/2005 5:09:54 AM PST by dhuffman@awod.com (The conspiracy of ignorance masquerades as common sense.)

To: zeugma

No machine can decrypt what Mohammad whispers into Omar's ear.

5 posted on 11/09/2005 5:11:01 AM PST by MindBender26 (Having my own CAR-15 in RVN meant never having to say I was sorry......)

To: zeugma

As long as my tax dollars aren't paying for it...

6 posted on 11/09/2005 5:13:36 AM PST by Brilliant

To: zeugma
Just remember, that 80 Opteron boxes will go for less than \$80K as a one time capital cost. Then will cost a couple hundred per month for electricity to run.

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.

7 posted on 11/09/2005 5:28:18 AM PST by ikka

To: Brilliant
Your tax dollars are paying for research like this. They just are not telling you the results. Cryptography is important stuff in the modern world. The NSA is particulary interested in new methods of cracking codes. In this case, it looks like Germany is funding this particular group...

A team at the German Federal Agency for Information Technology Security (BSI)...

8 posted on 11/09/2005 5:31:08 AM PST by zeugma (Warning: Self-referential object does not reference itself.)

To: SirKit

9 posted on 11/09/2005 5:57:52 AM PST by SuziQ

I wondered about that once. Then I went out for a burger and forgot about it.

10 posted on 11/09/2005 6:01:02 AM PST by Constitution Day

To: zeugma

Dammit! They got there just an hour ahead of me!

11 posted on 11/09/2005 6:04:56 AM PST by SlowBoat407 (The best stuff happens just before the thread snaps.)

To: zeugma

"I'll take RSA-2048 for \$200,000, Alex."

12 posted on 11/09/2005 6:15:18 AM PST by Mannaggia l'America

To: ikka
A friend of mine who was in the field in the '90's told me that the NSA's unit of computational power, at that time, was the "Cray acre." I don't know if this is still the case.

When he told me this I laughed out loud. I stopped laughing as I searched his face for signs he was joking.

13 posted on 11/09/2005 6:24:56 AM PST by Steely Tom (Fortunately, the Bill of Rights doesn't include the word 'is'.)

To: zeugma
For those not terribly familiar with this stuff, I'd like to point out that this announcement 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.

Exactly. It's like saying that it took a team of expert safe-crackers seven days to finally break into the Acme Safe Model 29X. Almost more of an endorsement of the product than a concern.
14 posted on 11/09/2005 8:34:23 AM PST by Atlas Sneezed (Your FRiendly FReeper Patent Attorney)

To: zeugma

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.

15 posted on 11/09/2005 8:45:40 AM PST by wildbill

To: zeugma

Hmmm, the awesome power of the AMD Opteron CPU strikes again. :-)

16 posted on 11/09/2005 9:14:49 AM PST by TChris ("The central issue is America's credibility and will to prevail" - Goh Chok Tong)

To: wildbill
Keep posting articles from Mathworld. Perhaps I'll learn enough to make it through the second sentence.

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.

17 posted on 11/09/2005 9:22:41 AM PST by zeugma (Warning: Self-referential object does not reference itself.)

To: ikka
"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."

I think the list is just a thermometer the NSA uses to judge the speed at which lesser entities evolve in their decoding abilities.

18 posted on 11/09/2005 9:32:39 AM PST by avg_freeper (Gunga galunga. Gunga, gunga galunga)

To: zeugma

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.

19 posted on 11/09/2005 9:36:13 AM PST by wildbill

To: Steely Tom
I stopped laughing as I searched his face for signs he was joking.

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.

20 posted on 11/09/2005 9:49:43 AM PST by AFreeBird (your mileage may vary)

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.

 Free Republic Browse · Search News/Activism Topics · Post Article

FreeRepublic, LLC, PO BOX 9771, FRESNO, CA 93794