Help with RSA step

Question

There's one thing in RSA that haunts me. In books there's just a statement, that

$$ed \equiv 1 \bmod \varphi(n)$$

is taken from Euler's function somehow. And than we use it to get

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

I don't understand how we got $ed ≡ 1 \bmod \varphi(n)$. Could we take $ed ≡ 1 \bmod \varphi(n)$ somehow, if we have $m^{ed} ≡ m \bmod n$?

Answer 1

Contrary to what I understand the question asks to explain, we can NOT get $e\,d\equiv 1\pmod{\varphi(N)}$ from $m\equiv m^{e\,d}\pmod n$, even if we add that the later congruence holds for all $m$.

Proof by counterexample: $p=11$, $q=17$, $n=p\,q=187$, $\varphi(n)=(p-1)(q-1)=160$, $e=3$, $d=17$, $e\,d=81\not\equiv1\pmod{\varphi(n)}$. Yet $\forall m,\, m\equiv m^{e\,d}\pmod n$ (which can be verified exhaustively for integers $m$ from $0$ to $n-1$, and also follows fact 2 below).

---

Two related facts hold if $p$ and $q$ are distinct odd primes and $n=p\,q$ :

1.   $e\,d\equiv 1\pmod{\varphi(n)}\implies\forall m,\, m\equiv m^{e\,d}\pmod n$
2.   $e\,d\equiv 1\pmod{\lambda(n)}\iff\forall m,\, m\equiv m^{e\,d}\pmod n$

where $\varphi$ is the Euler totient, and $\lambda$ is the Carmichael function. They verify $\varphi(n)=(p-1)(q-1)$ and $\lambda(n)=\operatorname{lcm}(p-1,q-1)$. The later divides the former.

The left-to-right implication in facts 1 and 2 is proven in this answer. The right-to-left implication in fact 2 follows from a definition of $\lambda(n)$ as the smallest positive exponent $k$ such that $\forall m,\, m^k\equiv1\pmod n$. The first part of the present answer shows that equivalence does not hold in fact 1.

---

The reasons why it is often used $e\,d\equiv 1\pmod{\varphi(n)}$ in RSA are that

• $\varphi(n)$ is, by definition, the order of the group $\mathbb Z_n^*$ (that is, the number of elements in the set of integers $m$ with $0<m<n$ and $\gcd(m,n)=1$). It follows that $\forall m\in\mathbb Z_n^*,\, m^{\varphi(n)}\equiv1\pmod n$, and from that
  $e\,d\equiv 1\pmod{\varphi(n)}\implies\forall m\text{ with }\gcd(m,n)=1,\, m\equiv m^{e\,d}\pmod n$
  which is a simple proof of a large subset of fact 1 above, and one that works for all $n$ (there's not need to invoke that $n$ is the product of distinct primes).
• RSA was first described this way and with this proof in R.L. Rivest, A. Shamir, and L. Adleman's A Method for Obtaining Digital Signatures and Public-Key Cryptosystem.
• Using $\varphi(n)$ works perfectly fine in practice (that follows from fact 1), and avoids the slightly more complex calculation of $\lambda(n)$.
• For most choices of $p$ and $q$ following standard recommendations, using $\lambda(n)$ typically only leads to a slightly lower $d$, and a slight speedup in some implementations of the RSA private-key operation; and then not even always, and speed-optimized implementations turn out not to use $d$ at all anyway.
• Since $d$ is secret, using $\varphi(n)$ or $\lambda(n)$ causes no incompatibility issue at least as long as the private part of the key is not shared among several devices.

Answer 2

how did we get $ed \equiv 1 \bmod \phi(n)$?

For "textbook RSA", you choose secret primes $p$ and $q$, and from them, derive $N =pq$ and compute $\phi(N) = \phi(pq) = (p-1)(q-1)$. Now you choose $e$ such that $\gcd(e, \phi(N)) = 1$. Then you publish $(N,e)$ as your public exponent.

Once you have $e$, you use the extended Euclidean algorithm to compute the modular inverse $d \equiv e^{-1} \bmod \phi(N)$, or $ed \equiv 1 \bmod \phi(N)$.

If you select $e$ and $d$ this way, then the solution to $m^e = c \bmod N$ is $m = c^d \bmod N$.

The attacker will have access to $N$ and $e$, but they won't know $\phi(N) = (p-1)(q-1)$ because they don't know $p$ and $q$. This is because factoring $N$ into $pq$ is hard.

Another way of saying it: if the attacker doesn't know $\phi(N) = (p-1)(q-1) = N - (p+q) + 1$, then it's no easier for her to find out $\phi(N)$ than it is to figure out the secret primes $p$ and $q$.