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* = *m*^{e} 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 we discussed in the previous 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 *m*^{e} is an invertible function on *G*. Its inverse is the function that maps *c* to *c*^{d} where *d* is the private key. Encryption is an automorphism of *G* because

(*m*_{1} *m*_{2}) ^{e} = *m*_{1}^{e} *m*_{2}^{e} 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

*m*^{k} = 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*).