# 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!'