Common Modulus Attack

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:

The math behind the attack

We know that RSA goes as follows:

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

Using this, we can derive the original message :

NB: all the calculations are done mod

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 is the negative number:

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