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

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.

• You need $M_1 \not \equiv M_2 \pmod {n},$ otherwise $M_2 = M_1+ n$ would be a counter-example. The questions boils down to en.wikipedia.org/wiki/… with $d=e^{-1} \pmod {\varphi(n)}.$ Commented Sep 15, 2018 at 8:31
• @gammatester: You're right, I just found my previous proof is wrong because I implicitly assume $M_1,M_2\lt n$. Just for a check, if $M_1,M_2\lt n$ then $M_1=M_2,$ given that the result of my previous proof $M_1\equiv M_2(mod\ n)$ is correct? Commented Sep 15, 2018 at 8:34
• Yes, $M_1^e \equiv M_2^e \pmod n \Longrightarrow M_1\equiv (M_1^e)^d \equiv (M_2^e)^d = M_2 \pmod n$. The only non-trival part is when $\gcd(n,M_1) \ne 1$, see the related question math.stackexchange.com/questions/2702037/… Commented Sep 15, 2018 at 8:41

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".

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.

• Thank you sir, your proof is clean! (a little question: how to get $p,q\nmid M_2$ from $p,q\nmid M_1$? I only stuck at this part) Commented Oct 23, 2018 at 16:20
• @PostalModel, $M_1^e \equiv M_2^e$ (mod $n$) $\Rightarrow n \mid M_1^e - M_2^e$. This implies, $p \mid M_1^e - M_2^e$. Therefore, $p\mid M_2 \Rightarrow p \mid M_2^e \Rightarrow p \mid M_1^e \Rightarrow p \mid M_1$ (because $p$ is prime). Hence, $p \nmid M_1 \Rightarrow p \nmid M_2$. Similar argument holds for $q$. Commented Aug 6, 2020 at 16:19