# RSA: How to compute the number of possible plaintexts if $e$ is not coprime to $\varphi(n)$?

I'm studying for an exam next week, and there are two questions that me and my friend don't understand:

Question 1:
Let $p,q$ be big prime numbers and $n=pq$.
Let $e$ be a number between $1$ and $\varphi(n)$ such that $e\mid(p-1)$, $e\mid(q-1)$.
For a plaintext $M$, the ciphertext is $C=M^e \bmod n$.

How many different $M$s will be ciphered to the same $C$?
Edit: what is the maximum number of messages $M$ that will yield to the same $C$?
Why is the answer $e^2$?

Question 2:
Let $p,q$ be big prime numbers and $n=pq$.
Let $e$ be a number between $1$ and $\varphi(n)$ such that $\gcd(e,p-1)=a > 1$ and $\gcd(e,q-1)=1$.
For a plaintext $M$, the ciphertext is $C=M^e \bmod n$.

How may different $M$s will be ciphered to the same $C$?
Why is the answer $a$?

• You might want to clarify which set $M$ is chosen from. For example, if you allow $\gcd(M,n)\neq1$, a counterexample to the first question's claimed answer is given by $n=15$, $e=2$, $M=6$. – yyyyyyy Feb 7 '17 at 13:49
• Fixed the questions, for C=4, the following M yield to the same C: 13, 8,7,2 – CSE371 Feb 7 '17 at 14:05
• Since you're learning for an exam, the answers for both those questions is based on the number of roots or the order of subgroups (use Lagrange's theorem or the fundamental theorem of algebra), combined with the Chinese Remainder Theorem to assemble solutions mod $n$. – tylo Feb 7 '17 at 14:44

Both questions can be answered using the same kind of argument.

First, observe that in both cases we are really only interested in the number of $e$th roots of unity in $\mathbb Z/n$: Any $e$th root of unity can be multiplied to some $M$ without changing the value of $M^e\bmod n$, and two different $M$ with equal $M^e\bmod n$ differ by an $e$th root of unity. Thus we restrict our attention to the case $M=1$.

For succinctness, I will sometimes write only root for "$e$th root of unity".

The Chinese remainder theorem gives an isomorphism of rings $$\pi\colon\; \mathbb Z/n \cong \mathbb Z/p \times \mathbb Z/q \text.$$

The image of $x^e\bmod n$ under $\varphi$ is $(x^e\bmod p,x^e\bmod q)$. Some element $x\in\mathbb Z/n$ is a root if and only if both components of $\varphi(x)$ are roots in $\mathbb Z/p$ and $\mathbb Z/q$. In other words: Each root in $\mathbb Z/n$ "consists" of roots in $\mathbb Z/p$ and $\mathbb Z/q$, and vice-versa. Thus, if $\mathbb Z/p$ has $a$ roots and $\mathbb Z/q$ has $b$, the ring $\mathbb Z/n$ has $ab$ roots.

Now note that the order of the cyclic group $(\mathbb Z/p)^\ast$ is $p-1$, thus if $e$ divides $p-1$, there must be an element $r$ of multiplicative order $e$ in $\mathbb Z/p$. Its powers $r^1,r^2,\dots,r^{e-1}$ are nontrivial $e$th roots of unity in $\mathbb Z/p$, thus (including $1$) there are $e$ roots in $\mathbb Z/p$. There cannot be more than $e$ roots since $\mathbb Z/p$ is a field. Of course, the same holds for $q$.

Armed with that knowledge, let's tackle question 1: If $e$ divides both $p-1$ and $q-1$, there must exist $e$ different roots in both $\mathbb Z/p$ and $\mathbb Z/q$. Thus, by the above, there are $e^2$ different $e$th roots of unity in $\mathbb Z/n$.

As to question 2: Since $(\mathbb Z/q)^\ast$ has order $q-1$ and $\gcd(e,q-1)=1$, the map $x\mapsto x^e\bmod q$ is a permutation on $\mathbb Z/q$. In particular, there are no nontrivial $e$th roots of unity in $\mathbb Z/q$. Concerning $\mathbb Z/p$, note that the map $x\mapsto x^{e/a}\bmod p$ is a permutation since $e/a$ is coprime to $p-1$. Thus, $1=x^e=(x^a)^{e/a}$ in $\mathbb Z/p$ if and only if $x^a=1$. As $a\mid p-1$, we can apply the above results (with $a$ in place of $e$) to conclude that $\mathbb Z/p$ has $a$ roots, thus $\mathbb Z/n$ has $a\cdot 1=a$.

For arbitrary givens $$n$$, $$e$$, $$c$$ with $$e>0$$ and $$0\le c, we want to solve for $$m$$ with $$0\le m the equation $$c=m^e\bmod n$$. We assume $$n=p\,q$$ with $$p$$ and $$q$$ distinct primes as in standard RSA. All quantities are integers.

$$p$$ and $$q$$ are distinct primes, thus coprime, thus by the Chinese Remainder Theorem we can:

