RSA129 factoring attack -- participants needed
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-...@iastate.edu to be added to this list.
For more information, please mail rsa12...@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 <expl...@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-pub...@pgp.iastate.edu <*=-
Paul Fahn
> 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.
This is not correct. Commonly-used RSA systems use key sizes significantly
larger than 425 bits. Common RSA key sizes range from 512 bits to 1024.
Factoring RSA-129 does not in any way jeopardize the security of widely
used versions of RSA.
Paul
Roberto Sierra
: > 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.
FYI --
I set this up to run on the Sun system here and caught a little typo
in the makefile (the current version on the FTP server has been fixed,
so I'm told). If you have a Sun4 running SunOS and have the older code
and not the fixed version, change the section of the Makefile that reads
# Sun-4 with assembler speed-up
S4a_mpqs: sparc-sunos.s mpqs.c lip.c
$(MAKE) all CC=gcc CFLAGS="-O -DCONTRIBUTION_8" ASMFLAGS="-P -DFPU"\
OBJS="mpqs.o lip.o sparc-sunos.o" FILE=made_S4a_mpqs
to
# Sun-4 with assembler speed-up
S4a_mpqs: sparc-sunos.s mpqs.c lip.c
$(MAKE) all CC=gcc CFLAGS="-O -DCONTRIBUTION_8" ASMFLAGS="-P -DFPU" \
OBJS="mpqs.o lip.o sparc-sunos.o" FILE=made_S4a_mpqs
[the only difference is the insertion of a space before the \ character]
Otherwise gcc will fail to link the code properly.
--
\\|//
- - "Information gladly given, but safety requires
o o avoiding unnecessary conversation." -- MUNI
J roberto sierra
O tempered microdesigns NOTICE:
\_/ san francisco, calif. None of the ideas expressed herein
be...@netcom.com have anything to do with reality.
Paul C Leyland
You are both correct. It is very common to use RSA keys in the range
512 to 1024 bits. However, PGP (for example) provides 384-bit keys as
an option and quite a few people have taken up this option. Get hold of
the keyring from a public key server if you wish to check this claim.
I have been telling people to use at least 512-bit keys and they really
ought to be using much larger ones. Nonetheless, running RSA on a small
computer, in the 8086 class, can be so slow that some people trade off
security for convenience.
We can estimate that factoring 512-bit numbers is somewhere between a
hundred and a thousand times more difficult than factoring 425-bit
numbers. This increase in difficulty is sufficiently small that one
should be concerned about the security of 512-bit keys in the near
future.
Paul
--
Paul Leyland <p...@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 p...@black.ox.ac.uk for PGP key |