# KMA CTF 2025 - Crypto
## perfect days
> Tag: Easy

ĐỀ:

import random
from Crypto.Util.number import getPrime, bytes_to_long

soundtrack = [
    b"House Of The Rising Sun",
    b"the Dock of the Bay",
    b"(Walkin' Thru The) Sleepy City",
    b"Redondo Beach",
    b"Pale Blue Eyes",
    b"Brown Eyed Girl",
    b"Feeling Good",
    b"Aoi Sakana",
    b"Perfect Day"
]

print("Welcome to the song guessing game!")

for i in range(32):
    p = getPrime(512)
    k = random.randint(1, 4096)
    song = random.choice(soundtrack)
    padded_song = song + b"0xff"*(256 - len(song))
    hint = pow(1 + k*p, bytes_to_long(padded_song), p**2)
    
    print(f"p = {p}")
    print(f"hint = {hint}")
    ans = input("Guess the song: ")
    
    if ans == song.decode():
        print("Correct!")
    else:
        print("Wrong! Try again.")
        exit(0)
        
FLAG = open("flag.txt", "r").read()
print("Congratulations! You've guessed all the songs correctly.")
print(f"Flag: {FLAG}")

### Phân tích
Các song được mã hóa và gửi cho ta kiểu: $(1 + kp)^{paddedsong} \mod p^2 =
hint$. Ta sẽ coi $paddedsong = e$

- Ta áp dụng nhị thức Newton cho vế trái, ta còn được là: $e.kp + 1 = hint \mod p^2$
- Lúc này, ta có: $e = \frac{hint - 1}{kp} \mod p^2$.
- Ta chưa biết k, nhưng biết rằng:

k = random.randint(1, 4096)

- Ta sẽ tiến hành brute k trong khoảng đó, tính được $e \mod p^2$ rồi từ đó check thử xem $paddedsong$ nào có thể $\mod p^2$ để ra được tương tự. Nếu khớp thì đó là song của đề bài.
- Solve đủ 32 lần là có flag.
### Solution

from pwn import *
from Crypto.Util.number import *

HOST = "36.50.177.41"
PORT = 5001


soundtrack = [
    b"House Of The Rising Sun",
    b"the Dock of the Bay",
    b"(Walkin' Thru The) Sleepy City",
    b"Redondo Beach",
    b"Pale Blue Eyes",
    b"Brown Eyed Girl",
    b"Feeling Good",
    b"Aoi Sakana",
    b"Perfect Day"
]

# Kết nối
conn = remote(HOST, PORT)

for round in range(32):
    print(i)

    # Nhận p và hint
    conn.recvuntil(b"p = ")
    p = int(conn.recvline().strip())
    conn.recvuntil(b"hint = ")
    hint = int(conn.recvline().strip())

    for k in range(1, 4098):
        kp = k * p
        for song in soundtrack: 
            padded_song = bytes_to_long(song + b"0xff"*(256 - len(song))) 
            guessing = padded_song*kp 
            guessing %= (p*p) 
            if guessing == (hint - 1) % (p**2):
                conn.sendline(song) 
                print(song) 
    
conn.interactive()

Flag: KMACTF{did_you_enjoy_soundtrack_perfect_days}

## Make some noise
> Tag: Medium (but for me is quite hard :/)

ĐỀ:

from random import randint
from re import search

flag = b"KMACTF{fake_flag}"
flag = flag[7: -1]

p = random_prime(2**1024)
setup = [randint(0, 2**32) for _ in range(len(flag))]
setup = [f ^^ ((pad >> 8) << 8) for f, pad in zip(flag, setup)]

output = []

