# Why do we need Euler's totient function $\varphi(N)$ in RSA?

After we calculated $$N = p * q$$, we calculate $$\varphi(N)$$ and use it later to determine $$e$$ (PR) and $$d$$ (PU). But why?

For decryption and encryption we only use $$N$$ and don't need $$\varphi(N)$$. So why can't we find $$e$$ and $$d$$ without Euler's totient function? I know that $$\varphi(N)$$ is giving me the amount of numbers which are coprime to $$N$$ and if $$N$$ is a prime then it would be $$\varphi(N) = N - 1$$. But why is this useful? Or rather why is it a must for determing $$e$$ and $$d$$ in RSA?

Edit: And why does $$e$$ need to be smaller than $$\varphi(N)$$?

• Do you understand how $e$ and $d$ are generated in RSA key generation, and what relationship they need to satisfy? – pg1989 Mar 13 '16 at 23:25

What we really need is a number $\lambda$ satisfying $x^{\lambda+1} \equiv x \pmod n$ for all integers $x$ (which, by induction, then implies that $x^{k\lambda+1} \equiv x \pmod n$ for any $k$).

Given such a $\lambda$, and an arbitrary encryption exponent $e$ which is coprime to it, we can then find the multiplicative inverse of $e$ modulo $\lambda$, i.e. a number $d$ such that $ed \equiv 1 \pmod \lambda$, or in other words, $ed = k\lambda + 1$ for some integer $k$. Such $e$ and $d$ then satisfy $$(x^e)^d = x^{ed} = x^{k\lambda+1} \equiv x \pmod n,$$ meaning that, if we encrypt a number by raising it to the $e$-th power modulo $n$, we can recover the original number by raising the result to the $d$-th power and again reducing it modulo $n$. This is what we need for RSA encryption and decryption to work correctly.

The smallest such number $\lambda$ is given by the Carmichael totient function, which, for a product $n = pq$ of two primes, is $$\lambda(pq) = \operatorname{lcm}(p-1, q-1)$$ where $\operatorname{lcm}(p-1,q-1)$ denotes the least common multiple of $p-1$ and $q-1$. However, since we don't necessarily need the smallest such number, it's also possible to use the Euler totient function $$\varphi(pq) = (p-1)(q-1)$$ which is, by definition, always a multiple of $\lambda$.

I'm not aware of any particular reason for preferring $\varphi$ over $\lambda$, except that it's slightly easier to compute $\varphi$ and to explain why it has the necessary property $x^{\varphi+1} \equiv x \pmod n$, which may be why introductory texts tend to prefer it. I do believe, however, that actual practical RSA implementations (insofar as they explicitly compute the decryption exponent at all, rather than e.g. using the Chinese remainder theorem) generally use $\lambda$ rather than $\varphi$, since doing so yields the smallest possible decryption exponent $d$.

Addendum: The reason why $\lambda$ (and $\varphi$) satisfies $x^{\lambda+1} \equiv x \pmod n$ is basically Fermat's little theorem, which says that, for any prime $p$ and any integer $x$, $$x^p \equiv x \pmod p.$$

This can be easily generalized to show that, for any multiple $k\lambda(p)$ of $\lambda(p) = p-1$, $$x^{k\lambda(p)+1} \equiv x^{\lambda(p)+1} = x^p \equiv x \pmod p.$$

In particular, since $\lambda(pq) = \operatorname{lcm}(p-1,q-1)$ is, by definition, a multiple (and in fact, the smallest common multiple) of both $\lambda(p) = p-1$ and $\lambda(q) = q-1$, it follows that $x^{\lambda(pq)+1} \equiv x$ modulo both $p$ and $q$, and therefore, also modulo $pq = n$.

Of course, since $\varphi(pq) = (p-1)(q-1)$ is also a multiple of both $p-1$ and $q-1$, it also has the same property, as does any other common multiple of those numbers.

The fact that $\varphi(n)$ also happens to be the order of the multiplicative group modulo $n = pq$ is basically a red herring; there's nothing special about $\varphi(n)$ among all the other multiples of $\lambda(n)$ as far as RSA is concerned. What's more relevant is that $\lambda(n)$ is the exponent of this group, which is essentially another way of stating the crucial property that $x^{\lambda(n)+1} \equiv x \pmod n$ for all $x$.

• "... it's slightly easier to compute φ and to explain why it has the necessary properties". Sorry I do not see where you explained the properties? I just got the fact that you can use it, but not why you can use it. So now I know that phi(N) can be used to determine the lambda. But why? What has the number of integers which are coprime to N to do with this? – Rimen Mar 14 '16 at 13:44
• What is interesting in $\phi(N)$ is not the number of coprime of $N$. But the property $\phi(N)=(p-1)(q-1)$. – Biv Mar 14 '16 at 14:49
• @Biv Could you explain shortly in your words why this property is interesting? – Joey Mar 15 '16 at 7:34

