A Quiet Change to RSA

Summary

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 wa...