{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# RSA in ECB mode\n", "\n", "Suppose that the RSA public key \$(n, e) = (2491, 1595)\$\n", "has been used to encrypt each individual character in a message \$m\$ (using their ASCII codes),\n", "giving the following ciphertext:\n", "\$\$\n", "c = (111, 2474, 1302, 1302, 1587, 395, 224, 313, 1587, 1047, 1302, 1341, 980).\n", "\$\$\n", "Determine the original message \$m\$ without factoring \$n\$." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "n = 2491\n", "e = 1595\n", "c = [111, 2474, 1302, 1302, 1587, 395, 224, 313, 1587, 1047, 1302, 1341, 980]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Since there are only 128 ASCII characters, we can build a dictionary mapping encryptions to the corresponding codes." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "d = {pow(x, e, n): x for x in range(128)}" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{0: 0,\n", " 1: 1,\n", " 1290: 2,\n", " 404: 3,\n", " 112: 4,\n", " 932: 5,\n", " 541: 6,\n", " 1050: 7,\n", " 2: 8,\n", " 1301: 9,\n", " 1618: 10,\n", " 693: 11,\n", " 410: 12,\n", " 574: 13,\n", " 1887: 14,\n", " 387: 15,\n", " 89: 16,\n", " 568: 17,\n", " 1847: 18,\n", " 323: 19,\n", " 2253: 20,\n", " 730: 21,\n", " 2192: 22,\n", " 931: 23,\n", " 808: 24,\n", " 1756: 25,\n", " 633: 26,\n", " 3: 27,\n", " 523: 28,\n", " 2054: 29,\n", " 1030: 30,\n", " 193: 31,\n", " 224: 32,\n", " 980: 33,\n", " 366: 34,\n", " 2128: 35,\n", " 1234: 36,\n", " 1766: 37,\n", " 673: 38,\n", " 233: 39,\n", " 1864: 40,\n", " 1339: 41,\n", " 102: 42,\n", " 1721: 43,\n", " 395: 44,\n", " 1906: 45,\n", " 328: 46,\n", " 2162: 47,\n", " 1082: 48,\n", " 1478: 49,\n", " 921: 50,\n", " 300: 51,\n", " 2013: 52,\n", " 212: 53,\n", " 1379: 54,\n", " 707: 55,\n", " 2100: 56,\n", " 960: 57,\n", " 1727: 58,\n", " 2290: 59,\n", " 997: 60,\n", " 2122: 61,\n", " 2361: 62,\n", " 982: 63,\n", " 4: 64,\n", " 1894: 65,\n", " 1263: 66,\n", " 138: 67,\n", " 1341: 68,\n", " 2474: 69,\n", " 38: 70,\n", " 2218: 71,\n", " 111: 72,\n", " 398: 73,\n", " 1366: 74,\n", " 1980: 75,\n", " 1302: 76,\n", " 278: 77,\n", " 1650: 78,\n", " 1587: 79,\n", " 745: 80,\n", " 1212: 81,\n", " 1047: 82,\n", " 341: 83,\n", " 2048: 84,\n", " 1284: 85,\n", " 609: 86,\n", " 313: 87,\n", " 1386: 88,\n", " 2029: 89,\n", " 123: 90,\n", " 2369: 91,\n", " 2141: 92,\n", " 751: 93,\n", " 1551: 94,\n", " 2116: 95,\n", " 820: 96,\n", " 1720: 97,\n", " 1005: 98,\n", " 2342: 99,\n", " 2374: 100,\n", " 2460: 101,\n", " 895: 102,\n", " 126: 103,\n", " 1148: 104,\n", " 317: 105,\n", " 1961: 106,\n", " 1326: 107,\n", " 336: 108,\n", " 669: 109,\n", " 324: 110,\n", " 1038: 111,\n", " 1283: 112,\n", " 1686: 113,\n", " 373: 114,\n", " 824: 115,\n", " 876: 116,\n", " 1965: 117,\n", " 2265: 118,\n", " 1051: 119,\n", " 774: 120,\n", " 1977: 121,\n", " 2262: 122,\n", " 409: 123,\n", " 1688: 124,\n", " 5: 125,\n", " 1352: 126,\n", " 2108: 127}" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "d" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can now use the dictionary to decrypt each character." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'HELLO, WORLD!'" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "''.join(chr(d[y]) for y in c)" ] } ], "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 }