# Multiple Ciphertexts

## Common Modulus

### Theory

**Common Modulus Attack** is used when the same plaintext $$m$$ is encrypted twice with the same modulus $$N$$ but distinct public exponent $$e\_1$$ and $$e\_2$$. In other words:

$$
c\_1 \equiv m^{e\_1} \mod N \\
c\_2 \equiv m^{e\_2} \mod N
$$

If $$e\_1$$ and $$e\_2$$ are **coprime**, then **Bezout's Identity** tells us that $$\exists \ a,b \in \mathbb{Z}$$ s.t.

$$
a \cdot e\_1 + b \cdot e\_2 = 1
$$

Here $$a$$ and $$b$$ can be solved using **extended Euclidean Algorithm**. Once we know $$a$$ and $$b$$, we could compute

$$
m \equiv {c\_1}^a + {c\_2}^b \mod N
$$

**Correctness:**

$$
{c\_1}^a + {c\_2}^b \equiv (m^{e\_1})^a \cdot (m^{e\_2})^b
\equiv m^{e\_1 \cdot a + e\_2 \cdot b}
\equiv m^1
\equiv m \mod N
$$

### Implementation

```python
#!/usr/bin/env python3
from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long
from Crypto.PublicKey import RSA
from sympy import gcdex
from sys import exit

#--------Data--------#

N = <N>
e1 = <e1>
e2 = <e2>
c1 = <c1>
c2 = <c2>

#--------Common modulus--------#

a, b, gcd = gcdex(e1, e2)
a = int(a)
b = int(b)

# Test if e1 and e2 are coprime
if gcd != 1:
    print("e1 and e2 must be coprime")
    exit()

m = (pow(c1, a, N) * pow(c2, b, N)) % N
flag = long_to_bytes(m)

print(flag)
```

## Hastad Broadcast Attack

### Theory

**Hastad Broadcast Attack** is used when the same plaintext $$m$$ is encrypted multiple ($$\geq 3$$) times with the same public exponents $$e$$ but distinct modulus $$N\_i$$. In other words:

$$
c\_1 \equiv m^{e} \mod N\_1 \\
c\_2 \equiv m^{e} \mod N\_2 \\
... \\
c\_n \equiv m^{e} \mod N\_n
$$

**Chinese Remainder Theorem** tells us the solution to the following equation exists:

$$
c\_i \equiv m^e \mod \prod\_{i=1}^{n} N\_i
$$

Denote this solution as $$M$$. Chinese Remainder Theorem also provides a method for computing $$M$$:

$$
M \equiv \sum\_{i=1}^{e} c\_i \cdot u\_i \cdot N\_i \mod N
$$

where $$N = \prod\_{i=1}^{n} N\_i$$. Note that the plaintext $$m < N\_i$$, hence $$m^e < \prod\_{i=1}^{n} N\_i = N$$. As a result, **taking** $$e$$**-th root of** $$M$$ **gives us the plaintext** $$m$$. No need to worry about modulo $$N$$ since $$m^e$$ is not large enough.

### Implementation

```python
#!/usr/bin/env python3
from Crypto.Util.number import inverse, long_to_bytes
from sympy import root

#--------Data--------#

e = 3

n1 = <n1>
n2 = <n2>
n3 = <n3>

c1 = <c1>
c2 = <c2>
c3 = <c3>

#--------Hastad broadcast attack--------#

N = n1 * n2 * n3
N1 = N // n1
N2 = N // n2
N3 = N // n3

u1 = inverse(N1, n1)
u2 = inverse(N2, n2)
u3 = inverse(N3, n3)

M = (c1*u1*N1 + c2*u2*N2 + c3*u3*N3) % N
m = root(M, e)

print(long_to_bytes(m).decode())
```


---

# 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://ret2basic.gitbook.io/ctfnote/crypto/rsa/multiple-ciphertexts.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.