Fireshell CTF 2019 Biggars writeup

gist.github.com

とにかく長大なパラメータを持つ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暗号は成立する。オイラーのφ関数を一般化して、 $N = \prod_i p_i^{k_i}$ と表されるとき、 $\phi(N) = \prod_i(p_i^{k_i}-p_i^{k_i-1})$ である。あとは $d$ を計算して復号すれば良い

ただしこの問題の場合、 $n$ が非常に大きいため、 $c^d \mod n$ の計算はそのままでは非常に時間がかかる。そこで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:]))

ふるつき

v('=')v かに

Fireshell CTF 2019 Biggars writeup