[RC5] possible third project...

Greg Wooledge greg at wooledge.org
Fri Jul 27 22:21:12 EDT 2001


Jonathan Smith (jsmith at cygnacom.com) wrote:

> Of course we could not use the general number field sieve.  We could just 
> brute force try the "keyspace", just like we are doing for rc5-64.

The keyspace in this case is the set of prime numbers which are less
than the square root of the number to be factored.  We need only to find
a single prime number p in this range such that p divides our number N.

According to the prime number theorem
<http://www.utm.edu/research/primes/howmany.shtml>, the number of primes
which are less than or equal to x is approximately x/log(x).

The number N to be factored is approximately 1.88 x 10^173.  The square
root of this is approximately 4.33 x 10^86.  The natural logarithm of
that is about 199.  So a rough estimate of the keyspace size would be
(4.33 x 10^86) / 199 =~ 2 x 10^84.

And that's assuming you already had a list of the primes.  Generating
such a list would be an undertaking of monumental effort.  Storing it
is nearly inconceivable.

If you just hand out ranges of the set of integers up to sqrt(N) then
your keyspace is 4.33 x 10^86, which is 200 times as big.  Storing that
would be 200 times as inconceivable. ;-)

Suppose you hand this keyspace out in blocks of a million.  Then you would
have to keep track of each of the roughly 4.33 x 10^80 chunks.  This is
a million times better in terms of storage, but it's still ridiculous.

> By emailing RSA using the supplied contact in their factoring challenge faq
> http://www.rsasecurity.com/rsalabs/challenges/factoring/index.html
> we can get the code used to create the random numbers,

This is already explained in their FAQ
<http://www.rsasecurity.com/rsalabs/challenges/factoring/faq.html>

    "1. First, 30,000 random bytes were generated using a ComScire
     QNG hardware random number generator, attached to the laptop's
     parallel port.

     2. The random bytes were used as the seed values for the
     B_GenerateKeyPair function, in version 4.0 of the RSA BSAFE
     library. The private portion of the generated keypair was
     discarded. The public portion was exported, in DER format to a
     disk file.

     3. The moduli were extracted from the DER files and converted to
     decimal for posting on the Web page.

     4. The laptop's hard drive was destroyed."

> Then just hand out ranges of numbers inside this boundary to clients and let
> them
> try dividing the contest number by each number in the range. **
> If the result was an integer then you are done and have found both factors.

There is an attractive elegance to this approach, but you simply can't
track it.  There's not enough data storage in the whole world.

If you insist on using such a naive method, you might be better off
simply letting the "client" computers pick a random starting point in
the keyspace, and then start processing from there.  This would at least
have a nonzero probability of success....

Suppose that each computer can check 1000 primes per second in the
keyspace of 2x10^84 primes.  Suppose you have a million computers.
That's 10^9 primes checked per second, so you would exhaust the keyspace
in 2x10^75 seconds.  If you get lucky and find the key when you're
halfway through, then the contest will be completed in 10^75 seconds,
or 10^70 days, or 3x10^67 years.

And that's under ideal circumstances (no duplicated work).

> So we don't have to use the best scheme, we could just try throwing enough
> computers
> at the problem to do it the hard way.

Or we could work on RC5-64 which will be finished within about 2 years. ;-)

-- 
Greg Wooledge                  |   "Truth belongs to everybody."
greg at wooledge.org              |    - The Red Hot Chili Peppers
http://wooledge.org/~greg/     |
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 240 bytes
Desc: not available
Url : http://lists.distributed.net/pipermail/rc5/attachments/20010727/6037a438/attachment-0001.bin


More information about the rc5 mailing list