如何实现对于巨大的数字，计算 c=m^e mod n？（注：涉及 IT 技术）

Question

如何实现对于巨大的数字，计算 c=m^e mod n？（注：涉及 IT 技术）

mathencryptioncryptographybigintegerbignum

7

我正在尝试从头开始实现RSA加密（只是为了智力锻炼），但我卡在这个点上：

对于加密，c = m的e次方 mod n

现在，e通常为65537。m和n是1024位整数（例如128字节数组）。这显然对于标准方法来说太大了。你会如何实现它？

我一直在阅读这里的指数运算，但它对我来说并不清晰： Wikipedia-Exponentiation by squaring This Chapter（见第14.85节）

谢谢。

编辑：我还发现了这个 - 这更符合我应该关注的内容吗？ Wikipedia- Modular Exponentiation

- Chris

嗯...我想我问的是，当实现它时，我只是想知道从哪里开始。 - Chris

5

是的，模指数运算是你应该关注的。主要的重点在于在每一步中进行重复的模减操作，而不是在最后进行单个的模减。 - lhf

记住，过早的优化是万恶之源。实现一个简单的算法，如果它需要超过一分钟的时间，找到最慢的部分并进行优化。使用直接的平方指数法，就像我的答案中所示，将把您的大整数操作数量从约130,000个减少到约35个，因此可能没有必要寻找更快的方法。 - Artelius

4个回答

3

为了实现高效的算法，需要在每个步骤后将幂运算和模运算结合起来。对于奇数的指数e，有以下公式：

m^e mod n = m ⋅ m^e-1 mod n

对于偶数的指数e，有以下公式：

m^e mod n = (m^e/2 mod n)² mod n

以 m¹ = m 作为基本情况定义了一种递归方式来进行高效的模指数运算。

但即使使用这样的算法，由于m和n非常大，仍需要使用能够处理如此大整数的类型/库。

- sth

3

结果 = 1
当 e > 0 时：
  如果 (e & 1) != 0：
    结果 = 结果 * m
    结果 = 结果 mod n
  m = m * m
  m = m mod n
  e = e >> 1
返回结果
这段代码检查指数中的位，从最低有效位开始。每次移动一位相当于将 m 的幂加倍 - 因此我们移位 e 并平方 m。只有在该位置的指数具有 1 位时，结果才会得到 m 的幂乘积。所有乘法都需要对 n 取模。
例如，考虑 m^13。11 = 1101 二进制。因此，这与 m^8 * m^4 * m 相同。请注意幂次 8、4（不是 2）、1，它们与位 1101 相同。然后回想一下，m^8 = (m^4)^2 并且 m^4 = (m^2)^2。

- phkahler

我们不需要从最高有效位开始吗？请参见此处的VII.A：http://people.csail.mit.edu/rivest/Rsapaper.pdf - Chris

我的错误，你正在使用从右到左的二进制方法，这是一种不同于我所想的算法：http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method - Chris

我本来打算从左到右扫描它，但当时似乎很麻烦。这种方法不需要找到最高有效位，但每次循环都必须将整个指数进行移位。这是一个小的权衡。 - phkahler

1

如果对于您的大数库来说，计算g(x) = x mod 2^k比计算f(x) = x mod N（其中N不可被2整除）更快，那么请考虑使用蒙哥马利乘法。当与模幂运算一起使用时，它避免了在每个步骤中计算模N，您只需要在开始和结束时进行“蒙哥马利化”/“非蒙哥马利化”即可。

- Jason S

N 不能是偶数，例如 26 不能用于蒙哥马利乘法，但 26 不是 2 的幂。 - President James K. Polk

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Artelius · Accepted Answer

平方求幂算法：

让我们举一个例子。你想要求解17的23次方。注意23在二进制中为10111。让我们从左到右逐步构建它。

           // a      exponent in binary

a = 17     //17^1          1

a = a * a  //17^2         10

a = a * a  //17^4        100
a = a * 17 //17^5        101

a = a * a  //17^10      1010
a = a * 17 //17^11      1011

a = a * a  //17^22     10110
a = a * 17 //17^23     10111

当你进行平方操作时，指数会加倍（左移1位）。当你乘以m时，指数会加1。

如果你想对模数n取余，可以在每次乘法后执行（而不是最后执行，这样数字会变得非常大）。

65537的二进制表示为10000000000000001，这使得所有操作都变得非常简单。

a = m
repeat 16 times:
    a = a * a
    a = a mod n
a = a * m
a = a mod n

当然，a、n和m都是“大整数”。a至少需要2048位，因为它可能会变得很大，最大可以达到(n-1)²。