performance - 影响 RSA 加密/解密时间的因素

Question

“RSA加密或解密时间大致与指数中的位数成正比”。

我假设它更多地依赖于位的位置。例如，M^e。
e1 = 10001 = 17
e2 = 00111 = 7

如果 M = 5，我认为 5^17 的计算比 5^7 需要更多的时间。

我对吗？

Answer 1

最简单的模幂算法是“平方和乘法”。

假设一个t位指数:指数值在2t-1(含)和2t(不含)之间；换句话说，它在索引 t-1 处的最高非零位(如果从 0 开始计数)，所有更高(也称为“前导”)位为 0。例如，17 是一个 5 位指数(它写为'10001')，而 7 是 3 位指数('111')。

然后用 e 对 m 取幂就像这样(我们想要我 mod n):

以 r = m

开头

对于从 t-2 到 0 的 k:

平方 r:设置 r = r2 mod n

如果 e 中索引 k 处的位为 1，则设置 r = r*m mod n

求幂结果为 r

因此，求幂将需要 t-1 次平方和 s-1 次额外乘以 m，其中 s 是 e 的二进制表示中的非零位数。模平方的成本与模乘的成本大致相同。

通过使用基于窗口的优化，可以减少额外的乘法次数。这个想法是按组处理指数位。例如，如果指数中有两个连续的非零位，那么上面的算法将对这些位执行以下操作:平方 r，将 r 乘以 m，平方 r，将 r 乘以 m。此序列可以替换为:平方 r，平方 r，将 r 乘以 m3。因此，如果您预先计算 m3(这需要两次乘法)，那么每次指数中有两个连续的非零位时，您可以保存一次乘法。这确保不会有超过 t/2 的额外乘法。这个过程可以扩展到多于两位的组；如果您使用大小为 w 的窗口，那么您必须进行大约 2w-1 次乘法的预计算，但之后最多只有 t/w 次额外乘法。

底线是，对于大指数(几百位或更多)，超过 80% 的计算成本来自 t-1 平方，即“大致与指数中的位数成正比”。额外的乘法(取决于实际的指数位值)加起来只占总成本的不到 20%。

现在，以上所有内容都假设一个“大指数”。实现模幂运算的有效方法是使用 Montgomery reduction :这意味着在计算开始和结束时执行的转换步骤。当指数很大时，这些转换的相对成本可以忽略不计。但是，对于较短的指数(例如 7 和 17)，情况不再如此，转换步骤的成本实际上可能占主导地位。

此外，对于 RSA 私钥操作(使用私有(private)指数的操作)，习惯上使用 Chinese Remainder Theorem :CRT 使用模数的特殊结构(即 n = pq，其中 p 和 q 是大素数)将模幂运算替换为对较小值的两倍取幂)。基于 CRT 的实现意味着一些额外的步骤，但允许 4 倍的加速。我还必须补充一点，设计 RSA key 以使私有(private)指数大大短于模数(以加快运算速度)是一个安全风险:如果指数小于模数长度的 29%，则 key 可能会被破解.因此，上面所有关于取幂速度和指数长度的文字，实际上只适用于公共(public)指数，我们可以选择较小，此时关于基于窗口的优化的讨论不再适用。

如需更完整的处理，请阅读 the Handbook of Applied Cryptography 的第 14 章(可以免费下载)。