Fun_People Archive
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