我试图弄清楚如何从头开始实施 RSA 加密(仅用于智力练习),我坚持这一点:
对于加密,c = m e mod n
现在,e 通常是 65537。m 和 n 是 1024 位整数(例如 128 字节数组)。这对于标准方法来说显然太大了。你将如何实现这一点?
我在这里读了一些关于幂运算的文章,但对我来说并没有点击:
本章(见第 14.85 节)
谢谢。
编辑:也发现了这个 - 这是我应该看的更多吗?维基百科-模幂
通过平方取幂:
让我们举个例子。你想找到 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一样大。
对于一个有效的算法,您需要通过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会非常大,您仍然需要使用可以处理这种大小的整数的类型/库。
结果 = 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。
如果g(x) = x mod 2^k
为您的 bignum 库计算比f(x) = x mod N
N 不能被 2 整除的速度更快,则考虑使用Montgomery multiplication。当与模幂一起使用时,它避免了必须在每一步计算模N,您只需要在开始和结束时进行“Montgomeryization”/“un-Montgomeryization”。