7

我试图弄清楚如何从头开始实施 RSA 加密（仅用于智力练习），我坚持这一点：

对于加密，c = m e mod n

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

我在这里读了一些关于幂运算的文章，但对我来说并没有点击：

维基百科-平方求幂

本章（见第 14.85 节）

谢谢。

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

4

4 回答 4

8

通过平方取幂：

让我们举个例子。你想找到 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。

如果你想减少 modulo 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) 2一样大。

于 2010-07-07T00:52:34.370 回答
3

对于一个有效的算法，您需要通过mod在每一步之后重复应用平方来组合取幂。

对于奇数e，这成立：

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

对于偶数e：

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

以m 1 = m作为基本情况，这定义了一种递归方式来进行有效的模幂运算。

但即使使用这样的算法，因为m和n会非常大，您仍然需要使用可以处理这种大小的整数的类型/库。

于 2010-07-07T00:47:49.837 回答
3 
结果 = 1
当 e>0 时：
  如果 (e & 1) != 0:
    结果 = 结果 * 米
    结果 = 结果 mod n
  米=米*米
  m = m mod n
  e = e>>1
返回结果

这会检查指数中从最低有效位开始的位。每次我们向上移动一点，它对应于 m 的幂的两倍 - 因此我们移动 e 和平方 m。如果指数在该位置有 1 位，则结果只会乘以 m 的幂。所有乘法都需要减少 mod n。

例如，考虑 m^13。11 = 1101 二进制。所以这与 m^8 * m^4 * m 相同。注意 8,4,(not 2),1 的幂，它与位 1101 相同。然后回想一下 m^8 = (m^4)^2 和 m^4 = (m^2)^2。

于 2010-07-07T01:43:01.343 回答
1

如果g(x) = x mod 2^k为您的 bignum 库计算比f(x) = x mod NN 不能被 2 整除的速度更快，则考虑使用Montgomery multiplication。当与模幂一起使用时，它避免了必须在每一步计算模N，您只需要在开始和结束时进行“Montgomeryization”/“un-Montgomeryization”。

于 2010-07-07T22:53:32.547 回答