# 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:

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