<h1 style="text-align:center; color:#7eb5e0">HCMUS recruitCTF 2025: Part 2</h1>

Dưới đây là lời giải cho các thử thách còn lại ở mục **crypography** cho cuộc thi **HCMUS recruitCTF 2025**.

## Baby Pad
:::spoiler <b>chall.py</b>

from Crypto.Cipher import AES 
import os 

with open('./FLAG.txt', 'rb') as f:
    flag = f.readline()

def pad(message):
    l = -len(message) % 16 
    if l == 0: 
        l = 16 
    return message + bytes([l]) * l 

def check_pad(message):
    l = message[-1]
    if not (l >= 1 and l <= 16):
        return False
    return message[-l:] == bytes([l] * l)

key = os.urandom(16)
iv = os.urandom(16)

def encrypt(message, iv):
    cipher = AES.new(key = key, iv = iv, mode = AES.MODE_CBC)
    return cipher.encrypt(message)

def decrypt(message, iv):
    cipher = AES.new(key = key, iv = iv, mode = AES.MODE_CBC)
    return cipher.decrypt(message)

ct = iv + encrypt(pad(flag), iv)

print(f"enc = {ct.hex()}")

while True: 

    print('1. Send me a message!')
    print('2. 1 is your only choice actually')

    choice = input("Your choice: ") 

    if choice == '1':
        ciphertext = bytes.fromhex(input())
        iv = bytes.fromhex(input())
        message = decrypt(ciphertext, iv)
        if not check_pad(message):
            print("Can't read that")
        else:
            print("Message received!")
    else:
        print("Good bye")
        exit()    

:::

Nhìn đề thì không cần nghi ngờ gì nữa, đây là thử thách liên quan trực tiếp đến tấn công <a href="https://en.wikipedia.org/wiki/Padding_oracle_attack">Padding Oracle</a> rất nổi tiếng rồi. Như vậy thì mình không cần giải thích gì thêm nữa, bạn có thể tìm các file tấn công này trên github, trên mạng,...

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

:::spoiler <b style="color:#7eb5e0">padding_oracle.py</b>

import logging
from tqdm import trange
from Crypto.Util.strxor import strxor


def _attack_block(padding_oracle, iv, c):
    logging.info(f"Attacking block {c.hex()}...")
    r = bytes()
    for i in reversed(range(16)):
        s = bytes([16 - i] * (16 - i))
        for b in trange(256):
            iv_ = bytes(i) + strxor(s, bytes([b]) + r)
            if padding_oracle(iv_, c):
                r = bytes([b]) + r
                break
        else:
            raise ValueError(f"Unable to find decryption for {s}, {iv}, and {c}")

    return strxor(iv, r)


def attack(padding_oracle, iv, c):
    """
    Recovers the plaintext using the padding oracle attack.
    :param padding_oracle: the padding oracle, returns True if the padding is correct, False otherwise
    :param iv: the initialization vector
    :param c: the ciphertext
    :return: the (padded) plaintext
    """
    p = _attack_block(padding_oracle, iv, c[0:16])
    for i in range(16, len(c), 16):
        p += _attack_block(padding_oracle, c[i - 16:i], c[i:i + 16])

    return p

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

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

HOST = "vm.daotao.antoanso.org"; PORT = 34085
connection = remote(HOST, PORT)

connection.recvuntil(b"enc = ")
information = bytes.fromhex(connection.recvline().strip().decode())

iv = information[:16]; ct = information[16:]

def oracle(iv: bytes, ciphertext: bytes) -> bool:
    connection.sendlineafter(b"Your choice: ", b"1")
    connection.sendline(ciphertext.hex().encode())
    connection.sendline(iv.hex().encode())

    receive = connection.recvline().strip().decode()

    return receive == "Message received!"

solution = attack(oracle, iv, ct)

flag = unpad(solution, 16).decode()
connection.success(f"Got flag: {flag}")
# [+] Got flag: BPCTF{Just_a_simple_padding_oracle_attack_to_warm_up_49fab148518a}

connection.close()

:::

:::success
**Flag: BPCTF{Just_a_simple_padding_oracle_attack_to_warm_up_49fab148518a}**
:::

## Baby RSA 1
:::spoiler <b>chall.py</b>

from Crypto.Util.number import *
from Crypto.PublicKey import RSA 