• Solve for $$0\le x the equation $$c\equiv x^e\pmod p\quad$$🄐
• Solve for $$0\le y the equation $$c\equiv x^e\,\pmod q\quad$$🄑
• Use each possible $$(x,y)$$ combination to get all $$m=(q^{-1}(x-y)\bmod p)\,q+y$$.

Note: Most actual implementations of RSA decryption follow these steps, because that requires several times less computational effort than computing $$m=c^d\bmod n$$ directly, and parallelizes better on top of that.

Each $$(x,y)$$ leads to a unique $$m$$, with $$0\le m. Thus the number of possible messages $$m$$ for a given ciphertext $$c$$ is $$u\,v$$, where $$u$$ [resp. $$v\,$$] is the number of solutions to 🄐 [resp. 🄑 ]. Depending on conditions about $$p$$, $$e$$, $$c$$ that we will detail, $$u$$ is one of $$\gcd(e,p-1)$$, $$1$$, or $$0$$ (and similar for $$v$$).

The 3×3 cases for $$(u,v)$$ reduce to at most 5 for the numbers $$u\,v$$ of solutions for $$m$$:

1. $$\;\gcd(e,p-1)\gcd(e,q-1)\quad$$ [when $$\gcd(c,n)=1\,$$].
2. $$\;\gcd(e,p-1)\quad$$ [when $$q$$ divides $$c$$; value can conflate with case 1]
3. $$\;\gcd(e,q-1)\quad$$ [when $$p$$ divides $$c$$; value can conflate with case 1]
4. $$\;1\quad$$ [when $$c=0$$; value can conflate with cases 1/2/3]
5. $$\;0\quad$$ [can occur only when $$c$$ is not obtained by actual encryption]

In normal RSA, the condition $$\gcd(e,\varphi(n))=1$$ implies $$u=v=1$$, therefore a single $$m$$ is possible for every $$c$$. Otherwise said $$\gcd(e,p-1)=1=\gcd(e,q-1)$$, cases 1/2/3/4 conflate to $$1$$, and the later case can't occur.

In this section we detail determining the number $$u$$ of distinct solutions for $$0\le x the equation $$c\equiv x^e\pmod p$$; and solving for $$x$$ in some cases.

If $$c\bmod p=0$$, then the only solution is $$x=0$$, and $$u=1$$.

There remains to handle $$c\bmod p\ne 0$$, and we assume that. Since $$p$$ is prime, $$\gcd(c,p)=1$$. Thus by Fermat's Little Theorem $$x^{p-1}\equiv1\pmod p$$. Thus $$x^e\equiv x^{e\bmod(p-1)}\pmod p$$.

If $$e\bmod(p-1)=0$$, then equation $$c\equiv x^e\pmod p$$ becomes $$c\equiv 1\pmod p$$. If that holds, there are $$p-1$$ solutions with $$1\le x; and $$\gcd(e,p-1)=p-1$$ thus $$u=\gcd(e,p-1)$$ (a case we'll meet later). Otherwise $$u=0$$ (that can't happen if $$c$$ was actually obtained by computing $$m^e\bmod n\,$$).

There remains to handle $$e\bmod(p-1)\ne0$$, and we assume that. Compute $$r=\gcd(p-1,e)$$, then $$f=e/r$$. Define the auxiliary unknown $$z=x^r\bmod p$$. The equation $$c\equiv x^e\pmod p$$ becomes $$z^f\equiv c\pmod{p-1}$$, with $$\gcd(f,p-1)=1$$. By the FLT that has (modulo $$p$$) a single solution $$z=c^{f^{-1}\bmod(p-1)}\bmod p$$.

When $$r=1$$, we have found the only solution $$x=z$$. That's the case in normal RSA. But in the question we want to handle $$\gcd(e,\varphi(n))>1$$, thus $$r>1$$ will hold while soving for 🄐 or/and 🄑

There remains to solve for $$0 the equation $$z=x^r\bmod p$$, where $$p$$, $$r$$ and $$\hat x$$ are known, $$p$$ is prime, $$r$$ divides $$p-1$$, it holds $$2\le r, and $$0<\hat x.

• if $$z^{(p-1)/r}\bmod p\ne1$$ then there is (per FLT) no solution, thus $$u=0$$.
• otherwise (without proof) there are $$r$$ distinct solutions, thus $$u=\gcd(e,p-1)$$

[To be expanded maybe: when $$\gcd(e,p-1)$$ is neither $$1$$ nor $$p-1$$, we have not told how to compute the solutions $$x$$ in the general case. Some of it is covered here].

• I believe that the answer you're trying to get to is, assuming $c$ is relatively prime to $pq$, then $c^e = m \bmod pq$ has either $\gcd( p-1, e ) \gcd( q-1, e )$ solutions or none. Complications that you've considered: what if $e$ is composite? What if both $p-1, q-1$ is not r.p. to $e$? – poncho Aug 27 at 18:16
• @poncho: Yes. I've added that, and the conditions. – fgrieu Aug 27 at 19:18