nitectf 2024 Quadrillion_Matrices [19 Solves]

chall

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

from Crypto.Util.number import *
from secret import gen_matrix
from sage.all import *
import random

p = getPrime(256)

with open('flag', 'rb') as f:
    flag = bin(bytes_to_long(f.read()))[2:]

inp = []
out = []

for i in flag:
    M = gen_matrix(p)
    inp.append(list(M))
    out.append( list((M**(random.randrange(3+int(i), p, 2))) * (M**(random.randrange(3, p, 2)))) )

with open('out', 'w') as f:
    f.write(str(p) + '\n')
    f.write(str(inp) + '\n')
    f.write(str(out))

ベースとなる2×2の行列Mを作り、\(ct_i = M^{u_i}*M^{v_i}\)を作ります。この時、\(a_i\)は偶数番目だと、偶数に、奇数番目だと奇数の値がランダムに選ばれます。

前提条件

まず、フェルマーの小定理を思い出しましょう。

これは\(1\equiv a^{p-1}\mod p \in [0,p-1] \)となるものです。この時、初めに1に戻るときの指数部の値をorderと呼びます。今回は\(p-1\)です。

これを行列に適応するとどうなりますか？（以下の行列ではmodを省略して書いてます。）

まず、

$$ A= \begin{bmatrix} a & b\\ c & d \end{bmatrix}$$

のときジョルダン標準形を用いて対角化することができます。

具体的には、\(PBP^{-1} \)です。この時\(B\)は対角化行列（もしくは上三角行列）になります。

これらの嬉しい性質として、\(B^k=PA^kP^{-1}\)という性質を満たします。

ということは、$B$という対角化行列を考えれば結果的によさそうですね。

要素まで見たべき乗ではこうなり、

$$B=\begin{bmatrix}
b_0 & 0 \\0 & b_1\\ \end{bmatrix} \Leftrightarrow B^k =\begin{bmatrix}b_0^k & 0 \\0 & b_1^k\
\end{bmatrix}$$

先ほど見たフェルマーの小定理みたいな形になります。

なので、行列のorderは$p-1$になります。

$$B^{p-1} = \begin{bmatrix} b_0^{p-1} & 0 \\ 0 & b_1^{p-1}\\ \end{bmatrix}\Leftrightarrow I =\begin{bmatrix} 1 & 0 \\ 0 & 1\\ \end{bmatrix}$$

sol

なので、仮に\(i=1\)を考えると、\(ct_i = M^{u_i}*M^{v_i}$の$u_i\)は偶数であり、\(u_i＋v_i\)は奇数になり、\(p-1\)とは基本的に互いに素になります。

仮に$i=0$を考えると、\(ct_i = M^{u_i}*M^{v_i}\)の\(u_i\)は奇数であり、\(u_i＋v_i\)は偶数になり、\(p-1\)とは基本的に最大公約数が2になります。これによって、flagのbitが判定できます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

from Crypto.Util.number import *
a = [eval(f) for f in open("out").readlines()]
p, _base, _ct = a
pt = ""

for i in range(len(_ct)):
    base = Matrix(GF(p),_base[i])
    ct = Matrix(GF(p),_ct[i])
    o = base.multiplicative_order()
    o2 = ct.multiplicative_order()
    pt += str((o//o2)%2)

print(long_to_bytes(int(pt,2)))

nite{0ur_b4tt1e_w4s_l0g3ndr3}