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

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

## Super Computer
:::spoiler <b>chall.py</b>

from Crypto.Util.number import GCD
from Crypto.Cipher import AES
import random 

k1 = 721919140332708275664160621428853988653441049264644517303176376909
k2 = 762740838008948738628397951381835990843814483667554565638672490531

# This challenge is free flag! If you have super computer :) 
k = GCD((2024 ** k1 - 1) * (2024 ** k1 + 1), (2024 ** k2 - 1) * (2024 ** k2 + 1)) 

random.seed(k)

k = random.randbytes(16)
iv = b"S\x0f\xac'\xd0\x18\xfb\xe3\x92\xfdoc\x93\x7fJ\xfc"
ciphertext = b"8\x9a>&=Q\xc14\xcf\xab\xac\xbaa@\xa0s\xd4T\x18\x1f\x82\x04F\xdb\xa2\xc2\xb9V\x04\xcbG6\xe54U\x1d2\xe2q\x0b\xe6\x9b\x1e\x8d\xc6\x8c7/"
cipher = AES.new(key = k, iv = iv, mode = AES.MODE_CBC)

flag = cipher.decrypt(ciphertext)

print(flag)

:::

Ta có thể sử dụng một định lý cơ bản của lý thuyết số (nhưng không cơ bản cho lắm trong HSG trung học cơ sở) để tăng tốc độ tính toán, định lý đó được phát biểu như sau:
Với mọi $a, m, n \in \mathbb{Z}^{+}$, ta có:
$$\gcd(a^{n} - 1, a^{m} - 1) = a^{\gcd(n, m)} - 1$$

Bạn có thể đọc thêm chứng minh <a href="https://math.stackexchange.com/questions/7473/prove-that-gcdan-1-am-1-a-gcdn-m-1">ở đây</a>, dưới đây là toàn bộ lời giải cho thử thách:

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

from Crypto.Util.number import GCD
from Crypto.Cipher import AES
import random 

k1 = 721919140332708275664160621428853988653441049264644517303176376909
k2 = 762740838008948738628397951381835990843814483667554565638672490531

# This challenge is free flag! If you have super computer :) 
# k = GCD((2024 ** k1 - 1) * (2024 ** k1 + 1), (2024 ** k2 - 1) * (2024 ** k2 + 1)) 
k = 2024**GCD(2*k1, 2*k2) - 1

random.seed(k)

k = random.randbytes(16)
iv = b"S\x0f\xac'\xd0\x18\xfb\xe3\x92\xfdoc\x93\x7fJ\xfc"
ciphertext = b"8\x9a>&=Q\xc14\xcf\xab\xac\xbaa@\xa0s\xd4T\x18\x1f\x82\x04F\xdb\xa2\xc2\xb9V\x04\xcbG6\xe54U\x1d2\xe2q\x0b\xe6\x9b\x1e\x8d\xc6\x8c7/"
cipher = AES.new(key = k, iv = iv, mode = AES.MODE_CBC)

flag = cipher.decrypt(ciphertext).strip().decode()

print("[!] Got flag:", flag)
# [!] Got flag: BPCTF{All_we_need_is_Euclid_algorithm}

:::

:::success
**Flag: BPCTF{All_we_need_is_Euclid_algorithm}**
:::

## Super Computer V2
:::spoiler <b>chall.py</b>

from Crypto.Cipher import AES 
import random 

p = 105063592580446545974028951012743983897531876308535061339451568776273476140417
a = [83976481011811924301399130599504493293806898813567214331578547737846462043958, 49020426275786164529115108197272670769137595551571093637487791519433419519672, 24128105217328007401966909205085981217503713864081435807557452995781759742691, 54164402277699203441372828355514660347224703731247371001251599709472819892728, 5692038086237571692337343150891799220298365811757620367764289696380335050730, 9194117858273293290441837426276641586104842710061165598417982956745859622444, 27514892046750325649899981908633136074585793442699873185550644927834059630396, 66943725126331355485802310409645040036783514684318190205044041417883671830813, 36611954202140140239054776427180396851470554264500586218901125625358436893646, 93863495610885066386571402764570126016623604962463646403287688220849161122613]
b = [97461761096716147515500249810325859398244538389518130625167636466504806053237, 16186849429230042905493135221645960782811658483413984147534270789857649397900, 71342178650803093723481761619050183147490358888778566439516835390010233583079, 42978771428288111481549054267767962257445180314707234054048040896605726288851, 29120967694716870074542540604659996320145561630287811543954439503459626728291, 42698044025699644061005796009375197205179997240105171525488864698040253468486, 7809495582561305433394495659190738835412543684981410733357553129731203148539, 32385280315917393807024145684356627341683296786146343663491116566930261796667, 13004050673282999217589086204520195844228711320714522230534397332477244173876, 71584418374288378249025460600779108813126354610745231566224182660591294310622]
y = b

