# What is the proof that the RSA is collision-free?

We have the RSA function: $$c = m^e (mod n)$$. I would like to know the proof that there is not an $$m_1$$ and an $$m_2$$ message that produce the same $$c$$.

My thoughts:

We know that $$m \le n$$, so $$m_1 \ncong m_2 (mod n)$$. We also know that if $$a \cong b (mod n)$$, then $$a^k \cong b^k (mod n)$$. So if $$m_1 \ncong m_2 (mod n)$$ then $$m_1^e \ncong m_2^e (mod n)$$?

• The part of the reasoning that goes from the correct $a\equiv b\pmod n\implies a^k\equiv b^k\pmod n$ to the conclusion $m_1\not\equiv m_2\pmod n\implies{m_1}^e\not\equiv {m_2}^e\pmod n$ is of the form: $P\implies Q$ therefore $\bar P\implies\bar Q$. That line of reasoning is wrong. Counterexample to the conclusion thus obtained: $n=25$, $k=e=3$, $a=m_1=10$, $b=m_2=20$. Slightly different one: $n=35$, $k=e=3$, $a=m_1=2$, $b=m_2=22$. Yet with proper hypothesis, textbook RSA is collision-free. We have a closely related question.
– fgrieu
Mar 11, 2023 at 10:58
• In that kind of proof about RSA, notation is important. In cryptography, we tend to write $c\equiv m^e\pmod n$ ($c\equiv m^e\pmod n$) when we mean that $m^e-c$ is a multiple of $n$. The opening parenthesis right before$\bmod$denotes that$\bmod$is not an operator. We tend to write $c=m^e\bmod n$ ($c=m^e\bmod n$) when we mean that $c\in[0,n)$ and $c\equiv m^e\pmod n$. In this$\bmod$is an operator, similar to % in C except for precedence and what happens for negative arguments. Anything in-between, like $c=m^e\pmod n$, is ambiguous. Avoid $mod n$ at all cost.
– fgrieu
Mar 11, 2023 at 11:16
• Sorry, i'm not that familiar with Latex, and thank you for pointing me to the right direction. Mar 11, 2023 at 16:15
• Hints: you'll need a definition of RSA such that $n$ is the product of distinct primes, and such that if prime $p$ divides $n$ then $\gcd(e,p-1)=1$. My counterexamples can be because they violate these rules.
– fgrieu
Mar 11, 2023 at 20:35
• So if we prove the correctness of RSA (All encrypted M can be decrypted to M), then we prove the collision-freeness as well, because two encrypted message can not yield the same decrypted message, am I right? Mar 12, 2023 at 15:10