<h1 style="text-align:center; color:#4287f5">ImaginaryCTF 2025: Part 1</h1>

Dưới đây là lời giải cho cuộc thi **ImaginaryCTF 2025** cùng với một số lời giải thích và phân tích.

<h2 style="color:#4287f5">redacted</h2>


Chúng ta sẽ được cho một bức ảnh sau, nhiệm vụ của chúng ta là phải đoán **flag** dựa vào bức ảnh này:

Bài này đơn giản là **Reverse Engineering** trá hình mà lại ném vào phần **Cryptography** thôi :-1:.

Chú ý rằng đầu vào của khung **XOR** và khung **Input** đều là **flag**, tuy nhiên do **flag** dài quá nên phần XOR không hiện hết được, dẫn tới việc phần màu đỏ trong khung **XOR** ngắn hơn khung **Input**.

Dưới đây là script để giải thử thách:
:::spoiler <b style="color:#f5d142">solution.py</b>

import string
from tqdm import trange

def CyberChef_hexparse(value: string) -> bytes:
    hex_string = ''
    
    for char in value:
        if char in string.hexdigits:
            hex_string += char
            
            if ' ' not in hex_string[-2:]:
                hex_string += ' '
        else:
            hex_string += ' '
    
    return bytes([int(x, 16) for x in hex_string.split()])

def CyberChef_xor(value: bytes, key: bytes) -> bytes:
    return bytes([value[i] ^ key[i % len(key)] for i in range(len(value))])

output = "65 6c ce 6b c1 75 61 7e 53 66 c9 52 d8 6c 6a 53 6e 6e de 52 df 63 6d 7e 75 7f ce 64 d5 63 73"
new_output = output.replace(" ", '')
bytes_output = bytes.fromhex(new_output)

flag_prefix = b"ictf{"
key_prefix = CyberChef_xor(flag_prefix, bytes_output[:len(flag_prefix)])

for attempt_length in range(len(key_prefix), len(bytes_output)):
    print(f"Trying key_length = {attempt_length}...")
    is_found = False

    suffix_length = attempt_length - len(key_prefix)

    for key_suffix in trange(256**suffix_length):
        key = key_prefix + key_suffix.to_bytes(suffix_length)
        possible_flag = CyberChef_xor(bytes_output, key)

        if(possible_flag.isascii() and CyberChef_hexparse(possible_flag.decode()) == key):
            flag = possible_flag
            is_found = True

            break

    if(is_found): break

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

:::

:::success
**Flag:** <b style="color:#f542c8">ictf{xor_is_bad_bad_encryption}</b>
:::

<h2 style="color:#4287f5">leaky-rsa</h2>

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

#!/usr/local/bin/python3
import json
from Crypto.Util.number import getPrime
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secrets import randbelow, token_bytes
from hashlib import sha256

with open('flag.txt') as f:
    flag = f.read()

p = getPrime(512)
q = getPrime(512)
n = p * q
e = 65537
d = pow(e, -1, (p-1)*(q-1))

key_m = randbelow(n)
key_c = pow(key_m, e, n)

key = sha256(str(key_m).encode()).digest()[:16]
iv = token_bytes(16)
ct = AES.new(key, AES.MODE_CBC, IV=iv).encrypt(pad(flag.encode(), 16))

print(json.dumps({'n': n, 'c': key_c, 'iv': iv.hex(), 'ct': ct.hex()}))

def get_bit(n, k):
    return (n >> k) % 2

for _ in range(1024):
    idx = randbelow(4)
    print(json.dumps({'idx': idx}))
    try:
        response = json.loads(input())
        c = response['c'] % n
        assert c != key_c
        m = pow(c, d, n)
        b = get_bit(m, idx)
    except (json.JSONDecodeError, TypeError, KeyError, ValueError, AssertionError):
        b = 2
    print(json.dumps({'b': b}))
print(key_m)

:::

Vì bài này là phiên bản dễ nên ta không cần phải làm gì ngoài việc cho chạy vòng lặp $1024$ lần để lấy `key_m`, từ đó có **flag** mà thôi!

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

from pwn import *
import json
from tqdm import trange
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

HOST = "leaky-rsa.chal.imaginaryctf.org"; PORT = 1337
e = 65537

connection = remote(HOST, PORT)
connection.recvuntil(b'== proof-of-work: disabled ==\n')

infomation = json.loads(connection.recvline())
n = infomation["n"]; c = infomation["c"]
iv = bytes.fromhex(infomation["iv"]); ct = bytes.fromhex(infomation["ct"])

chosen_c = (pow(2, e, n)*c) % n
for i in trange(1024):
    connection.recvline()
    connection.sendline(json.dumps({"c": chosen_c}).encode())
    connection.recvline()

key_m = int(connection.recvline().strip().decode())
key = sha256(str(key_m).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, IV=iv)

flag = unpad(cipher.decrypt(ct), 16).decode()

connection.success(f"Got flag: {flag}")
# [+] Got flag: ictf{p13cin9_7h3_b1t5_t0g37her_3f0068c1b9be2547ada52a8020420fb0}

connection.close()

:::

