[rc5] Let's factor RSA-155!

Jason C. Harris jason.harris at internetmci.com
Thu Oct 23 22:36:39 EDT 1997

At 09:10 PM 10/23/97 -0400, you wrote:
>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.

Here, here!!

Jason C. Harris

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

More information about the rc5 mailing list