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

  • $\begingroup$ 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. $\endgroup$ – David Schwartz Apr 15 '12 at 10:50
  • $\begingroup$ @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. $\endgroup$ – Ashwin Apr 15 '12 at 11:26
  • $\begingroup$ @Ashwin: That is why you are supposed to use padding, such as OAEP or PKCS#1 v1.5. $\endgroup$ – Henrick Hellström Apr 15 '12 at 11:27
  • 1
    $\begingroup$ 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. $\endgroup$ – Henrick Hellström Apr 16 '12 at 8:55
  • 1
    $\begingroup$ @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. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – Ashwin Apr 18 '12 at 11:21
  • 2
    $\begingroup$ @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 $\endgroup$ – poncho Apr 26 '12 at 0:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.