a factor that impacts RSA encryption/decryption time

"the RSA encryption or decryption time is roughly proportional to the number of bits in the exponent".

I am assuming that it counts more on the position of the bits. For example, M^e. e开发者_如何学编程1 = 10001 = 17 e2 = 00111 = 7

If M = 5, I think the calculation of 5^17 takes more time than 5^7.

am I right?

The simplest modular exponentiation algorithm is the "square and multiply".

Assume a t-bit exponent: the exponent value is between 2^t-1 (inclusive) and 2^t (exclusive); in other words, the highest non-zero bit it at index t-1 (if counting from 0), all higher (aka "leading") bits being 0. For instance, 17 is a 5-bit exponent (it is written as '10001') while 7 is a 3-bit exponent ('111').

Then exponentiation of m by e works like this (we want m^e mod n):

1. begin with r = m
2. for k ranging from t-2 downto 0:
   • square r: set r = r² mod n
   • if bit at index k in e is 1, then set r = r*m mod n
3. exponentiation result is r

So the exponentiation will require t-1 squarings, and s-1 extra multiplications by m where s is the number of non-zero bits in the binary representation of e. A modular squaring has about the same cost than a modular multiplication.

The number of extra multiplications can be reduced by using window-based optimizations. The idea is to handle exponent bits by groups. For instance, if you have two consecutive non-zero bits in the exponent, then the algorithm above will do the following for those bits: square r, multiply r by m, square r, multiply r by m. This sequence can be replaced by: square r, square r, multiply r by m³. Hence, if you precompute m³ (which requires two multiplications), then you can save one multiplication every time there are two consecutive non-zero bits in the exponent. This ensures that there will be no more than t/2 extra multiplications. This process can be extended to groups of more than two bits; if you use a window of size w, then you must do a precomputation of about 2^w-1 multiplications, but afterwards there are only at most t/w extra multiplications.

Bottom-line is that for big exponents (of a few hundred bits or more), more than 80% of the computational cost comes from the t-1 squarings, i.e. "is roughly proportional to the number of bits in the exponent". The extra multiplications (which depend on the actual exponent bit values) will add up only to less than 20% of the total cost.

Now, all of the above assumes a "big exponent". The efficient way to implement modular exponentiation involves using Montgomery reduction: this implies conversion steps, which are performed at the beginning and the end of the computation. When the exponent is big, the relative cost of those conversions is negligible. However, with short exponents (such as 7 and 17), this is no longer the case, and the cost of the conversion steps may actually dominate.

Also, for RSA private key operations (those which use the private exponent), it is customary to use the Chinese Remainder Theorem: the CRT uses the special structure of the modulus (i.e. n = pq where p and q are big primes) to replace the modular exponentiation by two exponentiations on twice smaller values). The CRT-based implementation implies some extra steps, but allows for a 4x speedup. I must also add that designing the RSA key so that the private exponent is substantially shorter than the modulus (to speed up operations) is a security risk: if the exponent is smaller than 29% of the modulus length, then the key can be cracked. Therefore, all of the text above, about exponentiation speed and the length of the exponent, really applies to the public exponent only, which we can choose to be small, at which point the discussion on the window-based optimizations do not apply anymore.

For a more complete treatment, read chapter 14 of the Handbook of Applied Cryptography (which can be freely downloaded).