{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Coppersmith's attack on a small exponent\n",
    "\n",
    "Suppose Alice sends the RSA encryptions of the same message $m$ three people.\n",
    "Each time, she uses the same public exponent $e = 3$, but different moduli $n_i$ ($i = 1, 2, 3$).\n",
    "An attacker can retrieve the message $m$ only from the public data\n",
    "(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$).\n",
    "\n",
    "Assuming $n_i$ ($i = 1, 2, 3$) are mutually coprime\n",
    "(otherwise they can be factored and a private key can then be retrieved),\n",
    "the following system of congruences has a unique solution modulo $n_1 n_2 n_3$:\n",
    "\n",
    "\\begin{align*}\n",
    "x &\\equiv c_1 \\pmod{n_1} \\\\\n",
    "x &\\equiv c_2 \\pmod{n_2} \\\\\n",
    "x &\\equiv c_3 \\pmod{n_3} \\\\\n",
    "\\end{align*}\n",
    "\n",
    "Since $m < n_i$ ($i = 1, 2, 3$) and $x \\equiv m^3 \\pmod{n_1 n_2 n_3}$,\n",
    "it follows that we can retrieve $m$ as $\\sqrt[3]{x \\bmod{n_1 n_2 n_3}}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example\n",
    "\n",
    "Let $e = 3$, $n_1 = 55$, $n_2 = 391$, $n_3 = 1189$, $c_1 = 6$, $c_2 = 105$ and $c_3 = 1148$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "e = 3\n",
    "n1, n2, n3 = 55, 391, 1189\n",
    "c1, c2, c3 = 6, 105, 1148"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We may express $x = c_1 + n_1 a = 6 + 55a$.\n",
    "Inserting it into the second congruence, we get\n",
    "\\begin{alignat*}{2}\n",
    "6 + 55a &\\equiv 105 &&\\pmod{391} \\\\\n",
    "55a &\\equiv 99 &&\\pmod{391} \\\\\n",
    "5a &\\equiv 9 &&\\pmod{391} \\\\\n",
    "5a &\\equiv 400 &&\\pmod{391} \\\\\n",
    "a &\\equiv 80 &&\\pmod{391} \\\\\n",
    "\\end{alignat*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "80"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = (c2 - c1) / n1 % n2\n",
    "a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We may now express $a = 80 + 391b$, and therefore $x = c_1 + n_1(80 + n_2 b) = 4406 + 21505 b$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4406"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x12 = c1 + n1 * a\n",
    "x12"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "21505"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n12 = n1 * n2\n",
    "n12"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Inserting the above into the last congruence, we get\n",
    "\\begin{alignat*}{2}\n",
    "4406 + 21505b &\\equiv 1148 &&\\pmod{1189} \\\\\n",
    "103b &\\equiv 309 &&\\pmod{1189} \\\\\n",
    "b &\\equiv 3 &&\\pmod{1189} \\\\\n",
    "\\end{alignat*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b = (c3 - x12) / n12 % n3\n",
    "b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We thus express $b = 3 + 1189c$, and therefore $x = 4406 + 21505(3 + 1189c) = 68921 + n_1 n_2 n_3 c$.\n",
    "This gives us the congruence $x \\equiv 68921 \\pmod{n_1 n_2 n_3}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "68921"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = x12 + n12 * b\n",
    "x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us now compute its cube root."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "41"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m = x ^ (1/e)\n",
    "m"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can verify that the decryption really encrypts to the given ciphertexts."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[6, 105, 1148]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[m^e % n for n in (n1, n2, n3)]"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.2.rc2",
   "language": "sage",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}