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)$?

  • 2
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Mar 11, 2023 at 10:58
  • 2
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Mar 11, 2023 at 11:16
  • $\begingroup$ Sorry, i'm not that familiar with Latex, and thank you for pointing me to the right direction. $\endgroup$ Mar 11, 2023 at 16:15
  • $\begingroup$ 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. $\endgroup$
    – fgrieu
    Mar 11, 2023 at 20:35
  • $\begingroup$ 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? $\endgroup$ Mar 12, 2023 at 15:10


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.