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
participants (2)
-
hughes＠ah.com -
Karl Lui Barrus