The Carmichael Function

Hamdaan AliApril 3, 2025About 5 min

The Carmichael Function 관련

The Cryptography Handbook: Exploring RSA PKCSv1.5, OAEP, and PSS

The RSA algorithm was introduced in 1978 in the seminal paper, ”A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”. Over the decades, as RSA became integral to secure communications, various vulnerabilities and attacks have emerg...

The Cryptography Handbook: Exploring RSA PKCSv1.5, OAEP, and PSS

The Carmichael Function, represented by $\lambda\left(n\right)$ , also known as the reduced totient or least universal exponent, is defined as the smallest positive integer $m$ such that for every integer a co-prime to $n$ , $a^{m}\equiv{1}\left(\text{mod}\:n\right)$ .

To put this in easy terms, $\lambda\left(n\right)$ is the exponent of the multiplicative group modulo $n$ (the least common multiple of the orders of all elements). For RSA-style moduli (product of primes), the Carmichael function is guided by the formula:

\lambda\left(n\right)=\text{lcm}\left(p−1,q−1\right)

where $n=p\cdot{q}$ with $p$ and $q$ being the large primes.

You may now understand the Carmichael function better if we put it in the following way: $\lambda\left(n\right)$ is the least common multiple of $\lambda\left(n\right)$ of each prime power dividing $n$ . So for a prime $p$ , $\lambda\left(p\right)=\phi\left(p\right)=p-1$ , and for two primes, we take the $\text{lcm}$ of $p−1$ and $q−1$ .

Mathematical Implication of The Carmichael function

The Carmichael function $\lambda\left(n\right)$ is a “tighter” bound. What this means is that $\lambda\left(n\right)$ divides $\phi\left(n\right)$ (since the exponent of a finite group always divides the group order by Lagrange’s Theorem^[1])

If $p$ and $q$ are both odd primes, then $p-1$ and $q-1$ are even, so their least common multiple is roughly half of $(p-1)(q-1)$ . Mathematically:

\lambda\left(n\right)=\frac{\left(p-1\right)\left(q-1\right)}{\text{gcd}\left(p-1,q-1\right)}

We can observe that this $\lambda\left(n\right)$ is lesser than or equal to $\phi\left(n\right)$ and often considerably smaller. This means $\lambda\left(n\right)$ provides the minimal exponent needed for RSA’s correctness, whereas $\phi\left(n\right)$ might be a larger number that still works but isn’t necessary.

When you choose two large random primes $p$ and $q$ , you have:

\phi\left(n\right)=\left(p−1\right)\left(q−1\right)\approx{n}

because for large primes, the subtracted ones make only a small difference compared to $p$ and $q$ themselves.

Now, since both $p−1$ and $q−1$ are even, they each have a factor of $2$ . If those are their only common factors (which is often the case for random primes), then:

\lambda\left(n\right)=\text{lcm}\left(p−1,q−1\right)\approx\frac{\phi\left(n\right)}{2}

When you compute the private exponent $d$ as the modular inverse of e (a small number) modulo $\phi\left(n\right)$ versus modulo $\lambda\left(n\right)$ , the range from which $d$ is chosen is roughly twice as large in the former case. That means the typical $d$ when computed modulo $\phi\left(n\right)$ can be about twice as large as when computed modulo $\lambda\left(n\right)$ . A larger $d$ means that during decryption (or signing) the modular exponentiation cdmodn takes slightly more time.

Intuitively, using $\lambda\left(n\right)$ ensures we don’t “overshoot” the exponent required for the modular arithmetic to cycle back to 1. A smaller $d$ makes every RSA decryption and signature operation faster. For instance, if $\lambda\left(n\right)$ is roughly half of $\phi\left(n\right)$ , then $d$ will have one less bit than it would otherwise, cutting the exponentiation work by about 50%. This is a free performance gain, as we aren’t changing the security assumptions or the key size $n$ , just using the mathematically tight value for the exponent. The RSA algorithm’s security is not weakened by this and now the $d$ is different but functionally equivalent.

The Carmichael Function in Modern Implementations

The critical property for RSA ( $e\cdot{d}\equiv{1}\:\text{mod}\:\lambda\left(n\right)$ ) is both necessary and sufficient for correct decryption, thanks to Carmichael’s theorem. So there’s no need for $d$ to also satisfy the stronger condition modulo $\phi\left(n\right)$ .

By switching to computing $d$ modulo $\lambda\left(n\right)$ (i.e., $d=e^{−1}\:\text{mod}\:\lambda\left(n\right)$ ), we directly get the smallest working private exponent. Ronald Rivest himself noted this optimization in his 1999 seminal paper^[2], stating that solving for $d$ using $\lambda\left(n\right)$ instead of $\phi\left(n\right)$ is slightly preferable because it can result in a smaller value for $d$ .

Over time, the use of $\lambda\left(n\right)$ in RSA moved from an academic suggestion to an industry standard. Today’s cryptographic standards explicitly acknowledge or require the $\lambda\left(n\right)$ approach.

For example, the official RSA standard (PKCS #1 v2.2, RFC 8017^[3]) defines the RSA key generation in terms of $\lambda\left(n\right)$ . It specifies that the private exponent $d$ is chosen such that $e\cdot{d}\equiv{1}\left(\text{mod}\:\lambda\left(n\right)\right)$ (with $\lambda\left(n\right)=\text{lcm}\left(p-1,q-1\right)$ ). In other words, PKCS #1 expects the Carmichael function to be used for the modulus of the exponent. Likewise, NIST’s FIPS 186-4 (Digital Signature Standard) mandates that $d$ be less than $\lambda\left(n\right)$ .

Any RSA key where $d$ is larger than $\lambda\left(n\right)$ is considered non-compliant in those strict contexts. This effectively forces implementations to use the smaller $\lambda\left(n\right)$ -based exponent, since any “oversized” $d$ can be reduced mod $\lambda\left(n\right)$ to meet the criterion.

Standards such as FIPS 186-4^[4] (the Digital Signature Standard) and RFC 8017^[3:1] (which specifies PKCS#1 v2.2 for RSA Cryptography) include requirements or recommendations that imply the private exponent $d$ should be as small as possible and ideally less than $\lambda\left(n\right)$ . Using $\lambda\left(n\right)$ (the least common multiple of $p−1$ and $q−1$ ) directly produces the smallest valid d, whereas using $\phi\left(n\right)$ often results in a $d$ that is larger than necessary. This not only improves performance (by reducing the number of modular multiplications needed during decryption/signing) but also helps maintain interoperability with protocols that expect $d$ to be below a certain size.

The Python cryptography library (PyCA cryptography) explicitly documents^[5] that it uses Carmichael’s totient to generate the “smallest working value of $d$ ,” noting that older implementations (including the original RSA paper) used Euler’s totient and ended up with larger exponents. OpenSSL also uses the Carmichael function in their low-level RSA API^[6].

This shift to the Carmichael function ensures that under the hood your RSA key is a bit more efficient than the ones from the late 1970s while providing the same level of security.

Lagrange's theorem ↩︎
Ronald L. Rivest, Robert D. Silverman: Are Strong Primes Needed for RSA? ↩︎
RFC 8017 PKCS #1: RSA Cryptography Specifications ↩︎ ↩︎
FIPS 186-5: Digital Signature Standard (DSS) ↩︎
pyca/cryptography ↩︎
OpenSSL Github (openssl/openssl): rsa_chk.c ↩︎