3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.
$\endgroup$
  • 2
    $\begingroup$ I think this answer is only likely to add to the OP's confusion. $\endgroup$ – TonyK Jun 11 '17 at 20:30
  • 2
    $\begingroup$ @TonyK: The answer being accepted comforts me that I did not add to confusion. In too many RSA expositions, the condition $e\,d\equiv 1\pmod{\varphi(n)}$ falls out from nowhere; it is legitimate and sound to question that abuse of authority and ask: A) if that condition can be derived from $m^{ed}\equiv m\bmod n$ (the answer is no, first part of answer). B) if the reverse hold (yes, fact 1). C) if a similar, mathematically more satisfying relation could be derived (yes, fact 2). D) why the teacher and many implementations use $e\,d\equiv 1\pmod{\varphi(n)}$ (third part). $\endgroup$ – fgrieu Jun 11 '17 at 20:53
  • $\begingroup$ @Tonyk: and from the OP's next question, my attempt at guessing what the OP wanted (stated in the first paragraph of my answer) might have been right. $\endgroup$ – fgrieu Jun 11 '17 at 21:24
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Just a small hint: \bmod tends to be shorter than \text{ mod }. \pmod{m} will also add parenthesis around the modulus. $\endgroup$ – SEJPM Jun 11 '17 at 18:35
  • 1
    $\begingroup$ You also may want to use \greek-letter-name like \phi or \Phi or \varphi ($\phi,\Phi,\varphi$) and \equiv ($\equiv$). $\endgroup$ – SEJPM Jun 11 '17 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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