for _ in range(len(flag)^2):
    noise1 = [randint(0, 2**32) for _ in range(1000)]
    noise2 = [randint(0, len(setup)-1) for _ in range(1000)]
    noise3 = [randint(0, len(setup)-1) for _ in range(1000)]
    noise4 = [randint(0, 2**32) for _ in range(1000)]
    noise5 = [randint(0, 2**32) for _ in range(1000)]


    output.append(noise1)
    output.append(noise2)
    output.append(noise3)
    output.append(noise4)
    output.append(noise5)

    s = 0
    for i in range(1000):
        s += (noise5[i] * (noise1[i] + pow(setup[noise2[i]], 1337, p) * pow(setup[noise3[i]], 1663, p)) + noise4[i]) % p

    output.append(s % p)

f = open("out.txt", "w")
f.write(f"{p = }\n")
f.write(f"{output = }\n")

### Phân tích
Nhìn từ trên xuống, ta để ý thấy rằng:

p = random_prime(2**1024)
setup = [randint(0, 2**32) for _ in range(len(flag))]
setup = [f ^^ ((pad >> 8) << 8) for f, pad in zip(flag, setup)]

- P là 1 số prime lớn, hãy ghi nhớ điều này.
- Mỗi phần tử của setup thực chất là 1 byte $flag + 256.k$

Hiểu được điều này, ta nhận ra rằng để khôi phục Flag từ output, ta cần tìm lại các phần tử của setup, lấy mod 256 để khôi phục dần flag.

Ta quan sát cách output được tạo ra:

output = []

for _ in range(len(flag)^2):
    noise1 = [randint(0, 2**32) for _ in range(1000)]
    noise2 = [randint(0, len(setup)-1) for _ in range(1000)]
    noise3 = [randint(0, len(setup)-1) for _ in range(1000)]
    noise4 = [randint(0, 2**32) for _ in range(1000)]
    noise5 = [randint(0, 2**32) for _ in range(1000)]


    output.append(noise1)
    output.append(noise2)
    output.append(noise3)
    output.append(noise4)
    output.append(noise5)

    s = 0
    for i in range(1000):
        s += (noise5[i] * (noise1[i] + pow(setup[noise2[i]], 1337, p) * pow(setup[noise3[i]], 1663, p)) + noise4[i]) % p

    output.append(s % p)

Ta gọi mỗi lần lặp lớn là $m$, trong vòng lặp $m$, ta có được list các noise từ 1 đến 5, đồng thời cuối mỗi vòng còn được add thêm $s$:
$s_m = \sum_{i=0}^{999}N5_{m,i} + (N1_{m, i} + Sp[N2_{m, i}]^{1337}.Sp[N3_{m, i}]^{1663}) + N4_{m, i} \mod p$ (Sp = Setup)
>Nhìn khá tởm nhưng không sao, ta sẽ tiến hành làm đơn giản nó bằng đặt ẩn:

<=> $s_m - \sum_{i=0}^{999}N5_{m,i}.N1_{m,i} + N4_{m, i} = \sum_{i=0}^{999}N5_{m,i}.Sp[N2_{m, i}]^{1337}.Sp[N3_{m, i}]^{1663} \mod p$

- Coi vế trái là $R_m$, Ta thấy rằng phần tử trong Setup được lấy không phụ thuộc vào $i$ mà thay vào đó phụ thuộc vào $N3$ và $N2$, mà trong vòng lặp thứ $m$, giá trị của 2 thằng này chỉ nằm trong khoảng [0, $n - 1$] (Trong bài, ta sẽ coi độ dài của flag là $n$ nhé).
- Điều này nghĩa là sao? nghĩa là ta chỉ có $n. n$ cặp ($j, k$) với $(j, k)$ là index trong Setup, ta có ý được tính tích các cặp Setup($j, k$) từ những phương trình này.

Ta có được vế phải của phương trình nãy là:

$\sum_{j=0}^{n - 1}.\sum_{k=0}^{n-1}(\sum_{i}N5_{m,i}.Sp[j]^{1337}.Sp[1663]^{1663}) \mod p$ ($j = N2_{m,i}, k = N3_{m, i}$)
- $\sum_{i}N5_{m,i} = Wjk_m$
- $Sp[j]^{1337}.Sp[k]^{1663} = Pjk$

