By Euler's theorem, if $\gcd(e,n) = 1$, then $e^{\varphi(n)} \equiv 1 \pmod n$. But why does RSA need to make sure that $\gcd(e,\varphi(n)) = 1$?


You want to be able to encrypt a message and decrypt it, that is translated to:

$m^{ed} \equiv m^1 \equiv m \pmod n$

But why does this work? Since $ed \equiv 1 \pmod{\varphi(n)}$

If $\gcd(e,d) \neq 1$ then $e$ and $d$ are not coprime then $ed \not \equiv 1 \pmod{\varphi(n)}$. So $e$ must be coprime with $\varphi(n)$ to have a modular multiplicative inverse.

Also $\gcd(e,n)=1$, since the public key is presented as $(e,n)$. Then you trivially can compute a factor of $n$ if $e$ is not coprime.

  • 1
    $\begingroup$ $ed \equiv 1 \pmod{\varphi(n)}$ is not necessary for $m^{ed} \equiv m^1 \equiv m \pmod n$ to hold for all $m$. Example: $p=5$, $q=11$, $n=55$, $e=3$, $d=7$, $\varphi(n)=40$, $ed\equiv21\not\equiv1\pmod{40}$. Hence the "since" is technically incorrect. $\endgroup$ – fgrieu Oct 25 '19 at 7:18
  • 2
    $\begingroup$ I think that a better argument would be to show that if $\gcd(e,\varphi(n))\ne1$, one can exhibit $m,m'$ with $0\le m<m'<n$ and $m^e\equiv (m')^e\bmod n$, hence reliable decryption would be impossible. $\endgroup$ – fgrieu Oct 25 '19 at 7:30
  • 2
    $\begingroup$ Also: $e$ and $d$ don't have to be coprime. If e.g. x is a square root of $1$ mod $\lambda(n)$, you could also use $e=d=x$. Of course it is quite insecure if it is known you chose it like that. But you still can uniquely decrypt. $\endgroup$ – tylo Oct 25 '19 at 7:44

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.