C++ 计算 pow(a,b) mod n

Calculating pow(a,b) mod n

提问by Moein Hosseini

I want to calculate a^bmodn for use in RSA decryption. My code (below) returns incorrect answers. What is wrong with it?

我想计算 a ^b modn 以用于 RSA 解密。我的代码（如下）返回不正确的答案。它有什么问题？

unsigned long int decrypt2(int a,int b,int n)
{
    unsigned long int res = 1;

    for (int i = 0; i < (b / 2); i++)
    {
        res *= ((a * a) % n);
        res %= n;
    }

    if (b % n == 1)
        res *=a;

    res %=n;
    return res;
}

回答by Blastfurnace

You can try this C++ code. I've used it with 32 and 64-bit integers. I'm sure I got this from SO.

你可以试试这个 C++ 代码。我已经将它用于 32 位和 64 位整数。我确定我是从 SO 那里得到的。

template <typename T>
T modpow(T base, T exp, T modulus) {
  base %= modulus;
  T result = 1;
  while (exp > 0) {
    if (exp & 1) result = (result * base) % modulus;
    base = (base * base) % modulus;
    exp >>= 1;
  }
  return result;
}

You can find this algorithm and related discussion in the literature on p. 244 of

您可以在 p. 的文献中找到该算法和相关讨论。244

Schneier, Bruce (1996). Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition (2nd ed.). Wiley. ISBN 978-0-471-11709-4.

施奈尔，布鲁斯 (1996)。应用密码学：C 语言中的协议、算法和源代码，第二版（第 2 版）。威利。ISBN 978-0-471-11709-4。

---

---

Note that the multiplications result * baseand base * baseare subject to overflow in this simplified version. If the modulus is more than half the width of T(i.e. more than the square root of the maximum Tvalue), then one should use a suitable modular multiplication algorithm instead - see the answers to Ways to do modulo multiplication with primitive types.

请注意，在此简化版本中，乘法result * base和base * base可能会溢出。如果模数大于宽度的一半T（即大于最大值的平方根T），则应改用合适的模乘法算法 - 请参阅使用原始类型进行模乘法的方法的答案。

回答by Shubham Khatri

In order to calculate pow(a,b) % nto be used for RSA decryption, the best algorithm I came across is Primality Testing¹⁾which is as follows:

为了计算pow(a,b) % n用于 RSA 解密，我遇到的最好的算法是Primality Testing ¹⁾如下：

 int modulo(int a, int b, int n){
    long long x=1, y=a; 
    while (b > 0) {
        if (b%2 == 1) {
            x = (x*y) % n; // multiplying with base
        }
        y = (y*y) % n; // squaring the base
        b /= 2;
    }
    return x % n;
}

See below reference for more details.

有关更多详细信息，请参阅以下参考资料。

---

---

¹⁾Primality Testing : Non-deterministic Algorithms – topcoder

¹⁾ Primality Testing : Non-deterministic Algorithms – topcoder

回答by Kerrek SB

Usually it's something like this:

通常是这样的：

while (b)
{
    if (b % 2) { res = (res * a) % n; }

    a = (a * a) % n;
    b /= 2;
}

return res;

回答by ruakh

The only actual logic error that I see is this line:

我看到的唯一实际逻辑错误是这一行：

if (b % n == 1)

which should be this:

应该是这样的：

if (b % 2 == 1)

But your overall design is problematic: your function performs O(b) multiplications and modulus operations, but your use of b / 2and a * aimplies that you were aiming to perform O(log b) operations (which is usually how modular exponentiation is done).

但是您的整体设计是有问题的：您的函数执行 O(b) 乘法和取模运算，但是您使用b / 2和a * a暗示您的目标是执行 O(log b) 运算（这通常是模幂运算的完成方式）。

回答by bragboy

Doing the raw power operation is very costly, hence you can apply the following logic to simplify the decryption.

执行原始功率操作的成本非常高，因此您可以应用以下逻辑来简化解密。

From here,

从这里，

Now say we want to encrypt the message m = 7,
c = m^e mod n = 7^3 mod 33 = 343 mod 33 = 13.
Hence the ciphertext c = 13.

