C++自主实现RSA加密算法解密输出异常无法定位问题根源

云原生阿岚

2026-9-24

代码问题排查与修复

核心问题：幂运算溢出

你当前实现的普通幂运算会在指数偏大时直接超出unsigned long long的存储上限，发生无符号整数溢出截断，最终取模结果与预期不符。RSA加解密需使用模幂运算，每一步计算后直接取模，从根源避免数值溢出。

其他存在的问题

素数判断逻辑与注释不符：注释标注判断上限为sqrt(n)，但实际代码使用0.5 * n作为上限，虽不会误判素数，但执行效率极低，大素数场景下会出现明显卡顿。
模逆计算暴力枚举效率低：当前模逆实现通过递增遍历寻找符合条件的d，小参数下可正常运行，参数增大后会出现长时间无响应的问题。
未限制明文大小：RSA算法要求输入明文必须小于公钥n，若输入明文大于等于n也会出现异常输出。

修复后的核心代码

1. 新增模幂运算函数

#include <cmath>
// 替代原有普通pow函数，计算 (base^exponent) % mod
unsigned long long modPow(unsigned long long base, unsigned long long exponent, unsigned long long mod) {
    unsigned long long result = 1;
    base = base % mod;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result = (result * base) % mod;
        }
        exponent = exponent >> 1;
        base = (base * base) % mod;
    }
    return result;
}

2. 修正素数判断函数

bool prime(const unsigned long long n) {
    if(n <= 1) return false;
    if(n == 2) return true;
    if(n % 2 == 0) return false;
    unsigned long long m = sqrt(n);
    for(unsigned long long i = 3; i <= m; i += 2)
        if(n % i == 0)
            return false;
    return true;
}

3. 修改加解密逻辑

unsigned long long RSA::encrypt(const unsigned long long message, const unsigned long long e, const unsigned long long n) {
    return modPow(message, e, n);
}

unsigned long long RSA::decrypt(const unsigned long long encryptedMessage, const unsigned long long d, const unsigned long long n) {
    return modPow(encryptedMessage, d, n);
}