# Can RSA encryption produce collisions?

In RSA, a message is encrypted by $m^e \pmod N$. $N$ is the modulus, $m$ is the message and $e$ is the public exponent. (I know that $m$ should not be greater than $N$.)

My question is, can $m^e$ be greater than $N$ (obviously, before taking the modulus)?

In that case is there a possibility like $m_1^e=m_2^e \pmod N$, i.e. can we get a collision?

-

Yes, $m^e$ is in fact supposed to be larger than the public modulus $N$, or else it would be trivial for an attacker with knowledge of nothing but the cipher text and the public exponent to calculate $m$. If $m^e$ is less than $N$, then it is obviously equal to its residue $\bmod N$. Calculating roots is not hard; calculating the root of a residue $\bmod N$ is.

Regarding your second question: As Poncho wrote, as long as the RSA parameters are correctly selected, it is impossible that you will accidentally find two different messages $m_1$ and $m_2$, both greater than 0 and less than $N$, such that $m_1^e \pmod N = m_2^e \pmod N$, because it will only happen if $GCD(e,LCM(p-1,q-1)) \neq 1$.

-
Since factoring the modulus is so hard that for practical purposes it is impossible, finding two such messages must also be so hard that for practical purposes it is impossible. – David Schwartz Apr 15 '12 at 10:50
@Henrick Hellstrom : Take the case where e is only 3. And if your message is small m^e will be smaller than the large N. – Ashwin Apr 15 '12 at 11:26
@Ashwin: That is why you are supposed to use padding, such as OAEP or PKCS#1 v1.5. – Henrick Hellström Apr 15 '12 at 11:27
Unless my math is completely off, if $e|p-1$ and $m_1^e \equiv m_2^e \pmod N$, then $m_1 \equiv m_2 \pmod q$. As poncho wrote, however, this won't happen if $e$ is correctly chosen. – Henrick Hellström Apr 16 '12 at 8:55
@HenrickHellström: from the 'nits-r-us' department, the example $e=3$, $N=91$, $p=7$, $q=13$, $m_1=5$, $m_2=6$ shows $e|p-1$ and $m_1^e \equiv m_2^e (\bmod N)$ but $m_1 \neq m_2 (\bmod q)$. On the other hand, if you add the condition $gcd(e, q-1) = 1$, then your statement is true. – poncho Apr 18 '12 at 14:13

Correction to Henricks answer: collisions are impossible (unless someone did something wrong). That is, if:

• $e$ is a proper RSA exponent (that is, relatively prime to $p-1$ and $q-1$, where $p$ and $q$ are the factors of $N$), and:

• $m_1 \neq m_2 \mod N$ (that is, you're not trying to encrypt the same message twice),

Then we will always have $m_1^e \neq m_2^e \mod N$

This is rather implied by the fact that the RSA operation can be inverted using the decryption exponent; if two different messages collided, then that couldn't be inverted uniquely.

-
can, you atleast point me to the proof of what henrick hellstrom said - me1(modN)=me2(modN), because it will only happen if GCD(e,LCM(p−1,q−1))≠1. – Ashwin Apr 18 '12 at 11:21
@Ashwin: Well, an outline of a proof would look like: if $GCD(e, p-1)=1$, and if $m_1 \neq m_2 \mod p$, then $m_1^e \neq m_2^e \mod p$ (note: the proof of this relies on the primality of $p$). And, by symmetry, if $GCD(e, q-1)=1$, and if $m_1 \neq m_2 \mod q$, then $m_1^e \neq m_2^e \mod q$. Now, if we combine these two statements using the Chinese Remainder Theorem, we get: if $GCD(e, lcm(p-1, q-1))=1$ and if $m_1 \neq \m_2 \mod pq$, then $m_1^e \neq m_2^e \mod pq$. Take the converse of that statement, and that's the statement you're asking about – poncho Apr 26 '12 at 0:35