To check decryption we compute
m' = c^d mod n = 13^7 mod 33 = 7.
Note that we don't have to calculate the full value of 13 to the power 7 here. We can make use of the fact that
a = bc mod n = (b mod n).(c mod n) mod n
so we can break down a potentially large number into its components and combine the results of easier, smaller calculations to calculate the final value.

One way of calculating m' is as follows:-
Note that any number can be expressed as a sum of powers of 2. So first compute values of
13^2, 13^4, 13^8, ... by repeatedly squaring successive values modulo 33. 13^2 = 169 ≡ 4, 13^4 = 4.4 = 16, 13^8 = 16.16 = 256 ≡ 25.
Then, since 7 = 4 + 2 + 1, we have m' = 13^7 = 13^(4+2+1) = 13^4.13^2.13^1
≡ 16 x 4 x 13 = 832 ≡ 7 mod 33

现在假设我们要加密消息 m = 7,
c = m^e mod n = 7^3 mod 33 = 343 mod 33 = 13。
因此密文 c = 13。

为了检查解密，我们计算
m' = c^d mod n = 13^7 mod 33 = 7。
请注意，我们不必在这里计算 13 的 7 次方的完整值。我们可以利用
a = bc mod n = (b mod n).(c mod n) mod n的事实，
这样我们就可以将一个潜在的大数分解成它的组成部分，并结合更简单、更小的计算的结果来计算最终值。

计算 m' 的一种方法如下：-
请注意，任何数字都可以表示为 2 的幂之和。因此，首先计算
13^2, 13^4, 13^8, ...取模 33 的值。13^2 = 169 ≡ 4, 13^4 = 4.4 = 16, 13^8 = 16.16 = 256 ≡ 25。
然后，由于 7 = 4 + 2 + 1，我们有 m' = 13^7 = 13^(4+2+1) = 13^4.13^2.13^1
≡ 16 x 4 x 13 = 832 ≡ 7 mod 33

回答by chux - Reinstate Monica

Calculating pow(a,b) mod n

计算 pow(a,b) mod n

1. A key problem with OP's code is a * a. This is intoverflow (undefined behavior) when ais large enough. The type of resis irrelevant in the multiplication of a * a.

   The solution is to ensure either:

   • the multiplication is done with 2x wide math or
   • with modulusn, n*n <= type_MAX + 1

2. There is no reason to return a wider type than the type of the modulusas the result is always represent by that type.

   // unsigned long int decrypt2(int a,int b,int n)
   int decrypt2(int a,int b,int n)
   

3. Using unsignedmath is certainly more suitable for OP's RSA goals.

1. OP 代码的一个关键问题是a * a. int当a足够大时，这是溢出（未定义的行为）。的类型res与 的乘法无关a * a。

   解决方案是确保：

   • 乘法是用 2 倍宽的数学运算完成的，或者
   • 与模数n,n*n <= type_MAX + 1

2. 没有理由返回比模数类型更宽的类型，因为结果总是由该类型表示。

   // unsigned long int decrypt2(int a,int b,int n)
   int decrypt2(int a,int b,int n)
   

3. 使用无符号数学当然更适合 OP 的 RSA 目标。

---

---

Also see Modular exponentiation without range restriction

另请参阅无范围限制的模幂运算

// (a^b)%n
// n != 0

// Test if unsigned long long at least 2x values bits as unsigned
#if ULLONG_MAX/UINT_MAX  - 1 > UINT_MAX
unsigned decrypt2(unsigned a, unsigned b, unsigned n) {
  unsigned long long result = 1u % n;  // Insure result < n, even when n==1
  while (b > 0) {
    if (b & 1) result = (result * a) % n;
    a = (1ULL * a * a) %n;
    b >>= 1;
  }
  return (unsigned) result;
}

#else
unsigned decrypt2(unsigned a, unsigned b, unsigned n) {
  // Detect if  UINT_MAX + 1 < n*n
  if (UINT_MAX/n < n-1) {
    return TBD_code_with_wider_math(a,b,n);
  }
  a %= n;
  unsigned result = 1u % n;
  while (b > 0) {
    if (b & 1) result = (result * a) % n;
    a = (a * a) % n;
    b >>= 1;
  }
  return result;
}

