2

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

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

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

我对吗？

4

1 回答 1

3

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

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

然后用e对m取幂就像这样（我们想要m e mod n）：

  1. 以r = m开头
  2. 对于k范围从t-2到0：
    • 平方r : 设置r = r 2 mod n
    • 如果e中索引k处的位为 1，则设置r = r*m mod n
  3. 求幂结果为r

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

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

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

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

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

如需更完整的处理，请阅读应用密码学手册（可免费下载）的第 14 章。

于 2011-03-21T13:05:39.187 回答