Where does the $\varphi(n)$ part of RSA come from?

Question

$e d \equiv 1 \pmod{\varphi(n)}$

Where does the $\varphi(n)$ part come from? How did the inventors of RSA arrive at $\varphi(n)$?

Answer 1

$\phi(n)$ is the order of the multiplicative group of the numbers in $\mathbb{Z}_n$. $\phi$ is known as Euler's totient function. A consequence Lagrange's theorem is that any element of a group, raised to the order of the group is equal to the identity element.

So, using $\phi(n)$ ensures that decryption works. Since $ed\equiv 1\bmod{\phi(n)}$, we can say that $ed-1\equiv\phi(n)$ or $ed\equiv\phi(n)+1$.

So if we look at $m^{ed}\bmod{n}$ well that is just the same as $m^{\phi(n)+1}\bmod{n}$ which is the same as $m^{\phi(n)}m^1\bmod{n}$. But since $\phi(n)$ is the order of the group, we know that $m^{\phi(n)}\equiv 1$ so we have $m^{\phi(n)}m^1\equiv 1m^1\equiv m\bmod{n}$. This proves that decryption works and we were only able to prove it since we chose $d$ accordingly.

If we didn't use $\phi(n)$ the mathematics wouldn't necessarily^* work out and decryption would not be guaranteed to work. So, the designers of RSA used $\phi(n)$ out of necessity.

*See the comment by fgrieu. Any multiple of $LCM(p-1,q-1)$ would work.

Answer 2

Where does the $\phi(n)$ part come from?

Well, the actual requirement is that, if $n = pq$ and both $p$ and $q$ are prime, we have:

$de \equiv 1 \mod p-1$

$de \equiv 1 \mod q-1$

The first ensures that RSA encryption, followed by RSA decryption, will obtain the original value modulo $p$.

The second ensures that RSA encryption, followed by RSA decryption, will obtain the original value modulo $q$.

When both are true, then RSA encryption, followed by RSA encryption, will obtain the original value modulo $lcm(p,q) = n$

And, if $de \equiv 1 \mod \phi(n)$, that will ensure that both of the above are true.

How did the inventors of RSA arrive at $\phi(n)$?

Perhaps they knew number theory?

Can't it be any positive integer coprime with $e$?

No, $d$ and $e$ must satisfy the above two conditions; a $d$ picked with an arbitrary positive integer coprime with $e$ is unlikely to.

Answer 3

(I answered other question first when wanted to answer this one. But they are similar though.)

So, it's better to view $ed \equiv 1 \pmod{\varphi (N)}$ as $ed=1 + k\varphi (N)$, then when we exponent message as $m^{ed}$ it becomes $m^{1 + k\varphi (N)}$, where $k\varphi (N)$ part strips out because of Euler's theorem $a^{\varphi(n)} \equiv 1 \pmod {n}$, so we get $\space m(m^{\varphi (N)})^k \equiv m$.

Other (maybe more intuitive) way to look at this is: $\varphi(n)$ is the order (size) of cyclic multiplicative group $\mathbb{Z}_n^*$ with the order of its generator being the same. So while group elements values are $\pmod{n}$, values of exponents are $\pmod{\varphi(n)}$. (Actually it is $\lambda(n)$, but $\varphi(n)$ is multiply of it.) So, to get message back we need to neutralize exponent by turning it into $1$, and to do that we should multiply $e$ to $e^{-1}$ (exponentiating message by $e^{-1}$), and to get the value of $e^{-1}$ we need to know order of the group, which is $\varphi(n)$. And to know this we need to know factorization of $n$ into $p\cdot q$, which finally gives $\varphi(n) = (p-1)(q-1)$ and then $e^{-1}$ is calculated using Extended Euclidean Algorithm.

Answer 4

We want $e$ to be a coprime to $\varphi(N)$ and not coprime to $N$ for the following reason:

• The RSA function is (the popular notation though): $c=[m^e\mod N]$.
• To inverse that function we need $d$ and $e$ such that $(m^e)^d=m^{ed}=m\mod N$ but $e$ and $d$ are coprime to $N$ or $\varphi(N)$?
• Note that $m^{\varphi(N)}=1$ because $Z^*_N$ is abelian. So $m^i=m^{[i\mod \varphi(N)]}$ because we have $\varphi(N)$ elements in $Z^*_N$.
• Thus, in the exponent we use $\mod \varphi(N)$ and for the equation $m^{ed}=m$ to be true we need that $ed$ to be equal to $1\mod \varphi(N)$.