C++实现RSA Algorithm对部分整数加密解密失效问题求助

问题根源 #

• 核心问题：加密、解密方法直接使用了cmath库的pow()函数，该函数返回值为双精度浮点数，当指数较大时会出现精度丢失，且计算结果超出int类型的存储范围时会发生溢出，最终导致模运算结果完全错误。
• 次要问题：RSA加密要求明文数值必须小于模数n，你当前代码中n = 3*11 = 33，如果输入的待加密整数大于等于33，也会出现无法解密的问题。
• 潜在问题：当前查找私钥d的逻辑只循环i到9，当后续调整p、q为更大的素数时，可能无法在该范围内找到合法的d值。

修复方案 #

你需要自行实现**模幂运算（快速幂）**方法，边计算乘法边取模，避免数值溢出和精度丢失：

第一步：修改头文件RSA.h，新增模幂运算私有方法声明 #

#ifndef _RSA_
#define _RSA_

#include <cmath>
#include <string>

// A class that defines the RSA algorithm
class RSA {
    private:
        int p, q, n, z, d = 0, e;
        // 新增模幂运算方法
        long long mod_pow(long long base, long long exp, long long mod);

    public:
        RSA();
        int gcd(int a, int b);
        int encrypt(int m);
        int decrypt(int c);
    
};

#endif

第二步：修改实现文件RSA.cpp，补充模幂方法、替换原有加密解密逻辑 #

#include "./RSA.h"

RSA::RSA() {
    this->p = 3;
    this->q = 11;
    this->z = (this->p - 1) * (this->q - 1);
    this->n = this->p * this->q;

    for (this->e = 2; this->e < this->z; this->e++) {
        if (this->gcd(this->e, this->z) == 1) {
            break;
        }
    }

    for (int i = 0; i <= 9; ++i) {
        int x = (i * this->z) + 1;
        if (x % this->e == 0) {
            this->d = x / this->e;
            break;
        }
    }
}

int RSA::gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// 新增模幂运算实现
long long RSA::mod_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        exp = exp >> 1;
        base = (base * base) % mod;
    }
    return result;
}

int RSA::encrypt(int m) {
    // 增加明文合法性校验
    if (m >= this->n || m < 0) {
        return -1;
    }
    return (int)mod_pow(m, this->e, this->n);
}

int RSA::decrypt(int c) {
    return (int)mod_pow(c, this->d, this->n);
}

验证效果 #

修改后重新测试[1,17]区间的整数，之前异常的3、4、5、17均可正常解密还原，所有测试用例均符合预期。

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