RSA encryption a map from numbers mod n to numbers mod n where n is a public key. A message is represented as an integer m and is encrypted by computing
c = me mod n
where e is part of the public key. In practice, e is usually 65537 though it does not have to be.
Multiplicative group
As discussed in an earlier post, not all messages m can be decrypted unless we require m to be relatively prime to n. In practice this is almost certainly the case: discovering a message m not relatively prime to n is equivalent to finding a factor of n and breaking the encryption.
If we limit ourselves to messages which can be encrypted and decrypted, our messages come not from the integers mod n but from the multiplicative group of integers mod n: the integers less than and relatively prime to n form a group G under multiplication.
The encryption function that maps m to me is an invertible function on G. Its inverse is the function that maps c to cd where d is the private key. Encryption is an automorphism of G because
(m1 m2) e = m1e m2e mod n.
Totient functions
Euler’s theorem tells us that
mφ(n) = 1 mod n
for all m in G. Here φ is Euler’s totient function. There are φ(n) elements in G, and so we could see this as a consequence of Lagrange’s theorem: the order of an element divides the order of a group.
Now the order of a particular m might be less than φ(n). That is, we know that if we raise m to the exponent φ(n) we will get 1, but maybe a smaller exponent would do. In fact, maybe a smaller exponent would do for all m.
Carmichael’s totient function λ(n) is the smallest exponent k such that
mk = 1 mod n
for all m. For some values of n the two totient functions are the same, i.e. λ(n) = φ(n). But sometimes λ(n) is strictly less than φ(n). And going back to Lagrange’s theorem, λ(n) always divides φ(n).
For example, there are 4 positive integers less than and relatively prime to 8: 1, 3, 5, and 7. Since φ(8) = 4, Euler’s theorem says that the 4th power of any of these numbers will be congruent to 1 mod 8. That is true, but its also true that the square of any of these numbers is congruent to 1 mod 8. That is, λ(8) = 2.
Back to RSA
Now for RSA encryption, n = pq where p and q are large primes and p ≠ q. It follows that
φ(pq) = φ(p) φ(q) = (p − 1)(q − 1).
On the other hand,
λ(pq) = lcm( λ(p), λ(q) ) = lcm(p − 1, q − 1).
Since p − 1 and q − 1 at least share a factor of 2,
λ(n) ≤ φ(n)/2.
Example
It’s possible that λ(n) is smaller than φ(n) by more than a factor of 2. For example,
φ(7 × 13) = 6 × 12 = 72
but
λ(7 × 13) = lcm(6, 12) = 12.
You could verify this last calculation with the following Python code:
>>> from sympy import gcd
>>> G = set(n for n in range(1, 91) if gcd(n, 91) == 1)
>>> set(n**12 % 91 for n in s)
This returns {1}.
Implementation
The significance of Carmichael’s totient to RSA is that φ(n) can be replaced with λ(n) when finding private keys. Given a public exponent e, we can find d by solving
ed = 1 mod λ(n)
rather than
ed = 1 mod φ(n).
This gives us a smaller private key d which might lead to faster decryption.
OpenSSL example
I generated an RSA key with openssl as in this post
openssl genpkey -out fd.key -algorithm RSA \
-pkeyopt rsa_keygen_bits:2048 -aes-128-cbc
and read it using
openssl pkey -in fd.key -text -noout
The public exponent was 65537 as noted above. I then brought the numbers in the key over to Python.
from sympy import lcm
modulus = xf227d5...a9
prime1 = 0xf33514...d9
prime2 = 0xfee496...51
assert(prime1*prime2 == modulus)
publicExponent = 65537
privateExponent = 0x03896d...91
phi = (prime1 - 1)*(prime2 - 1)
lamb = lcm(prime1 - 1, prime2 - 1)
assert(publicExponent*privateExponent % lamb == 1)
assert(publicExponent*privateExponent % phi != 1)
This confirms that the private key d is the inverse of e = 65537 using modulo λ(pq) and not modulo φ(pq).
Related posts
