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$?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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 ♦Commented Oct 25, 2019 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 ♦Commented Oct 25, 2019 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$– tyloCommented Oct 25, 2019 at 7:44