当前位置：文江博客话题详情

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

发布于 2024-08-22 18:24:53 字数 145 浏览 2 评论 0原文

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

感谢

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

堇年纸鸢 2024-08-29 18:24:54

我们分别将 n、d 和 e 称为 RSA 模数、私有指数和公共指数。 RSA解密速度与(log d)(log n)²成正比（即模数长度的二次方，私有指数长度的线性）。同样，RSA加密速度与(log e)(log n)²成正比。私钥持有者还知道 n 的因式分解，它可用于将私钥操作速度加快约 4 倍（使用中国剩余定理）。有关所涉及算法的详细信息，请参阅应用密码学手册，特别是第14章（ “高效实施”）。

为了获得适当的安全性，私有指数 (d) 必须很大；已经表明，如果它小于模数长度 (n) 的 29%，则可以重建私钥。我们不知道避免此类弱点的最小长度是多少，因此实际上 d 的长度将与 n 的长度大致相同。这意味着解密大约是 n 长度的立方。

同样的规定不适用于公共指数 (e)，只要符合 RSA 规则，公共指数可以尽可能小（e 必须是对于 n 的所有质因数 r 而言，与 r-1 互质。所以习惯上选择一个非常小的e。习惯上，广泛部署的实现无法处理大的公共指数。例如，如果 e 不适合 32，则 Windows CryptoAPI 中的 RSA 实现（例如，当连接到具有 RSA 服务器证书的 HTTPS 站点时，Internet Explorer 使用的实现）无法处理 RSA 公钥。位。 e=3 是最好的，但 e=65537 是传统的（这是一种历史性的错误，因为如果 RSA 是，非常小的指数可能会导致明显的弱点）在没有适当和标准填充的情况下使用，无论如何都不应该这样做）。 65537 是一个 17 位长整数，而 n 和 d 的典型长度将为 1024 位或更多。这使得公钥操作（消息加密、签名验证）比私钥操作（消息解密、签名生成）快得多。

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

回复收藏 0 原文

耀眼的星火 2024-08-29 18:24:54

理论上来说，不一定是这样。加密和解密算法本质上是相同的。给定：

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

则：

加密 c_i = m_i^e (mod n)
解密 m_i = c_i^d (mod n)

求幂的正常算法是迭代的，因此所花费的时间取决于指数的大小。在大多数情况下，该对的解密密钥（通常相当大）大于加密密钥。

不过，扭转这一局面是可能的。仅举一个玩具示例，请考虑：

p=17
q=23
n=391

以下是该特定素数对的一些有效加密/解密密钥对的列表：

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 个密钥对中，只有一个的解密密钥小于加密密钥对钥匙。在其他情况下，解密密钥的范围从不到两倍到几乎 17 倍。当然，当模数像这样很小时，可以快速轻松地生成大量密钥对，因此找到一个小的解密密钥将相当容易——但是，对于真正的 RSA 密钥，这并不是那么简单，并且我们通常只接受我们找到的第一对。正如您从上面的列表中看到的，在这种情况下，您很可能最终得到的解密密钥比加密密钥大得多，因此解密最终会比加密慢。当处理大约 100 位数字时，我们必须非常耐心地找到一对解密速度（甚至接近）与加密速度一样快的数字。

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:

Encryption c_i = m_i^e (mod n)
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.

回复收藏 0 原文