with open('./FLAG.txt', 'rb') as f:
    flag = f.read()

def gen_key():
    key = RSA.generate(2024)
    public_key = (key.n, key.e)
    private_key = (key.p, key.q, key.d)
    return public_key, private_key

def decrypt_data(c, private_key, q_inv):
    """
    https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Using_the_Chinese_remainder_algorithm
    """
    p, q, d = private_key[0], private_key[1], private_key[2] 
    dp, dq = d % (p - 1), d % (q - 1) 
    m1 =  pow(c, dp, p)
    m2 = pow(c, dq, q)
    h = q_inv * (m1 - m2) % p
    m = m2 + h * q % (p * q) 
    return long_to_bytes(m)

def get_encrypted_flag(flag, public_key):
    n, e = public_key[0], public_key[1]
    flag = bytes_to_long(flag)
    flag_enc = pow(flag, e, n)
    return long_to_bytes(flag_enc)

border = '-' * 69
public_key, private_key = gen_key() 

flag_enc = get_encrypted_flag(flag, public_key).hex()

c = ''

while True:
    print(border)
    print('1. Decrypt data')
    print('2. Get public key')
    print('3. Get encrypted flag')
    print(border)
    
    choice = input('Enter your choice: ')

    if choice == '1':
        if c == '':
            c = input('Enter your ciphertext in hex string: ')
            c = int(c, 16)
            if c == int(flag_enc, 16):
                print("No cheating")
                exit()

        num = int(input('Enter your magic number: ')) 
        msg = decrypt_data(c, private_key, num).hex()
        print(msg)

    elif choice == '2':
        print(f'n = {public_key[0]}')
        print(f'e = {public_key[1]}')

    elif choice == '3':
        print(flag_enc)

    else:
        print('Bye')
        exit()   

:::

Sau khi đọc kỹ đề bài, mình phát hiện đây là một thử thách liên quan đến lỗi triển khai của thuật toán RSA. Ta chỉ được nhập một văn bản mã để dùng trong suốt phiên kết nối, nhưng ta có thể nhập bao nhiêu số ma thuật tùy thích!

Để ý rằng server không cho phép ta gửi thẳng $c_{\text{flag}}$ đến server để tiến hành giải mã. Như vậy ta sẽ chọn $c \neq c_{\text{flag}}$ và lấy hai số ma thuật ngẫu nhiên $\text{num}_{a}$ và $\text{num}_{b}$, Sau khi server tính toán, nó sẽ trả về cho chúng ta:

