MeePwn CTF 1st 2017 Writeup

この大会は2017/7/14 9:00(JST)～2017/7/16 9:00(JST)に開催されました。
今回もチームで参戦。結果は900点で542チーム中32位でした。
自分で解けた問題をWriteupとして書いておきます。

nub_cryptosystem (CRYPTO)

暗号化のコードが与えられているので、読んでいくとMerkle-Hellmanナップサック暗号であることがわかる。この場合、解読できる条件は秘密鍵が超増加列になっていることだが、これも当然のごとくあてはまる。ということで、復号プログラムを書く。

def load_data():
    with open('pubkey.txt', 'r') as f:
        pub_keys = f.read().strip()[1:-1].split(', ')

    with open('enc.txt', 'r') as f:
        ciphertext = int(long(f.read().strip()))

    return pub_keys, ciphertext

def create_matrix_from_knapsack(ciphertext, pub_keys):
    last_col = []
    for p in pub_keys:
        last_col.append(int(long(p)))

    last_col.append(ciphertext)
    last_row = [1 for i in pub_keys]

    my_matrix = MatrixSpace(ZZ, len(pub_keys))(2)
    m_last_row = matrix(ZZ, 1, len(last_row), last_row)
    m_last_col = matrix(ZZ, len(last_col), 1, last_col)

    my_matrix = my_matrix.stack(m_last_row)
    my_matrix = my_matrix.augment(m_last_col)

    return my_matrix

def is_short_vector(vector):
    for v in vector:
        if v != 1 and v != -1 and v != 0:
            return False
    return True

def find_short_vector(matrix):
    for row in matrix:
        if is_short_vector(row):
            return row

def main():
    pub_keys, cipher = load_data()
    my_matrix = create_matrix_from_knapsack(cipher, pub_keys)

    new_matrix = my_matrix.LLL()

    short_vector = find_short_vector(new_matrix)

    bin_flag = ''
    for v in short_vector:
        if v == 1:
            bin_flag += '0'
        elif v == -1:
            bin_flag += '1'

    flag = ''
    for i in range(0, len(bin_flag), 8):
        flag += chr(int(bin_flag[i:i+8], 2))

    flag = 'MeePwnCTF{' + flag + '}'
    print flag

if __name__ == '__main__':
    main()

これで復号でき、フラグが得られた。

MeePwnCTF{Merkleee-Hellmannn!}