5
$\begingroup$

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)$?

$\endgroup$
  • $\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 '16 at 23:25
8
$\begingroup$

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

$\endgroup$
  • 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 '16 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 '16 at 14:49
  • 1
    $\begingroup$ @Biv Could you explain shortly in your words why this property is interesting? $\endgroup$ – Joey Mar 15 '16 at 7:34
3
$\begingroup$

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.

$\endgroup$
  • 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 '16 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 '16 at 14:46
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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