Weak RSA keys?

>He probably believes, along with most people, that for each
>encryption exponent there is ONLY ONE decription exponent.
>In fact there are AT LEAST TWO.  Yes, you have a "spare key".

Yes, it does look like there are two possible decryption exponents,
but one is derived from the other and information only known to the
person who can factor n, so it isn't clear to me how this is a big
weakness.  If you pick good factors of n and the primes are large, the
problem is just as infeasible as it was before, and you get ONLY two
decryption exponents.

In fact, if you look on page 92 of "Cryptography; An Introduction to
Data Security" by Seberry and Pieprzyk, you will see that they make it
more explicit than some other texts: they give this as the formula
relating then encryption and decryption exponents:

			 e d = 1 mod gamma(n)

		   where gamma(n) = lcm (p-1, q-1)

So they use the least common multiple of p-1 and q-1.

With good choices of p and q, there will be 2 decryption exponents: d
and (d + phi(n)/gamma(n)).  If you have more than 2 decryption
exponents, you have made poor choices of primes.

Again, to calculate the "spare" key you nee need to know how n factors,
which makes the whole thing moot.

Example with better choices for p and q:

p = 107; q = 167; n = 17869
phi(n) = 106 * 166 = 17596
e = 43

d = 43^-1 mod 17596 = 7775

71^43 mod 17869 = 10073 (the encrypted message)
to decrypt: 10073^7775 mod 17869 = 71.

If you use 

e d = 1 mod gamma(n) 

you get

d = 43^-1 mod 8798 = 7775, which is the same d you got above.  Thus,
the spare key is 7775 + 8798 = 16573, which does work as a decryption
exponent.  


-- 
Karl L. Barrus: klbarrus@owlnet.rice.edu         
keyID: 5AD633 hash: D1 59 9D 48 72 E9 19 D5  3D F3 93 7E 81 B5 CC 32 

"One man's mnemonic is another man's cryptography" 
  - my compilers prof discussing file naming in public directories

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