3kCTF-2021 Writeup

この大会は2021/5/15 20:00(JST)～2021/5/17 2:00(JST)に開催されました。
今回もチームで参戦。結果は363点で232チーム中69位でした。
自分で解けた問題をWriteupとして書いておきます。

sponsors (Misc)

添付されているPDFの最後のページにフラグが書いてあった。

3k{saNiTy_ch3K_2732832}

crypto warmup (Crypto)

ナップザック暗号。24ビットごとにビットの有無に対応するBの各要素の合計が暗号になっている。LLLを使って復号する。

#!/usr/bin/sage
from Crypto.Util.number import long_to_bytes

def is_valid_vector(b):
    if b[0] != 0:
        return False
    for i, x in enumerate(b):
        if i != 0 and abs(x) != 1:
            return False

    return True

B = [4267101277, 4946769145, 6306104881, 7476346548, 7399638140, 1732169972, 1236242271, 5109093704, 2163850849, 6552199249, 3724603395, 3738679916, 5211460878, 642273320, 3810791811, 761851628, 1552737836, 4091151711, 1601520107, 3117875577, 2485422314, 1983900485, 6150993150, 2045278518]
ct_list = [34451302951, 58407890177, 49697577713, 45443775595, 38537028435,
    47069056666, 49165602815, 43338588490, 32970122390]

matrix_size = len(B) + 1
m_list = [
    [0 for _ in range(matrix_size)] for _ in range(matrix_size)
]

for i in range(matrix_size - 1):
    m_list[i][0] = B[i]
    m_list[i][i+1] = 2
    m_list[matrix_size - 1][i+1] = -1

flag = ''
for ct in ct_list:
    m_list[matrix_size - 1][0] = -ct

    llled = Matrix(ZZ, m_list).LLL()

    flag_vecs = []
    for basis in llled:
        if is_valid_vector(basis):
            flag_vecs.append(basis)

    for v in flag_vecs:
        m = ''
        for _bit in reversed(v[1:]):
            c = ("1" if _bit == 1 else "0")
            m = c + m
        flag += long_to_bytes(int(m, 2))

print flag

CTF{w4rmup-kn4ps4ck-ftw!}