# HW1 Crypto CTF writeup
R11922138
CTF Account: eric070021

### 1. LSB
The original message $m$ can be write as a polynomial of 3:
$$m = a_n*3^n+a_{n-1}*3^{n-1}+...+a_1*3+a_0$$
So, I constrct the message $m'$ and send it to the server, where $m'$:
$$m' = (3^{-e*t}*enc)\%n=(3^{-e*t}*m^e)\%n=(3^{-t}*m)^e\%n
\\ 3^{-t}*m=a_n*3^{n-t}+a_{n-1}*3^{n-t-1}+...+a_1*3^{1-t}+a_0*3^{-t}$$
By controlling t starting from 0 and keep increasing, I can get all $a_n$.
The ending condition is that if the output is more than 20 consecutive 0, meaning the message might have all been printed, then the program will stop.
All operations need to be calculated under modulo n, I debug for a while just because I forgot to modulo n in a place.

### 2. XOR-revenge
The state change of LFSR can be seen as multiplying a companion matrix, and the companion matrix can directly get from the chal.py. The companion matrix will look like the below which subdiagonal elements are all ones but a 64*64 version and the right-most column will be the binary representation of 0xda785fc480000001 (the value xor with the state in chal.py)
\begin{bmatrix}
0 & 0 & 0 & 0 & 1\\
1 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 0\\
\end{bmatrix}
Since I have the 70 (>=64) clean output bits of the LFSR, I can recover the original state by solving linear equations.
Define $W_0 = [0 0 0...01]$ as a 1\*64 matrix., C is the companion matrix, S[k] is the origin state of LFSR, and Y[k] is the first 64 bits of clean output.
We have the following equations:
$$\begin{bmatrix}
W_0C^{12468} \\
W_0C^{12468+37} \\
. \\
. \\
W_0C^{12468+37*63} \\
\end{bmatrix}
S[k]=Y[k]$$
(12468 is because flag is 336 bits long, so the first clean output bit needs (336+1)*37 - 1 = 12468)
Next, I use Gauss Jordan to solve the linear equations under modulo 2. I can't just directly use the method of solving linear equations in numpy or other libraries since most of them are solved by multiplying inverse matrix. I write it myself instead.
After solving the equations, I get the origin state. Then, I can recover every bit of FLAG.

### 3. DH
The server will power the number we transfer with a random number and multiply it with FLAG. If I want to get the FLAG I need to be able to recover the FLAG from it.
My first thought is to transfer the quadratic residue of 1 under modulo p to the server since by that the output of the server will be either the FLAG or FLAG multiply the quadratic residue of 1. But, I test for a while, and the quadratic residue of 1 is always 1 and p-1.
Then, I use the quadratic residue of p-1. Let's name it w. $w^4\%p=1$. So, the output of the server will only have 4 types, $FLAG,\ FLAG*w,\ FLAG*w^2,\ FLAG*w^3$.
I can recover FLAG by multiplying the corresponding mod inverse.
The result:
Since I don't know which types the server output, I simply output all 4 possibilities. The FLAG can always be recovered within these four recovery ways.

### 4. node
The name of the challenge implies the EC is singular, which is the type node.
By solving the equation:
$$y^2=x^3-3x+2=(x-\alpha)^2(x-\beta)\\
\alpha=1,\ \beta=-2$$
By the following homomorphism function, we can reduce to DLP on (Fp, *)
$$f(P(x,y))=\frac{y+\sqrt{\alpha-\beta}(x-\alpha)}{y-\sqrt{\alpha-\beta}(x-\alpha)}$$
The most important thing is that all operations need to be done in modulo p. I use sage's IntegerModRing to constrain my calculation all under modulo p and use sage's sqrt function to calculate square root.

def homomorphsim_func(x, y):
    R = IntegerModRing(p)
    numerator = R(y) + R(alpha - beta).sqrt() * R(x - alpha)
    denominator = R(y) - R(alpha - beta).sqrt() * R(x - alpha)
    return numerator / denominator

I put the origin x, y in the function and also new x, y in the function, take their outputs and use sage's discrete_log function to solve.
Then I get the FLAG.

### 5. AES
I use CPA(correlation power attack) to attack at the intermediate value after SBOX.
First, use one byte of plaintext and guess one byte of key, xor them, and put the result in sbox. Doing this for all 256 possibilities of keys. Later, pick the other plaintext and do the same thing all again.
The power model I use is Hamming weight. Calculate the hamming weight of the result of sbox and the result will be a D*256 matrix, with D being the number of plaintexts.

for i in range(len(data)):
    for key in range(256):
      HM[i][key] = bin(sbox[pt[i][round] ^ key]).count('1')

I need to calculate the correlation of each key with the power results. Pick each column of the key matrix and calculate the correlation with each column of power results. After doing all keys, the key has the highest correlation will be our first byte of keys.

for i in range(256):
    for j in range(1806):
      correlation[i][j] = np.corrcoef(HM[:, i], pm[:, j])[0][1]

  print(hex(np.argmax(correlation) // 1806).replace('0x', ''), end='')

Doing the above process to all bytes of plaintext, then we can get our secret key of AES which is our FLAG, too.