週末に開催されていた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時間近くかかったが解いてて楽しかった．
来年もあるなら参加してみたい．
