3
$\begingroup$

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.

|improve this question
$\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$

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.

|improve this answer
$\endgroup$
  • 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

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.