> For the complete documentation index, see [llms.txt](https://ret2basic.gitbook.io/ctfnote/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ret2basic.gitbook.io/ctfnote/crypto/rsa/multiple-ciphertexts.md).

# 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())
```