An RSA public key is a pair of numbers (e, n) where e is an exponent and n = pq where p and q are large prime numbers. The original RSA paper said choose a private key d and compute e. In practice now we choose e and compute d. Furthermore, e is now almost always 65537 for reasons given here. So the public key is essentially just n.
Euler’s totient function
The relationship between the exponent and the private decryption key in the original RSA paper was
ed = 1 mod φ(n).
It is easy to compute e given d, or d given e, when you know Euler’s totient function of n,
φ(n) = (p − 1)(q − 1).
The security of RSA encryption rests on the assumption that it is impractical to compute φ(n) unless you know p and q.
Carmichael’s totient function
Gradually over the course of several years, the private key d changed from being the solution to
ed = 1 mod φ(n)
to being the solution to
ed = 1 mod λ(n)
where Euler‘s totient function φ(n) was replaced with Carmichael‘s totient function λ(n).
The heart of the original RSA paper was Euler’s generalization of Fermat’s little theorem which says if a is relatively prime to m, then
aφ(n) = 1 (mod n)
Carmichael’s λ(n) is defined to be the smallest number that can replace φ(n) in the equation above. It follows that λ(n) divides φ(n).
Why the change?
Using Carmichael’s totient rather than Euler’s totient results in smaller private keys and thus faster decryption. When n = pq for odd primes p and q,
λ(n) = lcm( (p − 1), (q − 1) ) = (p − 1)(q − 1) / gcd( (p − 1), (q − 1) )
so λ(n) is smaller than φ(n) by a factor of gcd( (p − 1), (q − 1) ). At a minimum, this factor is at least 2 since p − 1 and q − 1 are even numbers.
However, an experiment suggests this was a trivial savings. When I generated ten RSA public keys the gcd was never more than 8.
from sympy import randprime, gcd
for _ in range(10):
p = randprime(2**1023, 2**1024)
q = randprime(2**1023, 2**1024)
print(gcd(p-1, q-1))
I repeated the experiment with 100 samples. The median of the gcd’s was 2, the mean was 35.44, and the maximum was 2370. So the while gcd might be moderately large, but it is usually just 2 or 4.
Better efficiency
The efficiency gained from using Carmichael’s totient is minimal. More efficiency can be gained by using Garner’s algorithm.