Ta được phương trình lúc này cần phải làm việc còn lại là:
$R_m = \sum_{j=0}^{n - 1}.\sum_{k=0}^{n-1}(Wjk_m.Pjk) \mod p (*)$

Vì được lặp lại $n^2 - 1$ lần, nên ta sẽ có $m$ phương trình $(*)$, tạo thành 1 hệ phương trình mod p:
$R_0 = \sum_{j=0}^{n - 1}.\sum_{k=0}^{n-1}(Wjk_0.Pjk) \mod p (*)$
$R_1 = \sum_{j=0}^{n - 1}.\sum_{k=0}^{n-1}(Wjk_1.Pjk) \mod p (*)$
$R_2 = \sum_{j=0}^{n - 1}.\sum_{k=0}^{n-1}(Wjk_2.Pjk) \mod p (*)$
...
$R_{n^2 - 1} = \sum_{j=0}^{n - 1}.\sum_{k=0}^{n-1}(Wjk_{n^2 - 1}.Pjk) \mod p (*)$

Từ những $noise, s$ đã có, ta sẽ tiến hành tìm lại tập $Pjk$ bằng cách giả hệ này.

Bắt tay vào làm thôi!
- Tạo hàm trích xuất p và output từ file out.txt, vì cấu trúc output khá phức tạp, ta dùng ast lib.
Mình dùng Gemini viết hộ hàm lấy p và output từ file:

import ast 
from sage.all import * 

def parse_output(filename="out.txt"):
    """Parses the output file to extract p and the output list."""
    p = None
    output = None
    try:
        with open(filename, 'r') as f:
            content = f.read()

        # Safely evaluate the assignments
        # Find the lines containing p and output
        p_line = next(line for line in content.splitlines() if line.startswith("p = "))
        output_line = next(line for line in content.splitlines() if line.startswith("output = "))

        p_str = p_line.split("=", 1)[1].strip()
        output_str = output_line.split("=", 1)[1].strip()

        # Use ast.literal_eval for safe parsing of the literal string
        # This is a standard Python library function available within SageMath
        p = ast.literal_eval(p_str)
        output = ast.literal_eval(output_str)

    except FileNotFoundError:
        print(f"Error: File '{filename}' not found.")
        return None, None
    except Exception as e:
        print(f"Error parsing file: {e}")
        return None, None

    return p, output

- Có được p và output, ta tiến hành Lập và Giải hệ $(*)$. Ta coi hệ sẽ có dạng $M.X = B \mod p$. Lúc này, việc ta cần làm đó là tạo ma trận hệ số $M$ và ma trận cột kết quả $B$. X sẽ là các $Pjk$ cần tìm.
- Ma trận hệ số của ta sẽ kiểu như này:

p, output = parse_output() 
R = Zmod(p) 
n_sq = len(output) // 6 
n = int(n_sq**0.5) 
print(n)

#Step1: Tạo pt + giải pt 
#making M and B: 
M = Matrix(R, n_sq, n_sq, 0) 
B = Matrix(R, n_sq, 1, 0)

for m in range(n_sq): 
    noise1 = output[6*m + 0] 
    noise2 = output[6*m + 1]
    noise3 = output[6*m + 2]
    noise4 = output[6*m + 3]
    noise5 = output[6*m + 4]
    s = output[6*m + 5] 

    R_m = R(s) - R(sum(noise1[i]*noise5[i] + noise4[i] for i in range(1000))) 
    B[m,0] = R_m 
    
    Wm = [[R(0)]*n for i in range(n)] 
    for i in range(1000): 
        j = noise2[i] 
        k = noise3[i] 
        Wm[j][k] += noise5[i]
    # Ta xếp Pij với k tăng trước i (0,0), (0, 1), (0, 2)...(1,0)...
    for j in range(n): 
        for k in range(n): 
            M[m, j*n+ k] = Wm[j][k]   

X = M.solve_right(B) 
print(X)

