9
$\begingroup$

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?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
11
$\begingroup$

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

Improve this answer
$\endgroup$
11
  • $\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
    Commented Apr 15, 2012 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
    Commented Apr 15, 2012 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
    Commented Apr 15, 2012 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
    Commented Apr 16, 2012 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
    Commented Apr 18, 2012 at 14:13
14
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Apr 18, 2012 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 ≢ m_2\pmod p$, then ${m_1}^e ≢ {m_2}^e\pmod 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 ≢ m_2\pmod q$, then ${m_1}^e ≢ {m_2}^e\pmod q$. Now, if we combine these two statements using the Chinese Remainder Theorem, we get: if $\gcd(e,\operatorname{lcm}(p-1,q-1))=1$ and if $m_1 ≢ m_2 \pmod{p\,q}$, then ${m_1}^e ≢ {m_2}^e\pmod{p\,q}$. Take the converse of that statement, and that's the statement you're asking about. $\endgroup$
    – poncho
    Commented Apr 26, 2012 at 0:35

Your Answer

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

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