[rc5] Let's factor RSA-155!

Dmitriy Bobkov dbobkov at raleigh.ibm.com
Fri Oct 24 11:57:41 EDT 1997

Does not sound to be a bad idea at all. And that will give everyone some
time to get more ppl involved and faster PC's will be already out. I'm in
for it.

trei at relay-1.ziplink.net on 10/23/97 09:10:09 PM

Please respond to rc5 at llamas.net

To:   rc5 at llamas.net
cc:   trei at ziplink.net (bcc: Dmitriy Bobkov/NWSMEL)
Subject:  [rc5] Let's factor RSA-155!

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

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.

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

More information about the rc5 mailing list