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$.
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.
d = {pow(x, e, n): x for x in range(128)}
d
{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.
''.join(chr(d[y]) for y in c)
'HELLO, WORLD!'