C++实现RSA大整数加解密时解密结果与原文不一致问题咨询

核心原因 #

• 私钥计算函数中变量x定义为int类型，public_key为(p-1)*(q-1)，数值接近2^{31，当`x`取值超过1时，`x*public_key`直接超出32位有符号int的最大值（2}31-1=2147483647），发生有符号整数溢出（C++中有符号整数溢出属于未定义行为），最终计算得到的私钥d完全错误。
• 暴力枚举求解模逆元的方式效率极低，且天生容易触发数值溢出，小数值明文可以正常解密属于巧合，是错误的d刚好满足小数值的模幂结果匹配。
• 额外问题：模幂函数重复调用两次递归计算，存在不必要的性能损耗；未提前校验e和φ(n)是否互素，若二者不互素则不存在合法私钥，加解密必然失败。

修复方案 #

1. 将私钥计算函数中的x改为unsigned long long类型，避免溢出。
2. 替换暴力枚举为扩展欧几里得算法求解模逆元，效率和正确性都有保障。
3. 优化模幂函数，避免重复计算，也可改为迭代实现避免递归栈风险（当前场景递归深度极低无问题）。

修复后代码示例 #

#include <iostream>
using namespace std;
// 优化后的模幂函数，避免重复递归
unsigned long long poww(unsigned long long a, unsigned long long k, unsigned long long q)
{
    if (k == 0) return 1;
    unsigned long long w = poww(a, k/2, q);
    w = (w * w) % q;
    if(k % 2 == 1) w = (w * a) % q;
    return w;
}
// 扩展欧几里得算法求模逆元
unsigned long long ext_gcd(unsigned long long a, unsigned long long b, long long &x, long long &y)
{
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    unsigned long long d = ext_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return d;
}
unsigned long long private_key(unsigned long long phi, unsigned long long e) {
    long long x, y;
    unsigned long long g = ext_gcd(e, phi, x, y);
    if (g != 1) {
        cout << "e和φ(n)不互素，不存在逆元" << endl;
        exit(1);
    }
    // 保证逆元为正
    x = (x % phi + phi) % phi;
    return (unsigned long long)x;
}
int main() {
    unsigned long long p = 47917;
    unsigned long long q = 44771;
    unsigned long long n = p * q;
    unsigned long long phi = (p-1)*(q-1);
    unsigned long long e = 24407;
    unsigned long long d = private_key(phi, e);
    unsigned long long message = 6382179;
    cout << "Message: " << message << endl;
    unsigned long long encrypted_message = poww(message, e, n);
    cout << "Encrypted message: " << encrypted_message << endl;
    unsigned long long decrypted_message = poww(encrypted_message, d, n);
    cout << "Decrypted message: " << decrypted_message << endl;
    return 0;
}

运行验证 #

修复后解密结果将和原始明文完全一致。 #

内容的提问来源于stack exchange，提问作者dosad