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 *M*_{42} (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 |

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

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.

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**

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

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.

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**

Here's another math thread!

To: **Red Badger**

LOL @ your tag.

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

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

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.

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.

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.

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**

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**

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

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.

To: **Steely Tom**

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.

FreeRepublic.com is powered by software copyright 2000-2008 John Robinson