# NTU Computer Security HW1
###### tags: `NTU`
## AES
1. we can visualize the powertrace to find the first round data set. the reason why we select first round is that it's same as the original key.
* note: y axis is the powertrace value, x axis is the data point index.
2. after find out the data set, we still need some preprocessing before making statistical analysis.
a. AddRoundKey: xor the plaintext with guessed key.
b. SubBytes: transformation by S-box with previous result.
3. calculate the hamming weight with previous result and calculate the correlation coefficient to figure out the key byte with maxium result.

    highest score: 0.7953237685820772
    highest score: 0.7734930245952536
    highest score: 0.7862970548364613
    highest score: 0.7693514149160879
    highest score: 0.8303942203194717
    highest score: 0.8934208879733103
    highest score: 0.8858194278735226
    highest score: 0.9077147559148856
    highest score: 0.8120312663960112
    highest score: 0.7825815297329007
    highest score: 0.7981611726939593
    highest score: 0.8534907243247877
    highest score: 0.8633358939085477
    highest score: 0.9151174571753856
    highest score: 0.9384709550391714
    highest score: 0.8995213123678847
    b'18MbH9oEnbXHyHTR'

## DH
$c=flag \times (user\;imput)^x$
if the order of user input is small enough(ex: 3), then we can reduce the equation by $c=flag \times (user\;input)^x=flag \times (user\;imput)^{3k+r}$$=flag \times (user\;imput)^{r}, 0\le r\le 2 \in Z$
then we can bruteforce the flag by multiply $c$ with $(user\;input)^{-r}$ and obtain the flag.
## lsb
for message $m$, we can express it as the following format
$m=3^km_k+...+3m_1+m_0$
when we pass the ciphertext $c$ to the oracle, we can obtain $m\mod 3=m_0$. then we can pass $3^{-e}c=(3^{-1}m)^e$ to the oracle. the oracle will return $3^{-1}m \mod 3$, which can be expressed into the following format.
$3^{-1}m\mod n \mod 3=3^{k-1}m_k+...+m_1+3^{-1}m_0 \mod n \mod 3$$=m_1+3^{-1}m_0 \mod n \mod 3$
since we already have $m_0$ in previous step and we also capable to compute $3^{-1}$, then we can recover $m_1$. as a result, we can obtain flag by recovering other $m_i$ similarly.
## node
since this curve is singular curve $-16(4a^3+27b^2)\%p=-16(4\times(-27)+27\times4)=0$ and the curve equation is equal to $(x - 1)^2 \times (x + 2) = y^2$, the points on the curve can be map to multiplicative group of $F^*_{p^2}$ where discrete log is easier to compute with sagemath ```discrete_log``` function. then, we transform the ciphertext node and base by isomorphic map then pass into ```discrete_log```, we can obtain the flag by order of the ciphertext.
## xor-revenge

$\left[
\begin{matrix}
v\end{matrix}
\right\rvert
\begin{matrix}
I_{63}&& \\
0\end{matrix}]\times\begin{bmatrix}
s_{63} && \\
\vdots && \\
s_0
\end{bmatrix}=\begin{bmatrix}
s_{63}' && \\
\vdots && \\
s_0'
\end{bmatrix}=Ms=s'$
where $M$ is the translation matrix, $s$ is the state before operation, and $v$ is the bit representation of ```0xda785fc480000001```. for some state output $o_i$ without xoring the plaintext, there is a relationship that $M^{37}\times\begin{bmatrix}o_i && o_{i+1} && \dots && \end{bmatrix}^T=\begin{bmatrix}o_{i+1} && o_{i+2} && \dots && \end{bmatrix}^T$. as a result we can simply recover the original state vector by multiplying the following matrix's inverse with state output vector $o$
$\begin{bmatrix}
[1, 0, 0, \dots, 0]\times M^{36} && \\
[0, 1, 0, \dots, 0]\times M^{36+37} && \\
\vdots && \\
[0, 0, 0, \dots, 1]\times M^{36+37\times63}
\end{bmatrix}$
after recovering back the original state $s$, we can run the algo again to get key and xor it with ciphertext to obtain flag.