# This challenge is free flag! If you have super computer v2 :) 
n = 2 ** 2976579765

for i in range(n):
    x = sum(aa * yy for aa, yy in zip(a, y)) % p
    y = [x] + y[:0:-1]

random.seed(x)

k = random.randbytes(16)

iv = b"S\x0f\xac'\xd0\x18\xfb\xe3\x92\xfdoc\x93\x7fJ\xfc"
ct = b"9\x18~C<3\xba\x04\xfb\x04t\x94\x7f\x86t\xb7\x9b\x9b\xc0N8\x0c\x8er]\x14\xfd\x033\xac;PVa\xd0m\xfdH\xf4pI\xf7s\xd5\xc2\x03\t\x9a\x1d\x96<?k\x16\xc0GVp\xcdj#\xde\xe8\x991\xb7k\xc7\xe2^\xd5h\xa7\xf8\x07\x02\xf9\xcee\xbej \x86y\xf6\xf3T\x8c8\x85\x11Ps\xb1E\xe5WK\xb3\xcbE}\xbb\xc7\x10\xea\xb92FJ\xf6\xde&I\x99\xd8\xa9\xae\x94\x0675\xcelc\x1a\xe4\x9c"

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

print(cipher.decrypt(ct))

:::

Đây là phiên bản nâng cấp của bài trên (và tất nhiên sẽ khó hơn rồi). Chúng ta sẽ có hai danh sách `a` và `b` có độ dài $10$ và một số nguyên `n` siêu lớn, chương trình sẽ lặp qua số nguyên đó lần và làm các phép biến đổi kỳ lạ liên quan đến một biến `p` và `y` để được `x`. Cuối cùng họ sẽ đưa `x` để làm **seed** cho hàm giả ngẫu nhiên của python.
Như vậy nhiệm vụ của chúng ta là bằng một cách nào đó tìm được giá trị `x` của chương trình.

Đặt: $a = \left( a_{0}, a_{1}, \dots, a_{9} \right)$ và $b = \left( b_{0}, b_{1}, \dots, b_{9} \right)$, dễ thấy $x = a \cdot b \bmod{p}$.
Đặt: $y_0 = b$, từ chương trình ta có biểu thức trong trường $\mathbb{F}_{p}$ như sau:

$$
y_1 = \left(x, b_{9}, b_{8}, \dots, b_{1} \right) = \left(b_{0}, b_{1}, \dots, b_{9} \right) \cdot
\begin{pmatrix}
a_0 & & & & 1 \\
a_1 & & & ⋰ & \\
\vdots & & 1 & & \\
a_9 & 1 & & &
\end{pmatrix}
= y_{0}\cdot
\begin{pmatrix}
a_0 & & & & 1 \\
a_1 & & & ⋰ & \\
\vdots & & 1 & & \\
a_9 & 1 & & &
\end{pmatrix}
$$

Đặt: $A =
\begin{pmatrix}
a_0 & & & & 1 \\
a_1 & & & ⋰ & \\
\vdots & & 1 & & \\
a_9 & 1 & & &
\end{pmatrix}$, bằng phương pháp quy nạp ta chứng minh được:

$$
y_k = y_{k-1}A = \dots = y_{0}A^{k}, \forall k = 0, 1, 2, \dots
$$

Tiếp theo, ta sẽ thấy $A$ là <a href="https://en.wikipedia.org/wiki/Nilpotent_matrix">ma trận lũy linh</a> trên $\mathbb{F}_{p}$ (ta có thể dùng **SageMath** để kiểm chứng điều đó). Gọi $r$ là bậc của $A$, khi đó $A^{k} = A^{(k \bmod{r})}$, như vậy:

$$
y_n = y_{0}A^{n} = y_{0}A^{(n \bmod{r})}
$$

Nhờ vào <a href="https://en.wikipedia.org/wiki/Exponentiation_by_squaring">thuật toán **lũy thừa bằng bình phương**</a> mà chúng ta có thể tính $n \bmod{r}$ với tốc độ cực kỳ nhanh! Như vậy là chúng ta đã có thể giảm thời gian tính xuống rất rất nhiều rồ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 sage.all import Matrix, GF, is_prime, vector
from tqdm import trange
from Crypto.Cipher import AES 
import random 
import re

