神のミソ汁のセカイ

大学生活のことや技術的な備忘録を残してます

EasyCTF 2015: Matrices Write-up

問題

EasyCTF 2015: Matrices

チャレンジ中のリストはこちCrypto Challenges List(2015)

解答

問題文を見るとoutput2を復元すればいいようだ。 Zobがオリジナルの暗号化アルゴリズム(matrix.java)に共通の鍵を使ってmessage1を暗号化したという。プログラムを見るとoutput1に結果を出力しているので、message1output1を使って鍵を復元すればoutput2を復元できる。

matrix.javaを見るとブロック暗号のCBCモードに似た暗号化を行っている。 CBCモードについては暗号利用モード - Wikipediaを参照。

メッセージは長さ16のブロックに分割されている。また暗号化アルゴリズムは行列の積であり、鍵は$16 \times 16$の正方行列である。メッセージを$m=m_1||m_2||\dots||m_n$、暗号文を$c=c_1||c_2||\dots||c_n$、鍵を $\text{K}$ とするとmatrix.javaで行われている暗号化は

$$c_i^\text{T} = \text{K}(c_{i-1} \oplus m_i)^\text{T}\quad(i=1,2,\dots)\ ただしc_0 = \bf{0}$$

である。$m_i$と$c_i$を16個集めると逆行列の計算によって鍵を手に入れることができる。

$$\text{C} = (c_1^\text{T}, c_2^\text{T}, \dots c_{16}^\text{T})$$

$$\text{M} = ((c_0 \oplus m_1)^\text{T}, (c_1 \oplus m_2)^\text{T}, \dots, (c_{15} \oplus m_{16})^\text{T})$$

とすると

$$\text{C} = \text{KM}\\ \text{K} = \text{C}\text{M}^{-1}$$

鍵$\text{K}$が手に入ったら鍵の逆行列$\text{K}^{-1}$を求めてoutput2を復号すればよい。復号アルゴリズムCBCモードと同じ。

これらを踏まえてmessage1output1から暗号化鍵を取り出してoutput2を復号するプログラムを作った。

#! /usr/bin/env python3
# -*- coding : utf-8 -*-

import numpy as np
import gmpy2 as gp2

def inv_mod(matrix, modulo):
    A = np.copy(matrix)
    n = A.shape[0]
    inv_A = np.identity(n, dtype=int)
    for i in range(n):
        tmp = int(gp2.invert(int(A[i][i]), modulo))
        for j in range(n):
            A[i][j] = (A[i][j] * tmp) % modulo
            inv_A[i][j] = (inv_A[i][j] * tmp) % modulo

        for j in range(n):
            if i != j:
                tmp = A[j][i]
                for k in range(n):
                    A[j][k] = (A[j][k] - A[i][k] * tmp) % modulo
                    inv_A[j][k] = (inv_A[j][k] - inv_A[i][k] * tmp) % modulo

    return np.copy(inv_A)

def get_key(message, ciphertext, n):
    M = [message[i:i+n] for i in range(0, n*n, n)]
    C = [list(ciphertext[i:i+n]) for i in range(0, n*n, n)]
    iv = [(b'\0'*n + ciphertext)[i:i+n] for i in range(0, n*n, n)]
    for i in range(n):
        M[i] = list(map(lambda a,b : a ^ b, M[i], iv[i]))

    M = np.array(M).transpose()
    C = np.array(C).transpose()
    M_inv = inv_mod(M, 251)
    key = C.dot(M_inv) % 251
    return key

def decrypt(ciphertext, key):
    n = len(key)
    inv_key = inv_mod(key, 251)
    C = [list(ciphertext[i:i+n]) for i in range(0, len(ciphertext), n)]
    iv = [(b'\0'*n + ciphertext)[i:i+n] for i in range(0, len(ciphertext), n)]
    message = b''
    for i in range(len(C)):
        c = np.array(C[i]).transpose()
        message += bytes(map(lambda a,b : a^b, inv_key.dot(c) % 251, iv[i]))
    return message

N = 16
with open('message1', 'rb') as f:
    message1 = f.read()

with open('output1', 'rb') as f:
    output1 = f.read()

with open('output2', 'rb') as f:
    output2 = f.read()

key = get_key(message1, output1, N)
message = decrypt(output2, key)
print(message)

inv_mod関数内の逆行列を求めるアルゴリズム行列式の値の求め方、逆行列の作り方の C 言語プログラム - Blue Sky Labを参考にした。ただし今回は実数の範囲でなく $GF(251)$ であるので通常の割り算の代わりに逆元の計算を行っている。

プログラムの実行結果は

$ ./solver.py
b'the flag: easyctf{4b5+r4C+10N}\xc6\xc0'

よってflagはeasyctf{4b5+r4C+10N}

感想

numpyを初めて使ったけど行列の計算が簡単にできて便利そう。数値計算系のアルゴリズムはそらで書けるようにしたい。 また、線形代数の知識の抜けを実感したので復習したい。

(githubに載ってたWrite-upではSageを使っていたけどSageって有限体とか環を扱えるのね)