# autotaker's blog

### Japanese Version

\begin{align}
C_i &= M_i + R_i \\
\begin{bmatrix}
R_{i+1} \\
1
\end{bmatrix} &=
\begin{bmatrix}
A & B\\
0 & 1\\
\end{bmatrix}^{N_i}
\begin{bmatrix}
R_{i} \\
1
\end{bmatrix} \\
N_{i+1} &= N_i^2\\
\end{align}
$$C_1 \dots, C_5 , M_1, \dots, M_4, A, B$$が既知である。$$M_5$$にフラグがあるようだ。

#### 解析

まず、行列の累乗を計算する。
\begin{align}
\begin{bmatrix}
A & B\\
0 & 1\\
\end{bmatrix}^{n} &=
\begin{bmatrix}
A^n & A^{n-1} B + A^{n-2} B + \dots + B \\
0 & 1
\end{bmatrix} \\
&=
\begin{bmatrix}
A^n & \frac{(A^{n} - 1)B}{A - 1}\\
0 & 1
\end{bmatrix}
\end{align}
したがって
$R_{2} = A^{N_1} R_{1} + \frac{(A^{N_1} - 1)B}{A - 1}$
これを$$A^{N_1}$$について解くと
$A^{N_1} = (R_2 + B (A - 1)^{-1})(R_1 + B(A-1)^{-1})^{-1}$
よって$$A^{N_1}$$の値は計算できる。
$$N_1$$を計算するのは離散対数問題といって一般の体では計算するのは難しいが、少なくとも$$GF(2^{128})$$なら離散対数は現実的な時間で計算できるようだ。

#### 解法

pari/gpで離散対数を計算する処理までを行った。

gistc2a4481d5f18d35e913503664320a016

$gp -q doit.gp x^123 + x^117 + x^116 + x^114 + x^113 + x^112 + x^110 + x^109 + x^108 + x^107 + x^104 + x^99 + x^98 + x^97 + x^95 + x^93 + x^91 + x^89 + x^87 + x^84 + x^83 + x^82 + x^81 + x^80 + x^78 + x^74 + x^69 + x^68 + x^66 + x^62 + x^57 + x^53 + x^52 + x^51 + x^45 + x^43 + x^42 + x^41 + x^38 + x^37 + x^35 + x^33 + x^32 + x^31 + x^30 + x^29 + x^28 + x^25 + x^22 + x^19 + x^18 + x^17 + x^15 + x^14 + x^13 + x^12 + x^10 + x^8 + x^5 + x^2 + 1 76716889654539547639031458229653027958 10秒くらい待つと離散対数が計算できたので元のプログラムを改変して復号した。 gistedf58b1bf3484af727d98a7ebda023ff $ python exploit.py
['\r\xa8\xe9\xe8J\x99\xd2M\x0fx\x8cqn\xf9\xe9\x9c', '\xc4G\xc3\xcf\x12\xc7\x16 m\xee\x92\xb9\xceY\x1d\xc0', 'r-BF)\x18b\x11 \xec\xe6\x8a\xc6NI:', 'A\xea:p\xdd\x7f\xe2\xb1\xd1\x16\xacH\xf0\x8d\xbf+', '&\xbdc\x83O\xa5\xb4\xcbu\xe3\xc6\rIg\x92', '\x1b\x91\xdf^^c\x1e\x8e\x9eP\xc9\xd8\x03P\x9c'] ['One-Time Pad is ', 'used here. You w', "on't know that t", 'he flag is flag{'] One-Time Pad is used here. You won't know that the flag is flag{LCG1sN3ver5aFe!!}.��Y���+�]j�  flag文字列が自分の解法とあまり一致していない気がするので離散対数をもとめずとも計算できるのかもしれない。 ### English Version #### Task In the provided zip file, there are an encryption script 'oneTimePad2.py' and 'ciphertext'. In this time, the crypt system is built on $$GF(2^{128})$$ \begin{align} C_i &= M_i + R_i \\ \begin{bmatrix} R_{i+1} \\ 1 \end{bmatrix} &= \begin{bmatrix} A & B\\ 0 & 1\\ \end{bmatrix}^{N_i} \begin{bmatrix} R_{i} \\ 1 \end{bmatrix} \\ N_{i+1} &= N_i^2\\ \end{align} We know $$C_1 \dots, C_5, M_1, \dots, M_4, A, B$$. The flag must be in $$M_5$$. We want to detect the value of $$N_1$$ in order to break this system. #### Analysis First, let's compute the matrix power. \begin{align} \begin{bmatrix} A & B\\ 0 & 1\\ \end{bmatrix}^{n} &= \begin{bmatrix} A^n & A^{n-1} B + A^{n-2} B + \dots + B \\ 0 & 1 \end{bmatrix} \\ &= \begin{bmatrix} A^n & \frac{(A^{n} - 1)B}{A - 1}\\ 0 & 1 \end{bmatrix} \end{align} Therefore, $R_{2} = A^{N_1} R_{1} + \frac{(A^{N_1} - 1)B}{A - 1}$ By solving this equation for $$A^{N_1}$$, $A^{N_1} = (R_2 + B (A - 1)^{-1})(R_1 + B(A-1)^{-1})^{-1}$ Then, we can conpute the value of $$A^{N_1}$$. Task to compute the value of $$N_1$$ from $$A^{N_1}$$ is called 'discrete logarithm problem', which is known to be difficult for general fields. Fortunately, in this field $$GF(2^{128})$$, the discrete logarithm is computable in a reasonable time. #### Solution We compute the descrete logarithm with PARI/GP. gistc2a4481d5f18d35e913503664320a016  gp -q doit.gp
x^123 + x^117 + x^116 + x^114 + x^113 + x^112 + x^110 + x^109 + x^108 + x^107 + x^104 + x^99 + x^98 + x^97 + x^95 + x^93 + x^91 + x^89 + x^87 + x^84 + x^83 + x^82 + x^81 + x^80 + x^78 + x^74 + x^69 + x^68 + x^66 + x^62 + x^57 + x^53 + x^52 + x^51 + x^45 + x^43 + x^42 + x^41 + x^38 + x^37 + x^35 + x^33 + x^32 + x^31 + x^30 + x^29 + x^28 + x^25 + x^22 + x^19 + x^18 + x^17 + x^15 + x^14 + x^13 + x^12 + x^10 + x^8 + x^5 + x^2 + 1
76716889654539547639031458229653027958

It took around ten seconds before we have the discrete logarithm.
Then, we decrypted the cipher text with a modified version of the encryption program.

gistedf58b1bf3484af727d98a7ebda023ff

$python exploit.py ['\r\xa8\xe9\xe8J\x99\xd2M\x0fx\x8cqn\xf9\xe9\x9c', '\xc4G\xc3\xcf\x12\xc7\x16 m\xee\x92\xb9\xceY\x1d\xc0', 'r-BF)\x18b\x11 \xec\xe6\x8a\xc6NI:', 'A\xea:p\xdd\x7f\xe2\xb1\xd1\x16\xacH\xf0\x8d\xbf+', '&\xbdc\x83O\xa5\xb4\xcbu\xe3\xc6\rIg\x92', '\x1b\x91\xdf^^c\x1e\x8e\x9eP\xc9\xd8\x03P$\x9c']
['One-Time Pad is ', 'used here. You w', "on't know that t", 'he flag is flag{']
One-Time Pad is used here. You won't know that the flag is flag{LCG1sN3ver5aFe!!}.��Y���+�]j�


Now, we have the flag, but there may be another solution which does not require to compute discrete logarithms, since our solution seems to be different from what the flag suggests.