RSA加解密计算异常求助：解密结果与原消息不符

算力阿峰

2026-6-18

RSA解密失败问题排查与修复

问题原因

你的RSA参数选择完全符合规则：p、q是质数，phi(n)计算正确，e与phi(n)互质，d的逆元计算也正确（验证：11 * 6457379 mod 17757792 = 1），加密结果18^11 mod 17766221 = 11689003也正确。

解密结果错误的核心原因是手动（或程序实现错误）计算大指数模幂时出现了偏差。直接计算11689003^6457379显然不现实，必须通过快速模幂算法分步计算，否则极易出现计算错误。

根据RSA数学原理，当x与n互质时，x^(e*d) ≡ x mod n。这里18与n（17766221）互质，且e*d = 1 + 4*phi(n)，因此x^(e*d) = x*(x^phi(n))^4 ≡ x*1^4 = x mod n，必然得到原消息18。

通过正确的模幂计算工具验证，11689003^6457379 mod 17766221的结果确实为18。

实现正确的快速模幂算法：
快速模幂的核心是将指数分解为二进制，分步计算并取模，避免大数溢出或计算错误。示例Python实现：
```
def mod_pow(base, exp, mod):
    result = 1
    base = base % mod
    while exp > 0:
        if exp % 2 == 1:
            result = (result * base) % mod
        exp = exp // 2
        base = (base * base) % mod
    return result
```
调用mod_pow(11689003, 6457379, 17766221)将得到正确结果18。
利用语言内置函数：
多数编程语言内置了高效的模幂实现，比如Python的pow(11689003, 6457379, 17766221)可直接返回正确结果。