Why RSA Decryption process takes longer time than

问题:

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?

回答1:

In theory, it doesn't have to be. The encryption and decryption algorithms are essentially identical. Given:

d = decryption key
e = encryption key
n = modulus (product of primes)
c = encrypted code group
m = plaintext code group

Then:

1. Encryption c_i = m_i^e (mod n)
2. Decryption m_i = c_i^d (mod n)

The normal algorithm for raising to a power is iterative, so the time taken depends on the size of the exponent. In most cases, the pair works out with the decryption key being (usually considerably) larger than the encryption key.

It is possible to reverse that though. Just for a toy example, consider:

p=17
q=23
n=391

Here's a list of some valid encryption/decryption key pairs for this particular pair of primes:

e = 17, d = 145
e = 19, d = 315
e = 21, d = 285
e = 23, d = 199
e = 25, d = 169
e = 27, d = 339
e = 29, d = 85
e = 31, d = 159
e = 35, d = 171
e = 37, d = 333
e = 39, d = 343
e = 41, d = 249
e = 43, d = 131
e = 45, d = 133
e = 47, d = 15   
e = 49, d = 273
e = 51, d = 283
e = 53, d = 93
e = 57, d = 105
e = 59, d = 179 

Out of those 20 key pairs, only one has a decryption key smaller than the encryption key. In the other cases, the decryption key ranges from just under twice as big to almost 17 times as large. Of course, when the modulus is tiny like this, it's quick and easy to generate a lot of key pairs, so finding a small decryption key would be fairly easy -- with a real RSA key, however, it's not quite so trivial, and we generally just accept the first pair we find. As you can see from the list above, in that case, you're quite likely to end up with a decryption key that's considerably larger than your encryption key, and therefore decryption will end up slower than encryption. When working with ~100 digit numbers, we'd have to be quite patient to find a pair for which decryption was going to be (even close to) as fast as encryption.

回答2:

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).

回答3:

The encryption power is usually chosen to be a prime of the form 2^n+1 (17, 63357) which requires a relatively few multiplication operations. The decryption value will be a much larger number as a consequence, and thus take more work to compute.

回答4:

There are two factors involved in this:

On the one hand, the public exponent can be chosen to be a small number with only two 1-bits (usually 3, 17 or 65537). This means the RSA encryption operation can be done with a few modular squarings and an addition. This cannot be reversed: If you force the private exponent to be a small number, the security of the system is obviously broken.

On the other hand, the holder of the private key can store some precalculated values derived from the original primes. With those he can use the CRT algorithm to replace the single exponentiation modulo a n-bit number with two exponentiaions modulo a n/2-bit number. This is approximately four times faster than the naive way.

So for RSA key pairs with random public exponents, private key operations can actually be faster. But the effect of choosing a small public exponent is much greater than the effect of the faster algorithm, so encryption is faster in practice.

回答5:

RSA Laboratories describes why pretty well

In practical applications, it is common to choose a small public exponent for the public key.

...

With the typical modular exponentiation algorithms used to implement the RSA algorithm, public key operations take O(k^2) steps, private key operations take O(k^3) steps

回答6:

How much longer? Do you have any exact details?

Any way, it make sense that decryption is complicated more than encryption, since the encryption it is not in a symmetric way like 123 => abc and abc > 123.

For more details I suggest starting here.
To read about how the calculatio works, this article seems very good one http://www.di-mgt.com.au/rsa_alg.html

回答7:

In short "multiply = easy, factor = hard".

Take a look at (http://en.wikipedia.org/wiki/RSA#Encryption) which references optimizations in exponentiation (http://en.wikipedia.org/wiki/Exponentiation_by_squaring#Further_applications)

The best resource I found was the following lecture on cryptography from Princeton (http://www.cs.princeton.edu/courses/archive/spr05/cos126/lectures/22.pdf)

回答8:

d and e are multiplicatively inverse numbers modulo phi(n). That means that it doesn't matter witch of the two you'll choose for encryption, and witch one for decryption. You just choose once before encryption. If you want fast decryption than you choose the bigger number for encryption. It's that simple.