Re: common modulus attack on RSA

[Derek Atkins <warlord@xxxxxxx>]

You do realize that the liklihood of using the same 'N' is near zero.
If you and I choose the same N, that means that we can effectively
decrypt each others' messages.

Also, the 'm' being encrypted has random padding, and that random
padding should be unique per key.  In other words, 'm' _should_ be
different for each key anyways.

-derek

john.dlugosz@xxxxxxxxx writes:

> From: John Dlugosz
> 
> In "Applied Cryptography", page 472, Schneier warns against ever encrypting
> the same plaintext with two keys having the same n (but different e).
> 
> Different public keys may indeed have a common n, either by chance, because
> of an implementation that reuses a small set of n, or a deliberate attack.
> 
> The session key is encrypted to multiple public keys.
> 
> Looking at section 5.1 of RFC2440, it appears that only the MPI of the
> RSA-encrypted value of m is used.  I'm supposing that m is much smaller
> than n, so the whole thing takes one "block" through RSA.
> 
> The other values put into m (the algorithm and the  checksum) are the same,
> too, so m will be identical in every public-key encrypted session key
> packet.
> 
> Perhaps the new draft should note that an implementation could warn about
> multiple recipients with the same n.  Remember, this could be done by
> other-than-chance, such as deliberatly introducing them as an attack.
> Better yet, I'd be happier if another number, chosen by the encryptor, were
> prepended to the session key, different for each recipient (e.g. a simple
> counter).
> 
> Is the note that a new PKCS-1 padding be made doing exactly this?  If so,
> does that add a unique value to the =end= (what I normally think of as
> padding), or does it pre-pend anything, too?  If so, is it guaranteed that
> the length of the final m is shorter than n?
> 
> --John
> 
> 

-- 
       Derek Atkins, SB '93 MIT EE, SM '95 MIT Media Laboratory
       Member, MIT Student Information Processing Board  (SIPB)
       URL: http://web.mit.edu/warlord/    PP-ASEL-IA     N1NWH
       warlord@xxxxxxx                        PGP key available