A Discussion of RSA-129 Activity.

Introduction

Original Call for Participants (September 3, 1993)

Excerpted from the RSA Factoring Challenge news:

The "RSA challenge" published in the August 1977 issue of Scientific American (in Martin Gardner's column) is still open, and the $100 prize offer still stands. This prize can be won by factoring the RSA modulus published there, which is:

RSA-129 = 11438162575788886766923577997614661201021829672124236256256184293 5706935245733897830597123563958705058989075147599290026879543541 (129 digits, checksum = 105443)

--- End of RSA Factoring Challenge news ---

As with several other recent large scale factoring projects, we propose to attack this number with a very large number of workstations independently operating at dozens of research and corporate networks around the world. We are soliciting volunteers to provide compute cycles to help us towards our goal.

With the permission of the authors, we will use the publicly available code of the Lenstra/Manasse Factoring by Email project, with modifications by Paul Leyland for RSA-129. The sieving will be distributed around the Internet, with relations transferred to a central site by email or ftp as convenient. Combining the relations and matrix elimination will be performed at ISU, using a combination of structured Gauss and a MasPar dense matrix eliminator.

Each participant will be provided with complete source code for the siever. You can easily verify that the program takes no input from your machines and does not pose a security risk. It requires only an email connection to transmit partial results -- the software does not require communication with other machines except for this purpose. It is easy to install, and is designed so that it will take up no CPU cycles on your machine when interactive users or other important processes are active. If preferred, participants can accumulate the results locally and ftp them to the central site manually.

The project currently has around 500 workstations which are ready to begin sieving. However, to finish in a reasonable amount of time, this count needs to increase greatly. We are attempting to enroll around 10,000 workstations in this project.

This is a call for participants, who have workstations or MasPars at their disposal and would like to participate in this project. All contributions help a great deal.

There is a $100 prize associated with factoring this number. The prize, if we win it, will be donated to the GNU project of the Free Software Foundation to help generate more of the excellent software they currently provide.

--Michael Graff [project coordinator/programmer]

--Derek Atkins [coordinator/programmer]

--Paul Leyland [advisor/programmer]

--Daniel Ashlock [faculty advisor ISU]

Status Report (October 20, 1993)

The RSA-129 project has just passed the one million relations mark.

As of 5am UT, Wednesday 20 October 1993, hot-spare.mit.edu had received 1030805 relations. These are distributed as follows:

• 14263 full relations (fuls)
• 182353 partial relations (pars)
• 834189 double partial relations (pprs).

When the sum of the fulls and the cycles reach 524400 we are almost done. A few hours work on a workstation, followed by some heavy crunching on a MasPar and we will know the Ultimate Answer (and I will be most upset if it turns out to be 42 :-)

The number of cycles might seem to be disappointingly small. However, the number of cycles per par and per ppr grows quadratically with the number of relations collected. We had fewer than 100 cycles in from the first 250k relations; we now have 20 times as many cycles from only four times as many relations.

Because we still have relatively few cycles, it is difficult to give an accurate estimate of how much further we have to go. However, I can give a guestimate which won't be too far out. We know from previous large-scale runs of MPQS, that the final total consists of about 20% fulls and 80% cycles. As we need something over half a million altogether, we can divide the number of cycles by one thousand, and call that the percentage completion. Accordingly, my best estimate is that we are about 14% done.

As more machines come on-stream, we are collecting more and more relations per day. During October, we have averaged 24247 relations per day, with a peak of 31162 last Sunday. Machines tend to be more idle at the weekend; this shows up quite clearly in our statistics. It is difficult to determine exactly how many machines are contributing; certainly many hundreds. Even more would be nice, of course! What I can say is that we have allocated over 9000 UIDs so far.

The following is also very rough and ready. My DEC 5000/25 generates one relation per 1100 seconds on average, and is rated at 15MIPS or so. Therefore, 24000 relations per day corresponds to an *average* compute power of 4600MIPS. That's a powerful supercomputer by most people's standards. Almost all of this computation comes from machine time that would otherwise go to waste.

So, a big thank you to everyone who has contributed to the project so far. Your help is much appreciated. Anyone reading this who has not joined in yet, is invited to send email to rsa129-info@iastate for more information. All you need is a Unix box with at least 8Mb of memory, some idle cputime, and a desire to join in the largest single computation currently taking place anywhere on the Internet.

Paul Leyland

Status Report (February 21, 1994)

Here is what I hope is the penultimate progress report for the RSA-129 project. That is, I believe that by this time next month we will be very near the end of the networked portion of the factoring program.

First, the raw figures. As of 0600UT, 20 February 1994 we have 6632193 relations, made up of 86737 fulls, 1120177 partials (pars) and 5425279 double partials (pprs). The pars and pprs together yield 202828 cycles. When the sum (cycles + fulls) exceeds 524400, we have enough relations. You will note that by this measure, we have more than half -- the sum is 289565.

The rate of growth in cycles is much faster than linear. A quartic fits it very well right now, though why this should be no-one yet knows. Using the most recent data, we can predict that when we have about 108000 fulls, and 8.2 million pars and pprs, we'll have enough. Using these figures, I conclude that we are almost exactly 80% finished. How this produces a finishing *date* depends, of course, on how many relations we get each day from our contributors. We have not received so many this month as last, but that is to be expected since last month's figures included the Xmas and New Year holidays when we should expect machines not to be doing real work but rather to run mpqs. If last month's rate is continued, I expect that we will have enough relations by the last week in March.

Of course, we won't have a factorization by then. The largest part will have completed, but about 3-4 weeks work needs to be done. This work can not easily be parallelized over the Internet. The ultimate answer should be known before the end of April.

Summary:  86737 fuls, 1120177 pars. 5425279 pps, 6545456 relations.
          202828 cycles.
          80% of the networked portion completed.
          Network should be finished  20-31 March       (Deo volente)
          Factorization completed before 30 April            ditto

Paul Leyland

Final Answer (April 27, 1994)

RSA-129 = 11438162575788886766923577997614661201021 82967212423625625618429357069352457338978 30597123563958705058989075147599290026879543541

= 3490529510847650949147849619903898133417764638493387843990820577 * 32769132993266709549961988190834461413177642967992942539798288533

The encoded message published was

968696137546220614771409222543558829057599911245743198746951209 30816298225145708356931476622883989628013391990551829945157815154

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

106698614368578024442868771328920154780709906633937862801226224 496631063125911774470873340168597462306553968544513277109053606095

this becomes

20080500130107090300231518041900011805 0019172105011309190800151919090618010705

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

Comments on the future

Using the quadratic sieve, it takes roughly a factor of 10 more computing resources (disks & cycles, if not keyboards) to factor each additional 10 digits. Further, that factor of ten becomes available in off-the-shelf workstations every 2-5 years. In practice, the biggest factorable number has been growing by about 10 digits per year, thanks in part to algorithmic improvements. I (and others) figure 512 bits will become inadequate by the late '90's. At the crypto '93 conference, where rsa-120's demise was announced (it took 1/6 as much resources), people were already recommending the move to 768-bit or 1024-bit rsa keys.

It's not yet possible to guess at what it would take to crack a 1024-bit key, because the general number field sieve, which will eventualy/soon replace the quadratic seive as the fastest factoring algorithm, has unknown constants in its complexity- growth curve. Once gnfs sees some use, those constants will get pinned down a little, and such predictions will then be more possible. Here, I'm paraphrasing what I heard last year at crypto.

-Don Davis, Openvision