I read this question a while back (In RSA, why is it important to choose e so that it is coprime to φ(n)?). I was wondering whether there is a proof that shows that a public key exponent e that is coprime with the totient of the modulus N will result in a unique answer when the cipher text is decrypted. Please help.
3
$\begingroup$
$\endgroup$
-
1$\begingroup$ A proof for what? $\endgroup$ – yyyyyyy Dec 13 '15 at 12:21
-
$\begingroup$ Are you asking for a proof, rather that an illustration by example as given in the answer to the linked question, of the fact: $$\gcd(e,\varphi(N))\ne1\implies\exists (x,y)\in\mathbb N^2,\;\;x\not\equiv y\pmod N,\;\;x^e\equiv y^e\pmod N$$all other things being as specified in RSA (like, $N$ is a square-free integer, or is it the product of two distinct primes)? $\endgroup$ – fgrieu Dec 13 '15 at 12:39
-
$\begingroup$ @fgrieu Yes, a 'formal' proof. $\endgroup$ – user9750060 Dec 14 '15 at 2:58
1
$\begingroup$
$\endgroup$
First, if $e$ is the public key exponent, then the private key exponent $d$ is the (unique) multiplicative inverse modulo $\phi(n)$, or alternatively $ed \equiv 1 \pmod{\phi(n)}$. The reason we want $d$ to have this property is because by Euler's theorem, which says $a^{\phi(n)} \equiv 1 \pmod{n}$ for essentially all values of $a$, so $(a^e)^d\equiv a^{ed} \equiv a \pmod{n}$ ensures we can always decrypt $a^e$ to $a$.
Now, how do we know $d$ is the unique multiplicative inverse of $e$? Because if there were another value of $d'$ such that $ed' \equiv 1 \pmod{\phi(n)}$, then $0 \equiv 1-1 \equiv (ed-ed') \equiv (d-d')e \equiv (d-d') \pmod{\phi(n)}$, where the last congruence holds because $\gcd(e,\phi(n))=1$. Thus, $d$ is unique.
Finally, if $\gcd(e,\phi(n)) \ne 1$, then $e$ does not have a multiplicative inverse mod $\phi(n)$. This is because, assuming $e^{-1}$ exists, then there exists some integer $k$ such that $k\phi(n) + ee^{-1} = 1$, which implies $\gcd(e,\phi(n)) = 1$.
In practice, $e$ not having a multiplicative inverse means that the sequence $a^e, a^{2e}, a^{3e}, \ldots$ may never attain the value $a$ modulo $n$.
As fgrieu points out, there are other values of $d$ that can serve as private key exponent (besides the multiplicative inverse of $e$) but we can always choose $d$ to be $e^{-1}$ and we are guaranteed that this choice will work with high probability.
-
1$\begingroup$ $d=e^{-1}\bmod\phi(N)$ is typically not the only working $d$ modulo $\phi(N)$. Counterexample: $N=55$, $\phi(N)=40$, $e=3$, $e^{-1}\bmod\phi(N)=27$. Notwithstanding, $d'=7$ is a perfectly fine private exponent, such that $(a^e)^{d'}\equiv a\pmod N$ for all $a$, even though $e\cdot d'\not\equiv1\pmod{\phi(N)}$. Things are not quite that simple! $\endgroup$ – fgrieu Dec 14 '15 at 9:54
-
$\begingroup$ The chinese remainder theorem guarantees that such alternative d exist that can serve as private key exponent, even though they are not multiplicative inverses mod $\phi$. That does not conflict with anything I have said...you can always choose $d$ to be the multiplicative inverse and euler's thm gives us that whp we can recover the message. What does not work there? $\endgroup$ – Joe Bebel Dec 14 '15 at 10:07
-
$\begingroup$ I think there is some confusion, because I added proof that the multiplicative inverse of e is unique. I added that for completeness only. The original question is completely answered in my first paragraph. $\endgroup$ – Joe Bebel Dec 14 '15 at 10:20
-
$\begingroup$ The question asks to show that $\gcd(e,\varphi(N))=1$ is required so that we can always decrypt. The answer does not do that. It proves that $\gcd(e,\varphi(N))=1$ is required so that we can use $d\equiv e^{-1}\pmod{\phi(N)}$, which allows to always decrypt. The answer's reasoning does not rule out that other $d$ allow to always decrypt; which turns out to be the case, with these other values of $d$ are used in RSA practice. $\endgroup$ – fgrieu Dec 14 '15 at 11:06
-
1$\begingroup$ @fgrieu: If that's what he's asking, then a related answer (with, a bit of work, does answer the question) is crypto.stackexchange.com/questions/31980/… $\endgroup$ – poncho Feb 12 '16 at 14:35
