#!/usr/bin/env python
# coding: utf-8

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


# 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


# In[4]:


n12 = n1 * n2
n12


# 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


# 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


# Let us now compute its cube root.

# In[7]:


m = x ^ (1/e)
m


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

# In[8]:


[m^e % n for n in (n1, n2, n3)]