[RC5] RSA decryption

Andreas D. Landmark andreas.landmark at noxtension.com
Sat Mar 3 22:42:10 EST 2001

At 03.03.2001 22:19, you wrote:

>I disagree with you, Andreas.  Distributed.net is testing every single key,
>so it must find the correct key *eventually* (provided there is a correct
>key......)  If people put more effort behind thinking of which key probably
>is the right one, they (maybe) could eliminate a lot of keys to test.
>Now I get to make a really *really* bad analogy:     :-D
>There are millions of monkeys with typewriters.  Eventually, they will
>produce Moby Dick, but it will probably take a very long time for them to do
>that. (Monkeys = dnet participants)  Herman Melville also tries to write
>Moby Dick.  (Herman = Competition with lots of thought)  Who has a higher
>probability of getting the correct version first?  :-)
>I know, this shouldn't really matter because the correct key should have
>been selected *perfectly* at random, but what is perfect?

I suggest you read my answer again,

(the relevant section pasted to make it easier for you ;-)

> > Well the distributed.net effort is _very_ likely to succeed because of
> > the exhaustive testing that is going on as I'm writing this. This means
> > in simple terms that the clients affiliated with distributed.net and the
> > rc5 project is trying out every possible combination to try to decrypt
> > the rc5 encrypted data we are trying to decrypt.

Your analogy misses a big point about dnet, it doesn't test keys at random,
it starts with the first possible key and goes on to test until the last 
key. Your monkeys are just hammering away at the typewriters,
(you should give them a tty and emacs, or atleast vi to make it a fair
game ;-) and it's very likely that a lot of the monkeys would try the same

The whole point of the keyserver/proxy structure of dnet is to avoid such
a thing, and to make sure that work done is recorded and not sent out
to the clients again.

In your analogy Herman Melville clearly has the big advantage,
1) he can write the language
2) he can use a typewriter ;-)
3) and he actually wrote Moby Dick ;-)

with something pseudo-random like rc5, none of the participants (who are
eligible for the award) have more information than anybody else, nobody
actually knows the text we're trying to decrypt. Everybody can assume
what ever they think it is, but they don't know _exactly_ what it is. An 
trying to decrypt it by guessing the text and working backwards, would
perhaps have more luck than the joint effort of dnet-participants, but I find
it highly unlikely that somebody would successfully be able to guess the
correct text without some _bovine_ intervention...

Andreas D. Landmark / noXtension
PGP ID:0xB2BEAE80 / 4096bits
Fingerprint:654B 3BCD 1130 9B3A 08BB  AB1A BF72 841D B2BE AE80

To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest

More information about the rc5 mailing list