Coppersmith's attack on a small exponent

Suppose Alice sends the RSA encryptions of the same message $m$ three people. Each time, she uses the same public exponent $e = 3$, but different moduli $n_i$ ($i = 1, 2, 3$). An attacker can retrieve the message $m$ only from the public data (i.e., the moduli $n_i$, the public exponent $e$, and the encryptions $c_i = m^e \bmod{n_i}$ for $i = 1, 2, 3$).

Assuming $n_i$ ($i = 1, 2, 3$) are mutually coprime (otherwise they can be factored and a private key can then be retrieved), the following system of congruences has a unique solution modulo $n_1 n_2 n_3$:

\begin{align*} x &\equiv c_1 \pmod{n_1} \\ x &\equiv c_2 \pmod{n_2} \\ x &\equiv c_3 \pmod{n_3} \\ \end{align*}

Since $m < n_i$ ($i = 1, 2, 3$) and $x \equiv m^3 \pmod{n_1 n_2 n_3}$, it follows that we can retrieve $m$ as $\sqrt[3]{x \bmod{n_1 n_2 n_3}}$.

Example

Let $e = 3$, $n_1 = 55$, $n_2 = 391$, $n_3 = 1189$, $c_1 = 6$, $c_2 = 105$ and $c_3 = 1148$.

In [1]:
e = 3
n1, n2, n3 = 55, 391, 1189
c1, c2, c3 = 6, 105, 1148

We may express $x = c_1 + n_1 a = 6 + 55a$. Inserting it into the second congruence, we get \begin{alignat*}{2} 6 + 55a &\equiv 105 &&\pmod{391} \\ 55a &\equiv 99 &&\pmod{391} \\ 5a &\equiv 9 &&\pmod{391} \\ 5a &\equiv 400 &&\pmod{391} \\ a &\equiv 80 &&\pmod{391} \\ \end{alignat*}

In [2]:
a = (c2 - c1) / n1 % n2
a
Out[2]:
80

We may now express $a = 80 + 391b$, and therefore $x = c_1 + n_1(80 + n_2 b) = 4406 + 21505 b$.

In [3]:
x12 = c1 + n1 * a
x12
Out[3]:
4406
In [4]:
n12 = n1 * n2
n12
Out[4]:
21505

Inserting the above into the last congruence, we get \begin{alignat*}{2} 4406 + 21505b &\equiv 1148 &&\pmod{1189} \\ 103b &\equiv 309 &&\pmod{1189} \\ b &\equiv 3 &&\pmod{1189} \\ \end{alignat*}

In [5]:
b = (c3 - x12) / n12 % n3
b
Out[5]:
3

We thus express $b = 3 + 1189c$, and therefore $x = 4406 + 21505(3 + 1189c) = 68921 + n_1 n_2 n_3 c$. This gives us the congruence $x \equiv 68921 \pmod{n_1 n_2 n_3}$.

In [6]:
x = x12 + n12 * b
x
Out[6]:
68921

Let us now compute its cube root.

In [7]:
m = x ^ (1/e)
m
Out[7]:
41

We can verify that the decryption really encrypts to the given ciphertexts.

In [8]:
[m^e % n for n in (n1, n2, n3)]
Out[8]:
[6, 105, 1148]