Common Modulus Attack

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.

What we know

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.

Conditions of the attack

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

The math behind the attack

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