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

Question

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

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

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

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

维基百科 - 通过平方来表示

本章(见第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)^2那么大.