# 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
• $e$ does not need to be smaller than $\varphi(N)$. Everything works correctly if it is larger. – Martin Kochanski Jun 21 at 17:56

## 4 Answers

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$.

The OP asks two questions. The first question is:

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

This is exactly the prescription on page 6 of the original RSA paper, where $$n=p\cdot q$$ is the product of two (very large) prime numbers, and, hence the number of integers relatively prime to $$n,$$ or Euler's totient function, is the multiplication $$\varphi(n)=(p-1)\cdot(q-1).$$ From the RSA paper:

You then pick the integer $$d$$ to be a large, random integer which is relatively prime to $$(p − 1) · (q − 1).$$ That is, check that $$d$$ satisfies: $$\gcd(d,(p − 1) · (q − 1)) = 1.$$

There are two points to explain in the way the OP is formulated. Firstly, the introduction of Euler's totient function stems from Fermat-Euler's theorem. Again quoting the RSA original paper, page 7:

We demonstrate the correctness of the deciphering algorithm using an identity due to Euler and Fermat: for any integer (message) $$M$$ which is relatively prime to $$n,$$ $$M^{\varphi(n)}\equiv 1 \pmod n$$

Multiplying each side by $$M,$$ and rearranging:

\begin{align} M^{k\,\varphi(n)}& \equiv 1 \pmod n\\ M\cdot M^{k\,\varphi(n)}& \equiv M \cdot 1\pmod n\\ M^{k\,\varphi(n)+1}& \equiv M \pmod n \end{align}

we get to the last equation showing that the message to encrypt ($$M$$) is unchanged under modular exponentiation by multiples ($$k$$) of Euler's totient function of $$n$$ plus $$1$$, i.e. $$\varphi(n) +1.$$ This is great news, because we can figure out an encryption ($$e$$) and decryption ($$d$$) set of keys such that

$$e\cdot d = k\,\varphi(n) +1$$

as $$d = \frac{k\,\varphi(n)+1}{e}.$$

Of note, $$k\,\varphi(n) +1,$$ with $$k$$ being an integer, is the mathematical formulation of $$1 \pmod{\varphi(n)},$$ or, equivalently, $$e\cdot d\equiv 1 \pmod{\varphi(n)}\tag 1.$$

[See below the post for a toy example of a manual solution.]

Therefore modular exponentiation of the message $$M$$ will render the original message if both keys, $$e$$ and $$d,$$ are known - in this way, one key can be made public, while the other key is kept private:

\begin{align} M^{k\,\varphi(n)+1}& \equiv M \pmod n\\ M^{e\cdot d}&\equiv M \pmod n \end{align}

As on the first quote from the RSA article, $$d$$ needs to be coprime to $$\varphi(n)$$ precisely so that (from the RSA paper):

...it has a multiplicative inverse e in the ring of integers modulo $$\varphi (n).$$

Hence, allowing a solution to Eq. (1).

This introduces the abstract algebra concept of the finite ring of integers modulo $$\varphi(n),$$ which can represented as $$\mathbb Z/\varphi(n)\mathbb Z.$$ At first sight this is scary, but it is simply saying that the set of integers in modular arithmetic form a finite ring with the operations of addition and multiplication, whereby an element of the set will have a multiplicative inverse provided it is coprime to the modulus. From Wikipedia:

A modular multiplicative inverse of an integer $$a$$ with respect to the modulus $$m$$ is a solution of the linear congruence $$ax\equiv 1\pmod {m}.$$ [...] a solution exists if and only if $$\gcd(a, m) = 1,$$ that is, $$a$$ and $$m$$ must be relatively prime (i.e. coprime).

For example, in the ring of of integers modulus $$10,$$ i.e. $$\mathbb Z/10\mathbb Z=\{0,1,2,3,\dots,9\},$$ the element $$9$$ being coprime to $$10$$ secures a multiplicative inverse, i.e. $$9\cdot 9 =81\equiv 1 \pmod {10}.$$

The idea is that modular exponentiation of $$M$$ to $$e\cdot d$$ equals exponentiation to $$1,$$ returning the original message.

The second question in the OP was:

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

follows as $$e$$ and $$d$$ are elements of the ring of integers modulus $$\varphi (n),$$ that is $$e,d\in \mathbb Z/\varphi(n)\mathbb Z.$$

Manual example:

Let's take $$p=13$$ and $$q=23,$$ yielding $$n=299.$$ The totient function is $$\varphi(299)=12\times 22 = 264.$$

To select the $$e$$ value we need a coprime to $$\varphi(n)=264.$$ Some of the coprime values of $$264$$ are $$245, 247, 251, 257, 259,...$$ If we select $$e=245,$$ the linear congruency to find a corresponding $$d$$ can be expressed as

$$245 d = 1 + 264k$$

This is equivalent to

$$245d + 264k =1\tag {*}$$

since is an arbitrary integer, $$k\in \mathbb Z,$$ and the rearrangement amounts to a change of sign, which wouldn't influence clock arithmetic.

Given that the values in equation $$(*)$$ are coprime, the expression amounts to Bézout's identity, $$245x+264y=\gcd(245,264),$$ and we can use the extended Euclidean theorem. This is explained in an example on this post.

Dividing the larger of the values ($$\color{blue}{264}$$) by the smaller value ($$\color{magenta}{245}$$) in the LHS of $$(*),$$ i.e. $$\color{magenta}{245}d + \color{blue}{264}k =1,$$ and keeping tally of the multiples in parenthesis, e.g. $$\small\text{Dividend}=\text{Divisor}(\text{Quotient})+\text{Remainder}:$$

\begin{align} \frac{\color{blue}{264}}{\color{magenta}{245}}=\color{tan}1{\small\text{, Rm }}\color{red}{19} \implies&\color{blue}{264}(1) = \color{magenta}{245}(\color{tan}1) + \color{red}{19} \\[2ex] \frac{\color{magenta}{245}}{\color{red}{19}}=\color{tan}{12} {\small\text{, Rm }}\color{purple}{17} \implies& \color{magenta}{245}(1) = \color{red}{19}(\color{tan}{12}) + \color{purple}{17} \\[2ex] \frac{\color{red}{19}}{\color{purple}{17}}=\color{tan}{1} {\small\text{, Rm }}\color{orange}{2} \implies& \color{red}{19}(1) = \color{purple}{17}(\color{tan}1) + \color{orange}2 \\[2ex] \frac{\color{purple}{17}}{\color{orange}{2}}=\color{tan}{8} {\small\text{, Rm }}\bf{1} \implies&\color{purple}{17}(1) = \color{orange}2(\color{tan}8) +\bf 1 \end{align}

Moving the remainders to the RHS...

\begin{align} \color{red}{19} &= 264(1) + 245(-1)\\ \color{purple}{17} &= 245(1) + 19(-12)\\ \color{orange}2 &= 19(1) + 17(-1) \\ \bf 1 &= 17(1) + 2(-8) \end{align}

Progressively linking these equations by substitution from the last one to the first, and distributing and rearranging terms...

\begin{align} \bf 1 &= 17(1) + \color{orange}2(-8)\\ &= 17(1) + \color{orange}{[19(1) + 17(-1)]}\bf{(-8)}\\ &= 17(1) + [19{\bf(-8)} + 17{\bf(8)}]\\ &= \color{purple}{17}(9) + 19(-8)\\ &= \color{purple}{[245(1) + 19(-12)]}{\bf(9)} + 19(-8)\\ &= [245{\bf(9)} + 19{\bf(-108)}] + 19(-8) \\ &= 245(9) + \color{red}{19}(-116) \\ &= 245(9) + \color{red}{[264(1) + 245(-1)]}{\bf(-116)}\\ &= 245(9) + [264{\bf(-116)} + 245{\bf(116)}]\\ &= \color{magenta}{245}(125) + \color{blue}{264}(-116) \end{align}

Comparing this last equation to $$(*),$$ the value of $$d=125.$$ And indeed, $$245 \times 125 \pmod {264} = 1.$$ The value $$k=-116$$ just spins the wheels on the clock face, and it is a single example of the general solution $$1=245\times 125+264k.$$

If we want to pass along the message "Hi", composed of the 8th and 9th letters of the alphabet, i.e. $$89,$$ we use the public key in the example, $$(e,n)=(245, 299),$$ and send the message $$89^{245} \pmod {299}=111,$$ which will be decrypted by the receiver by using the private key, $$(d,n)= (125,299),$$ exponentiating $$111^{125}\pmod{299}=89,$$ in other words, "Hi."