Ok, giờ ta đã có các giá trị $Pjk$, ta tiếp tục mổ xẻ:
$P_{00} = Sp[0]^{1337}.Sp[0]^{1663} \mod p$
=> $(\frac{Sp[k]}{Sp[0]})^{1337} = P_{k0}.P_{00}^{-1} \mod p$
=>$(\frac{Sp[k]}{Sp[0]})^{1663} = P_{0k}.P_{00}^{-1} \mod p$

Ta nhận ra phân số trên là hoàn toàn có thể tính được do các $P$ đã có sẵn.
- Đặt $Y_k$ là $\frac{Sp[k]}{Sp[0]}$, ta biết được rằng k = 0 thì $Y$ sẽ = 1.
- Ta hoàn toàn có thể tính được các $Y_k$ dựa vào Euclid khi tính được $Y_k^{1337}, Y_k^{1663}$.

Pjk_vals = [[R(0)]*n for i in range(n)] 
for j in range(n): 
    for k in range(n): 
        Pjk_vals[j][k] = X[j*n + k, 0] 

P00_inv = Pjk_vals[0][0].inverse() 
gcD, u, v = xgcd(1337, 1663) 
Yk_vals = [R(0)]*n 
Yk_vals[0] = R(1) 
for k in range(1, n): 
    P0k = Pjk_vals[0][k]
    Pk0 = Pjk_vals[k][0] 
    Yk_1337 = Pk0*P00_inv 
    Yk_1663 = P0k*P00_inv 
    Yk = (Yk_1337**u)*(Yk_1663**v) 
    Yk_vals[k] = int(Yk) 

- Với các giá trị $Yk$ đã tính được, ta biết rằng: $Yk.Sp[0] \equiv Sp[k] \mod p$
=>$Yk.Sp[0] - m_k.p = Sp[k]$

Với các $Yk$ đã biết, ta nghĩ đến việc tìm lại Setup bằng LLL, do $m_k$ hay các $Sp[k]$ đều nhỏ. Bài toán lúc này giống dạng HNP.

Ma trận cơ sở Lattice của chúng ta sẽ có dạng kiểu như này: (có thể để dương p cũng được nhưng mình sẽ để -p cho đúng công thức):
Ma trận L(n+1)(n+1) được xây dựng sao cho các hàng là cơ sở, vậy vector cần tìm của ta sẽ có dạng:
$v = m_0.s_0 + m_1.s_1 + ... + m_{n-1}.s_{n-1} + Sp_0.Bound$ (các $s$ là cơ sở)
$v = (Sp[0], Sp[1], ..., Sp[n-1], Sp[0].Bound)$
(Đề bài cung cấp cho ta dữ kiện tuyệt vời rằng các phần tử của Setup được lấy rand dưới $2^{32}$, ta thêm chiều Bound = $2^{32}$ khống chế $Sp[k]$).

#Tạo L
L = Matrix(ZZ, n+1, n+1, 0)
for i in range(n): 
    L[i, i] = -p 
for i in range(n): 
    L[n, i] = Yk_vals[i] 
L[n, n] = 2**32 
newL = L.LLL() 
print(newL.row(0))

Sau khi LLL(), ta tìm được cơ sở trông khá đẹp khi so với đống oằn tà là vằn khác:
Nên là ta lấy cơ sở hay hàng đầu tiên:

(-1897021025, -3720483959, -1198507315, -2835181171, -3669596720, -4230456941, -3739620965, -3889969503, -3079380339, -2769052976, -919415916, -1494302837, -1658467444, -1074391089, -1388234351, -1361733486, -8147643262199398400)

Bingo! Nếu phần từ đầu là $|-1897021025|$ thì phần tử cuối chính xác là $|-1897021025|.Bound (or) Sp[0].Bound$. Ta đã thành công lụm được Setup.
Việc cuối cùng ta cần làm đó là lấy mỗi phần tử của Setup recover được chia dư cho 256 là tìm được full flag rồi hẹ hẹ hẹ.
### Solution:

import ast 
from sage.all import * 

