# autotaker's blog

### Japanese Version

\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$$という擬似乱数生成器の生成した数列にある。

$R_{i+1} = (R_{i} + K)^2$

$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というツールを使うと計算できる。

#### 解法

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

### English Version

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

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