2
$\begingroup$

I have seen that there is a similar question here but none that really answers the question. I understand that if I choose the encryption exponent $e$ not coprime with $\varphi(n)$ then there is not a unique way to decrypt a message.

What I am wondering is what is the mathematical reason behind this? It seems to me that since $m^{(k \varphi(n)+1)} = m \bmod N$ and $d$ is defined as $(k\varphi(n)+1)/e$ then $d\cdot e$ is always going to be $k\varphi(n) +1$. What am I missing?

$\endgroup$
3
$\begingroup$

Textbook RSA encryption goes $c\gets m^e\bmod n$ with $n=p\,q$, and $p$ and $q$ primes (all quantities non-negative integers throughout). The question states

$d$ is defined as $(k\,\varphi(n)+1)/e$

Yes¹, for some integer $k$ such that this division yields an integer. And that can only be the case if $\gcd(e,\varphi(n))=1$. Proof: Let $r=\gcd(e,\varphi(n))$. This $r$ divides $e$ and $\varphi(n)$. Let $f=e/r$, and $z=\varphi(n)/e$, both integers. We have $d=(k\,\varphi(n)+1)/e$, thus $e\,d=k\,\varphi(n)+1$, thus $r\,f\,d-k\,r\,z=1$, thus $r\,(f\,d-r\,z)=1$. When the product of two integers is $1$, both are $\pm1$; thus $r=1$. Thus by construction of $r$, we must have $\gcd(e,\varphi(n))=1$.

The definition of $d$ in the question implies $\gcd(e,\varphi(n))=1$. But the question also asks:

If I choose the encryption exponent $e$ not coprime with $\varphi(n)$ then there is not a unique way to decrypt a message. What (..) is the mathematical reason behind this?

That's asking for a seldom given proof of: if a decryption of textbook RSA encryption can be consistently made, then $\gcd(e,\varphi(n))=1$ must hold. Here we go.


We want RSA decryption to be uniquely possible, the encryption transformation $m\mapsto m^e\bmod n$ must thus be injective over $[0,n)$, which we assume in the following. This implies three facts:

  1. $e\ne0$. Proof: otherwise, all messages $m$ in $[1,n)$ would encrypt to $c=1$. There are more than one such $m$, contradicting injectivity.
  2. $p\ne q$ or $e<2$. Proof: if otherwise, that is if $p=q$ and $e\ge2$, then all $m$ multiple of $p$ encrypt to $0$, since for all $i$ it holds $(i\,p)^e=i^e\,p^{e-2}\,p^2$, hence $(i\,p)^e$ is a multiple of $p^2$, hence $(i\,p)^e\bmod n=0$. There are more than one such $m$, contradicting injectivity.
  3. $\gcd(e,\varphi(n))=1$, which the question asks to prove.

If $e=1$, then $\gcd(e,\varphi(n))=1$ holds. Given fact (1.), we can restrict the proof of (3.) to $e\ge2$, and we do so in the following.

Given fact (2.), $\varphi(n)=(p-1)(q-1)$. Thus $$\begin{align} \gcd(e,\varphi(n))=1&\iff\gcd(e,(p-1)(q-1))=1\\ &\iff\gcd(e,p-1)=1\text{ and }\gcd(e,q-1)=1 \end{align}$$ Thus for the proof of (3.) it is enough that we prove $\gcd(e,p-1)=1$ (the same proof applies for $q$, giving the desired result). We do so in the following.

Given that $p$ is prime, the multiplicative group $\Bbb Z_p^*$ (that is the integers $[1,p)$ under multiplication modulo $p$) has $p-1$ elements. It is known to be a cyclic group, thus there exists a generator $g$ with $x\mapsto g^x\bmod p$ a bijection on $[1,p)$, with $p-1\mapsto 1$.

Let $r=\gcd(e,p-1)$. This $r$ divides $e$ and $p-1$. Let $f=e/r$, $s=(p-1)/r$, and $h=g^s\bmod n$. It holds $h^e={(g^s)}^e=g^{s\,e}=g^{f\,r\,s}=g^{(p-1)\,f}={(g^{p-1})}^f$. Hence $h^e\bmod p=1$.

Given fact (2.) and $p$ and $q$ prime, $p$ and $q$ are coprime. Thus by the Chineese Remainder Theorem there exists² $t\in[0,p\,q)$ with $t\bmod p=h$ and $t\bmod q=1$.

It follows that $t^e\bmod p=h^e\bmod p=1$, and $t^e\bmod q=1^e\bmod q=1$. Again by the CRT, it follows that $t^e\bmod n=1$.

It also holds $1^e\bmod n=1$. For RSA encryption $m\mapsto m^e\bmod n$ to be injective, we must thus have $t=1$, therefore $h=1$. Since $x\mapsto g^x\bmod p$ is a bijection on $[1,p)$, and transforms $x=p-1$ into $1$, and $s$ into $h=1$, it must hold $s=p-1$.

By construction $s=(p-1)/r$ and $r=\gcd(e,p-1)$, thus $\gcd(e,p-1)=1$, Q.E.D.


Note: for proper generation of $N$ the condition $p=q$ is extremely improbable, and even if it occurs it leads to vanishingly few $m$ which encryption could not be uniquely deciphered, which is why $p\ne q$ is sometime omitted in the definition of textbook RSA. However when $\gcd(e,\varphi(n))\ne1$, the proportion of $m$ which encryption could not be uniquely deciphered becomes sizable, which is why condition (3.) on $e$ or an equivalent is always required. An argument for this sizable proportion is that there are many generators $g$ leading to distinct $h$, and for each $h$ that we exhibited there are $q$ messages $t$ encrypting to the same $c$.


¹ A standard proof is that if $e\,d\equiv 1\pmod{\varphi(n)}$, then decryption per $m\gets c^d\bmod n$ works for most messages in $[0,m)$, and for all such messages when $n$ is squarefree. The converse does not hold.

² That $t$ is unique and could be computed as $\left((p^{-1}\bmod q)(h-1)\bmod q\right)\,p+1$.

| improve this answer | |
$\endgroup$

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.