<h1 style="text-align:center;">ImaginaryCTF 2025</h1>



>Trong hai ngày từ ngày 6/9/205 - 8/9/2025, mình đã cùng team **Universea** tham gia giải đấu này và đạt được vị trí **top 7**.
Đây là một giải CTF rất hay, mình đã học được nhiều thứ từ các challenge và cả bạn của mình, sau đây là write up các challenge mà mình cho là hay và học được nhiều thứ.
++**Note:**++ Các kiến thức được mình viết dưới đây đều dựa theo ý hiểu của mình là chính nên nếu bạn đọc thấy khó chịu thì thông cảm cho mình.


# Challenges
## scalar-division (100pts) - 124 solves
:::spoiler **chal.sage**

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

:::
Challenge này chỉ có **một** dòng mà thôi, nhưng ta có thể tóm tắt các ý chính như sau:

- Challenge chuyển **Flag** thành một số nguyên rồi sau đó ép nó thành $x_P$ của một điểm $P = (x_P, y_P)$ nào đó thuộc đường cong $E$.
- Sau đó tính điểm $Q$ theo công thức $Q = [n]P$ với $n|\#E$ tức $n$ là một ước của $\#E$.
- Trả về điểm $Q$ và giá trị $n$, Challenge yêu cầu ta khôi phục lại điểm $P$ để có Flag.

Đường cong mà Challenge sử dụng là:
$$E:y^2 = x^3 + 5x+7 \\\mod p$$

Với $\#E = 2^3\times 17 \times 59 \times 457 \times 617 \times 1123 \times 1279\times \dots$

> Giá trị $n$ được sử dụng là $457$.

---