To complete Ilmari great answer, I would like to quote the Handbook of Applied Cryptography (p 286,291):

Proof that decryption works. Since $ed \equiv 1 \pmod \phi$, there exists and integer $k$ such as $ed = k\phi +1$. Now, if $gcd(m,p) = 1$ then my Fermat's little theorem

$m^{p-1} \equiv 1 \pmod p$

Raising both sides of this congruence to the power $k(q-1)$ and then multiplying both sides by $m$ yields

$m^{k(p-1)(q-1)+1} \equiv m \pmod p$

On the other hand, if $gcd(m,p) = p$, then this last congruence is again valid since each side is congruent to $0$ modulo $p$. Hence in all cases

$m^{ed} \equiv m \pmod p$

By the same argument,

$m^{ed} \equiv m \pmod q$

Finally, since $p$ and $q$ are distinct primes, it follows that

$m^{ed} \equiv m \pmod n$

This emphasis the reason why the use of $k\phi + 1 = k(p-1)(q-1)+1$ (or $k\lambda+1$ in Ilmari answer).

And on the use of $\phi$ over $\lambda$:

8.5 Note (universal exponent) The number $\lambda = lcm(p-1,q-1)$, sometimes called the universal exponent of $n$, may be used instead of $\phi = (p-1)(q-1)$ in the RSA key generation. Observe that $\lambda$ is a proper divisor of $\phi$. Using $\lambda$ can result in a smaller decryption $d$, which may result in faster decryption (cf. Note 8.9). However, if $p$ and $q$ are chosen at random, then $gcd(p-1,q-1)$ is expected to be smallm and consequently $\phi$ and $\lambda$ will be roughly the same size.

8.9 Note (small encryption exponents)
(i) If the encryption exponent $e$ is chosen at random, then RSA encryption using the repeated square-and-multiply algorithm takes $k$ modular multiplications and an expected $k/2$ (less with optimizations) modular multiplications, where $k$ is the bitlength of the modulus $n$. Encryption can be sped up by selecting $e$ to be small and/or by selecting $e$ with a small number of 1's in its binary representation. [$\ldots$] Another encryption exponent used in practice is $e = 2^{16}+1 = 655357$. This number has only two 1's in its binary representation, so encryption using the repeated square-and-multiply algorithm requires only 16 modular squaring and 1 modular multiplication.

• I don't get where k comes from? What does k stand for? Why does it need to be defined? – Rimen Mar 14 '16 at 14:03
• Let's consider $p=5,q=11$ then $\phi=4 \times10=40$. Suppose $e=7$ then $d=23$. $e \times d=23 \times 7=161=4 \times 40 + 1$. Hence here $k$ is $4$. But this is not what really matters, the most interesting is that $ed=4 \times 40 + 1 \equiv 1 \pmod{40}$. $k$ is only here to make the link with the modulo. If you were to give it a name, $k$ is the quotient of the division of $ed$ by $\phi$. – Biv Mar 14 '16 at 14:46

Why?

$\varphi(N)$, in the original RSA specification, works because it is a multiple of $\lambda(N)$.

Exponentiation of ring $R_N$ creates a period of length $\lambda(N)$. The cycle of this period starts as $m^0\equiv1 \pmod{N}, m^1\equiv m \pmod{N},...$

Using any multiple $k\lambda(N)$, including $\varphi(N)$, to compute the multiplicative inverse $d$ of $e$ can be viewed two ways. The first, $ed \equiv 1 \pmod{\lambda(N)}$ results in $m^{k\lambda(N)+1} \equiv m^{ed} \equiv m^1 \equiv m \pmod{N}$. And second, $ed=k\lambda(N)+1$ where $k\lambda(N)$ is a multiple of the period and $+1$ then becomes the second element of the cycle, aka $m^1 \equiv m \pmod{N}$.

Why do we need $\varphi(N)$ to compute $d$?

As noted above, any multiple $k\lambda(N)$, including $\varphi(N)$, can be used to compute a valid $d$, and each result may be unique. Because, $k\lambda(N)$ is a multiple of the period and $ed$ is the first element in the cycle of the period. Therefore, $m^{k\lambda(N)+1} \equiv m^{ed} \equiv m^1 \equiv m \pmod{N}$.

You can us any number (almost) to create a multiplicative inverse, however the resulting $ed$ will not align with the period. Therefore will not recover $m$.

Why $e$ needs to be smaller that $\varphi(N)$?

Numbers are typically smaller than the modulus, $\varphi(N)$ in this case. Though, technically, it doesn't need to be. It does help the computation cost by keeping these exponents smaller. It also makes sense that when smaller than $\varphi(N)$, computing $e$ as the multiplicative inverse of $d$ will result in the same $e$.