:::success
**Flag:** <b style="color:#f542c8">ictf{p13cin9_7h3_b1t5_t0g37her_3f0068c1b9be2547ada52a8020420fb0}</b>
:::

<h2 style="color:#4287f5">leaky-rsa-revenge</h2>

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

#!/usr/local/bin/python3
import json
from Crypto.Util.number import getPrime
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secrets import randbelow, token_bytes
from hashlib import sha256

with open('flag.txt') as f:
    flag = f.read()

p = getPrime(512)
q = getPrime(512)
n = p * q
e = 65537
d = pow(e, -1, (p-1)*(q-1))

key_m = randbelow(n)
key_c = pow(key_m, e, n)

key = sha256(str(key_m).encode()).digest()[:16]
iv = token_bytes(16)
ct = AES.new(key, AES.MODE_CBC, IV=iv).encrypt(pad(flag.encode(), 16))

print(json.dumps({'n': n, 'c': key_c, 'iv': iv.hex(), 'ct': ct.hex()}))

def get_bit(n, k):
    return (n >> k) % 2

for _ in range(1024):
    idx = randbelow(4)
    print(json.dumps({'idx': idx}))
    try:
        response = json.loads(input())
        c = response['c'] % n
        assert c != key_c
        m = pow(c, d, n)
        b = get_bit(m, idx)
    except (json.JSONDecodeError, TypeError, KeyError, ValueError, AssertionError):
        b = 2
    print(json.dumps({'b': b}))

:::

Đây là một bài rất khó và nặng về công thức toán học nên mình sẽ trình bày cách giải bài này trước, sau đó sẽ là nguyên lý toán học đằng sau lời giải.

Các bước giải bài này như sau:
1. Chọn $n$ sao cho $n \equiv -1 \pmod{16}$, nếu thất bại thì ta chỉ cần kết nội lại cho đến khi thỏa mãn điều kiện này là được.
2. Chạy vòng lặp $j$ với $j = \overline{0, 1023}$, ở vòng lặp thứ $j$ ta sẽ tính $\text{chosen_c} = c\cdot 2^{e*(j + \text{idx} + 1)} \bmod{n}$, sau đó gửi $\text{chosen_c}$ cho server để nhận lại $b_{j+1}$.
3. Ta tìm lại được $\displaystyle m = n\cdot\sum_{j = 0}^{1023}{\frac{b_{j+1}}{2^{j+1}}}$ (thực tế thì ta phải dùng phần nguyên trần để tính chính xác được $m$). Sau khi có $m$ thì ta sẽ tiến hành khôi phục **flag** một cách dễ dàng.

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

from pwn import *
import json
from tqdm import trange
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from sage.all import RealField, ceil

e = 65537
R = RealField(2048)
sup_idx = 4
sup_power = 2**sup_idx

HOST = "leaky-rsa-revenge.chal.imaginaryctf.org"; PORT = 1337

connection_num = 1
while(True):
    print(f"Connection attempt: {connection_num}")

    try:
        connection = remote(HOST, PORT)
        connection.recvuntil(b'== proof-of-work: disabled ==\n')

        information = json.loads(connection.recvline())
        n = information["n"]; c = information["c"]
        iv = bytes.fromhex(information["iv"]); ct = bytes.fromhex(information["ct"])

        assert n % sup_power == sup_power - 1, "Critical Error 1!"

        break
    except AssertionError:
        connection_num += 1
        connection.close()

        continue

m_estimate = R(0)
multiplier = pow(2, e, n)

num_iterations = 1024
for j in trange(num_iterations):
    idx = json.loads(connection.recvline())["idx"]
    
    chosen_c = (c*pow(multiplier, j + idx + 1)) % n

    connection.sendline(json.dumps({'c': chosen_c}).encode())
    b = json.loads(connection.recvline())['b']

    assert b != 2, "Critical Error 2!"

    m_estimate += R(n*b)/R(2**(j+1))

key_m = ceil(m_estimate)

key = sha256(str(key_m).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, IV=iv)

flag = unpad(cipher.decrypt(ct), 16).decode()

connection.success(f"Got flag: {flag}")
# [+] Got flag: ictf{p13cin9_7h3_b1t5_t0g37her_7d092f5d43ebbf6fa60fba8c9e9ac4466daba9a71d04def7e5bf09bcce5649c8}

connection.close()

:::

:::success
**Flag:** <b style="color:#f542c8">ictf{p13cin9_7h3_b1t5_t0g37her_7d092f5d43ebbf6fa60fba8c9e9ac4466daba9a71d04def7e5bf09bcce5649c8}</b>
:::

:::info
Dưới đây là một số công thức toán học cần biết trước khi phân tích tính đúng đắn về mặt toán học của lời giải cho thử thách này. Vì các công thức này khá dễ để chứng minh nên mình sẽ để việc chứng minh như một bài tập nhỏ cho các bạn đọc.