p = 105063592580446545974028951012743983897531876308535061339451568776273476140417
a = [83976481011811924301399130599504493293806898813567214331578547737846462043958, 49020426275786164529115108197272670769137595551571093637487791519433419519672, 24128105217328007401966909205085981217503713864081435807557452995781759742691, 54164402277699203441372828355514660347224703731247371001251599709472819892728, 5692038086237571692337343150891799220298365811757620367764289696380335050730, 9194117858273293290441837426276641586104842710061165598417982956745859622444, 27514892046750325649899981908633136074585793442699873185550644927834059630396, 66943725126331355485802310409645040036783514684318190205044041417883671830813, 36611954202140140239054776427180396851470554264500586218901125625358436893646, 93863495610885066386571402764570126016623604962463646403287688220849161122613]
b = [97461761096716147515500249810325859398244538389518130625167636466504806053237, 16186849429230042905493135221645960782811658483413984147534270789857649397900, 71342178650803093723481761619050183147490358888778566439516835390010233583079, 42978771428288111481549054267767962257445180314707234054048040896605726288851, 29120967694716870074542540604659996320145561630287811543954439503459626728291, 42698044025699644061005796009375197205179997240105171525488864698040253468486, 7809495582561305433394495659190738835412543684981410733357553129731203148539, 32385280315917393807024145684356627341683296786146343663491116566930261796667, 13004050673282999217589086204520195844228711320714522230534397332477244173876, 71584418374288378249025460600779108813126354610745231566224182660591294310622]
y = b

# n = 2 ** 2976579765

assert len(b) == 10, "Error 1!"
assert is_prime(p), "Error 2!"

A = Matrix(GF(p), 10)
for i in range(10):
    A[i, 0] = a[i]
for i in range(9):
    A[9 - i, i+1] = 1

# for row in A:
#     print(row.list())

# order = A.multiplicative_order()
# print(order)
order = 13132949072555818246753618876592997987191484538566882667431446097034184517552

r = pow(2, 2976579765, order)

y0 = vector(GF(p), y)
yn = y0*(A**(r))

x = int(yn.list()[0])

random.seed(x)

k = random.randbytes(16)

iv = b"S\x0f\xac'\xd0\x18\xfb\xe3\x92\xfdoc\x93\x7fJ\xfc"
ct = b"9\x18~C<3\xba\x04\xfb\x04t\x94\x7f\x86t\xb7\x9b\x9b\xc0N8\x0c\x8er]\x14\xfd\x033\xac;PVa\xd0m\xfdH\xf4pI\xf7s\xd5\xc2\x03\t\x9a\x1d\x96<?k\x16\xc0GVp\xcdj#\xde\xe8\x991\xb7k\xc7\xe2^\xd5h\xa7\xf8\x07\x02\xf9\xcee\xbej \x86y\xf6\xf3T\x8c8\x85\x11Ps\xb1E\xe5WK\xb3\xcbE}\xbb\xc7\x10\xea\xb92FJ\xf6\xde&I\x99\xd8\xa9\xae\x94\x0675\xcelc\x1a\xe4\x9c"

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

message = cipher.decrypt(ct)

flag = re.search(rb"BPCTF\{[!-~]+\}", message).group()

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

:::

:::success
**Flag: BPCTF{Man1pula7in6_M4tr1X_l1k3_M4gic}**
:::

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

from sage.all import *
print(sin(int.from_bytes(b'BPCTF{redact}', "big")).n(1024))

# -0.8796972610321827563892090184824431008849260677490432314800583299448516158025013449932132939406906383183958298737064924365086071175560501988906753789730930083786567693599492134797230852234912883707809575810061997560245813817036699876221799005582540720450489560203640716799332256956137334545111300264623648046

:::

Bài này giống hệt với <a href="https://hackmd.io/@0160ca14/BJfAJeQslx#Elita-Challenge-2-Elita">bài này</a>, chỉ khác là lần này ta không biết được độ dài **flag** nên việc ước lượng trọng số trở nên khó khăn hơn một chút. Tuy nhiên ta có thể thử nhiều giá trị trọng số khác nhau để giải bài này thay vì rập khuôn tính toán công thức!
Vì mình đã phân tích rất kỹ bài tương tự kia, nên bài này mình sẽ không giải thích gì thêm.

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 RealField, arcsin, pi, identity_matrix, QQ, round
from Crypto.Util.number import long_to_bytes


R = RealField(4444)

