Re: Public Key Break Paper

[Hal Finney <hal@rain.org>]

Peter Gutmann, pgut001@cs.auckland.ac.nz, writes:
> (I had another look at the unbalanced RSA proposal in the Autumn 1995
>  CryptoBytes as I was trying to find the above article, did anyone ever do
>  anything with unbalanced RSA or was it just left as a curiosity?).

The unbalanced RSA idea, by Shamir, was to choose primes p and q with p
considerably less than q, e.g. p = 500 bits, q = 4500 bits.  With numbers
of this size, the difficulty of factoring a 5000 bit n = pq is still just
as hard as if p and q were both about 2500 bits.  Then, you only encrypt
numbers < p, and it turns out that you can do the decryption mod p rather
than mod n, so decrypt is much, much faster than for a conventional 5000
bit modulus.

There have been some attacks on this.  The main limitation is that the
encrypted number is supposed to be < p.  There is a chosen-cyphertext
attack, taking an x a few bits larger than p, encrypting it, and asking
for the resulting decryption.  This produces x mod p, which combined
with x can be used to find p.

Another attack along these lines is to guess x about the size of p, send
a legitimate message based on it, then watch the receiver's behavior to
try to determine whether the message had decrypted correctly.  If x < p
it would decrypt OK, otherwise it would decrypt to garbage.  Repeat this
to narrow down an interval containing p.

I believe these were presented by Quisquater at the Crypto 96 rump session,
although I think he was referring in part to some attacks which had already
been discovered.

Hal