###### tags: `NTU`

# HW1 Writeup

<style>
.markdown-body {
font-family: 'Arial', -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
font-size: 14px;
line-height: 1.6;
} !important;
</style>

contents of zip file

.
├── code
│   ├── HNP-revenge
│   │   └── solve.ipynb
│   ├── Single
│   │   └── single.ipynb
│   └── nLFSR
│       ├── nLFSR.ipynb
│       ├── nLFSR.sage
│       └── nLFSR.sage.py
└── writeup.pdf

## nLFSR

First of all, I create a companion matrix $M$ from the related polynomial $P$, where $ploy_i$ denotes the ith bit in the constant called ploy. The reason why ploy is put on the left side instead of the bottom of the matrix, this is derived from the observation of the `step` function.

$$
P = x^{64} + 1
$$

$$M =
\begin{bmatrix}
ploy_{1} & 1 & 0 & 0 & \dots & 0 \\
ploy_{2} & 0 & 1 & 0 & \dots & 0 \\
ploy_{3} & 0 & 0 & 1 & \dots & 0 \\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
ploy_{64} & 0 & 0 & 0 & \dots & 0
\end{bmatrix}
$$

However, the server outputs bits in the stride of 42 or 43. So we need another matrix that can calculate state multiple steps forward.

In this case, we can construct a formula that calculate by the stride indicated in the program, where $M^{42}_{1}$ denote the first **row vector** of $M$ multiplied itself by 42 times.

$$
\left[
\begin{array}{ccc}
\rule[.5ex]{2.5ex}{0.5pt} & M^{42}_{1} & \rule[.5ex]{2.5ex}{0.5pt} \\
\rule[.5ex]{2.5ex}{0.5pt} & M^{42 + (1×43)}_{1} & \rule[.5ex]{2.5ex}{0.5pt} \\
\rule[.5ex]{2.5ex}{0.5pt} & M^{42 + (2×43)}_{1} & \rule[.5ex]{2.5ex}{0.5pt} \\
& \vdots & \\
\rule[.5ex]{2.5ex}{0.5pt} & M^{42 + (63×43)}_{1} & \rule[.5ex]{2.5ex}{0.5pt} \\
\end{array}
\right]
\begin{bmatrix}
s_{1} \\
s_{2} \\
s_{3} \\
\vdots \\
s_{64}
\end{bmatrix} =
\begin{bmatrix}
s_{1+42} \\
s_{1+42 + (1×43)} \\
s_{1+42 + (2×43)} \\
\vdots \\
s_{1+42 + (63×43)}
\end{bmatrix}
$$

$s_1$ to $s_{64}$ is the **seed** that we wish to recover. After getting 64 numbers from the sever, we can use inverse matrix to solve for the seed. Continously generating the rest number, we can now finally reach the statement that print out the FLAG.

## Single

The name of the problem has hinted that the elliptic curve is singular. The key to this problem is to solve for $a$ and $b$ in the first place. So that we can know which type of singular elliptic curve it is, whether it is Cusp or Node.

$$
y^2= x^3 + ax + b \mod{n}
$$

All the computation is under the field $GF(p)$. Using the formula of elliptic curve, we can construct matrix equation from three known points $A$, $B$, and $G$ (the generator point). $x_A$ denotes the value of point $A$, and so on.

$$
\begin{bmatrix}
x_A & 1 & x_A^3 \\
x_B & 1 & x_B^3 \\
x_G & 1 & x_G^3 \\
\end{bmatrix}
\begin{bmatrix}
a \\
b \\
1 \\
\end{bmatrix} =
\begin{bmatrix}
y_A^2 \\
y_B^2 \\
y_G^2 \\
\end{bmatrix}
$$

After solving for $a$ and $b$, we know that the curve is of type **Node**, because it has two roots. Therefore, we can use the homomorphism $φ(P + Q) = φ(P) × φ(Q)$ from the slide [Crypto II](https://www.youtube.com/watch?v=vR1aVKzoOyc&ab_channel=TimmyKuo) on page 62, and reduce the discrete logarithm problem (DLP) to multiplicative group of field $GF(p)$. This allows us to find $dA$ efficiently, and finally compute the private key value.

## HNP-revenge

The last two pages of slide [Crypto III](https://www.youtube.com/watch?v=hTU_ebHTr-s&ab_channel=TimmyKuo) tell us the solution. Our goal is to find the hidden number $d$, but first we need to find the nonces $k_1$ and $k_2$.

Using the variables $t$ and $u$ from the slide

$$
k_1 + tk_2 + u \equiv 0 \mod n
$$

We know the prefix of both nonces. Therefore, we can simplify the above equation by denoting prefix as a constant $p$.

$$
\begin{align*}
(p + k_1) + t(p + k_2) + u &\equiv 0 \mod n \\
k_1 + tk_2 + \underbrace{(t + 1)p + u}_\text{new constant} &\equiv 0 \mod n
\end{align*}
$$

Finally, we can construct lattice, where $n$ is the order of SECP256k1.

$$
B =
\begin{bmatrix}
n & 0 & 0 \\
t & 1 & 0 \\
(t + 1)p + u & 0 & 2^{128} \\
\end{bmatrix}
$$

Using LLL to solve for $k_1$ and $k_2$, this row vector will be in the LLL reduced lattice.

$$
\begin{bmatrix}-k_1 & k_2 & 2^{128}\end{bmatrix}
$$

However, LLL will not always return the correct solution. I run my script about ten times and finally get the FLAG.