{ "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 }