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