日: 2019年5月20日

週末に開催されていたHarekaze CTFに参加して以下の1問だけ解けたので解法を書き残しておく（間違っていたら直します）．

[Crypto] ONCE UPON A TIME 100

problem.pyと実行結果のresult.txtが与えられる．

Encrypted Flag:
ea5929e97ef77806bb43ec303f304673de19f7e68eddc347f3373ee4c0b662bc37764f74cbb8bb9219e7b5dbc59ca4a42018

result.txt

Encrypted Flagは，フラグを25文字ずつに分割して5×5行列の各要素に1文字を割り当て，法251のもとで行列積を行って暗号化したものだった．
（もう片方の5×5行列m2はプログラム中で与えられる）

m2 = [[1,3,2,9,4], [0,2,7,8,4], [3,4,1,9,4], [6,5,3,-1,4], [1,4,5,3,5]]

def takenoko(X, Y):
  W = [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]
  for i in range(5):
    for j in range(5):
      for k in range(5):
        W[i][j] = (W[i][j] + X[i][k] * Y[k][j]) % 251
  return W

problem.pyの一部

解法

n次正方行列A，n次元列ベクトルb，整数mがあり，det (A) とmが互いに素のとき，mを法とする連立合同式

Ax ≡ b (mod m)

の解が

x = cÃb  

（ただし，Ã = det (A)・A^-1，　c・det(A) ≡ 1（mod m））

で与えられるようなので（このpdfを参考にした），これもとに実装した．

pdfに載っているのは行列-ベクトル積の合同式だが，本問題のような行列-行列積でも同じように適用できた．

以下に実装を示す．

def decrypt(m1, m2):
    c = b""
    for mat in m1:
        g = random.randint(0,1)
        if g == 0:
            _mk = np.dot(m2, mat)
        else:
            _mk = np.dot(mat, m2)
            
        mk = []
        for i in range(5):
            tmp = []
            for j in range(5):
                hoge = int(np.floor(_c * det_m2 * _mk[i][j] + 0.5))
                tmp.append(int(hoge)%251)
            mk.append(tmp)

        for k in mk:
            c += bytes(k)

    return c

answer.pyの一部

このdecryptに，m2の逆行列と，暗号化されたバイナリを要素にもつ行列を渡してフラグを得た．

 

本問題では，法251に関するdet(A)の逆元c（プログラム中では変数_c）の値は94となった．

逆行列や行列式の計算にはnumpyを用いた．

また，暗号化の際にrandom関数で行列積の順序を予測できないようにされていたが，積の順序は4通りしかないことが分かっていたのでゴリ押した．

感想

この1問に6時間近くかかったが解いてて楽しかった．

来年もあるなら参加してみたい．