この大会は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!}