lcm versus phi in RSA

Question

In textbook RSA, the Euler $\varphi$ function $$\varphi(pq) = (p-1)(q-1)$$ is used to define the private exponent $d$. On the other hand, real-world cryptographic specifications require the Carmichael lcm function $$\lambda(pq) = \operatorname{lcm}(p-1,q-1)$$ to define $d´$. It is clear that the $d´$ divides $d$, and therefore using $d´$ may be more efficient than using $d$.
My question is: Are there any further reasons, e.g. regarding security, why one should not use $d$?

Answer 1

I'll use these common definitions and notations:

• $a\equiv b\pmod c$ means that $c>0$ and $c$ divides $b-a$
• $a\equiv b^{-1}\pmod{c}$ means that $a\cdot b\equiv 1\pmod{c}$
• $a=b\bmod c$ means that $a\equiv b\pmod{c}$ and $0\le a<c$
• $a=b^{-1}\bmod c$ means that $a\equiv b^{-1}\pmod c$ and $0\le a<c$
• $\varphi$ is the Euler totient function (also noted $\phi$)
• $\lambda$ is the Carmichael function

I restrict to $N$ product of distinct primes; for two such primes, $\varphi(N)=(p-1)\cdot(q-1)$, $\lambda(N)=\operatorname{lcm}(p-1,q-1)$, and $\varphi(N)=\lambda(N)\cdot\gcd(p-1,q-1)$.

---

The cryptographic standard PKCS#1 requires that the private exponent $d$ is an integer with $0<d<N$ and $e\cdot d \equiv1\pmod{\lambda(N)}$. The later condition is used because it is precisely the necessary and sufficient condition on $d$ so that textbook RSA works, that is: $$\forall x\in\{0,\dots,n-1\}, y=x^e\bmod N\implies x=y^d\bmod N$$

Notice that $e\cdot d \equiv1\pmod{\lambda(N)}$, or equivalently $d\equiv e^{-1}\pmod{\lambda(N)}$, does not uniquely define $d$. If $d$ is a valid private exponent, then from a mathematical standpoint $k\cdot\lambda(N)+d$ is also a valid private exponent $\forall k\in\mathbb Z$, and is valid from a PKCS#1 standpoint when $0<d<N$.

It is PKCS#1-conformant to use $d=e^{-1}\bmod\varphi(N)$; that uniquely defines a value of $d$, with $0<d<N$ since $\varphi(N)\le N$, and $d\equiv e^{-1}\pmod{\lambda(N)}$ since $\lambda(N)$ divides $\varphi(N)$. This common choice of $d$ will lead to exactly the same results as using any other valid $d$ when exponentiating to the $d$^th power modulo $N$. As far as we know, it is not less safe than using $d=e^{-1}\bmod\lambda(N)$, even when side channel attacks are taken into consideration.

Using $d=e^{-1}\bmod\lambda(N)$ rather than $d\equiv e^{-1}\pmod{\varphi(N)}$ is not a good speed optimization: if one is interested in speed, one does not use $d$ at all! Rather, one implements RSA using the Chinese Remainder Theorem (CRT), where exponentiation is performed modulo each prime $p$ dividing $N$, using an exponent which can be computed as $d_p=e^{-1}\bmod{(p-1)}$ irrespective of which $d$ is chosen.

Update: as pointed in comment, the FIPS 186-4 standard requires $2^{\lceil\log_2(N)\rceil/2}<d<\lambda(N)$. Use of $\lambda(N)$ rather than $\varphi(N)$ restricts to a single private exponent, easing Known Answer Tests used for certification; does that in the most mathematically satisfying way; and happens to simplify the requirement $2^{\lceil\log_2(N)\rceil/2}<d$, intended to repel some dangerous ideas of using $p$, $q$ and/or $e$ crafted for low $d$, which otherwise would need to be expressed as the cumbersome $2^{\lceil\log_2(N)\rceil/2}<\big(d\bmod\lambda(N)\big)$.

Answer 2

The security of $\varphi$ and $\lambda$ should be equivalent since they are mathematically equivalent in the context in which they are used. (That is: the $d´$th power in $(\mathbb Z/pq \mathbb Z)^\times$ is exactly the same operation as the $d$th power.)

However, the mathematically right modulus for computing $d$ is $\lambda(pq)$: it is precisely the exponent of the group $(\mathbb Z/pq\mathbb Z)^\times$, that is, the least non-negative integer $k$ such that $x^k\equiv1\pmod{pq}$ for all $x\in(\mathbb Z/pq\mathbb Z)^\times$. Both options work, but what one actually wants, conceptually, is $\lambda$. Along with the practical performance advantage, this makes it the better choice.