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

#!/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

#!/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())