A Quiet Change to RSA
11 hours ago
- #Cryptography
- #RSA
- #Euler's totient function
- An RSA public key consists of a pair (e, n), where e is an exponent and n is the product of two large primes p and q.
- Originally, RSA chose a private key d and computed e, but now e is chosen first (commonly 65537) and d is computed.
- Euler’s totient function φ(n) = (p − 1)(q − 1) is used to relate e and d in the original RSA paper.
- RSA security relies on the difficulty of computing φ(n) without knowing p and q.
- Carmichael’s totient function λ(n) replaced Euler’s φ(n) for computing d, leading to smaller private keys and faster decryption.
- λ(n) is defined as the smallest number that can replace φ(n) in Euler’s theorem and divides φ(n).
- The change to Carmichael’s function results in λ(n) being smaller than φ(n) by a factor of gcd(p − 1, q − 1).
- Experiments show that the gcd of (p − 1, q − 1) is usually small (median 2, mean 35.44, max 2370 in a test of 100 samples).
- The efficiency gain from using Carmichael’s totient is minimal compared to other optimizations like Garner’s algorithm.