26 Oct

RSA Factoring Challenge -- pass it on

Date: Tue, 26 Oct 93 15:29:43 PDT To: Fun_People Subject: RSA Factoring Challenge -- pass it on From rsa129-info@iastate.edu Wed Sep 22 09:56:40 EDT 1993 From: explorer@iastate.edu (Michael Graff) CALL FOR PARTICIPANTS ---------------------- In 1977, a 129-digit integer appeared in the pages of Scientific American. This number, the RSA challenge modulus or RSA-129, has not yet been successfully factored. Factoring it, a 425-bit number, would be a major milestone in cryptography, as it would show that current technology is able to break commonly-used RSA-cryptosystem keys within a reasonable time. 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 = 11438162575788886766923577997614661201021829672124236256256184 29357069352457338978305971235639587050589890751475992900268795 43541 (129 digits, checksum = 105443) ---- End of RSA Factoring Challenge news --- As with several other recent large scale factoring projects, we are attacking 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 are using the publicly available code of the Lenstra/Manasse Factoring by Email project, with modifications by Paul Leyland and Derek Atkins for RSA-129 and multiple machine types. The sieving is 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 is 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. However, the program does require rather a lot of active virtual memory -- at least 6.5 megabytes and the more you have the faster it runs. That said, it runs happily on any Unix box with at least 8Mb of physical memory. It is currently running on Suns (SunOS and Solaris), DEC (MIPS and Alpha), HP-UX, Linux, NetBSD, 386BSD, FreeBSD, and RS6000 machines. The project currently has around 500 workstations which are busy 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. We estimate that we are over 5% of the way to completion at this time. 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. SOURCE CODE and ID INFORMATION ------------------------------- Source code can be obtained by FTP (or using a FTP to mail gateway) from toxicwaste.mit.edu as /pub/rsa129/MPQS.shar.Z black.ox.ac.uk as /math/rsa129/MPQS.shar.Z To unpack it (on a Unix system) do: uncompress MPQS.shar.Z sh MPQS.shar It will unpack several files, one of which is called ``README'', which should be consulted for building instructions, information on how to obtain a set of IDs, and input files for this project. If you need this via mail or have further questions, please mail a message to the address below. STATUS REPORTS and WORKER MAILING LIST --------------------------------------- A mailing list for status reports and other informational mailing is maintained. Send mail to rsa129-request@iastate.edu to be added to this list. For more information, please mail rsa129-info@iastate.edu. We will respond to all questions quickly. - --Michael Graff [project coordinator/programmer] - --Derek Atkins [coordinator/programmer] - --Paul Leyland [advisor/programmer] - --Daniel Ashlock [faculty advisor ISU] - -- Michael Graff <explorer@iastate.edu> Speaking for myself, not Project Vincent Voice: (515)294-4994 for ISU or the ISUCC Iowa State Univ Comp Center Fax: (515)294-1717 Ames, IA 50011 -=*> PGP key on pgp-public-keys@pgp.iastate.edu <*=- - ---------------------------- ... and the progress report: - ---------------------------- One million and counting.... 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). The full relations are usable as they stand. The pars and pprs have to be further processed to find cycles. So far, we have 1679 cycles. 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 - -- Paul Leyland <pcl@oxford.ac.uk> | Hanging on in quiet desperation is Oxford University Computing Service | the English way. 13 Banbury Road, Oxford, OX2 6NN, UK | The time is gone, the song is over. Tel: +44-865-273200 Fax: +44-865-273275 | Thought I'd something more to say. Finger pcl@black.ox.ac.uk for PGP key |

© 1993 Peter Langston