とにかく長大なパラメータを持つRSA。nは大きいが小さい素因数からなっていて、簡単に素因数分解できる。
>>> list(factor(n)) [(3, 1545), (7, 1626), (11, 1569), (13, 1552), (17, 1519), (19, 1673), (23, 1498), (29, 1667), (31, 1604), (37, 1542), (41, 1622), (43, 1525), (53, 1606), (59, 1531), (61, 1484), (67, 1631), (71, 1596), (73, 1495), (79, 1656), (83, 1658), (89, 1581), (97, 1592), (101, 1656), (103, 1487), (107, 1488), (109, 1577), (113, 1500), (127, 1514), (131, 1660), (137, 1610), (139, 1677), (149, 1637), (151, 1596), (157, 1656), (163, 1534), (167, 1627), (173, 1580), (179, 1646), (181, 1511), (191, 1651), (193, 1591), (197, 1562), (199, 1661), (211, 1539), (223, 1620), (227, 1492), (229, 1665), (233, 1654), (239, 1679), (241, 1620), (251, 1566), (257, 1622), (263, 1677), (269, 1551), (271, 1563), (277, 1507)]
3つ以上の素因数からなるRSAはMulti-prime RSAと言われる。この場合にもRSA暗号は成立する。オイラーのφ関数を一般化して、 と表されるとき、 である。あとはを計算して復号すれば良い
ただしこの問題の場合、が非常に大きいため、の計算はそのままでは非常に時間がかかる。そこでRSA-CRTの考え方を使い、中国剰余定理を用いてこの計算を高速化する。
import gmpy from params import n, e, c def chinese_remainder(ms, ns): assert(len(ms) == len(ns)) n = 1 for i in range(len(ms)): n = n * ns[i] r = 0 for i in range(len(ms)): p = n / ns[i] r += ms[i] * gmpy.divm(1, p, ns[i]) * p try: return long(r % n) except: return int(r % n) factors = [(3, 1545), (7, 1626), (11, 1569), (13, 1552), (17, 1519), (19, 1673), (23, 1498), (29, 1667), (31, 1604), (37, 1542), (41, 1622), (43, 1525), (53, 1606), (59, 1531), (61, 1484), (67, 1631), (71, 1596), (73, 1495), (79, 1656), (83, 1658), (89, 1581), (97, 1592), (101, 1656), (103, 1487), (107, 1488), (109, 1577), (113, 1500), (127, 1514), (131, 1660), (137, 1610), (139, 1677), (149, 1637), (151, 1596), (157, 1656), (163, 1534), (167, 1627), (173, 1580), (179, 1646), (181, 1511), (191, 1651), (193, 1591), (197, 1562), (199, 1661), (211, 1539), (223, 1620), (227, 1492), (229, 1665), (233, 1654), (239, 1679), (241, 1620), (251, 1566), (257, 1622), (263, 1677), (269, 1551), (271, 1563), (277, 1507)] ms = [] ns = [] for p, k in factors: n = pow(p, k) phi = pow(p, k) - pow(p, k - 1) d = gmpy.divm(1, e, phi) m = pow(c, d, n) ms.append(m) ns.append(n) m = chinese_remainder(ms, ns) print(bytes.fromhex(hex(m)[2:]))