Why RSA Decryption process takes longer time than the Encryption process?

Question

I have some idea that it is due to some complex calculation, but i want to know about what exactly happens which takes long time than the corresponding encryption process. Any link to webpage or paper would be of great help.

Thanks

Thanks for the answers, One more Doubt, What about the Signing and verification? Will this time difference be there for Signing and verification also? Ex. Signing requires more time than Verification?

Answer 1

Let's call n, d and e the RSA modulus, private exponent and public exponent, respectively. The RSA decryption speed is proportional to (log d)(log n)² (i.e. quadratic in the length of the modulus, and linear in the length of the private exponent). Similarly, the RSA encryption speed is proportional to (log e)(log n)². The private key holder also knows the factorization of n, which can be used to speed up private key operation by a factor of about 4 (with the Chinese Remainder Theorem). For details on the involved algorithms, see the Handbook of Applied Cryptography, especially chapter 14 ("Efficient Implementation").

For proper security, the private exponent (d) must be big; it has been shown that if it is smaller than 29% of the length of the modulus (n) then the private key can be reconstructed. We do not know what is the minimum length to avoid such weaknesses, so in practice d will have about the same length than n. This means that decryption will be about cubic in the length of n.

The same provisions do not apply to the public exponent (e), which can be as small as wished for, as long as it complies with the RSA rules (e must be relatively prime to r-1 for all prime factors r of n). So it is customary that a very small e is chosen. It is so customary that there are widely deployed implementations that cannot handle big public exponents. For instance, the RSA implementation in Windows' CryptoAPI (the one used e.g. by Internet Explorer when connected to a HTTPS site with a RSA server certificate) cannot process a RSA public key if e does not fit in 32 bits. e=3 is the best possible, but e=65537 is traditional (it is an historical kind of blunder, because a very small exponent can induce a perceived weakness if RSA is used without its proper and standard padding, something which should never be done anyway). 65537 is a 17-bit long integer, whereas a typical length for n and d will be 1024 bits or more. This makes public-key operations (message encryption, signature verification) much faster than private-key operations (message decryption, signature generation).