如何对大量数字实现 c=m^e mod n？

Question

我试图弄清楚如何从头开始实现 RSA 加密（只是为了智力练习），但我坚持这一点：

对于加密，c = m^e mod n

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

我在这里读了一些关于幂的内容，但它只是不适合我：

Wikipedia-Exponentiation通过平方

本章（参见第 14.85 节）

谢谢。

编辑：还发现了这个 - 这是我应该看的吗？ 维基百科-模幂

Answer 1

通过平方求幂：

让我们举个例子。您想要查找 17²³。请注意，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)²。

Answer 2

为了获得高效的算法，您需要在每一步之后通过重复应用 mod 来组合求幂。

对于奇数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 将非常大，您仍然需要使用可以处理此类大小的整数的类型/库。

Answer 3

result = 1
while e>0:
  if (e & 1) != 0:
    result = result * m
    result = result mod n
  m = m*m
  m = m mod n
  e = e>>1
return result

这会检查指数中从最低有效位开始的位。每次我们向上移动一点，它对应于 m 的幂加倍 - 因此我们移动 e 和 m 的平方。如果指数在该位置有 1 位，则结果仅获得 m 的乘方。所有乘法都需要减少 mod 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。

Answer 4

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