Ta biết rằng phương trình $[n]P = Q$ có $\text{gcd}(n, \#E)$ giá trị $P$ thỏa mãn, vì vậy ta có đến $457$ giá trị $P$ thỏa mãn và Flag của ta sẽ nằm trong số đó, vậy ta tìm chúng như thế nào?

++**Tính chất**++: Nếu $[n]P=Q$ thì tồn tại các giá trị $P'$ cũng thỏa mãn $[n]P'=Q$ với công thức:
$$P' = P+T$$

Với $T$ là các điểm thuộc $\text{ker}([n])$ i.e các điểm thỏa mãn $[n]T=\mathcal{O}$.

++**Chứng minh**++: Vì $[n]T = \mathcal{O}$ nên ta có:
$$[n]P' = [n](P + T) = [n]P + [n]T = Q + \mathcal{O} = Q$$

> Vì vậy để giải Challenge này, ta cần tìm một điểm $P$ sao cho $[n]P=Q$ trước, sau đó lấy $P + T$ đến khi nào được Flag thì thành công.

:::spoiler **script**

from string import printable
from Crypto.Util.number import *

p = 0xbde3c425157a83cbe69cee172d27e2ef9c1bd754ff052d4e7e6a26074efcea673eab9438dc45e0786c4ea54a89f9079ddb21
E = EllipticCurve(GF(p), [5, 7])
order = 0xbde3c425157a83cbe69cee172d27e2ef9c1bd754ff052d4e7de4b95b45c27d829309eeaf9136e53bf43445eaaeaa1a450708

# điểm Q thỏa mãn [n]P = Q
target_x = 0x686be42f9c3f431296a928c288145a847364bb259c9f5738270d48a7fba035377cc23b27f69d6ae0fad76d745fab25d504d5
n = 457
Q = E.lift_x(ZZ(target_x))
assert Q * (order//n) == 0 # order của Q là #E/457, tức không chứa 457 

# tính điểm P sao cho [n]P = Q
P = Q * pow(n, -1, (order//n))

# tính giá trị T là một điểm bất kỳ trong kernel([n])
T = E.random_element() * (order//n)
assert T * n == 0

# recover flag
for i in range(n):
    P_ = P + i*T
    flag = long_to_bytes(int(P_.x()))
    if all([i in printable.encode() for i in flag]):
        print(flag)
        break

:::spoiler Flag
**ictf{mayb3_d0nt_m4ke_th3_sca1ar_a_f4ctor_0f_the_ord3r}**
:::

## clcg (486pts) - 13 solves
:::spoiler **chall․py**

from Crypto.Util.number import getPrime
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secrets import randbelow, token_bytes
import json

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

class CLCG:
    
    def __init__(self, length):
        self.p = getPrime(256)
        self.A = [randbelow(self.p) for _ in range(length)]
        self.C = [randbelow(self.p) for _ in range(length)]
        self.X = [randbelow(self.p) for _ in range(length)]
    
    def rand(self):
        self.X = [(a * x + c) % self.p for a, x, c in zip(self.A, self.X, self.C)]
        return int.to_bytes((sum(self.X) % self.p) >> 192, 8)

NUM_HINTS = 36

clcg = CLCG(8)
data = dict()
data['p'] = clcg.p
data['A'] = clcg.A
data['hints'] = [clcg.rand().hex() for _ in range(NUM_HINTS)]

key = clcg.rand() + clcg.rand()
iv = token_bytes(16)
cipher = AES.new(key, AES.MODE_CBC, iv=iv)
data['iv'] = iv.hex()
data['ct'] = cipher.encrypt(pad(flag.encode(), 16)).hex()

print(json.dumps(data))

:::
:::spoiler **out.txt**

{"p": 94049999023160394359193340596870035925823725883211957738536443562820739705973, "A": [76126868043017160832856842373172648902916768954599129453079237129360499313962, 51678063238025220765110997632457232008690291015284851943390286753761356618085, 39951246837359548967076410927801192227206173471122762601131749536543881895894, 70177641962115922254704297313258463035117857381063778172279054947185070674555, 8965746873558080241774868583662572625777968944700179075444591752295251433019, 18264173557905911967621630361892236094943582222251094570083149172799074502122, 89443846084550423623113263446537118923446048303566300633045504499134907063874, 22447648158071671082292968419944584387297771409436486066846586421863893217866], "hints": ["6c7845832305b0f7", "536eb82826e8fb6e", "0618bc0e05c7f7a2", "6b72b47bf053cf3c", "93af5e045de215c8", "85eefe2f368fd7db", "c4e1289552c47522", "abe6def585ea6f83", "c7205019297ce664", "b28e6c0185a53064", "73de008d886c6bac", "1f2d6314e34baa97", "43c501fdb8d4eaac", "caf3d534a073b11a", "2fd29199b539d41f", "4f950585dd988f7d", "6da83a92ccc5f4ef", "a950dc01e84d962f", "4ac0c34d69737b78", "8f6f238836852b06", "8e1610cb8f437093", "69e3a0b94fd8e431", "cccc2ab0054b2594", "c99ca4e37d3b870f", "a2ab7316a5e29c28", "bf36a1fbd7295e2f", "b3060040e68374a9", "5f6dbb47e912b39e", "cc9d32c184f6f108", "b7f2cba86f670685", "9c40cc1a16bc0886", "0a6549bc259b9517", "a0580410e0ccf8c0", "51423cad0d189d47", "07bcc42a5d1e012f", "924020d9ba594fb7"], "iv": "c12413411b390dc2f4229df29bf7edd2", "ct": "c99dc5fabed54ffb6bfb71fcf803216492f63c506a88e461501f0c68468fe0cb12a4ab48cbd0f4d187ffbdf97ba117fa9970425fc56d4dc6c5c7bf11c6fde1da"}

:::

||Một Challenge khó 💀 nếu không có sự trợ giúp của bạn bè thì bài này quá sức với mình.||

++**Mô tả**:++ Đây là một Challenge về **truncated LCG** nhưng thay vì dùng LCG chuẩn nó sử dụng một phiên bản LCG là **tổng** của nhiều LCG nhỏ hơn.

---

Tiến hành phân tích Class **CLCG** - cách mà Challenge tạo giá trị ngẫu nhiên:

class CLCG:
    
    def __init__(self, length):
        self.p = getPrime(256)
        self.A = [randbelow(self.p) for _ in range(length)]
        self.C = [randbelow(self.p) for _ in range(length)]
        self.X = [randbelow(self.p) for _ in range(length)]
    
    def rand(self):
        self.X = [(a * x + c) % self.p for a, x, c in zip(self.A, self.X, self.C)]
        return int.to_bytes((sum(self.X) % self.p) >> 192, 8)

Ta thấy rằng nó sử dụng **length** LCG - ở đây là $8$ LCG với mỗi LCG sử dụng một bộ $(a_i,c_i,x_i)$ khác nhau, ta đặt chúng là:
$$A = [a_0, a_1, a_2,\dots,a_7]$$

$$C = [c_0, c_1, c_2,\dots,c_7]$$

$$X= [x_{0}, x_{1}, x_{2},\dots,x_{7}]$$

Hàm `rand()` tạo các state như sau:

$$\text{State} = \sum_{i=0}^{7} (a_i \cdot x_i + c_i)\mod p$$

Sau đó cắt $\text{State}$ lấy $64$ bit đầu, chuyển về bytes là được $8$ bytes ngẫu nhiên.

> Mỗi lần gọi `rand()` thì giá trị $X$ sẽ được cập nhật lại.

---

Challenge gọi hàm `rand()` $36$ lần để cho ta $36$ giá trị `hints` và sau đó gọi `rand()` $2$ lần tiếp để tạo $16$ bytes ngẫu nhiên làm key mã hóa Flag.

data['hints'] = [clcg.rand().hex() for _ in range(NUM_HINTS)]

key = clcg.rand() + clcg.rand()

> Vì vậy ta cần tận dụng được $36$ giá trị `hint` và list `A` mà Challenge cho.

---

Đặt công thức của `hints` là:
$$ h_j = \left ( \sum_{i=0}^{7} (a_i \cdot x_i + c_i)\right ) \times 2^{192} + k_j \hspace{3mm}|\hspace{3mm}j\in \left\{0\dots35 \right\}$$

> Với $k_j$ là phần bit bị mất

Với các ẩn $(x_i,c_i,k_j)$ ta khai triển $36$ phương trình trên như sau:

from sage.all import *

NUM_HINTS = 36
length = 8

packet = {"p": , 
          "A": , 
          "hints": , 
          "iv": "", 
          "ct": ""}

p = packet["p"];A = packet["A"];hints = packet["hints"]; hints = [int(i, 16) for i in hints];iv = packet["iv"];ct = packet["ct"]

C = [(f"c{_}") for _ in range(length)]
X = [(f"x{_}") for _ in range(length)]
k = [(f"k{_}") for _ in range(NUM_HINTS)]
VARS = PolynomialRing(GF(p), C + X + k).gens()

C, X, k = VARS[:length], VARS[length:2*length], VARS[2*length:]

eqs = []
for i in range(NUM_HINTS):
    X = [(a * x + c) for a, x, c in zip(A, X, C)]
    f = sum(X) - (hints[i] << 192) - k[i]
    eqs.append(f)

with open("output.txt", "w") as f:
    for i in eqs:
        f.write(str(i) + "\n")

Sẽ được một hệ $36$ phương trình như sau:

Sử dụng `groebner_basis()` để rút gọn:

G = Ideal(eqs).groebner_basis()

with open("output.txt", "w") as f:
    for i in G:
        f.write(str(i) + "\n")

Ta được $36$ phương trình mới:

> Chú ý vào $27$ phương trình cuối, ta thấy rằng chúng chỉ chứa toàn biến $k_j$ mà thôi, ví dụ:

k0 + 27927257145553081926906602112991604227777823090462724303146903352367131282206*k27 + 71817381072852909733882940126645120598480233259413115258918547379589782106492*k28 + 1111897954700476738671615393439388375889465103563054635456663023325814657131*k29 + 23773593233102204347157818339075072748566679328274544313636516760770374461150*k30 + 35287966769237184060368861425269417282976037116221672676334264431759067812761*k31 + 80259737450221814115088386153448166228683716760301370861379134955367709372175*k32 + 74909637881949099499986374945251357831859801578422577582500931759876234616272*k33 + 28024385996887506210953532157327831651726647152030799389126857003110690840913*k34 + 33088138588137300803757231734032184757334500144157971933645955585116153674791*k35 + 60813323254666881042159384206872919567635361680088342524627087018968522166571
(...)

Biết được $k_j<2^{192}$, ta tiến hành lập hệ và sử dụng `solve_linear_mod` để giải hệ phương trình modulo trên:

#...
G = Ideal(eqs).groebner_basis()

kx = [var(f"k{_}") for _ in range(NUM_HINTS)]
k0, k1, k2, k3, k4, k5, k6, k7, k8, k9, k10, k11, k12, k13, k14, k15, k16, k17, k18, k19, k20, k21, k22, k23, k24, k25, k26, k27, k28, k29, k30, k31, k32, k33, k34, k35 = kx

e = []
for i in G[-27:]:
    tmp = str(i)
    e.append([eval(tmp) == 0, p])
bounds = {k : (0, 2**192) for k in kx}
ks = solve_linear_mod(e, bounds) # https://github.com/nneonneo/pwn-stuff/blob/main/math/solvelinmod.py

print(f"{ks = }")

Tính được $36$ giá trị $k_j$:

ks = {k0: 5981260177186558279546968945331437220356844688889786121977, k1: 5179778159674895774763231598979253912777585537805410076018, k2: 614456212661956723898598139068750771975143567648636132717, k3: 2151416485657224745312846443282203922484989141879630871461, k4: 6198977440728050004887415244036143957975088135520475767549, k5: 2059565528466530265615861643228286234885246265588710743086, k6: 707434202790597324488824417615986766481112458440186569248, k7: 3126279442311578998593980560293123468455012735882636609337, k8: 1337770375426748679712734073808109852824680557756735189220, k9: 3161597783070193016239275584505896860039657020669494867851, k10: 1202147688777862142818180101064846260905856527597155505648, k11: 2844623377541565218676070593163247856541390410991302586312, k12: 3385177004493051713331445891224036806854302414884021394882, k13: 2176370113508183210961847065754954312562053552171041419896, k14: 4933813265475441690647346706284040483228901311840950883740, k15: 1850265215776421434342885238351831399398714339045178343912, k16: 2595779473132055317559127199467980878220164844258001005475, k17: 198364505819308433188901596684490588247398424808253350148, k18: 4844016471730801935636111076751189450139246123786836752185, k19: 2310019499480707673052674151645740135341234441953538646790, k20: 4059597307170550233931908354627092261659917093919724380338, k21: 966852461665170649154525922935491503597522853874168769988, k22: 2746588872495481055324247055752054054774912247755878308438, k23: 4628425585622206718479483604805231884168890131410587153767, k24: 3050468759352805066952360918669428088678914740221949748209, k25: 1780798573169136494282478577696873017803808909702054157518, k26: 6289816685001571177161197807075258822370446385932711692496, k27: 3936622010740898874599314275829770770199760017164734126082, k28: 558780046225582501690474100123875612341591180519921316725, k29: 965874091963596741109936132844298417970007225488586049563, k30: 5484053757286043532742605421887241131576006291461741821159, k31: 5517477470486776366412756373385432317539357743280141089454, k32: 6095059078902334586611418953782419759770207499093472095212, k33: 3599518154109169091214390328469425292213610693219527691128, k34: 4065010740312731357947389258699782113725146860588851772233, k35: 2383775218746466718155396260612769301757675625300588222361}

---

Có $k_j$ ta thay vào $36$ phương trình của `hints` và tạo thêm $2$ phương trình dùng để tạo `key` cho AES là:

$$\text{Keys}_{(1,2)} = \text{state}_j = \sum_{i=0}^{7} (a_i \cdot x_i + c_i)\hspace{3mm}|\hspace{3mm}j\in \left\{36,37 \right\}$$

Sau đó sử dụng `groebner_basis()` với $38$ phương trình trên, ta sẽ tìm được hai state tiếp theo:

from sage.all import *
from Crypto.Util.number import *
from Crypto.Cipher import AES

NUM_HINTS = 36
length = 8

# list
Ks = [...]
packet = {"p": , 
          "A": , 
          "hints": , 
          "iv": "", 
          "ct": ""}

p = packet["p"];A = packet["A"];hints = packet["hints"]; hints = [int(i, 16) for i in hints];iv = bytes.fromhex(packet["iv"]);ct = bytes.fromhex(packet["ct"])

C = [(f"c{_}") for _ in range(length)]
X = [(f"x{_}") for _ in range(length)]
S = [(f"s{_}") for _ in range(2)]

VARS = PolynomialRing(GF(p), C + X + S).gens()
C, X, S = VARS[:length], VARS[length:2*length], VARS[-2:]

C_ = [c for c in C]
X_ = [x for x in X]
S_ = [s for s in S]

Eqs = []
for i in range(36):
    X_ = [(a * x + c) for a, x, c in zip(A, X_, C_)]
    f = sum(X_) - ((hints[i] << 192) + Ks[i]) 
    Eqs.append(f)
for j in range(2):
    X_ = [(a * x + c) for a, x, c in zip(A, X_, C_)]
    f = sum(X_) - S_[j]
    Eqs.append(f)
    
G = Ideal(Eqs).groebner_basis()
with open("output.txt", "w") as f:
    for i in G:
        f.write(str(i) + "\n")


> Vậy là ta tìm được hai state tiếp theo của CLCG rồi, cắt lấy 64 bit đầu, làm key cho AES là giải mã được ciphertext.

:::spoiler **Script**
[**here**](https://drive.google.com/file/d/1uY8HjM4qAgE6SK4Mc1u8ttYKqlsLHaYh/view?usp=sharing)
:::spoiler **Flag**
**ictf{y3t_an07h3r_lcg_ch411_7b24ac314588057bfd4b70b10585a277}**
:::

## feistier-network (490pts) - 11 solves

:::spoiler **chal․py**

#!/usr/local/bin/python3
from Crypto.Hash import SHA256
from Crypto.Util.number import bytes_to_long, long_to_bytes
import random
from secrets import randbits
import base64
import os


secret_half = randbits(256)

def xor(bytes1,bytes2):
    return bytes(a ^ b for a, b in zip(bytes1, bytes2))

def readflag():
    try:
        flag = os.getenv("FLAG").encode('utf-8')
    except:
        print('the flag is missing please contact ictf admins')
        flag = b'ictf{fake_flag}'
    return flag



def keygen(seed):
    random.seed(seed) # chọn seed
    out = []
    for i in range(623):
        h = SHA256.new()
        h.update(long_to_bytes(secret_half ^ random.getrandbits(32)))
        out.append(h.digest())
    return out



def encryption_round(A,key):
    left,right = A[:32], A[32:]
    h = SHA256.new()
    h.update(xor(right,key))
    new_right = xor(left,h.digest())
    return right + new_right

def encrypt(message,keys):
    encrypted = message[:]
    assert(len(encrypted) == 64)
    for key in keys:
        encrypted = encryption_round(encrypted,key)
    return encrypted
    
    
    
def main():
    try:
        public_half = bytes_to_long(base64.b64decode(str(input("give me your best shot >:)\t"))))
        keys = keygen(public_half)
        flag = readflag().ljust(64, b'\x00')

        while(True):
            choice = int(input("1) print flag\n2) print custom message\n"))
            if (choice == 1):
                print(base64.b64encode(encrypt(flag,keys)).decode('utf-8'))
            elif (choice == 2):
                your_message = base64.b64decode(input("sure what's the message: ")).ljust(64,b'\x00')
                print(base64.b64encode(encrypt(your_message,keys)).decode('utf-8'))
            else:
                exit(1)
                
    except:
        print("don't try and break me (ノಠ益ಠ)ノ彡┻━┻")
        exit(1)
        

if __name__ == "__main__":
    main()

:::

++**Mô tả:**++ Một Challenge liên quan đến **feistel cipher**, điểm chú ý chính là nó cho ta chọn **seed** cho quá trình tạo **key**, liệu ta có thể khai thác điểm này như thế nào?

def keygen(seed):
    random.seed(seed) # ta được phép chọn seed
    out = []
    for i in range(11):
        h = SHA256.new()
        h.update(long_to_bytes(secret_half ^ random.getrandbits(32)))
        out.append(h.digest())
    return out

---

Ta biết rằng `feistel cipher` có tính đối xứng, tức quá trình mã hóa và giải mã giống hệt nhau chỉ cần đảo ngược key ở bước giải mã thôi:

ciphertext = Enc(message, key) 
message = Dec(ciphertext, key[::-1])

Ở hàm `keygen`, các key của ta là `Hash(secret_half ^ random.getrandbits(32)))`, tập trung vào phần `random.getrandbits(32)` vì đây là thứ ta có thể tác động được thông qua `seed`.

> Vì vậy để tác động đến các key, ta sẽ tìm cách thao túng các giá trị `getrandbits(32)` từ việc lựa chọn `seed` một cách hợp lý.

---

Ở hàm `main`, ta có hai lựa chọn là `encrypt(flag)` hoặc `encrypt(your_message)`, không có hàm `decrypt` nên ta cần phải lợi dụng hàm `encrypt` để giải mã flag nhờ tính đối xứng của `feistel cipher`:

while(True):
    choice = int(input("1) print flag\n2) print custom message\n"))
    if (choice == 1):
        print(base64.b64encode(encrypt(flag,keys)).decode('utf-8'))
    elif (choice == 2):
        your_message = base64.b64decode(input("sure what's the message: ")).ljust(64,b'\x00')
        print(base64.b64encode(encrypt(your_message,keys)).decode('utf-8'))
    else:
        exit(1)

++**Ý tưởng:**++ Vì chỉ được dùng hàm `encrypt` để giải mã, ta cần tìm một key mà khi giữ nguyên và khi đảo ngược lại phải giống nhau, tức `k == k[::-1]`. Bởi vì như đã đề cập ở trên thì bước giải mã của `feistel cipher` chỉ cần lật ngược key lại.

Vì thế ta cần tìm một `seed` mà tạo ra $623$ giá trị `getrandbits(32)` đối xứng dạng:

$$[r_0,r_1,r_2,...r_{310}, r_{311},r_{310},...,r_2,r_1,r_0]$$

Điều này nghe có vẻ bất khả thi, nhưng không. Ta hoàn toàn có thể tìm được một seed như thế mà mất chưa tới `10 giây`. Sử dụng tool [randcrack](https://github.com/Mistsuu/randcracks/tree/release/python_mt19937) của `mitstu`, ta làm như sau:

from secrets import randbits
import sys
sys.path.append("/mnt/c/vc/test/randcracks/python_mt19937")
sys.set_int_max_str_digits(10000)
from mt19937_crack import *


arr = [randbits(32) for i in range(311)]
arr = arr + [randbits(32)]  + arr[::-1]
print(arr == arr[::-1])

rndSolver = RandomSolver()
for i in range(len(arr)):
    rndSolver.submit_getrandbits32(arr[i])

rndSolver.init_seed_states()                    # Solving seed states before
rndSolver.accumulate_solve()                    # solving seed values helps
rndSolver.init_seed_finder(624 * 32)            # finding seed faster.
rndSolver.solve(force_redo=True)
print(f'seed = {rndSolver.get_seed()}')

Và tìm được một seed thỏa mãn là:

Có `seed` thì bước tiếp chỉ là gửi seed → `option 1` → nhận ciphertext của flag → gửi ciphertext cho `option 2` → nhận flag.

> **Chú ý**: trước khi gửi ciphertext cho `option 2` thì ta cần đảo 32 bytes đầu và 32 bytes cuối với nhau thì mới giải mã đúng được (tuân theo cấu trúc của feistel cipher thì trước khi in ra ciphertext thì ta cần có bước hoán 32 bytes đầu và 32 bytes cuối, nhưng ở challenge thì không có bước đó nên ta cần làm thủ công).

:::spoiler **Script**

from pwn import *
import sys
from base64 import *
from Crypto.Util.number import bytes_to_long, long_to_bytes

sys.set_int_max_str_digits(10000)

io = process(["python3", "test.py"])
seed = ""
seed = long_to_bytes(int(seed))
seed = b64encode(seed)

io.sendlineafter(b"give me your best shot >:)\t", seed)
io.sendlineafter(b"message\n", b"1"); flag = b64decode(io.recvline())
io.sendlineafter(b"message\n", b"2"); flag = b64encode(flag[len(flag)//2:] + flag[:len(flag)//2])
io.sendlineafter(b"sure what's the message: ", flag)

pt = b64decode(io.recvline())
FLAG = pt[len(pt)//2:] + pt[:len(pt)//2]
print(FLAG)

:::spoiler **Flag**
**ictf{57r1n65_4r3_h45h3d_bu7_1n736r4l5_4r3n7_v3ry_c00l_cpy7h0n}**
:::

## bigger-rsa (495pts) - 8 solves

:::spoiler **bigger_rsa․py**

from Crypto.Util.number import getPrime, bytes_to_long
import secrets

n = 32
e = 0x10001
N = 64

flag = b'ictf{REDACTED}'
flag = secrets.token_bytes((n * 63) - len(flag)) + flag

ps = [getPrime(512) for _ in range(n)]

m = 1
for i in ps:
    m *= i

nums = [CRT([1 + secrets.randbits(260) for _ in range(n)],ps) for __ in range(N)]
ct = pow(bytes_to_long(flag),e,m)
print(f"ct={ct}")
print(f"m={m}")
print(f"nums={nums}")

:::
::: spoiler **out.txt**
https://github.com/ImaginaryCTF/ImaginaryCTF-2025-Challenges/blob/main/Crypto/bigger-rsa/challenge/out.txt
:::

++**Mô tả:**++ Đây là một Challenge RSA sử dụng modulus rất lớn là $n=p_1.p_2...p_{32}$ với các $p_i$ khoảng `512` bit. Tiếp theo Challenge tính $64$ giá trị `nums` theo công thức:
$$
\begin{aligned}
\text{nums}_1 & = \text{CRT}([r_{1, 1}, r_{1, 2}, \dots, r_{1, 32}], [p_1, p_2, \dots, p_{32}]) \\\
\text{nums}_2 & = \text{CRT}([r_{2, 1}, r_{2, 2}, \dots, r_{2, 32}], [p_1, p_2, \dots, p_{32}]) \\\
\vdots \\\
\text{nums}_{64} &= \text{CRT}([r_{64, 1}, r_{64, 2}, \dots, r_{64, 32}], [p_1, p_2, \dots, p_{32}]) \\\
\end{aligned}
$$

Ở đây `CRT` là công thức của định lý thặng dư trung hoa và $r_{i,j}$ là các giá trị `260` bit ngẫu nhiên.

> Việc giải Challenge này gặp rất nhiều khó khăn vì số rất lớn, debug cũng rất chậm, vì vậy để có thể hình dung, ta sẽ lấy một ví dụ nhỏ với $m = p_1.p_2.p_3.p_4$ và $n$ giá trị $\text{nums}$.

Khai triển công thức `CRT` của một giá trị $\text{nums}_i$ bất kỳ ta được:
$$
\begin{aligned}
\text{nums}_i = \ & r_{i,1} \cdot (p_1.p_2.p_3) \cdot [(p_1.p_2.p_3) ^{-1} \mod p_4] \hspace{3mm} + r_{i,2} \cdot (p_1.p_2.p_4) \cdot [(p_1.p_2.p_4) ^{-1} \mod p_3] \hspace{3mm} + \\\
& r_{i,3} \cdot (p_2.p_3.p_4) \cdot [(p_2.p_3.p_4) ^{-1} \mod p_1] \hspace{3mm} + r_{i,4} \cdot (p_1.p_3.p_4)
\cdot [(p_1.p_3.p_4) ^{-1} \mod p_2]
\end{aligned}
$$

Khi ta mod phương trình trên với $p_1,p_2,p_3,p_4$ ta được:
$$
\begin{aligned}
\text{nums}_i & \equiv r_{i,1} \pmod {p_4} \\\
\text{nums}_i & \equiv r_{i,2} \pmod {p_3} \\\
\text{nums}_i & \equiv r_{i,3} \pmod {p_1} \\\
\text{nums}_i & \equiv r_{i,4} \pmod {p_2} \\\
\end{aligned}
$$

Ta biến đổi phương trình `đầu tiên` như sau:
$$
\begin{aligned}
& \text{nums}_i && + k_1\cdot p_4 && = r_{i,1} \\\
\Rightarrow \ & \text{nums}_i && + k_1 \cdot (m / (p_1.p_2.p_3)) &&= r_{i,1} \\\
\Rightarrow \ & \text{nums}_i \cdot(p_1.p_2.p_3) &&+ k_1\cdot m &&= r_{i,1} \cdot (p_1 . p_2 . p_3) \\\
\Rightarrow \ & \text{nums}_i \cdot q_4 &&+ k_1\cdot m &&= r_{i,1} \cdot q_4
\end{aligned}
$$

> Đặt $q_i = m/p_i$.

Ta có được $n$ phương trình dạng:
$$
\left\{\begin{matrix}
\text{nums}_1 \cdot q_4 + k_1\cdot m &= r_{1,1} \cdot q_4 \\
\text{nums}_2 \cdot q_4 + k_2\cdot m &= r_{2,1} \cdot q_4 \\
\dots \\
\text{nums}_n \cdot q_4 + k_n\cdot m &= r_{n,1} \cdot q_4
\end{matrix}\right.
$$

Phương trình trên là bài toán `ACD` (Approximate Common Divisor) và ta có $r_{i,j} \cdot q_4$ (vế phải) chỉ khoảng $1796$ bit, nhỏ hơn nhiều so với vế trái nên ta hoàn toàn có thể nghĩ đến việc thiết lập một cơ sở Lattice như sau:
$$
\begin{bmatrix}
\text{nums}_1 & \text{nums}_2 & \cdots & \text{nums}_n & 1 \\
m & 0 & \cdots & 0 & 0 \\
0 & m & \cdots & 0 & 0 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \cdots & m & 0
\end{bmatrix}
$$

Khi áp dụng LLL với cơ sở trên, ta sẽ được một vector ngắn dạng:
$$[r_{1,1}.q_4, \hspace{3mm} r_{2,1}.q_4, \hspace{3mm} ...\hspace{3mm}r_{n,1}.q_4, \hspace{3mm} q_4]$$

>[!Important]
Tuy nhiên vì ma trận khá là lớn nên để LLL nhanh thì ta nên dùng thuật toán [**flatter**](https://github.com/keeganryan/flatter) để có thể LLL nhanh hơn, nhưng để LLL thành công thì ta cần scale ma trận bằng cách nhân cột cuối cho $2^{260}$ để các giá trị trong vector kết quả có giá trị bằng nhau thì flatter mới dễ tìm ra được.

Khi này vector mà ta mong đợi sẽ có dạng:
$$[r_{1,1}.q_4, \hspace{3mm} r_{2,1}.q_4, \hspace{3mm} ...\hspace{3mm}r_{n,1}.q_4, \hspace{3mm} q_4.2^{260}]$$

Có $q_4$, lấy $m/q_4$ là có được $p_4$ là một trong ba ước của $m$ rồi.
Sau khi có $p_4$, ta sẽ giảm modulus xuống còn $m' = m/p_4$, sau đó tiếp tục quá trình LLL như trên với modulus mới và `nums` cũng thanh đổi thành `nums' = nums % m'` để tìm ba số nguyên tố còn lại.

>[!Important]
Một điểm quan trọng khác là sau khi LLL, không phải lúc nào cũng được một số nguyên tố ở cuối mà có thể là `tích` của nhiều số nguyên tố, vì thế ta sẽ `GCD` lần lượt từng cặp `hai` giá trị cuối của từng vector trong cơ sở mới để tìm được các số nguyên tố khác.

:::spoiler **script**

from Crypto.Util.number import long_to_bytes    
from subprocess import check_output
from re import findall
from tqdm import *

def flatter(M):
    print("flatter...")
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))

exec(open("out.txt", "r").read(), globals())
ct = ct
m = m
M = m # cái này dùng để giải mã
nums = nums
print("m has", ZZ(m).nbits(), "bits.")

def get_primes(L): # hàm này được dùng để tìm các số nguyên tố bằng cách GCD
    tmp = set()
    for row in L:
        num = int(abs(row[-1]))
        if num != m and num!= 0:
            num = gcd(num, m)
            p = m // num
            tmp.add(p)
     
    tmp = list(tmp)   
    primes = set()
    for a in range(len(tmp)): # vì có một vài giá trị có chung ước nguyên tố nên ta sẽ dùng hai vòng lặp như thế này để gcd
        for b in range(a + 1, len(tmp)):
            g = gcd(tmp[a], tmp[b])
            if is_prime(g):
                if g not in primes:
                    primes.add(g)
                    print(f"Found prime: {g}")
                    
    print(f"Found {len(primes)} primes")
    return primes

primes = set()
while True:
    if m == 1:
        break
    
    if is_prime(m):
        primes.add(m)
        break

    nums = [num % m for num in nums]
    mat = block_matrix([[matrix(nums[:]),                   2**260],
                        [identity_matrix(len(nums[:]))*m,   0]])
    mat =  flatter(mat)
    candidates = get_primes(mat)
    assert all([is_prime(p) for p in candidates])
    
    for p in candidates:
        m //= p # cứ tìm ra một ước nguyên tố thì ta sẽ giảm m
        primes.add(p)
    
    print(f"m has {m.nbits()} bits remaining to factor.")

primes = list(primes)
assert prod(primes) == M
print("All primes found ✅")

phi = prod(p - 1 for p in primes)
e = 0x10001
d = inverse_mod(e, phi)

print(long_to_bytes(pow(ct, d, M)))

:::spoiler **Flag**
**ictf{rsa_lattices_and_crt_in_1_challenge_surely_has_real_world_applications_lmao_8719617206370154061234128157781624678026841512064124}**
:::


# END