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

## ✅ perfect day (15 solves)

:::spoiler **chall․py**

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

soundtrack = [
    b"House Of The Rising Sun",
    b"the Dock of the Bay",
    b"(Walkin' Thru The) Sleepy City",
    b"Redondo Beach",
    b"Pale Blue Eyes",
    b"Brown Eyed Girl",
    b"Feeling Good",
    b"Aoi Sakana",
    b"Perfect Day"
]

print("Welcome to the song guessing game!")

for i in range(32):
    p = getPrime(512)
    k = random.randint(1, 4096)
    song = random.choice(soundtrack)
    padded_song = song + b"0xff"*(256 - len(song))
    hint = pow(1 + k*p, bytes_to_long(padded_song), p**2)
    
    print(f"p = {p}")
    print(f"hint = {hint}")
    ans = input("Guess the song: ")
    
    if ans == song.decode():
        print("Correct!")
    else:
        print("Wrong! Try again.")
        exit(0)
        
FLAG = open("flag.txt", "r").read()
print("Congratulations! You've guessed all the songs correctly.")
print(f"Flag: {FLAG}")

:::

### Mô tả
Source code viết khá đơn giản nên có thể tóm tắt được các ý chính như sau:
- Challenge tạo một vòng lặp $32$ lần, mỗi lần lặp chọn một bài hát (`song`) bất kỳ trong một list $9$ bài hát, một số nguyên tố $p$ dài $512$ bit làm **modulus** và một số nguyên $k \in [1, 4096]$.

- Tiếp theo Challenge **pad** `song` theo công thức `padded_song = song + b"0xff"*(256 - len(song))` nhằm tăng độ lớn của `song` lên nhiều lần.

- Sau đó Challenge tạo một giá trị $\text{hint}$ theo công thức:
$$\text{hint} \equiv (1 + k\times p)^{\text{padded song}} \pmod {p^2}$$

- Cuối cùng in ra modulus $p$ và $\text{hint}$, yêu cầu ta gửi lại `song` mà Challenge đã sử dụng để tạo ra $\text{hint}$.

---

### Hướng suy nghĩ

> **Mục tiêu:** Cần tìm lại `song` từ `padded_song` với các giá trị cho trước là $\text{hint}$ và $p$.

Ta có `padded_song` là giá trị lũy thừa của $(1 + k\times p)$. Nghĩ ngay đến **DLP**, nhưng không thể **Logarit** được vì giá trị của `padded_song` rất lớn, lớn hơn cả $p^2$, cần phải nghĩ đến hướng giải khác.

Thấy rằng giá trị $k$ rất nhỏ, mà `song` cũng chỉ có $9$ giá trị, ta nghĩ ngay đến **brute force** $k$ và `song` sao cho thỏa mãn phương trình:
$$\text{hint} \equiv (1 + k\times p)^{\text{padded song}} \pmod {p^2}$$

Nhưng nếu chỉ brute force như vậy thì code sẽ chạy rất rất lâu vì phép tính của ta là phép lũy thừa, ta cần biến đổi lại phương trình trên một xíu để tăng tốc quá trình brute force.

Khai triển **nhị thức newton** của $(1 + k\times p)^{\text{padded song}} \mod {p^2}$, ta được:
$$(1 + k\times p)^{\text{padded song}} \equiv 1 + \text{padded song} \times k \times p \pmod {p^2}$$

Vậy phương trình ban đầu trở thành:
$$\text{hint} \equiv 1 + \text{padded song} \times k \times p \pmod {p^2}$$

Khi này ta có thể brute force nhanh hơn vì nó chỉ là phép nhân mà thôi, tìm được `song` và $k$ thỏa mãn giá trị $\text{hint}$, ta gửi đến server và bài toán kết thúc.

---

### Lời giải
:::spoiler **solution**

from pwn import *
from Crypto.Util.number import *

io = remote("36.50.177.41", 5001)
for i in range(32):
    print(f"i = {i+1}")

    io.recvuntil(b"p = ")
    p = int(io.recvline())

    io.recvuntil(b"hint = ")
    hint = int(io.recvline())

    soundtrack = [
        b"House Of The Rising Sun",
        b"the Dock of the Bay",
        b"(Walkin' Thru The) Sleepy City",
        b"Redondo Beach",
        b"Pale Blue Eyes",
        b"Brown Eyed Girl",
        b"Feeling Good",
        b"Aoi Sakana",
        b"Perfect Day"
    ]

    for song in soundtrack:
        padded_song = bytes_to_long(song + b"0xff"*(256 - len(song)))
        for k in range(1, 4096):
            if hint == (1 + padded_song * k * p) % p**2:
                print(song)
                io.sendlineafter(b"Guess the song: ", song)
                print(io.recvline()) #check
                break
io.interactive()

:::spoiler **Flag**
**KMACTF{did_you_enjoy_soundtrack_perfect_days}**
:::

## ❌ make some noise (3 solves)
:::spoiler **chall.sage**

from random import randint
from re import search

flag = b"KMACTF{fake_flag}"
flag = flag[7: -1]

p = random_prime(2**1024)
setup = [randint(0, 2**32) for _ in range(len(flag))]
setup = [f ^^ ((pad >> 8) << 8) for f, pad in zip(flag, setup)]

output = []

for _ in range(len(flag)^2):
    noise1 = [randint(0, 2**32) for _ in range(1000)]
    noise2 = [randint(0, len(setup)-1) for _ in range(1000)]
    noise3 = [randint(0, len(setup)-1) for _ in range(1000)]
    noise4 = [randint(0, 2**32) for _ in range(1000)]
    noise5 = [randint(0, 2**32) for _ in range(1000)]


    output.append(noise1)
    output.append(noise2)
    output.append(noise3)
    output.append(noise4)
    output.append(noise5)

    s = 0
    for i in range(1000):
        s += (noise5[i] * (noise1[i] + pow(setup[noise2[i]], 1337, p) * pow(setup[noise3[i]], 1663, p)) + noise4[i]) % p

    output.append(s % p)

f = open("out.txt", "w")
f.write(f"{p = }\n")
f.write(f"{output = }\n")