t = R("-0.8796972610321827563892090184824431008849260677490432314800583299448516158025013449932132939406906383183958298737064924365086071175560501988906753789730930083786567693599492134797230852234912883707809575810061997560245813817036699876221799005582540720450489560203640716799332256956137334545111300264623648046")

PI =  pi.n(4444)
r = PI - arcsin(t)

basis = identity_matrix(QQ, 3)
weight1 = 2**500; weight2 = 2**700

basis[1,1] = QQ(1)/weight1
basis[0,2] = r*weight2
basis[1,2] = 2*PI*weight2
basis[2,2] = -1*weight2

# for row in basis:
#     print(row.list())

reduced_basis = basis.LLL()

# for row in reduced_basis:
#     print(row.list())

for row in reduced_basis:
    if(abs(row[0]) == 1):
        k = round(R(row[1])*weight1)
        break

m = round(r + abs(k) * 2 * PI)

flag = long_to_bytes(m).decode()
print("[!] Got flag:", flag)
# [!] Got flag: BPCTF{c4n_LLL_be_used_too?!?}

:::

:::success
**Flag: BPCTF{c4n_LLL_be_used_too?!?}**
:::

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

from Crypto.Util.number import getPrime, isPrime

p = getPrime(256)
q = getPrime(256) 
N = p*q

e = 65537

flag = b'BPCTF{redact}' 
c = pow(int.from_bytes(flag, 'big'), e, N)
gift = (p+q)>>40
print(f'N = {N}\nc = {c}\ngift = {gift}')


"""
N = 5758124415184468271370250630048687746812715972269092676700260830924771547226161680827118153372606993872590019171624226415454063566537634596851695999313069
c = 4258014490469377191207443169980969026536758269486705363402307773455639773007422079769567310663689852817179059312032143236005345809847891632360620594960862
gift = 139200565274113272217771369795858181556454302427519574149545982701
"""

:::

Lại là một bài mà chúng ta đã có bài tương tự, bạn có thể xem bài tương tự <a href="https://hackmd.io/BVk5kipBTaSnavYXlxMSPw?view#Too-Little-Information-NBCTF-2023"> ở đây</a>. Nội dung thì y hệt bài bên kia, chỉ khác một chút về thông số và hơi khó khăn khi ước lượng khi mà không biết ước lượng bit cho $p$ và $q$ mà thôi!

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

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

from sage.all import var, PolynomialRing, Zmod
from Crypto.Util.number import long_to_bytes

e = 65537
N = 5758124415184468271370250630048687746812715972269092676700260830924771547226161680827118153372606993872590019171624226415454063566537634596851695999313069
c = 4258014490469377191207443169980969026536758269486705363402307773455639773007422079769567310663689852817179059312032143236005345809847891632360620594960862
gift = 139200565274113272217771369795858181556454302427519574149545982701

S_approx = gift << 40

p0 = var('p')
p_approx = int((p0**2 - S_approx*p0 + N).roots()[0][0])

R = PolynomialRing(Zmod(N), name='x')
x = R.gen(0)

f = x + p_approx
roots = f.small_roots(X = 2**41, beta = 0.49, epsilon = 1/32)

p = int(f(roots[0]))
q = N//p
d = pow(e, -1, (p-1)*(q-1))

flag = long_to_bytes(pow(c, d, N)).decode()
print("[!] Got flag:", flag)
# [!] Got flag: BPCTF{l4w_priv4ate_key_attack_easy_right?}

:::

:::success
**Flag: BPCTF{l4w_priv4ate_key_attack_easy_right?}**
:::

## Hash Collision
:::spoiler <b>chall.py</b>

import string 
import random 

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

s = string.ascii_letters
l = 20

def check(a):
    if len(a) != 20:
        return True 
    for x in a:
        if x not in s:
            return True 
    return False 

def h(msg, c, m):
    res = 0 
    for x, y in zip(msg, c):
        res += x * y 
        res %= m 
    return res 

m = random.randint(2 ** 127, 2 ** 128)
c = [random.randint(2 ** 69, 2 ** 75) for i in range(l)]

print(f"m = {m}")
print(f"c = {c}")

while True:
    print("Give me two strings a and b of length such that a != b and h(a, c, m) = h(b, c, m): ")
    a = input() 
    b = input()

    if check(a) or check(b):
        print("Can't read that")
        exit()

    if a == b:
        print("No")
        exit()
    
    a = a.encode()
    b = b.encode()

    if h(a, c, m) == h(b, c, m):
        print(f"Congrats! Here's your flag: {flag}")
        exit()

    else:
        print("Unlucky")
        exit()

