RSA: Prove/disprove that $M_1^e\equiv M_2^e\ (\textrm{mod}\ n),$ given $M_1\not=M_2$

Question

Given that $M_1\not=M_2, n=pq$ where $p,q$ are large primes and $\gcd(e,\varphi(n))=1$, how to prove/disprove that

$$M_1^e\equiv M_2^e\ (\textrm{mod}\ n)$$

is impossible? That is: I'm thinking about the case that two distinct messages $M_1,M_2$ has the same encrypted-text $C=M_1^e\mod n=M_2^e\mod n$.

I've tried a proof that using CRT and lead to a contradiction $M_1=M_2$ but it is a little bit complicated so I want to know is there any possible (simpler) alternatives.

Answer 1

I posted a proof here that RSA is a bijective map from $\mathbb{Z}_n$ to itself, provided that $(\phi(N),e) =1$, and where the message space is the set of classes modulo $N$, the modulus.

So if we assume (as we must) that we are working in that message set, the RSA mapping has an inverse (using the exponent $d$ as described) and is in particular injective.

I also use the CRT, but why not? It's a basic tool in number theory. It's not "complicated".

Answer 2

Note that $\phi(n)=\phi(p)\phi(q)$. Assume that the given is possible for some $M_1\not\equiv M_2 \pmod{n}$.

First suppose that $p,q\nmid M_1$. You will have that $p,q\nmid M_2$. Hence, using Fermat's theorem, you have $M_1^{p-1}\equiv 1\pmod{p}$, and $M_2^{p-1}\equiv 1\pmod{p}$. Now using $(e,\phi(n))=1$, we also deduce that $(e,p-1)=1$, hence there exists integers $a,b$ such that $ea+(p-1)b=1$. Using these integers, observe that, $$ M_1^{e}\equiv M_2^{e}\pmod{p} \quad\text{and}\quad M_1^{p-1}\equiv M_2^{p-1}\pmod{p}\implies M_1^{ae+b(p-1)}\equiv M_2^{ae+b(p-1)}\pmod{p}, $$ namely, $M_1\equiv M_2\pmod{p}$ ,and similarly, $M_1\equiv M_2\pmod{q}$, however since $n\nmid M_1-M_2$, this is a contradiction.

The other case can also be handled similarly.