# Crypto2 write up

# Tổng quan

Đề bài:

from Crypto.Util.number import *
from os import urandom

flag = b"KCSC{fake_flag}"
padding = urandom(180 - len(flag))
flag = padding[: (180 - len(flag))//2] + flag + padding[(180 - len(flag))//2 :]
   
p = getPrime(1024)
q = getPrime(512)
e = 0x10001

n = p * q
c = pow(bytes_to_long(flag), e, n)

key = q
ks = []
noises = []

for i in range(15):
    noise = key + 3*i + 5
    noise_inv = inverse(noise, p)
    k = (noise_inv * noise - 1) // p
    
    ks.append(k)
    noises.append(noise_inv % 2**562)
    
with open("data.txt","w") as f:
    f.write(f"{n = }\n{noises = }\n{ks = }\n")

Thông qua đề bài ta nhận được dữ kiện sau:

$$
\begin{split}
noises &= [noise_0, noise_1, \dots, noise_{14}]\\
ks &= [k_1, k_2, \dots, k_{14}]
\end{split}
$$

gọi `noise` được khởi tạo trong mỗi vòng thuộc miền $d$, lúc đó ta có:

$$
\begin{split}
d &= [d_0, d_1, \dots, d_{14}]\\
d_i &= key + 3*i + 5 \\
key &= q
\end{split}
$$

Ý tưởng của tác giả (~~ở đây là mình~~) là thí sinh phải tìm ra $p$ và $q$ thông qua các phương trình tổng quan có dạng như sau:

$$
d_i \cdot noise_{inv} - 1 = k_i \cdot p
$$

# Hướng tiếp cận

## Tìm $q$

Do ta chỉ nhận được mảng $noises$ là tập hợp kết quả của phép tính `noise_inv % 2^562` qua các vòng nên ta sẽ viết lại phương trình như sau:

Đặt:

$$
\begin{split}
p &= leak + 2^{562}b \\
noise_{inv} &= noise_i + 2^{562}n_i
\end{split}
$$

Tiếp đến, viết lại phương trình như sau:

$$
k_i (leak + 2^{562}b) - d_i(noise_i + 2^{562}n_i) + 1 = 0
$$

Phân phối và chuyển vế:

$$
k_i * 2^{562}b - 2^{562} n_i \cdot d_i = -1 + d_i \cdot noise_i - k_i \cdot leak
$$

Ta thấy $q$ là số nguyên tố $512$-bit, do đó $q < 2^{562}$ và bên canh đó ta cũng có thể kết luận $d_i < 2^{562}$, như vậy ta có thể mod phương trình trên cho $2^{562}$ và hy vọng có thể tìm được giá trị $q$.

Phương trình mới có dạng như sau:

$$
-1 + d_i \cdot noise_i - k_i \cdot leak = 0 \mod 2^{562}
$$

$$
-1 + (key + 3*i + 5) \cdot noise_i - k_i \cdot leak = 0 \mod 2^{562}
$$

Hiện tại, phươn trình của ta chỉ còn $2$ nghiệm là $key$ và $leak$, và đề cho tận $15$ phương trình nên việc tìm được $key$ và $leak$ là hoàn toàn khả thi.

Ở đây mình dùng `groebner_basis` , một phương pháp dùng đơn giản tập sinh của một ideal trong một vành đa thức.

P.<x,y> = PolynomialRing(Zmod(2**562))

I = P.ideal([
    noises[0]*(x+5) -1 - ks[0]*y,
    noises[1]*(x+8) -1 - ks[1]*y,
    noises[2]*(x+11) -1 - ks[2]*y
])

print(I.groebner_basis())
[x + 15095849699286157176165192141574519938693899918427427740708979667686108913040888895928594081761428218515984585906870777122468994835321959450919640276403457857023062016735, y + 8046359343118037782228277823598020857453001371030183803247456593467443731321455063833959619491793509652535546439016536857407146846080157709770883346704338364262578059073]

## Tìm $p$

Khi đã có $key$ và $leak$, ta sẽ dùng chúng để giải phương trình cũ với mục đích tìm lại $p$:

$$
k_i * 2^{562}b - 2^{562} n_i \cdot d_i = -1 + d_i \cdot noise_i - k_i \cdot leak \ \ \ (1)
$$

Hiện tại ta đang có $16$ biến là $b$ và $n_0, n_1, \dots, n_{14}$, và $15$ phương trình có dạng như $(1)$. Bên cạnh đó các biến ta cần tìm có nhiều nhất là $462$-bit, khả năng cao ta có thể lập lattice và tìm các nghiệm thông qua thuật toán [$LLL$](https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm)

đặt $vs = [-1 + d_i \cdot noise_i - k_i \cdot leak \ \forall x \in \{1, \dots, 14\}] = [v_0, v_1, \dots, v_{14}]$

Ta thiết lập Lattice như sau:

$$
M = \begin{pmatrix}
k_0 \cdot 2^{562} &k_1 \cdot 2^{562} &\cdots &k_{14} \cdot 2^{562} &1 & & & & &\\
-d_0 \cdot 2^{562} &0 &\cdots &0 & &1 & & & &\\
& -d_1 \cdot 2^{562} &\cdots &0 & & &1 & & &\\
\vdots &\vdots &\ddots &\vdots & & & & \ddots & &\\
& &\cdots &-d_{14} \cdot 2^{562} & & & & &1 & \\
-v_0 &-v_1 &\cdots &-v_{14} & & & & & &1 \end{pmatrix}
$$

Sau khi áp dụng $LLL$ với Lattice trên thì vector mà ta mong muốn tìm được có dạng như sau:

$$
[0, 0, \dots, 0, b, n_0, n_1, \dots, n_{14}, 1]
$$

Như vậy ta đã có được $b$. Việc cuối cùng là tìm lại $p$ theo phương trình:

$$
p = leak + 2^{562}b
$$

Kết hợp với $q$ đã tìm được ở trên, ta có thể dễ dàng tìm lại được flag.

from Crypto.Util.number import long_to_bytes

M = []
v = []

M.append([ks[i] * 2^562 for i in range(m)])

for i in range(m):
    d = key + 3 * i + 5
    v.append(-(-1 + d * noises[i] - ks[i] * leak))

    row = [0]*(m)
    row[i] = -d * 2^562
    M.append(row)

M.append(v)

M = matrix(M)
M = M.augment(identity_matrix(m+2))
L = M.LLL()

b = L[0][m]
p = leak + b*2^562
n = p*q
phi = (p-1)*(q-1)
d = pow(65537, -1, phi)
print(long_to_bytes(pow(c, d, n)))
# KCSC{h0w_do_y0u_know_th1s_is_5olv4b13}