cryptography - 为什么 RSA 解密过程比加密过程需要更长的时间？

Question

我有一些想法，这是由于一些复杂的计算，但我想知道究竟发生了什么，这比相应的加密过程需要更长的时间。任何指向网页或论文的链接都会有很大帮助。

谢谢

感谢您的回答，还有一个疑问，签名和验证呢？签名和验证也会有这个时差吗？前任。签名比验证需要更多时间？

Answer 1

从理论上讲，它不一定是。加密和解密算法本质上是相同的。鉴于:

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

然后:

加密 ci = mie (mod n)

解密 mi = cid (mod n)

升幂的正常算法是迭代的，因此所用的时间取决于指数的大小。在大多数情况下，解密 key (通常相当大)比加密 key 大。

虽然可以扭转这种情况。仅以玩具为例，请考虑:

p=17
q=23
n=391

以下是这对特定素数的一些有效加密/解密 key 对的列表:

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 

在这 20 个 key 对中，只有一个的解密 key 小于加密 key 。在其他情况下，解密 key 的大小从不到两倍到几乎 17 倍不等。当然，当模数像这样很小时，生成大量 key 对是快速而容易的，因此找到一个小的解密 key 会相当容易——但是，如果使用真正的 RSA key ，就不是那么简单了，而且我们通常只接受我们找到的第一对。正如您从上面的列表中看到的那样，在这种情况下，您很可能会得到一个比加密 key 大得多的解密 key ，因此解密最终会比加密慢。在处理大约 100 位数字时，我们必须非常耐心地找到一对解密速度(甚至接近)与加密速度一样快的数字。