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?


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 sqrmod(m, n) 1024 times, and also mulmod(accumulator, m, n) roughly 512 times (the bits are random, so we only know it is less than 1024, and 512 on average).

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.

  • what is two bits set? – Ashwin Apr 11 '12 at 9:43
  • 3
    The number contains only two bits with value 1 (65537 has only bit positions 0 and 16 set to 1). – vhallac Apr 11 '12 at 10:03
  • So, is that a plus point? – Ashwin Apr 11 '12 at 10:18
  • It is. I'll update the answer a little to answer why. – vhallac Apr 11 '12 at 10:21
  • Thank you for the links. I will try to understand it and then ask you my doubts :) – Ashwin Apr 11 '12 at 11:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.