cryptoanarchy.wiki

Arise, you have nothing to lose but your barbed wire fences!

1994-06-17 - Re: Prime magnitude and keys…a ?

Header Data

From: Jim choate <ravage@bga.com>
To: mpd@netcom.com (Mike Duvos)
Message Hash: 5d77f604dc5234fe4ab4be9264a7527ce1d6c127b4bb6a689000c4faaba84f09
Message ID: <199406171640.LAA04964@zoom.bga.com>
Reply To: <199406171547.IAA13206@netcom.com>
UTC Datetime: 1994-06-17 16:41:42 UTC
Raw Date: Fri, 17 Jun 94 09:41:42 PDT

Raw message

From: Jim choate <ravage@bga.com>
Date: Fri, 17 Jun 94 09:41:42 PDT
To: mpd@netcom.com (Mike Duvos)
Subject: Re: Prime magnitude and keys...a ?
In-Reply-To: <199406171547.IAA13206@netcom.com>
Message-ID: <199406171640.LAA04964@zoom.bga.com>
MIME-Version: 1.0
Content-Type: text


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

Thread