I have seen that in gmail, there are 3 certificates in hierarchy. I noticed that all the certificates have the same exponent(65537 with 24bits). Why is the exponent value same for all certificates and how?
migrated from stackoverflow.com Apr 11 '12 at 15:11
This is a common trick to speed up encryption and verification. The exponent is special, in that, it is a small prime number with only two bits set, which makes modular exponentiation in software fast enough. Another commonly used public exponent is 3, but I think that one is falling out of favour these days.
See this question for some more information on the security of these special exponents.
As for the "how" of these exponents, since the modulus is a randomly generated (within some constraints, of course), the private key is still random, and cannot be determined from the public exponent and modulus alone.
The reason why we want as few bits in the exponent as possible is the way modular exponentiation is done. When you are calculating the modular exponentiation using the public key, you only have two numbers: the public exponent, e, and the modulus, n. For private keys, we can can have some more information (actually the prime factors of n) to speed up calculations (you can look up "Chinese remainder Theorem" for RSA if you are interested), but obviously these prime factors cannot be distributed along with the public key. So, we are left with the standard square and multiply algorithm.
The main idea of the algorithm is to square the message for each bit of your exponent, and multiply it to an accumulator when the corresponding bit in the exponent is set. Say, you want to calculate m13. You first write it as a multiplication of a series of m2j, i.e. m23·m22·m20. Set a variable to m, and result to 1. Now, start counting from 0 to 3 (the maximum bit length of modulus). For each value, if 13 has the bit position at counter set, multiply your result with the variable. Before increasing your counter, square your variable. With this scheme, you'll calculate m, m2, m4 and m8 at each iteration of your loop from squaring your variable. When a bit is set in exponent, you pick the value, and multiply it with your result to get m·m2·m8 (which is m13). For a random 1024 bit key, you'll need to call
When you have a small exponent with only two bits set, say 65537, you need to square only 16 times, and multiply only once (m2k can be calculated by initializing a value to m, and repeatedly squaring it k times, and m65537 = m216·m). It is even faster when exponent is 3: you square once, and multiply once.
|show 2 more comments|