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