[RC5] RSA Secret-Key Challenge Termination

[Décio Luiz Gazzoni Filho]

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...

Décio