- $a \equiv -a \pmod{2}$
- Với mọi $k \in \mathbb{Z}$ và $x \in \mathbb{R}$, ta có $\lfloor k + x \rfloor = k + \lfloor x \rfloor$ và $\lceil k + x \rceil = k + \lceil x \rceil$
- Với mọi số thực không âm $a$, ta có $\lfloor -a \rfloor = -\lceil a \rceil$
- Với mọi số nguyên $k$, ta có $\lfloor kx \rfloor = k\lfloor x \rfloor + r$ với $|r| \le k$ (dấu bằng chỉ xuất hiện khi $kx < 0$).
**Đặc biệt:** Với mọi số nguyên dương $k$ và số thực dương $x$ bất kỳ, ta có $\lfloor kx \rfloor = k\lfloor x \rfloor + r$ với $0 \le r \lt k$
:::

Đặt: $m = \text{key_m}$ với $0 \le m \lt n$, ta có định nghĩa các bit nhị phân như sau:

$$
\frac{m}{n} = {0.{b_1}{b_2}{b_3}...}_{(2)} \hspace{1em} (\text{binary form})
$$

>[!Note] Bổ đề
> Gọi $\text{LSB}(x)$ là hàm lấy ra bit kém quan trọng nhất của $x$, khi đó ta có đẳng thức sau:
>
> $$ \text{LSB}((m\cdot2^{i}) \bmod{n}) = b_{i} = \left\lfloor 2^{i}\frac{m}{n} \right\rfloor \bmod{2}, \forall i \in \mathbb{Z}^{+}$$
>
> Thật vậy, đặt $m\cdot2^{i} = an + r$, với $0 \le r < n; ~ r \in \mathbb{Z}$. Khi đó ta có $\displaystyle a = \left\lfloor \frac{m\cdot2^{i}}{n} \right\rfloor = \left\lfloor 2^{i}\frac{m}{n} \right\rfloor$. Dễ thấy $\text{LSB}((m\cdot2^{i}) \bmod{n})= \text{LSB}(r) = r \bmod{2}$.
>
> Vì $i \in \mathbb{Z}^{+}$ và $n = p\cdot q$ là số lẻ nên ta có $r = m\cdot2^{i} - an \equiv -a \equiv a \pmod{2}$.
>
> Suy ra $\displaystyle r \bmod{2} = a \bmod{2} = \left\lfloor 2^{i}\frac{m}{n} \right\rfloor \bmod{2}$ hay $\displaystyle \text{LSB}((m\cdot2^{i}) \bmod{n}) = \left\lfloor 2^{i}\frac{m}{n} \right\rfloor \bmod{2} \hspace{1em} (1)$
>
> Ta lại có:
> $$
> \left\lfloor 2^{i}\frac{m}{n} \right\rfloor \bmod{2} = \left\lfloor {{b_1}{b_2}...{b_i}.{b_{i+1}}...}_{(2)} \right\rfloor \bmod{2} = {{b_1}{b_2}...{b_i}}_{(2)} \bmod{2} = b_i \hspace{1em} (2)
> $$
>
> Từ $(1)$ và $(2)$ ta có điều phải chứng minh.

Quay trở lại bài toán, với mỗi vòng lặp $j$ và ta được chỉ số $\text{idx}$ được trả về từ server, ta đặt $k = j + \text{idx} + 1$.

Khi ta gửi $\text{chosen_c} = c\cdot 2^{e*(j + \text{idx} + 1)} \bmod{n}$ thì server sẽ tính lại $m'$ như sau:

$$
m'= \text{chosen_c}^{d} \bmod{n} = (c\cdot 2^{e*(j + \text{idx} + 1)})^{d} \bmod{n} = (c^d \bmod{n})((2^{de})^{j + \text{idx} + 1} \bmod{n}) = m\cdot 2^{j + \text{idx} + 1} \bmod{n} = m\cdot2^k \bmod{n}
$$

Đặt $T = m\cdot2^{k} = m\cdot2^{j + \text{idx} + 1}$, ta cũng có thể viết $T$ dưới dạng $T = an + r$ với $r \in \mathbb{Z},~ 0 \le r < n$ và $a = \left\lfloor \frac{T}{n} \right\rfloor$.
Khi đó, ta có $m' = m\cdot2^k \bmod{n} = T \bmod{n} = r$.

Ta đặt $\text{bit}_i(x)$ để chỉ bit thứ $i$ (với LSB tương ứng với $i = 0$) của $x$, ta có:

