1. kirv
  2. notebooks

RSA in ECB mode

Suppose that the RSA public key $(n, e) = (2491, 1595)$ has been used to encrypt each individual character in a message $m$ (using their ASCII codes), giving the following ciphertext: $$ c = (111, 2474, 1302, 1302, 1587, 395, 224, 313, 1587, 1047, 1302, 1341, 980). $$ Determine the original message $m$ without factoring $n$.

In [1]:
n = 2491
e = 1595
c = [111, 2474, 1302, 1302, 1587, 395, 224, 313, 1587, 1047, 1302, 1341, 980]

Since there are only 128 ASCII characters, we can build a dictionary mapping encryptions to the corresponding codes.

In [3]:
d = {pow(x, e, n): x for x in range(128)}
In [4]:
d
Out[4]:
{0: 0,
 1: 1,
 1290: 2,
 404: 3,
 112: 4,
 932: 5,
 541: 6,
 1050: 7,
 2: 8,
 1301: 9,
 1618: 10,
 693: 11,
 410: 12,
 574: 13,
 1887: 14,
 387: 15,
 89: 16,
 568: 17,
 1847: 18,
 323: 19,
 2253: 20,
 730: 21,
 2192: 22,
 931: 23,
 808: 24,
 1756: 25,
 633: 26,
 3: 27,
 523: 28,
 2054: 29,
 1030: 30,
 193: 31,
 224: 32,
 980: 33,
 366: 34,
 2128: 35,
 1234: 36,
 1766: 37,
 673: 38,
 233: 39,
 1864: 40,
 1339: 41,
 102: 42,
 1721: 43,
 395: 44,
 1906: 45,
 328: 46,
 2162: 47,
 1082: 48,
 1478: 49,
 921: 50,
 300: 51,
 2013: 52,
 212: 53,
 1379: 54,
 707: 55,
 2100: 56,
 960: 57,
 1727: 58,
 2290: 59,
 997: 60,
 2122: 61,
 2361: 62,
 982: 63,
 4: 64,
 1894: 65,
 1263: 66,
 138: 67,
 1341: 68,
 2474: 69,
 38: 70,
 2218: 71,
 111: 72,
 398: 73,
 1366: 74,
 1980: 75,
 1302: 76,
 278: 77,
 1650: 78,
 1587: 79,
 745: 80,
 1212: 81,
 1047: 82,
 341: 83,
 2048: 84,
 1284: 85,
 609: 86,
 313: 87,
 1386: 88,
 2029: 89,
 123: 90,
 2369: 91,
 2141: 92,
 751: 93,
 1551: 94,
 2116: 95,
 820: 96,
 1720: 97,
 1005: 98,
 2342: 99,
 2374: 100,
 2460: 101,
 895: 102,
 126: 103,
 1148: 104,
 317: 105,
 1961: 106,
 1326: 107,
 336: 108,
 669: 109,
 324: 110,
 1038: 111,
 1283: 112,
 1686: 113,
 373: 114,
 824: 115,
 876: 116,
 1965: 117,
 2265: 118,
 1051: 119,
 774: 120,
 1977: 121,
 2262: 122,
 409: 123,
 1688: 124,
 5: 125,
 1352: 126,
 2108: 127}

We can now use the dictionary to decrypt each character.

In [5]:
''.join(chr(d[y]) for y in c)
Out[5]:
'HELLO, WORLD!'