Timeline for Can RSA encryption produce collisions?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 27, 2012 at 2:25 | vote | accept | Ashwin | ||
| Nov 21, 2012 at 15:36 | |||||
| Apr 27, 2012 at 2:25 | vote | accept | Ashwin | ||
| Apr 27, 2012 at 2:25 | |||||
| Apr 26, 2012 at 0:35 | comment | added | poncho | @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. | |
| Apr 18, 2012 at 11:21 | comment | added | Ashwin | 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. | |
| Apr 15, 2012 at 11:35 | history | answered | poncho | CC BY-SA 3.0 |