$$
\left\{
\begin{align}
m_{a} = m_{2} + (h_{a}q \bmod{pq}) \\
m_{b} = m_{2} + (h_{b}q \bmod{pq}) \\
\end{align}
\right.
\Rightarrow m_{a} - m_{b} \equiv 0 \pmod{q}
$$

Như vậy ta sẽ tìm được $q = \gcd(m_{a} - m_{b}, n)$ với xác suất đúng gần như $100\%$, từ đó ta tiến hành khôi phục **flag** như bình thường thôi!

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

from pwn import *
from Crypto.Util.number import long_to_bytes, bytes_to_long
import random
from math import gcd

HOST = "vm.daotao.antoanso.org"; PORT = 34173

connection = remote(HOST, PORT)

connection.sendlineafter(b'Enter your choice: ', b'3')
encrypted_flag = connection.recvline().strip().decode()
encrypted_flag = bytes_to_long(bytes.fromhex(encrypted_flag))


connection.sendlineafter(b'Enter your choice: ', b'2')
n = int(connection.recvline()[3:].strip().decode())
e = int(connection.recvline()[3:].strip().decode())
new_encryted_flag = (pow(2, e, n)*encrypted_flag) % n


connection.sendlineafter(b'Enter your choice: ', b'1')
connection.sendlineafter(b'Enter your ciphertext in hex string: ', f"{new_encryted_flag}".encode())
connection.sendlineafter(b'Enter your magic number: ', f"{random.randrange(1, n)}".encode())

ma = connection.recvline().strip().decode()
ma = bytes_to_long(bytes.fromhex(ma))

connection.sendlineafter(b'Enter your choice: ', b'1')
connection.sendlineafter(b'Enter your magic number: ', f"{random.randrange(1, n)}".encode())

mb = connection.recvline().strip().decode()
mb = bytes_to_long(bytes.fromhex(mb))

q = gcd(abs(ma - mb), n)
p = n//q

phi = (p - 1)*(q - 1)
d = pow(e, -1, phi)

message = pow(encrypted_flag, d, n)

flag = long_to_bytes(message).decode()
connection.success(f"Got flag: {flag}")
# [+] Got flag: BPCTF{Thank_you_naul_for_finding_this_not_so_intended_solution_901832123ab}

connection.close()

:::

:::success
**Flag: BPCTF{Thank_you_naul_for_finding_this_not_so_intended_solution_901832123ab}**
:::

## Baby RSA 2
:::spoiler <b>chall.py</b>

from Crypto.Util.number import *
from Crypto.PublicKey import RSA 

with open('./FLAG.txt', 'rb') as f:
    flag = f.read()

def gen_key():
    key = RSA.generate(2024)
    public_key = (key.n, key.e)
    private_key = (key.p, key.q, key.d)
    return public_key, private_key

def decrypt_data(c, private_key, q_inv):
    """
    https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Using_the_Chinese_remainder_algorithm
    """
    p, q, d = private_key[0], private_key[1], private_key[2] 
    dp, dq = d % (p - 1), d % (q - 1) 
    m1 =  pow(c, dp, p)
    m2 = pow(c, dq, q)
    h = q_inv * (m1 - m2) % p 
    m = m2 + h * q % (p * q) 
    return long_to_bytes(m)

def get_encrypted_flag(flag, public_key):
    n, e = public_key[0], public_key[1]
    flag = bytes_to_long(flag)
    flag_enc = pow(flag, e, n)
    return long_to_bytes(flag_enc)

border = '-' * 69
public_key, private_key = gen_key() 

flag_enc = get_encrypted_flag(flag, public_key).hex()

num = ''

while True:
    print(border)
    print('1. Decrypt data')
    print('2. Get public key')
    print('3. Get encrypted flag')
    print(border)
    
    choice = input('Enter your choice: ')

    if choice == '1':
        c = input('Enter your ciphertext in hex string: ')
        c = int(c, 16)
        if c == int(flag_enc, 16):
            print("No cheating")
            exit()

        if num == '':
            num = int(input('Enter your magic number: '))
            try: assert num.bit_length() > 69 and num.bit_length() < 690
            except AssertionError: print("Bye"); exit()  

        msg = decrypt_data(c, private_key, num).hex()
        print(msg)

    elif choice == '2':
        print(f'n = {public_key[0]}')
        print(f'e = {public_key[1]}')

    elif choice == '3':
        print(flag_enc)

    else:
        print('Bye')
        exit()

:::

Lần này thì ngược lại, ta chỉ được nhập một số ma thuật để dùng trong suốt phiên kết nối, nhưng ta có thể nhập bao nhiêu văn bản mã tùy thích!

Vì $p$ và $q$ là các số nguyên tố rất lớn (khoảng $1024$ bit), ta có thể ước lượng rằng $\text{flag} << p$ và $\text{flag} << q$ nên $m_{1} = m \bmod{p} = m$ và $m_{2} = m \bmod{q} = m$ với $m$ không quá lớn so với $\text{flag}$.

Như vậy ta sẽ chọn $\text{num}$ ngẫu nhiên và $c = k^{e}c_{\text{flag}}$ sao cho $k\cdot\text{flag} < p$ và $k\cdot\text{flag} < q$ (chọn $k$ nhỏ thôi, $k = 2$ chẳng hạn). Theo thuật toán RSA, chúng ta sẽ nhận được văn bản rõ $m = k\cdot\text{flag}$ tương ứng (cái này dễ chứng minh nên các bạn tự chứng minh đi nhé).
Sau khi gửi cho server thì server sẽ tính ra được $m_{1} = m_{2} = m$, đồng thời $h = \text{num}(m_{1} - m_{2}) \bmod{p} = 0 \bmod{p} = 0$. Do đó, server sẽ trả về cho chúng ta $m_{\text{final}} = m_{2} + (h\cdot q \bmod{pq}) = m + (0 + \bmod{pq}) = k\cdot\text{flag}$.
Vậy là ta đã khôi phục lại được **flag** bằng cách tính $flag = \frac{m_{\text{final}}}{k}$ rồi!

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

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

from pwn import *
from Crypto.Util.number import long_to_bytes, bytes_to_long
import random
from math import gcd

HOST = "vm.daotao.antoanso.org"; PORT = 33905
connection = remote(HOST, PORT)

connection.sendlineafter(b'Enter your choice: ', b'3')
encrypted_flag = connection.recvline().strip().decode()
encrypted_flag = bytes_to_long(bytes.fromhex(encrypted_flag))


connection.sendlineafter(b'Enter your choice: ', b'2')
n = int(connection.recvline()[3:].strip().decode())
e = int(connection.recvline()[3:].strip().decode())

new_encryted_flag = (pow(2, e, n)*encrypted_flag) % n

connection.sendlineafter(b'Enter your choice: ', b'1')
connection.sendlineafter(b'Enter your ciphertext in hex string: ', hex(new_encryted_flag)[2:].encode())
connection.sendlineafter(b'Enter your magic number: ', f"{random.randrange(2**70, 2**689)}".encode())

new_m = connection.recvline().strip().decode()
new_m = bytes_to_long(bytes.fromhex(new_m))

int_flag = new_m // 2

flag = long_to_bytes(int_flag).decode()
connection.success(f"Got flag: {flag}")
# [+] Got flag: BPCTF{How_many_queries_did_you_use?_af434b1f1aec}

connection.close()

:::

:::success
**Flag: BPCTF{How_many_queries_did_you_use?_af434b1f1aec}**
:::

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

from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad  
import hashlib 
import random 

flag = b'BPCTF{??????????????????????????????????}'
               
p = 307119639745751469235752346635781766287891925576026383455555022557456022240440834093
s = random.randint(2, p - 1)

class Point:
    def __init__(self, x, y):
        self.x = x % p 
        self.y = y % p 
    def __add__(self, other):
        x = (self.x * other.y + self.y * other.x) % p 
        y = (self.y * other.y - self.x * other.x) % p 
        return Point(x, y)
    def __mul__(self, n):
        R = Point(0, 1)
        P = Point(self.x, self.y)
        while n > 0:
            if n % 2:
                R += P 
            P += P
            n >>= 1
        return R


G = Point(269706932193805755534663280853021102698237187960981530911954571811593219484562877686, 64681749570942311062995683097786979736444359061659263379460834230175114182600310869)

P = G * s

k = hashlib.sha256(long_to_bytes(s)).digest()[:16]
iv = random.randbytes(16)

cipher = AES.new(key = k, iv = iv, mode = AES.MODE_CBC)

ct = cipher.encrypt(pad(flag, 16))

print(f"P = {P.x, P.y}")
print(f"iv = {iv}")
print(f"ct = {ct}")

"""
P = (66458087392047205569134518238677614962987250315628901489579974197182257590937156372, 60031618721128621274849877211225119325796011838618857532417555895902612101315597171)
iv = b'\x84G\xd8\x9c\x8f-\xdb \r\x0c3\x07\xc2\xde\xa7\xfa'
ct = b'0\x8a\x8c><p^\x9d+\xa5\xcb%\xc2\x8c78\xd3\xe1w\xc8\xd12~SL\xe1\x1c\xadw\xdc\x9b\xd3\xfe\xba\xa5\xb04\x1b\x12D\x9fC\x9b\xcd\xf3V|\x9b'
"""

:::

Bài này là một bài khá nặng về toán học, bạn nên đọc kỹ file thử thách và hiểu nó trước khi đọc write-up này!

Trong thử thách, ta có định nghĩa điểm $P = (x, y)$ trên trường $\mathbb{F}_{p}$ với $p$ là một số nguyên tố (ai tinh ý sẽ nhận ra ngay $p \equiv 1 \pmod{4}$, cái này rất quan trọng để thử thách có thể giải được). Ta có ngay các tính chất sau của điểm được định nghĩ trong thử thách:

- Với $P = (x_{1}, y_{1}) ,~ Q = (x_{2}, y_{2})$ thì $P + Q = (x_{1}y_{2} + x_{2}y_{1},~ y_{1}y_{2} - x_{1}x_{2})$.
- Với $P = (x, y)$ thì $nP = \underbrace{P + P + \dots P}_{n\text{ điểm P}}$.

Nhìn qua thì chẳng thấy ý tưởng gì đúng không? Vậy bạn hãy thử nhân hai số phức xem và bạn sẽ thấy được hướng giải của bài toán:
Với $z_{1} = y_{1} + i\cdot x_{1},~ z_{2} = y_{2} + i\cdot x_{2}$ thì ta có $z_{1}z_{2} = (y_{1}y_{2} - x_{1}x_{2}) + i\cdot (x_{1}y_{2} + x_{2}y_{1})$.

Bạn thấy có gì đó tương đồng với phép cộng điểm ở trên phải không? Vậy là ta đã tìm được đường đi cho thử thách này rồi! Ta xét ánh xạ:

$$
\begin{array}{rcl}
\varphi : &\mathbb{F}_{p}^\times \times \mathbb{F}_{p}^\times &\to \mathbb{F}_{p}^\times, \\[1mm]
&(x, y) &\mapsto y + ix
\end{array}
$$

trong đó $i$ là phần tử trong nhóm $\mathbb{F}_{p}^\times$ sao cho $i^2 = -1$ (tồn tại một phần tử $i$ như thế trong nhóm $\mathbb{F}_{p}^\times$ vì $p \equiv 1 \pmod{4}$ ). Khi đó ta dễ dàng chỉ ra rằng:

$$
\varphi(P + Q) = \varphi(P)\varphi(Q)
$$

Từ đây ta có một hệ quả như sau: $\varphi(nP) = \varphi(\underbrace{P + P + \dots P}_{n\text{ điểm P}}) = \underbrace{\varphi(P)\varphi(P)\dots\varphi(P)}_{n\text{ lần} ~ \varphi(P)} = \varphi(P)^{n}$

Quay trở lại bài toán, ta có: $\varphi(P) = \varphi(sG) = \varphi(G)^{s}$.
Như vậy ta đã đưa bài toán trở về bài toán logarithm rời rạc trên nhóm $\mathbb{F}_{p}^\times$, hơn thế nữa bằng cách kiếm tra ta thấy $p - 1$ là số **smooth** nên thuật toán <a href="https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm">Pohlig–Hellman</a> hoạt động rất tốt và cho ta kết quả rất nhanh.
Vậy là ta đã tìm được $s$, từ đây ta có thể dễ khôi phục lại **flag**.

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

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

from sage.all import GF, PolynomialRing, discrete_log
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad  
import hashlib 

p = 307119639745751469235752346635781766287891925576026383455555022557456022240440834093
assert p%4 == 1, "Error 1!"

F = GF(p)

R = PolynomialRing(F, names='x'); x = R.gen()
i = F(R(x**2 +1).roots()[0][0])

phi_G = F(64681749570942311062995683097786979736444359061659263379460834230175114182600310869) + i*F(269706932193805755534663280853021102698237187960981530911954571811593219484562877686)

phi_P = F(60031618721128621274849877211225119325796011838618857532417555895902612101315597171) + i*F(66458087392047205569134518238677614962987250315628901489579974197182257590937156372)

s = discrete_log(phi_P, phi_G)

k = hashlib.sha256(long_to_bytes(int(s))).digest()[:16]
iv = b'\x84G\xd8\x9c\x8f-\xdb \r\x0c3\x07\xc2\xde\xa7\xfa'
ct = b'0\x8a\x8c><p^\x9d+\xa5\xcb%\xc2\x8c78\xd3\xe1w\xc8\xd12~SL\xe1\x1c\xadw\xdc\x9b\xd3\xfe\xba\xa5\xb04\x1b\x12D\x9fC\x9b\xcd\xf3V|\x9b'

cipher = AES.new(key = k, iv = iv, mode = AES.MODE_CBC)

pt = unpad(cipher.decrypt(ct), 16)

flag = pt.decode()
print("[!] Got flag:", flag)
# [!] Got flag: BPCTF{Group_isomorphism_and_smooth_order}

:::

:::success
**Flag: BPCTF{Group_isomorphism_and_smooth_order}**
:::

## Summary
Dưới đây là các thử thách còn lại của cuộc thi này, trừ bài cuối khi phải dùng khá nhiều toán thì các bài còn lại tương đối đơn giản và nhẹ nhàng. Chúc các bạn một ngày tốt lành 👋.