What to do when the same message is encrypted twice with the same modulus but a different public key?

Imagine we have Alice and Bob. Alice sends the **SAME** message to Bob more than once using the same public key. The internet being the internet, a problem may happen; a bit is flipped, and the public key changed while the modulus stayed the same.

Let be the following:

`m`

the message in plaintext`e1`

the public key of the first ciphertext`c1`

the first ciphertext`e2`

the public key of the second ciphertext`c2`

the second ciphertext`n`

the modulus that is common to both ciphertexts

All of these but `m`

are essentially given to us.

Because we are going to need to calculate inverses for this attack, we must first make sure that these inverses exist in the first place:

$gcd(e_1, e_2) = 1
\newline
gcd(c_2, n) = 1$

We know that RSA goes as follows:

$c = m^e\ mod\ n$

From the conditions above we also know that $e1$ and $e2$ are co-prime. Thus using Bezout's Theorem we can get:

$xe_1 +ye_2 = gcd(e_1, e_2) = 1$

Using this, we can derive the original message $m$ :

*NB: all the calculations are done mod *$n$

$C_1^x * C_2^y = (m^{e_1})^x*(m^{e_2})^y
\newline
= m^{e_1x+e_2y}
\newline
= m^1 = m$

In general, Bezout's Theorem gives a pair of positive and negative numbers. We just need to adapt this equation a little to make it work for us. In this case, let's assume $y$ is the negative number:

$Let\ y = -a
\newline
C_2^y = C_2^{-a}
\newline
= (C_2^{-1})^a
\newline
= (C_2^{-1})^{-y}$

Now to truly recover the plaintext, we are actually doing:

$C_1^x \times (C_2^{-1})^{-y}\ mod\ n$

â€‹