如何实现c = m ^ e mod n大量吗?

I'm trying to figure out how to implement RSA crypto from scratch (just for the intellectual exercise), and i'm stuck on this point:

我正试图弄清楚如何从scratch中实现RSA crypto(仅仅是为了进行智力练习)，我在这一点上被卡住了:

For encryption, c = m^e mod n

对于加密，c = me mod n。

Now, e is normally 65537. m and n are 1024-bit integers (eg 128-byte arrays). This is obviously too big for standard methods. How would you implement this?

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

I've been reading a bit about exponentiation here but it just isn't clicking for me:

我已经读了一些关于指数的东西但它并没有点击我:

Wikipedia-Exponentiation by squaring

Wikipedia-Exponentiation的平方

This Chapter (see section 14.85)

本章(见第14.85条)

Thanks.

谢谢。

edit: Also found this - is this more what i should be looking at? Wikipedia- Modular Exponentiation

编辑:也发现了这个——这是我应该看的更多吗?*-模幂运算

4 个解决方案

#1

Exponentiation by squaring:

求幂平方:

Let's take an example. You want to find 17²³. Note that 23 is 10111 in binary. Let's try to build it up from left to right.

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

When you square, you double the exponent (shift left by 1 bit). When you multiply by m, you add 1 to the exponent.

当你平方时，你的指数翻倍(左移1位)。当你乘以m时，你在指数上加1。

If you want to reduce modulo n, you can do it after each multiplication (rather than leaving it to the end, which would make the numbers get very large).

如果你想要减少模量n，你可以在每次相乘后做(而不是把它留到最后，这会使数字变得非常大)。

65537 is 10000000000000001 in binary which makes all of this pretty easy. It's basically

65537是10000000000000001二进制，这使得所有这些都很简单。它基本上是

a = m
repeat 16 times:
    a = a * a
    a = a mod n
a = a * m
a = a mod n

where of course a, n and m are "big integers". a needs to be at least 2048 bits as it can get as large as (n-1)².

当然，a、n和m都是“大整数”。a需要至少2048比特，因为它可以达到(n-1)2。

#2

For an efficient algorithm you need to combine the exponentiation by squaring with repeated application of mod after each step.

对于一种有效的算法，你需要在每一步之后，通过对mod的重复应用进行平方。

For odd e this holds:

对于奇怪的e，它成立:

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

我mod n = m⋅我1 mod n

For even e:

即使e:

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

我对n = (me/2 mod n)2 mod n。

With m¹ = m as a base case this defines a recursive way to do efficient modular exponentiation.

用m1 = m作为基本情况，这定义了一种递归的方法来实现高效的模幂运算。

But even with an algorithm like this, because m and n will be very large, you will still need to use a type/library that can handle integers of such sizes.

但是，即使有这样的算法，因为m和n将非常大，您仍然需要使用一个类型/库来处理这些大小的整数。

#3

result = 1
while e>0:
  if (e & 1) != 0:
    result = result * m
    result = result mod n
  m = m*m
  m = m mod n
  e = e>>1
return result

This checks bits in the exponent starting with the least significant bit. Each time we move up a bit it corresponds to doubling the power of m - hence we shift e and square m. The result only gets the power of m multiplied in if the exponent has a 1 bit in that position. All multiplications need to be reduced mod n.

这将检查指数中以最小值开始的位。每次向上移动时，它对应的是m的两倍，所以我们移动e和m，结果只有当指数在这个位置上有1位时，才会得到m的乘方。所有的乘法都需要被简化。

As an example, consider m^13. 11 = 1101 in binary. so this is the same as m^8 * m^4 * m. Notice the powers 8,4,(not 2),1 which is the same as the bits 1101. And then recall that m^8 = (m^4)^2 and m^4 = (m^2)^2.

作为一个例子,考虑m ^ 13。11 = 1101二进制。这是一样的m ^ 8 * m ^ 4 * m。注意到权力8日4,(2),1,1101位是一样的。然后记得m ^ 8 =(m ^ 4)^ 2和m ^ 4 =(m ^ 2)^ 2。

#4

If g(x) = x mod 2^k is faster to calculate for your bignum library than f(x) = x mod N for N not divisible by 2, then consider using Montgomery multiplication. When used with modular exponentiation, it avoids having to calculate modulo N at each step, you just need to do the "Montgomeryization" / "un-Montgomeryization" at the beginning and end.

如果g(x)= x国防部2 ^ k是更快的计算为你bignum图书馆比f(x)= x mod N N不能被2整除,那么考虑使用蒙哥马利乘法。当使用模幂运算时，它会避免在每一步中计算模N，你只需要在开始和结束时做“Montgomeryization”/“un-Montgomeryization”。

#1