[RC5] RSA Secret-Key Challenge Termination
Décio Luiz Gazzoni Filho
decio at decpp.net
Sat May 26 21:47:47 EDT 2007
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...
More information about the rc5