[RC5] RSA decryption

Jeff Lacy jeffdl at mn.mediaone.net
Sat Mar 3 17:56:56 EST 2001


----- Original Message -----
From: "Andreas D. Landmark" <andreas.landmark at noxtension.com>
To: <rc5 at lists.distributed.net>
Sent: Saturday, March 03, 2001 4:42 PM
Subject: Re: [RC5] RSA decryption


> 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?
> >
> >Jeff
>
> 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
> possible
> 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
> combination.
>
> 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 ;-)
Okay, my mistake.  These are very intellegent monkeys :-)

>
> 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
> attempt
> 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...

We can (maybe???) safely assume that the text is in English, is relatively
short, and has farily good grammar which helps limit things.

I'm also working under the assumption that nothing we can do/make is
perfect.  Maybe if we analyzed the program that generated the 'random' prime
number, we could make an educated guess as to what the key is (or is likely
to be).  By my assumption, there must be a way to at least reduce the number
of possible primes.

I hope this makes sense, but it might not be perfectly easy to
implement.....


[This is to Rodney:]  I didn't explain my analagy very well, and I'm sorry.
The *order* of the keyspaces is what is important.  Herman starts will the
keyspaces that he thinks contain the keys, while dnet starts as some
(random?) point.


>
>
>
> --
> 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
>



Jeff

--
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