c++ - 计算 pow(a,b) mod n

Question

我想计算 a ^b mod n 以用于 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;
}

score 62 · Accepted Answer

你可以试试这个 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;
}

您可以在第 4 页的文献中找到此算法和相关讨论。244 个

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

请注意，在此简化版本中，乘法result * base和base * base可能会溢出。如果模数大于宽度的一半T（即大于最大值的平方根T），则应改用合适的模乘算法 - 请参阅Ways to do modulo multiplication with primitive types的答案。

score 17 · Accepted Answer

为了计算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;
}

有关详细信息，请参阅下面的参考。

¹⁾ Primality Testing : Non-deterministic Algorithms – topcoder

score 13 · Accepted Answer

通常是这样的：

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

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

return res;

score 7 · Accepted Answer

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

if (b % n == 1)

应该是这样的：

if (b % 2 == 1)

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

score 4 · Accepted Answer

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

从这里开始，

现在假设我们要加密消息 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

score 2 · Accepted Answer

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

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

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

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

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

score 2 · Accepted Answer

计算 pow(a,b) mod n

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

解决方案是确保：
- 乘法是用 2x 宽的数学或
- 有模数 n，n*n <= type_MAX + 1
没有理由返回比模数类型更宽的类型，因为结果始终由该类型表示。
```
// unsigned long int decrypt2(int a,int b,int n)
int decrypt2(int a,int b,int n)
```
使用无符号数学当然更适合 OP 的 RSA 目标。

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

// (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

score 0 · Accepted Answer

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

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

score 0 · Accepted Answer

这是另一种方式。请记住，当我们在 mod 下找到modulo multiplicative inverseof时。然后am

a和m必须coprime相互配合。

我们可以gcd extended用来计算modulo multiplicative inverse。

为了计算a ^b mod m何时a并且b可以有超过 10 个⁵位，那么计算结果就很棘手。

下面的代码将完成计算部分：

#include <iostream>
#include <string>
using namespace std;
/*
*   May this code live long.
*/
long pow(string,string,long long);
long pow(long long ,long long ,long long);
int main() {
    string _num,_pow;
    long long _mod;
    cin>>_num>>_pow>>_mod;
    //cout<<_num<<" "<<_pow<<" "<<_mod<<endl;
    cout<<pow(_num,_pow,_mod)<<endl;
   return 0;
}
long pow(string n,string p,long long mod){
    long long num=0,_pow=0;
    for(char c: n){
        num=(num*10+c-48)%mod;
    }
    for(char c: p){
        _pow=(_pow*10+c-48)%(mod-1);
    }
    return pow(num,_pow,mod);
}
long pow(long long a,long long p,long long mod){
    long res=1;
    if(a==0)return 0;
    while(p>0){
        if((p&1)==0){
            p/=2;
            a=(a*a)%mod;
        }
        else{
            p--;
            res=(res*a)%mod;
        }
    }
    return res;
}

此代码有效，因为a ^b mod m可以写为(a mod m) ^{b mod m-1} mod m。

希望它有帮助{ :)

score -1 · Accepted Answer

使用快速求幂可能.....给出与上面的模板相同的 o(log n)

    int power(int base, int exp,int mod)
{
    if(exp == 0)
     return 1;

    int p=power(base, exp/2,mod);
    p=(p*p)% mod;
    return (exp%2 == 0)?p:(base * p)%mod;
}

score -1 · Accepted Answer

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

score -1 · Accepted Answer

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

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

score -2 · Accepted Answer

#include <cmath>
...
static_cast<int>(std::pow(a,b))%n

但我最好的选择是你在力量上溢出了 int（即：int 的数字是两个大）我在创建完全相同的函数时遇到了同样的问题。

score -2 · Accepted Answer

我正在使用这个功能：

int CalculateMod(int base, int exp ,int mod){
    int result;
    result = (int) pow(base,exp);
    result = result % mod;
    return result;
}

我解析变量结果是因为 pow 给你一个双精度值，并且为了使用 mod 你需要两个 int 类型的变量，无论如何，在 RSA 解密中，你应该只使用整数。

c++ - 计算 pow(a,b) mod n

14 回答 14

Related

Reference