From: hughes@ah.com (Eric Hughes)
Date: Thu, 7 Oct 93 14:35:56 PDT
To: cypherpunks@toad.com
Subject: Weak RSA keys?
In-Reply-To: <9310071956.AA02596@flammulated.owlnet.rice.edu>
Message-ID: <9310072135.AA01702@ah.com>
MIME-Version: 1.0
Content-Type: text/plain


Re: finding weak keys

The point with weak RSA keys is not that one can find other decryption
exponents deterministically given public information, but rather
probabilistically.  If gcd( p-1, q-1 ) is large with respect to pq,
then one can simply do a random search for these other exponents.

Greatest common divisors are quick to calculate, so there's no
practical problem with making sure that one does not generate weak
keys.

The rest of this message is a mathematical explanation of _why_ there
are at least two decryption exponents.

Warning: technical algebra follows.

Short answer: (Z/pqZ)^* is not a cyclic group, and therefore does not
contain elements of maximum order, i.e. of order (p-1)(q-1).
(Notation: the group above is the multiplicative group of numbers
modulo pq.)  The largest order of any element is lcm(p-1,q-1).

Longer answer: (Z/pqZ)^* is isomorphic to (Z/pZ)^* x (Z/qZ)^*.  The
isomorphism map is I: x mod pq |--> ( x mod p, x mod q ).  Let f =
gcd(p-1,q-1) and F = lcm(p-1,q-1).  Define f_p = (q-1)/f and f_q =
(p-1)/f; both are integers.

Note that since Ff = (p-1)(q-1), F = (p-1)f_p = (q-1)f_q.

I( x^F mod pq )
	= ( x^F mod p, x^F mod q )
	= ( x^((p-1)f_p) mod p, x^((q-1)f_q) mod q )
	= ( (x^(f_p))^(p-1) mod p, (x^(f_q))^(q-1) mod q )
	= ( 1 mod p, 1 mod q )

The last step follows by Fermat's Little Theorem.  Since the
isomorphic image of x^F is (1,1), we conclude that x^F == 1 (mod pq),
for all x.  (To see this, use the Chinese Remainder Theorem.)

Since p and q are both odd, p-1 and q-1 are both even.  Thus their gcd
must be at least two.

Out of curiosity, does anybody here know how to calculate any
expectations for gcd(p-1,q-1) for, say, 2^n < p < q < 2^(n+1) ?  I
don't know enough number theory myself.

Eric