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作为基本情况,这定义了一种递归方式来进行有效的模幂运算。

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

于 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 回答