[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