RSA-129

We are happy to announce that

RSA-129 = 1143816257578888676692357799761466120102182967212423625625618429\
          35706935245733897830597123563958705058989075147599290026879543541
        = 3490529510847650949147849619903898133417764638493387843990820577 *
          32769132993266709549961988190834461413177642967992942539798288533


The encoded message published was

968696137546220614771409222543558829057599911245743198746951209308162\
98225145708356931476622883989628013391990551829945157815154

This number came from an RSA encryption of the `secret' message using the
public exponent 9007. When decrypted with he `secret' exponent

106698614368578024442868771328920154780709906633937862801226224496631\
063125911774470873340168597462306553968544513277109053606095

this becomes

200805001301070903002315180419000118050019172105011309190800151919090\
618010705

Using the decoding scheme 01=A, 02=B, ..., 26=Z, and 00 a space between
words, the decoded message reads

THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE



To find the factorization of RSA-129, we used the double large prime
variation of the multiple polynomial quadratic sieve factoring method.
The sieving step took approximately 5000 mips years, and was carried
out in 8 months by about 600 volunteers from more than 20 countries,
on all continents except Antarctica. Combining the partial relations
produced a sparse matrix of 569466 rows and 524338 columns. This matrix
was reduced to a dense matrix of 188614 rows and 188160 columns using
structured Gaussian elimination. Ordinary Gaussian elimination on this
matrix, consisting of 35489610240 bits (4.13 gigabyte), took 45 hours
on a 16K MasPar MP-1 massively parallel computer. The first three
dependencies all turned out to be `unlucky' and produced the trivial
factor RSA-129. The fourth dependency produced the above factorization.

We would like to thank everyone who contributed their time and effort
to this project. Without your help this would not have been possible.

Derek Atkins
Michael Graff
Arjen Lenstra
Paul Leyland

Derek Atkins wrote:


> We are happy to announce that
> 
> RSA-129 = 1143816257578888676692357799761466120102182967212423625625618429\
>           35706935245733897830597123563958705058989075147599290026879543541
>         = 3490529510847650949147849619903898133417764638493387843990820577 *
>           32769132993266709549961988190834461413177642967992942539798288533
> 
> To find the factorization of RSA-129, we used the double large prime
> variation of the multiple polynomial quadratic sieve factoring method.
> The sieving step took approximately 5000 mips years, and was carried
> out in 8 months by about 600 volunteers from more than 20 countries,
> on all continents except Antarctica. Combining the partial relations

Now let's see, where's my slide rule, let's see 5,000 mips years
at $30,000 /mips = damn, where is that calculator. :-)

> We would like to thank everyone who contributed their time and effort
> to this project. Without your help this would not have been possible.
> 
> Derek Atkins

Nahh, couldn't be, 

> Michael Graff
> Arjen Lenstra
> Paul Leyland
>

Derek Atkins reports to us:

> 
> We are happy to announce that
> 
> RSA-129 = 1143816257578888676692357799761466120102182967212423625625618429\
>           35706935245733897830597123563958705058989075147599290026879543541
>         = 3490529510847650949147849619903898133417764638493387843990820577 *
>           32769132993266709549961988190834461413177642967992942539798288533


Of course. What else could it be?

First, to check your result, firing up Mathematica 2.2 gives:

Timing[3490529510847650949147849619903898133417764638493387843990820577

32769132993266709549961988190834461413177642967992942539798288533]

{0.0666667 Second, 11438162575788886766923577997614661201021\
 
   829672124236256256184293570693524573389783059712356395870\
 
   5058989075147599290026879543541}


That is, it took MMA only 0.066 second, mostly overhead, to multiply
your two factors to the product you gave.

But much more interesting is seeing how long MMA's "FactorInteger"
function takes to find the factors:

Timing[FactorInteger [11438162575788886766923577997614661201021\

   829672124236256256184293570693524573389783059712356395870\

   5058989075147599290026879543541]]

{4194 Second,

{{3490529510847650949147849619903898133417764638493387843990820577, 1}, 

{32769132993266709549961988190834461413177642967992942539798288533, 1}}}

So, this took slightly longer, 4194 seconds, or a bit over an hour,
but MMA had no problem factoring this number. Why such a big deal?

MMA was even able to extract the magic words:

ExtractMagicWords [%]

{ NOTE THAT THE TIMING ABOVE HAS A CERTAIN DATE VALUE }

You people at the universities sure do know how to waste taxpayer
money!

--Tim May

P.S. My congratulations. No practical use to factor just one such
number, given 10^72 particles in the Universe, but the methods used to
harness so many machines may be useful in all kinds of problems.

-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^859433 | Public Key: PGP and MailSafe available.
"National borders are just speed bumps on the information superhighway."

[stuff deleted]
> That is, it took MMA only 0.066 second, mostly overhead, to multiply
> your two factors to the product you gave.
[more stuff deleted]
> So, this took slightly longer, 4194 seconds, or a bit over an hour,
> but MMA had no problem factoring this number. Why such a big deal?

Cute, Tim!  (Uhh, you're about 3 weeks too late for this ;-)

Actually, the *first* thing I did when I received these factors was
fire up a trusty mathematics package and verify the product: bc. :-)

Although I admit that RSA-129 dprobably does not have any cosmic
significance with regards to protecting any vital data, it is a data
point: it is the largest number of its type to ever have been
factored.  As a result, it tells us that 425-bit keys are not secure,
and keys not much bigger are not secure, either, today!

But you are right, we are learning alot about factoring and
distributed problems as a result of this exercise (at least I feel
that I have learned alot).

-derek

         Derek Atkins, SB '93 MIT EE, G MIT Media Laboratory
       Member, MIT Student Information Processing Board (SIPB)
    Home page: http://www.mit.edu:8001/people/warlord/home_page.html
       warlord@MIT.EDU    PP-ASEL     N1NWH    PGP key available