A quiet change to RSA

An RSA public key is a pair of numbers (e,n) wheree is an exponent andn =pq wherep andq are large prime numbers. The original RSA paper said choose a private key d and computee. In practice now we choosee and computed. 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 computee givend, ord givene, when you know Euler's totient function ofn,

(n) = (p - 1)(q - 1).

The security of RSA encryption rests on the assumption that it is impractical to compute (n) unless you knowp andq.

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)

whereEulers totient function (n) was replaced with Carmichaels totient function (n).

The heart of the original RSA paper was Euler's generalization of Fermat's little theorem which says ifais relatively prime tom, then

a⁽ⁿ⁾= 1 (modn)

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. Whenn = 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, gcdfor _ 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.

The post A quiet change to RSA first appeared on John D. Cook.