Re: Prime magnitude and keys...a ?

[Jim choate <ravage@bga.com>]

> 
> This is an approach that I haven't heard of before.  If one could
> determine the numerical ordering of two different keys used to
> RSA-encrypt the same piece of plaintext by examining the
> ciphertext, one could easily break RSA by a binary search of the
> keyspace.
>
I also have found no info on it, surprises me...

> Given two moduli N1 and N2, and some plaintext P, and PGP's
> favorite encryption exponent, 17, you need to determine if
> N1 < N2 by examining P^17 MOD N1 and P^17 MOD N2.  Although this
> is only a one-bit function, it clearly depends upon P in a very
> complicated way.  Since P is unknown and deliberately made random
> in practical RSA implementations, I am not sure such an attack
> shows much promise.  I would guess that this would be at least as
> complicated as solving an RSA or discrete log problem directly.
>
I would agree with you if we talk about a single P, however I suspect
that if one looks at a sequence of P's in a message that there might
be some analysis that could be done relating to the residuals. If you
take into account the regularity (periodicity?) of english text then
it seems to me that you could make some form of 1-1 mapping of the 
P's in a cypher-text to the plain-text. 

If you have any other thoughts on it would appreciate them...


> -- 
>      Mike Duvos         $    PGP 2.6 Public Key available     $
>      mpd@netcom.com     $    via Finger.                      $
> 
>