:::
:::spoiler **out.txt**
[**download here**](https://drive.google.com/file/d/1MGfUoT_NgF3MmWsrfYlS4W7BgovQUMwa/view)
:::

### Mô tả
Mất một khoảng thời gian để hiểu được Challenge này hoạt động như thế nào, có thể giải thích tổng thể như sau:
- Challenge tạo một list độ dài là `flag[7: -1]` gồm các **số nguyên** tối đa $32$ bit, sau đó bỏ $8$ bit cuối của các số đó và thay bằng giá trị nhị phân của các ký tự trong `flag[7: -1]`, ta gọi list này là $\text{setup}$:

    flag = b"KMACTF{fake_flag}"
    flag = flag[7: -1]

    p = random_prime(2**1024)
    setup = [randint(0, 2**32) for _ in range(len(flag))]
    setup = [f ^^ ((pad >> 8) << 8) for f, pad in zip(flag, setup)]

- Tiếp theo Challenge tạo một vòng lặp $\text{len(Flag)}^2$ lần và trong **mỗi lần lặp**, Challenge tạo ra $5$ giá trị $\text{noise}_{1,2,...5}$ và $1$ giá trị $s$ như sau:
- Giá trị của $\text{noise}_{1,2,...5}$:

        noise1 = [randint(0, 2**32) for _ in range(1000)]
        noise2 = [randint(0, len(setup)-1) for _ in range(1000)]
        noise3 = [randint(0, len(setup)-1) for _ in range(1000)]
        noise4 = [randint(0, 2**32) for _ in range(1000)]
        noise5 = [randint(0, 2**32) for _ in range(1000)]

- Giá trị của $s$:

        s = 0
        for i in range(1000):
            s += (noise5[i] * (noise1[i] + pow(setup[noise2[i]], 1337, p) * pow(setup[noise3[i]], 1663, p)) + noise4[i]) % p

- Vì `output` `append` tổng cộng $6$ giá trị mỗi lần lặp, mà `len(output) = 1536`, ta sẽ tính được `len(Flag)^2 = 1536/6 = 256 = 16^2`, suy ra `len(Flag) = 16`.

- Challenge lặp $16^2 = 256$ lần nên ta có một hệ $256$ phương trình $s_i$ như sau:
$$s_i \equiv \sum_{i=0}^{999}\text{noise}_5[i] \cdot (\text{noise}_1[i] + \text{setup[noise}_2[i]]^{1337} \cdot \text{setup[noise}_3[i]]^{1663}) + \text{noise}_4[i] \pmod p$$

---

### Hướng làm
> **Mục tiêu:** Giải hệ trên để tìm được $16$ giá trị của $\text{setup}$ vì các ký tự của $\text{Flag}$ được ẩn trong $16$ giá trị của $\text{setup}$.

Trong lúc giải diễn ra thì đầu mình không nảy số kịp, đặt ẩn sai và vấp nhiều chỗ đâm ra không thể giải hệ được, sau khi giải kết thúc thì mới bình tĩnh mà giải lại. Qua bài này mình cũng học thêm được nhiều thứ hay khác.

Bước quan trọng nhất của bài này có lẽ là bước đặt ẩn, ta sẽ không đặt $\text{setup}_i$ là ẩn của phương trình bởi vì nó khiến phương trình của ta có bậc rất lớn, lên đến $3000$.

Đặt giá trị của $\text{noise}_2[i] = u$ và $\text{noise}_2[i] = v$ ta tiến hành đặt ẩn như sau:
$$
\left\{\begin{matrix}
\text{setup[u]}^{1337} = a_i \\
\text{setup[v]}^{1663} = b_i \\
\text{setup[u=v]}^{3000} = a_i \cdot b_i
\end{matrix}\right.
$$

Khi này công thức của $s$ trở thành:
$$s_i \equiv \sum_{i=0}^{999}\text{noise}_5[i] \cdot (\text{noise}_1[i] + a_i \cdot b_i) + \text{noise}_4[i] \pmod p$$

Ta có $16$ biến $a_i$ và $16$ biến $b_i$, trong khi có đến $256$ phương trình, ta hoàn toàn có thể dùng **Groeber_basis()** trong sagemath để đơn giản hệ phương trình trên, giúp tính lại các biến một cách dễ dàng hơn.

Thực hiện như sau:
:::spoiler **Groebner basis**

from tqdm import *

with open("out.txt", "r") as f:
    p = int(f.readline().split(" = ")[1])
    output = eval(f.readline().split(" = ")[1])
    
# đặt biến
F = GF(p, "i")
variables = [f"a{i}" for i in range(16)] + [f"b{i}" for i in range(16)] + [f"s{i}" for i in range(16)]
variables = PolynomialRing(F, variables).gens()

var_a = variables[:16]
var_b = variables[16:32]
var_s = variables[32:48]

# 32 biến dùng cho hàm eval
a0, a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15 = var_a
b0, b1, b2, b3, b4, b5, b6, b7, b8, b9, b10, b11, b12, b13, b14, b15 = var_b

# list lưu 256 phương trình để giải hệ 
equations = []

# output có len là 1536, mỗi lần lặp thì append 6 giá trị => len(flag)^2 = 1536/6 = 256  
for i in trange(0, len(output), 6):
    noise1 = output[0 + i]
    noise2 = output[1 + i]
    noise3 = output[2 + i]
    noise4 = output[3 + i]
    noise5 = output[4 + i]
    
    s = output[5 + i]
    s = -s
    for i in range(1000):
        s += noise5[i] * (noise1[i] + var_s[noise2[i]]^1337 * var_s[noise3[i]]^1663) + noise4[i]
    
    # tiến hành đặt biến:
    # setup[i]^1337 = ai
    # setup[i]^1663 = bi
    # setup[i]^3000 = ai * bi
    
    temp = s
    for i in range(16):
        temp = str(temp).replace(f"s{i}^1337", f"a{i}")
        temp = str(temp).replace(f"s{i}^1663", f"b{i}")
        temp = str(temp).replace(f"s{i}^3000", f"a{i}*b{i}")
    
    equations.append(eval(temp))

# Dùng groebner basis để đơn giản tập sinh
I = Ideal(equations).groebner_basis()
for i in I:
    print(i)

:::

Được một hệ phương trình gồm các phương trình hai ẩn như sau:
:::spoiler **output**

a15*b15 + 86119204666031778361132131538654988592326775231468800432934056629778577889530001825242000398790179830855620730526747366361857281443237003652942326626408419191346322771074668794688002257406764223811918592844662007822581591276059250739169915614756643680312405026412692864071890535780791147352585712854027431245
a0 + 103900091630338517113159682363020354834673093178208603338525971724633674416836534407494761030127719097640424629222104724835770538353514941509096452042015624989422783828417658210973565386799793111360509766152069398111700104543722778278789666682163094242232813342820456471977751899841362780235032867651086598776*a15
a1 + 94782593698022117811595741482319129956155198805414720462016242116623766911080216671486293956814996499207687684455205150878100119889366386083556456522054683377186501281256906568938546584809966096271538691815114215079239388496886641239813923815517441946581125375641585275336613687378494679209334894515748636137*a15
a2 + 29781328395362878010559972753928770820525547754735872300852534399931754382685254280726765681238719682821543179952466959015772927564601108064714668031532965462626720317649979903593364568071841547185568870316973491550811260686711860979161486279494470557050523209387400350555591302866075368939996204225068091231*a15
a3 + 42514568004702292296496446073890971461433627646024949037425788654888156253824159852754025903510747699895075702374722459742318014536634879996010101878697748587903010326510596734217371944846744853981413300364470153590995446987366739221951743043580156798033589461285382892878800209800287072424410796171383447580*a15
a4 + 104847499719235908329095063182318007610120286076264897937782889283466191436226502122105139369082067964764791882450665260396955668067288436637798185063068858671202289836612240592434361174077161993798886976242227091852921248759179720140104213821226607894451285293115562099407619373008805830627220791440511188773*a15
a5 + 857632708832169524649890569725458117131396427051496219603884996631981937443816327414350072800244351854787034229003195742437216705733262740869008672494422267659611235074928450500751761129690044049115111078942754864955525689697275922047774854005413084995504089865080812937882029302148328589095802559382779599*a15
a6 + 19959578203238765973999117072419572480483698112921132023594196768854961150172116412984497415714529093542991448705093842226361393891054000138450033706429410688510170120499064026502400198887175854588966521142193851370976805538103740571905253171735179613120705021061333391972946645921126086143564822642114488953*a15
a7 + 16932878932543870913732698042666318123669617199819533389821843536336735743890558169688532455077837524711101781920236432246957934382182647062090431592033960194174334877839169453259846647785564691181574547741751351243650286476791247542941085703315395592945093585658435161223120293512374600743903950658137229920*a15
a8 + 15479008526193966082012114686270132380273829670073329659978323666780320718109393225338159572626600409052560195584520002587798885234641500899816376630146996252983000996071630875751896022326206968405493063289491284215113793986616555999131799074939208861260553388992555700348127263065469614695035477945466997258*a15
a9 + 120472187316264035473413477097936733929894302361699354385182636147680713296660012568581356627070370499298911997790399956471573274950568401062289369876834842342599813238312293293669635811905915984005147587448999901798478072696426562353518994765480832272784117366537221261307078614807717761808419640233966630143*a15
a10 + 69238436947108827901154466321317357276492402135764977168328945151485080291829140635452518847692166480338648587917747196854159209223222357719347746676915977322027034686402477802670104597582828224335045374125016246868641764804911447607379445762008617075103705661266441611765294615364706206778684881990808554619*a15
a11 + 101820908694507446580717304326343569799882240473391612693965078212786521692310170985457783066604818046666603631829424794683313331821509554751860860574103150993927086461872132826693697290995254840734051245163649645546338995564384203510881767822410562618591733217049019320588582622609182394860736073158752673565*a15
a12 + 100155125642150340856700284444173781643525348881314314309769150316567367348390022207449078538431863073950386299479477593450621292680074817033713616266902364695281623526246411178483266430527926187327284536067153245949831657612542502379654678598665434170393462839343598650050559031953675368939289420388815370706*a15
a13 + 123280244404659171752758029970974388206633652163296981653447667262971850946859997526942861556135249495679678825887385409879620652161263565992801137840937254615969737099574232088068618348800948949865571474485840690172888401692148686518002871413132915405509946337680715499486661623590696018430606215247042556730*a15
a14 + 77561516189612536414626404512808990437227045945814442134885015895022626948197080737310876317683541004442210645564472187683687047563055266473286718260840144361100023736999714524439910381556594437791101932912686292570644062205322916504568490183569196404676847123738255744312377748689429891861986026520862310842*a15
b0 + 15778758265425978551533363875545849212491339699447432685982940785489154851303448807655871195453263443717735452759337847241486739775184249827758331043871750125448684798093449563180631135685506224758805210088247451992347858033190528617164170626991312902602787996367198470941376356331519598470561996860960330727*b15
b1 + 78923065615549431366756602832662337807337272583363934780710228327029685810556829775780112636724040253709404917828750419533801178689883851872614335924679249956227410733214919349219355774544916869920105735363584229873110870573733974840609617051368252944495452565259580222145273336763056441712779935021413011306*b15
b2 + 29200998217601073374605674312184188234929748540210062796068112466522660007084676962686386637249725344577176515089654989502919453951594693975810881795749314377739475769616599258814482095776771632946121943469315130330807053183436612542099649184785173400308784640922926760692384343022372907487351777493123310311*b15
b3 + 87687350227148096695341979281733450446109553593237330091966515365071886695473395549359510163303858558617390122269305223460763281278910861167492905148410451176736727479896800531844227294062892958073315741635660538617479697496084714235845467400991868678386935076970516167292021285458267007696432971370742807707*b15
b4 + 95134819177306196652012348349566053049054421103382930232098568634889216648823225322625949162171572813075353358523314806367609864873769793890102455077967372103006405458678922365691844224530885617194690335368086703318136496705602697500550494262248296260927190181576890337492022898884304534440759761787526329043*b15
b5 + 18803381170304553695974842112997820124222316603648877979282764845033312998488234621881401284894854174136762802610077641484897068739492959209705003194841052285651513132523873996042669406523707752047352558944653936286695304627669700039934091339879683442747728510571685540140952090403971517615248762607561081723*b15
b6 + 48152151649658799016233725648281340034472053411718997856820755201956221923990210370053736325795941381656248138734265770134110068693250141395892043897693586807693796498975737940723566273854763483443891329461905836947334910425425107533768635913816092107754064580621759889663826282719337696835039724514443138549*b15
b7 + 40657324629668571583872556446146840157981990396642740431976993180213639817186124868358542547536457190067608137587032693923242218783451753616277754230115056268116450733490948402952086447417139208337249093920328191174243152439818494807937661834302039007421612885110707893413928923345653636375904482849199816906*b15
b8 + 121721811391490811850354526554187071603846872928693633551002150639464959734707360825640229864903467573800489640854074087720060752110860427757682168077567162999330697062321757832630441021388425964050329930936654569223404493653463312535681012670270780417486277686413896011725831103470636569901492474060462311924*b15
b9 + 64725887878281498790826772350086114458938721534831872711343478153501684134716825178992826447041373037289227120014392902691754649020119362943906086133829849455271264262536769362687111589428273490574765560096680447120146200755457911759602328027009674297124217523013288729835252712066866707328048001935723061348*b15
b10 + 47883194390471797251278627818120490838709230858263630857574324274670748918853434855506394957975871882968116956626807644702185071644874656371148019167313089316153531234317475798354144415941627831840070505174482222219389088721194315112620747171268784398368417716902837893355738461426443597804613148813444351329*b15
b11 + 102149666884525196522495059294368503514941076121259322500135016589111893660994117306351810824342489432344425703877154532791555410389882279892126631630126237630152354102906399693994677947784269413327585223417038087145189406138615156854811371871437184755245118232615068661774449721699140722219647289704576328895*b15
b12 + 80174770868417978393104603722430586744453656226039535187085619103396188376431815556914753449644131201760539825264393790931638885562104717731855402651765839075929177264558469202693411597563378873772878213693845496956124198364424880559084311598646301686228492748274676721926441061879225632334432863859092529349*b15
b13 + 21635454974796825513421686511904534083841379912680835394972288722042031581487907459176249346393107680342121676421551292220329244442961454923100646119286578237840094189980189104591485893581953548713381210102936325448622635104361543672387833530245442474146754754496869455293324984213683345353821820879822207155*b15
b14 + 40759104077204701173061529263315525958772328341890294082049936647737639520852491359097233937164158125843447924017660879004684135811374588552401575801778090204654001969100005696025987941944120944143321883300722271020219729733672401085499031107322895848336357302933010888240197657162666349929395305691989863145*b15

:::

Chú ý vào $16$ phương trình đầu tiên có chứa biến $a_i$, từ phương trình **thứ hai** trở đi thì chúng đều dính tới ẩn $a_{15}$, vì vậy chỉ cần ta tính được $a_{15}$ là có thể tính được $15$ giá trị $a_i$ còn lại rồi, nhưng tính $a_{15}$ như thế nào nhỉ?

Dựa vào phương trình đầu, ta có $a_{15}\cdot b_{15} + x = 0$, mà $a_{15}\cdot b_{15}$ chính là $\text{setup}[15]^{3000}$, vậy ta có $\text{setup}[15]^{3000} = -x$, giờ chỉ cần mũ cho nghịch đảo của $3000$ trong $\phi(p)$ là có được $\text{setup}[15]$, sau đó tính $a_{15}$ bằng công thức $a_{15} = \text{setup}[15]^{1337}$ là có được $a_{15}$.

Nhưng mọi chuyện chưa đơn giản như vậy.
Khi thử tính $\text{GCD}(3000, p-1)$ thì ta có kết quả là $4$ 🐧. Giờ làm sao để triệt tiêu mũ $3000$ nhỉ, nhắc lại công thức của định lý **Euclid** mở rộng. Đặt $e = 3000$, tồn tại hai số $(d, k)$ sao cho:

$$e\cdot d + k\cdot \phi = \text{GCD}(e, \phi)$$

$$\Leftrightarrow e\cdot d + k\cdot \phi = 4$$

$$\Leftrightarrow e\cdot d \equiv 4 \pmod {\phi}$$

Vậy khi ta lấy $(\text{setup}[15]^{3000})^{d}$ ta sẽ còn $\text{setup}[15]^{4}$. Mà $\text{setup}[i]$ chỉ có giá trị là $32$ bit, nên $\text{setup}[i]^4$ vẫn bé hơn $p$ nhiều lần, ta chỉ cần tính căn bậc $4$ trên trường số thực là có được $\text{setup}[15]$.

Có $\text{setup}[15] \rightarrow$ Có $a_{15} \rightarrow$ Tính được $15$ giá trị $a_i$ còn lại $\rightarrow$ Lấy $a_i$ mũ cho $1337^{-1} \mod \phi \rightarrow$ có $15$ giá trị $\text{setup}[i]$ còn lại $\rightarrow$ Lấy $8$ bit cuối của $\text{setup}[i]$, ghép lại là có Flag $\rightarrow$ Kết thúc Challenge.

---

### Lời giải
:::spoiler **solution**

from tqdm import *
from gmpy2 import gcdext, iroot

# cho proof sai để tăng tốc độ tính toán
proof.arithmetic(False)

with open("out.txt", "r") as f:
    p = int(f.readline().split(" = ")[1])
    output = eval(f.readline().split(" = ")[1])
    
# đặt biến
F = GF(p, "i")
variables = [f"a{i}" for i in range(16)] + [f"b{i}" for i in range(16)] + [f"s{i}" for i in range(16)]
variables = PolynomialRing(F, variables).gens()

var_a = variables[:16]
var_b = variables[16:32]
var_s = variables[32:48]

# 32 biến dùng cho hàm eval
a0, a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15 = var_a
b0, b1, b2, b3, b4, b5, b6, b7, b8, b9, b10, b11, b12, b13, b14, b15 = var_b

# list lưu 256 phương trình để giải hệ 
equations = []

# output có len là 1536, mỗi lần lặp thì append 6 giá trị => len(flag)^2 = 1536/6 = 256  
for i in trange(0, len(output), 6):
    noise1 = output[0 + i]
    noise2 = output[1 + i]
    noise3 = output[2 + i]
    noise4 = output[3 + i]
    noise5 = output[4 + i]
    
    s = output[5 + i]
    s = -s
    for i in range(1000):
        s += noise5[i] * (noise1[i] + var_s[noise2[i]]^1337 * var_s[noise3[i]]^1663) + noise4[i]
    
    # tiến hành đặt biến:
    # setup[i]^1337 = ai
    # setup[i]^1663 = bi
    # setup[i]^3000 = ai * bi
    
    temp = s
    for i in range(16):
        temp = str(temp).replace(f"s{i}^1337", f"a{i}")
        temp = str(temp).replace(f"s{i}^1663", f"b{i}")
        temp = str(temp).replace(f"s{i}^3000", f"a{i}*b{i}")
    
    equations.append(eval(temp))

# Dùng groebner basis để đơn giản tập sinh
I = Ideal(equations)
equations = list(I.groebner_basis())
# print(equations)

# tính s15
x = int(-equations[0].coefficients()[-1] % p) # nhớ lấy dấu âm
d = gcdext(3000, p-1)[1] % (p-1)
s15 = iroot(pow(x, d, p), 4)[0] #1361733486

# ta tính được setup[15] rùi nè
# giờ ta cần tính a15 theo công thức: a15 = setup[15]^1337
a15 = pow(s15, 1337, p)

equations = [a15*b15 + 86119204666031778361132131538654988592326775231468800432934056629778577889530001825242000398790179830855620730526747366361857281443237003652942326626408419191346322771074668794688002257406764223811918592844662007822581591276059250739169915614756643680312405026412692864071890535780791147352585712854027431245, a0 + 103900091630338517113159682363020354834673093178208603338525971724633674416836534407494761030127719097640424629222104724835770538353514941509096452042015624989422783828417658210973565386799793111360509766152069398111700104543722778278789666682163094242232813342820456471977751899841362780235032867651086598776*a15, a1 + 94782593698022117811595741482319129956155198805414720462016242116623766911080216671486293956814996499207687684455205150878100119889366386083556456522054683377186501281256906568938546584809966096271538691815114215079239388496886641239813923815517441946581125375641585275336613687378494679209334894515748636137*a15, a2 + 29781328395362878010559972753928770820525547754735872300852534399931754382685254280726765681238719682821543179952466959015772927564601108064714668031532965462626720317649979903593364568071841547185568870316973491550811260686711860979161486279494470557050523209387400350555591302866075368939996204225068091231*a15, a3 + 42514568004702292296496446073890971461433627646024949037425788654888156253824159852754025903510747699895075702374722459742318014536634879996010101878697748587903010326510596734217371944846744853981413300364470153590995446987366739221951743043580156798033589461285382892878800209800287072424410796171383447580*a15, a4 + 104847499719235908329095063182318007610120286076264897937782889283466191436226502122105139369082067964764791882450665260396955668067288436637798185063068858671202289836612240592434361174077161993798886976242227091852921248759179720140104213821226607894451285293115562099407619373008805830627220791440511188773*a15, a5 + 857632708832169524649890569725458117131396427051496219603884996631981937443816327414350072800244351854787034229003195742437216705733262740869008672494422267659611235074928450500751761129690044049115111078942754864955525689697275922047774854005413084995504089865080812937882029302148328589095802559382779599*a15, a6 + 19959578203238765973999117072419572480483698112921132023594196768854961150172116412984497415714529093542991448705093842226361393891054000138450033706429410688510170120499064026502400198887175854588966521142193851370976805538103740571905253171735179613120705021061333391972946645921126086143564822642114488953*a15, a7 + 16932878932543870913732698042666318123669617199819533389821843536336735743890558169688532455077837524711101781920236432246957934382182647062090431592033960194174334877839169453259846647785564691181574547741751351243650286476791247542941085703315395592945093585658435161223120293512374600743903950658137229920*a15, a8 + 15479008526193966082012114686270132380273829670073329659978323666780320718109393225338159572626600409052560195584520002587798885234641500899816376630146996252983000996071630875751896022326206968405493063289491284215113793986616555999131799074939208861260553388992555700348127263065469614695035477945466997258*a15, a9 + 120472187316264035473413477097936733929894302361699354385182636147680713296660012568581356627070370499298911997790399956471573274950568401062289369876834842342599813238312293293669635811905915984005147587448999901798478072696426562353518994765480832272784117366537221261307078614807717761808419640233966630143*a15, a10 + 69238436947108827901154466321317357276492402135764977168328945151485080291829140635452518847692166480338648587917747196854159209223222357719347746676915977322027034686402477802670104597582828224335045374125016246868641764804911447607379445762008617075103705661266441611765294615364706206778684881990808554619*a15, a11 + 101820908694507446580717304326343569799882240473391612693965078212786521692310170985457783066604818046666603631829424794683313331821509554751860860574103150993927086461872132826693697290995254840734051245163649645546338995564384203510881767822410562618591733217049019320588582622609182394860736073158752673565*a15, a12 + 100155125642150340856700284444173781643525348881314314309769150316567367348390022207449078538431863073950386299479477593450621292680074817033713616266902364695281623526246411178483266430527926187327284536067153245949831657612542502379654678598665434170393462839343598650050559031953675368939289420388815370706*a15, a13 + 123280244404659171752758029970974388206633652163296981653447667262971850946859997526942861556135249495679678825887385409879620652161263565992801137840937254615969737099574232088068618348800948949865571474485840690172888401692148686518002871413132915405509946337680715499486661623590696018430606215247042556730*a15, a14 + 77561516189612536414626404512808990437227045945814442134885015895022626948197080737310876317683541004442210645564472187683687047563055266473286718260840144361100023736999714524439910381556594437791101932912686292570644062205322916504568490183569196404676847123738255744312377748689429891861986026520862310842*a15, b0 + 15778758265425978551533363875545849212491339699447432685982940785489154851303448807655871195453263443717735452759337847241486739775184249827758331043871750125448684798093449563180631135685506224758805210088247451992347858033190528617164170626991312902602787996367198470941376356331519598470561996860960330727*b15, b1 + 78923065615549431366756602832662337807337272583363934780710228327029685810556829775780112636724040253709404917828750419533801178689883851872614335924679249956227410733214919349219355774544916869920105735363584229873110870573733974840609617051368252944495452565259580222145273336763056441712779935021413011306*b15, b2 + 29200998217601073374605674312184188234929748540210062796068112466522660007084676962686386637249725344577176515089654989502919453951594693975810881795749314377739475769616599258814482095776771632946121943469315130330807053183436612542099649184785173400308784640922926760692384343022372907487351777493123310311*b15, b3 + 87687350227148096695341979281733450446109553593237330091966515365071886695473395549359510163303858558617390122269305223460763281278910861167492905148410451176736727479896800531844227294062892958073315741635660538617479697496084714235845467400991868678386935076970516167292021285458267007696432971370742807707*b15, b4 + 95134819177306196652012348349566053049054421103382930232098568634889216648823225322625949162171572813075353358523314806367609864873769793890102455077967372103006405458678922365691844224530885617194690335368086703318136496705602697500550494262248296260927190181576890337492022898884304534440759761787526329043*b15, b5 + 18803381170304553695974842112997820124222316603648877979282764845033312998488234621881401284894854174136762802610077641484897068739492959209705003194841052285651513132523873996042669406523707752047352558944653936286695304627669700039934091339879683442747728510571685540140952090403971517615248762607561081723*b15, b6 + 48152151649658799016233725648281340034472053411718997856820755201956221923990210370053736325795941381656248138734265770134110068693250141395892043897693586807693796498975737940723566273854763483443891329461905836947334910425425107533768635913816092107754064580621759889663826282719337696835039724514443138549*b15, b7 + 40657324629668571583872556446146840157981990396642740431976993180213639817186124868358542547536457190067608137587032693923242218783451753616277754230115056268116450733490948402952086447417139208337249093920328191174243152439818494807937661834302039007421612885110707893413928923345653636375904482849199816906*b15, b8 + 121721811391490811850354526554187071603846872928693633551002150639464959734707360825640229864903467573800489640854074087720060752110860427757682168077567162999330697062321757832630441021388425964050329930936654569223404493653463312535681012670270780417486277686413896011725831103470636569901492474060462311924*b15, b9 + 64725887878281498790826772350086114458938721534831872711343478153501684134716825178992826447041373037289227120014392902691754649020119362943906086133829849455271264262536769362687111589428273490574765560096680447120146200755457911759602328027009674297124217523013288729835252712066866707328048001935723061348*b15, b10 + 47883194390471797251278627818120490838709230858263630857574324274670748918853434855506394957975871882968116956626807644702185071644874656371148019167313089316153531234317475798354144415941627831840070505174482222219389088721194315112620747171268784398368417716902837893355738461426443597804613148813444351329*b15, b11 + 102149666884525196522495059294368503514941076121259322500135016589111893660994117306351810824342489432344425703877154532791555410389882279892126631630126237630152354102906399693994677947784269413327585223417038087145189406138615156854811371871437184755245118232615068661774449721699140722219647289704576328895*b15, b12 + 80174770868417978393104603722430586744453656226039535187085619103396188376431815556914753449644131201760539825264393790931638885562104717731855402651765839075929177264558469202693411597563378873772878213693845496956124198364424880559084311598646301686228492748274676721926441061879225632334432863859092529349*b15, b13 + 21635454974796825513421686511904534083841379912680835394972288722042031581487907459176249346393107680342121676421551292220329244442961454923100646119286578237840094189980189104591485893581953548713381210102936325448622635104361543672387833530245442474146754754496869455293324984213683345353821820879822207155*b15, b14 + 40759104077204701173061529263315525958772328341890294082049936647737639520852491359097233937164158125843447924017660879004684135811374588552401575801778090204654001969100005696025987941944120944143321883300722271020219729733672401085499031107322895848336357302933010888240197657162666349929395305691989863145*b15]

# vì nó dạng ai + x = 0 nên ta chỉ cần lấy -x mod p là có ai
# sau đó làm tương tự RSA để bỏ đi lũy thừa

flag = []
for i in equations[1:16]: # Lấy mấy biến a thui
    ai = int(- i.coefficients()[-1] % p)
    d = pow(1337, -1, p-1)
    flag.append(pow(ai, d, p))

flag.append(s15)
for i in flag:
    print(chr(int(bin(i)[-8:], 2)), end="")

print()

:::spoiler **Flag**
**KMACTF{aw3s0me_s0lut1on}**
:::
## ❌ stranger things (1 solves)
:::spoiler **chall.sage**

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

#p = getPrime(64)
p = 12267883553178394373
Fp = GF((p, 3))

FLAG = b'KMACTF{fake_flag}'

s = Fp.from_integer(bytes_to_long(FLAG))

set_random_seed(1337)
out = []
for i in range(15):
    a, b = Fp.random_element(), Fp.random_element()
    s = a * s + b
    out.extend(s)

print([x >> 57 for x in out])
# [43, 80, 59, 18, 3, 12, 77, 20, 25, 68, 68, 30, 47, 73, 78, 52, 62, 68, 84, 39, 32, 16, 1, 55, 39, 58, 48, 8, 72, 13, 63, 34, 19, 44, 45, 56, 82, 76, 10, 46, 69, 28, 69, 78, 29]

:::

### Mô tả
Một Challenge khá là khó, mình chưa đủ khả năng để làm bài này nên phải đi xin hint từ bạn **Minh** (top 1 KMA CTF 2025) mới có thể làm được bài này.

Vì source code viết khá đơn giản nên ta có thể tóm được các ý chính sau:
- Challenge này hoạt động trên trường mở rộng $\text{GF}(p^3)$, nên các phần tử trong trường đều sẽ có dạng $ax^2 + bx + c$. Nên $\text{Flag}$ của ta cũng tương tự, sau khi chuyển qua **int** và đặt vào trong $Fp$, nó cũng có dạng là $ax^2 + bx + c$.

- Tiếp theo tạo một vòng lặp $15$ vòng, mỗi vòng thực hiện phép tính:
$$s_{i+1} \equiv A \times s_i + B \pmod {GF\text{.modulus}}$$

> Với $s_0$ là $\text{Flag}$, $(A, B)$ là hai giá trị ngẫu nhiên được tạo từ **seed** cố định $1337$.
**Lưu ý** là với các số nguyên thì ta vẫn sẽ mod cho $p$, còn với đa thức thì ta phải mod cho đa thức của $GF(p^3)$.

- Vì $s$ đang được biểu diễn dưới dạng đa thức $ax^2 +bx+c$ nên Challenge sẽ thêm $s$ vào list `out` dưới dạng các hệ số $[c, b, a]$ (xếp từ bậc nhỏ nhất).

- Với $45$ giá trị trong `out`, Challenge tiến hành bỏ đi $57$ bit cuối của mỗi $s$, chỉ để lại $7$ bit đầu mà thôi.

- Cuối cùng in $45$ giá trị $s>> 57$ ra và yêu cầu khôi phục lại $\text{Flag}$ ban đầu từ modulus $p$, seed $1337$ và $45$ giá trị $s>>57$.

---

### Hướng làm
> **Mục tiêu:** Khôi phục Flag từ list `out`, modulus $p$ và seed $1337$.

Vì Flag của ta được biểu diễn dưới dạng $ax^2+bx+c$ nên ta cần phải tìm lại tập giá trị $(a, b, c)$ đó và khôi phục theo công thức:
$$\text{Flag} = a\cdot p^2+b\cdot p + c$$

Ở vòng lặp đầu tiên, đặt $\text{Flag} = s = a+bx+cx^2$, sử dụng seed $1337$, ta tính giá trị của $A\cdot s + B$ như sau:

p = 12267883553178394373

Fp = GF((p, 3))
x = Fp.gen()

# tạo các biến cho s
a, b, c = PolynomialRing(Fp, ["a", "b", "c"]).gens()
s = a + b * x + c * x ^ 2

set_random_seed(1337)
A, B = Fp.random_element(), Fp.random_element()

print(A*s + B)

Được kết quả là:

s = (11096584571873777345*z3^2 + 10557248725682989278*z3 + 3979752675954023529)*a + \
    (5937113067909077585*z3^2 + 3815924565230295538*z3 + 8753986609264543289)*b + \
    (9100459316456747575*z3^2 + 7344609725201457733*z3 + 5543455650548838382)*c + \
    5644891284203893353*z3^2 + 10321418373171877975*z3 + 10472345338873147245

Khi này giá trị $s$ là một đa thức dạng $ax^2+bx+c$ và được thêm vào list `out` đưới dạng các hệ số $[c, b, a]$.

Tiến hành gộp các giá trị chứa $\text{z}_3$, $\text{z}_3^2$ và các tham số tự do lại, ta có biểu diễn mới của $s$ là:

s = (11096584571873777345*a + 5937113067909077585*b + 9100459316456747575*c + 5644891284203893353)*z3^2 + \
    (10557248725682989278*a + 3815924565230295538*b + 7344609725201457733*c + 10321418373171877975)*z3 + \
    (3979752675954023529*a + 8753986609264543289*b + 5543455650548838382*c + 10472345338873147245)

Vì $s$ được thêm vào list `out` dưới dạng các hệ số nên khi đối chiếu công thức $s$ ở trên với ba phần tử đầu của list `out` là `[43, 80, 59]`, ta được một hệ phương trình như sau:

$$
\left\{\begin{matrix}
(3979..) \times a + (8753..)\times b + (5543..)\times c + (1047..) = 43 \times 2^{57} + m_0 \\
(1055..)\times a + (3815..)\times b + (7344..) \times c + (1032..) = 80 \times 2^{57} + m_1\\
(1109..) \times a + (5937..) \times b + (9100..) \times c + (5644..) = 59 \times 2^{57}+m_2
\end{matrix}\right.
$$

> Với $m_{0,1,2...}$ là các giá trị bit bị mất đi

Vì Challenge lặp $15$ lần nên ta sẽ có một hệ $45$ phương trình như trên với tổng cộng các ẩn ta cần tìm là $3$ ẩn $a,b,c$ và $45$ ẩn $m_0,m_1,...,m_{44}$.

Để giải hệ trên, ta sẽ không sử dụng `groebner_basis()` như bài trước mà sử dụng hàm `solve_linear_mod` để giải hệ phương trình tuyến tính, đã được [build sẵn](https://github.com/nneonneo/pwn-stuff/blob/main/math/solvelinmod.py), ta chỉ cần import rồi sử dụng thôi.

Sau khi giải hệ thành công, ta sẽ có được ba giá trị $(a, b, c)$, và có thể khôi phục Flag theo công thức $\text{Flag} = a\cdot p^2+b\cdot p + c$ rồi. Bài toán là kết thúc.

---

### Lời giải
:::spoiler **solution**

from Crypto.Util.number import *
import operator
from typing import List, Tuple
from collections.abc import Sequence
import math

"""
Solve a bounded system of modular linear equations.

(c) 2019-2022 Robert Xiao <[e-mail]>
https://robertxiao.ca

Originally developed in May 2019; updated July 2022

Please mention this software if it helps you solve a challenge!
"""

def _process_linear_equations(equations, vars, guesses) -> List[Tuple[List[int], int, int]]:
    result = []

    for rel, m in equations:
        op = rel.operator()
        if op is not operator.eq:
            raise TypeError(f"relation {rel}: not an equality relation")

        expr = (rel - rel.rhs()).lhs().expand()
        for var in expr.variables():
            if var not in vars:
                raise ValueError(f"relation {rel}: variable {var} is not bounded")

        # Fill in eqns block of B
        coeffs = []
        for var in vars:
            if expr.degree(var) >= 2:
                raise ValueError(f"relation {rel}: equation is not linear in {var}")
            coeff = expr.coefficient(var)
            if not coeff.is_constant():
                raise ValueError(f"relation {rel}: coefficient of {var} is not constant (equation is not linear)")
            if not coeff.is_integer():
                raise ValueError(f"relation {rel}: coefficient of {var} is not an integer")

            coeffs.append(int(coeff) % m)

        # Shift variables towards their guesses to reduce the (expected) length of the solution vector
        const = expr.subs({var: guesses[var] for var in vars})
        if not const.is_constant():
            raise ValueError(f"relation {rel}: failed to extract constant")
        if not const.is_integer():
            raise ValueError(f"relation {rel}: constant is not integer")

        const = int(const) % m

        result.append((coeffs, const, m))

    return result

def solve_linear_mod(equations, bounds, verbose=False, **lll_args):
    """Solve an arbitrary system of modular linear equations over different moduli.

    equations: A sequence of (lhs == rhs, M) pairs, where lhs and rhs are expressions and M is the modulus.
    bounds: A dictionary of {var: B} entries, where var is a variable and B is the bounds on that variable.
        Bounds may be specified in one of three ways:
        - A single integer X: Variable is assumed to be uniformly distributed in [0, X] with an expected value of X/2.
        - A tuple of integers (X, Y): Variable is assumed to be uniformly distributed in [X, Y] with an expected value of (X + Y)/2.
        - A tuple of integers (X, E, Y): Variable is assumed to be bounded within [X, Y] with an expected value of E.
        All variables used in the equations must be bounded.
    verbose: set to True to enable additional output
    lll_args: Additional arguments passed to LLL, for advanced usage.

    NOTE: Bounds are *soft*. This function may return solutions above the bounds. If this happens, and the result
    is incorrect, make some bounds tighter and try again.

    Tip: if you get an unwanted solution, try setting the expected values to that solution to force this function
    to produce a different solution.

    Tip: if your bounds are loose and you just want small solutions, set the expected values to zero for all
    loosely-bounded variables.

    >>> k = var('k')
    >>> # solve CRT
    >>> solve_linear_mod([(k == 2, 3), (k == 4, 5), (k == 3, 7)], {k: 3*5*7})
    {k: 59}

    >>> x,y = var('x,y')
    >>> solve_linear_mod([(2*x + 3*y == 7, 11), (3*x + 5*y == 3, 13), (2*x + 5*y == 6, 143)], {x: 143, y: 143})
    {x: 62, y: 5}

    >>> x,y = var('x,y')
    >>> # we can also solve homogenous equations, provided the guesses are zeroed
    >>> solve_linear_mod([(2*x + 5*y == 0, 1337)], {x: 5, y: 5}, guesses={x: 0, y: 0})
    {x: 5, y: -2}
    """

    # The general idea is to set up an integer matrix equation Ax=y by introducing extra variables for the quotients,
    # then use LLL to solve the equation. We introduce extra axes in the lattice to observe the actual solution x,
    # which works so long as the solutions are known to be bounded (which is of course the case for modular equations).
    # Scaling factors are configured to generally push the smallest vectors to have zeros for the relations, and to
    # scale disparate variables to approximately the same base.

    vars = list(bounds)
    guesses = {}
    var_scale = {}
    for var in vars:
        bound = bounds[var]
        if isinstance(bound, Sequence):
            if len(bound) == 2:
                xmin, xmax = map(int, bound)
                guess = (xmax - xmin) // 2 + xmin
            elif len(bound) == 3:
                xmin, guess, xmax = map(int, bound)
            else:
                raise TypeError("Bounds must be integers, 2-tuples or 3-tuples")
        else:
            xmin = 0
            xmax = int(bound)
            guess = xmax // 2
        if not xmin <= guess <= xmax:
            raise ValueError(f"Bound for variable {var} is invalid ({xmin=} {guess=} {xmax=})")
        var_scale[var] = max(xmax - guess, guess - xmin, 1)
        guesses[var] = guess

    var_bits = math.log2(int(prod(var_scale.values()))) + len(vars)
    mod_bits = math.log2(int(prod(m for rel, m in equations)))
    if verbose:
        print(f"verbose: variable entropy: {var_bits:.2f} bits")
        print(f"verbose: modulus entropy: {mod_bits:.2f} bits")

    # Extract coefficients from equations
    equation_coeffs = _process_linear_equations(equations, vars, guesses)

    is_inhom = any(const != 0 for coeffs, const, m in equation_coeffs)

    NR = len(equation_coeffs)
    NV = len(vars)
    if is_inhom:
        # Add one dummy variable for the constant term.
        NV += 1
    B = matrix(ZZ, NR + NV, NR + NV)

    # B format (rows are the basis for the lattice):
    # [ mods:NRxNR 0
    #   eqns:NVxNR vars:NVxNV ]
    # eqns correspond to equation axes, fi(...) = yi mod mi
    # vars correspond to variable axes, which effectively "observe" elements of the solution vector (x in Ax=y)
    # mods and vars are diagonal, so this matrix is lower triangular.

    # Compute maximum scale factor over all variables
    S = max(var_scale.values())

    # Compute equation scale such that the bounded solution vector (equation columns all zero)
    # will be shorter than any vector that has a nonzero equation column
    eqS = S << (NR + NV + 1)
    # If the equation is underconstrained, add additional scaling to find a solution anyway
    if var_bits > mod_bits:
        eqS <<= int((var_bits - mod_bits) / NR) + 1
    col_scales = []

    for ri, (coeffs, const, m) in enumerate(equation_coeffs):
        for vi, c in enumerate(coeffs):
            B[NR + vi, ri] = c
        if is_inhom:
            B[NR + NV - 1, ri] = const
        col_scales.append(eqS)
        B[ri, ri] = m

    # Compute per-variable scale such that the variable axes are scaled roughly equally
    for vi, var in enumerate(vars):
        col_scales.append(S // var_scale[var])
        # Fill in vars block of B
        B[NR + vi, NR + vi] = 1

    if is_inhom:
        # Const block: effectively, this is a bound of 1 on the constant term
        col_scales.append(S)
        B[NR + NV - 1, -1] = 1

    if verbose:
        print("verbose: scaling shifts:", [math.log2(int(s)) for s in col_scales])
        print("verbose: unscaled matrix before:")
        print(B.n())

    for i, s in enumerate(col_scales):
        B[:, i] *= s
    B = B.LLL(**lll_args)
    for i, s in enumerate(col_scales):
        B[:, i] /= s

    # Negate rows for more readable output
    for i in range(B.nrows()):
        if sum(x < 0 for x in B[i, :]) > sum(x > 0 for x in B[i, :]):
            B[i, :] *= -1
        if is_inhom and B[i, -1] < 0:
            B[i, :] *= -1

    if verbose:
        print("verbose: unscaled matrix after:")
        print(B.n())

    for row in B:
        if any(x != 0 for x in row[:NR]):
            # invalid solution: some relations are nonzero
            continue

        if is_inhom:
            # Each row is a potential solution, but some rows may not carry a constant.
            if row[-1] != 1:
                if verbose:
                    print(
                        "verbose: zero solution",
                        {var: row[NR + vi] for vi, var in enumerate(vars) if row[NR + vi] != 0},
                    )
                continue

        res = {}
        for vi, var in enumerate(vars):
            res[var] = row[NR + vi] + guesses[var]

        return res

p = 12267883553178394373

Fp = GF((p, 3))
x = Fp.gen()

# tạo biến cho s
a, b, c = PolynomialRing(Fp, ["a", "b", "c"]).gens()
s = a + b * x + c * x ^ 2

set_random_seed(1337)

# ba ẩn ta cần tìm
aa, bb, cc = var("aa bb cc")
Eq = []
for i in range(15):
    eq = [0, 0, 0]
    A, B = Fp.random_element(), Fp.random_element()
    s = A * s + B
        
    s_ = s.coefficients()
    
    eq[0] += int(s_[0][0]) * aa 
    eq[0] += int(s_[1][0]) * bb 
    eq[0] += int(s_[2][0]) * cc 

    eq[1] += int(s_[0][1]) * aa 
    eq[1] += int(s_[1][1]) * bb 
    eq[1] += int(s_[2][1]) * cc 

    eq[2] += int(s_[0][2]) * aa 
    eq[2] += int(s_[1][2]) * bb 
    eq[2] += int(s_[2][2]) * cc 

    eq[0] += int(s_[3][0])
    eq[1] += int(s_[3][1])
    eq[2] += int(s_[3][2])

    Eq += eq
    
out = [43, 80, 59, 18, 3, 12, 77, 20, 25, 68, 68, 30, 47, 73, 78, 52, 62, 68, 84, 39, 32, 16, 1, 55, 39, 58, 48, 8, 72, 13, 63, 34, 19, 44, 45, 56, 82, 76, 10, 46, 69, 28, 69, 78, 29]
out = [i << 57 for i in out]
   
ms =  var(" ".join([f"m{i}" for i in range(45)]))
equation = [] 
for i in range(45):
    equation.append([Eq[i] == out[i] + ms[i], p])

# Bound sử dụng cho hàm solve linear mod
bound = {}
for i in range(45):
    bound[ms[i]] = (0, 2**57)  
bound[aa] = (0, p)
bound[bb] = (0, p)
bound[cc] = (0, p)

# khôi phục Flag theo công thức Flag = c*p^2 + b*p + a
solution = (solve_linear_mod(equation, bound))
print(long_to_bytes(solution[aa] + solution[bb]*p + solution[cc]*p**2))

:::spoiler **Flag**
**KMACTF{y0u_ar3_4mazing}**
:::

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