C++实现RSA加解密遇问题：解密结果不符合预期

你遇到的解密错误，核心问题出在pow()和fmod()的组合使用上——这俩都是浮点数运算函数，根本不适合处理RSA这种需要高精度整数运算的场景。

举个例子，你要计算1489^1613 mod 2117，但1489^1613是一个天文数字，远超出了双精度浮点数（double）能精确表示的范围（double最多能精确表示到2^53左右的整数）。用pow()计算时，浮点数会丢失大量有效数字，最后再用fmod()取模，结果自然完全不对。而加密时指数是5，15^5=759375还在浮点数的精确范围内，所以碰巧能得到正确结果。

RSA解密的核心是计算(密文^私钥指数) mod 模数，这种运算必须用整数模幂算法来实现，最常用的就是快速模幂（也叫模幂的二进制分解）。它的思路是把大指数拆解成二进制位，通过反复平方和取模，一步步计算结果，全程都是整数运算，不会有精度丢失，还能避免大数溢出。

这里给你一个适合你场景的C++实现：

// 快速模幂函数：计算 (base^exp) mod mod_value
long long mod_pow(long long base, long long exp, long long mod_value) {
    long long result = 1;
    // 先把基数取模，减少后续计算量
    base = base % mod_value;
    
    while (exp > 0) {
        // 如果当前指数位是1，将结果与当前基数相乘后取模
        if (exp % 2 == 1) {
            result = (result * base) % mod_value;
        }
        // 指数右移一位（等价于除以2）
        exp = exp >> 1;
        // 基数平方后取模
        base = (base * base) % mod_value;
    }
    return result;
}

然后把你的解密代码替换成：

long long decryptedText = mod_pow(toBeDecrypted, pubD, pubN);

代入你的测试值：mod_pow(1489, 1613, 2117)会返回15，也就是正确的明文。

• 如果你的后续需求中模数或指数更大，超出了long long的范围，可以改用unsigned long long，或者考虑使用专门的大整数库来处理超大整数运算。
• 永远不要用浮点数函数来处理密码学中的整数运算，精度丢失几乎一定会导致逻辑错误。

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