[rc5] Factoring RSA-155.

Trei Family trei at relay-1.ziplink.net
Sat Oct 25 00:51:35 EDT 1997


My suggestion that an effort be made to factor RSA-155 seems to have 
generated quite a bit of enthusiasm. Now if we can just get distributed.net
interested...

In my earlier letter, I indicated that, at the level of participation
seen at the end of the Bovine effort, I thought that it could be done
in 6 months at the outside. I stand by that number.

For various reasons I cannot participate in such an effort, except
as a cheerleader.

People who wish to investigate further should look into the efforts
to factor RSA-129. Some of the code used, with documentation,
can be found at ftp://ftp.ox.ac.uk/pub/math/rsa129. There is a newer
version of freelip, the long integer package used, in 
/pub/math/freelip.

This is unix code. It will need some modification to run on other 
platforms, and to handle RSA-155. These modifications are not trivial,
and will need to be performed by someone who understands the underlying
mathematics.

-------------

Factoring is quite a bit different from brute forcing a key to a
symmetrical cipher. The file 'mpqs_sans_math.Z' contains a layman's
overview.

     There are basicly 2 phases - the first is a 'sieving' operation. 
This takes the bulk of the cpu time, and can be performed on fairly 
modest machines. Sieving produces lists of 'relations'. After enough 
relations have been gathered, a (huge) matrix is prepared (on a 
machine with Gbytes of RAM) using them, which eventually leads the the 
factors of the number.

Here's the facts as I understand them (no guarentees):

1. The sieving machines do not need to be coordinated. 
2. A central site is required to gather the relations - this is a
substantial storage requirement, possibly several gigabytes.
3. Relations need not be sent in immediately - they could be stored
on the seiving machines until they are needed. The storage requirement
for any given machine is quite modest. Teams could compete on the
basis of the rate at which they find relations.
4. The program creates a large file the first time it is run.
This may be as large as 50Mb. It's created once, and then statically 
read. On networked machines, this file can be shared.
5. It will be impossible to say that the factors were discovered by
any particular siever.
6. Time on a supercomputer will needed for the final
reduction steps. I suspect that this project is interesting 
enough that time can be donated.

Peter Trei
trei at ziplink.net

DISCLAIMER: The above is my own view, and should not be misconstrued
to represent that of my employer.


----
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.



More information about the rc5 mailing list