#endif

回答by Jay

Are you trying to calculate (a^b)%n, or a^(b%n)?

你是想计算(a^b)%n，还是a^(b%n)？

If you want the first one, then your code only works when bis an even number, because of that b/2. The "if b%n==1" is incorrect because you don't care about b%nhere, but rather about b%2.

如果您想要第一个，那么您的代码仅在b是偶数时才有效，因为b/2。" if b%n==1" 是不正确的，因为您不关心b%n这里，而是关心b%2.

If you want the second one, then the loop is wrong because you're looping b/2times instead of (b%n)/2times.

如果你想要第二个，那么循环是错误的，因为你循环了b/2次而不是(b%n)/2次。

Either way, your function is unnecessarily complex. Why do you loop until b/2and try to multiply in 2 a's each time? Why not just loop until band mulitply in one a each time. That would eliminate a lot of unnecessary complexity and thus eliminate potential errors. Are you thinking that you'll make the program faster by cutting the number of times through the loop in half? Frankly, that's a bad programming practice: micro-optimization. It doesn't really help much: You still multiply by a the same number of times, all you do is cut down on the number of times testing the loop. If b is typically small (like one or two digits), it's not worth the trouble. If b is large -- if it can be in the millions -- then this is insufficient, you need a much more radical optimization.

无论哪种方式，您的功能都不必要地复杂。为什么要循环直到b/2并尝试每次乘以 2 a？为什么不循环直到b并且每次都乘以一个 a。这将消除许多不必要的复杂性，从而消除潜在的错误。您是否认为通过将循环次数减半可以使程序更快？坦率地说，这是一个糟糕的编程实践：微优化。它并没有多大帮助：您仍然乘以相同的次数，您所做的只是减少测试循环的次数。如果 b 通常很小（比如一位或两位数字），那就不值得麻烦了。如果 b 很大——如果它可以达到数百万——那么这还不够，你需要更彻底的优化。

Also, why do the %neach time through the loop? Why not just do it once at the end?

另外，为什么%n每次都通过循环？为什么不只在最后做一次？

回答by zed_0xff

int's are generally not enough for RSA (unless you are dealing with small simplified examples)

int对 RSA 来说通常是不够的（除非您正在处理小的简化示例）

you need a data type that can store integers up to 2²⁵⁶(for 256-bit RSA keys) or 2⁵¹²for 512-bit keys, etc

您需要一种可以存储最多 2 ^{256 个}整数（用于 256 位 RSA 密钥）或 2 ⁵¹²用于 512 位密钥等的数据类型

回答by Red.Wave

This(encryption) is more of an algorithm design problem than a programming one. The important missing part is familiarity with modern algebra. I suggest that you look for a huge optimizatin in group theory and number theory. If nis a prime number, pow(a,n-1)%n==1(assuming infinite digit integers).So, basically you need to calculate pow(a,b%(n-1))%n; According to group theory, you can find esuch that every other number is equivalent to a power of emodulo n. Therefore the range [1..n-1]can be represented as a permutation on powers of e. Given the algorithm to find efor nand logarithm of abase e, calculations can be significantly simplified. Cryptography needs a tone of math background; I'd rather be off that ground without enough background.

这（加密）更像是一个算法设计问题，而不是一个编程问题。重要的缺失部分是对现代代数的熟悉。我建议你在群论和数论中寻找一个巨大的优化。Ifn是一个质数，pow(a,n-1)%n==1（假设有无穷位整数）。所以，基本上你需要计算pow(a,b%(n-1))%n; 根据群论，你可以发现e每隔一个数字都等价于e模的幂n。因此，范围[1..n-1]可以表示为 的幂的排列e。由于算法找到e了n和对数a基地e，计算可以大大简化。密码学需要数学背景；我宁愿在没有足够背景的情况下离开那个地方。

回答by Nam Le

For my code a^k mod nin php:

对于我的代码a^k mod n在 php 中：

function pmod(a, k, n)
{
    if (n==1) return 0;
    power = 1;
    for(i=1; i<=k; $i++)
    {
        power = (power*a) % n;
    }
    return power;
}