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

answer.pyの一部

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

 

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

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

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






感想

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

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