### KMA_CTF_2025

#### 1. perfect day

**__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}")

Để có được flag ta phải trả lời đúng 32 lần liên tiếp

for i in range(32):
    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(f"Flag: {FLAG}")

với dữ kiện được gợi ý là:
+ $hint = (1 + k * p) ^ {song} \pmod{p^2}$

$\to hint = 1 + {song} * k * p \pmod{p^2}$

$\to (hint - 1) / p = k * {song} \pmod{p}$

do tất cả chỉ có 8 bài hát nên ta có thể thực hiện bruteforce tất cả các bài hát để tìm lại $k$ sao cho thỏa mãn $k \in [0, 4096]$.

from Crypto.Util.number import getPrime, bytes_to_long

import os
os.environ["TERM"] = "xterm"

from pwn import *

s = connect("36.50.177.41", 5001)
# s.interactive()
s.recvline()
context.log_level = "debug"

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 i in range(32):

    p = eval(s.recvline().decode().split("=")[1].strip())
    hint = eval(s.recvline().decode().split("=")[1].strip())
    h = ((hint - 1) // p)
    for song in soundtrack:
        print(song)
        padded_song = song + b"0xff"*(256 - len(song))
        padded_song = bytes_to_long(padded_song)
        if (h * pow(padded_song, -1, p)) % p in list(range(1, 4096)):
            print("Found song:", song.decode())
            s.sendline(song.decode())
            s.recvline()
            break

#### 2. make some noise

**__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")

Ta có flag được dấu trong các bit cuối của từng phần tử trong mảng $setup$

setup = [f ^^ ((pad >> 8) << 8) for f, pad in zip(flag, setup)]

với $$f_ii = ({noise5}_i * ({noise1}_i + {setup}[{noise2}_i] ^ {1337} * {setup}[{noise3}_i] ^ {1663}) + {noise4}_i) % p
$$

Ta có 256 lần kết quả của s = $\sum_{i = 0}^{999}f_i \pmod{p}$

do đã biết hết các `noise` nên có thể viết lại s.
Khi viết ra thì ta có thể thấy các s được tính như sau

7096123480*s0^3000 + 14738955324*s0^1663*s1^1337 + 13783066574*s0^1337*s1^1663 + 7550523976*s1^3000 + 18833012292*s0^1663*s2^1337 + 10560142961*s1^1663*s2^1337 + 10935212851*s0^1337*s2^1663 + 7480678582*s1^1337*s2^1663 + 8706145996*s2^3000 + 11720204181*s0^1663*s3^1337 + 7122636976*s1^1663*s3^1337 + 13649446032*s2^1663*s3^1337 + 9806006309*s0^1337*s3^1663 + 10040381586*s1^1337*s3^1663 + 13439368664*s2^1337*s3^1663 + 4334996378*s3^3000 + 11535479523*s0^1663*s4^1337 + 10887059948*s1^1663*s4^1337 + 3699101816*s2^1663*s4^1337 + 3942587364*s3^1663*s4^1337 + 12691854224*s0^1337*s4^1663 + 10874080576*s1^1337*s4^1663 + 7322958729*s2^1337*s4^1663 + 5772391950*s3^1337*s4^1663 + 10854615428*s4^3000 + 2369557661*s0^1663*s5^1337 + 4801400834*s1^1663*s5^1337 + 18330184715*s2^1663*s5^1337 + 13520834445*s3^1663*s5^1337 + 9847351608*s4^1663*s5^1337 + 13759138067*s0^1337*s5^1663 + 2712565691*s1^1337*s5^1663 + 10184626319*s3^1337*s5^1663 + 1498119998*s4^1337*s5^1663 + 14589011532*s5^3000 + 15035119578*s0^1663*s6^1337 + 11339061691*s1^1663*s6^1337 + 6388849293*s2^1663*s6^1337 + 3432893461*s3^1663*s6^1337 + 10793037006*s4^1663*s6^1337 + 14122768224*s5^1663*s6^1337 + 11113199844*s0^1337*s6^1663 + 6131785471*s1^1337*s6^1663 + 8980686249*s2^1337*s6^1663 + 11214560990*s3^1337*s6^1663 + 5689650077*s4^1337*s6^1663 + 12390509712*s5^1337*s6^1663 + 10653001412*s6^3000 + 13245566255*s0^1663*s7^1337 + 7109461771*s1^1663*s7^1337 + 16702788955*s2^1663*s7^1337 + 6613491330*s3^1663*s7^1337 + 14757363563*s4^1663*s7^1337 + 6987479437*s5^1663*s7^1337 + 2233791464*s6^1663*s7^1337 + 10972103513*s0^1337*s7^1663 + 6834944159*s1^1337*s7^1663 + 6089711232*s2^1337*s7^1663 + 13434613823*s3^1337*s7^1663 + 8956016529*s4^1337*s7^1663 + 6203751829*s5^1337*s7^1663 + 15461538084*s6^1337*s7^1663 + 3693023618*s7^3000 + 11481970086*s0^1663*s8^1337 + 6904666833*s1^1663*s8^1337 + 9072196191*s2^1663*s8^1337 + 8971865939*s3^1663*s8^1337 + 5609561124*s4^1663*s8^1337 + 9957664637*s5^1663*s8^1337 + 6970832623*s6^1663*s8^1337 + 4147791912*s7^1663*s8^1337 + 14047260687*s0^1337*s8^1663 + 10281305551*s1^1337*s8^1663 + 4003357743*s2^1337*s8^1663 + 5716111707*s3^1337*s8^1663 + 6854845378*s4^1337*s8^1663 + 9910035037*s5^1337*s8^1663 + 8799282828*s6^1337*s8^1663 + 10210788101*s7^1337*s8^1663 + 9000166977*s8^3000 + 1585751421*s1^1663*s9^1337 + 1906504569*s2^1663*s9^1337 + 8404452245*s3^1663*s9^1337 + 37499922*s4^1663*s9^1337 + 8443121340*s5^1663*s9^1337 + 4355857861*s6^1663*s9^1337 + 3238102810*s7^1663*s9^1337 + 9238964859*s8^1663*s9^1337 + 9856850232*s0^1337*s9^1663 + 6675186922*s1^1337*s9^1663 + 7573975906*s2^1337*s9^1663 + 10227108674*s3^1337*s9^1663 + 5819442591*s4^1337*s9^1663 + 16108721868*s5^1337*s9^1663 + 9520191764*s6^1337*s9^1663 + 5958453080*s7^1337*s9^1663 + 9933966874*s8^1337*s9^1663 + 12042985316*s9^3000 + 10016530899*s0^1663*s10^1337 + 16449919177*s1^1663*s10^1337 + 5882361488*s2^1663*s10^1337 + 7532598444*s3^1663*s10^1337 + 20324536629*s4^1663*s10^1337 + 10123884088*s5^1663*s10^1337 + 1121821256*s6^1663*s10^1337 + 6413696005*s7^1663*s10^1337 + 7630282712*s8^1663*s10^1337 + 8747676938*s9^1663*s10^1337 + 4101646851*s0^1337*s10^1663 + 7871715399*s1^1337*s10^1663 + 3682112466*s2^1337*s10^1663 + 3877474298*s3^1337*s10^1663 + 5546344565*s4^1337*s10^1663 + 4839377643*s5^1337*s10^1663 + 9897812593*s6^1337*s10^1663 + 3176709610*s7^1337*s10^1663 + 4629763663*s8^1337*s10^1663 + 2193920044*s9^1337*s10^1663 + 4456697305*s10^3000 + 7971877110*s0^1663*s11^1337 + 3911306518*s1^1663*s11^1337 + 10594780372*s2^1663*s11^1337 + 1515015663*s3^1663*s11^1337 + 12995801747*s4^1663*s11^1337 + 12761437344*s5^1663*s11^1337 + 10571950940*s6^1663*s11^1337 + 7037572284*s7^1663*s11^1337 + 4814728567*s8^1663*s11^1337 + 9766238489*s9^1663*s11^1337 + 11973981372*s10^1663*s11^1337 + 1660809597*s0^1337*s11^1663 + 11933772507*s1^1337*s11^1663 + 2204098596*s2^1337*s11^1663 + 4479355763*s3^1337*s11^1663 + 4230517324*s4^1337*s11^1663 + 7725873794*s5^1337*s11^1663 + 2684412696*s6^1337*s11^1663 + 4096892300*s7^1337*s11^1663 + 4217161886*s8^1337*s11^1663 + 9170313905*s9^1337*s11^1663 + 19327018074*s10^1337*s11^1663 + 3378391230*s11^3000 + 3639716839*s0^1663*s12^1337 + 13360677145*s1^1663*s12^1337 + 1705968207*s2^1663*s12^1337 + 13093703635*s3^1663*s12^1337 + 13715315585*s4^1663*s12^1337 + 4933969890*s5^1663*s12^1337 + 4987551725*s6^1663*s12^1337 + 7256015103*s7^1663*s12^1337 + 5010185745*s8^1663*s12^1337 + 5366082169*s9^1663*s12^1337 + 4816001788*s10^1663*s12^1337 + 5726830982*s11^1663*s12^1337 + 2015567489*s0^1337*s12^1663 + 12853659250*s1^1337*s12^1663 + 14108803655*s2^1337*s12^1663 + 12795910069*s3^1337*s12^1663 + 4583422372*s5^1337*s12^1663 + 10849635660*s6^1337*s12^1663 + 7406887668*s7^1337*s12^1663 + 10825960057*s8^1337*s12^1663 + 10831173109*s9^1337*s12^1663 + 649129198*s10^1337*s12^1663 + 14852938908*s11^1337*s12^1663 + 6345360937*s12^3000 + 7416423743*s0^1663*s13^1337 + 15694724200*s1^1663*s13^1337 + 2139761605*s2^1663*s13^1337 + 16411378918*s3^1663*s13^1337 + 14492011189*s4^1663*s13^1337 + 4053263384*s5^1663*s13^1337 + 9914178487*s6^1663*s13^1337 + 6037604930*s7^1663*s13^1337 + 2727132074*s8^1663*s13^1337 + 6293204738*s9^1663*s13^1337 + 12645136642*s10^1663*s13^1337 + 1590556769*s11^1663*s13^1337 + 4205282613*s12^1663*s13^1337 + 19413262817*s0^1337*s13^1663 + 15226340691*s1^1337*s13^1663 + 4015318904*s2^1337*s13^1663 + 7312372213*s4^1337*s13^1663 + 5530413935*s5^1337*s13^1663 + 1759105465*s6^1337*s13^1663 + 7875916478*s7^1337*s13^1663 + 10061764203*s8^1337*s13^1663 + 5586826295*s9^1337*s13^1663 + 17101618944*s10^1337*s13^1663 + 5944822711*s11^1337*s13^1663 + 13207411312*s12^1337*s13^1663 + 9332596190*s13^3000 + 11715268045*s0^1663*s14^1337 + 9629029995*s1^1663*s14^1337 + 14947505789*s2^1663*s14^1337 + 8152503776*s3^1663*s14^1337 + 5302176038*s4^1663*s14^1337 + 6548034916*s5^1663*s14^1337 + 13921246170*s6^1663*s14^1337 + 2927768343*s7^1663*s14^1337 + 26319465079*s8^1663*s14^1337 + 3708931907*s9^1663*s14^1337 + 8030091692*s10^1663*s14^1337 + 13591681184*s12^1663*s14^1337 + 6041819681*s13^1663*s14^1337 + 13877873734*s0^1337*s14^1663 + 11640081093*s1^1337*s14^1663 + 706482481*s2^1337*s14^1663 + 6390743586*s3^1337*s14^1663 + 8528173189*s4^1337*s14^1663 + 14067335489*s5^1337*s14^1663 + 5192858417*s6^1337*s14^1663 + 4852555534*s7^1337*s14^1663 + 10688209628*s8^1337*s14^1663 + 10228654180*s9^1337*s14^1663 + 1066545393*s10^1337*s14^1663 + 11437626847*s11^1337*s14^1663 + 9781632742*s12^1337*s14^1663 + 7666861284*s13^1337*s14^1663 + 5411237564*s14^3000 + 4501935812*s0^1663*s15^1337 + 29156782774*s1^1663*s15^1337 + 2574969301*s2^1663*s15^1337 + 1383614560*s3^1663*s15^1337 + 581326061*s4^1663*s15^1337 + 13112476881*s5^1663*s15^1337 + 10596518533*s6^1663*s15^1337 + 14732231372*s7^1663*s15^1337 + 7013373934*s8^1663*s15^1337 + 4319617103*s9^1663*s15^1337 + 4565038161*s10^1663*s15^1337 + 6965613233*s11^1663*s15^1337 + 14563766895*s12^1663*s15^1337 + 6662075350*s13^1663*s15^1337 + 3181982771*s14^1663*s15^1337 + 9424658377*s0^1337*s15^1663 + 5471894115*s1^1337*s15^1663 + 12434433948*s2^1337*s15^1663 + 8039687635*s4^1337*s15^1663 + 15304092194*s5^1337*s15^1663 + 11385145449*s6^1337*s15^1663 + 1437448683*s7^1337*s15^1663 + 5156674090*s8^1337*s15^1663 + 17835521891*s9^1337*s15^1663 + 4961499956*s10^1337*s15^1663 + 16554925377*s11^1337*s15^1663 + 12868498073*s12^1337*s15^1663 + 13414709669*s13^1337*s15^1663 + 16149582004*s14^1337*s15^1663 + 8516070520*s15^3000 + 48559899652124046039796571179246407240501267760540261250838491389170194280408607030984128797788766034966810674242338257952450081112973901792940997784978187259316658245065936959234848174845501162615111294500690452946004898544418199480160226352895187319814553931798835245453736242814477042568703369868424143683

đặt $a_i = s_i ^ {1337}$ và $b_i = s_i^{1663}$

ta được hệ như sau

7096123480*a0*b0 + 14738955324*a1*b0 + 18833012292*a2*b0 + 11720204181*a3*b0 + 11535479523*a4*b0 + 2369557661*a5*b0 + 15035119578*a6*b0 + 13245566255*a7*b0 + 11481970086*a8*b0 + 10016530899*a10*b0 + 7971877110*a11*b0 + 3639716839*a12*b0 + 7416423743*a13*b0 + 11715268045*a14*b0 + 4501935812*a15*b0 + 13783066574*a0*b1 + 7550523976*a1*b1 + 10560142961*a2*b1 + 7122636976*a3*b1 + 10887059948*a4*b1 + 4801400834*a5*b1 + 11339061691*a6*b1 + 7109461771*a7*b1 + 6904666833*a8*b1 + 1585751421*a9*b1 + 16449919177*a10*b1 + 3911306518*a11*b1 + 13360677145*a12*b1 + 15694724200*a13*b1 + 9629029995*a14*b1 + 29156782774*a15*b1 + 10935212851*a0*b2 + 7480678582*a1*b2 + 8706145996*a2*b2 + 13649446032*a3*b2 + 3699101816*a4*b2 + 18330184715*a5*b2 + 6388849293*a6*b2 + 16702788955*a7*b2 + 9072196191*a8*b2 + 1906504569*a9*b2 + 5882361488*a10*b2 + 10594780372*a11*b2 + 1705968207*a12*b2 + 2139761605*a13*b2 + 14947505789*a14*b2 + 2574969301*a15*b2 + 9806006309*a0*b3 + 10040381586*a1*b3 + 13439368664*a2*b3 + 4334996378*a3*b3 + 3942587364*a4*b3 + 13520834445*a5*b3 + 3432893461*a6*b3 + 6613491330*a7*b3 + 8971865939*a8*b3 + 8404452245*a9*b3 + 7532598444*a10*b3 + 1515015663*a11*b3 + 13093703635*a12*b3 + 16411378918*a13*b3 + 8152503776*a14*b3 + 1383614560*a15*b3 + 12691854224*a0*b4 + 10874080576*a1*b4 + 7322958729*a2*b4 + 5772391950*a3*b4 + 10854615428*a4*b4 + 9847351608*a5*b4 + 10793037006*a6*b4 + 14757363563*a7*b4 + 5609561124*a8*b4 + 37499922*a9*b4 + 20324536629*a10*b4 + 12995801747*a11*b4 + 13715315585*a12*b4 + 14492011189*a13*b4 + 5302176038*a14*b4 + 581326061*a15*b4 + 13759138067*a0*b5 + 2712565691*a1*b5 + 10184626319*a3*b5 + 1498119998*a4*b5 + 14589011532*a5*b5 + 14122768224*a6*b5 + 6987479437*a7*b5 + 9957664637*a8*b5 + 8443121340*a9*b5 + 10123884088*a10*b5 + 12761437344*a11*b5 + 4933969890*a12*b5 + 4053263384*a13*b5 + 6548034916*a14*b5 + 13112476881*a15*b5 + 11113199844*a0*b6 + 6131785471*a1*b6 + 8980686249*a2*b6 + 11214560990*a3*b6 + 5689650077*a4*b6 + 12390509712*a5*b6 + 10653001412*a6*b6 + 2233791464*a7*b6 + 6970832623*a8*b6 + 4355857861*a9*b6 + 1121821256*a10*b6 + 10571950940*a11*b6 + 4987551725*a12*b6 + 9914178487*a13*b6 + 13921246170*a14*b6 + 10596518533*a15*b6 + 10972103513*a0*b7 + 6834944159*a1*b7 + 6089711232*a2*b7 + 13434613823*a3*b7 + 8956016529*a4*b7 + 6203751829*a5*b7 + 15461538084*a6*b7 + 3693023618*a7*b7 + 4147791912*a8*b7 + 3238102810*a9*b7 + 6413696005*a10*b7 + 7037572284*a11*b7 + 7256015103*a12*b7 + 6037604930*a13*b7 + 2927768343*a14*b7 + 14732231372*a15*b7 + 14047260687*a0*b8 + 10281305551*a1*b8 + 4003357743*a2*b8 + 5716111707*a3*b8 + 6854845378*a4*b8 + 9910035037*a5*b8 + 8799282828*a6*b8 + 10210788101*a7*b8 + 9000166977*a8*b8 + 9238964859*a9*b8 + 7630282712*a10*b8 + 4814728567*a11*b8 + 5010185745*a12*b8 + 2727132074*a13*b8 + 26319465079*a14*b8 + 7013373934*a15*b8 + 9856850232*a0*b9 + 6675186922*a1*b9 + 7573975906*a2*b9 + 10227108674*a3*b9 + 5819442591*a4*b9 + 16108721868*a5*b9 + 9520191764*a6*b9 + 5958453080*a7*b9 + 9933966874*a8*b9 + 12042985316*a9*b9 + 8747676938*a10*b9 + 9766238489*a11*b9 + 5366082169*a12*b9 + 6293204738*a13*b9 + 3708931907*a14*b9 + 4319617103*a15*b9 + 4101646851*a0*b10 + 7871715399*a1*b10 + 3682112466*a2*b10 + 3877474298*a3*b10 + 5546344565*a4*b10 + 4839377643*a5*b10 + 9897812593*a6*b10 + 3176709610*a7*b10 + 4629763663*a8*b10 + 2193920044*a9*b10 + 4456697305*a10*b10 + 11973981372*a11*b10 + 4816001788*a12*b10 + 12645136642*a13*b10 + 8030091692*a14*b10 + 4565038161*a15*b10 + 1660809597*a0*b11 + 11933772507*a1*b11 + 2204098596*a2*b11 + 4479355763*a3*b11 + 4230517324*a4*b11 + 7725873794*a5*b11 + 2684412696*a6*b11 + 4096892300*a7*b11 + 4217161886*a8*b11 + 9170313905*a9*b11 + 19327018074*a10*b11 + 3378391230*a11*b11 + 5726830982*a12*b11 + 1590556769*a13*b11 + 6965613233*a15*b11 + 2015567489*a0*b12 + 12853659250*a1*b12 + 14108803655*a2*b12 + 12795910069*a3*b12 + 4583422372*a5*b12 + 10849635660*a6*b12 + 7406887668*a7*b12 + 10825960057*a8*b12 + 10831173109*a9*b12 + 649129198*a10*b12 + 14852938908*a11*b12 + 6345360937*a12*b12 + 4205282613*a13*b12 + 13591681184*a14*b12 + 14563766895*a15*b12 + 19413262817*a0*b13 + 15226340691*a1*b13 + 4015318904*a2*b13 + 7312372213*a4*b13 + 5530413935*a5*b13 + 1759105465*a6*b13 + 7875916478*a7*b13 + 10061764203*a8*b13 + 5586826295*a9*b13 + 17101618944*a10*b13 + 5944822711*a11*b13 + 13207411312*a12*b13 + 9332596190*a13*b13 + 6041819681*a14*b13 + 6662075350*a15*b13 + 13877873734*a0*b14 + 11640081093*a1*b14 + 706482481*a2*b14 + 6390743586*a3*b14 + 8528173189*a4*b14 + 14067335489*a5*b14 + 5192858417*a6*b14 + 4852555534*a7*b14 + 10688209628*a8*b14 + 10228654180*a9*b14 + 1066545393*a10*b14 + 11437626847*a11*b14 + 9781632742*a12*b14 + 7666861284*a13*b14 + 5411237564*a14*b14 + 3181982771*a15*b14 + 9424658377*a0*b15 + 5471894115*a1*b15 + 12434433948*a2*b15 + 8039687635*a4*b15 + 15304092194*a5*b15 + 11385145449*a6*b15 + 1437448683*a7*b15 + 5156674090*a8*b15 + 17835521891*a9*b15 + 4961499956*a10*b15 + 16554925377*a11*b15 + 12868498073*a12*b15 + 13414709669*a13*b15 + 16149582004*a14*b15 + 8516070520*a15*b15 + 48559899652124046039796571179246407240501267760540261250838491389170194280408607030984128797788766034966810674242338257952450081112973901792940997784978187259316658245065936959234848174845501162615111294500690452946004898544418199480160226352895187319814553931798835245453736242814477042568703369868424143683

do ta chỉ có 64 ẩn và có tới 256 phương trình (ngoài ra các phương trình này khá "nhỏ") nên ta có thể sử dụng groebner basis để đưa về các hệ đơn giản hơn.

Khi đó ta được các hệ như sau:

eq = [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 ,
]

khi đó ta có thể dễ dàng tính lại các $a_i$ và $b_i$ rồi tìm lại flag một cách dễ dàng.

from out import p, output
from tqdm import *

proof.arithmetic(False)  # Tắt chứng minh để tăng tốc
RR = PolynomialRing(GF(p), [f"a{i}" for i in range(16)] + [f"b{i}" for i in range(16)])
sss = list(RR.gens())
aa = sss[:16]
bb = sss[16:]
a0, a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15 = aa
b0, b1, b2, b3, b4, b5, b6, b7, b8, b9, b10, b11, b12, b13, b14, b15 = bb

def parse_polynomial_with_substitution(text):

    terms = text
    for i, j in enumerate(F.gens()):
        terms = terms.replace(str(j ^ 1337), str(aa[i]))
        terms = terms.replace(str(j ^ 1663), str(bb[i]))
        terms = terms.replace(str(j ^ 3000), str(aa[i] * bb[i]))

    return eval(terms)

F = PolynomialRing(GF(p), 's', 16)
setup = F.gens()

eq = []

for _ in trange(256):

    o = output[6 * (_): 6 * (_ + 1)]
    noise1 = o[0]
    noise2 = o[1]
    noise3 = o[2]
    noise4 = o[3]
    noise5 = o[4]
    s_ = o[5]
    s = -s_
    for i in range(1000):
        s += (noise5[i] * (noise1[i] + pow(setup[noise2[i]], 1337) * pow(setup[noise3[i]], 1663)) + noise4[i])
    __ = (parse_polynomial_with_substitution(str(s)))

    eq.append(__)

I = ideal(eq)
for i in (I.groebner_basis()):
    print(i)

from sympy.ntheory.residue_ntheory import sqrt_mod

p = 127323918397150316495247800323239736951569445082942285169375292888159697258810514666685622809992817021336278127866745453118097667246223924313578829332502944435638227372399940204655893575649137109219740460943073519414196371116575629581737876660746420422214171896457055383594285868200602684084613842337701236613
k = -86119204666031778361132131538654988592326775231468800432934056629778577889530001825242000398790179830855620730526747366361857281443237003652942326626408419191346322771074668794688002257406764223811918592844662007822581591276059250739169915614756643680312405026412692864071890535780791147352585712854027431245

phi = p - 1
_a = pow(3000//8, -1, phi)
_b = pow(k, _a, p)

for a in sqrt_mod(_b, p, all_roots=True):
    for b in sqrt_mod(a, p, all_roots=True):
        for c in sqrt_mod(b, p, all_roots=True): 
            if c < (1 << 32):
                setup_0 = c

a15 = pow(setup_0, 1337, p)
a0  = (-103900091630338517113159682363020354834673093178208603338525971724633674416836534407494761030127719097640424629222104724835770538353514941509096452042015624989422783828417658210973565386799793111360509766152069398111700104543722778278789666682163094242232813342820456471977751899841362780235032867651086598776*a15) % p
a1  = (-94782593698022117811595741482319129956155198805414720462016242116623766911080216671486293956814996499207687684455205150878100119889366386083556456522054683377186501281256906568938546584809966096271538691815114215079239388496886641239813923815517441946581125375641585275336613687378494679209334894515748636137*a15) % p
a2  = (-29781328395362878010559972753928770820525547754735872300852534399931754382685254280726765681238719682821543179952466959015772927564601108064714668031532965462626720317649979903593364568071841547185568870316973491550811260686711860979161486279494470557050523209387400350555591302866075368939996204225068091231*a15) % p
a3  = (-42514568004702292296496446073890971461433627646024949037425788654888156253824159852754025903510747699895075702374722459742318014536634879996010101878697748587903010326510596734217371944846744853981413300364470153590995446987366739221951743043580156798033589461285382892878800209800287072424410796171383447580*a15) % p
a4  = (-104847499719235908329095063182318007610120286076264897937782889283466191436226502122105139369082067964764791882450665260396955668067288436637798185063068858671202289836612240592434361174077161993798886976242227091852921248759179720140104213821226607894451285293115562099407619373008805830627220791440511188773*a15) % p
a5  = (-857632708832169524649890569725458117131396427051496219603884996631981937443816327414350072800244351854787034229003195742437216705733262740869008672494422267659611235074928450500751761129690044049115111078942754864955525689697275922047774854005413084995504089865080812937882029302148328589095802559382779599*a15) % p
a6  = (-19959578203238765973999117072419572480483698112921132023594196768854961150172116412984497415714529093542991448705093842226361393891054000138450033706429410688510170120499064026502400198887175854588966521142193851370976805538103740571905253171735179613120705021061333391972946645921126086143564822642114488953*a15) % p
a7  = (-16932878932543870913732698042666318123669617199819533389821843536336735743890558169688532455077837524711101781920236432246957934382182647062090431592033960194174334877839169453259846647785564691181574547741751351243650286476791247542941085703315395592945093585658435161223120293512374600743903950658137229920*a15) % p
a8  = (-15479008526193966082012114686270132380273829670073329659978323666780320718109393225338159572626600409052560195584520002587798885234641500899816376630146996252983000996071630875751896022326206968405493063289491284215113793986616555999131799074939208861260553388992555700348127263065469614695035477945466997258*a15) % p
a9  = (-120472187316264035473413477097936733929894302361699354385182636147680713296660012568581356627070370499298911997790399956471573274950568401062289369876834842342599813238312293293669635811905915984005147587448999901798478072696426562353518994765480832272784117366537221261307078614807717761808419640233966630143*a15) % p
a10 = (-69238436947108827901154466321317357276492402135764977168328945151485080291829140635452518847692166480338648587917747196854159209223222357719347746676915977322027034686402477802670104597582828224335045374125016246868641764804911447607379445762008617075103705661266441611765294615364706206778684881990808554619*a15) % p
a11 = (-101820908694507446580717304326343569799882240473391612693965078212786521692310170985457783066604818046666603631829424794683313331821509554751860860574103150993927086461872132826693697290995254840734051245163649645546338995564384203510881767822410562618591733217049019320588582622609182394860736073158752673565*a15) % p
a12 = (-100155125642150340856700284444173781643525348881314314309769150316567367348390022207449078538431863073950386299479477593450621292680074817033713616266902364695281623526246411178483266430527926187327284536067153245949831657612542502379654678598665434170393462839343598650050559031953675368939289420388815370706*a15) % p
a13 = (-123280244404659171752758029970974388206633652163296981653447667262971850946859997526942861556135249495679678825887385409879620652161263565992801137840937254615969737099574232088068618348800948949865571474485840690172888401692148686518002871413132915405509946337680715499486661623590696018430606215247042556730*a15) % p
a14 = (-77561516189612536414626404512808990437227045945814442134885015895022626948197080737310876317683541004442210645564472187683687047563055266473286718260840144361100023736999714524439910381556594437791101932912686292570644062205322916504568490183569196404676847123738255744312377748689429891861986026520862310842*a15) % p
flag = b""

for i in [a0, a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15]:
    
    i = pow(i, pow(1337, -1, p - 1), p)
    flag += bytes([int(i) % 256])
    
print(flag)

#### 3. stranger things

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]

- flag được được thành phần tử trong trường GF(p^3) và do có seed nên ta cũng có luôn a và b. Ta có hệ số bị dịch 57 bit của s sau mỗi vòng cộng.

+ với a, b, c là các số nguyên trong $GF(p)$ ta có

F.<a, b, c> = PolynomialRing(Fp)
s = a + b * x + c * x ^ 2

sage: p = 12267883553178394373
sage: Fp = GF((p, 3))
sage: x = Fp.gen()
sage: Fp.modulus()                                                            
x^3 + 6051502788270824690*x^2 + 1658644780344182767*x + 12267883553178394370            

với $F_p = (Z/pZ[x])/ (x^3 + 6051502788270824690*x^2 + 1658644780344182767*x + 12267883553178394370 )$

Khi đó ta có:

$\to x^3 + 6051502788270824690*x^2 + 1658644780344182767*x + 12267883553178394370 = 0\text{ in }F_p$

$\to x^3 = -6051502788270824690*x^2 - 1658644780344182767*x - 12267883553178394370\text{ in }F_p$

giả sử ta có hai đa thức là:

+ $f = a + bx + cx^2$
+ $g = d + ex + dx^2$

khi đó $f * g = (a + bx + cx^2) * (d + ex + dx^2)$

trong đó $x^3 = -6051502788270824690*x^2 - 1658644780344182767*x - 12267883553178394370$

$x^4 = x * (-6051502788270824690*x^2 - 1658644780344182767*x - 12267883553178394370)$
$\to x^4 = -6051502788270824690*(-6051502788270824690*x^2 - 1658644780344182767*x - 12267883553178394370) - 1658644780344182767*x^2 - 12267883553178394370*x$

ta thực hiện việc nhân cho tới khi đa thức trở nên tối giản và không thể rút gọn được nữa.

Quay lại thử thách trên, ta có thể thấy sau mỗi vòng nhân vào thì ta có kết quả dạng như sau:

(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

Đây là kết quả của lần tính giá trị `s` đầu tiên.

Thực hiện viết lại các hệ số như sau:

(3979752675954023529*a0 + 8753986609264543289*b0 + 5543455650548838382*c0 + 10472345338873147245) + (10557248725682989278*a0 + 3815924565230295538*b0 + 7344609725201457733*c0 + 10321418373171877975) * x + (11096584571873777345*a0 + 5937113067909077585*b0 + 9100459316456747575*c0 + 5644891284203893353) * x^2

khi đó ta có thể thấy

(3979752675954023529*a0 + 8753986609264543289*b0 + 5543455650548838382*c0 + 10472345338873147245) mod p >> 57 = output[0]

(10557248725682989278*a0 + 3815924565230295538*b0 + 7344609725201457733*c0 + 10321418373171877975) mod p >> 57 = output[1]

(11096584571873777345*a0 + 5937113067909077585*b0 + 9100459316456747575*c0 + 5644891284203893353) mod p >> 57 = output[2]

Thực hiện tương tự với các lần tiếp theo.

Ta thấy đây là một hàm tuyến tính cùng với việc đã biết các high bit của kết quả ta có thể đưa về ma trận để tính lại a, b, c. Sử dụng code solve linear có sẵn là ta dễ dàng có được flag.

import os
from Crypto.Util.number import bytes_to_long, getPrime
"""
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!
"""

from collections.abc import Sequence
import math
import operator
from typing import List, Tuple
from sage.all import ZZ, gcd, matrix, prod, var


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()

F.<a, b, c> = PolynomialRing(Fp)
s = a + b * x + c * x ^ 2

set_random_seed(1337)
out = []

for i in range(15):
    ka, kb = Fp.random_element(), Fp.random_element()

    s = ka * s + kb

    out.append(s)

var("a0 b0 c0")
M = []

for i in out:
    m = [0, 0, 0]
    k = i.coefficients()
    k = [x.list() for x in k]

    m[0] += int(k[0][0]) * a0
    m[0] += int(k[1][0]) * b0
    m[0] += int(k[2][0]) * c0
    
    m[1] += int(k[0][1]) * a0
    m[1] += int(k[1][1]) * b0
    m[1] += int(k[2][1]) * c0
    
    m[2] += int(k[0][2]) * a0
    m[2] += int(k[1][2]) * b0
    m[2] += int(k[2][2]) * c0
    
    m[0] += int(k[3][0])
    m[1] += int(k[3][1])
    m[2] += int(k[3][2])
    

    for _ in m:
        M.append(_)
        
var(" ".join([f"m{i}" for i in range(45)]))
ms = [m0, m1, m2, m3, m4, m5, m6, m7, m8, m9, m10, m11, m12, m13, m14, m15,
        m16, m17, m18, m19, m20, m21, m22, m23, m24, m25, m26, m27, m28,
        m29, m30, m31, m32, m33, m34, m35, m36, m37, m38, m39, m40,
        m41, m42, m43, m44]
eq = []

o = [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]

o = [x << 57 for x in o]

for i in range(45):
    e += M[i]
    eq.append([M[i] == o[i] + ms[i], p])
    
bound = {}
for i in range(45):
    bound[ms[i]] = (0, 2**57)
bound[a0] = (0, p)
bound[b0] = (0, p)
bound[c0] = (0, p)

from Crypto.Util.number import *
tmp = (solve_linear_mod(eq, bound))

print(long_to_bytes(tmp[a0] + tmp[b0] * p + tmp[c0] * p * p))