<div style="text-align:center">
<h1>KCSC Recruitment 2026</h1>
</div>

# Mini RSA

Source code :

from Crypto.Util.number import getPrime, bytes_to_long
from hashlib import sha256

# fake flag, complete 4 phases below to get the real one
FLAG = b"KCSC{676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767676767}"
FLAG = FLAG[5:-1]  
assert all(c in b"0123456789abcdef" for c in FLAG) # hex-only
assert len(FLAG) == 162

part1 = FLAG[0  : 37]
part2 = FLAG[37 : 91]
part3 = FLAG[91 : 155]
part4 = FLAG[155: 162]
assert part1 + part2 + part3 + part4 == FLAG





# Phase 1:
assert len(part1) == 37

n1 = getPrime(1024) * getPrime(1024)
flag1 = bytes_to_long(part1)
assert flag1 < n1
e1 = 7
c1 = pow(flag1, e1, n1)

print("Phase 1:")
print(f"n = {n1}")
print(f"e = {e1}")
print(f"c = {c1}\n")





# Phase 2:
assert len(part2) == 54

moduli = [getPrime(500) * getPrime(500) for _ in range(3)]
flag2 = bytes_to_long(part2)
assert flag2 < min(moduli)
e2 = 7
ciphertexts = [pow(flag2, e2, moduli[i]) for i in range(3)]

print("Phase 2:")
print(f"ns = {moduli}")
print(f"e  = {e2}")
print(f"cs = {ciphertexts}\n")





# Phase 3:
assert len(part3) == 64

p3 = getPrime(512)
q3 = getPrime(512)
n3 = p3 * q3

flag3 = bytes_to_long(part3)
assert flag3 < n3

phi3 = (p3 - 1) * (q3 - 1)
e3 = 0x10001
E = getPrime(16)

assert e3 != E
d3 = pow(E, -1, phi3) # I'm so generous that I will give you d directly :)
c3 = pow(flag3, e3, n3)

print("Phase 3:")
print(f"n = {n3}")
print(f"e = {e3}")
print(f"E = {E}")
print(f"d = {d3}")
print(f"c = {c3}\n")
 




# Phase 4:
assert len(part4) == 7

# hash of the flag
Flag_hash = sha256(FLAG).hexdigest()
print("Phase 4:")
print(f"{Flag_hash = }")

Nhìn qua Source code cũng như cái tên của Challenge thì ta có thể thấy đây là một bài toán mã hóa RSA đã được custom lại thành nhiều phần. Cụ thể hơn, flag của ta đã được chia ra là $4$ phần với độ dài khác nhau. Mỗi phần đều sẽ được mã hóa RSA theo một quy tắc không giống nhau ở mỗi phần. Và bây giờ ta sẽ giải quyết từng phần một để lấy lại Flag.

## Phase 1
Ở Phase 1 Flag của ta có độ dài là 37 bytes, tương ứng là một số nguyên có độ dài $37\times 8=296$ bits. Số mũ công khai là $e=7$ và độ dài Modulo $N$ là $2048$ bits. Rõ ràng khi mã hóa Flag trên thì độ dài của Ciphertext sẽ là :
$$
296\times 7=2072>2048\text{ bits}
$$

Chính vì vậy nên Ciphertext này sẽ bị rút gọn đi bởi Modulo $N$. Vậy thì ta sẽ phải làm sao? Đơn giản là khi này độ dài của Ciphertext cũng chỉ hơn Modulo $N$ một chút nên ta có thể tính lại Flag như thế này :
$$
m^e\equiv c\pmod{N}
$$

$$
\Leftrightarrow m^e=c+kN
$$

$$
\Leftrightarrow m=\sqrt[e]{c+kN}
$$

Brute-force $k$ trong một khoảng nhất định là ta sẽ khôi phục lại được flag1.

Script khai thác :

from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot
from tqdm import trange

FLAG = b""
n = 
e = 
c = 

for k in trange(100000):
    x = c + k*n
    m1, check = iroot(x, e)
    if check:
        break

flag1 = long_to_bytes(m1)
FLAG += flag1

:::success
**flag1 : f8fc7143e81ab9e2a4b8cd7b5893504c68619**
:::

## Phase 2
Ở Phase 2 này Flag của ta có độ dài là 54 và số mũ công khai $e$ vẫn bằng $7$. Điều đặc biệt nhất khi này là Flag của ta sẽ được mã hóa với 3 Modulo $N_i$ khác nhau. Mỗi Modulo có độ dài là $1000$ bits. Điều đó cho ta một hệ phương trình như sau :
$$
\begin{cases}
c_1\equiv m^e\pmod{N_1}\\
c_2\equiv m^e\pmod{N_2}\\
c_3\equiv m^e\pmod{N_3}
\end{cases}
$$

Sử dụng thuật toán CRT (Chinese Remainder Theorem) để gộp $3$ phương trình trên lại với nhau sẽ cho ta một phương trình duy nhất là :
$$
m^e\equiv C\pmod{N_1.N_2.N_3}
$$

Modulo $N_1.N_2.N_3$ sẽ có độ dài là khoảng $3000$ bits. Trong khi đó độ dài của flag2 là $54$ bytes, tức là bằng $54\times 8=432$ bits. Cùng với việc $e=7$ thì Ciphertext của ta khi này sẽ có độ dài khoảng :
$$
432\times 7=3024>3000\text{ bits}
$$

Tới đây thì cách khai thác vẫn sẽ giống như ở Phase 1 do độ dài của Ciphertext cũng chỉ lớn hơn độ dài của Modulo một chút. Thế là ta đã khôi phục được flag2 rồi!!!

Script khai thác :

from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot
from tqdm import trange
from math import prod

def crt(remainders, mod):
    prod = 1
    for m in mod:
        prod *= m
    result = 0
    for r, m in zip(remainders, mod):
        p = prod // m
        result += r * pow(p,-1,m) * p
    return result % prod

ns = []
e  = 
cs = []

m_power_e = crt(cs, ns)
for k in trange(100000):
    x = m_power_e + k*(prod(ns))
    m2, check = iroot(x, e)
    if check:
        break

flag2 = long_to_bytes(m2)
FLAG += flag2

::: success
**flag 2 : 9fea0ba22e7e9ffafae5aaba63a1a64b732debe30e2aaa9e957040**
:::

## Phase 3
Ở Phase 3 này Flag của ta có độ dài cao hơn nữa là $64$ bytes. Độ dài Modulo $N$ khi này là $1024$ bits và $e=65537$. Tưởng chừng như sẽ không có lỗ hỏng nhưng mà đề lại cho ta một giá trị khác rất đặc biệt là một số nguyên $E$ có độ dài là $16$ bits và cũng đồng thời cho ta luôn giá trị nghịch đảo $D$ của số nguyên $E$ đó trong Modulo $N$.

Điều này sẽ tạo ra một lỗ hỏng rất lớn cho phép ta có thể tìm lại được các giá trị bí mật của RSA, để từ đó phá vỡ đi tính bảo mật của loại mã hóa này. Cụ thể hơn, ta có công thức tính khóa bí mật $D$ như sau :
$$
D\equiv E^{-1}\pmod{\phi(N)}
$$

$$
\Leftrightarrow E.D\equiv1\pmod{\phi(N)}
$$

$$
\Leftrightarrow E.D=1+k.\phi(N)
$$

$$
\Leftrightarrow \phi(N)=\frac{E.D-1}{k}
$$

Tới đây ta chỉ cần brute-force một vài giá trị $k$ nhỏ thôi là đã có lại được $\phi(N)$ rồi. Có được $\phi(N)$ sẽ cho ta tính được giá trị khóa bí mật $d$ theo giá trị $e=65537$ để giải Phase 3 này.

Script khai thác :

from Crypto.Util.number import *
from tqdm import trange

n = 58918298105520625812936595965949791679948485672063422501379350174567652137330835174097919449869935351283983373480427262310194532256798429690185381024326970315021350533262412067581291819891395690548362953546838296879197806387922608866341956665531154816197564814442845602714598090456294723302800178858587739713
e = 65537
E = 39119
d = 47540992349005816963249153906419008010878957801546101159437592685401670280805946273432368604390309296333723642831097076480004356212731471488808547049589210685661344692631483342927181931551362472531714993510869363985573142465639097423475598977423653768735951445358570563443850030507199283981083278104055782079
c = 37398307787309593195399039608335293998782975977344821375594074480912755773091240878727726167860952796427287138264423555320002390940336425049899775688041256572345243342480573394310574660551049821001839500881785836377907724697125451771009902048018563262095797500165548399273323153654585302502917216971632506342    

for k in trange(1,2):
    phi = (E*d - 1) // k
    if k*phi == (E*d - 1):
        d_e = pow(e, -1, phi)
        m = pow(c, d_e, n)
        flag3 = long_to_bytes(m)
        if all(c in b"0123456789abcdef" for c in flag3):
            break

FLAG += flag3

::: success
**flag 3 : 3504c6861f68832310c7d569ae3ec1ecbfbba80d65a282127376ef656f9ce50e**
:::

## Phase 4
Ở Phase 4 ta sẽ không còn gặp bất kì mã hóa RSA nào như 3 Phase trên nữa mà thay vào đó ta sẽ nhận lại giá trị băm $\text{SHA256}$ của toàn bộ Flag gốc. Như ta đã biết thì hàm băm $\text{SHA256}$ là một hàm băm rất là an toàn nên việc Crack hàm băm này là điều không thể. Vậy thì ta sẽ phải làm như thế nào để lấy được phần flag cuối cùng này đây?

Trước hết ta có được một vài thông tin quý giá rằng phần Flag được đem đi băm này là phần lõi của Flag và toàn bộ kí tự của phần lõi này là các bytes hex (base16) như trong phần đầu có định nghĩa :

FLAG = FLAG[5:-1]  
assert all(c in b"0123456789abcdef" for c in FLAG) # hex-only

Flag trong Phase 4 này có độ dài là $7$ bytes, kết hợp thêm việc ta đã biết được gần như toàn bộ flag ở trong các Phase trên nên ta hoàn toàn có thể brute-force phần flag ở Phase 4 này. Điều đó là hoàn toàn có thể vì tổng số trường hợp flag4 có thể có là :
$$
16^7=268435456\text{ trường hợp}
$$

Ta chỉ việc brute-force từng trường hợp rồi thử tính giá trị băm của toàn bộ flag đó rồi đem so sánh với giá trị nhận được là xong. Như vậy là đã giải xong Challenge!

Script khai thác :

from Crypto.Util.number import *
from hashlib import sha256
from itertools import product

prefix = FLAG
target_hash = ""
charset = "0123456789abcdef"

for i, p in enumerate(product(charset, repeat=7)):
    flag4 = "".join(p).encode()
    full_flag = prefix + flag4
    if sha256(full_flag).hexdigest() == target_hash:
        break

FLAG += flag4

:::success
**flag4 : d2aa3fe**
:::

Kết hợp lại tất cả ta có được FLAG cuối cùng sau :
:::success
**FLAG : KCSC{f8fc7143e81ab9e2a4b8cd7b5893504c686199fea0ba22e7e9ffafae5aaba63a1a64b732debe30e2aaa9e9570403504c6861f68832310c7d569ae3ec1ecbfbba80d65a282127376ef656f9ce50ed2aa3fe}**
:::

# Muiti RSA

Source code :

from Crypto.Util.number import *
from random import randint

flag = b'KCSC{??????????????????????????????????????????????????????????????????????????????????????????}'
assert flag.startswith(b"KCSC{") and len(flag) == 96

# my prime generator
def get_prime(factor_bits, nbits):
    while True:
        p = 2
        while p.bit_length() + factor_bits < nbits:
            p *= getPrime(factor_bits)
        current_len = p.bit_length()
        needed_bits = nbits - current_len
        
        if needed_bits < 2:
            continue
        try:
            last_prime = getPrime(needed_bits)
        except ValueError:
            continue
        
        p = p * last_prime + 1
        if p.bit_length() == nbits and isPrime(p):
            return p

p = get_prime(16, 128)
q = get_prime(16, 128)
n = p * q
phi = (p-1)*(q-1)

# 3 parts of the flag
m1, m2, m3 = [bytes_to_long(part) for part in [flag[i:i+32] for i in range(0, len(flag), 32)]]
assert all(part < n for part in [m1, m2, m3])

es = []
cs = []
for i in range(3):
    # rsa encryption
    e1, e2, e3 = [randint(1, phi-1) for _ in range(3)]
    
    c1 = pow(m1, e1, n)
    c2 = pow(m2, e2, n)
    c3 = pow(m3, e3, n)
    
    es.append((e1, e2, e3))
    # cs.append((c1, c2, c3)) # nah, too easy
    cs.append((c1 * c2 * c3) % n) # what if i multiply them together ?

# write outputs to file
with open("output.txt", "w") as f:
    f.write(str(n)  + "\n")
    f.write(str(es) + "\n")
    f.write(str(cs))

Vẫn tiếp tục là một bài RSA nhưng lần này cách mã hóa lại khác so với tiêu chuẩn. Trước hết, ta sẽ nói về hàm `get_prime` được custom trong Source code này. Về cơ bản thì hàm sẽ sinh ra các số nguyên tố $p$ có $p-1$ là một Smooth number. Hai tham số $p,q$ trong bài RSA này sẽ được lấy từ hàm `get_prime` đó và đặc biệt là độ dài của từng số chỉ vỏn vẹn có $128$ bits. Điều đó dẫn đến việc Modulo $N=p.q$ cũng sẽ chỉ có độ dài là $256$ bits và ta hoàn toàn có thể factor được nó bằng **[factordb](fttps://factordb.com)** như này :

Đó là về Modulo $N$ của ta. Còn bây giờ đến với việc mã hóa Flag của Challenge này. Flag của ta sẽ được chia ra làm $3$ phần bằng nhau và từng phần sẽ được mã hóa bằng số mũ $e_i$ khác nhau. Cuối cùng, ta sẽ nhận lại được giá trị tích của $3$ Ciphertext đó là :
$$
c\equiv m_1^{e_1}.m_2^{e_2}.m_3^{e_3}\pmod{N}
$$

Tuy nhiên, ta sẽ nhận được thêm $3$ Ciphertext giống như vậy nữa, dẫn đến việc ta có một hệ như sau :
$$
c_1\equiv m_1^{e_{1,1}} . m_2^{e_{1,2}} . m_3^{e_{1,3}} \pmod{N}
$$

$$
c_2\equiv m_1^{e_{2,1}} . m_2^{e_{2,2}} . m_3^{e_{2,3}} \pmod{N}
$$

$$
c_3\equiv m_1^{e_{3,1}} . m_2^{e_{3,2}} . m_3^{e_{3,3}} \pmod{N}
$$
>với mỗi $e_{i,j}$ là khác nhau

Vậy ta có thể giải bài toán này như thế nào?

Nếu như chỉ để nguyên các phương trình dạng như trên thì rất khó để có thể giải ra. Thay vào đó, ta sẽ dùng kĩ thuật nhằm đưa phương trình trên từ "phép nhân" về lại thành "phép cộng". Và tất nhiên, lý thuyết toán học đáp ứng được nhu cầu đó chính là phép toán Logarithm. Ta có phương trình dạng :
$$
c\equiv m_1^{e_1}.m_2^{e_2}.m_3^{e_3}\pmod{N}
$$

Khi này lấy Logarithm hai vế ta có :
$$
log(c)=log(m_1^{e_1}.m_2^{e_2}.m_3^{e_3})\pmod{N}
$$

$$
\Leftrightarrow log(c)=log(m_1^{e_1})+log(m_2^{e_2})+log(m_3^{e_3})\pmod{N}
$$

$$
\Leftrightarrow log(c)=e_1.log(m_1)+e_2.log(m_2)+e_3.log(m_3)\pmod{N}
$$
>Ở đây ta không cần phải biết về cơ số trong phép tính Logarithm này bởi vì mình chỉ dùng phép tính này để mô tả mối quan hệ giữa các thành phần trong từng phương trình với nhau

Áp dụng điều này cho hệ ba phương trình như trên ta có :
$$
\begin{cases}
log(c_1)=e_{1,1}.log(m_1)+e_{1,2}.log(m_2)+e_{1,3}.log(m_3)\pmod{N}\\
log(c_2)=e_{2,1}.log(m_1)+e_{2,2}.log(m_2)+e_{2,3}.log(m_3)\pmod{N}\\
log(c_3)=e_{3,1}.log(m_1)+e_{3,2}.log(m_2)+e_{3,3}.log(m_3)\pmod{N}
\end{cases}
$$

Biểu diễn dưới dạng Ma trận ta có :
$$
\begin{bmatrix}
log(c_1)\\
log(c_2)\\
log(c_3)
\end{bmatrix}=
\begin{bmatrix}
e_{1,1} & e_{1,2} & e_{1,3}\\
e_{2,1} & e_{2,2} & e_{2,3}\\
e_{3,1} & e_{3,2} & e_{3,3}
\end{bmatrix}\times
\begin{bmatrix}
log(m_1)\\
log(m_2)\\
log(m_3)
\end{bmatrix}\pmod{N}
$$

Ta có thể kí hiệu gọn hơn là :
$$
C=E\times M\pmod{N}
$$

Từ đây ta có :
$$
M=E^{-1}\times C\pmod{N}
$$

Đặt $D=E^{-1}\pmod{\phi(N)}$, ta có :
$$
M=D\times C\pmod{N}
$$

Sau khi tính được ma trận $D$ (gồm các phần tử $d_{i,j}$), ta chuyển ngược lại từ dạng Logarithm về dạng lũy thừa RSA để tính từng phần Flag:

$$
m_1\equiv c_1^{d_{1,1}} . c_2^{d_{1,2}} . c_3^{d_{1,3}} \pmod{N}
$$

$$
m_2\equiv c_1^{d_{2,1}} . c_2^{d_{2,2}} . c_3^{d_{2,3}} \pmod{N}
$$

$$
m_3\equiv c_1^{d_{3,1}} . c_2^{d_{3,2}} . c_3^{d_{3,3}} \pmod{N}
$$

Vậy thì bây giờ ta phải tính ma trận $D=E^{-1}\pmod{\phi(N)}$ như thế nào?

Nếu như bạn đã học qua đại số tuyến tính thì bạn chắc cũng đã biết những cách để tính ma trận nghịch đảo của một ma trận $E$ cho trước rồi đúng không? Công thức tính nghịch đảo của một ma trận vuông $E$ cấp $n$ là :
$$
E^{-1} = \frac{1}{\det(E)} \text{adj}(E)
$$

Mình sẽ không giải thích nhiều về công thức trên vì cái này đã được giảng dạy ở năm nhất rồi. Còn nếu như bạn đã quên về nó thì có thể xem **[Video này](https://www.youtube.com/watch?v=KH8cP3u1e1I&list=PLsEmKKF4H46nqwlr8JDf05ecduzzaNz3R&index=8)** để nhớ lại nhá :smile:

Còn trong bài này, ta có một cách rất là nhanh để tính giá trị $adj(E)$ là sử dụng phương thức `adjugate()` trong SageMath. Sau khi đã tính xong thì bạn sẽ nhận ra một điều khá đặc biệt. Đó là ta sẽ có tính chất :
$$
E.\text{adj}(E)=det(E).I
$$
>Cái này biến đổi từ công thức tính ma trận nghịch đảo như trên.

Rõ ràng, việc nhân hai ma trận $E$ và $\text{adj(E)}$ sẽ cho ta một ma trận đường chéo có các phần tử trên đường chéo là $det(E)$. Điều đó đồng nghĩa với việc ta sẽ thu được một vài giá trị $V_i$ mới là :
$$
V_i\equiv m_i^{\det(E)} \pmod{N}
$$

Giờ đây, bài toán trên trở thành : Tìm $x$ (chính là $m_1$) khi biết $x^K = V \pmod n$ (với $K = \det(E)$). Nhìn sơ qua thì đây là bài toán RSA cơ bản ($m^e\equiv c\pmod{N}$). Tuy nhiên, $K$ ở đây có thể không nguyên tố cùng nhau với $\phi(n)$ khiến ta không thể tính nghịch đảo trực tiếp để tìm $d$. Vậy thì cách giải ở đây sẽ là gì?

Đó chính là ta chia nhỏ phương trình kia thành phương trình nhỏ hơn trong Modulo $p$ và $q$ đã biết. Cụ thể ta sẽ :
- Tìm $x_p$ sao cho $x_p^K \equiv V \pmod p$
- Tìm $x_q$ sao cho $x_q^K \equiv V \pmod q$
> Ở đây các bạn có thể dùng hàm `nth_root` trong SageMath để tính căn thức.

Sau cùng là sử dụng thuật toán CRT để ghép hai nghiệm $x_p$ và $x_q$ lại thành nghiệm $x$ trong Modulo $N$. Thế là xong rồi!!!

Script khai thác :

from Crypto.Util.number import long_to_bytes,GCD
from sage.all import *

n = 
es = []
cs = []
p = 208241528391730184734449228964657137983
q = 228925423331290125959230566821710134887
assert n == p * q

Matrix_E = Matrix(ZZ, es)
det_E = Matrix_E.determinant()
adj_E = Matrix_E.adjugate()

assert GCD(det_E, (p-1)*(q-1)) != 1

parts_candidates = []

for i in range(3):
    print(f"\n[*] Solving for m{i+1}...")
    target_val = 1
    for j in range(3):
        exponent = Integer(adj_E[i, j])
        term = pow(cs[j], exponent, n) 
        target_val = (target_val * term) % n
    
    try:
        roots_p = GF(p)(target_val).nth_root(det_E, all=True)
        roots_q = GF(q)(target_val).nth_root(det_E, all=True)

    except ValueError:
        print("No found root k.")
        continue
        
    candidates = []
    for rp in roots_p:
        for rq in roots_q:
            val = crt([Integer(rp), Integer(rq)], [p, q])
            candidates.append(val)
            
    valid_cands = []
    for cand in candidates:
        try:
            m_bytes = long_to_bytes(cand)
            if all(32 <= b <= 126 for b in m_bytes): 
                valid_cands.append(m_bytes)
            elif i == 0 and b'KCSC' in m_bytes:
                valid_cands.append(m_bytes)
        except:
            pass
            
    if not valid_cands:
        valid_cands = [long_to_bytes(c) for c in candidates]

    print(f"Found {len(valid_cands)} candidate(s) for part {i+1}")
    parts_candidates.append(valid_cands)


for p1 in parts_candidates[0]:
    for p2 in parts_candidates[1]:
        for p3 in parts_candidates[2]:
            flag = p1 + p2 + p3
            if b"KCSC" in flag:
                print(f"\n{flag.decode()}")

::: success
**FLAG : KCSC{I_hope_you_used_factor_and_discrete_log_to_solve_this_challenge_9f72b5a7608c076684b6ca6157}**
:::

# Lost

Source code :

from Crypto.Util.number import getPrime, bytes_to_long

flag = "KCSC{████████████████████████████████████████l█e███████ha█████████████████████}"
assert len(flag) == 79
flag = bytes_to_long(flag.encode())

p = getPrime(512)
q = getPrime(512)
n = p * q
e = 0x10001
phi = (p-1) * (q-1)

# how many bits of phi do you want me to truncate <(") ?
HINT = phi & ((1 << (445)) - 1)

assert flag < n
c = pow(flag, e, n)

print(f'{n = }')
print(f"{e = }")
print(f'{c = }')
print(f'{HINT = }')

Thêm một bài RSA nữa :smile:. Ở đây mọi thứ được tạo ra rất bình thường với các tham số chuẩn. Tuy nhiên, Source có cho ta thêm Hint đó là tiết lộ cho ta biết $445$ bits cuối của giá trị $\phi(N)$. Điều này vô tình chung đã tạo ra một lỗ hỏng rất lớn cho phép ta khôi phục lại được giá trị của $p,q$.

Cụ thể hơn, với việc tiết lộ $445$ bits cuối của $\phi(N)$ sẽ cho ta thông tin như sau :
$$
\phi(N)=(p-1)(q-1)
$$

$$
\Leftrightarrow\phi(N)=N-(p+q)+1
$$

$$
\Leftrightarrow p+q=N-\phi(N)+1
$$

$$
\Leftrightarrow p+q\equiv N-\phi(N)+1\pmod{2^{445}}
$$

$$
\Leftrightarrow p+q\equiv N-\text{Hint}+1\pmod{2^{445}}
$$

Khi này ta cũng đồng thời biết được luôn $445$ bits cuối của giá trị $S=p+q$. Bạn có thể thêm đoạn code dưới đây vào Source challenge để kiểm chứng :

lsb_p_plus_q = (n - HINT + 1) % 2**445
assert (p+q) & ((1 << (445)) - 1) == lsb_p_plus_q

Như vậy khi có được các bits cuối của $p+q$ thì ta có thể khai thác như thế nào? Nhớ lại định lý Viète về phương trình bậc hai đã học ở lớp $9$ ta có :
:::info
**Định lý Viète** : Nếu $x_1,x_2$ là nghiệm của phương trình $ax^2+bx+c=0$ với $a\neq 0$ thì ta có :
- $x_1+x_2=-\frac{b}{a}$
- $x_1.x_2=\frac{c}{a}$

Muốn tìm hai số $u,v$ thỏa mãn $S=u+v$ và $P=u.v$ thì ta chỉ cần giải phương trình $x^2-Sx+P=0$, với $S^2-4P\geq 0$
:::

Ta đã biết được giá trị của $S\equiv p+q\pmod{2^{445}}$ và việc tính giá trị $P\equiv p.q\pmod{2^{445}}$ là hoàn toàn dễ dàng với $N=p.q$. Như vậy ta sẽ có phương trình Modulo như sau :
$$
x^2-Sx+P\equiv 0\pmod{2^{445}}
$$

Theo lý thuyết thì khi giải phương trình này sẽ cho ta nghiệm là các giá trị của $p,q$. Tuy nhiên khi này do đang bị áp Modulo $2^{445}$ nên giá trị thực tế mà ta nhận được chỉ là $p\mod{2^{445}}$, trong khi đó giá trị gốc của $p$ là một số dài $512$ bits. Vậy thì ta phải làm sao để tìm được $p$ ban đầu đây?

Ta biết rằng, giá trị mà ta nhận được sau khi giải phương trình bậc hai trên là giá trị của $445$ bits cuối của $p$. Tức là về mặt lý thuyết ta đang không biết khoảng $512-445=67$ bits đầu của $p$. Tới đây có thể bạn sẽ nghĩ rằng ta có thể brute-force thử $67$ bits đầu đó của $p$, thế nhưng điều đó là khó thể thực hiện được vì bạn sẽ phải brute-force tối đa $2^{67}$ trường hợp có thể xảy ra để tìm lại giá trị $p$ chuẩn. Điều đó sẽ làm tiêu tốn rất nhiều tài nguyên trên máy của các bạn nên là trừ khi các bạn có siêu máy tính thì gần như với máy tính cá nhân thì không thể thực hiện brute-force kiểu đó được. Vậy thì còn cách nào khác không?

Tất nhiên là vẫn còn rồi :smile:. Ở đây nếu ta đặt `p_low` là giá trị của $445$ bits cuối của $p$ thì ta có thể biểu diễn $p$ dưới dạng phương trình là :
$$
p=2^{445}.x+\text{p_low}
$$

Tới đây ta sẽ sử dụng thuật toán CopperSmith để giải phương trình trên. Đó vốn là một công cụ rất mạnh để giải các phương trình tìm nghiệm nguyên nhỏ trong một vành Modulo nào đó (ở đây là Modulo $N$). Ta sẽ sử dụng phương thức `small_roots` của thư viện SageMath với giới hạn của nghiệm $x$ tìm được là $2^{67}$ và `beta=0.5`. Sau khi có được $x$ thì ta có thể tìm được $p,q$ và có thể giải mã RSA rồi!!!

Script khai thác :

from Crypto.Util.number import long_to_bytes
from sage.all import *

n = 
e = 
c = 
HINT = 

known_bits = 445  

s_lsb = (n - HINT + 1) % (2**known_bits)

x = PolynomialRing(Zmod(2**known_bits), 'x').gen()
f = x**2 - s_lsb*x + n

list_roots = f.roots(multiplicities=False)
print(f"Số nghiệm là {len(list_roots)}")

unknown_bits = 512 - known_bits
X_bound = 2**unknown_bits  

for r in list_roots:
    p0 = Integer(r)
    PR = PolynomialRing(Zmod(n), 'y')
    y = PR.gen()
    
    g = y * (2**known_bits) + p0
    g = g.monic()
    res = g.small_roots(X=X_bound, beta=0.5)
    
    if res:
        print(f"Found y : {res[0]}")
        p_high = Integer(res[0])
        p = p_high * (2**known_bits) + p0
        if n % p == 0:
            q = n // p
            
            phi = (p-1)*(q-1)
            d = inverse_mod(e, phi)
            m = pow(c, d, n)
            flag_bytes = long_to_bytes(m)
            
            if b'KCSC' in flag_bytes:
                print("\nFLAG:", flag_bytes.decode())
                break
            else:
                print("Not found flag")
        else:
            print("Not found p.")
    else:
        print("Not found root with this p0")

#Found y : 129363962604587626237

::: success
**FLAG : KCSC{i_hope_you_used_coppersmith_method_to_solve_this_challenge_not_bruteforce}**
:::

# rsabcde

Source code :

from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime
# from secret import flag, f4k3_fl4g
import sys , random
sys.set_int_max_str_digits(678)

flag = b"KCSC{Real_flag}"
f4k3_fl4g = "KCSC{Fake_flag}"
assert bytes_to_long(flag) < 2**456

try: 
    a, b, c, d, e = [ int(input(f"{x} = ")) for x in "abcde" ]
    assert a > 0 
    assert 1111111111111111111 * a == c + 8888888888888888881 * e
    assert 9999999999999999961 * b == 1258462969247482836585791373370000000000000000000000000000000000000000011896691036181988787986574538026426876 * a
    assert d ** 2 == a + b
    if a.bit_length() < 234:
        prime = getPrime(512)
        rand = random.choice([a, b, c, d, e])
        n = prime * rand
        ct = pow(bytes_to_long(flag), e, n)
        print(f"n = {n}")
        print(f"ct = {ct}")
    else:
        print("(👉ﾟヮﾟ)👉", f4k3_fl4g.decode())

except: print("Nope!")

>RSA again :(

Nói challenge này là một dạng mã hóa RSA thì cũng không sai, nhưng ý tưởng chính của nó lại nằm ở một vấn đề toán học khác. Cụ thể hơn thì để có thể nhận các tham số cần thiết của RSA thì ta phải giải quyết một bài toán trước đó là : Tìm các số nguyên $a,b,c,d,e$ thỏa mãn các điều kiện sau :
$$
\begin{cases}
C_a\times a=c+C_e\times e\\
K_b\times b=K_a\times a\\
d^2=a+b
\end{cases}
$$

Ngoài ra, điều kiện của $a$ còn phải là $0<a<2^{234}$. Thỏa mãn các điều kiện đó thì Server sẽ trả về cho ta hai giá trị là : $N=p\times\text{rand}$ với $\text{rand}$ là chọn ngẫu nhiên trong năm số $a,b,c,d,e$ mà ta gửi vào. Tiếp đến là giá trị : $c\equiv m^e\pmod{N}$ với $e$ là giá trị mà ta gửi vào. Đó chính là tất cả những gì mà Source code thực hiện. Bây giờ ta phải làm sao để giải quyết Challenge này đây?

Đầu tiên hãy xét phương trình :
$$
K_b\times b=K_a\times a
$$

Ta biết rằng $\text{gcd}(K_a,K_b)=1$ nên nếu muốn $b$ là một số nguyên thì $b$ phải chia hết cho $K_a$ và tương tự $a$ phải chia hết cho $K_b$. Ta có thể đặt :
$$
\begin{cases}
a=K_b.t\\
b=K_a.t
\end{cases}
$$

$$
\Rightarrow d^2=(K_a+K_b).t
$$

$$
\Leftrightarrow d=\sqrt[2]{(K_a+K_b).t}
$$

Factor giá trị $(K_a+K_b)$ ta có :

from sage.all import factor

K_a = 1258462969247482836585791373370000000000000000000000000000000000000000011896691036181988787986574538026426876 
K_b = 9999999999999999961 

print(K_a + K_b)
# 1258462969247482836585791373370000000000000000000000000000000000000000011896691036181988797986574538026426837


factor = 125846296924748283658579137337^2 * 79462012346534541362149890632590776427112926556773

Như vậy để cho giá trị $d$ là số nguyên thì ta có thể lấy luôn $t=7946..$. Và khi đã có $t$ thì ta đã có thể tính được giá trị của $a,b$ rồi, từ đó tính thêm được cả giá trị $d$. Giờ chỉ còn mỗi hai giá trị $e$ và $c$.

Khi này, theo trực giác thì ta nên chọn $e=1$ bởi vì giá trị $e$ này còn đóng vai trò là số mũ công khai mã hóa RSA. Việc chọn $e$ như vậy sẽ đảm bảo rằng giá trị của Flag sẽ không bị ảnh hưởng bởi Modulo $N$, và khi đó giá trị $ct$ sẽ chính là giá trị của Flag mà ta cần tìm.
$$
ct\equiv\text{flag}\pmod{N}
$$

Như vậy, ta đã có được $e$ rồi. Chỉ cần thay $a$ và $e$ vào phương trình đầu tiên là có thể tìm lại được $c$ rồi. Bài toán kết thúc !!!

Script khai thác :

from Crypto.Util.number import long_to_bytes
from pwn import process, remote
from math import isqrt

# io = process(["python3", "rsabcde.py"])
io = remote('67.223.119.69', 5010)

K_b = 9999999999999999961
K_a = 1258462969247482836585791373370000000000000000000000000000000000000000011896691036181988787986574538026426876
t =  79462012346534541362149890632590776427112926556773
a = K_b * t
b = K_a * t

d = int(isqrt(a + b))

e = 1
c = 1111111111111111111 * a - 8888888888888888881 * e

assert a > 0 
assert a.bit_length() < 234
assert 1111111111111111111 * a == c + 8888888888888888881 * e
assert 9999999999999999961 * b == 1258462969247482836585791373370000000000000000000000000000000000000000011896691036181988787986574538026426876 * a
assert d ** 2 == a + b

io.sendlineafter("a = ", str(a).encode())
io.sendlineafter("b = ", str(b).encode())
io.sendlineafter("c = ", str(c).encode())
io.sendlineafter("d = ", str(d).encode())
io.sendlineafter("e = ", str(e).encode())

io.recvline()
n  = int(io.recvline().decode().split("n = ")[1].strip())
ct = int(io.recvline().decode().split("ct = ")[1].strip())

flag = long_to_bytes(ct)
print(flag.decode())

:::success
**FLAG : KCSC{f4c70rDB_15_4m4z1ng!}**
:::

# to be continued

Source code :

from sage.all import *
from Crypto.Util.number import getPrime, bytes_to_long, GCD
import random

flag = bytes_to_long(b"KCSC{???????????????????????????}")
rbits = lambda x: random.getrandbits(x)
p, q = getPrime(1024), getPrime(1024)
N = p*q
a, b = rbits(910), rbits(910)
assert GCD(a, b) == 1
phi = (p**3 - a) * (q**3 - b)
d = getPrime(1024)
e = pow(d, -1, phi)
c = pow(flag, e, N)

print("Welcome to KCSC's Recruiment")
print("Gifts: ")
print("a = ", a)
print("b = ", b)
print("N = ", N)
print("e = ", e)
print("c = ", c)

:::spoiler Don't click this :(
:::

Nhìn sơ qua Source code thì đây vẫn là một bài RSA thông thường với các tham số $p,q$ được chọn khá to để tránh việc Modulo $N$ được tạo nên từ hai số đó có thể bị factor một cách dễ dàng. Điều đặc biệt ở trong bài mã hóa RSA này là việc giá trị $\phi(N)$ được tính với công thức khác là :
$$
\Phi=(p^3-a)(q^3-b)
$$
>với $a,b$ là các số ngẫu nhiên dài khoảng $910$ bits. Ký hiệu $\Phi$ ở đây được dùng để ký hiệu cho hàm Phi đã được custom này thay vì $\phi(N)$ để tránh nhầm lẫn với công thức đúng.

Source thay vì đi tính giá trị $d$ từ giá trị $e$ cho trước thì ở đây lại làm ngược lại, và lại còn tính trong Modulo $\Phi$ đã được custom kia. Vậy thì ta sẽ phải khai thác bài này như thế nào?

Đầu tiên, khi bạn đọc các tham số trong file `output.txt` thì bạn có thể thấy một điều đặc biệt ở giá trị $e$. Đó là nó có giá trị rất rất lớn, vượt xa hơn hẳn giá trị của Modulo $N$. Mà trong RSA, nếu như giá trị của $e$ mà lớn hơn hoặc gần bằng Modulo $N$ thì ta có kiểu tấn công gì nhỉ? Đúng rồi, đó là **Wiener Attack**.

Ta sẽ phân tích một chút. Trước hết, ta có được mối quan hệ giữa hai giá trị $e$ và $d$ là :
$$
d\equiv e^{-1}\pmod{\Phi}
$$

$$
\Leftrightarrow e.d=1+k.\Phi
$$

Độ dài của hai số nguyên tố $p,q$ là khoảng $1024$ bits, dẫn đến độ dài của Modulo $N$ là khoảng $2048$ bits. Nếu ta viết lại công thức của $\Phi$ thì ta sẽ có :
$$
\Phi=(p^3-a)(q^3-b)
$$

$$
\Leftrightarrow\Phi=(pq)^3-(aq^3+bp^3-ab)\approx N^3
$$
>với $N^3$ có độ dài khoảng $2048\times 3=6144$ bits

Giá trị bí mật $d$ có độ dài là $1024$ bits. Vậy theo định lý Wiener, nếu $d<\frac{1}{3}\sqrt[4]{M}$, với $M$ là Modulo mà $e$ và $d$ nghịch đảo cho nhau thì ta có thể khôi phục $d$ bằng phương pháp liên phân số (Continued Fractions).

Cụ thể hơn, nếu như ta lấy $d\approx 2^{1024}$ và $M=\Phi\approx N^3\approx 2^{6144}$ thì điều kiện của ta sẽ là :
$$
d<\frac{1}{3}\sqrt[4]{M}
$$

$$
\Leftrightarrow 2^{1024}<\frac{1}{3}\sqrt[4]{2^{6144}}
$$

$$
\Leftrightarrow 2^{1024}<\frac{1}{3}2^{1536}\hspace{5mm}\text{(luôn đúng)}
$$

Như vậy là ta có thể triển khai được liên phân số của $\frac{e}{N^3}$ để tìm lại được cặp $(k,d)$ rồi. Sau đó ta sẽ tính được $\Phi=\frac{e.d-1}{k}$. Có được giá trị $\Phi$ thì ta sẽ bắt đầu tìm lại giá trị của $p$ và $q$. Từ đẳng thức :
$$
\Phi=(p^3-a)(q^3-b)
$$

ta sẽ biến đổi như sau : Đặt $q=\frac{N}{p}$ ta có :
$$
\Phi=(p^3-a)[(\frac{N}{p})^3-b]
$$

$$
\Leftrightarrow \Phi.p^3=(p^3-a)(N^3-b.p^3)
$$

Đặt $X=p^3$ ta có :
$$
\Phi.X=(X-a)(N^3-b.X)
$$

$$
\Leftrightarrow \Phi.X=-bX^2+N^3X-aN^3+abX
$$

$$
\Leftrightarrow bX^2 + (\Phi-N^3-ab)X+aN^3=0
$$

Giải phương trình bậc hai trên để tìm $X$ rồi từ đó có thể tính được $p$ bằng cách tính $p=\sqrt[3]{X}$. Như vậy là xong rồi!!!

Script khai thác :

from sage.all import *
from Crypto.Util.number import long_to_bytes

a =  
b =  
N =  
e =  
c =  

Phi_approx = N**3

# Khai triển liên phân số e / N^3
cf = continued_fraction(Integer(e) / Integer(Phi_approx))

found = False
p_found = 0

for conv in cf.convergents():
    k = conv.numerator()
    d_guess = conv.denominator()
    
    if k == 0: continue
    if (e * d_guess - 1) % k != 0:
        continue
        
    Phi_real = (e * d_guess - 1) // k
    
    A = b
    B = Phi_real - N**3 - a*b
    C = a * N**3
    
    delta = B**2 - 4*A*C
    
    if delta >= 0 and delta.is_square():
        sqrt_delta = delta.isqrt()
    
        X1 = (-B + sqrt_delta) // (2*A)
        X2 = (-B - sqrt_delta) // (2*A)
        
        for X in [X1, X2]:
            if X > 0:
                try:
                    p_val = X.nth_root(3)
                    if N % p_val == 0:
                        p_found = p_val
                        found = True
                        print(f"[+] Found p: {p_found}")
                        break
                except:
                    pass
    if found:
        break

if found:
    q_found = N // p_found
    phi_standard = (p_found - 1) * (q_found - 1)
    
    try:
        d_standard = inverse_mod(e, phi_standard)
        m = pow(c, d_standard, N)
        flag = long_to_bytes(m)
        print(f"\nFlag: {flag.decode()}")
    except Exception as err:
        print(f"{err}")
else:
    print("No solution.")

:::success
**FLAG : KCSC{Be_water!My_friend}**
:::

# Sign v2

Source code :

from hashlib import sha256
from Crypto.Util.number import bytes_to_long, long_to_bytes
from ecdsa import ellipticcurve
from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key
from os import *
from random import randint
from pwn import xor
# from flag import flag
from base64 import b64decode

flag = b"KCSC{fake_flag}"
secret = urandom(16)

G = generator_256
p = G.order()

def genKeyPair():
    d = randint(1,p-1)
    pubkey = Public_key(G, d*G)
    privkey = Private_key(pubkey, d)
    return pubkey, privkey

def ecdsa_sign(msg, nonce,privkey):
    hsh = sha256(b64decode(msg)).digest()
    nonce = sha256(xor(sha256(b64decode(nonce)).digest(), secret)).digest()
    sig = privkey.sign(bytes_to_long(hsh), bytes_to_long(nonce))
    return {"msg": msg, "r": hex(sig.r), "s": hex(sig.s)}

def challenge() :
    pubkey , privkey = genKeyPair()
    
    print('\nPublic key:', (int(pubkey.point.x()), int(pubkey.point.y())), '\n')
    print("1 : Sign msg ")
    print("2 : Submit private key")
    nonces = []
    for _ in range(3) :
        try : 
            option = int(input("Option : "))
            if option == 1 :
                
                msg = (input("Enter your message: ")).encode()
                nonce = (input("Enter your nonce: ")).encode()
                
                if nonce in nonces :
                    print('Nope')
                    exit()
                    
                if len(nonces) > 0 : 
                    
                    for i in nonces :
                        if nonce in i or i in nonce:
                            print('Nope')
                            exit()
                       
                nonces.append(nonce)
                print(ecdsa_sign(msg,nonce,privkey))
                    
                            
            if option == 2 :
                
                d = int(input("Private key : "))
                print(nonces)
                if d == int(privkey.secret_multiplier) :
                    print(f'Very nice , here is your flag : {flag}')
                    exit()
                
                else :
                   
                    print(f'Wrong key , correct is {privkey.secret_multiplier}')
                    exit()
                    
        except :
            
            print("Not legal option")
            exit()
    print("Out of attemps !! ")    
challenge()

>Sau một chuỗi các bài RSA thì cuối cùng ta cũng đã thoát khỏi nó :smiling_imp:

Nhìn sơ qua Source code thì có thể thấy đây là một dạng Service mô phỏng lại quá trình kí dữ liệu bằng thuật toán ECDSA. Ta sẽ có quyền được nhập một $msg$ bất kì và một Nonce dưới dạng chuỗi $base64$. Server sẽ kí cái $msg$ đó bằng Nonce mà ta gửi kèm. Điều kiện để lấy được Flag là ta phải có được khóa bí mật $d$ được dùng trong quá trình kí $msg$, gửi nó lên cho Server để lấy được Flag. Đó là toàn bộ những gì mà Server thực hiện. Vậy ta cần phải làm sao để biết được khóa bí mật $d$ đây?

Đầu tiên, ta có thể thấy được loại đường cong mà Server sử dụng để thực hiện thuật toán ECDSA là **[NIST P-256](https://std.neuromancer.sk/nist/P-256)**, vốn là một đường cong rất an toàn nên ta sẽ không thể khai thác được gì ở trong phần này.

Thực ra nếu để ý thì trong option $1$ là ký $msg$ thì ta còn được phép gửi kèm Nonce theo và Server sẽ sử dụng cái Nonce mà ta gửi đó để ký $msg$. Điều đó có thể dẫn đến việc : Nếu như ta kí hai tin nhắn khác nhau nhưng cùng sử dụng chung một Nonce thì rõ ràng đây chính là lỗ hỏng **Reuse Nonce** của ECDSA. Khi đó ta hoàn toàn có thể khôi phục lại khóa bí mật $d$. Thế nhưng liệu điều đó có thể thực hiện được không?

Tất nhiên là không rồi! Hãy nhìn vào đoạn code này :

nonces = []
if option == 1 :
    
    msg = (input("Enter your message: ")).encode()
    nonce = (input("Enter your nonce: ")).encode()

    if nonce in nonces :
        print('Nope')
        exit()

    if len(nonces) > 0 : 

        for i in nonces :
            if nonce in i or i in nonce:
                print('Nope')
                exit()

    nonces.append(nonce)
    print(ecdsa_sign(msg,nonce,privkey))

Server sẽ thực hiện việc kiểm tra xem chuỗi Nonce mà ta vừa nhập có giống với chuỗi nào mà ta đã nhập trước đó hay không và kiểm tra xem chuỗi Nonce nhập vào có chứa chuỗi đã nhập trước đó hay không (tức là kiểu nhập lại chuỗi trước đó nhưng thêm một vài bytes nữa). Điều đó đã gần như chặn đi việc ta có thể tái sử dụng Nonce để khai thác lỗ hỏng của ECDSA nhằm khôi phục lại $d$ rồi. Vậy bây giờ ta phải làm sao?

Đọc lại Source code một lần nữa thì bạn sẽ thấy một điều rất là thú vị. Cụ thể là ở trong hàm `ecdsa_sign` này :

def ecdsa_sign(msg, nonce,privkey):
    hsh = sha256(b64decode(msg)).digest()
    nonce = sha256(xor(sha256(b64decode(nonce)).digest(), secret)).digest()
    sig = privkey.sign(bytes_to_long(hsh), bytes_to_long(nonce))
    return {"msg": msg, "r": hex(sig.r), "s": hex(sig.s)}

Như đã nói lúc đầu, Server sẽ yêu cầu ta truyền vào một $msg$ cùng với Nonce ở dạng base64 để có thể ký được $msg$ đó. Điều đáng chú ý nằm ở chỗ : Khi decode một vài chuỗi base64 thì có thể cho ra hai chuỗi giống hệt nhau.

Ví dụ :

from base64 import b64decode

str1 = "YWxpbmc="
str2 = "YWxpbmd="

print(b64decode(str1) == b64decode(str2) == b"aling")
# True

> Điều này có thể hiểu khi chuỗi gốc không chia hết cho 3 bytes, khiến các bit đệm (padding bits) dư thừa bị bộ giải mã bỏ qua.

Có thể thấy, hai chuỗi `str1` và `str2` dù khác nhau nhưng khi decode base64 vẫn cho ra cùng một kí giống nhau ("a"). Điều đó sẽ giúp cho ta qua mắt được vòng kiểm tra Nonce mà ta gửi vào của Server. Với việc có được hai $msg$ có chung một Nonce thôi là ta đã có thể khôi phục lại khóa bí mật $d$ và có thể lấy được Flag rồi!!!

Cách để tìm lại $d$ :

- Ta có được công thức tính các chữ kí như sau :
$$
\begin{cases}
s_1 \equiv k^{-1}.(z_1 + d.r) \pmod n \hspace{5mm} (1) \\
s_2 \equiv k^{-1}.(z_2 + d.r) \pmod n \hspace{5mm} (2)
\end{cases}
$$
>với $d$ là khóa bí mật, $z$ là giá trị băm của $msg$ và $n$ là order của điểm sinh $G$ của đường cong Elliptic.

- Lấy $(2)-(1)$ ta có :
$$
s_2-s_1\equiv k^{-1}.(z_2-z_1)\pmod n
$$

$$
\Leftrightarrow k\equiv\frac{z_2-z_1}{s_2-s_1} \pmod n
$$

- Có được $k$ rồi thì ta sẽ có thể tìm lại được giá trị khóa bí mật $d$ như sau :
$$
d\equiv\frac{s_1.k-z_1}{r}\pmod n
$$

Script khai thác :

from pwn import process, remote
from ecdsa.ecdsa import curve_256, generator_256
from hashlib import sha256
from sage.all import *
from base64 import b64encode, b64decode
from json import loads, dumps
from Crypto.Util.number import bytes_to_long

# io = process(["python3", "chall.py"])
io = remote("67.223.119.69", 5009)

G = generator_256
n = G.order()

io.recvline()

x, y = eval(io.recvline().decode().split(": ")[1])
p = curve_256.p()
a = curve_256.a()
b = curve_256.b()
E = EllipticCurve(GF(p), [a, b])
P = E(x, y)

msg1 = b64encode(b"aling")
z1 = bytes_to_long(sha256(b64decode(msg1)).digest())
io.sendlineafter(b"Option : ", b"1")
io.sendlineafter(b"Enter your message: ", msg1)
io.sendlineafter(b"Enter your nonce: ", b"YWxpbmc=")
sig1 = eval(io.recvline().decode().strip())
r1 = int(sig1["r"], 16)
s1 = int(sig1["s"], 16)

msg2 = b64encode(b"alinh")
z2 = bytes_to_long(sha256(b64decode(msg2)).digest())
io.sendlineafter(b"Option : ", b"1")
io.sendlineafter(b"Enter your message: ", msg2)
io.sendlineafter(b"Enter your nonce: ", b"YWxpbmd=")
sig2 = eval(io.recvline().decode().strip())
r2 = int(sig2["r"], 16)
s2 = int(sig2["s"], 16)

assert r1 == r2
k = ((z1 - z2) * pow((s1 - s2), -1, n)) % n
d = ((s1 * k - z1) * pow(r1, -1, n)) % n

io.sendlineafter(b"Option : ", b"2")
io.sendlineafter(b"Private key : ", str(d).encode())

recv = io.recvuntil(b"Very nice , here is your flag : ")
flag = io.recvline()
print(flag.decode().strip())

:::success
**FLAG : KCSC{no_more_byte_\x00_today}**
:::

# umama

Source code :

import socket
import threading
import time
import random
# from flag import FLAG
FLAG = b"KCSC{fake_flag}"
# =========================================================================
# I. LCG - Linear Congruential Generator
# =========================================================================
class LCG:
    def __init__(self, seed=None):
        self.M = 3287099835290195791649721107570004318267582246774226300213811649423225012170212287749142020192530464259481640735325781154239321190173754611921808393447501266888056440801327249770117062004226214495561535681369100056816111927528166402933420016083242583498654107351130511963025469986264222148916890724787070272803001
        self.A = 2894777803559679218352190554394546666288076241619396764815133803772055992385941101609673369526743001851311268818989398042025043757099501509707445437248873549911623395016719427960022056683203263457712425937702117698191301068614729419207159556006174347883149816514548460625672181804096655842375751872041822338728496
        self.C = 122
        self.seed = int(random.getrandbits(512)) % self.M if seed is None else seed % self.M
        
    def _next_seed(self):
        self.seed = (self.A * self.seed + self.C) % self.M
        return self.seed

    def uniform(self, min_val, max_val):
        normalized = self._next_seed() / self.M
        return min_val + normalized * (max_val - min_val)

# =========================================================================
# II. Uma Musume - Race Stats
# =========================================================================
class UmaMusume:
    def __init__(self, name, speed=50, stamina=50, skill_factor=50):
        self.name = name
        self.speed = speed
        self.stamina = stamina
        self.skill_factor = skill_factor
        self.odds = 0.0
        self.current_pos = 0.0
        self.current_speed = speed

    def update_position(self, lcg_gen, track_length):
        race_progress = self.current_pos / track_length
        stamina_drain = max(0, race_progress - 0.7)
        drain_reduction = self.stamina / 100.0
        speed_modifier = 1 - (stamina_drain * (1.5 - drain_reduction))
        self.current_speed = max(self.speed * 0.4, self.speed * speed_modifier)
        skill_multiplier = 2.5 if race_progress > 0.7 else 1.0
        random_boost = lcg_gen.uniform(0.95, 1.05 + self.skill_factor * 0.01 * skill_multiplier)
        micro_random = lcg_gen.uniform(0.99, 1.01)
        step_speed = self.current_speed * micro_random + random_boost
        self.current_pos += step_speed
        return step_speed

# =========================================================================
# III. Race Engine
# =========================================================================
class Race:
    def __init__(self, uma_list, track_length, lcg_gen):
        self.umas = uma_list
        self.track_length = track_length
        self.lcg_gen = lcg_gen
        self.max_steps = 1000

    def start_race(self):
        for uma in self.umas:
            uma.current_pos = 0.0
        step_count = 0
        race_over = False
        while not race_over and step_count < self.max_steps:
            step_count += 1
            for uma in self.umas:
                uma.update_position(self.lcg_gen, self.track_length)
                if uma.current_pos >= self.track_length:
                    race_over = True
        results = sorted(self.umas, key=lambda uma: uma.current_pos, reverse=True)
        return results

# =========================================================================
# IV. Betting System
# =========================================================================
class Betting:
    INITIAL_BALANCE = 10000.0
    FLAG_PRICE = 100000.0

    def __init__(self, umas, lcg_gen):
        self.umas = umas
        self.lcg_gen = lcg_gen
        self.balance = self.INITIAL_BALANCE
        self.current_bets = {}
        self.current_odds = {}

    def _calculate_odds(self):
        total_power = sum(u.speed + u.stamina + u.skill_factor for u in self.umas)
        self.current_odds = {}
        for uma in self.umas:
            uma_power = uma.speed + uma.stamina + uma.skill_factor
            base_odds = total_power / uma_power
            random_factor = self.lcg_gen.uniform(0.8, 1.2)
            uma.odds = max(1.5, base_odds * random_factor * 0.5)
            self.current_odds[uma.name] = uma.odds

    def show_odds(self):
        self._calculate_odds()
        msg = "\n" + "="*60 + "\n"
        msg += f"💰 WALLET: {self.balance:,.2f} Yen\n"
        msg += "-"*60 + "\n"
        msg += "📊 CURRENT ODDS:\n"
        for i, uma in enumerate(self.umas):
            msg += f"  [{i + 1:2d}] {uma.name:25s} | 1 to {uma.odds:6.2f} x\n"
        msg += "="*60 + "\n"
        return msg

    def place_bet(self, uma_index, amount):
        self.current_bets = {}
        try:
            uma_index = int(uma_index) - 1
            amount = float(amount)
        except:
            return False, "Invalid input"

        if not (0 <= uma_index < len(self.umas)):
            return False, f"Index must be 1 to {len(self.umas)}"

        if amount <= 0 or amount > self.balance:
            return False, "Invalid bet amount"

        uma_name = self.umas[uma_index].name
        self.balance -= amount
        self.current_bets[uma_name] = amount
        msg = f"\n✅ BET PLACED: {amount:,.2f} Yen on {uma_name}\n"
        msg += f"📉 Remaining: {self.balance:,.2f} Yen\n"
        return True, msg

    def process_winnings(self, winning_uma_name):
        total_winnings = 0.0
        msg = "\n" + "="*60 + "\n"
        msg += "🏆 RACE RESULTS 🏆\n"
        msg += "-"*60 + "\n"

        for uma_name, bet_amount in self.current_bets.items():
            winning_odds = self.current_odds.get(uma_name, 0)
            if uma_name == winning_uma_name:
                winnings = bet_amount * winning_odds
                self.balance += winnings
                total_winnings += winnings
                msg += f"🎉 WINNER! {uma_name}\n"
                msg += f"   Bet: {bet_amount:,.2f} Yen × {winning_odds:.2f} = +{winnings:,.2f} Yen\n"
            else:
                msg += f"❌ LOST: {uma_name} - {bet_amount:,.2f} Yen\n"

        msg += "-"*60 + "\n"
        msg += f"💵 TOTAL RETURN: +{total_winnings:,.2f} Yen\n"
        msg += f"💰 NEW BALANCE: {self.balance:,.2f} Yen\n"
        msg += "="*60 + "\n"
        return msg

# =========================================================================
# V. Socket Server
# =========================================================================
class CTFServer:
    def __init__(self, host='0.0.0.0', port=1337):
        self.host = host
        self.port = port
        self.server = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        self.server.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)

    def send(self, conn, msg):
        try:
            conn.sendall((msg + '\n').encode())
        except:
            pass

    def recv(self, conn, timeout=30):
        conn.settimeout(timeout)
        try:
            return conn.recv(1024).decode().strip()
        except:
            return None

    def handle_client(self, conn, addr):
        print(f"[+] Client connected: {addr}")
        
        umas = [
            UmaMusume("Special Week"),
            UmaMusume("Silence Suzuka"),
            UmaMusume("Gold Ship"),
            UmaMusume("Mejiro McQueen"),
            UmaMusume("Tokai Teio"),
            UmaMusume("Rice Shower"),
            UmaMusume("Symboli Rudolf"),
            UmaMusume("Kitasan Black"),
            UmaMusume("Satono Diamond"),
            UmaMusume("Daiwa Scarlet"),
        ]

        lcg_gen = LCG(seed=int(time.time() * 1000))
        betting_system = Betting(umas, lcg_gen)
        track_length = 500.0

        self.send(conn, "="*60)
        self.send(conn, "🌸 UMA MUSUME - CTF BETTING GAME 🌸")
        self.send(conn, f"Goal: Earn {betting_system.FLAG_PRICE:,.2f} Yen to buy the FLAG")
        self.send(conn, f"Start: {betting_system.INITIAL_BALANCE:,.2f} Yen")
        self.send(conn, "="*60)

        while True:
            self.send(conn, "\n" + "="*60)
            self.send(conn, f"💰 CURRENT BALANCE: {betting_system.balance:,.2f} Yen")
            self.send(conn, "-"*60)
            self.send(conn, "[1] 🏇 Start Race (Place Bet)")
            self.send(conn, "[2] 🏳️ Buy CTF Flag (100,000 Yen)")
            self.send(conn, "[3] 🚪 Exit Game")
            self.send(conn, "="*60)

            choice = self.recv(conn)
            if not choice:
                break

            if choice == '1':
                self.send(conn, betting_system.show_odds())
                self.send(conn, f"Uma Index [1-10] or 0 to cancel: ")
                uma_index = self.recv(conn)
                if not uma_index or uma_index == '0':
                    continue

                self.send(conn, "Amount to bet: ")
                amount = self.recv(conn)
                if not amount:
                    continue

                success, msg = betting_system.place_bet(uma_index, amount)
                self.send(conn, msg)

                if success:
                    race = Race(umas, track_length, lcg_gen)
                    results = race.start_race()
                    winning_name = results[0].name

                    self.send(conn, "\n" + "="*60)
                    self.send(conn, f"🥇 WINNER: {winning_name}")
                    self.send(conn, "🏁 RACE FINISHED - STANDINGS 🏁")
                    for rank, uma in enumerate(results):
                        if rank == 0:
                            self.send(conn, f"  #{rank + 1}: **{uma.name}**")
                        else:
                            self.send(conn, f"  #{rank + 1}: {uma.name}")
                    self.send(conn, "="*60)

                    self.send(conn, betting_system.process_winnings(winning_name))

            elif choice == '2':
                if betting_system.balance >= betting_system.FLAG_PRICE:
                    betting_system.balance -= betting_system.FLAG_PRICE
                    self.send(conn, "\n" + "="*60)
                    self.send(conn, "🎉 CONGRATULATIONS! 🎉")
                    self.send(conn, "="*60)
                    self.send(conn, f"🚩 FLAG: {FLAG}")
                    self.send(conn, f"💰 Remaining Balance: {betting_system.balance:,.2f} Yen")
                    self.send(conn, "="*60 + "\n")
                    break
                else:
                    need = betting_system.FLAG_PRICE - betting_system.balance
                    self.send(conn, f"\n❌ NOT ENOUGH MONEY!")
                    self.send(conn, f"   You need: {need:,.2f} more Yen")
                    self.send(conn, f"   Current: {betting_system.balance:,.2f} Yen")
                    self.send(conn, f"   Target:  {betting_system.FLAG_PRICE:,.2f} Yen\n")

            elif choice == '3':
                self.send(conn, "\n👋 Thank you for playing! Sayonara!")
                break
            else:
                self.send(conn, "⚠️ Invalid choice! Please try again.")

        conn.close()
        print(f"[-] Client disconnected: {addr}")

    def start(self):
        self.server.bind((self.host, self.port))
        self.server.listen(5)
        print(f"[*] Server listening on {self.host}:{self.port}")

        try:
            while True:
                conn, addr = self.server.accept()
                thread = threading.Thread(target=self.handle_client, args=(conn, addr))
                thread.daemon = True
                thread.start()
        except KeyboardInterrupt:
            print("\n[*] Server shutting down...")
        finally:
            self.server.close()

if __name__ == "__main__":
    server = CTFServer(host='0.0.0.0', port=1337)
    server.start()

>Source code khá là dài nên mình sẽ cố gắng tóm tắt lại cách mà nó đang thực hiện.

Đầu tiên, ta có một **class LCG** với các thông số đã được chọn từ trước. Class này đóng vai trò làm bộ sinh số giả ngẫu nhiên cho toàn bộ Challenge này. Nếu như bạn chưa biết nó hoạt động như thế nào thì hiểu đơn giản nó là một hàm sinh ra các chuỗi số có công thức là :
$$
s_{i+1}\equiv A.s_i+C\pmod{M}
$$
>với đầu vào $s_0$ là seed.

Điều ta cần phải quan tâm tới là hàm `uniform` ở trong class này :

def uniform(self, min_val, max_val):
    normalized = self._next_seed() / self.M
    return min_val + normalized * (max_val - min_val)

Nó có tác dụng là chuyển đổi một số nguyên ngẫu nhiên có giá trị lớn (từ hàm LCG) thành một số thực nằm trong phạm vi mà ta mong muốn. Các class và hàm ở bên dưới sẽ có sử dụng đến hàm `uniform` nên ta cần lưu ý.

Tiếp theo là **class UmaMusume**. Về cơ bản thì nó có vai trò là đối tượng mô phỏng các nhân vật đua ngựa, lưu trữ thông tin nhân vật và chứa logic tính toán sự di chuyển của ngựa trong từng bước chạy. Mỗi con ngựa khi mới được khởi tạo thì sẽ có các chỉ số giống như nhau :

def __init__(self, name, speed=50, stamina=50, skill_factor=50)

Nhưng ở trong hàm `update_position` thì có đoạn :

random_boost = lcg_gen.uniform(0.95, 1.05 + self.skill_factor * 0.01 * skill_multiplier)
micro_random = lcg_gen.uniform(0.99, 1.01)

Mỗi khi một con ngựa di chuyển 1 bước, Server sẽ có 2 lần gọi `_next_seed()` của bộ LCG. Và cũng có thể nói là chỉ số và tỉ lệ thắng của từng con ngựa khi này lại đang có phần phụ thuộc vào bộ sinh số giả ngẫu nhiên LCG kia.

Tiếp đến là **class Race**. Class này cũng là đang mô phỏng cách mà cuộc đua diễn ra, từ lúc xuất phát cho tới kết thúc. Nhìn chung là không điều gì mà ta cần lưu ý ở trong class này.

Kế đến là **class Betting**. Class này đóng vai trò làm nhà cái và cũng là nơi làm lộ ra các thông tin quan trọng liên quan đến các state của LCG. Cụ thể hơn là trong hàm `_calculate_odds` :

def _calculate_odds(self):
    # Tổng sức mạnh của 10 con ngựa. Vì chỉ số bằng nhau (150), tổng là 1500.
    total_power = sum(u.speed + u.stamina + u.skill_factor for u in self.umas)
    
    self.current_odds = {}
    for uma in self.umas:
        # Sức mạnh từng con là 150. Base Odds = 1500 / 150 = 10.0
        uma_power = uma.speed + uma.stamina + uma.skill_factor
        base_odds = total_power / uma_power
        
        # Bug ở đây: Gọi LCG để tạo hệ số ngẫu nhiên
        random_factor = self.lcg_gen.uniform(0.8, 1.2)
        
        # Công thức cuối: Odds = 10.0 * random * 0.5 = 5.0 * random
        uma.odds = max(1.5, base_odds * random_factor * 0.5)
        self.current_odds[uma.name] = uma.odds

Hàm này đóng vai trò tính toán tỉ lệ đặt cược cho từng con ngựa và sẽ in ra tỉ lệ đó cho ta. Điều đáng chú ý là tỷ lệ cược bạn nhìn thấy trên màn hình **tỷ lệ thuận** trực tiếp với số ngẫu nhiên **random_factor** mà LCG vừa sinh ra. Công thức ở đây là :
$$
Odds\approx 5.0\times RNG
$$

Với mỗi lần chọn option `[1] 🏇 Start Race (Place Bet)` thì hàm `_calculate_odds` sẽ được gọi để tính Odds cho từng con ngựa, cụ thể ở đây là $10$ con, nên hàm `_next_seed()` sẽ bị gọi $10$ lần.

Ngoài hàm đó ra thì ta sẽ còn có thêm các hàm tính toán tiền đặt cược và sẽ trả về hoặc bớt đi số tiền mà ta đang có (vốn ban đầu là $10000$ Yên), tùy vào kết quả cuộc đua. Giá tiền của Flag sẽ là $100000$ Yen, và ta sẽ phải chơi sao để có thể kiếm được đủ tiền để mua Flag.

Cuối cùng là **class CTFServer**. Tại đây thì ta sẽ biết được tên của $10$ con ngựa. Cùng với đó là lỗ hỏng lớn nhất của Challenge này :

lcg_gen = LCG(seed=int(time.time() * 1000))

Theo code định nghĩa hàm LCG như đã nói ở trên thì seed của ta sẽ có giá trị là một số nguyên lớn dài khoảng $512$ bits nếu như lúc khởi tạo LCG ta không truyền vào giá trị seed nào cả. Tuy nhiên ở đây thì Server đã sử dụng seed chính là thời gian tại thời điểm lúc mới connect tới Server (tính bằng mili-giây). Đó chính là lỗ hỏng lớn nhất của Challenge này, vì ta biết thời gian thực hiện kết nối, và ta có thể đoán được giá trị này với sai số rất nhỏ (chỉ vài trăm mili-giây do độ trễ mạng). Đây là cơ sở cho tấn công Brute-force Seed theo thời gian.

Vậy ta sẽ thực hiện quá trình khai thác này như thế nào ?

- Đầu tiên, ta sẽ lấy thời gian hiện tại ($t$) ngay lúc kết nối tới Server.
- Sau đó, sử dụng option `[1] 🏇 Start Race (Place Bet)` để in ra danh sách tỷ lệ cược ban đầu. Tới đây, ta sẽ tạo một vòng lặp thử các giá trị seed từ $t-2s$ đến $t+2s$.
- Với mỗi seed giả giả, ta sẽ khởi tạo một class LCG cục bộ (giống hệt với Server) và sẽ thử tính toán các giá trị Odds đầu tiên xem có khớp với số liệu Server gửi về không.
- Nếu khớp thì ta đã tìm ra Seed chính xác.
- Khi này ta chỉ cần dùng Seed vừa tìm được, chạy hàm Race cục bộ (code giống với Server) và xem con ngựa nào về nhất thì "All-in" vào nó thôi :smiling_imp:.
- Nếu chưa đủ 100k thì ta sẽ lặp lại quy trình cho tới khi đủ thì thôi.

Script khai thác :

from pwn import *
import time
import re

class LCG:
    def __init__(self, seed=None):
        self.M = 
        self.A = 
        self.C = 
        self.seed = int(seed) % self.M if seed is not None else 0
        
    def _next_seed(self):
        self.seed = (self.A * self.seed + self.C) % self.M
        return self.seed

    def uniform(self, min_val, max_val):
        normalized = self._next_seed() / self.M
        return min_val + normalized * (max_val - min_val)

class UmaMusume:
    def __init__(self, name, speed=50, stamina=50, skill_factor=50):
        self.name = name
        self.speed = speed
        self.stamina = stamina
        self.skill_factor = skill_factor
        self.odds = 0.0
        self.current_pos = 0.0
        self.current_speed = speed

    def update_position(self, lcg_gen, track_length):
        race_progress = self.current_pos / track_length
        stamina_drain = max(0, race_progress - 0.7)
        drain_reduction = self.stamina / 100.0
        speed_modifier = 1 - (stamina_drain * (1.5 - drain_reduction))
        self.current_speed = max(self.speed * 0.4, self.speed * speed_modifier)
        skill_multiplier = 2.5 if race_progress > 0.7 else 1.0
        random_boost = lcg_gen.uniform(0.95, 1.05 + self.skill_factor * 0.01 * skill_multiplier)
        micro_random = lcg_gen.uniform(0.99, 1.01)
        step_speed = self.current_speed * micro_random + random_boost
        self.current_pos += step_speed
        return step_speed

class Race:
    def __init__(self, uma_list, track_length, lcg_gen):
        self.umas = uma_list
        self.track_length = track_length
        self.lcg_gen = lcg_gen
        self.max_steps = 1000

    def start_race(self):
        for uma in self.umas:
            uma.current_pos = 0.0
        step_count = 0
        race_over = False
        while not race_over and step_count < self.max_steps:
            step_count += 1
            for uma in self.umas:
                uma.update_position(self.lcg_gen, self.track_length)
                if uma.current_pos >= self.track_length:
                    race_over = True
        results = sorted(self.umas, key=lambda uma: uma.current_pos, reverse=True)
        return results

UMA_NAMES = [
    "Special Week", "Silence Suzuka", "Gold Ship", "Mejiro McQueen",
    "Tokai Teio", "Rice Shower", "Symboli Rudolf", "Kitasan Black",
    "Satono Diamond", "Daiwa Scarlet"
]

def get_fresh_umas():
    return [UmaMusume(name) for name in UMA_NAMES]

def sync_next_odds_generation(lcg_gen):
    temp_umas = get_fresh_umas()
    for uma in temp_umas:
        lcg_gen.uniform(0.8, 1.2)


context.log_level = 'info'
connect_time = time.time() 

# io = process(["python3", "chal_server.py"])
io = remote("67.223.119.69", 5008)

io.recvuntil(b'Exit Game')

print("Requesting Odds to leak RNG state...")
io.sendline(b'1')

odds_buffer = io.recvuntil(b'cancel:').decode()

# Parse Odds
server_odds = []
matches = re.findall(r'\|\s+1\s+to\s+(\d+\.\d+)', odds_buffer)
if matches:
    server_odds = [float(x) for x in matches]
    print(f"Captured Odds: {server_odds}")
else:
    print("Failed to parse odds from server.")


# Brute-force Seed
base_ms = int(connect_time * 1000)
found_seed = None
cracked_lcg = None

p = log.progress("Cracking Seed")

# Quét +/- 5000ms
for ms in range(base_ms - 5000, base_ms + 5000):
    test_lcg = LCG(ms)
    temp_umas = get_fresh_umas()
    total_power = sum(u.speed + u.stamina + u.skill_factor for u in temp_umas)
    
    match = True
    for i, uma in enumerate(temp_umas):
        uma_power = uma.speed + uma.stamina + uma.skill_factor
        base_odds = total_power / uma_power
        
        random_factor = test_lcg.uniform(0.8, 1.2)
        val = max(1.5, base_odds * random_factor * 0.5)
        
        if f"{val:.2f}" != f"{server_odds[i]:.2f}":
            match = False
            break
    
    if match:
        found_seed = ms
        cracked_lcg = test_lcg 
        p.success(f"Found Seed: {found_seed}")
        break
        
if not cracked_lcg:
    p.failure("Seed not found. Network delay might be weird.")

current_balance = 10000.0
TARGET_MONEY = 1000000.0 

while current_balance < TARGET_MONEY:
    print(f"-----Round Start | Balance: {current_balance:,.2f}-----")

    race_umas = get_fresh_umas()
    race_sim = Race(race_umas, 500.0, cracked_lcg)
    results = race_sim.start_race()
    
    winner_name = results[0].name
    winner_idx = UMA_NAMES.index(winner_name) + 1
    
    log.success(f"Predicted Winner: {winner_name} (Index: {winner_idx})")
    
    # Send Bet
    io.sendline(str(winner_idx).encode()) 
    io.recvuntil(b'bet:')                 
    
    bet_amount = int(current_balance)
    io.sendline(str(bet_amount).encode()) # All-in
    
    # Read Results & Parse New Balance
    result_text = io.recvuntil(b'Exit Game').decode()
    
    if "WINNER!" in result_text:
        print("Race won! Updating balance...")
    else:
        print("Something went wrong, check logic!")

    balance_match = re.search(r'NEW BALANCE:\s+([\d,]+\.\d+)', result_text)
    if balance_match:
        current_balance = float(balance_match.group(1).replace(',', ''))
    
    # Check Win Condition
    if current_balance >= 1000000:
        print("Buying Flag...")
        break
    
    # Prepare Next Round (Sync RNG)
    io.sendline(b'1') 
    io.recvuntil(b'cancel:') 
    
    log.info("Syncing RNG state for next round...")
    sync_next_odds_generation(cracked_lcg)

# Buy Flag
io.sendline(b'2')
flag_data = io.recvall(timeout=2).decode()

print(flag_data)

io.close()

:::success
**FLAG : KCSC{3m4m4}**
:::
>Thực ra mình nghĩ câu này vẫn có thể Revenge được, đơn giản chỉ cần không thêm bất cứ tham số nào lúc khởi tạo LCG thì có lẽ đây sẽ là câu khó!

# theMidnIghTMan

Source code :

from Crypto.Cipher import AES
import hashlib, os, time

class x3AES:
    def __init__(self, key1, key2, key3):
        self.key1 = hashlib.md5(key1).digest()
        self.key2 = hashlib.md5(key2).digest()
        self.key3 = hashlib.md5(key3).digest()
        self.secret = os.urandom(16)
    
    def pad(self, data, block_size):
        length = len(data)

        if length % block_size == 0:
            return data

        pad_len = block_size - (length % block_size)

        return data + bytes([pad_len]) * pad_len

    def encrypt(self, plaintext):
        padded_data = self.pad(plaintext, AES.block_size)
        iv = os.urandom(AES.block_size)              
                                    
        cipher1 = AES.new(self.key1, AES.MODE_OFB, iv)
        enc1 = cipher1.encrypt(padded_data)

        cipher2 = AES.new(self.key2, AES.MODE_CBC, self.secret)
        enc2 = cipher2.encrypt(enc1)

        cipher3 = AES.new(self.key3, AES.MODE_ECB)
        enc3 = cipher3.encrypt(enc2)

        return iv + enc3

    def decrypt(self, ciphertext):
        iv = ciphertext[:AES.block_size]
        enc3 = ciphertext[AES.block_size:]

        cipher3 = AES.new(self.key3, AES.MODE_ECB)
        dec3 = cipher3.decrypt(enc3)

        cipher2 = AES.new(self.key2, AES.MODE_CBC, self.secret)
        dec2 = cipher2.decrypt(dec3)

        cipher1 = AES.new(self.key1, AES.MODE_OFB, iv)
        dec1 = cipher1.decrypt(dec2)

        return dec1

class Challenge:
    def __init__(self):
        self.flag = b"KCSC{??????????????????????????????????????????}"
        self.key = os.urandom(9)
        self.key1 = self.key[:3]
        self.key2 = self.key[3:6]
        self.key3 = self.key[6:]
        self.cipher = x3AES(self.key1, self.key2, self.key3)
        self.banner = """
                           ;                                                              
                           ED.                                                            
                           E#Wi        L.                                                 
                       t   E###G.      EW:        ,ft t           .Gt .    .              
            ..       : Ej  E#fD#W;     E##;       t#E Ej         j#W: Di   Dt    GEEEEEEEL
           ,W,     .Et E#, E#t t##L    E###t      t#E E#,      ;K#f   E#i  E#i   ,;;L#K;;.
          t##,    ,W#t E#t E#t  .E#K,  E#fE#f     t#E E#t    .G#D.    E#t  E#t      t#E   
         L###,   j###t E#t E#t    j##f E#t D#G    t#E E#t   j#K;      E#t  E#t      t#E   
       .E#j##,  G#fE#t E#t E#t    :E#K:E#t  f#E.  t#E E#t ,K#f   ,GD; E########f.   t#E   
      ;WW; ##,:K#i E#t E#t E#t   t##L  E#t   t#K: t#E E#t  j#Wi   E#t E#j..K#j...   t#E   
     j#E.  ##f#W,  E#t E#t E#t .D#W;   E#t    ;#W,t#E E#t   .G#D: E#t E#t  E#t      t#E   
   .D#L    ###K:   E#t E#t E#tiW#G.    E#t     :K#D#E E#t     ,K#fK#t E#t  E#t      t#E   
  :K#t     ##D.    E#t E#t E#K##i      E#t      .E##E E#t       j###t f#t  f#t      t#E   
  ...      #G      ..  E#t E##D.       ..         G#E E#t        .G#t  ii   ii       fE   
           j           ,;. E#t                     fE ,;.          ;;                 :   
                           L:                       ,                                     
"""

    def print_banner(self):
        for line in self.banner.split("\n"):
            print(line)
            time.sleep(0.1)
    
    def main(self):
        prefix = b'Midnight is coming. Stay awake!!'
        print(prefix)

        while True:
            option = input("Enter your option:\n1. Encrypt\n2. Decrypt\n3. Get Flag\n> ")
            try:
                if option == "1":
                    plaintext = bytes.fromhex(input("Enter plaintext (hex): "))
                    ciphertext = self.cipher.encrypt(plaintext)
                    print("Ciphertext: ", ciphertext.hex())
                elif option == "2":
                    iv = bytes.fromhex(input("Enter IV (hex): "))
                    assert len(iv) == 16
                    ciphertext = bytes.fromhex(input("Enter ciphertext (hex): "))
                    plaintext = self.cipher.decrypt(iv + prefix + ciphertext)
                    print("Plaintext: ", plaintext.hex())
                elif option == "3":
                    key_input = bytes.fromhex(input("Enter the key (hex): "))
                    if key_input == self.key:
                        print("Flag:", self.flag.decode())
                    else:
                        print("Wrong key!")
                        break
                else:
                    break
            except:
                print("Don't pwn me!")
                break

if __name__ == "__main__":
    challenge = Challenge()
    challenge.print_banner()
    challenge.main()

Nhìn sơ qua Source code thì có thể thấy ngay đây là một Challenge AES với một vài điều rất thú vị. Cụ thể nó nằm ở hàm `encrypt` và `decrypt` của **class x3AES**. x3AES ở đây không phải là một dữ liệu được mã hóa AES ba lần, mà thay vào đó, dữ liệu sẽ được mã hóa bằng ba chế độ khác nhau của Block Cipher.

Trong hàm `encrypt` thì thứ tự mã hóa sẽ là :
$$
\text{OFB}\rightarrow\text{CBC}\rightarrow\text{ECB}
$$

CBC, ECB thì ta đã gặp nhiều rồi, còn chế độ OFB khá là hiếm gặp nên đây chính là sơ đồ mã hóa của chế độ OFB :

Có thể thấy vì đầu vào của OFB là một chuỗi IV bất kì nên sau khi mã hóa xong ta sẽ nhận được chuỗi `IV || enc3`. Mục đích là để dùng cho việc giải mã OFB. Còn đối với IV của CBC thì nó là chuỗi Secret đã được khai báo làm biến toàn cục nên nó sẽ không đổi đối với mỗi lần gọi hàm `encrypt`

Trong hàm `decrypt` thì thứ tự giải mã sẽ là :
$$
\text{ECB}\rightarrow\text{CBC}\rightarrow\text{OFB}
$$

Đó là về các hàm mã hóa và giải mã của **class x3AES**. Bây giờ ta sẽ xem cách Challenge hoạt động như thế nào. Đầu tiên, Server sẽ sinh ra một khóa gốc dài $9$ bytes và sẽ chia khóa này ra làm ba khóa con có độ dài bằng nhau là $3$ bytes. Mỗi khóa con này chính là khóa được dùng để làm khóa cho các chế độ Block Cipher như đã nói ở trên. Tất nhiên là các khóa này sẽ được băm qua hàm hash $MD5$ nên ta không cần phải quá lo lắng về độ dài của chúng.

Server sẽ cung cấp cho ta ba option chính là : Encrypt, Decrypt và GetFlag. Với option Encrypt thì không có gì để nó cả vì ta đã phân tích như ở trên rồi. Còn đối với option Decrypt thì có một chỗ mà ta cần phải lưu ý. Đó chính là :

prefix = b'Midnight is coming. Stay awake!!'
plaintext = self.cipher.decrypt(iv + prefix + ciphertext)

Option Decrypt sẽ yêu cầu ta cung cấp IV và chuỗi Ciphertext bất kì để giải mã. Tuy nhiên, Server sẽ cố tình thêm vào chuỗi **Prefix** ở trước chuỗi Ciphertext để giải mã chung. Tất nhiên là chuỗi **Prefix** này có độ dài là $32$ bytes nên ta không cần phải quá lo lắng về độ dài của chuỗi Ciphertext mà ta truyền vào. Vậy điều đó có ý nghĩa gì?

Nếu nhìn lại tên Challenge thì bạn có thể thấy một vài chữ được viết in hoa một cách bất thường. Và khi ghép chúng lại theo thứ tự thì bạn có được từ : **MITM**. Điều đó ám chỉ tới kỹ thuật Man in the Middle Attack đối với các mã hóa khối. Cùng với đó là việc các key của từng chế độ mã hóa tuy đã có băm bằng hàm $MD5$ nhưng trên thực tế chúng ban đầu cũng chỉ là một chuỗi byte có độ dài là $3$. Điều đó đồng nghĩa với việc không gian khóa lúc này chỉ vỏn vẹn có :
$$
2^{3\times 8}=2^{24}=16777216\text{ khả năng}
$$

Như vậy có thể thấy lỗ hỏng chính của bài này là ta có thể dùng MITM được. Nó nằm ở việc option Decrypt còn nhận thêm chuỗi **Prefix** để giải mã. Kết hợp với không gian khóa chỉ vỏn vẹn có $2^{24}$ khả năng thì ta sẽ hoàn toàn có thể tấn công brute-force và tìm lại từng khóa được. Và sau khi có được chuỗi khóa ban đầu thì ta chỉ cần gửi nó cho Server và sẽ nhận được Flag. Vậy thì ta sẽ khai thác cụ thể như thế nào.

## Recover Key1
Đầu tiên, ta sẽ tìm lại key1 dựa trên tính chất của OFB. Cụ thể, từ sơ đồ mã hóa trên ta có được mối quan hệ như sau :
$$
D_{OFB}(C)=C\oplus Keystream(key1, IV)
$$
>$C$ ở đây là giá trị đầu ra của hàm giải mã CBC

Hướng khai thác ở đây là :
- Gửi option Decrypt lần 1 : $IV_1$, Ciphertext rỗng (server sẽ chèn prefix). Nhận được Plaintext $P_1$.
- Gửi option Decrypt lần 2 : $IV_2$, Ciphertext rỗng (giống hệt trên). Nhận được Plaintext $P_2$. Vì Ciphertext đi vào Layer 3 và Layer 2 là như nhau (do prefix cố định), đầu ra của Layer 2 ($C_{L2}$) là giống nhau.

Ta có:
$$
P_1 = C_{L2} \oplus Keystream(key1, IV_1)$$

$$
P_2 = C_{L2} \oplus Keystream(key1, IV_2)
$$

XOR hai vế:
$$
P_1\oplus P_2 = Keystream(key1, IV_1) \oplus Keystream(key1, IV_2)
$$

Khi này ta chỉ cần brute-force key1 sao cho phương trình trên thỏa mãn là được. Vậy là đã tìm được key1.

## Recover Key3
Tiếp theo là ta sẽ tìm lại key3. Ta sẽ khai thác dựa vào tính chất ECB và cấu trúc **Prefix**. Cụ thể sau khi có key1, ta có thể tính được đầu ra của Layer 2 ($C_{L2}$), nó chính là Input của Layer 1.
$$
C_{L2}=D_{CBC, key2}(D_{ECB, key3}(Input))
$$

Hướng khai thác ở đây là :
- **Prefix** dài $32$ bytes = $2$ blocks. Ta chia chuỗi **Prefix** ra làm hai phần là $P_1, P_2$.
- Gửi ciphertext là $P_2$. Dữ liệu đi vào giải mã sẽ là :
$$
P_1 \ || \ P_2 \ || \ P_2
$$
- Gọi :
$$
\begin{cases}
I_1=D_{ECB, k3}(P_1)\\
I_2=D_{ECB, k3}(P_2)
\end{cases}
$$

- Dữ liệu đi vào CBC Decrypt sẽ có dạng là :
$$
I_1 \ || \ I_2 \ || \ I_2
$$
- Đầu ra CBC (sau khi đã loại bỏ lớp OFB bằng key1 tìm được ở bước 1) thì ta có :
$$
\begin{cases}
Block 1: O_1 = D_{k2}(I_1) \oplus Secret\\
Block 2: O_2 = D_{k2}(I_2) \oplus I_1\\
Block 3: O_3 = D_{k2}(I_2) \oplus I_2
\end{cases}
$$
- Xor hai block 2 và 3 lại ta có :
$$
O_2\oplus O_3 = [D_{k2}(I_2) \oplus I_1]\oplus [D_{k2}(I_2) \oplus I_2] = I_1 \oplus I_2
$$

$$
\Leftrightarrow O_2\oplus O_3 = I_1 \oplus I_2
$$

$$
\Leftrightarrow O_2 \oplus O_3 = D_{ECB, k3}(P_1) \oplus D_{ECB, k3}(P_2)
$$

Khi này ta chỉ cần brute-force key3 sao cho phương trình trên thỏa mãn là được. Vậy là đã tìm được key3.

## Recover Key2
Cuối cùng chỉ còn mỗi key2. Ý tưởng chính ở đây là ta sẽ lợi dụng hệ quả của việc chỉ dùng duy nhất một $\text{IV}=\text{Secret}$ đối với chế độ CBC trong suốt quá trình mã hóa và giải mã. Cụ thể sau khi có được key1 và key3, ta đã biết key1, key3. Ta tính được chính xác $I_1, I_2$.

Hướng khai thác ở đây là : Sử dụng lại giá trị $O_2$ thu được ở bước 2. Ta có:
$$
O_2 = D_{k2}(I_2) \oplus I_1
$$

$$
\Rightarrow D_{k2}(I_2) = O_2 \oplus I_1
$$

Khi này ta chỉ cần brute-force key2 sao cho phương trình trên thỏa mãn là được. Vậy là đã tìm được key2.

Sau khi tìm được đầy đủ các phần của key thì ta chỉ cần ghép chúng lại rồi gửi cho Server rồi lấy Flag thôi. Bài toán kết thúc !!!

Script khai thác :

from pwn import *
from Crypto.Cipher import AES
import hashlib
import itertools

AES_BLOCK_SIZE = 16
PREFIX = b'Midnight is coming. Stay awake!!' 
P1 = PREFIX[:AES_BLOCK_SIZE]
P2 = PREFIX[AES_BLOCK_SIZE:]

def md5_digest(key_bytes):
    return hashlib.md5(key_bytes).digest()

def get_keystream(k1_md5, iv, blocks):
    cipher_k1_ecb = AES.new(k1_md5, AES.MODE_ECB)
    keystream = b''
    iv_block = iv
    for _ in range(blocks):
        iv_block = cipher_k1_ecb.encrypt(iv_block)
        keystream += iv_block
    return keystream


def connect_and_recv_banner():
    try:
        io = remote("67.223.119.69", 5011)
        io.recvuntil(b'Midnight is coming. Stay awake!!')
        io.recvuntil(b'> ') 
        return io
    
    except Exception as e:
        print(f"{e}")
        return None

def interact_decrypt(io, iv_hex, ciphertext_hex):
    io.sendline(b'2')
    io.recvuntil(b'Enter IV (hex): ')
    io.sendline(iv_hex)
    io.recvuntil(b'Enter ciphertext (hex): ')
    io.sendline(ciphertext_hex)
    
    io.recvuntil(b'Plaintext: ')
    plaintext_hex = io.recvline().strip().decode()
    io.recvuntil(b'> ') 
    return plaintext_hex

def get_decryption_data(io):
    iv_a = os.urandom(AES_BLOCK_SIZE)
    P_A_hex = interact_decrypt(io, iv_a.hex().encode(), b'')
    P_A_padded = bytes.fromhex(P_A_hex)
    P_A = P_A_padded[:32] 

    iv_b = os.urandom(AES_BLOCK_SIZE)
    P_B_hex = interact_decrypt(io, iv_b.hex().encode(), b'')
    P_B_padded = bytes.fromhex(P_B_hex)
    P_B = P_B_padded[:32]
    
    P_XOR_PB = bytes([a ^ b for a, b in zip(P_A, P_B)])
    
    return iv_a, iv_b, P_XOR_PB, P_A

def solve_key1(iv_a, iv_b, P_XOR_PB):
    print("Brute-force Key1")
    
    for key_bytes in itertools.product(range(256), repeat=3):
        k1_candidate = bytes(key_bytes)
        k1_md5 = md5_digest(k1_candidate)
        
        keystream_a = get_keystream(k1_md5, iv_a, 2)
        keystream_b = get_keystream(k1_md5, iv_b, 2)
            
        keystream_xor = bytes([a ^ b for a, b in zip(keystream_a, keystream_b)])
        
        if keystream_xor == P_XOR_PB:
            print(f"Found Key1 : {k1_candidate.hex()}")
            return k1_candidate, k1_md5
    
    print("Not found Key1.")
    return None, None

def solve_key3(io, k1_md5, iv_a, P_A):
    print("Brute-force Key3")

    keystream_a = get_keystream(k1_md5, iv_a, 2)
    C_L2 = bytes([a ^ b for a, b in zip(P_A, keystream_a)])
    
    P_trippled_hex = interact_decrypt(io, iv_a.hex().encode(), P2.hex().encode())
    P_trippled_padded = bytes.fromhex(P_trippled_hex)
    P_trippled = P_trippled_padded[:48] 
    
    keystream_trippled = get_keystream(k1_md5, iv_a, 3) 
    O_trippled = bytes([a ^ b for a, b in zip(P_trippled, keystream_trippled)])

    O2 = O_trippled[AES_BLOCK_SIZE : 2*AES_BLOCK_SIZE]
    O3 = O_trippled[2*AES_BLOCK_SIZE : 3*AES_BLOCK_SIZE]
    O2_XOR_O3 = bytes([a ^ b for a, b in zip(O2, O3)])
    
    for key_bytes in itertools.product(range(256), repeat=3):
        k3_candidate = bytes(key_bytes)
        k3_md5 = md5_digest(k3_candidate)
        
        cipher_k3 = AES.new(k3_md5, AES.MODE_ECB)
        Dec_P1 = cipher_k3.decrypt(P1)
        Dec_P2 = cipher_k3.decrypt(P2)
        
        Dec_P1_XOR_Dec_P2 = bytes([a ^ b for a, b in zip(Dec_P1, Dec_P2)])
        
        if Dec_P1_XOR_Dec_P2 == O2_XOR_O3:
            print(f"Found Key3 : {k3_candidate.hex()}")
            return k3_candidate, k3_md5, Dec_P1, Dec_P2, O2, O3
            
    print("Not found Key3.")
    return None, None, None, None, None, None

def solve_key3_internal(k1_md5, O2, O3):
    """Hàm nội bộ cho Bước 2."""
    O2_XOR_O3 = bytes([a ^ b for a, b in zip(O2, O3)])
    
    for key_bytes in itertools.product(range(256), repeat=3):
        k3_candidate = bytes(key_bytes)
        k3_md5 = md5_digest(k3_candidate)
        
        cipher_k3 = AES.new(k3_md5, AES.MODE_ECB)
        Dec_P1 = cipher_k3.decrypt(P1)
        Dec_P2 = cipher_k3.decrypt(P2)
        
        Dec_P1_XOR_Dec_P2 = bytes([a ^ b for a, b in zip(Dec_P1, Dec_P2)])
        
        if Dec_P1_XOR_Dec_P2 == O2_XOR_O3:
            log.success(f"Key3 được tìm thấy: {k3_candidate.hex()}")
            return k3_candidate, k3_md5, Dec_P1, Dec_P2
            
    log.failure("Không tìm thấy Key3.")
    return None, None, None, None

def solve_key2_and_secret(k3_md5, Dec_P1, Dec_P2, O1, O3):
    print("Brute-force Key2")

    Dec_k2_I2_target = bytes([a ^ b for a, b in zip(O3, Dec_P2)])
    
    for key_bytes in itertools.product(range(256), repeat=3):
        k2_candidate = bytes(key_bytes)
        k2_md5 = md5_digest(k2_candidate)
        
        cipher_k2 = AES.new(k2_md5, AES.MODE_ECB)
        Dec_k2_I2_candidate = cipher_k2.decrypt(Dec_P2)
        
        if Dec_k2_I2_candidate == Dec_k2_I2_target:
            print(f"Found Key2 : {k2_candidate.hex()}")
            
            Dec_k2_I1 = cipher_k2.decrypt(Dec_P1)
            secret_key = bytes([a ^ b for a, b in zip(O1, Dec_k2_I1)])
            
            print(f"Found Secret : {secret_key.hex()}")
            return k2_candidate, k2_md5, secret_key
            
    print("Not found Key2.")
    return None, None, None



def solve():
    io = connect_and_recv_banner()
    if not io:
        return

    iv_a, iv_b, P_XOR_PB, P_A = get_decryption_data(io)
    
    k1, k1_md5 = solve_key1(iv_a, iv_b, P_XOR_PB)
    if not k1:
        io.close()
        return
        
    keystream_a = get_keystream(k1_md5, iv_a, 2)
    C_L2 = bytes([a ^ b for a, b in zip(P_A, keystream_a)])
    O1 = C_L2[:AES_BLOCK_SIZE]


    P_trippled_hex = interact_decrypt(io, iv_a.hex().encode(), P2.hex().encode())
    P_trippled_padded = bytes.fromhex(P_trippled_hex)
    P_trippled = P_trippled_padded[:48] 
    
    keystream_trippled = get_keystream(k1_md5, iv_a, 3) 
    O_trippled = bytes([a ^ b for a, b in zip(P_trippled, keystream_trippled)])
    O2 = O_trippled[AES_BLOCK_SIZE : 2*AES_BLOCK_SIZE]
    O3 = O_trippled[2*AES_BLOCK_SIZE : 3*AES_BLOCK_SIZE]

    k3, k3_md5, Dec_P1, Dec_P2 = solve_key3_internal(k1_md5, O2, O3)
    if not k3:
        io.close()
        return

    k2, k2_md5, secret = solve_key2_and_secret(k3_md5, Dec_P1, Dec_P2, O1, O3)
    if not k2:
        io.close()
        return

    full_key = k1 + k2 + k3
    print(f"Found Last Key : {full_key.hex()}")
    
    io.sendline(b'3')
    io.recvuntil(b'Enter the key (hex): ')
    io.sendline(full_key.hex().encode())
    
    io.recvuntil(b'Flag: ')
    flag = io.recvline().strip().decode()
    print(f"FLAG: {flag}")
    
    io.close()

if __name__ == "__main__":
    solve()

:::success
**FLAG : KCSC{a_formal_gift_to_honor_you_e5bb1bb281165c0}**
:::

# 五六七

Source code :

from Crypto.Util.number import isPrime
import random

FLAG = open('flag.txt', 'rb').read()
p = int(input("Choose p > "))
if not isPrime(p) or p.bit_length() < 512:
    print("Fail")
    exit(1)
x = random.getrandbits(128)

def f(x):
    res = 0
    for i in range(7):
        if i==5: continue
        res += pow(i, x, p)
        res %= p
    return res

res = f(x)
print(res)
guess = int(input("guess x = "))
if guess == x:
    print(f"Here is your flag: {FLAG}")    
else:
    print('false')                                      

Nhìn sơ qua Source code thì ta có thể thấy đây là một dạng giải phương trình mũ Modulo khi mà ta được cho biết phương trình có dạng là :
$$
f(x)\equiv1+2^x+3^x+4^x+6^x\pmod{p}
$$

Server sẽ cho phép ta nhập một giá trị $p$ vào và sẽ tính toán giá trị : $res\equiv f(x_0)\pmod{p}$ với $x_0$ là số nguyên bí mật dài khoảng $128$ bits. Bây giờ nhiệm vụ của ta là tìm lại được $x_0$ và gửi cho Server để lấy được Flag. Vậy thì ta nên giải phương trình trên như thế nào.

Nếu phân tích kĩ phương trình $f(x)$ trên thì ta có thể viết lại như sau :
$$
f(x)\equiv1+2^x+3^x+(2^x)^2+2^x.3^x\pmod{p}
$$

Nếu như ta có thể tìm được một giá trị $k$ sao cho :
$$
2^k\equiv 3\pmod{p}
$$

thì khi đó :
$$
f(x)\equiv1+2^x+(2^k)^x+(2^x)^2+2^x.(2^k)^x\pmod{p}
$$

$$
\Leftrightarrow f(x)\equiv1+2^x+(2^x)^k+(2^x)^2+(2^x)^{k+1}\pmod{p}
$$

Đặt $a=2^x$ ta có :
$$
f(x)\equiv1+a+a^k+a^2+a^{k+1}\pmod{p}
$$

Khi kết nối tới Server thì ta sẽ nhận lại giá trị $\text{res}=f(x_0)$. Khi đó ta có :
$$
f(x_0)\equiv\text{res}\equiv1+a+a^k+a^2+a^{k+1}\pmod{p}
$$

$$
\Leftrightarrow a^{k+1}+a^k+a^2+a+1-res\equiv 0\pmod{p}
$$

Bây giờ chỉ cần giải phương trình trên là ta sẽ thu về các nghiệm $a_i$ và khi đó ta sẽ có phương trình :
$$
2^{x_0}\equiv a_i\pmod{p}
$$

Bây giờ chỉ cần tính logarithm rời rạc thôi là có thể tìm được $x_0$ rồi!!!. Nhưng đó là một cách đi chưa hoàn toàn đầy đủ. Tại sao lại như vậy? Đơn giản là vì khi chọn số nguyên tố $p$ có dạng $p=2^k-3$ thì khi đó ta sẽ có :
$$
p-1=2^k-4=4.(2^{k-2}-1)
$$

Với yêu cầu là $p$ phải là số nguyên tố có độ dài ít nhất là $512$ bits nên $k$ khi này sẽ có điều kiện là : $k>512$. Với điều kiện như vậy thì rõ ràng $p-1=4.(2^{k-2}-1)$ không phải lúc nào là một Smooth number đủ tốt (hay nói đúng hơn là gần như không có một số Smooth number nào đủ tốt đối với dạng $p-1$ như thế này).
> Từ "**đủ tốt**" ở đây theo ý của mình là $p-1$ là một **B-smooth**, với $B<2^{64}$. Đó là điều kiện lý tưởng để ta có thể thực hiện thuật toán Pohlig-Hellman để giải các bài toán DLP (Logarithm rời rạc) một cách dễ dàng.

Điều đó khiến cho việc giải bài toán Logarithm rời rạc đối với phương trình trên là điều không thể vì sẽ luôn có những thừa số nguyên tố lớn hơn $2^{64}$. Vậy thì ta sẽ phải giải bài này như thế nào?

Tất nhiên là vẫn còn có cách, nếu bạn để ý thì giá trị bí mật $x_0$ của ta chỉ có độ dài là khoảng $128$ bits.

x = random.getrandbits(128)

Thế thì rõ ràng là ta không nhất thiết phải đi tính Pohlig-Hellman với toàn bộ thừa số nguyên tố của $p-1$, mà thay vào đó chỉ cần tính với các thừa số nguyên tố nhỏ hơn sao cho khi CRT lại các nghiệm đó ta được một số vừa đủ $128$ bits là được rồi.

Vậy thì ý tưởng bây giờ là ta sẽ đi tìm một số nguyên tố $p$ có dạng là $p=2^k-3$, với $k>512$ sao cho factor của $p-1$ sẽ chứa nhiều các thừa số nguyên tố nhỏ hơn $2^{64}$. Không nhất thiết là tất cả thừa số phải bé hơn $2^{64}$, chỉ cần có càng nhiều thừa số trong factor đó bé hơn $2^{64}$ là được rồi. Sau một hồi tìm kiếm thì mình có tìm được một số $p$ thỏa mãn điều kiện trên như sau :


Đó chính là $p=2^{694}-3$, với $k=694$ thỏa mãn điều kiện trên của ta. Bây giờ ta chỉ cần lấy những thừa số nguyên tố nhỏ đầu tiên và tính DLP với từng thừa số và dùng CRT để ghép lại các nghiệm thôi là xong rồi. Bài toán kết thúc !!!

Script khai thác :

from sage.all import *
from pwn import process, remote
from Crypto.Util.number import isPrime
from math import prod, isqrt
from factordb.factordb import FactorDB

# io = process(["python3", "chall.py"])
io = remote("67.223.119.69", 5012)

for i in range(690, 700):
    p = 2**i - 3
    if isPrime(p):
        k = i
        break

io.sendlineafter(b"Choose p > ", str(p).encode())
res = int(io.recvline().decode().strip())

f = FactorDB(p-1)
f.connect()
factors = f.get_factor_list()


target_size = 2**130
current_prod = 1
list_small_factors = []
for fac in factors:
    fac = int(fac)
    if fac > 10**12: 
        continue
    
    list_small_factors.append(fac)
    current_prod *= fac
    if current_prod > target_size:
        break

a = PolynomialRing(Zmod(p), "a").gen()
f = 1 + a + a**2 + a**k + a**(k+1) - res
roots = f.roots(multiplicities=False)

g = GF(p)(2)

real_x = None

for r in roots:
    a = GF(p)(r)
    print(f"[*] a = {a}...")
    
    remainders = []
    moduli = []
    
    try:
        for q in list_small_factors:
            cofactor = (p - 1) // q
            g_sub = power(g, cofactor)
            h_sub = power(a, cofactor)
            
            xi = discrete_log(h_sub, g_sub, ord=q)
            
            remainders.append(xi)
            moduli.append(q)

        x_part = crt(remainders, moduli)
        smooth_order = prod(moduli)
        
        if pow(2, x_part, p) == a:
            real_x = x_part
            print(f"\nFound x: {real_x}")
            break
        else:
            candidate = x_part + smooth_order
            if pow(2, candidate, p) == a:
                real_x = candidate
                print(f"\nFound x: {real_x}")
                break

    except ValueError:
        print("[-] Cannot DLP for this root :(")
        continue
        
    if real_x: break

if real_x:
    io.sendlineafter(b"guess x = ", str(real_x).encode())
    print(io.recvall().decode())
else:
    print("[-] Fail!!")

Tuy nhiên cần phải bổ sung thêm rằng : Code trên vẫn sẽ có lúc cho ra kết quả sai bởi vì giá trị $g=2$ không phải là **primitive_root** của $p=2^{694}-3$. Ta có thể kiểm chứng điều này như sau :

from factordb.factordb import FactorDB

def get_multiplicative_order(g, p):
    f = FactorDB(p - 1)
    f.connect()
    factors_info = f.get_factor_list() 
    
    order = p - 1
    
    unique_factors = set(factors_info) 
    
    for q in unique_factors:
        while order % q == 0 and pow(g, order // q, p) == 1:
            order = order // q
            
    return order

p = 2**694 - 3
g = 2
order = get_multiplicative_order(g, p)
assert pow(g, order, p) == 1
assert order == (p-1) // 3

Order của $g=2$ khi này chỉ bằng $\frac{p-1}{3}$. Điều đó dẫn tới việc thực tế $2^x$ chỉ có thể sinh ra được một không gian có số lượng phần tử chỉ bằng $\frac{1}{3}$ so với **primitive_root** gốc của $p$. Khi đó, nếu như giá trị $a_i$ mà ta giải được từ phương trình :
$$
a^{k+1}+a^k+a^2+a+1-res\equiv 0\pmod{p}
$$

không nằm trong khoảng không gian được sinh ra bởi $2^x$ trong Modulo $p$ đó thì phương trình :
$$
2^x\equiv a_i\pmod{p}
$$

sẽ vô nghiệm.

Tất nhiên ta không cần phải quá lo lắng về điều đó là bởi vì giá trị $a_i$ mà ta giải được có xác suất khoảng $33.3\%$ sẽ nằm trong không gian sinh bởi $2^x$. Xác suất này cũng khá cao nên ta có thể thử spam connect lại nếu như không tìm được giá trị $x$ đối với giá trị $a_i$ của lần connect đó. Thế là xong rồi!

>**UPDATE** : Sau một lúc suy nghĩ thì mình đã tìm thấy được một lời giải sẽ chắc chắn cho ra Flag $100\%$. Đó chính là chọn $p=2^{850}-3$. Với giá trị $p$ này, ta sẽ có $2$ là **primitive_root** của $p$ và bản thân $p$ này có factor của $p-1$ là có rất nhiều số nguyên bé hơn $2^{64}$ như sau :

**Và tất nhiên rồi, ta đã tìm được một Intend Solution một cách hoàn chỉnh!!!**

:::success
**FLAG : KCSC{why_do_you_choose_crypto?}**
:::

# e

Source code :

flag = ???


def hash(msg: bytes) -> bytes:
    msg = list(map(int, bin(int((msg).hex(), 16))[2:]))
    g = 35835915874844867368919076489095108449946327955754392558399825615420669938882575126094039892345713852759 
    n = 36
    for b in msg:
        n = (g * (n + int(3 if b else 6))) & ((1 << 512) - 1)
    return (n)
print(hash(flag), len(flag))
# 4733050325257322080995332543647525767201053028813565191926008882515250832618947947748792937964480829322550895675027130098198538016461241391725598109040829 28

Nhìn sơ qua Source code thì ta có thể thấy đây là một bài toán có hàm hash là một hàm khá giống với **[FNV hash](https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function#)**. Cụ thể hơn thì hàm hash này sẽ được tính bằng cách duyệt từng bit của $msg$ truyền vào và tính :

n = (g * (n + int(3 if b else 6))) & ((1 << 512) - 1)

Hay bằng một cách trực quan hơn, ta có thể biểu diễn hàm hash trên về dưới dạng một đa thức tuyến tính như thế này :
$$
H\equiv 36g^L + \sum^{L-1}_{i=0}[(6 - 3b_i).g^{L-i}]\pmod{2^{512}}
$$
>với $L$ là độ dài tính theo bits của $msg$ truyền vào hàm hash.

Biến đổi một chút thì ta có như sau :
$$
H\equiv 36g^L + 6.\sum^{L-1}_{i=0}(g^{L-i}) - 3.\sum^{L-1}_{i=0}(b_i . g^{L-i})\pmod{2^{512}}
$$

$$
\Leftrightarrow 3.\sum^{L-1}_{i=0}(b_i . g^{L-i})\equiv 36g^L + 6.\sum^{L-1}_{i=0}(g^{L-i}) - H\pmod{2^{512}}
$$

$$
\Leftrightarrow \sum^{L-1}_{i=0}(b_i . g^{L-i})\equiv [36g^L + 6.\sum^{L-1}_{i=0}(g^{L-i}) - H]\times 3^{-1}\pmod{2^{512}}
$$

Đặt $S=[36g^L + 6.\sum^{L-1}_{i=0}(g^{L-i}) - H]\times 3^{-1}$ và $C_i=g^{L-i}$ ta có :
$$
\Leftrightarrow \sum^{L-1}_{i=0}(b_i . C_i)\equiv S\pmod{2^{512}}
$$

Rõ ràng, đây chính là bài toán Modular Subset Sum Problem. Để giải được bài toán này thì ta sẽ thiết lập một Lattice như sau :
$$
\mathbf{B}=
\begin{pmatrix}
1 & 0 & \cdots & 0 & 0 & N.C_1 \\
0 & 1 & & & 0 & N.C_2 \\
\vdots & & \ddots & & \vdots & \vdots \\
0 & & & 1 & 0 & N.C_L \\
0 & 0 & \cdots & 0 & 0 & N.2^{512} \\
\frac{1}{2} & \frac{1}{2} & \cdots & \frac{1}{2} & \frac{1}{2} & N.S
\end{pmatrix}_{(L+2)\times(L+2)}
$$

Trong đó : $N>\sqrt{L}$, ở đây mình cho nó bằng Modulo luôn

>Giải thích qua lý do vì sao ta lại xây dựng được Lattice như trên : Cụ thể thì nó nằm trong **[paper này.](https://informatika.stei.itb.ac.id/~rinaldi.munir/Kriptografi/2022-2023/Makalah2/Makalah2-Kriptografi-2023%20(25).pdf)** :smile:

Giảm cơ sở Lattice trên bằng thuật toán LLL hoặc BKZ, ta có thể hy vọng rằng thuật toán sẽ tìm một vector $\mathbf{t}$ có dạng :
$$
\mathbf{t}=(b_1,b_2,...,b_L,k,-1)
$$

Để tính : $\mathbf{tB}=\mathbf{x}$ với vector $\mathbf{x}$ là vector ngắn nhất của Lattice sau khi giảm cơ sở có dạng là :
$$
\mathbf{x}=(b_1-\frac{1}{2}, b_2-\frac{1}{2},...,b_L-\frac{1}{2}, -\frac{1}{2}, 0)
$$

Tuy nhiên, vì Flag của ta có độ dài là $28$ bytes $=$ $224-1$ bits (Bỏ bit đầu tiên của chuỗi Flag khi đổi sang nhị phân) nên $L$ khi này sẽ bằng $223$. Điều đó sẽ dẫn đến việc ma trận $\mathbf{B}$ là một ma trận vuông có cấp là $n=225$. Đó là một con số rất lớn khiến cho việc giảm cơ sở Lattice khi này không tìm được vector ngắn nhất như ta mong muốn. Vậy thì ta phải làm sao ?

Như ta biết rằng Flag của ta bắt đầu bằng chuỗi `b"KCSC{"` và kết thúc bằng `b"}"`. Điều đó đã cho ta biết thêm một lượng thông tin về các giá trị bit $b_i$. Với việc ta đã biết được $6$ bytes của Flag nên ta có thể giảm xuống được thêm $7+8\times5=47$ số lượng hàng cột của ma trận $\mathbf{B}$ ban đầu. Cùng với đó ta biết thêm được rằng : Trong $22$ bytes còn lại của Flag thì tất cả đều bắt đầu bằng bit $0$ khi ta đổi từng byte đó sang dạng bit. Điều đó lại giúp cho ta giảm thêm được $22$ số lượng hàng cột nữa. Khi này, ma trận $\mathbf{B}'$ mới của ta sẽ là một ma trận vuông cấp $n=225-47-20=158$.

Khi đó, ta có thể sử dụng thuật toán BKZ với `block_size=17` để có thể giảm cơ sở Lattice trên và hy vọng rằng có thể tìm được vector nhỏ nhất thỏa mãn yêu cầu.

Script khai thác :

from sage.all import *
import binascii

H = 4733050325257322080995332543647525767201053028813565191926008882515250832618947947748792937964480829322550895675027130098198538016461241391725598109040829
g = 35835915874844867368919076489095108449946327955754392558399825615420669938882575126094039892345713852759 
MOD = 2**512
len_flag = 28
L = 8 * len_flag - 1 # 223 bits 

S = ((36 * pow(g, L, MOD) + 6 * sum([pow(g, L-i, MOD) for i in range(L)]) - H) * pow(3, -1, MOD)) % MOD
N_ = 2**512

prefix_bytes = b"KCSC{"
prefix_bits = list(map(int, bin(int((prefix_bytes).hex(), 16))[2:]))
prefix_value = 0
for i in range(len(prefix_bits)):
    bi = prefix_bits[i]
    C_i = pow(g, L - i, MOD)
    prefix_value = (prefix_value + bi * C_i) % MOD

suffix_bytes = b"}"
suffix_bits = [0] + list(map(int, bin(int((suffix_bytes).hex(), 16))[2:]))    #Đoạn này quên thêm cái bit 0 vào đầu nên bảo sao mãi chưa giải ra :(
suffix_value = 0
for i in range(len(suffix_bits)):
    bi = suffix_bits[i]
    C_i = pow(g, len(suffix_bits) - i, MOD) 
    suffix_value = (suffix_value + bi * C_i) % MOD

S_new = (S - prefix_value - suffix_value) % MOD

middle_indices = []
for i in range(39, L - 8):
    if (i - 39) % 8 != 0:
        middle_indices.append(i)

num_vars = len(middle_indices) 

# Ở đây ta sẽ nhân 2 vào cơ sở Lattice ban đầu nhằm loại bỏ đi các phần tử 1/2 để Lattice này là một Lattice trên trường số nguyên
As = Matrix(ZZ, [(N_ * pow(g, L - i, MOD) * 2) for i in middle_indices] + [N_ * MOD * 2] + [N_ * S_new * 2]).T
I = identity_matrix(num_vars) * 2 
vec1 = Matrix(ZZ, [0 for _ in range(num_vars)])
vec2 = Matrix(ZZ, [1 for _ in range(num_vars + 1)]) 
vec3 = Matrix(ZZ, [0 for _ in range(num_vars + 1)]).T

M = I.stack(vec1)        
M = M.augment(vec3)       
M = M.stack(vec2)         
M = M.augment(As)        
M = M.dense_matrix()

M = M.BKZ(block_size=17) 

for vector in M:
    vec = list(vector)
    if vec[-1] == 0:
        vals = vec[:num_vars]
        if all(val in [1, -1] for val in vals):
            
            def recover_flag(found_vals, inverted=False):
                target_bit = 1 if not inverted else -1
                
                middle_bits_raw = [1 if v == target_bit else 0 for v in found_vals]
                
                full_middle_bits = []
                idx = 0
                for _ in range(22): 
                    full_middle_bits.append(0)
                    for _ in range(7):
                        full_middle_bits.append(middle_bits_raw[idx])
                        idx += 1

                total_bits = [0] + prefix_bits + full_middle_bits + suffix_bits
                
                try:
                    s = "".join(map(str, total_bits))
                    n_val = int(s, 2)
                    flag = binascii.unhexlify(format(n_val, f'0{len_flag*2}x'))
                    if b"KCSC" in flag:
                        print(f"\nFlag : {flag.decode()}")
                        return True
                except:
                    pass
                return False

            if recover_flag(vals, inverted=False): break
            if recover_flag(vals, inverted=True): break

:::success
**FLAG : KCSC{Th1s_1s_4_fl4g_f0r_y0u}**
:::
>Nhìn chung ý tưởng giải thì nó rõ ràng như thế rồi nhưng mình lại code ngố quá nên trong suốt thời gian giải diễn ra mà mình làm mãi chưa ra :(

>Nhận xét một cách công tâm thì đây có lẽ là câu hay nhất giải TTV lần này :smile: