0CTF Writeup: oneTimePad1

これは0CTFのoneTimePad1という問題のWriteupです。

Japanese Version

Task

zipファイルを開くと暗号化スクリプトoneTimePad.pyと暗号文ciphertextがある。
暗号化の仕組みはブロック暗号で\(GF(2^{256})\)上で次のように計算する。

\begin{align}
C_1 &= M_1 + R_1 \\
C_2 &= M_2 + R_2 \\
C_3 &= M_3 + R_3
\end{align}
ここで\(C_1, C_2, C_3\)が暗号文、 \(M_1, M_2, M_3\)が平文となる。
\(C_1, C_2, C_3, M_2, M_3\)は既知で\(M_1\)を復号するのが問題のようだ。

解析

もちろん、暗号化の肝は\(R_1, R_2, R_3\)という擬似乱数生成器の生成した数列にある。
擬似乱数生成器は、秘密鍵\(K\)と現在の乱数\(R_i\)から次の乱数\(R_{i+1}\)を次のように生成する。
\[
R_{i+1} = (R_{i} + K)^2
\]
今\(GF(2^{256})\)上で考えているので、\(2 = 0, X + Y = X - Y \)が成り立つことに注意すると、
\[
R_{i+1} = R_{i}^2 + K^2
\]
となる。\(C_2, C_3, M_2, M_3\)はわかっているので、\(K^2 = R_2 + R_1^2\)の右辺は計算できる。
これを\(R_1 = R_0^2 + K^2\)に代入すると
\[
R_0 = \sqrt{ R_1 + R_2 + R_1^2 }
\]
である。右辺の平方根は平方剰余というやつでPARI/GPというツールを使うと計算できる。

解法

gist8bcd0ce53f61a87c8742e697917cfae1

$ gp -q doit.gp 
52553756545437879763013576434186236591362916937163148104579268147006553551449
$ python
>>> hex(52553756545437879763013576434186236591362916937163148104579268147006553551449)[2:-1].decode('hex')
't0_B3_r4ndoM_en0Ugh_1s_nec3s5arY'

English Version

Task

There are an encryption script 'oneTimePad.py' and 'ciphertext' in the provided zip file.

The crypto system is described over \(GF(2^{256})\)
\begin{align}
C_1 &= M_1 + R_1 \\
C_2 &= M_2 + R_2 \\
C_3 &= M_3 + R_3
\end{align}
Here, \(C_1, C_2, C_3\) are cipher texts and \(M_1, M_2, M_3\) are plain texts.
We know \(C_1, C_2, C_3, M_2, M_3\), and the task of this problem is to decrypt \(C_1\).

Analysis

Of course, the clue of this crypto system is pseudo random numbers \(R_1, R_2, R_3\).
The random number generator generates the next number \(R_{i+1}\) from Secret key \(K\)
and the current number \(R_i\) in the following way:
\[
R_{i+1} = (R_{i} + K)^2
\]
We note that equations like \(2 = 0, X + Y = X - Y\) hold because the field is \(GF(2^{256})\).
Then, we have,
\[
R_{i+1} = R_{i}^2 + K^2
\]
The rhs of \(K^2 = R_2 + R_1^2\) is computable since we know \(C_2, C_3, M_2, M_3\).
By substituting it to \(R_1 = R_0^2 + K^2\), we have
\[
R_0 = \sqrt{ R_1 + R_2 + R_1^2 }
\]
The square root in its rhs is so called quadratic residue and it is computable with
tools like PARI/GP.

Solution

gist8bcd0ce53f61a87c8742e697917cfae1

$ gp -q doit.gp 
52553756545437879763013576434186236591362916937163148104579268147006553551449
$ python
>>> hex(52553756545437879763013576434186236591362916937163148104579268147006553551449)[2:-1].decode('hex')
't0_B3_r4ndoM_en0Ugh_1s_nec3s5arY'