2019年5月 – ページ 2 – mktのブログ

火曜授業があった

今日は授業2コマを受けてから研究室でぼちぼち作業してた．

口内炎が痛い．

作業した

月曜日は授業が無いのでタイトルに困る．

今日は研究室で課題とバの作業をした．

ようやくバの進捗が生まれたので良かった．

Harekaze CTF 2019 Writeup（ONCE UPON A TIME）

週末に開催されていた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