使用PyCryptodome时RSA算法出现模逆元验证不一致问题

在openSUSE Leap 15.6系统上使用版本为3.9.0-150200.9.1的python3-pycryptodome，调用Crypto.PublicKey.RSA类生成RSA密钥时，发现存在算法不一致问题。

代码片段 #

from Crypto.PublicKey import RSA
import gmpy2 as gm

zero = gm.mpz(0)
one = gm.mpz(1)

key = RSA.generate(1024)
p = gm.mpz(key.p)
q = gm.mpz(key.q)
n = gm.mpz(key.n)
d = gm.mpz(key.d)
e = gm.mpz(key.e)
f = gm.mul(gm.sub(p, one), gm.sub(q, one))
t, r = gm.t_divmod(gm.sub(gm.mul(e, d), one), f)

print("T:", t, "\nR:", r, "\n")
assert(r == zero)

预期与实际情况 #

理论上，e和d是模f=(p-1)*(q-1)的乘法逆元，因此(e*d -1)除以f的余数r应该始终为0，但批量生成密钥时该断言会随机失败。不过即便断言失败，生成的密钥仍能正常完成加密和解密操作。

示例错误输出 #

N:  148502774403628390194611500709682347814667593710263804255157829583856187369359709690285563468375111786415727941281838364540498319732753028415238432642064018564768129734406037062641477861055248558990411663521667242748082850681361695820916286468764801272766079977549468298872839357850688001921905070150870021617 

F:  148502774403628390194611500709682347814667593710263804255157829583856187369359709690285563468375111786415727941281838364540498319732753028415238432642063994175826236354417984972173597931150214536367983662042569355961801875348542016817518199738121181705454851577038738077546432331820850702935944555788782117440 

D:  3786287874221628833060271941142911125529353972159943582788217876798211113616120434328141578912323768742993739941575982481376680422409348089969728845438894796344787140928803863554860738865651625260009135296914439478294793149354932137846389802769093381050561713735488167704149676139058582518170514697039795113 

P:  12644301210276125955062852673893145078336308093529189288020587426377781795770169081395069044878276629331783016359362180011337579202434183256912567514342137 

Q:  11744640683103862097027615206036759955686314334472289809866198854597551023908834316691661598741290681896617494370859146395688450634864802703601794573562041 

E:  65537 

T:  1670 

R:  142315158803477207269836021513445583322389777305669479077859586684528846228969721786523664990526148795315072610395095099351310889743888318897936831281977994418500143172983902264999698017352288930685984342790795632796726797209019432783454941415699465801060899427995457324315330984661648590313613532630916195880 

Traceback (most recent call last):
  File "./utils.py", line 226, in <module>
    (n, f, d, p, q, s, k, u, e, g, h) = generate_rsa(1024, TYPE_CRYPTODOME, debug=True)
  File "./utils.py", line 83, in generate_rsa
    assert(r == zero)
AssertionError

疑问 #

为何会出现这种断言随机失败但密钥功能正常的情况？

问题核心是你对RSA密钥生成逻辑的认知与PyCryptodome的实现不一致：

• 传统教材常说d是e关于欧拉函数φ(n)=(p-1)(q-1)的逆元，但PyCryptodome的RSA.generate()实际使用的是卡迈克尔函数λ(n)——即lcm(p-1, q-1)（(p-1)和(q-1)的最小公倍数）来计算d。
• 因为λ(n)是φ(n)的约数，满足e*d ≡ 1 mod λ(n)的d，必然满足e*d ≡1 mod p-1和e*d ≡1 mod q-1，所以e*d-1是(p-1)和(q-1)的公倍数，但不一定是两者乘积φ(n)的倍数。这就导致你的断言会随机失败：当p-1和q-1互质时，φ(n)=λ(n)，断言成立；当两者不互质时，φ(n)是λ(n)的倍数，断言就会失败。
• 密钥能正常加密解密的原因是，RSA的正确性只要求e*d ≡1 mod λ(n)，这已经保证了对任意明文m，m^(e*d) ≡m mod n成立，完全不需要满足e*d ≡1 mod φ(n)。

简单来说，你的代码用了φ(n)作为校验模，但PyCryptodome实际用了更小的λ(n)生成d，所以余数不为0，但密钥功能不受影响。

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