<h1 style="text-align:center; color:#7e9bf3">
BITSCTF 2026
</h1>

Dưới đây là lời giải cho một số thử thách mật mã học của cuộc thi **BITSCTF 2026**, tuy không quá khó nhưng có một số bài hay.

## Aliens Eat Snacks

:::spoiler <b>README.md</b>

# AES

I found an AES implementation online and used it to encrypt the flag. I heard AES is very secure so I used it to encrypt the flag.

## Files

- `aes.py` - The AES implementation
- `output.txt` - Some encrypted data for you to analyze

## Flag Format

`BITSCTF{...}`

:::

:::spoiler <b>aes.py</b>

#!/usr/bin/env python3

from typing import List

IRREDUCIBLE_POLY = 0x11B

def gf_mult(a: int, b: int) -> int:
    result = 0
    for _ in range(8):
        if b & 1:
            result ^= a
        hi_bit = a & 0x80
        a = (a << 1) & 0xFF
        if hi_bit:
            a ^= (IRREDUCIBLE_POLY & 0xFF)
        b >>= 1
    return result

def gf_pow(base: int, exp: int) -> int:
    if exp == 0:
        return 1
    result = 1
    while exp > 0:
        if exp & 1:
            result = gf_mult(result, base)
        base = gf_mult(base, base)
        exp >>= 1
    return result

def gf_inv(a: int) -> int:
    if a == 0:
        return 0
    return gf_pow(a, 254)

def generate_sbox() -> List[int]:
    sbox = []
    for x in range(256):
        val = gf_pow(x, 23)
        val ^= 0x63
        sbox.append(val)
    return sbox

def generate_inv_sbox(sbox: List[int]) -> List[int]:
    inv_sbox = [0] * 256
    for i, v in enumerate(sbox):
        inv_sbox[v] = i
    return inv_sbox

SBOX = generate_sbox()
INV_SBOX = generate_inv_sbox(SBOX)

MIX_MATRIX = [
    [0x02, 0x03, 0x01, 0x01],
    [0x01, 0x02, 0x03, 0x01],
    [0x01, 0x01, 0x02, 0x03],
    [0x03, 0x01, 0x01, 0x02]
]

INV_MIX_MATRIX = [
    [0x0E, 0x0B, 0x0D, 0x09],
    [0x09, 0x0E, 0x0B, 0x0D],
    [0x0D, 0x09, 0x0E, 0x0B],
    [0x0B, 0x0D, 0x09, 0x0E]
]

RCON = [0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1B, 0x36]

