<h1 style="text-align:center; color:#164d36">
AmateursCTF 2025
</h1>
Dưới đây là lời giải của các thử thách mật mã học trong cuộc thi **AmateursCTF 2025**.
Cuộc thi này ra đề khá ngắn gọn và dễ hiểu đề, đồng thời nó cũng cung cấp các kiến thức hay ho cho mình. Ngoài ra mình cũng học được một số kỹ thuật nhập câu lệnh cho AI để giải quyết các bài CTF từ những cao nhân trong cuộc thi này.
## aescure
:::spoiler <b>chall.py</b>
```python=
from Crypto.Cipher import AES
cipher = AES.new(open('flag.txt', 'rb').read(), AES.MODE_ECB)
pt = b'\x00' * 16
print(cipher.encrypt(pt).hex())
"""
5aed095b21675ec4ceb770994289f72b
"""
```
:::
Vì mã hóa **AES** luôn yêu cầu độ dài khóa phải là $16$, $24$ hoặc $32$ và định dạng **flag** của cuộc thi là `amateursCTF{...}` vốn có số ký tự đã biết là $13$, vì vậy ta chỉ cần tiến hành brute-force $3$, $11$ hoặc $19$ ký tự bên trong định dạng **flag** để tìm ra **flag** hoàn chỉnh.
Dưới đây là toàn bộ lời giải cho thử thách này:
:::spoiler <b style="color:#164d36">solution.py</b>
```python=
from Crypto.Cipher import AES
import itertools
from string import printable
from tqdm import tqdm
plaintext = b'\x00' * 16
ciphertext = bytes.fromhex("5aed095b21675ec4ceb770994289f72b")
prefix_flag = "amateursCTF{"
suffix_flag = '}'
# Độ dài của key chỉ có thể là 16, 24 hoặc 32
content_length = 3
for content_tuple in tqdm(itertools.product(printable, repeat=content_length), desc="Finding flag...", total=len(printable)**3):
generated_key = prefix_flag + ''.join(content_tuple) + suffix_flag
cipher = AES.new(generated_key.encode(), AES.MODE_ECB)
encrypted_data = cipher.encrypt(plaintext)
if encrypted_data == ciphertext:
flag = generated_key
break
print("[!] Got flag:", flag)
# [!] Got flag: amateursCTF{@3s}
```
:::
:::success
**Flag: amateursCTF{@3s}**
:::
## uncrackable
:::spoiler <b>chall.py</b>
```python=
import os
import hashlib
flag = open("flag.txt", "rb").read()
assert len(flag) == 47 # just an fyi
class stream():
def __init__(self, seed = os.urandom(8)):
self.state = hashlib.sha256(str(seed).encode()).digest()[:len(flag)]
def next(self):
out = self.state[0]
self.state = self.state[1:] + bytes([(out + 1) % 256])
return out
def get_bytes(self, num):
return bytes(self.next()for _ in range(num))
def xor(a, b):
assert len(a) == len(b)
return bytes(i^j for i,j in zip(a,b))
def encrypt(x):
return xor(x := x.strip(), rng.get_bytes(len(x)))
rng = stream()
open("out.txt", "w").write(b''.join(encrypt(os.urandom(2))for _ in range(10000)).hex() + encrypt(flag).hex())
```
:::
:::spoiler <b>out.txt</b> (dài quá nên mình chỉ viết một phần ở đây để minh họa thôi)
```text!
abc60262b142a717921dfcb11445d5640e083257b8b59bf98d300a90d3e649b0e45718dec194709bedd0ded942e34c0c61b1e677ea8232e4b1fe88ea371c19528a077f9f7cb3a7d23193c6b573ec60f669453a414485dff7870e3f4826ab607ef8ed1e80f45d32d42c6fd3958bed8ce71179cd6bcec707910548a68d1939a18f99aef249049fd5731e55264c9bf65a97f98cfc3f0017eb61b67bdebee430b7fb1249589def9039502e879e0495a8a139e468af65b6e045d08ce9309d1ff977b6462869da21e362ea67904ac5b892aad2988558eb7853ff0ab65d2a4a4375c2c1037d8f8be79dd4706424270998a4b661bfdf16f3d70814083b75fd0c5a585f7303a7845123b92be4465fff6b60b91cedc69a9644380d93c444ee64729e3ae06662990b899a5c9d6546b14cd7e636734062b7221c4545120c6d65001924af5c3b7f096f1791d03c1aa6f0711ee7657cf72827f7ad928aa9d1c6b934de3baf6f610c852fe7676b4e74b050e068d986f86706202b3c82541c28ec31b9160962e0091fa01b96beb2371181cc792b752441df5d996cafe69c0172be3016825033b6c2c5ab0dceb399f4e94109757d50418db847af610fbd035f7cd72eb7f003cbb30e4d830e5f8c78394774348270c67a6dc50b4e68570339064b41869c53a443fc638cbcc9eb25bdb6d44ecd6ea9f241161bfed1ae78bb711f4570e727a3334207c42c2d41ca16e52e87b3554ad1e42c55005d02ab3754ca63125640e7629fd5b6f434e5a7a1204157aa255ab7e29e5c528d485c8987b771b95c5c61985b182d4499ed4c0c27e3812dc4667538f6883d995a73a88efd7eb09d4a15f62ee5b1ed78570d769e163d3e8bd16bf5a78b2d6cd2c2454b050ae2dff85a96ae2ff6a8bdad9dc3a55769e724501e01e6ec04bf0fd5ee9f7596f2d8d6490ae6c1148b2529f5070737048da7bf500f8414eb99df448941e975d869b124ec75e9e99b8eb7d1144be33f67dcf3be7bd6a9bd6717525e6de22c142ec1d75abfac1b08b6287e75d4debf81b10343bf130d3ab26e08ef85794c7f57cb1d36a47f2f5ebe06f7e1f51982d7739477a0b48baca8a6846cbd4b615a88afb7820549040142ffa948202cac35fdebfa9070bfcbfe2a05ea25089f6a89acfbe2ff455391e10e652ed8c50e17dc114e005325fa33ba21ee6cd9da84e519a957ecebc9de46ee9a262...
```
:::
Bài này hoạt động giống như một **LFSR** phiên bản lỗi khi mà byte được thêm vào chính là byte được lấy ra và cộng thêm $1$ theo modulo $256$. Chương trình sẽ lấy các byte ngẫu nhiên và thực hiện phép **XOR** với dãy byte đầu ra của **LFSR**, và nhiệm vụ của chúng ta là phải khôi phục lại được **flag** từ cái mã hóa kỳ lạ này:
Hãy chú ý đoạn mã trong `class stream()` như sau:
```text
def __init__(self, seed = os.urandom(8)):
self.state = hashlib.sha256(str(seed).encode()).digest()[:len(flag)]
```
Nếu không phân tích kỹ thì sẽ lầm tưởng rằng trạng thái sẽ là một danh sách gồm $47$ byte, nhưng thực chất trạng thái chỉ là một danh sách gồm $32$ byte vì hàm băm **SHA-256** có đầu ra luôn là $32$ byte.
Tiếp theo ta nhìn vào đoạn mã của hàm `encrypt` như sau:
```
def encrypt(x):
return xor(x := x.strip(), rng.get_bytes(len(x)))
```
Ta thấy rằng đầu vào bị loại bỏ **khoảng trắng (whitespace)** trước khi tiến hành phép **XOR** với dãy byte đầu ra của **LFSR**. Điều này có nghĩa là dãy đầu ra của **LFSR** không bao giờ phải thực hiện phép **XOR** với bất kỳ khoảng trắng nào cả.
Cuối cùng ta được biết là độ dài **flag** sẽ là $47$, vậy là đủ thông tin để tiến hành giải quyết bài toán này.
Ta sẽ tiến hành brute-force từng byte của đầu ra **LFSR** mà được thực hiện phép **XOR** với **flag**, với byte thứ $j$ mà ta đang brute-force, ta sẽ tiến hành tính **XOR** của đầu ra thứ $j - 32i$ với $\text{byte} - 32 \bmod{256}$ và kiểm tra xem kết quả có phải là khoảng trắng không. Nếu tồn tại một kết quả là khoảng trắng thì ta sẽ loại byte này và chuyển qua byte tiếp theo, nếu không có kết quả không phải là khoảng trắng thì ta kiểm tra tiếp bằng cách cho byte đó thực hiện phép **XOR** với byte ở dãy văn bản mã tương ứng. Nếu kết quả là ký tự nằm trong `string.printable` thì ta đã thu được $1$ byte của **flag**.
Dưới đây là toàn bộ lời giải cho thử thách này:
:::spoiler <b style="color:#164d36">solution.py</b>
```python=
from string import printable, whitespace
from tqdm import trange
with open("out.txt", "r") as file:
data_stream = bytes.fromhex(file.read())
length = len(data_stream)
whitespace_list = list(whitespace.encode())
flag = ""
for i in trange(47):
for byte in range(256):
is_satisfy = True
shift = 0
for j in range(length - i - 1, -1, -32):
current_byte = (byte - shift) % 256
if((data_stream[j] ^ current_byte) in whitespace_list):
is_satisfy = False
break
shift += 1
if is_satisfy == False: continue
flag_char = chr(byte ^ data_stream[-i - 1])
if(flag_char not in printable): continue
flag = flag_char + flag
break
flag = "amateursCTF{" + flag + '}'
print("[!] Got flag:", flag)
# [!] Got flag: amateursCTF{the_r4nd0m_data_isnT_s0_R4nd0m_hUh_8d7ac2d8e8d3}
```
:::
:::success
**Flag: amateursCTF{the_r4nd0m_data_isnT_s0_R4nd0m_hUh_8d7ac2d8e8d3}**
:::
## division
:::spoiler <b>chall.sage</b>
```python=
import random
flag = int.from_bytes(open('flag.txt', 'rb').read(), 'big')
x = flag.bit_length()
r = random.getrandbits(x*3)
s = random.getrandbits(x*3) >> x*2 << x*2
p = random_prime(2^(x*3)-1, False, 2^(x*3-1))
c = (r*flag+s)%p
print(f"{c = }")
print(f"{r = }") # just divide to get the flag
print(f"{p = }") # ok fine maybe you need the modulus as well
"""
c = 75375527234510651665677207066229891926040929328980582924525303994966835168796055022727363375804269692143070561263128516881074866977604549208239672350292604269324775848328528401041649243536698878068388663854658455888665567421528139676553398379791728850136444114360571254958597748469715514303229969364378553163423222522897412606507907342566717324675248648278152290809106176295241303943659155279739413927229119348178739649701446536277787785586385384290648596225479179951687047854987093302449400449408907035601103612171991422127378147919500898428845497702002243505620992542869790261271932282435731195032724808409252081154632950628964417018040860488194082532635686263681213906375790385569586239071410623996119802591938958940165788806391189899599255362316672332888493379847547083365240770226903398674774357924053797951490900058983308593594684075033516959188148000904700191560112121648591490057629599361214369099947477414730697724448515856824615139071844639957575363257387078768257241797937595586141467195592425033618924139126557481
r = 48648359606087607054764975061246586804946899771075465950463841480503792391242075718361379574064958310831886132797205905782225730921050328582127691139051377153885590959058584931544239373521818766047205266802911821810151109225243130179140623399478388305644784028218706385078397300157808478028917780169261334807047724247279925670091509482240375019889452543079342438321747327926834796379012339921188615926117511143813280492641218017371403897472661550045565397359426254471576804581357221127582353441561380497515665661934473669613838790969595463036823630557187360129867186459025552953339813671569683189170774295708055929734217591905795428441403136096735625270568765197391423757594103320945558276124412602379303298694436105059220213537852584622876964933389323070365214287371704961312345353833390325002117393017327937680001690416415146226901969211615033627210161600009415469801626322733646436539056402194785639655852044899338363041427982892348396424818762289291934998870311926616547712216114710383692009811315188831592384925859038824
p = 86177866064517609033880568807115953555242816860796465315994122793500658219204691266285400596992843986822859067988140541321102737268469256003488633194805732902328449668973675656034407479445206199285327332956250166678724833829086476894512753542599582930303813548509716626122990897384869145771777456521841989016732565902948058499497558560940675936638149144787557866682549895410172503475134761737103764159012832476099457080767621349093023525464199464437775892158425340808608831357847290625769994444619608418683397291585743320119410163556022541745013298562365924431890839096568358382609153300688137255847854540583022798338370905413030872305343628451395156651510799422269846199097346654778450970192181652155045761310415676411676415321314004703082183268372839586588063507099961869739615845147256459914569897668249853629651515566126984158856990492614415609777375564680454921886476795802100545467623117528820164062239760078312599781978838070617837964620704025708935814492400262083101517057997114593888320133983970592497555237407111597
"""
```
:::
Đề bài cũng chỉ là vài phép toán đơn giản nên mình sẽ không giải thích đề bài ở đây.
Theo đề bài, ta được cho biết giá trị của `s = s'*2**(2x)`, `p` và `c` và có thể dễ dàng tìm được `x`. Cũng từ đề bài ta có phương trình sau:
$$
\begin{align*}
&c = r\cdot \text{flag} + s \bmod{p} \\
&\Rightarrow r\cdot \text{flag} + s'\cdot 2^{2x} - c \equiv 0 \pmod{p} \\
&\Leftrightarrow r\cdot \text{flag} + s'\cdot 2^{2x} - c + k\cdot p = 0, k \in \mathbb{Z}
\end{align*}
$$
Đến đây với $\text{flag}$ có độ lớn $x$ bit, $s'$ có độ lớn $x$ bit, ta tiến hành lập ma trận cơ sở như sau:
$$\textbf{B} =
\begin{bmatrix}
1 & 0 & 0 & r\cdot w \\
0 & 1 & 0 & 2^{2x}\cdot w \\
0 & 0 & w_1 & -c\cdot w \\
0 & 0 & 0 & -p\cdot w
\end{bmatrix}
$$
, trong đó $w_1 = 2^x$ và $w$ là một số nguyên càng lớn càng tốt, nhưng chú ý tốc độ tính toán của máy tính.
Sau khi thực hiện tấn công giảm cơ sở mạng, ta sẽ khôi phục lại được **flag** 🥳.
Dưới đây là toàn bộ lời giải cho thử thách này:
:::spoiler <b style="color:#164d36">solution.py</b>
```python=
from sage.all import Matrix, ZZ, diagonal_matrix
from Crypto.Util.number import long_to_bytes
c = 75375527234510651665677207066229891926040929328980582924525303994966835168796055022727363375804269692143070561263128516881074866977604549208239672350292604269324775848328528401041649243536698878068388663854658455888665567421528139676553398379791728850136444114360571254958597748469715514303229969364378553163423222522897412606507907342566717324675248648278152290809106176295241303943659155279739413927229119348178739649701446536277787785586385384290648596225479179951687047854987093302449400449408907035601103612171991422127378147919500898428845497702002243505620992542869790261271932282435731195032724808409252081154632950628964417018040860488194082532635686263681213906375790385569586239071410623996119802591938958940165788806391189899599255362316672332888493379847547083365240770226903398674774357924053797951490900058983308593594684075033516959188148000904700191560112121648591490057629599361214369099947477414730697724448515856824615139071844639957575363257387078768257241797937595586141467195592425033618924139126557481
r = 48648359606087607054764975061246586804946899771075465950463841480503792391242075718361379574064958310831886132797205905782225730921050328582127691139051377153885590959058584931544239373521818766047205266802911821810151109225243130179140623399478388305644784028218706385078397300157808478028917780169261334807047724247279925670091509482240375019889452543079342438321747327926834796379012339921188615926117511143813280492641218017371403897472661550045565397359426254471576804581357221127582353441561380497515665661934473669613838790969595463036823630557187360129867186459025552953339813671569683189170774295708055929734217591905795428441403136096735625270568765197391423757594103320945558276124412602379303298694436105059220213537852584622876964933389323070365214287371704961312345353833390325002117393017327937680001690416415146226901969211615033627210161600009415469801626322733646436539056402194785639655852044899338363041427982892348396424818762289291934998870311926616547712216114710383692009811315188831592384925859038824
p = 86177866064517609033880568807115953555242816860796465315994122793500658219204691266285400596992843986822859067988140541321102737268469256003488633194805732902328449668973675656034407479445206199285327332956250166678724833829086476894512753542599582930303813548509716626122990897384869145771777456521841989016732565902948058499497558560940675936638149144787557866682549895410172503475134761737103764159012832476099457080767621349093023525464199464437775892158425340808608831357847290625769994444619608418683397291585743320119410163556022541745013298562365924431890839096568358382609153300688137255847854540583022798338370905413030872305343628451395156651510799422269846199097346654778450970192181652155045761310415676411676415321314004703082183268372839586588063507099961869739615845147256459914569897668249853629651515566126984158856990492614415609777375564680454921886476795802100545467623117528820164062239760078312599781978838070617837964620704025708935814492400262083101517057997114593888320133983970592497555237407111597
x = p.bit_length()//3
weight = diagonal_matrix(ZZ, [1, 1, 2**x, 2**1000])
basis = Matrix(ZZ, [[1, 0, 0, r],
[0, 1, 0, 2**(2*x)],
[0, 0, 1, -c],
[0, 0, 0, -p]])
weighted_basis = basis * weight
reduced_basis = weighted_basis.LLL()
reduced_basis *= weight.inverse()
# for row in reduced_basis:
# print(row)
for row in reduced_basis:
if(row[-2] == 1):
flag_int = int(abs(row[0]))
break
flag = long_to_bytes(flag_int).decode()
print("[!] Got flag:", flag)
# [!] Got flag: amateursCTF{the_flag_format_is_kinda_long_but_if_i_just_type_enough_text_here_it_doesnt_matter_righttttttttttttttttttttttttttt_yeahh_probably}
```
:::
:::success
**Flag: amateursCTF{the_flag_format_is_kinda_long_but_if_i_just_type_enough_text_here_it_doesnt_matter_righttttttttttttttttttttttttttt_yeahh_probably}**
:::
## triangulate
:::spoiler <b>chall.py</b>
```python=
#!/usr/local/bin/python3
from random import getrandbits
from Crypto.Util.number import *
flag = bytes_to_long(open('flag.txt', 'rb').read())
k = flag.bit_length()
m = getPrime(flag.bit_length() + 1)
def lcg():
seed = flag
a = getrandbits(k)
c = getrandbits(k)
ctr = 0
while True:
ctr += 1
for _ in range(ctr):
seed = (a * seed + c) % m
yield seed
rng = iter(lcg())
for _ in range(6):
print(next(rng))
"""
1471207943545852478106618608447716459893047706734102352763789322304413594294954078951854930241394509747415
1598692736073482992170952603470306867921209728727115430390864029776876148087638761351349854291345381739153
7263027854980708582516705896838975362413360736887495919458129587084263748979742208194554859835570092536173
1421793811298953348672614691847135074360107904034360298926919347912881575026291936258693160494676689549954
7461500488401740536173753018264993398650307817555091262529778478859878439497126612121005384358955488744365
7993378969370214846258034508475124464164228761748258400865971489460388035990421363365750583336003815658573
"""
```
:::
Bài này là một bài **LCG** kỳ lạ vì thay vì cung cấp cho ta các trạng thái liên tiếp thì họ lại cho chúng ta các trạng thái theo một quy luật rất kỳ lạ. Cụ thể với $\text{flag} = S_0$ là trạng thái ban đầu của **LCG** và $S_i$ là trạng thái thứ $i$ thì ta chúng ta sẽ được cho biết các các trạng thái $S_1$, $S_3$, $S_6$, $S_{10}$, $S_{15}$, $S_{21}$.
Nếu gọi $x_i$ là đầu ra thứ $i$ trong file thử thách thì ta sẽ có $x_i = S_{\frac{i(i+1)}{2}}, ~ i = \overline{1, 6}$.
Để làm được bài này, trước tiên chúng ta cần phải biết được một khái niệm toán học, đó chính là [kết thức (resultant)](https://en.wikipedia.org/wiki/Resultant). Về phần khái niệm và các tính chất cơ bản của nó, vì mình quá lười để viết lại nên các bạn hãy tìm đọc ở các giáo trình đại số hiện đại và đại số tuyến tính để hiểu hơn về nó.
:::info
###### Liên quan đến kết thức
Kết thức (resultant) có một tính chất rất hữu dụng như sau:
Cho $f(x)$ và $g(x)$ là các đa thức thuộc $K[x]$ với $K$ là một trường (Một số sách yêu cầu có đặc số là 0 để mong muốn trường ta xét là trường vô hạn, nhưng mình không biết trường hữu hạn với đặc số $p$ có còn thỏa mãn không nữa), các đa thức $f(x)$ và $g(x)$ có nghiệm chung trong $\overline{K}$ (ký hiệu [trường đóng đại số](https://en.wikipedia.org/wiki/Algebraic_closure)) khi và chỉ khi $\text{res}(f, g) = 0$.
Ngoài ra, $K$ không nhất thiết phải là một trường mà cấu trúc tối thiểu của nó chỉ cần là một **vành giao hoán** thì $\text{res}(f, g)$ vẫn được xác định.
Tuy nhiên tính chất vừa nói ở trên không còn đúng khi $K$ không phải là trường nên hãy chú ý khi sử dụng kết thức.
:::
Quay trở lại bài toán, hệ thống sinh số **LCG** hoạt động như sau:
$$
S_{n+1} \equiv a\cdot S_n + c \pmod{m}, \forall n = 0, 1, 2,\ldots
$$
Công thức này rất khó biến đổi và xử lý các state không liên quan tục vì có phép cộng $c$, vì vậy để khử $c$, ta sẽ sử dụng một biến đổi toán học rất hay dùng, đó là đặt biến phụ $u$ sao cho:
$$
\begin{align*}
S_{n+1} + u &\equiv a(S_n + u) \pmod{m}&&, \forall n \in \mathbb{N} \\
\Leftrightarrow aS_n + c + u &\equiv aS_n + au \pmod{m}&&, \forall n \in \mathbb{N} \\
\Leftrightarrow u &\equiv \frac{c}{a - 1} \pmod{m}&&, \forall n \in \mathbb{N}
\end{align*}
$$
Vậy là ta đã thành công biến đổi từ dạng tuyến tính khó chịu về dạng cấp số nhân đẹp hơn rồi.
Đến đây, ta áp dụng công thức với các đầu ra của thử thách:
$$
x_i + u \equiv S_{\frac{i(i+1)}{2}} + u \equiv a^{\frac{i(i+1)}{2}}(S_0 + u) \pmod{m}, \forall i = \overline{1, 6} \hspace{15pt} (1)
$$
Bây giờ, chúng ta cần phải tìm ra mỗi liên hệ giữa các $x_i + u$ liên tiếp để tạo thành một đa thức ẩn $u$. Dễ thấy với $2$ đầu ra $x_i$ và $x_{i+1}$ liên tiếp, ta không thể tìm được mối liên hệ nào cả. Còn với $3$ đầu ra $x_i$, $x_{i+1}$ và $x_{i+2}$ ta xét phương trình ẩn $k_1(i)$, $k_2(i)$ và $k_3(i)$ như sau:
$$
\begin{align*}
(x_i + u)^{k_1(i)}(x_{i+1} + u)^{k_2(i)}(x_{i+2} + u)^{k_3(i)} &\equiv 1 \pmod{m} \hspace{15pt} (2) \\
\Leftrightarrow a^{k_1(i)\frac{i(i+1)}{2} + k_2(i)\frac{(i+1)(i+2)}{2} + k_3(i)\frac{(i+2)(i+3)}{2}}(S_0 + u)^{k_1(i) + k_2(i) + k_3(i)} &\equiv 1 \pmod{m} \hspace{15pt} (3)
\end{align*}
$$
, đến đây bạn chắc đã hiểu mục đích mà chúng ta nên đưa về dạng giống cấp số nhân rồi, đó là để việc thao tác giữa các đầu ra trở nên dễ dàng hơn.
>[!Note]
>Sở dĩ có phương trình $(2)$ là vì ta muốn tận dụng tối đa tính chất "cấp số nhân" của công thức **LCG** với ẩn $u$.
Quay trở lại bài này, đồng nhất hệ số hai vế của phương trình $(3)$, ta được:
$$
\begin{cases}
k_1(i)[i(i+1)] + k_2(i)[(i+1)(i+2)] + k_3(i)[(i+2)(i+3)] = 0 \\[5pt]
k_1(i) + k_2(i) + k_3(i) = 0
\end{cases}
$$
Hệ phương trình có số ẩn nhiều hơn số phương trình và bằng các xét hạng của các ma trận kết hợp với [định lý Kronecker-Capelli](https://en.wikipedia.org/wiki/Rouch%C3%A9%E2%80%93Capelli_theorem), ta có thể kết luận rằng phương trình có vô số nghiệm.
>[!Note]
> Theo bản chất toán học, vế phải của phương trình thứ nhất trong hệ phương trình có thể có dạng $k\cdot \text{ord}_m(a)$ với $k \in \mathbb{Z}$, tương tự với phương trình thứ hai của hệ.
> Nhưng vì đây là lĩnh vực mật mã học, và ta cũng không biết được giá trị của $m$ nên ta sẽ chọn vế phải bằng $0$ để có thể tính toán.
Bây giờ, ta sẽ tiến hành tìm cơ sở của không gian nghiệm của hệ phương trình trên. Bởi vì **SageMath** đã có các hàm và lớp hỗ trợ chúng ta những công việc tính toán nặng nhọc nên chúng ta không cần phải tính bằng tay.
Dưới đây là script (có nhờ AI hỗ trợ) để tìm cơ sở của không gian nghiệm:
```python=
from sage.all import PolynomialRing, QQ, Matrix
# 1. Define the ring
R = PolynomialRing(QQ, name='x'); x = R.gen()
# 2. Input polynomials a, b, c (Example)
a = x**2 + x
b = x**2 + 3*x + 2
c = x**2 + 5*x + 6
# 3. Construct Matrix for the system of equations
# Equation 1: f*a + g*b + h*c = 0 => Row 1: [a, b, c]
# Equation 2: f + g + h = 0 => Row 2: [1, 1, 1]
M = Matrix(R, [
[a, b, c],
[1, 1, 1]
])
# 4. Find Kernel (Null Space)
# Kernel contains all tuples (f, g, h) such that M * vector(f,g,h) = 0
kernel = M.right_kernel()
# 5. Output results
print(f"Dimension of the solution space: {kernel.dimension()}")
if kernel.dimension() == 0:
print("Only trivial solution f = g = h = 0 exists")
else:
print("Basis solution sets (f, g, h):")
for vec in kernel.basis():
f_sol, g_sol, h_sol = vec
print("-" * 20)
print(f"f(x) = {f_sol}")
print(f"g(x) = {g_sol}")
print(f"h(x) = {h_sol}")
# Verify
# We check if the linear combination actually equals 0
eq1 = f_sol*a + g_sol*b + h_sol*c
eq2 = f_sol + g_sol + h_sol
print(f"Check EQ1 (f*a + g*b + h*c = 0): {eq1 == 0}")
print(f"Check EQ2 (f + g + h = 0): {eq2 == 0}")
```
Sau khi chạy chương trình, ta đã tìm được nghiệm tổng quát của hệ phương trình trên là $(k_1(i), k_2(i), k_3(i)) = (i+2, -2i-3, i+1)$. Lúc này, ta thế nghiệm trở lại vào phương trình $(2)$, ta được:
$$
\begin{align*}
(x_i + u)^{i+2}(x_{i+1} + u)^{-2i-3}(x_{i+2} + u)^{i+1} &\equiv 1 \pmod{m} \\
\Leftrightarrow (x_{i+1} + u)^{2i+3} - (x_i + u)^{i+2}(x_{i+2} + u)^{i+1} &\equiv 0 \pmod{m}
\end{align*}
$$
Vậy là sau một loạt các phép biến đổi, chúng ta đã đưa được về dạng một phương trình ẩn $u$ 🎉.
Bây giờ, ta sẽ tiếp tục bằng cách đặt $P_i(u) = (x_{i+1} + u)^{2i+3} - (x_i + u)^{i+2}(x_{i+2} + u)^{i+1}, \forall i = \overline{1, 4}$ với $P_i(u) \in \mathbb{F}_m[u]$ (khả năng rất cao người ra đề cho $m$ là số nguyên tố thay vì là lũy thừa của một số nguyên tố), kết quả là ta đã có $4$ đa thức ẩn $u$. Tiếp theo, ta sẽ tính $\text{res}(P_0(u), P_j(u)), j = \overline{1, 4}$, vì ta đang tính trong miền nguyên $\mathbb{Z}$, nên các giá trị kết thức sẽ là một số nguyên rất lớn. Tuy nhiên, ta có $P_i(u)$ có nghiệm trong $\mathbb{F}_m$ với mọi $i = \overline{1, 4}$ nên $\text{res}(P_0(u), P_j(u)) \equiv 0 \pmod{m}, \forall j = \overline{1, 4}$. Như vậy ta có thể khôi phục $m$ bằng cách tìm ước chung lớn nhất giữa các kết thức.
Lúc này vì đã khôi phục được $m$, ta sẽ tiến hành chuyển các đa thức $P_i(u)$ sang miền nguyên $\mathbb{F}_m[x]$. Vì $P_i(u) \equiv 0 \pmod{m}, \forall i = \overline{1, 4}$ nên ta có thể tìm lại được $u$ bằng cách tìm ước chung lớn nhất của các đa thức này. Khi đó ta sẽ thu được kết quả là đa thức $Au + B$, giải phương trình trên trường $\mathbb{F}_m$, ta sẽ khôi phục lại được $u$.
Từ phương trình $(1)$ ta có điều sau:
$$
\frac{x_{i+1} + u}{x_i + u} \equiv \frac{a^{\frac{(i+1)(i+2)}{2}}(S_0 + u)}{a^{\frac{i(i+1)}{2}}(S_0 + u)} \equiv a^{i + 1} \pmod{m}, \forall i = \overline{1, 5}
$$
Từ đó ta suy ra:
$$
\frac{(x_{i+2} + u)(x_i + u)}{(x_{i+1} + u)^2} \equiv \frac{a^{i+2}}{a^{i+1}} \equiv a \pmod{m}, \forall i = \overline{1, 4}
$$
Từ công thức này ta đã khôi phục được $a$, giờ chỉ lại $c$ và ta có thể khôi phục nó dễ dàng bằng cách tính:
$$
c = u(a - 1) \bmod{m}
$$
Sau khi khôi phục đầy đủ các tham số của **LCG**, ta có thể khôi phục được trạng thái ban đầu chính là **flag**.
Dưới đây là toàn bộ lời giải cho thử thách này:
:::spoiler <b style="color:#164d36">solution.py</b>
```python=
from sympy import symbols, Poly, gcd
from Crypto.Util.number import isPrime, inverse, long_to_bytes
x_list = [int(x) for x in """
1471207943545852478106618608447716459893047706734102352763789322304413594294954078951854930241394509747415
1598692736073482992170952603470306867921209728727115430390864029776876148087638761351349854291345381739153
7263027854980708582516705896838975362413360736887495919458129587084263748979742208194554859835570092536173
1421793811298953348672614691847135074360107904034360298926919347912881575026291936258693160494676689549954
7461500488401740536173753018264993398650307817555091262529778478859878439497126612121005384358955488744365
7993378969370214846258034508475124464164228761748258400865971489460388035990421363365750583336003815658573
""".split()]
print("[*] Building polynomials...")
u = symbols('u')
polynomial_list = []
for i in range(1, 5):
polynomial_list.append( (x_list[i] + u)**(2*i + 3) - (x_list[i-1] + u)**(i + 2)*(x_list[i+1] + u)**(i+1) )
P1, P2, P3, P4 = polynomial_list
poly1 = Poly(P1, u)
poly2 = Poly(P2, u)
poly3 = Poly(P3, u)
poly4 = Poly(P4, u)
print("[*] Calculating Resultants and finding GCD to recover m...")
m_sympy = gcd(poly1.resultant(poly2), poly1.resultant(poly3), poly1.resultant(poly4))
m = int(m_sympy)
print(f"[+] Raw GCD (bit length): {m.bit_length()}")
print("[*] Finding small factors to filter out...")
for factor in [2, 3, 5, 7]:
while m % factor == 0:
m //= factor
if isPrime(m):
print(f"[+] Found m (Prime): {m}")
else:
print(f"[!] WARNING: m is not prime (isPrime=False).")
print(f" Value of m: {m}")
# Still try to proceed in case isPrime check is wrong or m is a special composite (though the problem states getPrime)
print("[*] Finding u in the field F_m...")
# Convert polynomials to F_m using set_modulus (accepts standard int)
P1_mod = poly1.set_modulus(m)
P2_mod = poly2.set_modulus(m)
# Calculate GCD of polynomials over F_m
# This GCD will be linear: a*u + b
G = gcd(P1_mod, P2_mod)
if G.degree() < 1:
print("[-] Could not find u (GCD polynomial is constant).")
exit(1)
# Get coefficients to solve the linear equation: A * u + B = 0
coefficients = G.all_coeffs() # [A, B]
A = int(coefficients[0])
B = int(coefficients[1])
# u = -b * a^-1 mod m
u_val = (-B * inverse(A, m)) % m
print(f"[+] Found u: {u_val}")
# Recover a
# a^2 = (x2+u)/(x1+u)
# a^3 = (x3+u)/(x2+u)
# a = a^3 * (a^2)^-1
a2 = ((x_list[1] + u_val) * inverse(x_list[0] + u_val, m)) % m
a3 = ((x_list[2] + u_val) * inverse(x_list[1] + u_val, m)) % m
a = (a3 * inverse(a2, m)) % m
print(f"[+] Found a: {a}")
# Recover c
# u = c(a-1)^-1 => c = u(a-1)
c = (u_val * (a - 1)) % m
print(f"[+] Found c: {c}")
# Recover Flag
# x1 = (a * flag + c) mod m => flag = (x1 - c) * a^-1
flag_int = ((x_list[0] - c) * inverse(a, m)) % m
try:
flag = long_to_bytes(flag_int)
print(f"\n[!] Got flag: {flag.decode()}")
except Exception as e:
print(f"\nFlag (int): {flag_int}")
print(f"Decode error: {e}")
# [!] Got flag: amateursCTF{w0w_such_cr3ativ3_lcG_ch4ll3ngE}
```
:::
:::success
**Flag: amateursCTF{w0w_such_cr3ativ3_lcG_ch4ll3ngE}**
:::
>[!Note] Về đoạn code lời giải
>Đoạn code này thực chất bắt nguồn từ AI, nhưng mà mình thấy các viết các lệnh có vẻ đẹp nên mình chôm luôn vào lời giải và kết hợp với code gốc của mình.
## addition
:::spoiler <b>chall.py</b>
```python=
#!/usr/local/bin/python
from Crypto.Util.number import *
from random import getrandbits, choice
import hashlib
flag = open('flag.txt','rb').read().strip()
assert len(flag) == 72
flag = bytes_to_long(flag) << 256
n = getPrime(1024) * getPrime(1024)
e = 3
cs = [flag + getrandbits(256) for _ in range(100000)]
print(f'{n, e = }')
while True:
scramble = int(input('scramble the flag: '))
ms = [(m + scramble)%n for m in cs]
print('scrambling...')
c = choice([pow(m, e, n) for m in ms])
print(f'{c = }')
```
:::
Bài này là một bài **RSA** với `m = flag + r + scramble`, trong đó `r = getrandbits(256)` và `scramble` là giá trị tùy ý được ta nhập vào và gửi cho server. Nhìn có vẻ phức tạp nhưng thực chất bài này là một bài liên quan đến xác suất và tấn công [Franklin-Reiter Related Message](https://crypto.stackexchange.com/questions/30884/help-understanding-basic-franklin-reiter-related-message-attack).
Đầu tiên, ta sẽ thu thập nhiều mẫu (khoảng 400 để vừa khít với thời gian cho phép của server và tăng cơ hội ra **flag** lên cao nhất có thể) văn bản mã với `scramble = 0` và lưu vào một `set`, tương tự với `scramble = 1`. Sau đó, ta sẽ lặp qua các phần tử của $2$ `set` và hy vọng ta sẽ tìm được một cặp văn bản mã $c_1$ và $c_2$ sao cho chúng tạo bởi $2$ `scramble` khác nhau là $0$ và $1$ đồng thời giá trị `r` của chúng là như nhau.
Lúc này với quy ước `m = flag + r`, ta có:
$$
\begin{cases}
c_1 \equiv m^e \pmod{n} \\
c_2 \equiv (m + 1)^e \pmod{n} \\
\end{cases}
$$
Vì $e = 3$ nên ta có một biểu thức gọn gàng như sau:
$$
\begin{align*}
&\begin{cases}
c_1 \equiv m^3 \pmod{n} \\
c_2 \equiv (m + 1)^3 \pmod{n} \\
\end{cases} \\
\Rightarrow &m \equiv \frac{c_2 + 2c_1 - 1}{c_2 - c_1 + 2} \pmod{n}
\end{align*}
$$
Sau khi có được $m$, ta sẽ kiểm tra nó có phải chính là văn bản rõ mà server đã tạo hay không bằng cách kiểm tra $m^3 \bmod{n}$ có bằng với $c_1$ hay không.
Nếu duyệt hết mẫu mà vẫn không có $m$ nào thỏa mãn, ta chỉ cần chạy lại chương trình với một cổng khác là được.
Sau khi đã có $m$, ta dễ dàng tính được **flag** bằng cách tính `flag = m >> 256`.
Dưới đây là toàn bộ lời giải cho thử thách này:
:::spoiler <b style="color:#164d36">solution.py</b>
```python=
from pwn import remote
from tqdm import trange
from Crypto.Util.number import inverse, long_to_bytes
zero_adding = set()
one_adding = set()
SAMPLE_COUNT = 400
HOST = "amt.rs"; PORT = 35339
connection = remote(HOST, PORT, timeout = None)
n, e = eval(connection.recvline().strip().decode()[6:])
for i in trange(SAMPLE_COUNT):
connection.sendlineafter(b"scramble the flag: ", b"0")
connection.recvline()
zero_adding.add(int(connection.recvline().decode()[3:]))
connection.sendlineafter(b"scramble the flag: ", b"1")
connection.recvuntil(b"c = ")
one_adding.add(int(connection.recvline().decode()))
for c0 in zero_adding:
for c1 in one_adding:
numerator = (c1 + 2 * c0 - 1) % n
denominator = (c1 - c0 + 2) % n
m = (numerator * inverse(denominator, n)) % n
if pow(m, 3, n) == c0:
int_flag = m >> 256
flag = long_to_bytes(int_flag).decode()
connection.success(f"Got flag: {flag}")
connection.close()
exit(0)
# [+] Got flag: amateursCTF{1_h0p3_you_didnT_qU3ry_Th3_s3RVer_100k_tim3s_1b9490c255fe83}
```
:::
:::success
**Flag: amateursCTF{1_h0p3_you_didnT_qU3ry_Th3_s3RVer_100k_tim3s_1b9490c255fe83}**
:::
## addition 2
:::spoiler <b>chall.py</b>
```python=
#!/usr/local/bin/python
from Crypto.Util.number import *
from random import getrandbits, choice
import hashlib
flag = open('flag.txt','rb').read().strip()
assert len(flag) == 72
flag = bytes_to_long(flag) << 256
n = getPrime(1024) * getPrime(1024)
e = 3
print(f'{n, e = }')
while True:
cs = [flag + getrandbits(256) for _ in range(100000)]
scramble = int(input('scramble the flag: '))
ms = [(m + scramble)%n for m in cs]
print('scrambling...')
c = choice([pow(m, e, n) for m in ms])
print(f'{c = }')
```
:::
Bài này chỉ khác với bài thứ nhất ở chỗ `cs = [flag + getrandbits(256) for _ in range(100000)]` được đặt trong vòng lặp while thay vì bên ngoài và điều này đã làm cho cách làm của bài thứ nhất của chúng ta hoàn toàn phá sản.
Để đơn giản hóa, ta sẽ cho `scramble = 0` trong suốt thời gian chạy chương trình và để cho ngắn gọn khi viết các công thức toán học, ta sẽ đặt $f = \text{flag}\cdot2^{256}$. Lúc này mọi văn bản rõ mà server tạo ra sẽ có dạng $m_i = f + r_i, \forall i \in \mathbb{N}^*$.
Ta sẽ quy ước $m_{\text{base}} = f + r_0$ chính là văn bản rõ đầu tiên mà server tạo ra để tính văn bản mã sau khi ta gửi yêu cầu nhận về văn bản mã từ server. Hơn nữa để có thể giải được bài này, ta đặt $\Delta_i = r_i - r_0, \forall i \in \mathbb{N}^*$, lúc này ta sẽ có $m_i = m_{\text{base}} + \Delta_i, \forall i \in \mathbb{N}^*$.
Ta có biểu thức sau:
$$
\begin{align*}
c_i - c_{\text{base}} &\equiv m_i^e - m_{\text{base}}^e \equiv (m_{\text{base}} + \Delta_i)^3 - m_{\text{base}}^3 \\
&\equiv 3m_{\text{base}}^2\Delta_i + 3m_{\text{base}}\Delta_i^2 + \Delta_i^3 \pmod{n}, \forall i \in \mathbb{N}^*
\end{align*}
$$
Ta sẽ đặt $D_i = c_i - c_{\text{base}}, \forall i \in \mathbb{N}^*$, lúc này ta có:
$$
D_i \equiv 3m_{\text{base}}^2\Delta_i + 3m_{\text{base}}\Delta_i^2 + \Delta_i^3 \pmod{n}, \forall i \in \mathbb{N}^*
$$
Vì $m_{\text{base}}$ mang giá trị $832$ bit, $\Delta_i$ mang giá trị không quá $256$ bit với mọi $i \in \mathbb{N}^*$ nên $D_i$ sẽ mang giá trị khoảng $1924$ bit, nhỏ hơn số bit của $n$ là $2024$. Do đó, ta có:
$$
D_i = 3m_{\text{base}}^2\Delta_i + 3m_{\text{base}}\Delta_i^2 + \Delta_i^3, \forall i \in \mathbb{N}^*
$$
Tương tự như trên, ta sẽ quy ước $D_{0}$ là sai khác đầu tiên mà ta tính trong lúc chạy chương trình và $\Delta_{0} = r_{\text{base}} - r_0$ là biến số tương ứng với $D_{0}$ trong công thức trên.
Tiếp theo, ta có một xấp xỉ khá tốt như sau:
$$
\frac{D_i}{D_0} \approx \frac{3m_{\text{base}}^2\Delta_i}{3m_{\text{base}}^2\Delta_0} = \frac{\Delta_i}{\Delta_0}
$$
Vì $(3m_{\text{base}}\Delta_i^2 + \Delta_i^3)$ mang giá trị $1346$ bit nên $\displaystyle \delta D_j = \frac{2^{1346}}{2^{1924}} = 2^{1346 - 1924} = 2^{-578}, \forall j \in \mathbb{N}$, do đó $\delta\frac{D_i}{D_0} = 2\cdot 2^{-578} = 2^{-577}$. Ta thấy sai số tương đối cực kỳ nhỏ, điều này chứng minh rằng xấp xỉ của công thức trên là một xấp xỉ cực kỳ tốt.
>[!Note] Nói thêm về công thức sai số
> Để hiểu thêm về lý thuyết và công thức sai số, hãy tìm trên mạng hoặc đọc [tại đây](https://hackmd.io/@0160ca14/BJfAJeQslx#Elita-Challenge-1-Elita)
Để có thể tìm được phân số $\displaystyle \frac{\Delta_i}{\Delta_0}$ với $i \in \mathbb{N}^*$, tuỳ ý, ta có thể sử dụng phương thức `.limit_denominator()` của lớp `Fraction()` trong thư viện tiêu chuẩn `fractions` của python.
>[!Note] Phương thức `.limit_denominator()`
>Nếu bạn chưa hiểu ý nghĩa và cách dùng của phương thức này, hãy đọc chúng tại [tài liệu python](https://docs.python.org/3/library/fractions.html#fractions.Fraction.limit_denominator).
Có thể ta sẽ tìm được một phân số tối giản và chưa tìm ra giá trị của $\Delta_0$ ngay, nhưng ta có thể tính nhiều cặp phân số khác nhau và sau đó lấy bội chung nhỏ nhất giữa các mẫu số là ra được $\Delta_0$.
Sau khi tìm được $\Delta_0$, ta sẽ tiến hành giải phương trình ẩn $m_{\text{base}}$ sau:
$$
3\Delta_0m_{\text{base}}^2 + 3\Delta_0^2m_{\text{base}} + (\Delta_0^3 - D_0) = 0
$$
Sau khi tìm lại được $m_{\text{base}}$, ta có thể dễ dàng khôi phục lại **flag** bằng cách tính $\text{flag} = m_{\text{base}} >> 256$.
Dưới đây là lời giải cho toàn bộ thử thách này:
:::spoiler <b style="color:#164d36">solution.py</b>
```python=
from sage.all import lcm, ZZ
from pwn import remote
from fractions import Fraction
from Crypto.Util.number import long_to_bytes
from tqdm import trange
HOST, PORT = "amt.rs", 46361
connection = remote(HOST, PORT, timeout = None)
n, e = eval(connection.recvline().strip().decode()[6:])
ciphertext_list = []
for _ in trange(5):
connection.sendlineafter(b"scramble the flag: ", b"0")
connection.recvuntil(b"c = ")
ciphertext_list.append(int(connection.recvline().strip().decode()))
connection.close()
base_cipher = ciphertext_list[0]
difference_list = []
for cipher in ciphertext_list[1:]:
difference_list.append(cipher - base_cipher)
base_difference = difference_list[0]
denominator_list = []
for difference in difference_list[1:]:
ratio = Fraction(difference, base_difference).limit_denominator(2**260)
denominator_list.append(ratio.denominator)
delta_r = lcm(denominator_list)
P = ZZ['x']; x = P.gen()
for delta in (delta_r, -delta_r):
equation = 3*delta*(x**2) + 3*(delta**2)*x + (delta**3 - base_difference)
roots = equation.roots()
if(roots):
flag_int = int(roots[0][0]) >> 256
break
flag = long_to_bytes(flag_int).decode()
connection.success(f"Got flag: {flag}")
# [+] Got flag: amateursCTF{n0_th3_fl4g_1s_n0T_th3_Same_1f_y0U_w3r3_w0ndeRing_533e72a10}
```
:::
:::success
**Flag: amateursCTF{n0_th3_fl4g_1s_n0T_th3_Same_1f_y0U_w3r3_w0ndeRing_533e72a10}**
:::
## addition 3
:::spoiler <b>chall.py</b>
```python=
#!/usr/local/bin/python
from Crypto.Util.number import *
import os
from random import getrandbits, choice
import hashlib
flag = open('flag.txt','rb').read().strip()
assert len(flag) == 52
flag = bytes_to_long(flag) << 512
while True:
n = int(os.popen('openssl genrsa 2048 | openssl rsa -noout -modulus').read()[8:], 16)
e = 3
print(f'{n, e = }')
cs = [flag + getrandbits(512) for _ in range(100000)]
scramble = int(input('scramble the flag: '))
ms = [(m + scramble)%n for m in cs]
print('scrambling...')
c = choice([pow(m, e, n) for m in ms])
print(f'{c = }')
```
:::
Bài này sẽ cho luôn cả khóa công khai vào trong vòng lặp và thay đổi độ lớn bit của một số biến chương trình, khiến cho cách giải của bài số $2$ hoàn toàn phá sản.
Ta sẽ sử dụng một loại tấn công trong tấn công bên kênh (**side-channel attack**) rất phổ biến, đó chính là [**timing attack**](https://en.wikipedia.org/wiki/Timing_attack).
Đầu tiên, ta sẽ tiến hành gửi các biến `scramble = n - guess` với `guess = (bytes_to_long(prefix + b'\x00'*(FLAG_LENGTH - len(prefix))) << 512)` là một biến có cùng độ lớn bit với $m_i$ là $928$ bit và tiến hành đo đạc thời gian chạy.
Khi gửi `scramble` lên server, server sẽ tính cho ta `(m + scramble)%n` tận $100000$ lần, sau đó họ cũng sẽ tiến hành mã hóa **RSA** tiếp tục là $100000$ lần!
$$
ms = (m + \text{scramble}) \bmod{n} = (m + n - \text{guess}) \bmod{n} = (m - \text{guess}) \bmod{n}
$$
Nếu `m > guess` thì `ms` thu được sẽ có độ lớn khoảng $52 \cdot 8 + 512 = 928$ bit, còn nếu `m < guess` thì `ms` thu được sẽ có độ lớn khoảng $2047$ đến $2048$ bit.
Khi mã hóa **RSA** với hai số này, thời gian chạy có vẻ là gần như bằng nhau, nhưng vì chương trình lặp lại tận $100000$ lần nên thời gian chạy sẽ có sự khác biệt rõ ràng, vượt qua tầm ảnh hưởng của đường truyền internet.
Vậy ta chỉ cần tiến hành brute-force từng byte của **flag** bằng cách sử dụng tìm kiếm nhị phân và tìm ra byte lớn nhất sao cho `guess <= m` (cách chọn như thế này là hợp lý tại vì `guess` của chúng ta được đệm bởi 512 bit $0$), sau đó cứ lặp lại cho đến khi đủ độ dài **flag** là được.
Dưới đây là toàn bộ lời giải cho thử thách này:
:::spoiler <b style="color:#164d36">solution.py</b>
```python=
from pwn import remote, process
from Crypto.Util.number import bytes_to_long
import time
FLAG_LENGTH = 52
def oracle(connection: remote, prefix: bytes)->int:
n, e = eval(connection.recvline().strip().decode()[6:])
scramble = n - (bytes_to_long(prefix + b'\x00'*(FLAG_LENGTH - len(prefix))) << 512)
connection.sendlineafter(b"scramble the flag: ", f"{scramble}".encode())
start = time.time()
connection.recvuntil(b"c = ")
end = time.time()
c = int(connection.recvline())
return end - start
HOST, PORT = "amt.rs", 42297
# connection = process(["python", "local_chall.py"])
connection = remote(HOST, PORT, timeout = None)
fast_oracle, slow_oracle = oracle(connection, b'\x00'), oracle(connection, b'\xff')
# print(f"{fast_oracle = }")
# print(f"{slow_oracle = }")
flag = b"amateursCTF{"
while len(flag) < FLAG_LENGTH:
left, right = 32, 127
while right - left > 1:
middle = (left + right) >> 1
current_oracle = oracle(connection, flag + bytes([middle]))
# print(f"{current_oracle = }")
if abs(fast_oracle - current_oracle) > abs(slow_oracle - current_oracle):
right = middle
else: left = middle
flag += bytes([left])
connection.close()
connection.success(f"Got flag: {flag.decode()}")
# [+] Got flag: amateursCTF{fa6effd5cad0301c74447cdc098220d6ef9d236}
```
:::
:::success
**Flag: amateursCTF{fa6effd5cad0301c74447cdc098220d6ef9d236}**
:::
## Summary
Trên đây là tất cả các bài ở hạng mục mật mã học trong cuộc thi **AmateursCTF 2025**. Trừ câu đầu tiên ra, những câu còn lại đều rất khó và cần nhiều tư duy.
Sign in with Wallet
Connect another wallet