Fireshell CTF 2019|Biggars - crypto-writeup-public

#FireshellCTF2019

E, C, N が与えられているRSAの問題

パラメータが長くて収まりきらなかったのでgistに貼った

https://gist.github.com/theoldmoon0602/b901a875f8a53b1ecdbcfbaeb9bf3d48

Nがあまりに大きすぎるので明らかに怪しい。とりあえずfactordb.comに投げようとしたけど大きすぎたので、ここではsagemathを使う。次のようなスクリプトを書いた。実行は sage factorize.pyとやればいい。

from sage.all import Integer, factor, euler_phi, inverse_mod

lines = open("params.txt").readlines()
n = Integer(lines[0].split("=")[1])
c = Integer(lines[1].split("=")[1])
e = Integer(lines[2].split("=")[1])

print(list(factor(n)))

すると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)]

Nが3個以上の素数の積として表される場合のRSA暗号はMulti Prime RSAと呼ばれる。このようなRSAも暗号として成立しており、ちゃんと標準化されている。

以下少しだけMulti Prime RSAを説明する。Nは2素数の積から任意の自然数に拡張される（要するに好きな数だけ素数をかけたものになるので）。 $N = \prod_i p_i^{k_i}$ （素数 $p_i$ が $k_i$ 個ある）と表すと、オイラーのトーシェント関数 $\phi(N) = \prod_i(p_i^{k_i}-p_i^{k_i-1})$ であり、適当な正整数eを持ってきて $d = modinv(e, \phi(N))$ は通常のRSAと変わらない。

ただし、このような場合dが非常に大きくなってしまい $c^d \mod n$ を求めるのは難しい（重い）のでこの処理はCRTで高速化する。中国人剰余定理は互いに素であるm個の数値 $n_i (i=1...m)$ について $x \equiv a_i \mod n_i$ というm元連立方程式の解 $0 \leq x < \prod_i n_i$ が一意に定まるという定理で、計算も容易らしい。

これを用いると、各 $n_i$ に対してeの逆数 $d_i = modinv(e, n_i)$ を求めて $x \equiv c^d_i \mod n_i$ の式をm個たててxを求めることができる。

結局こんな感じになった。

import gmpy
from params import n, e, c
from oldknife import *

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(as_str(m))

F#{b1g_m0d_1s_unbr34k4bl3_4m_1_r1gh7?}