On cypherpunks warlord@MIT.EDU (Derek Atkins) posted an example of a (small) RSA key. He is perpetuating a dangerous myth about RSA. 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". Maybe many. In fact I can generate RSA keys with "good" primes that are hard to factor, yet the keys are WEAK - easy to break. This is part of Derek Atkins' example:
Here is a better example:
p = 5 q = 11 N = pq = 55 m = (p-1)(q-1) = 4*10 = 40
Now, we need to choose our public and private decryptors, E and d, such that Ed = 1 mod (m): E = 3 d = 27
In his example the decrypt exponent is 27. The "spare" is 7. The "spare" runs faster, too. Go ahead, try it. The myth is that "ED = 1 mod (m)". The truth is as follows: G = gcd( p-1 , q-1) in this example G=2 F = m/G in this example F=20 ED = 1 mod (F) I showed this to Phillip Zimmermann and PGP keys are generated this way. At first PRZ checked to be sure G=2. Then he found that with random large primes G was almost always small, say < 17 or so. So now he doesn't check. HERE IS WHY IT IS IMPORTANT TO KNOW THIS: Let's say my name is Denning. Lets say there is a new government chip they want certified. They describe the (RSA) algorithm to me, in secret. I look at it from every angle I *can think of*. Yes the skipj--- RSA algorithm is good. I say so in public. No, I can't reveal how it works, but trust me, my name is Denning and I know what I speak of. Now the government starts producing KEYS for this new algorithm. They key escrow them to two agencies. They also make sure that G IS LARGE. The algorithm can be brute force attacked (search for spares). They don't give a da*m about warrants and escrow, the TLA can brute force any keys they need. Think about it, Dorothy. We aint in Kansas any more. Here is an example (using small numbers) of a weak key. P=607 q=1213 n=736291 phi=(p-1)*(q-1)=734472 G=606 F = phi/g = 1212 E=5 D=485 (D*E)=1 mod F M=40 (message) M^E mod n = 55551 cyphertext=55551 55551^D mod n = 40 A spare key can be found every 1212 numbers, just add 1212 to D: 1697, 2909, 4121, 5333.....etc They are all spares. Charlie Merritt's rule of cryptography: "Don't trust even RSA if you don't generate the keys; Know your source (code)."