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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cryptohack.gitbook.io/cryptobook/untitled/common-modulus-attack.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.