def parse_output(filename="out.txt"):
    """Parses the output file to extract p and the output list."""
    p = None
    output = None
    try:
        with open(filename, 'r') as f:
            content = f.read()

        # Safely evaluate the assignments
        # Find the lines containing p and output
        p_line = next(line for line in content.splitlines() if line.startswith("p = "))
        output_line = next(line for line in content.splitlines() if line.startswith("output = "))

        p_str = p_line.split("=", 1)[1].strip()
        output_str = output_line.split("=", 1)[1].strip()

        # Use ast.literal_eval for safe parsing of the literal string
        # This is a standard Python library function available within SageMath
        p = ast.literal_eval(p_str)
        output = ast.literal_eval(output_str)

    except FileNotFoundError:
        print(f"Error: File '{filename}' not found.")
        return None, None
    except Exception as e:
        print(f"Error parsing file: {e}")
        return None, None

    return p, output

p, output = parse_output() 
R = Zmod(p) 
n_sq = len(output) // 6 
n = int(n_sq**0.5) 
print(n)

#Step1: Tạo pt + giải pt 
#making M and B: 
M = Matrix(R, n_sq, n_sq, 0) 
B = Matrix(R, n_sq, 1, 0)

for m in range(n_sq): 
    noise1 = output[6*m + 0] 
    noise2 = output[6*m + 1]
    noise3 = output[6*m + 2]
    noise4 = output[6*m + 3]
    noise5 = output[6*m + 4]
    s = output[6*m + 5] 

    R_m = R(s) - R(sum(noise1[i]*noise5[i] + noise4[i] for i in range(1000))) 
    B[m,0] = R_m 
    
    Wm = [[R(0)]*n for i in range(n)] 
    for i in range(1000): 
        j = noise2[i] 
        k = noise3[i] 
        Wm[j][k] += noise5[i]
    # Ta xếp Pij với k tăng trước i (0,0), (0, 1), (0, 2)...(1,0)...
    for j in range(n): 
        for k in range(n): 
            M[m, j*n+ k] = Wm[j][k]   

X = M.solve_right(B) 

Pjk_vals = [[R(0)]*n for i in range(n)] 
for j in range(n): 
    for k in range(n): 
        Pjk_vals[j][k] = X[j*n + k, 0] 

P00_inv = Pjk_vals[0][0].inverse() 
gcD, u, v = xgcd(1337, 1663) 
Yk_vals = [R(0)]*n 
Yk_vals[0] = R(1) 
for k in range(1, n): 
    P0k = Pjk_vals[0][k]
    Pk0 = Pjk_vals[k][0] 
    Yk_1337 = Pk0*P00_inv 
    Yk_1663 = P0k*P00_inv 
    Yk = (Yk_1337**u)*(Yk_1663**v) 
    Yk_vals[k] = int(Yk) 

#Tạo L
L = Matrix(ZZ, n+1, n+1, 0)
for i in range(n): 
    L[i, i] = -p 
for i in range(n): 
    L[n, i] = Yk_vals[i] 
L[n, n] = 2**32 
newL = L.LLL() 
print(newL.row(0))

Ouput:

(-1897021025, -3720483959, -1198507315, -2835181171, -3669596720, -4230456941, -3739620965, -3889969503, -3079380339, -2769052976, -919415916, -1494302837, -1658467444, -1074391089, -1388234351, -1361733486, -8147643262199398400)

Recorver:

setup = [-1897021025, -3720483959, -1198507315, -2835181171, -3669596720, -4230456941, -3739620965, -3889969503, -3079380339, -2769052976, -919415916, -1494302837, -1658467444, -1074391089, -1388234351, -1361733486, -8147643262199398400]
flag = [] 
for i in setup: 
    flag.append(chr((i*-1)%256))
print(''.join(flag))

Flag: KMACTF{aw3s0me_s0lut1on
## Stranger Things
Lời giải mình để trong Link này:
https://hackmd.io/@3ku7Xf2QSBydV4qF-RWO7g/ryAZ2KEWxx