# Perfect day (easy)
## Description
**Challenge code**

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}")

Trước hết thì cũng phân tích challenge code để ta tìm được hướng giải mã

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)

Ở đoạn code này thì ta thấy được là cần đoán đúng tên bài hát 32 lần thì ta sẽ nhận về **flag**
Ngoài ra thì sau mỗi lần đoán đúng thì ta sẽ được cung cấp giá trị $hint$ và $p$ mới trong đó giá trị $hint$ được tính như sau:

m = bytes_to_long(padded_song)

$$
hint = (1 + k.p)^m \mod p^2
$$
Bằng cách sử dụng khai triển nhị thức Newton thì ta có được phương trình mới
$$
hint ≡ 1 + m.k.p \mod p^2
$$

$$
(hint - 1) / p ≡ m.k \mod p
$$
Đặt `r = (hint - 1) / p`

Dựa vào điều kiện có ở `k = random.randint(1, 4096)`, thì với mỗi round ta sẽ có cặp $(p,hint)$ và khi đấy ta sẽ xem bài hát nào cho ra giá trị $k$ thoả mãn `1 <= k <= 4096` thì bài hát đấy là đáp án đúng cho round đó:
$$
k = r.m^{-1} \mod p
$$

## Code

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

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"
]

def recover_song(p, hint, soundtrack):
    r = ((hint - 1) // p) % p
    for song in soundtrack:
        padded = song + b"0xff" * (256 - len(song))
        m = bytes_to_long(padded)
        try:
            inv_m = inverse(m, p)
        except ValueError:
            continue
        k = (r * inv_m) % p
        if 1 <= k <= 4096:
            return song.decode()
    return None

host = '36.50.177.41'
port = 5001

r = remote(host,port)
for i in range(32):
    p_line = r.recvline_contains(b'p = ').strip()
    hint_line = r.recvline_contains(b'hint = ').strip()
    p = int(p_line.split(b'=')[1])
    hint = int(hint_line.split(b'=')[1])
    print(f"[Round {i+1}] p = {p}\n[Round {i+1}] hint = {hint}")
    song = recover_song(p,hint,soundtrack)
    r.sendline(song)
    rep = r.recvline().decode().strip()
    print(rep)
    if 'Wrong' in rep:
        break

flag = r.recvall().decode()
print(flag)

## Flag

KMACTF{did_you_enjoy_soundtrack_perfect_days}

# Make some noise (medium)
## Description
**Challenge code**

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")

**File [out.txt](https://docs.google.com/document/d/1jgpvEIuXZ9Jw42IRz8U-ecwRZjBePB4DZQY46YrSkus/edit?usp=sharing)**

Bắt đầu với `setup`, thì nó ban đầu là 1 danh sách chứa các giá trị ngẫu nhiên 32 bit trong đó số lượng giá trị bằng với độ dài của flag `flag = flag[7: -1]` . Sau đó

setup = [randint(0, 2**32) for _ in range(len(flag))]

Mỗi kí tự `f` trong `flag` được `xor` với một giá trị được tạo từ `pad `tương ứng:
- `pad >> 8`: dịch phải pad 8 bit, lúc này sẽ loại bỏ 8 bit thấp của pad
- `(pad >> 8) << 8`: tiếp tục dịch trái 8 bit, lúc này pad sẽ được thêm 8 bit 0 vào cuối
- Như vậy có nghĩa là 8 bit thấp của `f` sẽ không bị thay đổi khi thực hiện `xor` mà chỉ có các bit cao mới có thể bị thay đổi.

Tiếp đến với phần tạo `output`, thì vòng lặp chính chạy `len(flag)^2` lần mà trong mỗi lần lặp thì:
- 5 danh sách chứa các giá trị ngẫu nhiên `noise1`, `noise2`, `noise3`, `noise4`, `noise5` được tạo. Trong đó noise 1, 4 và 5 chứa các số nguyên ngẫu nhiên 32 bit còn noise 2 và 3 là các chỉ số của setup.
- Mỗi giá trị $s$ được tính toán theo công thức sau:
$$
s
\;\equiv\;
\sum_{i=0}^{999}
\Bigl(
\text{noise5}_i \,\cdot\,
\bigl(
\text{noise1}_i
\;+\;
\bigl(\text{setup}[{\text{noise2}_i}]\bigr)^{1337} \bmod p
\;\times\;
\bigl(\text{setup}[{\text{noise3}_i}]\bigr)^{1663} \bmod p
\bigr)
\;+\;
\text{noise4}_i
\Bigr)
\;\pmod{p}
$$

Từ phần phân tích `setup`, thì ta có thể suy ra được `setup[i] = flag[i] ^^ (pad[i] & 0xFFFFFF00)`, tức là 8 bit thấp của `setup[i]` là 8 bit thấp của `flag[i]`. Do đó có thể suy ra là `setup[i] & 0xFF = flag[i]`.

Vậy để tìm được flag thì ta cần tìm được `setup[i]`

Từ phương trình của $s$ ta có thể suy ra được như sau:
$$
s
\;-\;
\sum_{i=0}^{999}
\bigl(\,
\text{noise5}_i \,\cdot\, \text{noise1}_i
\;+\;
\text{noise4}_i
\bigr)
\;\equiv\;
\sum_{i=0}^{999}
\bigl(
\text{noise5}_i \,\cdot\, X_{\text{noise2}_i,\;\text{noise3}_i}
\bigr)
\pmod{p}
$$

Trong đó $X_{\text{noise2}_i,\;\text{noise3}_i}$
= $\bigl(\,(\text{setup}[noise2_i])^{1337} \bmod p \;\times\; (\text{setup}[noise3_i])^{1663} \bmod p\bigr)
\;\pmod{p}$
= $\bigl(\,(\text{setup}_j)^{1337} \bmod p \;\times\; (\text{setup}_k)^{1663} \bmod p\bigr)
\;\pmod{p}$

Lúc này ta sẽ giải phương trình `A.X = b` trong trường $p$ để tìm các giá trị $X$.

Tìm được $X_{j,k}$ thì để tìm lại các thành phần của `setup` bằng cách xét trường hợp $j=k$ thì ta có được như sau:
$$
X_{j,k} = \bigl(\,(\text{setup}_j)^{1337} \bmod p \;\times\; (\text{setup}_k)^{1663} \bmod p\bigr)
\;\pmod{p}
$$

$$
X_{j,j} = \bigl(\,(\text{setup}_j)^{1337} \bmod p \;\times\; (\text{setup}_j)^{1663} \bmod p\bigr)
\;\pmod{p}
$$

$$
X_{j,j} = \bigl(\,(\text{setup}_j)^{3000} \bmod p )
\;\pmod{p}
$$

Trong đó $j$ chạy từ $0$ đến $L-1$, tức là ta sẽ tìm được từ $setup[0]$ đến $setup[L-1]$, ghép lại là có được $flag$ :broken_heart:

## Code

from sage.all import *
import ast

def infer_L(output):
    n = len(output)
    if n % 6 != 0 or n == 0:
        raise ValueError(f"Chiều dài output_data ({n}) không hợp lệ.")
    L2 = n // 6
    L = Integer(sqrt(L2))
    if L * L != L2 or L == 0:
        raise ValueError(f"L^2={L2} không phải số chính phương >0.")
    return L


def find_A_b(f, output, L):
    m = len(output) // 6
    A = Matrix(f, m, L * L)
    b = vector(f, m)

    for k in range(m):
        block = output[6*k : 6*k + 6]
        noise1, noise2, noise3, noise4, noise5, s = block
        s = f(s)
        const = sum((f(n5) * f(n1) + f(n4)) for n1, n4, n5 in zip(noise1, noise4, noise5))
        b[k] = s - const
        for u, v, w in zip(noise2, noise3, noise5):
            idx = int(u) * L + int(v)
            A[k, idx] += f(w)

    return A, b


def recover_flag(sol, p, L):
    chars = []
    for j in range(L):
        Vj = sol[j*L + j]
        roots = Vj.nth_root(3000, all=True)
        ch = '?'
        for r in (roots if isinstance(roots, list) else [roots]):
            r = Integer(r)
            if 0 <= r < 2**32:
                c = int(r & 0xFF)
                if 32 <= c <= 126:
                    ch = chr(c)
                    break
        chars.append(ch)
    return ''.join(chars)

with open("out.txt") as f:
    p = Integer(f.readline().split('=')[1].strip())
    output = ast.literal_eval(f.readline().split('=')[1].strip())
f = GF(p)
L = infer_L(output)
A, b = find_A_b(f, output, L)
sol = A.solve_right(b)
flag = recover_flag(sol, p, L)
print(f"KMACTF{{{flag}}}")

## Flag

KMACTF{aw3s0me_s0lut1on}

# Stranger things (hard)
## Description
**Challenge code**

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

#p = getPrime(64)
p = 12267883553178394373
Fp = GF((p, 3))

FLAG = b'KMACTF{fake_flag}'

s = Fp.from_integer(bytes_to_long(FLAG))

set_random_seed(1337)
out = []
for i in range(15):
    a, b = Fp.random_element(), Fp.random_element()
    s = a * s + b
    out.extend(s)

print([x >> 57 for x in out])
[43, 80, 59, 18, 3, 12, 77, 20, 25, 68, 68, 30, 47, 73, 78, 52, 62, 68, 84, 39, 32, 16, 1, 55, 39, 58, 48, 8, 72, 13, 63, 34, 19, 44, 45, 56, 82, 76, 10, 46, 69, 28, 69, 78, 29]

Cùng phân tích source code:

`Fp = GF((p, 3))`: tạo ra một trường mở rộng $F_{p^3}$ mà trong đó các phần tử trong trường này là các đa thức có bậc nhỏ hơn 3.

Để tìm được $flag$ ta cần tìm được $s_0$ hay chính là `s = Fp.from_integer(bytes_to_long(FLAG))`

Vì đã có $seed$ nên ta có thể dễ dàng khôi phục được các cặp giá trị $(a,b)$. Ngoài ra hệ thống cũng có ta biết được phần thông tin rõ rỉ là 7 bit cao nhất của mỗi hệ số.

## Code

from sage.all import *
set_random_seed(1337)

p = 12267883553178394373
Fp = GF((p, 3))
trunc = 57

leak = [43, 80, 59, 18, 3, 12, 77, 20, 25, 68, 68, 30,
        47, 73, 78, 52, 62, 68, 84, 39, 32, 16, 1, 55,
        39, 58, 48, 8, 72, 13, 63, 34, 19, 44, 45, 56,
        82, 76, 10, 46, 69, 28, 69, 78, 29]

n = len(leak) // 3

a_list = []
b_list = []
for i in range(n):
    a_list.append(Fp.random_element())
    b_list.append(Fp.random_element())

c = [Fp(1)]
d = [Fp(0)]
for i in range(1, n):
    c.append(c[-1] * a_list[i])
    d.append(a_list[i] * d[-1] + b_list[i])

def embed(M):
    M = matrix(M)
    R = zero_matrix(ZZ, M.nrows(), 3 * M.ncols())
    R[:, 0::3] = M.apply_map(lambda z: z[0])
    R[:, 1::3] = M.apply_map(lambda z: z[1])
    R[:, 2::3] = M.apply_map(lambda z: z[2])
    return R

def unembed_vec(v):
    return vector([
        v[i] + v[i+1] * Fp.gen() + v[i+2] * Fp.gen()**2
        for i in range(0, len(v), 3)
    ])

As = matrix(Fp, [[c_i for c_i in c]])
L = embed(As.stack(As * Fp.gen()).stack(As * Fp.gen()**2))
L = L.stack((identity_matrix(3 * n) * p)[3:])

B_ZZ = vector(embed([[d_i] for d_i in d]))

lb = vector([x << trunc for x in leak]) - B_ZZ
ub = vector([(x + 1) << trunc for x in leak]) - B_ZZ
mid = (lb + ub) / 2

def cvp(B, t):
    t = vector(ZZ, t)
    B = B.LLL()
    S = B[-1].norm().round() + 1
    L2 = block_matrix([
        [B, zero_matrix(ZZ, B.nrows(), 1)],
        [matrix(t), matrix(1, 1, S)]
    ])
    for v in L2.LLL():
        if abs(v[-1]) == S:
            return t - v[:-1] * sign(v[-1])
    raise ValueError("CVP failed")

v = cvp(L, mid) + B_ZZ
seq = unembed_vec(v)

s0 = (seq[0] - b_list[0]) / a_list[0]
flag_int = s0.to_integer()
flag_bytes = flag_int.digits(256)[::-1]
flag = ''
for i in flag_bytes:
    flag += chr(i)
print(flag)

## Flag

KMACTF{y0u_ar3_4mazing}

## Note
- Bài này trong thời gian giải diễn ra thì mình chưa làm được và sau giải thì mình được a Tuệ hint mới giải ra :broken_heart: