[rc5] Let's factor RSA-155!

Trei Family trei at relay-1.ziplink.net
Thu Oct 23 22:10:09 EDT 1997


First of all, my heartfelt congratulations go out Adam, Jeff, Dave, Peter
Stuer, Jo Hermans, and everyone who contributed cycles (which I did to 
a small extent). This has been an astounding effort!

But where next? 64 bit RC5 is the target most people are talking about, but
it's at least 256x as far away; even if we got 10x the number of cycles, 
we're talking about several years of effort. Note that the RC5/56 growth 
rate was leveling out at the end.

There's another target.

* It's a lot easier than RC5/64 - it should take no longer than RC5/56.
* It's got twice the prize money.
* It's also sponsored by RSA.
* It's important, both politically and for improving Internet security.

It's the factorization of RSA-155.

This is roughly equivalent to a 512 bit RSA modulus. (the 155 refers to
decimal digits, not bits).

Long before RSA posted the secret key challenges (at my suggestion, he said
smugly :-), RSA created a series of challenge moduli for factoring tests. 
The largest number which has ever been factored is RSA-130. It's been 
estimated that RSA-155 (10^25 times larger!) could be factored in about 
500,000 MIPS years using the quadratic seive (QS) method, and 
about 17,000 MIPS years (if I remember correctly), using the 
General Number Field Seive (GNFS) method. 

GNFS has problems - the clients would probably require about 128 MB of RAM,
and the final data reduction would strain a supercomputer. While the QS
method requires more cycles, it can run on much more modest clients, and 
the data reduction step is also far more tractable. 

512 bit RSA keys are also the largest which can be easily exported from the
US. Thus, factoring one would show the vulnerabilities of all the easily 
exportable algorithms: 40 bit RC4, 56 bit DES, and 512 bit RSA. It would 
thus complete the 'triple crown' of weak cryptography, and leave those 
who would make us use vulnerable systems without a leg to stand on.  

Lets do the numbers:

500,000 MIPS years = about 1.6e19 instructions.

RC5/56 was cranking at a rate equivalent to 26,000 Pentium 200s (from the
victory announcement).

A Pentium running properly optimized code gets close to 2 instructions per
clock, so a Pentium 200 gets about 400 MIPS

26,000 of them get about 10 TIPS. (1e13 instructions/sec)

Thus, 1.6e19 instructions would take about 1.6e6 seconds, or around 19 days.

Now, real results won't be anywhere near this good - pairing is not perfect
in any program, and QS is memory intensive; RC5 probably never left
the L1 cache (or the L2 at worst). Let's add a factor of 10 to allow for
the inefficiencies.

We could then factor RSA-155 in 6 months, wall calender time.

The prize, last I checked, stood at over US $18,000, and is probably
around $20k by now.

Let's think about this one, before we plunge to years of effort on RC5/64.
If we head straight for RC5-64, we're likely to fail.

Peter Trei
trei at ziplink.net

Disclaimer: The above is my personal opinion, 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