为什么RSA解密过程需要比加密过程更长的时间？ [英] Why RSA Decryption process takes longer time than the Encryption process?

问题描述

我有一些想法，这是由于一些复杂的计算，但我想知道什么发生，需要比对应的加密过程长的时间。

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 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?

推荐答案

理论上，它不一定是。加密和解密算法基本上相同。给定：

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

然后：

1. 加密c _i = m _i ^e / li>
   
2. 解密m _i = c i d （mod n）

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 

，只有一个具有小于加密密钥的解密密钥。在其他情况下，解密密钥的范围从仅仅两倍大到几乎17倍大。当然，当模数很小这样，它是快速和容易生成大量的密钥对，所以找到一个小的解密密钥将是相当容易 - 与真正的RSA密钥，但是，它不是那么琐碎，我们一般只接受我们发现的第一对。从上面的列表中可以看出，在这种情况下，很可能最终得到的解密密钥比加密密钥大得多，因此解密将比加密慢。当使用〜100数字数字时，我们必须非常耐心地找到一个对，解密将加密（甚至接近）加密的速度。

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.

这篇关于为什么RSA解密过程需要比加密过程更长的时间？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！