math - 如何为巨大的数字实现 c=m^e mod n？

Question

我试图弄清楚如何从头开始实现 RSA 加密(仅用于智力练习)，但我坚持这一点:

对于加密，c = me mod n

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

我在这里阅读了一些关于取幂的内容，但它并没有为我点击:

Wikipedia-Exponentiation by squaring

This Chapter (见第 14.85 节)

谢谢。

编辑:也发现了这个 - 这是我更应该看的吗？ Wikipedia- Modular Exponentiation

Answer 1

平方取幂:

让我们举个例子。你要找 1723。注意 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)2 一样大。