影响RSA加密/解密时间的因素
“RSA 加密或解密时间大致与指数中的位数成正比”。
我假设它更依赖于位的位置。例如，M^e。 e1 = 10001 = 17 e2 = 00111 = 7
如果M = 5，我认为5^17的计算比5^7花费更多的时间。
我说得对吗？
"the RSA encryption or decryption time is roughly proportional to the number of bits in the exponent".
I am assuming that it counts more on the position of the bits. For example, M^e.
e1 = 10001 = 17
e2 = 00111 = 7
If M = 5, I think the calculation of 5^17 takes more time than 5^7.
am I right?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
最简单的模幂算法是“平方和乘法”。
假设一个t位指数：指数值在2t-1（含）和2t<之间/sup>（独占）；换句话说，最高的非零位位于索引 t-1（如果从 0 开始计数），所有较高（也称为“前导”）位均为 0。例如，17 是 5-位指数（写为“10001”），而 7 是 3 位指数（“111”）。
然后 m 乘以 e 的幂就像这样（我们想要 me mod n >)：
因此，求幂将需要 t-1 平方，以及 s-1 额外乘以 m，其中 s 是e 二进制表示中的非零位数。模平方的成本与模乘法的成本大致相同。
通过使用基于窗口的优化可以减少额外乘法的次数。这个想法是按组处理指数位。例如，如果指数中有两个连续的非零位，则上面的算法将对这些位执行以下操作：平方 r，将 r 乘以 m，平方r，将r乘以m。该序列可以替换为：平方r，平方r，将r乘以m3< /em>.因此，如果您预先计算 m3 （这需要两次乘法），那么每当指数中有两个连续的非零位时，您就可以保存一次乘法。这确保了额外的乘法不会超过 t/2 次。这个过程可以扩展到多于两位的组；如果您使用大小为 w 的窗口，那么您必须进行大约 2w-1 次乘法的预计算，但之后只有大多数t/w额外的乘法。
底线是，对于大指数（几百位或更多），超过 80% 的计算成本来自 t-1 平方，即“大致与指数中的位”。额外的乘法（取决于实际的指数位值）加起来仅占总成本的 20% 以下。
现在，以上所有内容都假设有一个“大指数”。实现模幂的有效方法涉及使用蒙哥马利约化：这意味着转换步骤，在以下位置执行计算的开始和结束。当指数很大时，这些转换的相对成本可以忽略不计。然而，对于短指数（例如 7 和 17），情况不再如此，转换步骤的成本实际上可能占主导地位。
另外，对于 RSA 私钥操作（使用私有指数的操作），通常使用 中国余数定理：CRT使用模数的特殊结构（即n = pq，其中p和q 是大素数），用两倍小值的两次幂替换模幂）。基于 CRT 的实现意味着一些额外的步骤，但可以实现 4 倍的加速。我还必须补充一点，设计 RSA 密钥时使私有指数大大短于模数（以加快运算速度）是一个安全风险：如果指数小于模数长度的 29%，则密钥可以被破解。因此，上面所有关于求幂速度和指数长度的文本实际上仅适用于公共指数，我们可以选择较小的公共指数，此时关于基于窗口的优化的讨论不再适用。
要获得更完整的处理，请阅读应用密码学手册的第 14 章（可以可以免费下载）。
The simplest modular exponentiation algorithm is the "square and multiply".
Assume a t-bit exponent: the exponent value is between 2t-1 (inclusive) and 2t (exclusive); in other words, the highest non-zero bit it at index t-1 (if counting from 0), all higher (aka "leading") bits being 0. For instance, 17 is a 5-bit exponent (it is written as '10001') while 7 is a 3-bit exponent ('111').
Then exponentiation of m by e works like this (we want me mod n):
So the exponentiation will require t-1 squarings, and s-1 extra multiplications by m where s is the number of non-zero bits in the binary representation of e. A modular squaring has about the same cost than a modular multiplication.
The number of extra multiplications can be reduced by using window-based optimizations. The idea is to handle exponent bits by groups. For instance, if you have two consecutive non-zero bits in the exponent, then the algorithm above will do the following for those bits: square r, multiply r by m, square r, multiply r by m. This sequence can be replaced by: square r, square r, multiply r by m3. Hence, if you precompute m3 (which requires two multiplications), then you can save one multiplication every time there are two consecutive non-zero bits in the exponent. This ensures that there will be no more than t/2 extra multiplications. This process can be extended to groups of more than two bits; if you use a window of size w, then you must do a precomputation of about 2w-1 multiplications, but afterwards there are only at most t/w extra multiplications.
Bottom-line is that for big exponents (of a few hundred bits or more), more than 80% of the computational cost comes from the t-1 squarings, i.e. "is roughly proportional to the number of bits in the exponent". The extra multiplications (which depend on the actual exponent bit values) will add up only to less than 20% of the total cost.
Now, all of the above assumes a "big exponent". The efficient way to implement modular exponentiation involves using Montgomery reduction: this implies conversion steps, which are performed at the beginning and the end of the computation. When the exponent is big, the relative cost of those conversions is negligible. However, with short exponents (such as 7 and 17), this is no longer the case, and the cost of the conversion steps may actually dominate.
Also, for RSA private key operations (those which use the private exponent), it is customary to use the Chinese Remainder Theorem: the CRT uses the special structure of the modulus (i.e. n = pq where p and q are big primes) to replace the modular exponentiation by two exponentiations on twice smaller values). The CRT-based implementation implies some extra steps, but allows for a 4x speedup. I must also add that designing the RSA key so that the private exponent is substantially shorter than the modulus (to speed up operations) is a security risk: if the exponent is smaller than 29% of the modulus length, then the key can be cracked. Therefore, all of the text above, about exponentiation speed and the length of the exponent, really applies to the public exponent only, which we can choose to be small, at which point the discussion on the window-based optimizations do not apply anymore.
For a more complete treatment, read chapter 14 of the Handbook of Applied Cryptography (which can be freely downloaded).