$$
\text{bit}_{\text{idx}}(m') = \text{bit}_{\text{idx}}(r) = \left\lfloor \frac{r}{2^{\text{idx}}} \right\rfloor \pmod{2}
$$

Ta lại có:

$$
\frac{r}{2^{\text{idx}}} = \frac{T - an}{2^{\text{idx}}} = m\cdot2^{j+1} - \frac{an}{2^{\text{idx}}}
$$

Vì $m\cdot2^{j+1}$ là một số nguyên nên ta suy ra:

$$
\left\lfloor \frac{r}{2^{\text{idx}}} \right\rfloor = \left\lfloor m\cdot2^{j+1} - \frac{an}{2^{\text{idx}}} \right\rfloor = m\cdot2^{j+1} + \left\lfloor - \frac{an}{2^{\text{idx}}} \right\rfloor = m\cdot2^{j+1} - \left\lceil \frac{an}{2^{\text{idx}}} \right\rceil
$$

Lấy modulo 2 hai vế, ta được:

$$
\text{bit}_{\text{idx}}(m') \equiv - \left\lceil \frac{an}{2^{\text{idx}}} \right\rceil \equiv \left\lceil \frac{an}{2^{\text{idx}}} \right\rceil \pmod{2} \hspace{3em} (1)
$$

Đặt $\displaystyle s = \left\lfloor 2^{j+1}\frac{m}{n} \right\rfloor$, chú ý rằng $s = b_{1}2^{j} + b_{2}2^{j-1} + \dots$ nhưng điều quan trọng nhất là $s \bmod{2} = b_{j+1}$. Ta có:

$$
a = \left\lfloor \frac{T}{n} \right\rfloor = \left\lfloor 2^{\text{idx}}\frac{m\cdot2^{j+1}}{n} \right\rfloor = 2^{\text{idx}}s + t,
$$

với $t \in \mathbb{Z}; ~ 0 \le t < 2^{\text{idx}}$.

Thay vào phương trình $(1)$:

$$
\text{bit}_{\text{idx}}(m') \equiv \left\lceil \frac{(2^{\text{idx}}s + t)n}{2^{\text{idx}}} \right\rceil \equiv sn + \left\lceil \frac{tn}{2^{\text{idx}}} \right\rceil \pmod{2}
$$

Hơn nữa, vì $n = p\cdot q$ là số lẻ nên ta suy ra:

$$
\text{bit}_{\text{idx}}(m') \equiv s + \left\lceil \frac{tn}{2^{\text{idx}}} \right\rceil \pmod{2}
$$

Như vậy thì $\displaystyle \text{bit}_{\text{idx}}(m') = s \bmod{2} = b_{j+1} \Leftrightarrow \left\lceil \frac{tn}{2^{\text{idx}}} \right\rceil \equiv 0 \pmod{2}$.

**Mục tiêu:** Làm sao để $\displaystyle \left\lceil \frac{tn}{2^{\text{idx}}} \right\rceil$ luôn là số chẵn $\forall t \in \{0, 1, 2, ..., 2^{\text{idx}} - 1\}$?
Vận dụng một chút trực giác toán học ta sẽ thấy ngay $n \equiv -1 \pmod{2^{\text{sup_idx}}}$, với $\text{sup_idx} = \max(\text{idx}) + 1$ (trong thử thách này thì `sup_idx = 4`) thì ta sẽ đạt được mục tiêu. Đây là một giá trị dễ thấy và không bị ảnh hưởng bởi $\text{idx}$ khác nhau ở các vòng lặp khác nhau, còn các giá trị khác khó có thể tìm được bởi vì tính không nhất quán của $\text{idx}$ qua các vòng lặp. Dưới đây mình sẽ giải thích tại sao với cách chọn $n$ ở trên thì ta đạt được mục tiêu:

Với $n \equiv -1 \pmod{2^{\text{sup_idx}}}$ thì $n = 2^{\text{sup_idx}}u - 1$, với $u \in \mathbb{Z}$. Ta có:

$$\displaystyle
\left\lceil \frac{tn}{2^{\text{idx}}} \right\rceil = \left\lceil \frac{t(2^{\text{sup_idx}}u - 1)}{2^{\text{idx}}} \right\rceil = 2^{\text{sup_idx} - \text{idx}}ut + \left\lceil \frac{-t}{2^{\text{idx}}} \right\rceil.
$$

Vì $0 \le t < 2^{\text{idx}}$ nên $\displaystyle -1 < \frac{-t}{2^{\text{idx}}} \le 0 \Leftrightarrow \left\lceil \frac{-t}{2^{\text{idx}}} \right\rceil = 0$. Như vậy thì $\displaystyle \left\lceil \frac{tn}{2^{\text{idx}}} \right\rceil$ sẽ là số chẵn.

Với cách chọn $n$ như vậy thì qua các vòng lặp ta sẽ thu được lần lượt là $b_1, b_2, b_3, \dots$ Khi đó dựa vào định nghĩa ban đầu ta có:

$$\displaystyle
\frac{m}{n} = \sum_{j \ge 0}{\frac{b_{j+1}}{2^{j+1}}} \Leftrightarrow m = n\sum_{j \ge 0}{\frac{b_{j+1}}{2^{j+1}}}
$$

(Dùng `RealField` với độ chính xác cao để tránh sai số thực)

Như vậy là ta đã tìm được gần như chính xác `key_m` để tiến hành khôi phục lại **flag** (sai số thực tế trong chương trình chỉ là $1$).

<h2 style="color:#4287f5">scalar-division</h2>


:::spoiler <b>chal.sage</b>

assert ((E:=EllipticCurve(GF(0xbde3c425157a83cbe69cee172d27e2ef9c1bd754ff052d4e7e6a26074efcea673eab9438dc45e0786c4ea54a89f9079ddb21),[5,7])).order().factor(limit=2**10)[3][0]*E.lift_x(ZZ(int.from_bytes((flag:=input('ictf{')).encode())))).x() == 0x686be42f9c3f431296a928c288145a847364bb259c9f5738270d48a7fba035377cc23b27f69d6ae0fad76d745fab25d504d5 and not print('\033[53C\033[1A}')

:::

Có vẻ những người ra đề của cuộc thi này có chơi luôn cả lĩnh vực **Reverse Engineering** khi mà đề hay dính tới một chút của phần này, cụ thể trong bài này thì đề đã được làm rối mã (<a href="https://en.wikipedia.org/wiki/Obfuscation_(software)"><b>obfuscation</b></a>).

Dưới đây là file đề bài đã được viết lại (có dựa vào AI) để trông dễ đọc hơn:

:::spoiler <b>rewritten_chal.sage</b>

# chall.sage
from sage.all import *

# Định nghĩa đường cong elliptic
p = 0xbde3c425157a83cbe69cee172d27e2ef9c1bd754ff052d4e7e6a26074efcea673eab9438dc45e0786c4ea54a89f9079ddb21
a = 5
b = 7
E = EllipticCurve(GF(p), [a, b])

# Phân tích thứ tự của đường cong và lấy một ước số nguyên tố nhỏ
factors = E.order().factor(limit=2**10)
small_prime = factors[3][0]  # Lấy thừa số nguyên tố thứ 4

# Nhận flag đầu vào
flag_input = input('ictf{')
flag_bytes = flag_input.encode()
flag_int = ZZ(int.from_bytes(flag_bytes))

# Tìm điểm trên đường cong có tọa độ x = flag_int
P = E.lift_x(flag_int)

# Thực hiện phép nhân scalar
Q = small_prime * P

# Điều kiện kiểm tra
target_x = 0x686be42f9c3f431296a928c288145a847364bb259c9f5738270d48a7fba035377cc23b27f69d6ae0fad76d745fab25d504d5
check_condition = (Q.x() == target_x)

# In kết quả (dòng code gốc có logic in phức tạp)
if check_condition and not print('\033[53C\033[1A}'):
    # Logic xử lý khi điều kiện đúng
    pass

:::

Bài này thì sẽ biến **flag** thành hoành độ của một điểm $P$ nào đó, sau đó nó sẽ thực hiện phép toán tính $Q = k\cdot P$ với $k$ là ước của $\#E(\mathbb{F}_{p})$ và sẽ trả về cho chúng ta hoành độ của $Q$. Ban đầu mình cứ nghĩ số nghiệm sẽ chắc chắn là $k$ nhưng sau khi nghiên cứu các tài liệu và cuốn sách về đường cong Elliptic thì công thức tìm số nghiệm của phương trình này rất phức tạp. Đối với trường hợp này thì số nghiệm đúng bằng $k$ nhưng không phải luôn luôn như vậy.

Nếu bạn chạy thử thì sẽ thấy thấy rằng `small_prime = 457`,
vậy trong trường hợp này ta sẽ có $457$ điểm $P$ thỏa mãn phương trình này. Do đó, mục tiêu của chúng ta là từ phương trình kia khôi phục và tìm được đúng điểm $P_{0}$ trong số $457$ điểm $P$ là nghiệm kia.

May mắn là chúng ta có một định lý khá hay ho liên quan đến <a href="https://en.wikipedia.org/wiki/Division_polynomials"><b>division polynomials</b></a> trong đường cong Elliptic. Nếu muốn tìm hiểu sâu hơn thì bạn có thể tham khảo ở cuốn **Elliptic Curves - Number Theory and Cryptography** của **Lawrence C. Washington**, phần này nằm ở mục **3.2 Division Polynomials** trong chương **3. Torsion Points** nhé. Quay trở lại bài toán, ta sẽ sử dụng định lý dưới đây:


Vì $Q = k\cdot P$ nên với $P = (x, y)$ thì ta có:

$$
Q_{x} = \frac{\phi_{k}(x)}{\psi_{k}^{2}(x)} \Leftrightarrow \psi_{k}^{2}(x)Q_{x} - \phi_{k}(x) = 0 \hspace{1em} (1)
$$

Giải phương trình $(1)$ thì ta sẽ được 457 giá trị của $x$, và chỉ một trong số đó chính là **flag** của chúng ta. Như vậy sau khi tìm được nghiệm của phương trình $(1)$ thì ta chỉ cần việc thử qua tất cả các giá trị $x$ là ta sẽ tìm được flag. Vì chỉ có $457$ nghiệm nên ta sẽ không cần phải thử quá lâu.

>[!Tip]
>Vì chúng ta đang làm việc trên trường $\mathbb{F}_{p}$ nên chúng ta sẽ có một **trick** khá hay để tìm nhanh các nghiệm của phương trình $f(x) = \psi_{k}^{2}(x)Q_{x} - \phi_{k}(x) = 0$, đó là tính $\gcd(f(x), x^{p} - x)$.
>Chứng minh tại sao nó đúng cũng dễ, nên mình để cho các bạn tự ngồi chứng minh.

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

from sage.all import EllipticCurve, GF, PolynomialRing
from Crypto.Util.number import long_to_bytes

p = 0xbde3c425157a83cbe69cee172d27e2ef9c1bd754ff052d4e7e6a26074efcea673eab9438dc45e0786c4ea54a89f9079ddb21
Qx = 0x686be42f9c3f431296a928c288145a847364bb259c9f5738270d48a7fba035377cc23b27f69d6ae0fad76d745fab25d504d5
a = 5
b = 7
E = EllipticCurve(GF(p), [a, b])

k = E.order().factor(limit=2**10)[3][0]

poly = E.multiplication_by_m(k, True)
poly = poly.numerator()-Qx*poly.denominator()

R = PolynomialRing(GF(p), name='x')
x = R.gen()

poly = R(poly)
poly2 = pow(x,p,poly)-x

final_poly = poly.gcd(poly2)
roots = final_poly.roots()

for root in roots:
    flag = long_to_bytes(int(root[0]))
    if flag.isascii():
        break

flag = "ictf{" + flag.decode() + '}'
print("[!] Got flag:", flag)
# [!] Got flag: ictf{mayb3_d0nt_m4ke_th3_sca1ar_a_f4ctor_0f_the_ord3r}

:::

:::success
**Flag:** <b style="color:#f542c8">ictf{mayb3_d0nt_m4ke_th3_sca1ar_a_f4ctor_0f_the_ord3r}</b>
:::

>[!Tip]
>Trong sagemath có phương thức `multiplication_by_m()` có thể dễ dàng hiện thực hóa định lý mà chúng ta đã đề cập ở trên. Bạn có thể đọc thêm về phương thức này <a href="https://doc.sagemath.org/html/en/reference/arithmetic_curves/sage/schemes/elliptic_curves/ell_generic.html#sage.schemes.elliptic_curves.ell_generic.EllipticCurve_generic.multiplication_by_m">ở đây</a>

>[!Warning] Chú ý
>Có thể phải mất từ vài phút đến vài chục phút thì mới chạy xong, đơn giản vì xử lý đa thức quá tốn thời gian!

<h2 style="color:#4287f5">zkpow</h2>


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

#!/usr/bin/env python3

import hashlib, secrets, json, time

# --- Utility functions ---
def sha256(b: bytes) -> bytes:
    return hashlib.sha256(b).digest()
def hexf(b: bytes) -> str:
    return b.hex()
def commit_vertex(v: int, color_label: int, nonce: bytes) -> bytes:
    return sha256(b"vertex:" + str(v).encode() + b":" + str(color_label).encode() + b":" + nonce)

# --- Merkle tree helpers ---
def build_merkle_tree(leaves_hex):
    leaves = [bytes.fromhex(h) for h in leaves_hex]
    if len(leaves) == 0:
        return hexf(sha256(b"")), [[sha256(b"")]]
    levels = [leaves]
    cur = leaves
    while len(cur) > 1:
        nxt = []
        for i in range(0, len(cur), 2):
            left = cur[i]
            right = cur[i+1] if i+1 < len(cur) else left
            nxt.append(sha256(left + right))
        levels.append(nxt)
        cur = nxt
    return hexf(levels[-1][0]), levels

def merkle_proof_for_index(levels, index):
    proof = []
    idx = index
    for level in levels[:-1]:
        if idx % 2 == 0:
            sib_index = idx + 1 if idx + 1 < len(level) else idx
            sibling = level[sib_index]
            proof.append((hexf(sibling), False))
        else:
            sib_index = idx - 1
            sibling = level[sib_index]
            proof.append((hexf(sibling), True))
        idx //= 2
    return proof

def verify_merkle_proof(root_hex, leaf_hex, proof):
    cur = bytes.fromhex(leaf_hex)
    for sibling_hex, sibling_is_left in proof:
        sibling = bytes.fromhex(sibling_hex)
        if sibling_is_left:
            cur = sha256(sibling + cur)
        else:
            cur = sha256(cur + sibling)
    return hexf(cur) == root_hex

# --- Fiat-Shamir edge selection ---
def fiat_shamir_select_index(root_hex, m):
    return int.from_bytes(hashlib.sha256(root_hex.encode()).digest(), "big") % m

# --- Configurable graph generator ---
def make_graph(n_vertices=1000, p_good=0.75, p_bad=0.003):
    coloring = [secrets.randbelow(3) for _ in range(n_vertices)]
    parts = {0: [], 1: [], 2: []}

    for v, c in enumerate(coloring):
        parts[c].append(v)
        edges = []

    for c1 in range(3):
        for c2 in range(c1+1, 3):
            A, B = parts[c1], parts[c2]
            for u in A:
               for v in B:
                   if secrets.randbelow(1_000_000) / 1_000_000 < p_good:
                       edges.append((u, v)) # spice things up :)

    for c in range(3):
        part = parts[c]
        for i in range(len(part)):
            for j in range(i+1, len(part)):
                if secrets.randbelow(1_000_000) / 1_000_000 < p_bad:
                    edges.append((part[i], part[j]))

    return edges, n_vertices

# --- zkPoW prover ---
def zkpow_prove(edges, coloring, n_vertices=1000):
    verts = list(range(n_vertices))

    # permutation + colors
    perm = [0,1,2]
    secrets.SystemRandom().shuffle(perm)
    permuted = {v: perm[coloring[v]] for v in verts}
    nonces = {v: secrets.token_bytes(16) for v in verts}

    leaves_hex = [hexf(commit_vertex(v, permuted[v], nonces[v])) for v in verts]
    merkle_root, levels = build_merkle_tree(leaves_hex)

    # pick single edge
    idx = fiat_shamir_select_index(merkle_root, len(edges))
    u,v = edges[idx]

    # prepare openings
    openings = {}
    for w in (u,v):
        openings[w] = {
            "color": permuted[w],
            "nonce": hexf(nonces[w]),
            "merkle_proof": merkle_proof_for_index(levels, w)
        }

    proof = {
        "merkle_root": merkle_root,
        "openings": openings,
    }
    return json.dumps(proof)

# --- zkPoW verifier ---
def zkpow_verify(proof, edges):
    merkle_root = proof["merkle_root"]
    openings = proof["openings"]

    # verify Merkle proofs
    for v_s, opened in openings.items():
        v = int(v_s)
        leaf_hex = hexf(commit_vertex(v, opened["color"], bytes.fromhex(opened["nonce"])))
        if not verify_merkle_proof(merkle_root, leaf_hex, opened["merkle_proof"]):
            print(f"Merkle proof failed for vertex {v}")
            return False

    # recompute chosen edge
    idx = fiat_shamir_select_index(merkle_root, len(edges))
    u,v = map(str, edges[idx])
    if u not in openings or v not in openings:
        print(f"Missing opening for endpoints of edge {idx}")
        return False
    if openings[u]["color"] == openings[v]["color"]:
        print(f"Edge {idx} endpoints same color -> invalid")
        return False
    return True

def main():
    print("==zk-proof-of-work: enabled==")
    for i in range(50):
        print(f"==round {i}==")
        edges, n_vertices = make_graph(i * 33 + 10, 0.8)
        print(json.dumps({"n": n_vertices, "edges": edges}))
        start = time.time()
        proof = json.loads(input("proof: "))
        end = time.time()
        if end - start > 5:
            print("too slow!")
            exit(-1)
        ok = zkpow_verify(proof, edges)
        if ok:
            print("verified!")
        else:
            print("failed!")
            exit(-1)

    flag = open("flag.txt").read()
    print("flag:", flag)

if __name__ == "__main__":
    main()

:::

Bài này khó mà không hiểu sao lại có nhiều lời giải như vậy 🤔.

Nhân tiện thì mình cũng không hiểu bài này cho lắm, chỉ biết đó là một bài ZKP rất phức tạp thôi.

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

import hashlib, secrets, json, time
from concurrent.futures import ThreadPoolExecutor, as_completed

# --- Utility functions ---
def sha256(b: bytes) -> bytes:
    return hashlib.sha256(b).digest()
def hexf(b: bytes) -> str:
    return b.hex()
def commit_vertex(v: int, color_label: int, nonce: bytes) -> bytes:
    return sha256(b"vertex:" + str(v).encode() + b":" + str(color_label).encode() + b":" + nonce)

# --- Merkle tree helpers ---
def build_merkle_tree(leaves_hex):
    leaves = [bytes.fromhex(h) for h in leaves_hex]
    if len(leaves) == 0:
        return hexf(sha256(b"")), [[sha256(b"")]]
    levels = [leaves]
    cur = leaves
    while len(cur) > 1:
        nxt = []
        for i in range(0, len(cur), 2):
            left = cur[i]
            right = cur[i+1] if i+1 < len(cur) else left
            nxt.append(sha256(left + right))
        levels.append(nxt)
        cur = nxt
    return hexf(levels[-1][0]), levels

def merkle_proof_for_index(levels, index):
    proof = []
    idx = index
    for level in levels[:-1]:
        if idx % 2 == 0:
            sib_index = idx + 1 if idx + 1 < len(level) else idx
            sibling = level[sib_index]
            proof.append((hexf(sibling), False))
        else:
            sib_index = idx - 1
            sibling = level[sib_index]
            proof.append((hexf(sibling), True))
        idx //= 2
    return proof

def verify_merkle_proof(root_hex, leaf_hex, proof):
    cur = bytes.fromhex(leaf_hex)
    for sibling_hex, sibling_is_left in proof:
        sibling = bytes.fromhex(sibling_hex)
        if sibling_is_left:
            cur = sha256(sibling + cur)
        else:
            cur = sha256(cur + sibling)
    return hexf(cur) == root_hex

# --- Fiat-Shamir edge selection (k=1 fixed) ---
def fiat_shamir_select_index(root_hex, m):
    return int.from_bytes(hashlib.sha256(root_hex.encode()).digest(), "big") % m

import secrets

def zkpow_forge_chain_fast(edges, n_vertices=1000, max_attempts=1000):
    """
    Forge zkPoW with a chain, building it in O(n):
    - Preprocess edges into adjacency list for fast neighbor lookup
    - Build a chain along random neighbors
    - Color the chain to avoid conflicts
    - Check Fiat-Shamir edge, retry if needed
    """
    verts = list(range(n_vertices))

    # --- preprocess edges into adjacency list ---
    adj = defaultdict(list)
    for u,v in edges:
        adj[u].append(v)
        adj[v].append(u)

    for attempt in range(max_attempts):
        # pick a random starting vertex
        chain = []
        used = set()
        v = secrets.randbelow(n_vertices)
        chain.append(v)
        used.add(v)

        # build chain greedily (O(n) traversal)
        while len(chain) < n_vertices:  # optional: cap chain length at n_vertices
            neighbors = [w for w in adj[v] if w not in used]
            if not neighbors:
                break
            # pick next vertex randomly
            v = secrets.choice(neighbors)
            chain.append(v)
            used.add(v)

        # assign colors along chain to avoid conflicts
        coloring = {}
        for i, v in enumerate(chain):
            forbidden = set()
            if i > 0:
                forbidden.add(coloring[chain[i-1]])
            coloring[v] = secrets.choice([c for c in range(3) if c not in forbidden])

        # assign remaining vertices random colors
        for v in verts:
            if v not in coloring:
                coloring[v] = secrets.randbelow(3)

        # --- commitments / Merkle tree ---
        nonces = {v: secrets.token_bytes(16) for v in verts}
        leaves_hex = [hexf(commit_vertex(v, coloring[v], nonces[v])) for v in verts]
        merkle_root, levels = build_merkle_tree(leaves_hex)

        # --- Fiat-Shamir picks a single edge ---
        idx = fiat_shamir_select_index(merkle_root, len(edges))
        u,v = edges[idx]

        # check if edge endpoints are in chain and colored differently
        if u in chain and v in chain and coloring[u] != coloring[v]:
            openings = {}
            for w in (u,v):
                openings[w] = {
                    "color": coloring[w],
                    "nonce": hexf(nonces[w]),
                    "merkle_proof": merkle_proof_for_index(levels, w)
                }
            proof = {
                "merkle_root": merkle_root,
                "openings": openings,
            }
            return proof

    raise RuntimeError(f"Failed to forge after {max_attempts} attempts")

def zkpow_forge_chain_fast(edges, n_vertices=1000, max_attempts=1000):
    """
    Forge zkPoW by:
    - Building a chain once and fixing its coloring
    - Randomizing colors for remaining vertices on each attempt
    - Checking Fiat-Shamir edge
    """
    verts = list(range(n_vertices))

    # --- preprocess edges into adjacency list ---
    adj = defaultdict(list)
    for u,v in edges:
        adj[u].append(v)
        adj[v].append(u)

    # --- build chain once ---
    chain = []
    used = set()
    v = secrets.randbelow(n_vertices)
    chain.append(v)
    used.add(v)
    while len(chain) < n_vertices:  # optionally cap chain length
        neighbors = [w for w in adj[v] if w not in used]
        if not neighbors:
            break
        v = secrets.choice(neighbors)
        chain.append(v)
        used.add(v)

    # --- assign colors along chain to avoid conflicts ---
    chain_coloring = {}
    for i, v in enumerate(chain):
        forbidden = set()
        if i > 0:
            forbidden.add(chain_coloring[chain[i-1]])
        chain_coloring[v] = secrets.choice([c for c in range(3) if c not in forbidden])

    # --- attempts: randomize remaining vertices ---
    for attempt in range(max_attempts):
        coloring = dict(chain_coloring)  # start with fixed chain colors
        for v in verts:
            if v not in coloring:
                coloring[v] = secrets.randbelow(3)

        # --- commitments / Merkle tree ---
        nonces = {v: secrets.token_bytes(16) for v in verts}
        leaves_hex = [hexf(commit_vertex(v, coloring[v], nonces[v])) for v in verts]
        merkle_root, levels = build_merkle_tree(leaves_hex)

        # --- Fiat-Shamir picks a single edge ---
        idx = fiat_shamir_select_index(merkle_root, len(edges))
        u,v = edges[idx]

        # check if edge endpoints are in chain and colored differently
        if u in chain and v in chain and coloring[u] != coloring[v]:
            openings = {}
            for w in (u,v):
                openings[w] = {
                    "color": coloring[w],
                    "nonce": hexf(nonces[w]),
                    "merkle_proof": merkle_proof_for_index(levels, w)
                }
            proof = {
                "merkle_root": merkle_root,
                "openings": openings,
            }
            return proof

    raise RuntimeError(f"Failed to forge after {max_attempts} attempts")



# Phần lời giải cho thử thách
from pwn import *
from tqdm import trange

# connection = process(["python3", "zkpow.py"])
connection = remote("zkpow.chal.imaginaryctf.org", 1337)

for i in trange(50):
    connection.recvuntil(f"==round {i}==\n".encode())

    a = json.loads(connection.recvline().strip())
    proof = json.dumps(zkpow_forge_chain_fast(a["edges"], a["n"]))
    connection.sendline(proof.encode())

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

connection.success(f"Got flag: {flag}")
# [+] Got flag: ictf{zero_knowledge_proof_more_like_i_have_zero_knowledge_of_how_to_prove_this}

connection.close()

:::

:::success
**Flag:** <b style="color:#f542c8">ictf{zero_knowledge_proof_more_like_i_have_zero_knowledge_of_how_to_prove_this}</b>
:::

<h2 style="color:#4287f5">Summary</h2>

Trên đây là một nửa trong số các thử thách ở hạng mục cryptography trong cuộc thi này. Nhìn chung thì các bài này khá khó và yêu cầu nhiều tư duy cũng như phải tìm tòi tài liệu nhiều.

Hẹn gặp lại các bạn ở phần 2 ~~nếu mình còn muốn làm~~ 👋.