[RC5] RSA Secret-Key Challenge Termination

david fleischer cilantro_il at yahoo.com
Sun May 27 04:38:50 EDT 2007

This is great! As we know, the RC5 is np-complete. Which 
makes it important, but a little "dry". There are incentives; 
the development community, the cash, the incremental 
improvements of which the hardware accelerators should
be an important part (check out the EFF cracker).

As you say, the factoring challenge is in addition a more
fertile research field in that a substantial portion of the alg-
orithm has to be adapted to distributed computing. Namely
if I'm not mistaken a huge matrix solver has to be developed
for distributed computation. Think of the potential applications
for this...

----- Original Message ----
From: Décio Luiz Gazzoni Filho <decio at decpp.net>
To: D.net Discussion <rc5 at lists.distributed.net>
Sent: Sunday, May 27, 2007 4:47:47 AM
Subject: Re: [RC5] RSA Secret-Key Challenge Termination

Le May 26, 2007 à 4:30 PM, david fleischer a écrit :

> In addition to the RC5 project (wich I hope will continue)
> we should also look into the factoring challenge.
> RC5 is np-complete, by definition. Which makes it an
> important benchmarking project. Factoring is believed
> to be np-complete, but there isn't any proof. However
> there are quite a number of algorithms, with code ready.
> D.net could adapt this to an applet easily.

I'm sorry, I wish it was that easy, but it's not.

Currently, factoring large integers is accomplished using either the  
elliptic curve method (ECM) or the number field sieve (NFS). The  
former is well suited to implementation in a distributed effort over  
the internet (independent work units, with no communication between  
participants and little communication between participants and the  
server), and it's quite efficient for removing `small' factors out of  
large or huge numbers, hence suitable for factoring most integers  
(due to the distribution of prime factors in a `random' integer) --  
unfortunately, RSA challenge numbers are far from random in that  
regard; it is known that they factor into two similarly-sized prime  
factors, each of which is about half the size of the original  
integer. For such integers, only the latter algorithm (NFS) is  
practical. NFS is divided into 5 main stages:

1. Polynomial selection: probably doable over a distributed network;
2. Sieving: most expensive part of the algorithm, known to be doable  
over a distributed network;
3. Filtering: requires an SMP machine or a cluster with high-speed  
interconnect, but not all that expensive, wouldn't be a bottleneck;
4. Linear algebra: very expensive, requires an SMP machine or a  
cluster with high-speed interconnect;
5. Square root: small cost, some hours (or at most a few days) in a  
single fast computer.

If it weren't for step 4, the algorithm could be implemented in a  
distributed network such as distributed.net. As it stands, some kind  
soul would have to arrange for processing time in the sorts of  
expensive machines that can tackle problems of this size (and few are  
willing to give such processing time away). More esoteric  
possibilities would be to develop a linear algebra algorithm suitable  
for a distributed network topology (good luck with that) or  
implementing this step in ASICs or FPGAs -- see for instance Dan  
Bernstein's proposal for integer factoring circuits, which uses a  
mesh architecture for linear algebra.

Note though that the cost of factoring a 1024-bit RSA modulus, the  
next milestone of real interest, is estimated to be similar to that  
of an 80-bit symmetric key crack, i.e. RC5-80, which by itself is  
~2^8 = 256 times harder than RC5-72, and we know first-hand how hard  
RC5-72 already is...

rc5 mailing list
rc5 at lists.distributed.net

More information about the rc5 mailing list