There is a problem i am trying to solve on RSA.
We have two ciphertexts which have been encrypted with different public exponents e, but share the same modulus N.
Assume that the c1,c2,e1,e2,N are known to us and m,p is unknown, where :
c1 = ciphertext 1 (We know its value)
c2 = ciphertext 2 (We know its value)
e1 = public exponent 1 (We know its value)
e2 = public exponent 2 (We know its value)
N = modulus (We know its value)
m = message we are trying to decrypt (Unknown)
p = one of two prime factors of N (Unknown)
If the ciphertext 1 was created from this equation :
c1 = (pow(p, e1, N) + m) % N
And ciphertext 2 was created from this equation :
c2 = (pow(p, e2, N) + m) % N
How can we find p in order to get q (both prime factors) and then decrypt the message ?
I tried subtracting the 2 equations to remove m and have the p as the only unknown in the equations and i got this :
c1-c2 ≡ pow(f,e1,N) - pow(f,e2,N)
Where pow(a,b,c) = (a^b) % c.
Also, the length of c1,c2,e1,e2 and N are the same.
I am stuck.
Best Answer
This seems to be only tangentially related to RSA.
$c_1-c_2$ will be congruent to $p^{e_1} - p^{e_2} \equiv p^{e_1} (p^{e_2-e_1} - 1)$ mod $N$, assuming that $e_2 > e_1$ (which we can without loss of generality).
So $c_1 - c_2$ is guaranteed to be divisible by $p$, and in the typical case, this means we can take $\gcd(c_1 - c_2, N)$ to extract $p$.
This only fails if by chance $q$ divides $p^{e_2 - e_1} - 1$ in which case the gcd will be equal to $pq=N$ instead of $p$. For the purposes of showing the scheme is insecure, that's enough since it can't depend on such rare coincidences for security.
Perhaps this knowledge of a congruence relation between $p$ and $q$ can be used to factor $N$ in the latter case, but I don't see one offhand and it's probably out of the question's scope. The proposed system is terribly insecure as capturing a single cleartext/ciphertext pair is enough to reliably reveal the factorization of $N$.