def key_expansion(key: bytes, rounds: int = 6) -> List[bytes]:
    assert len(key) == 16
    words = []
    for i in range(4):
        words.append(list(key[4*i:4*i+4]))
    
    for i in range(4, 4 * (rounds + 1)):
        temp = words[i-1][:]
        if i % 4 == 0:
            temp = temp[1:] + temp[:1]
            temp = [SBOX[b] for b in temp]
            temp[0] ^= RCON[(i // 4) - 1]
        words.append([words[i-4][j] ^ temp[j] for j in range(4)])
    
    round_keys = []
    for r in range(rounds + 1):
        rk = bytes()
        for i in range(4):
            rk += bytes(words[r*4 + i])
        round_keys.append(rk)
    
    return round_keys

def sub_bytes(state: List[List[int]]) -> List[List[int]]:
    return [[SBOX[state[r][c]] for c in range(4)] for r in range(4)]

def inv_sub_bytes(state: List[List[int]]) -> List[List[int]]:
    return [[INV_SBOX[state[r][c]] for c in range(4)] for r in range(4)]

def shift_rows(state: List[List[int]]) -> List[List[int]]:
    result = [[0]*4 for _ in range(4)]
    for r in range(4):
        for c in range(4):
            result[r][c] = state[r][(c + r) % 4]
    return result

def inv_shift_rows(state: List[List[int]]) -> List[List[int]]:
    result = [[0]*4 for _ in range(4)]
    for r in range(4):
        for c in range(4):
            result[r][c] = state[r][(c - r) % 4]
    return result

def mix_columns(state: List[List[int]]) -> List[List[int]]:
    result = [[0]*4 for _ in range(4)]
    for c in range(4):
        for r in range(4):
            val = 0
            for i in range(4):
                val ^= gf_mult(MIX_MATRIX[r][i], state[i][c])
            result[r][c] = val
    return result

def inv_mix_columns(state: List[List[int]]) -> List[List[int]]:
    result = [[0]*4 for _ in range(4)]
    for c in range(4):
        for r in range(4):
            val = 0
            for i in range(4):
                val ^= gf_mult(INV_MIX_MATRIX[r][i], state[i][c])
            result[r][c] = val
    return result

def add_round_key(state: List[List[int]], round_key: bytes) -> List[List[int]]:
    result = [[0]*4 for _ in range(4)]
    for r in range(4):
        for c in range(4):
            result[r][c] = state[r][c] ^ round_key[r + 4*c]
    return result

def bytes_to_state(data: bytes) -> List[List[int]]:
    state = [[0]*4 for _ in range(4)]
    for i in range(16):
        state[i % 4][i // 4] = data[i]
    return state

def state_to_bytes(state: List[List[int]]) -> bytes:
    result = []
    for c in range(4):
        for r in range(4):
            result.append(state[r][c])
    return bytes(result)

class AES:
    ROUNDS = 4
    
    def __init__(self, key: bytes):
        if len(key) != 16:
            raise ValueError
        self.key = key
        self.round_keys = key_expansion(key, self.ROUNDS)
    
    def encrypt(self, plaintext: bytes) -> bytes:
        if len(plaintext) != 16:
            raise ValueError
        
        state = bytes_to_state(plaintext)
        state = add_round_key(state, self.round_keys[0])
        
        for r in range(1, self.ROUNDS):
            state = sub_bytes(state)
            state = shift_rows(state)
            state = mix_columns(state)
            state = add_round_key(state, self.round_keys[r])
        
        state = sub_bytes(state)
        state = shift_rows(state)
        state = add_round_key(state, self.round_keys[self.ROUNDS])
        
        return state_to_bytes(state)
    
    def decrypt(self, ciphertext: bytes) -> bytes:
        if len(ciphertext) != 16:
            raise ValueError
        
        state = bytes_to_state(ciphertext)
        state = add_round_key(state, self.round_keys[self.ROUNDS])
        state = inv_shift_rows(state)
        state = inv_sub_bytes(state)
        
        for r in range(self.ROUNDS - 1, 0, -1):
            state = add_round_key(state, self.round_keys[r])
            state = inv_mix_columns(state)
            state = inv_shift_rows(state)
            state = inv_sub_bytes(state)
        
        state = add_round_key(state, self.round_keys[0])
        return state_to_bytes(state)

:::

:::spoiler <b>output.txt</b>

key_hint: 26ab77cadcca0ed41b03c8f2e5
encrypted_flag: 8e70387dc377a09cbc721debe27c468157b027e3e63fe02560506f70b3c72ca19130ae59c6eef47b734bb0147424ec936fc91dc658d15dee0b69a2dc24a78c44
num_samples: 1000
samples:
376f73334dc9db2a4d20734c0783ac69,9070f81f4de789663820e8924924732b
a4da3590273d7b33b2a4e73210c38a05,f501ed98c671cf1a23e5c028504d2603
7e52c00ceda7a3c1b338d90721615910,36ddbc3506b0a1844677ceb4006509f1
c1a10df2e2afc6ee1397ea1422752472,a3ec80650417136efe87d17257edc161
687bd6c20eb900bc06a2573a9233543f,efa5e5d84d48496206c1d94c98531980
56f198dc16c838e3afe133f21497fc9b,84d738ce296771708f6bfb307dbc9a30
8e0cb0a1db81a3cc2305e2d8d098652c,4fa59976ad0c7ffed7de91c99e0cd090
db436c344acbb5e6d750c5f67721ea1a,b093e04b8a3830fce2bcb894d2a7eb2c
d07bd532b4be566a227bd7933d0c5c87,a431d655311af7d285278f6589d145cb
52e4f5216508171fa0c25963f0d4ae7d,0afa353e68119e9aca76ed1d7f91dab8
1f2f693083467abfa779b5f28bbebff1,f7e0521636b684245c110b217abae229
... (có khoảng 1000 mẫu)

:::

Chỉ cần chú ý cái đoạn này trong phần `aes.py`:

    assert len(key) == 16
    words = []

Chúng ta đã được biết 13 bytes liền kề nhau của khóa rồi, việc còn lại chỉ là brute-force 3 bytes còn lại thôi.

Dưới đây là lời giải cho toàn bộ thử thách, có sử dụng đa tiến trình:

:::spoiler <b style="color:#7e9bf3">solution.py</b>

import multiprocessing as mp
from tqdm import tqdm

HINT = bytes.fromhex("26ab77cadcca0ed41b03c8f2e5")
PT = bytes.fromhex("376f73334dc9db2a4d20734c0783ac69")
CT = bytes.fromhex("9070f81f4de789663820e8924924732b")
ENC_FLAG = bytes.fromhex("8e70387dc377a09cbc721debe27c468157b027e3e63fe02560506f70b3c72ca19130ae59c6eef47b734bb0147424ec936fc91dc658d15dee0b69a2dc24a78c44")

def check_keys_for_b1(b1: int):
    from aes import AES
    
    for b2 in range(256):
        for b3 in range(256):
            key = HINT + bytes([b1, b2, b3])
            cipher = AES(key)
            
            if cipher.encrypt(PT) == CT:
                return key
    return None

def main():
    found_key = None
    cores = mp.cpu_count()
    
    # Sử dụng Pool để chạy đa luồng
    with mp.Pool(cores) as pool:
        # pool.imap_unordered giúp trả về kết quả ngay khi 1 worker xong mà không cần đợi theo thứ tự
        # Chúng ta bọc tqdm quanh iterable để tạo thanh tiến trình cho 256 tasks
        tasks = range(256)
        
        for result in tqdm(pool.imap_unordered(check_keys_for_b1, tasks), total=256, desc="[+] First byte iteration", unit=" task"):
            if result is not None:
                found_key = result
                tqdm.write(f"[!] Found key: {found_key.hex()}")
                pool.terminate()  # Lập tức hủy các tiến trình còn lại để tiết kiệm tài nguyên
                break

    # Nếu tìm thấy key, tiến hành giải mã flag
    if found_key:
        from aes import AES
        cipher = AES(found_key)
        
        # Giải mã từng block 16 bytes (ECB mode)
        flag_blocks = []
        for i in range(0, len(ENC_FLAG), 16):
            block = ENC_FLAG[i:i+16]
            flag_blocks.append(cipher.decrypt(block))
            
        flag = b"".join(flag_blocks)
        
        print("[!] Got flag:", flag.strip().decode())
    else:
        print("[-] Something's gone wrong!")

if __name__ == '__main__':
    # Lưu ý: Nếu chạy trên Windows, cần để mọi thứ chạy trong block if __name__ == '__main__' (mình từng thử không chạy kiểu này rồi và nó không dễ chịu lắm đâu)
    main()

# [!] Got flag: BITSCTF{7h3_qu1ck_br0wn_f0x_jump5_0v3r_7h3_l4zy_d0g}

:::

:::success
**Flag: BITSCTF{7h3_qu1ck_br0wn_f0x_jump5_0v3r_7h3_l4zy_d0g}**
:::

## Super DES

:::spoiler <b>server.py</b>

from Crypto.Cipher import DES3, DES
from Crypto.Random import get_random_bytes
from Crypto.Util.Padding import pad, unpad

def adjust_key(key8: bytes) -> bytes:
    out = bytearray()
    for b in key8:
        b7 = b & 0xFE                
        ones = bin(b7).count("1")     
        out.append(b7 | (ones % 2 == 0))  
    return bytes(out)

flag = b'REDACTED'
k1 = adjust_key(get_random_bytes(8))

def triple_des(pt, k2, k3):
    cipher = DES3.new(k3 + k2 + k1, DES3.MODE_ECB)
    return cipher.encrypt(pad(pt, 8))

def triple_des_ultra_secure_v1(pt, k2, k3):
    cipher1 = DES.new(k1, DES.MODE_ECB)
    cipher2 = DES.new(k2, DES.MODE_ECB)
    cipher3 = DES.new(k3, DES.MODE_ECB)

    return cipher1.encrypt(cipher2.encrypt(cipher3.encrypt(pad(pt, 8))))

def triple_des_ultra_secure_v2(pt, k2, k3):
    cipher1 = DES.new(k1, DES.MODE_ECB)
    cipher2 = DES.new(k2, DES.MODE_ECB)
    cipher3 = DES.new(k3, DES.MODE_ECB)

    return cipher1.decrypt(cipher2.encrypt(cipher3.encrypt(pad(pt, 8))))

while True:
    print("I will prove its secure af by letting you choose k2 and k3")
    k2 = adjust_key(bytes.fromhex(input("enter k2 hex bytes >")))
    k3 = adjust_key(bytes.fromhex(input("enter k3 hex bytes >")))
    
    print("1. triple des\n2. ultra secure v1\n3. ultra secure v2\n4. exit")
    option = int(input("enter option >"))

    print("1. encrypt flag\n2. encrypt your own text")
    option_ = int(input("enter option >"))
    
    if k2 == k3:
        print("ok its not thaaat secure, try again")
        continue

    if option_ == 2:
        pt = bytes.fromhex(input("enter hex bytes >"))
    else:
        pt = flag
    if option == 1:
        print(f"ciphertext : {triple_des(pt, k2, k3).hex()}")
    elif option == 2:
        print(f"ciphertext : {triple_des_ultra_secure_v1(pt, k2, k3).hex()}")
    elif option == 3:
        print(f"ciphertext : {triple_des_ultra_secure_v2(pt, k2, k3).hex()}")
    else:
        exit()

:::

Bài này liên quan đến khóa bán yếu (**semi-weak keys**) trong DES, cụ thể tồn tại hai khóa $k_A \neq k_B$ thỏa mãn $E_{k_A}(E_{k_B}(P)) = P$ với văn bản rõ $P$ bất kỳ.
Để đọc thêm về cái này thì bạn có thể đọc [tại đây](https://en.wikipedia.org/wiki/Weak_key#Weak_keys_in_DES) (có cả danh sách khóa bán yếu cho bạn tha hồ lựa chọn).

Trong server, chúng ta được chọn hai khóa $k_2, k_3$ và khóa $k_1$ sẽ là ngẫu nhiên do server sinh ra, như vậy chúng ta có 3 bước tấn công rất bài bản như sau:

**Bước 1: Lấy bản mã của flag qua `ultra_secure_v1`**
Hàm `triple_des_ultra_secure_v1` mã hóa flag theo công thức:
$$
C_{1} = E_{k_1}(E_{k_2}(E_{k_3}(\text{pad}_8(\text{flag}))))
$$
Chúng ta sẽ truyền cặp khóa bán yếu $k_2$ và $k_3$, biểu thức thu gọn lại thành:
$$C_{1} = E_{k_1}(\text{pad}_8(\text{flag}))$$

**Bước 2: Dùng `ultra_secure_v2` làm oracle giải mã**
Chúng ta sẽ dùng $C_{1}$ làm plaintext đầu vào cho `triple_des_ultra_secure_v2` cũng như tiếp tục sử dụng cặp khóa bán yếu $k_2, k_3$. Sau đợt mã hóa thứ nhất, $C_1$ đã có độ dài byte là bội của 8 rồi, qua lần mã hóa thứ hai thì lại tiếp tục thì được đệm thêm 8 byte nữa trở thành $C_1 \parallel \text{pad_block}$.
Khi vào hàm `triple_des_ultra_secure_v2`, ta có biểu thức sau:
$$
\begin{align}
C_2 &= D_{k_1}(E_{k_2}(E_{k_3}(C_{1} \parallel \text{pad_block}))) \\
&= D_{k_1}(C_{1} \parallel \text{pad_block}) \\
&= D_{k_1}(E_{k_1}(\text{pad}_8(\text{flag})) \parallel \text{pad_block})
\end{align}
$$

Vì DES được hoạt động ở chế độ ECB (Electronic Codebook) nên các khối 8 byte sẽ được mã hóa độc lập với nhau, do đó:
$$
\begin{align}
C_2 &= D_{k_1}(E_{k_1}(\text{pad}_8(\text{flag})) \parallel \text{pad_block}) \\
&= D_{k_1}(E_{k_1}(\text{pad}_8(\text{flag}))) \parallel D_{k_1}(\text{pad_block}) \\
&= \text{pad}_8(\text{flag}) \parallel D_{k_1}(\text{pad_block})
\end{align}
$$

Đến đây ta chỉ loại bỏ 8 byte cuối cùng của $C_2$ và sau đó bỏ luôn các byte đệm thì sẽ ra được flag.

Dưới đây là toàn bộ lời giải cho thử thách này:

:::spoiler <b style="color:#7e9bf3">solution.py</b>

from pwn import remote
from Crypto.Util.Padding import unpad

HOST = "20.193.149.152"
PORT = 1340

connection = remote(HOST, PORT)

k2 = b"E0FEE0FEF1FEF1FE"
k3 = b"FEE0FEE0FEF1FEF1"

connection.sendlineafter(b"enter k2 hex bytes >", k2)
connection.sendlineafter(b"enter k3 hex bytes >", k3)
connection.sendlineafter(b"enter option >", b"2")
connection.sendlineafter(b"enter option >", b"1")

connection.recvuntil(b"ciphertext : ")
c2_hex = connection.recvline().strip()

connection.sendlineafter(b"enter k2 hex bytes >", k2)
connection.sendlineafter(b"enter k3 hex bytes >", k3)
connection.sendlineafter(b"enter option >", b"3")
connection.sendlineafter(b"enter option >", b"2")
connection.sendlineafter(b"enter hex bytes >", c2_hex)

connection.recvuntil(b"ciphertext : ")
c3_hex = connection.recvline().strip().decode()

connection.close()

raw_flag = bytes.fromhex(c3_hex)[:-8]
flag = unpad(raw_flag, 8).decode()

connection.success(f"Got flag: {flag}")
# [+] Got flag: BITSCTF{5up3r_d35_1z_n07_53cur3}

:::

:::success
**Flag: BITSCTF{5up3r_d35_1z_n07_53cur3}**
:::

## Insane Curves

:::spoiler <b>description.txt</b>

I found a secure communication channel using my Too Genus Curve.
However, the curve parameters look... insane.
The curve equation is y^2 = f(x) where f(x) is degree 6.
Can you break it? bahahahhahahahhahahhahahahahhahahahah

:::

:::spoiler <b>val.txt</b>

p=129403459552990578380563458675806698255602319995627987262273876063027199999999
f_coeffs=[87455262955769204408909693706467098277950190590892613056321965035180446006909, 12974562908961912291194866717212639606874236186841895510497190838007409517645, 11783716142539985302405554361639449205645147839326353007313482278494373873961, 55538572054380843320095276970494894739360361643073391911629387500799664701622, 124693689608554093001160935345506274464356592648782752624438608741195842443294, 52421364818382902628746436339763596377408277031987489475057857088827865195813, 50724784947260982182351215897978953782056750224573008740629192419901238915128]
G_u=[95640493847532285274015733349271558012724241405617918614689663966283911276425, 1]
G_v=[23400917335266251424562394829509514520732985938931801439527671091919836508525]
Q_u=[34277069903919260496311859860543966319397387795368332332841962946806971944007, 343503204040841221074922908076232301549085995886639625441980830955087919004, 1]
Q_v=[102912018107558878490777762211244852581725648344091143891953689351031146217393, 65726604025436600725921245450121844689064814125373504369631968173219177046384]
enc_flag=f6ca1f88bdb8e8dda17861b91704523f914564888c7138c24a3ab98902c10de5

:::

Bài này nói về [**đường cong Hyperelliptic**](https://en.wikipedia.org/wiki/Hyperelliptic_curve) nên nó rất nặng về mặt toán học, mình sẽ cố giải thích cho nó dễ hiểu mà vẫn đúng bản chất toán học nhất.


Vì $f(x) = 0$ vô nghiệm và đường cong được đặt trong trường $\mathbb{F}_p$ có $\text{char}(\mathbb{F}_p) \neq 2$ nên ta có công thức tính **genus** như sau:
$$
g = \left\lfloor \frac{\deg(f) - 1}{2} \right\rfloor = \left\lfloor \frac{6 - 1}{2} \right\rfloor = 2
$$

Khác với đường cong Elliptic ($g = 1$), đối với đường cong Hyperelliptic có $g \ge 2$, tập hợp các điểm đơn lẻ trên đường cong không tạo thành một cấu trúc nhóm toán học. Do đó, ta phải tìm một không gian mới bao trùm lên đường cong này để thực hiện hệ mật mã, và [**nhóm Jacobian**](https://en.wikipedia.org/wiki/Imaginary_hyperelliptic_curve#The_Jacobian_of_a_hyperelliptic_curve) chính là cấu trúc đó (tự đọc thêm về cái này vì nó rất nặng toán).

Vì việc tính toán bằng tọa độ trong lập trình cực kỳ phức tạp, nên người ta thường dùng **biểu diễn Mumford** để biểu diễn các điểm này trong lập trình để dễ tính toán (cũng chính là cách đề bài biểu diễn các điểm).
Biểu diễn Mumford sử dụng một cặp đa thức $u(x)$ và $v(x)$ để đại diện cho một phần tử trong Jacobian. Đó chính là lý do trong file `val.txt` và trong code, bạn không thấy tọa độ $(x, y)$ bình thường, mà thay vào đó là các mảng hệ số `G_u`, `G_v` và `Q_u`, `Q_v`.

Sau khi chuyển qua nhóm Jacobian rồi, ta sẽ nghĩ đến việc giải quyết bài toán này bằng logarithm rời rạc. Nếu là một nhóm Jacobian bình thường thì chúng ta chắc chắn sẽ không giải được, nhưng vì đây là một bài CTF nên ta có thể chắc rằng đây là nhóm Jacobian siêu dị thường.
Gọi $C$ là đường cong Hyperelliptic, thì đối với các đường cong siêu dị thường, bậc của Jacobian $J(C)$ có thể rơi vào các dạng sau:
- $(p + 1)^2$
- $(p - 1)^2$
- $p^2 + 1$
- $p^2 - p + 1$
- $p^2 + p + 1$

Ta nhìn vào số nguyên tố $p$ thì trường hợp đầu tiên ta nghĩ đến đó chính là $|J(C)| = (p+1)^2$, phân tích thừa số nguyên tố thử thì cũng toàn các ước nguyên tố nhỏ, vì vậy ta có thể dám chắc rằng cấp của nhóm Jacobian này là $(p + 1)^2$, và chúng ta chỉ cần dùng thuật toán Pohlig - Hellman là có thể giải ra flag rồi.

Dưới đây là toàn bộ lời giải cho thử thách này:
:::spoiler <b style="color:#7e9bf3">solution.py</b>

from sage.all import GF, PolynomialRing, HyperellipticCurve, discrete_log
from Crypto.Util.number import long_to_bytes
from Crypto.Util.strxor import strxor
import hashlib

# 1. Nạp số nguyên tố p và khởi tạo vành đa thức
p = 129403459552990578380563458675806698255602319995627987262273876063027199999999
Fp = GF(p)
R = PolynomialRing(Fp, name = 'x')
x = R.gen()

# 2. Khởi tạo đường cong C: y^2 = f(x)
f_coeffs = [87455262955769204408909693706467098277950190590892613056321965035180446006909, 12974562908961912291194866717212639606874236186841895510497190838007409517645, 11783716142539985302405554361639449205645147839326353007313482278494373873961, 55538572054380843320095276970494894739360361643073391911629387500799664701622, 124693689608554093001160935345506274464356592648782752624438608741195842443294, 52421364818382902628746436339763596377408277031987489475057857088827865195813, 50724784947260982182351215897978953782056750224573008740629192419901238915128]
f = sum(c * (x**i) for i, c in enumerate(f_coeffs))
C = HyperellipticCurve(f)
J = C.jacobian()

# 3. Nạp điểm G và Q trên nhóm Jacobian
G_u = R([95640493847532285274015733349271558012724241405617918614689663966283911276425, 1])
G_v = R([23400917335266251424562394829509514520732985938931801439527671091919836508525])
G = J(G_u, G_v)

Q_u = R([34277069903919260496311859860543966319397387795368332332841962946806971944007, 343503204040841221074922908076232301549085995886639625441980830955087919004, 1])
Q_v = R([102912018107558878490777762211244852581725648344091143891953689351031146217393, 65726604025436600725921245450121844689064814125373504369631968173219177046384])
Q = J(Q_u, Q_v)

print("[*] Solving HECDLP by using Pohlig-Hellman...")
# Khai thác lỗ hổng Supersingular bằng cách chỉ định luôn order của nhóm
N = (p + 1)**2
d = discrete_log(Q, G, ord=N, operation='+')
print(f"[+] Secret key d: {d}")

# 4. Giải mã Flag
enc_flag = bytes.fromhex("f6ca1f88bdb8e8dda17861b91704523f914564888c7138c24a3ab98902c10de5")

key = hashlib.sha256(str(d).encode()).digest()
flag = strxor(enc_flag, key).decode()

print("[!] Got flag:", flag)
# [!] Got flag: BITSCTF{7h15_15_w4y_2_63nu5_6n6}

:::

:::success
**Flag: BITSCTF{7h15_15_w4y_2_63nu5_6n6}**
:::

## Lattices Wreck Everything
:::spoiler <b>README.md</b>

# Leakithium

We managed to intercept some debug data from a faulty hardware security module implementing the Falcon signature scheme.
Can you use the leaked hints to recover the private key and decrypt the flag?

## Files
- `challenge.py`: The script used to generate the challenge.
- `challenge_data.json`: The public key, hints, and other parameters.
- `challenge_flag.enc`: The encrypted flag.
- Library files: Implementation of logic.

## Flag Format
`BITSCTF{...}`

:::
:::spoiler <b>common.py</b>

q = 12 * 1024 + 1
def split(f):
    n = len(f)
    f0 = [f[2 * i + 0] for i in range(n // 2)]
    f1 = [f[2 * i + 1] for i in range(n // 2)]
    return [f0, f1]
def merge(f_list):
    f0, f1 = f_list
    n = 2 * len(f0)
    f = [0] * n
    for i in range(n // 2):
        f[2 * i + 0] = f0[i]
        f[2 * i + 1] = f1[i]
    return f
def sqnorm(v):
    res = 0
    for elt in v:
        for coef in elt:
            res += coef ** 2
    return res

:::
:::spoiler <b>samplerz.py</b>

from math import floor
from os import urandom
MAX_SIGMA = 1.8205
INV_2SIGMA2 = 1 / (2 * (MAX_SIGMA ** 2))
RCDT_PREC = 72
LN2 = 0.69314718056
ILN2 = 1.44269504089
RCDT = [
    3024686241123004913666,
    1564742784480091954050,
    636254429462080897535,
    199560484645026482916,
    47667343854657281903,
    8595902006365044063,
    1163297957344668388,
    117656387352093658,
    8867391802663976,
    496969357462633,
    20680885154299,
    638331848991,
    14602316184,
    247426747,
    3104126,
    28824,
    198,
    1]
C = [
    0x00000004741183A3,
    0x00000036548CFC06,
    0x0000024FDCBF140A,
    0x0000171D939DE045,
    0x0000D00CF58F6F84,
    0x000680681CF796E3,
    0x002D82D8305B0FEA,
    0x011111110E066FD0,
    0x0555555555070F00,
    0x155555555581FF00,
    0x400000000002B400,
    0x7FFFFFFFFFFF4800,
    0x8000000000000000]


def basesampler(randombytes=urandom):
    u = int.from_bytes(randombytes(RCDT_PREC >> 3), "little")
    z0 = 0
    for elt in RCDT:
        z0 += int(u < elt)
    return z0


def approxexp(x, ccs):
    y = C[0]
    z = int(x * (1 << 63))
    for elt in C[1:]:
        y = elt - ((z * y) >> 63)
    z = int(ccs * (1 << 63)) << 1
    y = (z * y) >> 63
    return y


def berexp(x, ccs, randombytes=urandom):
    s = int(x * ILN2)
    r = x - s * LN2
    s = min(s, 63)
    z = (approxexp(r, ccs) - 1) >> s
    for i in range(56, -8, -8):
        p = int.from_bytes(randombytes(1), "little")
        w = p - ((z >> i) & 0xFF)
        if w:
            break
    return (w < 0)


def samplerz(mu, sigma, sigmin, randombytes=urandom):
    s = int(floor(mu))
    r = mu - s
    dss = 1 / (2 * sigma * sigma)
    ccs = sigmin / sigma

    while(1):
        z0 = basesampler(randombytes=randombytes)
        b = int.from_bytes(randombytes(1), "little")
        b &= 1
        z = b + (2 * b - 1) * z0
        x = ((z - r) ** 2) * dss
        x -= (z0 ** 2) * INV_2SIGMA2
        if berexp(x, ccs, randombytes=randombytes):
            return z + s

:::
:::spoiler <b>ntt_constants.py</b>

phi4_roots_Zq = [1479, 10810]
phi8_roots_Zq = [4043, 8246, 5146, 7143]
phi16_roots_Zq = [5736, 6553, 4134, 8155, 722, 11567, 1305, 10984]
phi32_roots_Zq = [1646, 10643, 1212, 11077, 5860, 6429, 3195, 9094, 2545, 9744, 3621, 8668, 3504, 8785, 3542, 8747]
phi64_roots_Zq = [4591, 7698, 5728, 6561, 5023, 7266, 5828, 6461, 4978, 7311, 1351, 10938, 3328, 8961, 5777, 6512, 2975, 9314, 563, 11726, 3006, 9283, 2744, 9545, 949, 11340, 2625, 9664, 4821, 7468, 2639, 9650]
...

:::
:::spoiler <b>ntt.py</b>

from common import split, merge, q
from ntt_constants import roots_dict_Zq, inv_mod_q
i2 = 6145
sqr1 = roots_dict_Zq[2][0]


def split_ntt(f_ntt):
    n = len(f_ntt)
    w = roots_dict_Zq[n]
    f0_ntt = [0] * (n // 2)
    f1_ntt = [0] * (n // 2)
    for i in range(n // 2):
        f0_ntt[i] = (i2 * (f_ntt[2 * i] + f_ntt[2 * i + 1])) % q
        f1_ntt[i] = (i2 * (f_ntt[2 * i] - f_ntt[2 * i + 1]) * inv_mod_q[w[2 * i]]) % q
    return [f0_ntt, f1_ntt]


def merge_ntt(f_list_ntt):
    f0_ntt, f1_ntt = f_list_ntt
    n = 2 * len(f0_ntt)
    w = roots_dict_Zq[n]
    f_ntt = [0] * n
    for i in range(n // 2):
        f_ntt[2 * i + 0] = (f0_ntt[i] + w[2 * i] * f1_ntt[i]) % q
        f_ntt[2 * i + 1] = (f0_ntt[i] - w[2 * i] * f1_ntt[i]) % q
    return f_ntt


def ntt(f):
    n = len(f)
    if (n > 2):
        f0, f1 = split(f)
        f0_ntt = ntt(f0)
        f1_ntt = ntt(f1)
        f_ntt = merge_ntt([f0_ntt, f1_ntt])
    elif (n == 2):
        f_ntt = [0] * n
        f_ntt[0] = (f[0] + sqr1 * f[1]) % q
        f_ntt[1] = (f[0] - sqr1 * f[1]) % q
    return f_ntt


def intt(f_ntt):
    n = len(f_ntt)
    if (n > 2):
        f0_ntt, f1_ntt = split_ntt(f_ntt)
        f0 = intt(f0_ntt)
        f1 = intt(f1_ntt)
        f = merge([f0, f1])
    elif (n == 2):
        f = [0] * n
        f[0] = (i2 * (f_ntt[0] + f_ntt[1])) % q
        f[1] = (i2 * inv_mod_q[1479] * (f_ntt[0] - f_ntt[1])) % q
    return f


def add_zq(f, g):
    assert len(f) == len(g)
    deg = len(f)
    return [(f[i] + g[i]) % q for i in range(deg)]


def neg_zq(f):
    deg = len(f)
    return [(- f[i]) % q for i in range(deg)]


def sub_zq(f, g):
    return add_zq(f, neg_zq(g))


def mul_zq(f, g):
    return intt(mul_ntt(ntt(f), ntt(g)))


def div_zq(f, g):
    try:
        return intt(div_ntt(ntt(f), ntt(g)))
    except ZeroDivisionError:
        raise


def add_ntt(f_ntt, g_ntt):
    return add_zq(f_ntt, g_ntt)


def sub_ntt(f_ntt, g_ntt):
    return sub_zq(f_ntt, g_ntt)


def mul_ntt(f_ntt, g_ntt):
    assert len(f_ntt) == len(g_ntt)
    deg = len(f_ntt)
    return [(f_ntt[i] * g_ntt[i]) % q for i in range(deg)]


def div_ntt(f_ntt, g_ntt):
    assert len(f_ntt) == len(g_ntt)
    deg = len(f_ntt)
    if any(elt == 0 for elt in g_ntt):
        raise ZeroDivisionError
    return [(f_ntt[i] * inv_mod_q[g_ntt[i]]) % q for i in range(deg)]

ntt_ratio = 1

:::
:::spoiler <b>fft_constants.py</b>

phi4_roots = [1.00000000000000j, -1.00000000000000j]
phi8_roots = [0.707106781186548 + 0.707106781186547j,
              -0.707106781186548 - 0.707106781186547j,
              0.707106781186548 - 0.707106781186547j,
              -0.707106781186548 + 0.707106781186547j]
...

:::
:::spoiler <b>fft.py</b>

from common import split, merge
from fft_constants import roots_dict
def split_fft(f_fft):
    n = len(f_fft)
    w = roots_dict[n]
    f0_fft = [0] * (n // 2)
    f1_fft = [0] * (n // 2)
    for i in range(n // 2):
        f0_fft[i] = 0.5 * (f_fft[2 * i] + f_fft[2 * i + 1])
        f1_fft[i] = 0.5 * (f_fft[2 * i] - f_fft[2 * i + 1]) * w[2 * i].conjugate()
    return [f0_fft, f1_fft]
def merge_fft(f_list_fft):
    f0_fft, f1_fft = f_list_fft
    n = 2 * len(f0_fft)
    w = roots_dict[n]
    f_fft = [0] * n
    for i in range(n // 2):
        f_fft[2 * i + 0] = f0_fft[i] + w[2 * i] * f1_fft[i]
        f_fft[2 * i + 1] = f0_fft[i] - w[2 * i] * f1_fft[i]
    return f_fft
def fft(f):
    n = len(f)
    if (n > 2):
        f0, f1 = split(f)
        f0_fft = fft(f0)
        f1_fft = fft(f1)
        f_fft = merge_fft([f0_fft, f1_fft])
    elif (n == 2):
        f_fft = [0] * n
        f_fft[0] = f[0] + 1j * f[1]
        f_fft[1] = f[0] - 1j * f[1]
    return f_fft
def ifft(f_fft):
    n = len(f_fft)
    if (n > 2):
        f0_fft, f1_fft = split_fft(f_fft)
        f0 = ifft(f0_fft)
        f1 = ifft(f1_fft)
        f = merge([f0, f1])
    elif (n == 2):
        f = [0] * n
        f[0] = f_fft[0].real
        f[1] = f_fft[0].imag
    return f
def add(f, g):
    assert len(f) == len(g)
    deg = len(f)
    return [f[i] + g[i] for i in range(deg)]
def neg(f):
    deg = len(f)
    return [- f[i] for i in range(deg)]
def sub(f, g):
    return add(f, neg(g))
def mul(f, g):
    return ifft(mul_fft(fft(f), fft(g)))
def div(f, g):
    return ifft(div_fft(fft(f), fft(g)))
def adj(f):
    return ifft(adj_fft(fft(f)))
def add_fft(f_fft, g_fft):
    return add(f_fft, g_fft)
def sub_fft(f_fft, g_fft):
    return sub(f_fft, g_fft)
def mul_fft(f_fft, g_fft):
    deg = len(f_fft)
    return [f_fft[i] * g_fft[i] for i in range(deg)]
def div_fft(f_fft, g_fft):
    assert len(f_fft) == len(g_fft)
    deg = len(f_fft)
    return [f_fft[i] / g_fft[i] for i in range(deg)]
def adj_fft(f_fft):
    deg = len(f_fft)
    return [f_fft[i].conjugate() for i in range(deg)]
fft_ratio = 1

:::
:::spoiler <b>ntrugen.py</b>

from fft import fft, ifft, add_fft, mul_fft, adj_fft, div_fft
from fft import add, mul, div, adj
from ntt import ntt
from common import sqnorm
from samplerz import samplerz


q = 12 * 1024 + 1


def karatsuba(a, b, n):
    if n == 1:
        return [a[0] * b[0], 0]
    else:
        n2 = n // 2
        a0 = a[:n2]
        a1 = a[n2:]
        b0 = b[:n2]
        b1 = b[n2:]
        ax = [a0[i] + a1[i] for i in range(n2)]
        bx = [b0[i] + b1[i] for i in range(n2)]
        a0b0 = karatsuba(a0, b0, n2)
        a1b1 = karatsuba(a1, b1, n2)
        axbx = karatsuba(ax, bx, n2)
        for i in range(n):
            axbx[i] -= (a0b0[i] + a1b1[i])
        ab = [0] * (2 * n)
        for i in range(n):
            ab[i] += a0b0[i]
            ab[i + n] += a1b1[i]
            ab[i + n2] += axbx[i]
        return ab


def karamul(a, b):
    n = len(a)
    ab = karatsuba(a, b, n)
    abr = [ab[i] - ab[i + n] for i in range(n)]
    return abr


def galois_conjugate(a):
    n = len(a)
    return [((-1) ** i) * a[i] for i in range(n)]


def field_norm(a):
    n2 = len(a) // 2
    ae = [a[2 * i] for i in range(n2)]
    ao = [a[2 * i + 1] for i in range(n2)]
    ae_squared = karamul(ae, ae)
    ao_squared = karamul(ao, ao)
    res = ae_squared[:]
    for i in range(n2 - 1):
        res[i + 1] -= ao_squared[i]
    res[0] += ao_squared[n2 - 1]
    return res


def lift(a):
    n = len(a)
    res = [0] * (2 * n)
    for i in range(n):
        res[2 * i] = a[i]
    return res


def bitsize(a):
    val = abs(a)
    res = 0
    while val:
        res += 8
        val >>= 8
    return res


def reduce(f, g, F, G):
    n = len(f)
    size = max(53, bitsize(min(f)), bitsize(max(f)), bitsize(min(g)), bitsize(max(g)))

    f_adjust = [elt >> (size - 53) for elt in f]
    g_adjust = [elt >> (size - 53) for elt in g]
    fa_fft = fft(f_adjust)
    ga_fft = fft(g_adjust)

    while(1):
        Size = max(53, bitsize(min(F)), bitsize(max(F)), bitsize(min(G)), bitsize(max(G)))
        if Size < size:
            break

        F_adjust = [elt >> (Size - 53) for elt in F]
        G_adjust = [elt >> (Size - 53) for elt in G]
        Fa_fft = fft(F_adjust)
        Ga_fft = fft(G_adjust)

        den_fft = add_fft(mul_fft(fa_fft, adj_fft(fa_fft)), mul_fft(ga_fft, adj_fft(ga_fft)))
        num_fft = add_fft(mul_fft(Fa_fft, adj_fft(fa_fft)), mul_fft(Ga_fft, adj_fft(ga_fft)))
        k_fft = div_fft(num_fft, den_fft)
        k = ifft(k_fft)
        k = [int(round(elt)) for elt in k]
        if all(elt == 0 for elt in k):
            break
        fk = karamul(f, k)
        gk = karamul(g, k)
        for i in range(n):
            F[i] -= fk[i] << (Size - size)
            G[i] -= gk[i] << (Size - size)
    return F, G


def xgcd(b, n):
    x0, x1, y0, y1 = 1, 0, 0, 1
    while n != 0:
        q, b, n = b // n, n, b % n
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return b, x0, y0


def ntru_solve(f, g):
    n = len(f)
    if n == 1:
        f0 = f[0]
        g0 = g[0]
        d, u, v = xgcd(f0, g0)
        if d != 1:
            raise ValueError
        else:
            return [- q * v], [q * u]
    else:
        fp = field_norm(f)
        gp = field_norm(g)
        Fp, Gp = ntru_solve(fp, gp)
        F = karamul(lift(Fp), galois_conjugate(g))
        G = karamul(lift(Gp), galois_conjugate(f))
        F, G = reduce(f, g, F, G)
        return F, G


def gs_norm(f, g, q):
    sqnorm_fg = sqnorm([f, g])
    ffgg = add(mul(f, adj(f)), mul(g, adj(g)))
    Ft = div(adj(g), ffgg)
    Gt = div(adj(f), ffgg)
    sqnorm_FG = (q ** 2) * sqnorm([Ft, Gt])
    return max(sqnorm_fg, sqnorm_FG)


def gen_poly(n):
    sigma = 1.43300980528773
    assert(n < 4096)
    f0 = [samplerz(0, sigma, sigma - 0.001) for _ in range(4096)]
    f = [0] * n
    k = 4096 // n
    for i in range(n):
        f[i] = sum(f0[i * k + j] for j in range(k))
    return f


def ntru_gen(n):
    while True:
        f = gen_poly(n)
        g = gen_poly(n)
        if gs_norm(f, g, q) > (1.17 ** 2) * q:
            continue
        f_ntt = ntt(f)
        if any((elem == 0) for elem in f_ntt):
            continue
        try:
            F, G = ntru_solve(f, g)
            F = [int(coef) for coef in F]
            G = [int(coef) for coef in G]
            return f, g, F, G
        except ValueError:
            continue

:::
:::spoiler <b>ntru_gen.py</b>

# coding: utf-8

from random import SystemRandom
from sympy import *
import math
import numpy as np
import sys
class NTRUKeyGenerator:
  phi_1 = [-1,1]
  x = symbols('x')
  def __init__(self, HRSS, n, q=0):
    self.HRSS = HRSS
    self.n = n
    self.q = q
    
    self.cache = {}
    
    self.phi_n = [1]*n

    self.sample_iid_bits = 8*(n-1)
    self.sample_fixed_type_bits = 30*(n-1)

    if HRSS:
      self.q = 2**math.ceil(7/2+math.log2(n))
      self.sample_key_bits = 2*self.sample_iid_bits
    else:
      self.sample_key_bits = self.sample_iid_bits + self.sample_fixed_type_bits

    self.logq = int(math.log2(self.q))
  def randomBitArray(self, s):
    random = SystemRandom()
    return [ ( random.randrange(2) ) for i in range(s) ]
  def newSeed(self):
    return self.randomBitArray(self.sample_key_bits)
  def polyToSympy(self, poly):
    return Poly( poly[::-1], self.x )
  def sympyToPoly(self, symPoly):
    try:
      return symPoly.all_coeffs()[::-1]
    except:
      return [symPoly]
  def polyCoeffMod(self, poly,m):
    for i in range(len(poly)):
      poly[i] = poly[i] % m
      if m!=2 and poly[i] >= m/2:
        poly[i] -= m
    return poly
  def sympyPolyCoeffMod2(self, symPoly):
    return self.polyToSympy( self.polyCoeffMod( self.sympyToPoly(symPoly), 2 ) )
  def polyMod(self, poly1, m, poly2):
    poly1Sym = self.polyToSympy(poly1)
    poly2Sym = self.polyToSympy(poly2)

    q,r = div(poly1Sym,poly2Sym)

    poly1Sym = r
    poly1 = self.sympyToPoly(poly1Sym)

    poly1 = self.polyCoeffMod(poly1,m)

    return poly1
  def polynomialEEA_mod2(self, f_1, f_2):
    zeroPoly = self.polyToSympy([0])
    onePoly = self.polyToSympy([1])

    if f_1 == zeroPoly:
        f_2 = self.sympyPolyCoeffMod2(f_2)
        return (f_2, zeroPoly, onePoly)
    else:
        q,r = div( f_2, f_1 )

        q = self.sympyPolyCoeffMod2(q)
        r = self.sympyPolyCoeffMod2(r)

        g, s, t = self.polynomialEEA_mod2(r, f_1)
        return (self.sympyPolyCoeffMod2(g), self.sympyPolyCoeffMod2(t-q*s), self.sympyPolyCoeffMod2(s))
  def S2_(self, poly):
    return self.polyMod(poly,2,self.phi_n)
  def S3_(self, poly):
    return self.polyMod(poly,3,self.phi_n)
  def Sq_(self, poly):
    return self.polyMod(poly,self.q,self.phi_n)
  def S2_inverse(self, poly):
    g,s,t = self.polynomialEEA_mod2( self.polyToSympy(poly), self.polyToSympy(self.phi_n) )
    if g != self.polyToSympy([1]):
      raise ZeroDivisionError
    return self.sympyToPoly(s)
  def Sq_inverse(self, a):
    v_0 = self.S2_inverse(a)
    t = 1
    while t < self.logq:
      sympA = self.polyToSympy(a)
      sympV = self.polyToSympy(v_0)
      sympV = sympV * (2 - sympA*sympV )
      v_0 = self.sympyToPoly(sympV)
      v_0 = self.Sq_( v_0 )
      t *= 2
    return self.Sq_(v_0)
  def ternary(self, b):
    v = [0]*(self.n-1)

    for i in range(self.n-1):
      coeff_i = 0
      for j in range(8):
        coeff_i +=  2^j * b[ 8*i + j ]
      v[i] = coeff_i

    return self.S3_(v)
  def ternary_plus(self, b):
    v = self.ternary(b)

    t = 0
    for i in range(self.n-2):
      t += v[i]*v[i+1]

    if t < 0:
      s = -1
    else:
      s = 1
      
    i = 0
    while i < self.n-1:
      v[i] = s*v[i]
      i += 2

    v = self.S3_(v)
    
    test = 0
    for v_i in v:
      test += v_i
    
    return v
  def fixed_type(self, b):
    A = [0]*(self.n-1)
    v = [0]*(self.n-1)

    i = 0
    while i < min(self.q/16 - 1, floor(self.n/3)):
      A[i] = 1
      for j in range(30):
        A[i] += 2**(2+j)*b[30*i+j]
      i += 1

    while i < min(self.q/8 - 2, 2*floor(self.n/3)):
      A[i] = 2
      for j in range(30):
        A[i] += 2**(2+j)*b[30*i+j]
      i += 1

    while i < self.n-1:
      for j in range(30):
        A[i] += 2**(2+j)*b[30*i+j]
      i += 1

    A.sort()

    for i in range(self.n-1):
      v[i] = A[i] % 4

    return self.S3_(v)
  def sample_fg(self, fg_bits):

    f_bits = fg_bits[0:self.sample_iid_bits]
    g_bits = fg_bits[self.sample_iid_bits:]

    if self.HRSS:
      f = self.ternary_plus(f_bits)
      g_0 = self.ternary_plus(g_bits)
      gSymp = self.polyToSympy(g_0) * self.polyToSympy(self.phi_1)
      g = self.sympyToPoly(gSymp)
    else:
      f = self.ternary(f_bits)
      g = self.fixed_type(g_bits)
    
        
    if len(f) < self.n:
      f = f + [0]*(self.n-len(f))
    if len(g) < self.n:
      g = g + [0]*(self.n-len(g))
    
    return (f,g)
  def getKey(self, seed):
    seedT = tuple(seed)
    if seedT in self.cache:
      return self.cache[seedT]
    else:
      fg_bits = seed
      f,g = self.sample_fg(fg_bits)
      f_q = self.Sq_inverse(f)
            
      gSymp = self.polyToSympy(g)
      f_qSymp = self.polyToSympy(f_q)
    
      hSymp = gSymp * f_qSymp
      h = self.sympyToPoly(hSymp)
    
      modulus = [-1] + [0]*(self.n-1) + [1]
      h = self.polyMod(h, self.q, modulus)
        
      if len(h) < self.n:
        h = h + [0]*(self.n-len(h))
      
      self.cache[seedT] = (f,g,h)
      
      return (f,g,h)

:::
:::spoiler <b>lwe_gen.py</b>

from random import randrange
import numpy as np
import json
from ntrugen import ntru_gen
from ntt import div_zq
from ntru_gen import NTRUKeyGenerator

def generateLWEInstance(scheme):
  implementedSchemes = [
    "Kyber512", "Kyber768", "Kyber1024",
    "Dilithium2", "Dilithium3", "Dilithium5",
    "Falcon2", "Falcon4", "Falcon8", "Falcon16", "Falcon32", "Falcon64", "Falcon128", "Falcon256", "Falcon512", "Falcon1024",
    "NTRU-HPS-509", "NTRU-HPS-677", "NTRU-HPS-821", "NTRU-HRSS"
  ]

  if scheme not in implementedSchemes:
    raise NotImplementedError( "Scheme " + scheme + " is not supported." )

  if scheme.startswith("Kyber"):
    variant = int(scheme[5:])
    A,s,e,q = kyberGen(variant)
  elif scheme.startswith("Dilithium"):
    variant = int(scheme[9:])
    A,s,e,q = dilithiumGen(variant)
  elif scheme.startswith("Falcon"):
    variant = int(scheme[6:])
    A,s,e,q = falconGen(variant)
  elif scheme.startswith("NTRU"):
    scheme = scheme[5:]
    A,s,e,q = ntruGen(scheme)

  b = (s.dot(A) + e) % q

  return A,b,q,s,e


def loadLWEInstanceFromFile( fileName = None ):
  with open(fileName) as f:
      
      data = json.load(f)
      q = int(data["q"])
      A = np.array(data["A"])
      b = np.array(data["b"])
      
      if not( "s" in data and "e" in data ):
        return A,b,q
      
      else:
        s = np.array(data["s"])
        e = np.array(data["e"])
        return A,b,q,s,e
  
def generateToyInstance(n,m,q,eta):
  A,s,e = binomialLWEGen(n,m,q,eta)
  b = (s.dot(A) + e) % q
  
  return A,b,q,s,e

def binomial_dist(eta):
  s = 0
  for i in range(eta):
    s += randrange(2)
  return s
def binomial_vec(n, eta):
  v = np.array([0]*n)
  for i in range(n):
    v[i] = binomial_dist(2*eta) - eta
  return v
def uniform_vec(n, a, b):
  return np.array([randrange(a,b) for _ in range(n)])
def rotMatrix(poly, cyclotomic=False):
  n = len(poly)
  A = np.array( [[0]*n for _ in range(n)] )
  
  for i in range(n):
    for j in range(n):
      c = 1
      if cyclotomic and j < i:
        c = -1

      A[i][j] = c * poly[(j-i)%n]
      
  return A
def module( polys, rows, cols ):
  if rows*cols != len(polys):
    raise ValueError("len(polys) has to equal rows*cols.")
  
  n = len(polys[0])
  for poly in polys:
    if len(poly) != n:
      raise ValueError("polys must not contain polynomials of varying degrees.")
  
  blocks = []
  
  for i in range(rows):
    row = []
    for j in range(cols):
      row.append( rotMatrix(polys[i*cols+j], cyclotomic=True) )
    blocks.append(row)
  return np.block( blocks )
def binomialLWEGen(n,m,q,eta):
  A = np.array( [[0]*m for _ in range(n)] )
  for i in range(n):
    for j in range(m):
      A[i][j] = randrange(q)
  s = binomial_vec(n, eta)
  e = binomial_vec(m, eta)
  return A,s,e
  
def kyberGen(variant):
  if variant not in [512,768,1024]:
    raise NotImplementedError("kyberGen(variant) supports only variant = 512, 768, 1024, but variant = %d was given." % variant)
  
  n = 256
  q = 3329
  k = variant//n
  
  if k == 2:
    eta = 3
  else:
    eta = 2
  
  s = binomial_vec(variant, eta)
  e = binomial_vec(variant, eta)
  
  polys = []
  for i in range(k*k):
    polys.append( uniform_vec(n,0,q) )
  
  A = module(polys, k, k)
  
  return A,s,e,q
def dilithiumGen(variant):
  if variant not in [2,3,5]:
    raise NotImplementedError("dilithiumGen(variant) supports only variant = 2, 3, 5, but variant = %d was given." % variant)
  
  n = 256
  q = 8380417
  
  if variant == 2:
    k = 4
    l = 4
    eta = 2
  elif variant == 3:
    k = 6
    l = 5
    eta = 4
  else:
    k = 8
    l = 7
    eta = 2
  
  s = uniform_vec(n*l,-eta,eta+1)
  e = uniform_vec(n*k,-eta,eta+1)
  
  polys = []
  for i in range(k*l):
    polys.append( uniform_vec(n,0,q) )
  
  A = module(polys, l, k)
  
  return A,s,e,q
def falconGen(n):
  if n not in [ 2**i for i in range(1,11) ]:
    raise NotImplementedError("falconGen(n) supports only n = 2, 4, ..., 1024 but n = %d was given." % n)
  
  q = 12289
  
  f, g, F, G = ntru_gen(n)
  h = div_zq(g, f)
  
  A = rotMatrix(h, cyclotomic=True)
  s = np.array(f)
  e = -np.array(g)
  
  return A,s,e,q
def ntruGen(variant):
  if variant not in ["HPS-509", "HPS-677", "HPS-821", "HRSS"]:
    raise NotImplementedError("ntruGen(variant) supports only variant = HPS-509, HPS-677, HPS-821, HRSS but " + variant + " was given.")
    
  if variant == "HRSS":
    useHRSS = True
    n = 701
    q = 8192
  else:
    useHRSS = False
    n = int(variant[4:])
    if n == 821:
      q = 4096
    else:
      q = 2048
    
  generator = NTRUKeyGenerator(useHRSS, n, q)
  seed = generator.newSeed()
  f,g,h = generator.getKey(seed)
  
  A = rotMatrix(h)
  s = np.array(f)  
  e = -np.array(g)
  
  return A,s,e,q

:::
:::spoiler <b>challenge.py</b>

import sys
import os
import random
import json
import hashlib
import numpy as np

from lwe_gen import falconGen

def encrypt_flag(f, flag):
    key = hashlib.sha256(f.tobytes()).digest()
    encrypted = bytes([b ^ key[i % len(key)] for i, b in enumerate(flag.encode())])
    return encrypted.hex()

def main():
    N = 512
    num_hints = 436
    
    print(f"Generating Falcon-{N} keys...")
    A, f, g_neg, q = falconGen(N)
    
    print("Selecting hints...")
    indices = random.sample(range(N), num_hints)
    hints = [[int(i), int(f[i])] for i in indices]
    b = (f.dot(A) + g_neg) % q
    
    if not np.all(b == 0):
        print("Warning: b is not all zeros. This might happen if rotMatrix or falconGen has different conventions.")
        print(f"Non-zero elements in b: {np.count_nonzero(b)}")
    
    data = {
        "q": int(q),
        "n": int(N),
        "A": A.tolist(),
        "b": b.tolist(),
        "hints": hints
    }
    
    flag = "BITSCTF{REDACTED}"
    encrypted_flag = encrypt_flag(f, flag)
    
    print(f"Challenge generated successfully!")
    print(f"Leaked {num_hints} coefficients of f.")

if __name__ == "__main__":
    main()

:::
:::spoiler <b>challenge_flag.enc</b>

cf6e24d84002dab5a83bbdf22738cadeaab833f4ef8da8a573b8309f73729cb2b94b13bb6d25c3fab2398ce060148ad1

:::
:::spoiler <b>challeng_data.json</b>

{"q": 12289, "n": 512, "A": [[3377, 640, 11790, 10733, 7860, 4031, 1849, 10007, 11554, 8753, 6936, 3500, 2532, 635, 3283, 5598, 6049, 10948, 7215, 1696, 3607, 11033, 1839, 8363, 5369, 11088, 9952, 5115, 10006, 7228, 11432, 3504, 3801, 1861, 8474, 5238, 8113, 7931, 1464, 3880, 1872, 3001, 3506, 4784, 7225, 10360, 7254, 9993, 7193, 11807, 2939, 4204, 7073, 10657, 507, 10583, 5079, 5046, 12192, 548, 918, 1727, 5873, 9059, 1551, 5777, 1821, 11182, 6513, 5352, 8525, 6534, 7413, 3289, 1552, 858, 3499, 1427, 8829, 5986, 7861, 7172, 6691, 3140, 6453, 6761, 4421, 5965, 9660, 3054, 11740, 1788, 1292, 2905, 4041, 11677, 10861, 8708, 6326, 9928, 4891, 301, 511, 12243, 585, 2275, 2952, 11738, 7900, 5670, 12272, 2256, 946, 2588, 1600, 5879, 12042, 5799, 660, 8719, 9245, 8607, 1403, 4512, 726, 2020, 7177, 1828, 1996, 11560, 12030, 4293, 6428, 5025, 12071, 1691, 1334, 7090, 1440, 440, 6429, 4791, 2431, 1488, 10753, 2705, 7728, 7192, 7843, 6273, 7020, 2114, 2139, 9707, 901, 4535, 4528, 8262, 1683, 10989, 9180, 5212, 2044, 10838, 3702, 7191, 3949, 8351, 1214, 5504, 11993, 255, 10323, 10328, 7355, 5073, 1674, 3916, 2979, 3431, 1111, 3302, 309, 9705, 7942, 1099, 188, 1917, 11009, 1454, 8139, 10506, 9314, 5425, 11646, 916, 12285, 5286, 7579, 5895, 5263, 7861, 2967, 5181, 4703, 2082, 5832, 10285, 9452, 6859, 11240, 6716, 2538, 4543, 338, 9328, 2851, 11475, 2375, 10879, 4216, 7250, 6036, 10797, 10787, 7367, 7950, 6662, 7063, 10757, 9959, 736, 3096, 3556, 11194, 4012, 949, 12098, 9302, 9707, 11013, 9901, 7030, 8066, 9933, 8436, 4327, 1523, 4939, 6332, 8587, 8252, 10880, 6884, 1738, 2898, 5525, 10264, 10808, 10293, 186, 768, 6782, 5673, 1905, 11898, 6411, 5170, 9119, 3088, 9958, 6225, 5531, 8723, 2455, 7715, 5895, 4973, 5802, 3762, 3523, 3002, 10574, 2980, 3435, 792, 4520, 5680, 10708, 4661, 6456, 4163, 2168, 1379, 11635, 10278, 6060, 9373, 6749, 285, 4588, 11830, 5515, 650, 3848, 3962, 9368, 8641, 588, 2958, 10720, 9896, 6897, 5062, 9463, 9441, 11859, 10576, 1447, 5652, 224, 10090, 8005, 2888, 2196, 9975, 2996, 656, 9627, 2166, 202, 2159, 6567, 11809, 524, 11581, 5610, 6783, 10124, 2522, 100, 9630, 1562, 10254, 11053, 1030, 12202, 5291, 9323, 4254, 2950, 8292, 10588, 11699, 9162, 6535, 7603, 8210, 10939, 4746, 9152, 1326, 7633, 3070, 10032, 7314, 7732, 6742, 1507, 2146, 2459, 10242, 11653, 7611, 1931, 4644, 2765, 2933, 8164, 8003, 9694, 7166, 2996, 4131, 10927, 4689, 3637, 8512, 7346, 9639, 4404, 11559, 3095, 4553, 7715, 2888, 11887, 11911, 4941, 7504, 323, 9271, 7925, 7984, 8918, 12156, 7141, 10888, 1362, 2492, 9343, 854, 10449, 6820, 6530, 10275, 2200, 5696, 8504, 10427, 10898, 11923, 4529, 7899, 3806, 10620, 1302, 1158, 11042, 12219, 2579, 5544, 3673, 8760, 11312, 4237, ... (còn rất dài nữa)

:::

Bài này sử dụng [**hệ mã Falcon**](https://falcon-sign.info/), chỉ cần để ý đến 3 file cuối cùng vì nó chính là nội dung chính của chúng ta cho bài này.

Từ đề bài, chúng ta được cho biết 436 hệ số ngẫu nghiên của đa thức $f$, và chúng ta cần phải tìm cách khôi phục $k = 76$ hệ số còn lại để giải mã và lấy flag.
Gọi $f_{\text{known}}$ và $f_{\text{unknown}}$ lần lượt là các biểu diễn vector của đa thức $f$ tương ứng với các hệ số đã biết và các hệ số chưa biết. Dễ hiểu hơn thì $f = f_{\text{known}} + f_{\text{unknown}}$, trong đó các vị trí tương ứng với các giá trị đã biết sẽ nằm trong vector $f_{\text{known}}$, các vị trí tương ứng với các giá trị chưa biết sẽ nằm trong $f_{\text{unknown}}$. Như vậy thì cả $f_{\text{known}}$ và $f_{\text{unknown}}$ đều là các vector $n = 512$ chiều.

Từ thử thách ta có phương trình sau:
$$
\begin{matrix}
&b &\equiv& f \cdot A - g &\pmod{q} \\
\Leftrightarrow &b &\equiv& (f_{\text{known}} + f_{\text{unknown}}) \cdot A - g &\pmod{q} \\
\Leftrightarrow &f_{\text{unknown}} \cdot A - g &\equiv& b - f_{\text{known}} \cdot A &\pmod{q} &\quad (1)
\end{matrix}
$$

Cái phương trình này vẫn chưa phải là tối ưu để tấn công giảm cơ sở mạng, nên chúng ta cần phải biến đổi tiếp. Cụ thể ta thấy rằng $f_{\text{unknown}}$ là một vector thưa (sparse vector), nên chúng ta cần phải biến nó thành một vector đặc (dense vector). Cụ thể ta sẽ dùng ma trận chuyển vị của ma trận chọn (ma trận chọn có tên tiếng anh là [**selection matrix**](https://math.stackexchange.com/questions/2734205/whats-a-selection-matrix)), được ký hiệu là $M$ để biến đổi vector thưa thành vector đặc theo công thức:

$$
f_{\text{unknown}} = f_{\text{unknown}}^{'} \cdot M
$$
trong đó, $f_{\text{unknown}}$ là vector $n$ chiều, $f_{\text{unknown}}^{'}$ là vector $k$ chiều và $M$ là ma trận có kích thước $k \times n$.
>[!Tip] Cách lấy ma trận M trong sagemath
> Giả sử ta có một mảng `unknown_indices` để chỉ các vị trí mà ta chưa biết giá trị, khi đó ta có cách để lấy ma trận $M$ như sau:
> ```
> identity = identity_matrix(512, sparse=True)
> M = identity.matrix_from_rows(unknown_indices)
> ```

Như vậy phương trình $(1)$ lúc này trở thành:
$$
f_{\text{unknown}}^{'} \cdot MA - g \equiv b - f_{\text{known}} \cdot A \pmod{q}
$$

Lúc này, ta đặt $\begin{cases} A_{\text{new}} &= MA \\ e &= -g \\ b_{\text{new}} &= b - f_{\text{known}} \cdot A \end{cases}$ thì phương trình trên trở thành:

$$
f_{\text{unknown}}^{'} \cdot A_{\text{new}} + e \equiv b_{\text{new}} \pmod{q} \tag{2}
$$
trong đó, $f_{\text{unknown}}^{'}$ là vector ngang $k$ chiều, $A_{\text{new}}$ là ma trận đã biết với kích thước $k \times n$, $~ e$ và $b_{\text{new}}$ là các vector ngang có $n$ chiều.

Đến đây, ta sẽ xây dựng ma trận dựa trên [bài giảng này](https://www.maths.ox.ac.uk/system/files/attachments/lattice-reduction-and-attacks.pdf) để tiến hành tấn công giảm cơ sở mạng cho bài toán **LWE** này.
Cụ thể, trước hết ta sẽ đi tìm dạng bậc thang rút gọn $[I_{k \times k} | A']$ của ma trận $A_{\text{new}}$ trong $\mathbb{F}_q^{k \times n}$, sau đó ta tiến hành lập lưới như sau:

$$
\textbf{B} =
\begin{pmatrix}
I_{k \times k} & A' & 0_{k \times 1} \\
0_{(n - k) \times k} & qI_{(n - k) \times (n - k)} & 0_{(n - k) \times 1} \\
b_{\text{new}} & & t
\end{pmatrix}
$$
trong đó $t$ là một hệ số tự chọn, theo như bài giảng thì ta nên để $t = 1$.

>[!Warning] Về kích thước của lưới
> Nếu ta để nguyên $n$ thì lưới sẽ có kích thước $513 \times 513$, quá to để có thể thực hiện tấn công giảm cơ sở mạng hiệu quả, vì vậy chúng ta phải cắt bỏ ma trận $A_{\text{new}}$ thành ma trận kích thước $k \times n_{\text{new}}$, $~ b_{\text{new}}$ thành vector có số chiều là $n_{\text{new}}$ với $n_{\text{new}}$ được đề xuất có độ lớn khoảng $2k$ để mà tấn công giảm cơ sở mạng thành công.
> Tuy nhiên vì mình đang trình bày lý thuyết của lời giải nên mình vẫn sẽ dùng ký hiệu $n$ để gõ cho nhanh.

Sẽ có một tổ hợp tuyến tính $\mathbf{w} = (-\mathbf{s}_{new}, \mathbf{k}, 1)$ sinh ra vector ngắn $\mathbf{v} = (e_1, e_2, ..., e_n, t)$, và đây chính là vector mà chúng ta cần tìm. Cái phần tổ hợp tuyến tính $\mathbf{w}$ là gì thì khá phức tạp và chính mình cũng không hiểu rõ lắm nên các bạn có thể tự tìm hiểu trên mạng.

Từ vector ngắn $\mathbf{w}$ kia ta đã khôi phục lại được $e$, thay vào phương trình (2) ta được:

$$
f_{\text{unknown}}^{'} \cdot A_{\text{new}} \equiv b_{\text{new}} - e \pmod{q}
$$

Đến đây, ta dùng phương thức `solve_left()` của sagemath là đã tìm ra các giá trị chưa biết còn lại của đa thức $f$ rồi. Như vậy, việc còn lại chúng ta cần làm là khôi phục toàn bộ $f$ và từ đó lấy lại **flag** thôi 🥳🎉🥳🎉!

Dưới đây là toàn bộ lời giải cho thử thách này:
:::spoiler <b style="color:#7e9bf3">solution.py</b>

from sage.all import matrix, identity_matrix, zero_matrix, zero_vector, GF, ZZ
import json, hashlib
import numpy as np

with open("challenge_data.json", "r") as file:
    data = json.load(file)

q = data["q"]; Fq = GF(q)
n = data["n"]
A = matrix(Fq, data["A"])
b = matrix(Fq, data["b"])
hints = data["hints"]

known_indices = {int(h[0]): int(h[1]) for h in hints}
unknown_indices = [i for i in range(n) if i not in known_indices]

identity = identity_matrix(Fq, 512, sparse=True)
M = identity.matrix_from_rows(unknown_indices)

k = len(unknown_indices)

f_known = [0 for _ in range(n)]
for idx, val in hints:
    f_known[idx] = val
f_known = matrix(Fq, f_known)

b = b - f_known*A
A = M*A

n_new = 150
A_new = A[:, :n_new]
b_new = b[:, :n_new]

A_rref = A_new.echelon_form()
A_rref = matrix(ZZ, A_rref)

B = zero_matrix(ZZ, n_new - k, k).augment(q*identity_matrix(ZZ, n_new - k))
b_new = matrix(ZZ, b_new)

lattice = A_rref.stack(B)
lattice = lattice.stack(b_new)
lattice = lattice.augment(zero_vector(ZZ, n_new + 1))
lattice[-1, -1] = 1

reduced_basis_1 = lattice.LLL(algorithm = 'flatter', delta = 0.995)
reduced_basis_2 = reduced_basis_1.BKZ(block_size = 20)

for row in reduced_basis_2:
    if abs(row[-1]) == 1 and all([abs(x) < 20 for x in row]) == True:
        raw_g = row[-1]*row
        g = matrix(Fq, raw_g[:-1])

        break

A_new = matrix(Fq, A_new)
b_new = matrix(Fq, b_new)

s_vector = A_new.solve_left(b_new - g)
s_list = s_vector.list()

f_unknown = [int(x) - q if abs(int(x) - q) < int(x) else int(x) for x in s_list]

f_full = [0 for _ in range(n)]
for idx, val in hints:
    f_full[idx] = val

for i, idx in enumerate(unknown_indices):
    f_full[idx] = f_unknown[i]


with open("challenge_flag.enc", "r") as f_enc:
    enc_hex = f_enc.read().strip()

f_arr = np.array(f_full, dtype=np.int64)

key = hashlib.sha256(f_arr.tobytes()).digest()
encrypted = bytes.fromhex(enc_hex)
flag = bytes([b_val ^ key[i % len(key)] for i, b_val in enumerate(encrypted)])

print("[!] Got flag:", flag.decode())
# [!] Got flag: BITSCTF{h1nts_4r3_p0w3rfu1_4nd_f4lc0ns_4r3_f4st}

:::

:::success
**Flag: BITSCTF{h1nts_4r3_p0w3rfu1_4nd_f4lc0ns_4r3_f4st}**
:::

## Summary

Trên đây là một số bài mật mã học trong cuộc thi **BITSCTF 2026**, còn hai bài mật mã học nữa nhưng vì nó quá thiên về đoán mò nên mình sẽ không ghi write-up.
Cuộc thi này cũng có **Google Cloud** tài trợ nên đề cũng có một số câu khó nhai (nếu không dùng AI), trong đó có một câu PQC.