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 how many integers 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 determining $e$ and $d$ in RSA?

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

  • 1
    $\begingroup$ Do you understand how $e$ and $d$ are generated in RSA key generation, and what relationship they need to satisfy? $\endgroup$
    – pg1989
    Mar 13, 2016 at 23:25
  • $\begingroup$ $e$ does not need to be smaller than $\varphi(N)$. Everything works correctly if it is larger. $\endgroup$ Jun 21, 2019 at 17:56

4 Answers 4


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

  • 2
    $\begingroup$ "... 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? $\endgroup$
    – Rimen
    Mar 14, 2016 at 13:44
  • 1
    $\begingroup$ What is interesting in $\phi(N)$ is not the number of coprime of $N$. But the property $\phi(N)=(p-1)(q-1)$. $\endgroup$
    – Biv
    Mar 14, 2016 at 14:49
  • 1
    $\begingroup$ @Biv Could you explain shortly in your words why this property is interesting? $\endgroup$
    – Joey
    Mar 15, 2016 at 7:34

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


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 emphasises the reason for 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 = 65537$. 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.

  • 1
    $\begingroup$ I don't get where k comes from? What does k stand for? Why does it need to be defined? $\endgroup$
    – Rimen
    Mar 14, 2016 at 14:03
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Biv
    Mar 14, 2016 at 14:46


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.