:::

Bài này sẽ cho chúng ta hai biến `m` và `c` để dùng cho hàm băm tự tạo, nhiệm vụ của chúng ta là tìm ra hai chuỗi chữ cái bất kỳ `a` và `b` khác nhau sao cho chúng mang cùng một giá trị băm tự tạo này để server trả về cho chúng ta **flag**.
Lưu ý là khi đưa hai biến `a` và `b` vào hàm băm, chúng sẽ chuyển thành các danh sách các chữ cái trong chuỗi ở dạng **ASCII**.

Đặt $c = \left(c_{0}, c_{1}, \dots, c_{19} \right)$, $a = \left(a_{0}, a_{1}, \dots, a_{19} \right)$, $b = \left(b_{0}, b_{1}, \dots, b_{19} \right)$. Từ yêu cầu `h(a, c, m) == h(b, c, m)` ta có:

$$
\begin{align}
a\cdot c &\equiv b \cdot c &\pmod{m} \\
\Leftrightarrow (a - b)\cdot c &\equiv 0 &\pmod{m} \\
\Leftrightarrow (a_{0} - b_{0})c_{0} + \dots + (a_{19} - b_{19})c_{19} + km &\equiv 0 &(1)
\end{align}
$$

Đặt: $d_{i} = a_{i} - b_{i}, \forall i = \overline{0, 19}$, khi đó phương trình $(1)$ trở thành:

$$
\Leftrightarrow d_{0}c_{0} + d_{1}c_{1} + \dots + d_{19}c_{19} + km \equiv 0 \hspace{1em} (1)
$$

Lúc này ta chỉ cần lập ma trận như sau:

$$
\textbf{B} =
\begin{bmatrix}
1 & & & & c_{0} \\
& 1 & & & c_{1} \\
& & \ddots & & \vdots \\
& & & 1 & c_{19} \\
& & & & m
\end{bmatrix}
$$

Và sau đó dùng thuật toán **LLL** là ta có thể tìm lại được $d_{i}, \forall i = \overline{0, 19}$. Đến đây thì ta chỉ cần chọn bừa vector $a$ thỏa mãn yêu cầu đề bài và dựa vào đó để tìm vector $b$ hợp lý mà thôi.


Vì các giá trị quá nhỏ nên ta có thể chọn bừa $a_{i}$ mang giá trị $65$ hoặc $90$ tùy vào dấu của $a_{i}$.

>[!Important] Lưu ý
>Có thể tấn công này sẽ không thành công nếu nó không tìm ra một vector ngắn có thành phần cuối bằng $0$, lúc này ta chỉ cần chạy lại là được.

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

from sage.all import ZZ, identity_matrix, matrix
from pwn import *
import json, re
from tqdm import trange

def h(msg, c, m):
    res = 0 
    for x, y in zip(msg, c):
        res += x * y 
    return res % m

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

connection = remote(HOST, PORT)
m = int(connection.recvline()[3:].strip().decode())
c = json.loads(connection.recvline()[3:])

basis = identity_matrix(ZZ, 21)

for i in trange(20):
    basis[i, -1] = c[i]
basis[-1, -1] = m

# for row in basis:
#     print(row.list())

reduced_basis = basis.LLL()

# for row in reduced_basis:
#     print(row.list())

for row in reduced_basis:
    if(int(row[-1]) == 0):
        delta_list = row[:-1]
        break

a, b = [], []

for delta in delta_list:
    if(delta < 0):
        a.append(90)
        b.append(90 + delta)
    else:
        a.append(65)
        b.append(65 + delta)

assert h(bytes(a), c, m) == h(bytes(b), c, m), "Critical Error!"

a = bytes(a).decode()
b = bytes(b).decode()

connection.recvuntil(b"Give me two strings a and b of length such that a != b and h(a, c, m) = h(b, c, m): \n")
connection.sendline(f"{a}".encode())
connection.sendline(f"{b}".encode())

message = connection.recvline()

flag = re.search(rb"BPCTF\{[!-~]+\}", message).group()

connection.success(f"Got flag: {flag.decode()}")
# [+] Got flag: BPCTF{Yet_another_lattice_basis_reduction_algorithm_challenge_021ad1e3f365}


connection.close()

:::

:::success
**Flag: BPCTF{Yet_another_lattice_basis_reduction_algorithm_challenge_021ad1e3f365}**
:::

## Summary
Trên đây là một nửa trong số các thử thách trong cuộc thi này, chúc các bạn một ngày vui vẻ và hẹn gặp lại ở phần tiếp theo😃!