RSA in PyCryptodome: Verify the e and d inverse using Carmichael's lambda lcm(p-1,q-1) instead of Euler's totient

Learn why PyCryptodome's RSA uses Carmichael's lambda, not Euler's totient, for e and d. Verify keys with lcm(p-1,q-1) and avoid false alarms in audits.

RSA key generation in PyCryptodome may look inconsistent at first glance when you try to verify the modular inverse relationship between the public and private exponents. The surprise usually appears when a check against Euler’s totient returns a non‑zero remainder for some keys, even though encryption and decryption still work flawlessly.

Reproducing the issue

The following minimal code uses Crypto.PublicKey.RSA and gmpy2 to compute the remainder of (e · d − 1) modulo (p − 1)(q − 1). The expectation that this remainder should always be zero is what leads to the confusion.

from Crypto.PublicKey import RSA
import gmpy2 as gp
z = gp.mpz(0)
o = gp.mpz(1)
kpair = RSA.generate(1024)
p_val = gp.mpz(kpair.p)
q_val = gp.mpz(kpair.q)
n_mod = gp.mpz(kpair.n)
d_sec = gp.mpz(kpair.d)
e_pub = gp.mpz(kpair.e)
phi_mod = gp.mul(gp.sub(p_val, o), gp.sub(q_val, o))
quot, rem = gp.t_divmod(gp.sub(gp.mul(e_pub, d_sec), o), phi_mod)
print("remainder:", rem)
assert rem == z

What’s actually happening

The assumption that e and d are multiplicative inverses modulo Euler’s totient (phi) of n is the root of the issue. In PyCryptodome, d is constructed as the inverse of e with respect to Carmichael’s lambda function of n, not Euler’s totient. Both choices are valid for RSA, but using Carmichael’s lambda yields a private exponent that is a few bits smaller and therefore slightly more efficient. This approach is used by PyCryptodome and many other implementations.

For RSA moduli built from two primes p and q, Carmichael’s lambda is computed as lcm(p − 1, q − 1). That’s almost as straightforward to obtain as the product (p − 1)(q − 1), but it changes which congruence must hold for e and d.

Fixing the verification

To validate the key material the same way PyCryptodome defines it, compute the least common multiple of p − 1 and q − 1 and check the inverse relationship modulo that value.

from Crypto.PublicKey import RSA
import gmpy2 as gp
import math
z = gp.mpz(0)
o = gp.mpz(1)
kpair = RSA.generate(1024)
p_val = gp.mpz(kpair.p)
q_val = gp.mpz(kpair.q)
d_sec = gp.mpz(kpair.d)
e_pub = gp.mpz(kpair.e)
lam_mod = math.lcm(int(p_val - o), int(q_val - o))
quo2, rem2 = gp.t_divmod(gp.sub(gp.mul(e_pub, d_sec), o), gp.mpz(lam_mod))
print("remainder_lambda:", rem2)
assert rem2 == z

If you prefer, you can state the same condition even more directly:

assert (int(e_pub) * int(d_sec)) % lam_mod == 1

Why this matters

When you audit or instrument cryptographic code, it’s easy to embed checks that assume Euler’s totient as the canonical modulus for the inverse relationship. That assumption will lead to false alarms against libraries that use Carmichael’s lambda, even though the keys are valid and the algorithms behave correctly. Understanding which modulus an implementation targets prevents misdiagnosing healthy keys as inconsistent and keeps diagnostics aligned with the library’s design.

Takeaways

If you verify RSA keys from PyCryptodome, don’t expect (e · d − 1) mod (p − 1)(q − 1) to be zero for every key. Instead, use lcm(p − 1, q − 1) as the modulus for the check. This matches how the library defines the private exponent, avoids spurious assertion failures, and reflects a common practice that slightly reduces the size of d without changing the correctness of RSA.