SECCON CTF 2021 Writeup

Sun Dec 12 2021

    12/11-12 で開催していた SECCON CTF 2021 にチーム WreckTheLine で参加しました。結果は 14th/506 (得点のあるチームのみカウント) でした。

    自分は Crypto に集中して取り組みました。どの Crypto 問もシンプルだけど非自明な感じがあって好きでした。 ところで終了後の solves 数を改めて見ると、自分の解いた感覚の難易度と solves 数が結構違くて🤔 なんかシンプルな解法の見落としがあるのかな… (個人の感想としての難易度は難しいほうから oOoOoO > CCC > cerberus > Sign Wars > XXX > pppp でした)

    以下、 Crypto の問題について writeup をまとめます。

    Crypto

    Sign Wars

    8 solves

    challenge.sage
    from Crypto.Util.number import bytes_to_long, long_to_bytes
    from Crypto.Util.Padding import pad
    import random
    from secret import msg1, msg2, flag
    
    flag = pad(flag, 96)
    flag1 = flag[:48]
    flag2 = flag[48:]
    
    # P-384 Curve
    p = 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319
    a = -3
    b = 27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575
    curve = EllipticCurve(GF(p), [a, b])
    order = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643
    Z_n = GF(order)
    gx = 26247035095799689268623156744566981891852923491109213387815615900925518854738050089022388053975719786650872476732087
    gy = 8325710961489029985546751289520108179287853048861315594709205902480503199884419224438643760392947333078086511627871
    G = curve(gx, gy)
    
    for b in msg1:
        assert b >= 0x20 and b <= 0x7f
    z1 = bytes_to_long(msg1)
    assert z1 < 2^128
    
    for b in msg2:
        assert b >= 0x20 and b <= 0x7f
    z2 = bytes_to_long(msg2)
    assert z2 < 2^384
    
    # prequel trilogy
    def sign_prequel():
        d = bytes_to_long(flag1)
        sigs = []
        for _ in range(80):
            # normal ECDSA. all bits of k are unknown.
            k1 = random.getrandbits(128)
            k2 = z1
            k3 = random.getrandbits(128)
            k = (k3 << 256) + (k2 << 128) + k1
            kG = k*G
            r, _ = kG.xy()
            r = Z_n(r)
            k = Z_n(k)
            s = (z1 + r*d) / k
            sigs.append((r,s))
    
        return sigs
    
    # original trilogy
    def sign_original():
        d = bytes_to_long(flag2)
        sigs = []
        for _ in range(3):
            # normal ECDSA
            k = random.getrandbits(384)
            kG = k*G
            r, _ = kG.xy()
            r = Z_n(r)
            k = Z_n(k)
            s = (z2 + r*d) / k
            sigs.append((r,s))
    
        return sigs
    
    
    def sign():
        sigs1 = sign_prequel()
        print(sigs1)
        sigs2 = sign_original()
        print(sigs2)
    
    
    if __name__ == "__main__":
        sign()

    ECDSA の鍵としてフラグの前半部 (sign_prequel) と後半部 (sign_original) が使われています。前半部→後半部とフラグを求めていきます。

    sign_prequel ii 番目の署名について、k12256+k3=z1(si12128)+risi1dmodNk_1 2^{256} + k_3 = z_1 (s_i^{-1} - 2^{128}) + r_i s_i^{-1} d \mod N という式が成り立ちます。 k1,k3k_1, k_3 は128 bitの乱数です。署名は80個得られています。

    この式の両辺にある定数をかけることで左辺を小さい値にすることができれば、 Hidden Number Problem (HNP) として LLL で dd を求めることができます。まずはこのような定数を探しました。ソルバーとして rkm-san の実装 を使いました。

    # [x, k1, k2] mat
    mat = matrix(ZZ, 3, 3)
    mat[0, 0] = 2**256
    mat[1, 0] = -order
    mat[0, 1]
    mat[2, 1] = -order
    mat[0, 2] = 1
    lb = [0, 0, 0]
    ub = [2**190] * 3
    res = solve(mat, lb, ub)
    x = int(res[2][0])

    ↑で求めた xx を両辺にかけることで、左辺は 2190+1282^{190+128} 程度の大きさになります。あとは HNP を解きます。

    # [z1, d, l1, l2, ...] mat
    mat = matrix(ZZ, 82, 82)
    for i in range(80):
        r, s = sigs1[i]
        mat[0, i] = (pow(s, -1, order) - 2**128) * x
        mat[1, i] = r * pow(s, -1, order) * x
        mat[i+2, i] = -order
    mat[0, 80] = 1
    mat[1, 81] = 1
    lb = [0] * 82
    ub = [2**(190+128)] * 80 + [2**128, 2**(48*8)]
    res = solve(mat, lb, ub)
    z1 = int(res[2][0])
    d1 = int(res[2][1])

    これで前半部のフラグ (d1) が求まりました。

    sign_original ECDSA の部分を見ると署名は3個しかなく、kkの乱数も384 bitで生成しているので、前半の手法を使うことができません。普通だったらこの条件で dd を求めることはできません。

    というわけで前半→後半と別れている意味を考えます。乱数生成に注目すると、前半の時点で 128×2×80=20480128 \times 2 \times 80 = 20480bits 分が getrandbits で生成されています。これは32 bit整数640個分に相当します。 getrandbits は Mersenne Twister を使用していますが、この乱数生成方法は32 bit整数が624個がわかっているとき後続の乱数が再現されます。つまり今回の問題のケースでは、後半部分の kk の値を乱数生成の観点からリークさせることができます。 kk がわかれば当然 dd も求まります。

    rands = []
    for i in range(80):
        r, s = sigs1[i]
        k = int((z1 * pow(s, -1, order) + r * pow(s, -1, order) * d1) % order)
        rands.append(k % 2**128)
        k = k // 2**256
        assert k < 2**128
        rands.append(k)
    
    rands32 = []
    for rand in rands:
        for i in range(4):
            rands32.append(int(rand % 2**32))
            rand = rand // 2**32
    
    
    # https://inaz2.hatenablog.com/entry/2016/03/07/194147
    def untemper(x):
        x = unBitshiftRightXor(x, 18)
        x = unBitshiftLeftXor(x, 15, 0xefc60000)
        x = unBitshiftLeftXor(x, 7, 0x9d2c5680)
        x = unBitshiftRightXor(x, 11)
        return x
    
    def unBitshiftRightXor(x, shift):
        i = 1
        y = x
        while i * shift < 32:
            z = y >> shift
            y = x ^^ z
            i += 1
        return y
    
    def unBitshiftLeftXor(x, shift, mask):
        i = 1
        y = x
        while i * shift < 32:
            z = y << shift
            y = x ^^ (z & mask)
            i += 1
        return y
    
    mt_state = tuple([int(untemper(x)) for x in rands32[:624]] + [int(624)])
    random.setstate((int(3), mt_state, None))
    for _ in range(640 - 624):
        random.getrandbits(32)
    
    k1 = random.getrandbits(384)
    k2 = random.getrandbits(384)
    
    kG1 = k1*G
    kG2 = k2*G
    r1, s1 = sigs2[0]
    r2, s2 = sigs2[1]
    assert kG1.xy()[0] == r1
    assert kG2.xy()[0] == r2
    
    d2 = int((s1 * k1 - s2 * k2) * pow(r1 - r2, -1, order))
    long_to_bytes(d1) + long_to_bytes(d2)

    SECCON{New_STARWARS_Spin-Off_The_Book_Of_Boba_Fett_Will_Premiere_On_December_29-107c360aab}

    XXX

    14 solves

    task.sage
    import os
    
    flag = os.getenv("FLAG", "fake{fakeflag_blahblah}")
    x = int.from_bytes(flag.encode(), "big")
    
    p = random_prime(1 << int(x.bit_length() * 2.5))
    Fp = GF(p)
    
    params = []
    while len(params) != 6:
        try:
            y = randint(2, x)
            a = randint(2, p-1)
            b = (y^2 - (x^3 + a*x)) % p
    
            EC = EllipticCurve(Fp, [a, b])
            EC(x, y)
    
            params.append([a, b])
        except ValueError:
            pass
    
    print(p)
    print(params)

    フラグの値を xx をしたとき、ある yy をランダムに生成し、 (x,y)(x, y) が楕円曲線 y2=x3+ax+by^2 = x^3 + ax + b 上に乗るような (a,b)(a, b) がランダムに生成されます。 (a,b)(a, b) が6種類与えられています。

    ii 番目の楕円曲線を y2=x3+aix+biy^2 = x^3 + a_ix + b_i とおきます。 ii 番目と jj 番目の式の差を考えると、 yi2yj2=(aiaj)x+(bibj)y_i^2 - y_j^2 = (a_i - a_j)x + (b_i - b_j) となります。ここで各項のbit数を見てみると、左辺が右辺の各項に対して小さいことがわかります。そのため、 LLL を使って xx が求められそうです。

    solve.py
    from itertools import combinations
    from Crypto.Util.number import long_to_bytes
    
    
    mat = matrix(ZZ, 17, 17)
    for k, (i, j) in enumerate(combinations(range(6), 2)):
        ai, bi = params[i]
        aj, bj = params[j]
        mat[0, k] = ai - aj
        mat[1, k] = bi - bj
        mat[k+2, k] = -p
    mat[0, 15] = 1
    mat[1, 16] = p
    res = mat.LLL()
    C = mat.solve_left(res)
    
    for c in C:
        print(long_to_bytes(abs(round(c[0]))))

    SECCON{9dd4e461268c8034f5c8564e155c67a6}

    cerberus

    16 solves

    problem.py
    import base64
    from Crypto.Cipher import AES
    from Crypto.Random import get_random_bytes
    from Crypto.Util.Padding import pad, unpad
    from Crypto.Util.strxor import strxor
    from flag import flag
    import signal
    
    key = get_random_bytes(16)
    block_size = 16
    
    # encrypt by AES-PCBC
    # https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Propagating_cipher_block_chaining_(PCBC)
    def encrypt(m):
        cipher = AES.new(key, AES.MODE_ECB)  # MODE_PCBC is not FOUND :sob: :sob:
        m = pad(m, 16)
        m = [m[i : i + block_size] for i in range(0, len(m), block_size)]
    
        iv = get_random_bytes(16)
    
        c = []
        prev = iv
        for m_block in m:
            c.append(cipher.encrypt(strxor(m_block, prev)))
            prev = strxor(c[-1], m_block)
    
        return iv, b"".join(c)
    
    
    # decrypt by AES-PCBC
    # https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Propagating_cipher_block_chaining_(PCBC)
    def decrypt(iv, c):
        cipher = AES.new(key, AES.MODE_ECB)  # MODE_PCBC is not FOUND :sob: :sob:
        c = [c[i : i + block_size] for i in range(0, len(c), block_size)]
    
        m = []
        prev = iv
        for c_block in c:
            m.append(strxor(prev, cipher.decrypt(c_block)))
            prev = strxor(m[-1], c_block)
    
        return b"".join(m)
    
    
    # The flag is padded with 16 bytes prefix
    # flag = padding (16 bytes) + "SECCON{..."
    signal.alarm(3600)
    ref_iv, ref_c = encrypt(flag)
    print("I teach you a spell! repeat after me!")
    print(base64.b64encode(ref_iv + ref_c).decode("utf-8"))
    
    while True:
        c = base64.b64decode(input("spell:"))
        iv = c[:16]
        c = c[16:]
    
        if not c.startswith(ref_c):
            print("Grrrrrrr!!!!")
            continue
    
        m = decrypt(iv, c)
    
        try:
            unpad(m, block_size)
        except:
            print("little different :(")
            continue
    
        print("Great :)")

    AES の PCBC モード を使った Padding Oracle Attack 問題。 PCBC モード初めて知った… 少々困る制約として、復号してもらう暗号の前半部分は、フラグを暗号化したものである必要があります。 フラグの暗号文が64bytesなことから4ブロックあることがわかります。

    上記リンクの復号スキームの画像とにらめっこをしているとすぐわかることですが、 IV に対して何らかの値で xor をとると、復号結果の各ブロックそれぞれに対してその値の xor が加えられます。 この特徴を使うことで暗号文の最後のブロックに対して Padding Oracle Attack が適用でき、復号することができます。

    よくある Padding Oracle Attack の問題では、最後のブロックを一つ求めては削っていくことで全ブロックの復号ができます。しかしこの問題では送信する暗号の前半部がフラグの暗号と一致している必要があり、最後のブロックを削るということができません。ひと工夫必要です。

    今、 C0C1C2C3C0C_0 || C_1 || C_2 || C_3 || C_0ref_iv を使って復号してもらうことを考えます。最後のブロックの復号結果は P4=Deck(C0)(C3P3)P_4 = \mathrm{Dec}_k(C_0) \oplus (C_3 \oplus P_3) となります。 P0=IVDeck(C0)P_0 = \mathrm{IV} \oplus \mathrm{Dec}_k(C_0) であることを使うと P4=P0IVC3P3P_4 = P_0 \oplus \mathrm{IV} \oplus C_3 \oplus P_3 となります。ここから最後のブロックの復号結果が P0P_0 と同じになるための iv を求めることができ、その状態から Padding Oracle Attack を使って P0P_0 を求められます。 これを繰り返すことで全てのブロックの復号結果をリークできます。

    solve.py
    from pwn import remote
    
    io = remote("cerberus.quals.seccon.jp", 8080)
    _ = io.recvline()
    c = b64decode(io.recvline().strip())
    ref_iv = c[:16]
    ref_c = c[16:]
    
    
    def try_decrypt(iv, c):
        io.sendlineafter(b"spell:", b64encode(iv + c))
        ret = io.recvline().strip().decode()
        if "little" in ret:
            return False
        elif "Great" in ret:
            return True
        else:
            io.close()
            raise ValueError
    
    
    dec = b""
    iv = ref_iv
    for idx in range(16)[::-1]:
        print(idx)
        for i in range(256):
            tmp_iv = iv[:idx] + long_to_bytes(iv[idx] ^ i) + iv[idx+1:]
            if (idx == 15 and i == 0) or not try_decrypt(tmp_iv, ref_c):
                continue
            dec = long_to_bytes((16 - idx) ^ i) + dec
            print(dec)
            iv = iv[:idx] + long_to_bytes(iv[idx] ^ i) + iv[idx+1:]
            iv = iv[:idx] + xor(iv[idx:], long_to_bytes(16-idx), long_to_bytes(16-idx+1))
            break
    print(dec)
    dec3 = dec
    iv = xor(iv, b"\x11", ref_c[-16:], ref_iv)
    dec = b""
    for idx in range(16)[::-1]:
        print(idx)
        for i in range(256):
            tmp_iv = iv[:idx] + long_to_bytes(iv[idx] ^ i) + iv[idx+1:]
            if (idx == 15 and i == 0) or not try_decrypt(tmp_iv, ref_c+ref_c[:16]):
                continue
            dec = long_to_bytes((16 - idx) ^ i) + dec
            print(dec)
            iv = iv[:idx] + long_to_bytes(iv[idx] ^ i) + iv[idx+1:]
            iv = iv[:idx] + xor(iv[idx:], long_to_bytes(16-idx), long_to_bytes(16-idx+1))
            break
    print(dec)
    dec0 = dec
    iv = xor(iv, b"\x11", ref_c[:16], ref_c[:16], dec)
    dec = b""
    for idx in range(16)[::-1]:
        print(idx)
        for i in range(256):
            tmp_iv = iv[:idx] + long_to_bytes(iv[idx] ^ i) + iv[idx+1:]
            if (idx == 15 and i == 0) or not try_decrypt(tmp_iv, ref_c+ref_c[:32]):
                continue
            dec = long_to_bytes((16 - idx) ^ i) + dec
            print(dec)
            iv = iv[:idx] + long_to_bytes(iv[idx] ^ i) + iv[idx+1:]
            iv = iv[:idx] + xor(iv[idx:], long_to_bytes(16-idx), long_to_bytes(16-idx+1))
            break
    print(dec)
    dec1 = dec
    iv = xor(iv, b"\x11", ref_c[16:32], ref_c[16:32], dec)
    dec = b""
    for idx in range(16)[::-1]:
        print(idx)
        for i in range(256):
            tmp_iv = iv[:idx] + long_to_bytes(iv[idx] ^ i) + iv[idx+1:]
            if (idx == 15 and i == 0) or not try_decrypt(tmp_iv, ref_c+ref_c[:48]):
                continue
            dec = long_to_bytes((16 - idx) ^ i) + dec
            print(dec)
            iv = iv[:idx] + long_to_bytes(iv[idx] ^ i) + iv[idx+1:]
            iv = iv[:idx] + xor(iv[idx:], long_to_bytes(16-idx), long_to_bytes(16-idx+1))
            break
    print(dec)
    dec2 = dec
    flag = dec0 + dec1 + dec2 + dec3
    print(flag)

    SECCON{v._.^v-_-v^._.^_S0und_oF_0rpHeUs_Aha~~}

    日本のサーバーだからなのか、 Padding Oracle Attack 問なのに oracle が高速だったので待ち時間があまりなくストレスフリーでした。

    CCC

    17 solves

    challenge.py
    from Crypto.Util.number import bytes_to_long, getPrime, getRandomInteger, isPrime
    from secret import flag
    
    
    def create_prime(p_bit_len, add_bit_len, a):
        p = getPrime(p_bit_len)
        p_bit_len2 = 2*p_bit_len // 3 + add_bit_len
        while True:
            b = getRandomInteger(p_bit_len2)
            _p = a * p
            q = _p**2 + 3*_p*b + 3*b**2
            if isPrime(q):
                return p, q
    
    
    def encrypt(p_bit_len, add_bit_len, a, plain_text):
        p, q = create_prime(p_bit_len, add_bit_len, a)
        n = p*q
        e = 65537
    
        c = pow(plain_text, e, n)
        print(f"{n=}")
        print(f"{e=}")
        print(f"{c=}")
        print(f"{a=}")
    
    
    if __name__ == "__main__":
        encrypt(1024, 9, 23, bytes_to_long(flag))

    RSA の公開鍵n=pqn = pq について、 q=a2p2+3abp+3b2q = a^2p^2 + 3abp + 3b^2 が成り立ちます。a=23a = 23bb は乱数で生成されています。pp は1024bitで bb は691bitです。

    手計算をすると an=(ap)3+3b(ap)2+3b2(ap)=(ap+b)3b3an = (ap)^3 + 3b(ap)^2 + 3b^2(ap) = (ap + b)^3 - b^3 と変形できます。 b3b^3 は十分小さいため無視して考えると ap+b(an)1/3ap + b \simeq (an)^{1/3} と近似できます。 試しに自分で生成した p,bp, b について以上の近似がどれだけ成り立つか確認してみると、2122^{12}bit程度の誤差になりました。これは全探索するのに十分小さい値なので ap+bap + b の正確な値を探索させました。

    solve.py
    from gmpy2 import iroot
    
    
    ap_b_approx = int(iroot(a * n, 3)[0])
    for i in range(10000):
        tmp = ap_b_approx + i
        if tmp ** 3 - a * n < 0:
            continue
        root, exact = iroot(tmp ** 3 - a * n, 3)
        if exact:
            b = int(root)
            ap_b = tmp
            print(root)
    p = (ap_b - b) // a
    assert n % p == 0
    q = n // p
    phi = (p - 1) * (q - 1)
    d = int(pow(e, -1, phi))
    print(long_to_bytes(int(pow(c, d, n))))

    SECCON{CCC_means_Cubic_root_and_the_CTF_I_learnt_a_lot_about_fermat's_factorization_method}

    oOoOoO

    26 solves

    problem.py
    import signal
    from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime
    import random
    from flag import flag
    
    message = b""
    for _ in range(128):
        message += b"o" if random.getrandbits(1) == 1 else b"O"
    
    M = getPrime(len(message) * 5)
    S = bytes_to_long(message) % M
    
    print("M =", M)
    print('S =', S)
    print('MESSAGE =', message.upper().decode("utf-8"))
    
    signal.alarm(600)
    ans = input('message =').strip().encode()
    
    if ans == message:
        print(flag)
    else:
        print("🧙")

    oO で構成された128文字の文字列の数値に対して、ある素数 MM で mod を計算したもの SS が与えられます。元の文字列を当てられればフラグが手に入ります。

    o0x6fO0x4f です。この文字列を数値で表すと k=0127(79+32xk)256k\sum_{k=0}^{127}(79 + 32x_k)256^{k} となります。ここで xkx_k は末尾から数えてkk番目が O のとき0, o のとき1となります。 MMSS の関係性は k=0127(79+32xk)256k=SmodM\sum_{k=0}^{127}(79 + 32x_k)256^{k} = S \mod M と記せます。 問題の見方を変えると、集合 {32×256k0k<128}\{32 \times 256^k | 0 \le k < 128 \} のどの部分集合の和を取ると S79k=0127256kS - 79\sum_{k=0}^{127} 256^k になるかを求める問題となります。これは 部分和問題 です。

    自分はこの問題を k=012732×256kxk=S79k=0127256kmodM\sum_{k=0}^{127} 32\times 256^k x_k = S - 79\sum_{k=0}^{127}256^k \mod M となる xkx_k を LLL のような格子基底簡約アルゴリズムを使って解くことにしました。 mod のぶんは全探索しました (最大でも20-30種類程度しかない)。しかし LLL だと答えが出ず、 BKZ を使ってみると答えが得られました。 BKZ よく知らないんだよな…

    solve.py
    from pwn import remote
    
    io = remote("oooooo.quals.seccon.jp", 8000)
    io.recvuntil(b"M = ")
    M = int(io.recvline())
    io.recvuntil(b"S = ")
    S = int(io.recvline())
    
    res = 0
    for i in range(128):
        res += 0x4f * 256**i
    res -= S
    res %= M
    target = -res % M
    cands = []
    for i in range(128):
        cands.append(int(0x20 * 256**i % M))
    
    def check(res):
        for r in res[0]:
            if abs(r) != 0 and abs(r) != 1:
                return False
        return True
    
    for j in range(20):
        print(j)
        mat = matrix(ZZ, 129, 129)
        for i in range(128):
            mat[i, i] = 1
        for i in range(128):
            mat[i, 128] = cands[i]
        mat[128, 128] = -(j*M+target)
        weights = diagonal_matrix([1] * 128 + [12])
        mat *= weights
        res = mat.BKZ()
        res /= weights
        if check(res):
            break
    dec = b""
    for i in range(128):
        if res[0][i] == 0:
            dec = b"O" + dec
        elif abs(res[0][i]) == 1:
            dec = b"o" + dec
    print(dec)
    io.sendlineafter(b"message =", dec)
    print(io.recvline())

    SECCON{Here_is_Huge-Huge_Island_yahhoOoOoOoOoOoO}

    この問題がここまで解かれてるのすごい、 SECCON beginners でナップサック暗号が出たからなのだろうか。

    pppp

    70 solves

    problem.sage
    from Crypto.Util.number import *
    from flag import flag
    
    p = getStrongPrime(512)
    q = getStrongPrime(512)
    n = p*q
    
    mid = len(flag) // 2
    
    e = 65537
    
    m1 = int.from_bytes(flag[:mid], byteorder='big')
    m2 = int.from_bytes(flag[mid:], byteorder='big')
    
    assert m1 < 2**256
    assert m2 < 2**256
    
    m = [[p,p,p,p], [0,m1,m1,m1], [0,0,m2,m2],[0,0,0,1]]
    
    # add padding
    for i in range(4):
        for j in range(4):
            m[i][j] *= getPrime(768)
    
    m = matrix(Zmod(p*q), m)
    
    c = m^e
    
    print("n =", n)
    print("e =", e)
    print("c =", list(c))

    上三角行列を RSA で暗号化した問題。

    上三角行列なので対角項の暗号文 CiiC_{ii}Cii=MiiemodnC_{ii} = M_{ii}^e \mod n となります。 M00=k00pM_{00} = k_{00}p (kk は未知の素数) であることを考慮すると、 gcd(C00,n)\gcd(C_{00}, n)pp が求まります。 pp が求まったので RSA の復号ができるようになり、もともとの行列の対角にある M11=k11m1,M22=k22m2M_{11} = k_{11}m_1, M_{22} = k_{22}m_2 も求まります。 これらの M11,M22M_{11}, M_{22} が素因数分解できればフラグは求まるのですが、流石にできないようになっていました (M11M_{11} のほうはできたけど M22M_{22} はできなかった)。

    次に C12C_{12}C23C_{23} の値がMM の値を使ってどう表されるかを見てみると、 C12=M12i=0e1M22iM11e1imodnC_{12} = M_{12}\sum_{i=0}^{e-1} M_{22}^i M_{11}^{e-1-i} \mod n となります。 M11,M22M_{11}, M_{22} は上記の方法で求まるので M12M_{12} も求まります。 M12=k12m1M_{12} = k_{12} m_1 という形なので、 gcd(M11,M12)\gcd(M_{11}, M_{12})m1m_1 が求まります。 C23C_{23} に注目すると同様の方法で m2m_2 も求まります。

    solve.py
    p = gcd(c[0][0], n)
    q = n // p
    c1 = c[1][1]
    c2 = c[2][2]
    phi = (p - 1) * (q - 1)
    d = int(pow(e, -1, phi))
    
    m00 = int(pow(c[0][0], d, n))
    m11 = int(pow(c1, d, n))
    m22 = int(pow(c2, d, n))
    m33 = int(pow(c[3][3], d, n))
    
    tmp = 0
    for i in range(e):
        tmp += pow(m22, i, n) * pow(m11, e-1-i, n)
    m12 = int(c[1][2] / tmp)
    
    tmp = 0
    for i in range(e):
        tmp += pow(m33, i, n) * pow(m22, e-1-i, n)
    m23 = int(c[2][3] / tmp)
    
    print(long_to_bytes(gcd(m11, m12)) + long_to_bytes(gcd(m22, m23)))

    SECCON{C4n_y0u_prove_why_decryptable?}

      ;