# Steps

from Crypto.Util.number import getPrime
from random import randint
from hashlib import sha512
from secret import FLAG

p = getPrime(1024)

Pair = tuple[int, int]

def apply(x: Pair, y: Pair) -> Pair:
    z0 = x[0] * y[1] + x[1] * y[0] - x[0] * y[0]
    z1 = x[0] * y[0] + x[1] * y[1]
    return z0 % p, z1 % p

def calculate(n: int) -> Pair:
    out = 0, 1
    base = 1, 1

    while n > 0:
        if n & 1 == 1: out = apply(out, base)
        n >>= 1
        base = apply(base, base)

    return out

def step(x: Pair, n: int):
    '''Performs n steps to x.'''
    return apply(x, calculate(n))

def xor(a: bytes, b: bytes) -> bytes:
    return bytes(i ^ j for i, j in zip(a, b))

def main() -> None:
    g = tuple(randint(0, p - 1) for _ in range(2))
    a = randint(0, p)
    b = randint(0, p)

    A = step(g, a)
    B = step(g, b)

    print(p)
    print(g)
    print(A)
    print(B)

    shared = step(A, b)
    assert shared == step(B, a)

    pad = sha512(str(shared).encode()).digest()
    print(xor(FLAG, pad))

if __name__ == "__main__":
    main()

140323158913416495607520736187548995477774864895449373468435168606940894555091715325755245563618777520381345121826124291879072024129139794758353829170487152290036863771427918014687523291663877491666410660298255515196964873944928956895167652588843616727666115196647426152811435167407394960435891152283442366721
(96065253104055475368515351480749372850658086665031683689391433619786525841252022013348418216780129963411710917302022475212035579772549622047772413277044476931991100469638284113901919733675144788049607999711496364391389612383885735460390196619821411998848060208912802838145365054170790882835846039461477718592, 99241616571709523646659145402511086659276737895777010655080069795289409091105858433710404513588065826008320709508748555232998727290258965620812790826701703542423766306117851146140634247906095481346444357123297761881438234083584836393572339820023598801127329326758926529813665950889866710376403818615042210724)
(70755695722452190644681854912493449110123792967984325777144153291795297730471865203878351550134745747839905472832417565386100721034554991782211134122667955909129461935072670637104557733518048519759925441567454988894610693095988261459294358350906447578625319131211019007537053689563772428590632011546870587548, 67209626648557152207459211543890871397518255584981755641031188457446084495247511864090204533159666638951190009379067537952490757956859052998865712873197974689323985952177932343928382624951392835548222455898153557185369330197085287972647654361464363270469055087587755117442462138962625643131163131541853061105)
(112356264561144892053527289833892910675229600209578481387952173298070535545532140474473984252645999236867287593260325203405225799985387664655169620807429202440801811880698414710903311724048492305357174522756960623684589130082192061927190750200168319419891243856185874901350055033712921163239281745750477183871, 53362886892304808290625786352337191943295467155122569556336867663859530697649464591551819415844644455424276970213068575695727349121464360678240605137740996864232092508175716627306324344248722088013523622985501843963007084915323781694266339448976475002289825133821073110606693351553820493128680615728977879615)
b'\xbaH\xca[V\xdf\xbb0d2jN"\x9d$e\xec\xe0M\x00\xdb\xf0\x8f\x99f\xc5\n\x8a\xc2h\xa7\xa7'

## Solve

def step(x: Pair, n: int):
    '''Performs n steps to x.'''
    return apply(x, calculate(n))

Như ta thấy thì hàm step thực chất là hàm apply nhưng thêm bước tính toán n , với n là `key` , và kết quả của `caculate(n)` sẽ là 2 số mà mình chưa biết .

def apply(x: Pair, y: Pair) -> Pair:
    z0 = x[0] * y[1] + x[1] * y[0] - x[0] * y[0]
    z1 = x[0] * y[0] + x[1] * y[1]
    return z0 % p, z1 % p

Và hàm apply sẽ đem 2 số đó đi cộng trừ nhân chia gì đó và trả cho mình 2 giá trị , giờ đây ta coi `caculate(n)` là 2 ẩn x1 , x2 với 2 phương trình đã có -> Giải 2 phương trình 2 ẩn -> có được `caculate(n)` -> apply nó cho `B` -> Có được `Key` -> Done
> Script :

from Crypto.Util.number import *
from math import gcd
p = 140323158913416495607520736187548995477774864895449373468435168606940894555091715325755245563618777520381345121826124291879072024129139794758353829170487152290036863771427918014687523291663877491666410660298255515196964873944928956895167652588843616727666115196647426152811435167407394960435891152283442366721
g = (96065253104055475368515351480749372850658086665031683689391433619786525841252022013348418216780129963411710917302022475212035579772549622047772413277044476931991100469638284113901919733675144788049607999711496364391389612383885735460390196619821411998848060208912802838145365054170790882835846039461477718592, 99241616571709523646659145402511086659276737895777010655080069795289409091105858433710404513588065826008320709508748555232998727290258965620812790826701703542423766306117851146140634247906095481346444357123297761881438234083584836393572339820023598801127329326758926529813665950889866710376403818615042210724)
A = (70755695722452190644681854912493449110123792967984325777144153291795297730471865203878351550134745747839905472832417565386100721034554991782211134122667955909129461935072670637104557733518048519759925441567454988894610693095988261459294358350906447578625319131211019007537053689563772428590632011546870587548, 67209626648557152207459211543890871397518255584981755641031188457446084495247511864090204533159666638951190009379067537952490757956859052998865712873197974689323985952177932343928382624951392835548222455898153557185369330197085287972647654361464363270469055087587755117442462138962625643131163131541853061105)
B = (112356264561144892053527289833892910675229600209578481387952173298070535545532140474473984252645999236867287593260325203405225799985387664655169620807429202440801811880698414710903311724048492305357174522756960623684589130082192061927190750200168319419891243856185874901350055033712921163239281745750477183871, 53362886892304808290625786352337191943295467155122569556336867663859530697649464591551819415844644455424276970213068575695727349121464360678240605137740996864232092508175716627306324344248722088013523622985501843963007084915323781694266339448976475002289825133821073110606693351553820493128680615728977879615)
cipher = b'\xbaH\xca[V\xdf\xbb0d2jN"\x9d$e\xec\xe0M\x00\xdb\xf0\x8f\x99f\xc5\n\x8a\xc2h\xa7\xa7'
from sage.all import *
P.<x,y> = PolynomialRing(Zmod(p))
f1 = g[0] *y + g[1]* x - g[0] * x - A[0]
f2 = g[0] * x + g[1] * y - A[1]
I = Ideal([f1,f2]).variety()
x = I[0]['x']
y = I[0]['y']
from hashlib import sha512
Pair = tuple[int, int]
def apply(x: Pair, y: Pair) -> Pair:
    z0 = x[0] * y[1] + x[1] * y[0] - x[0] * y[0]
    z1 = x[0] * y[0] + x[1] * y[1]
    return z0 % p, z1 % p
key = (x,y)
key = apply(B,key)
pad = sha512(str(key).encode()).digest()
print(pad)
from pwn import xor
print(xor(pad,cipher))

Flag : ```corctf{w4it_i7's_4ll_f1b0n4cci?}```
# monkfish

#!/usr/bin/sage

import sys
print("I caught a monkfish in the sea! ")
sys.stdout.flush()

from hashlib import sha256
from Crypto.Util.number import bytes_to_long
from random import SystemRandom
import ast

n = 100
m = 100
q = 5
FF.<x> = GF(q)


def apply(F, v):
    out = []
    for i in range(m):
        out.append((v.T * F[i] * v)[0, 0])
    return matrix(FF, m, 1, out)

def apply_verif_info(F, a, b):
    out = []
    for i in range(m):
        out.append((a.T * (F[i] + F[i].T) * b)[0, 0])
    return matrix(FF, m, 1, out)

def create_pok(v, s, F):
    t = matrix(FF, n, 1, [FF.random_element() for i in range(n)])
    com = apply(F, t)
    verif = apply_verif_info(F, t, s)
    a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
    print(f'{a = }')
    return (com, t - a * s, verif)

def verif_pok(v, F, pi):
    com = pi[0]
    resp = pi[1]
    verif = pi[2]
    a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
    out1 = apply(F, resp)
    out2 = com + (a * a) * v - a * verif
    return out1 == out2

rng = SystemRandom()
gen_seed = []

for i in range(64):
    gen_seed.append(rng.randint(0, 255))

init_seed = gen_seed
gen_seed = b'I\xe5U\xd8\x12%\xda\xb3\xc1\x00\xfd%k\xbcj\x11\xcf\xd2\x1f-5\xb2\xddEt_\xee\xc9T/Du'
print(f'{gen_seed = }')
F = []

for i in range(m):
    cur = []
    for j in range(n):
        cur.append([])
        for k in range(n):
            cur[-1].append(list(FF)[sha256(gen_seed).digest()[0] % len(list(FF))])
            gen_seed = sha256(gen_seed).digest()
    F.append(matrix(FF, n, n, cur))


s = random_matrix(FF, n, 1)

v = apply(F, s)

pok = create_pok(v, s, F)


assert verif_pok(v, F, pok)

print("m0 =", [list(FF).index(i[0]) for i in list(pok[0])])
print("m1 =", [list(FF).index(i[0]) for i in list(pok[1])])
print("m2 =", [list(FF).index(i[0]) for i in list(pok[2])])

print("Can you catch a monkfish? ")
print("seed =", [int(i) for i in init_seed])
print("v =", [list(FF).index(i[0]) for i in v])
print(list(FF))
m0 = [int(i)  for i in ast.literal_eval(input("m0 = "))]
print(m0)
m1 = [int(i) for i in ast.literal_eval(input("m1 = "))]
m2 = [int(i) for i in ast.literal_eval(input("m2 = "))]

assert(m0 != [list(FF).index(i[0]) for i in list(pok[0])])
assert(m1 != [list(FF).index(i[0]) for i in list(pok[1])])
assert(m2 != [list(FF).index(i[0]) for i in list(pok[2])])

m0 = matrix(FF, m, 1, [list(FF)[i] for i in m0])
m1 = matrix(FF, n, 1, [list(FF)[i] for i in m1])
m2 = matrix(FF, m, 1, [list(FF)[i] for i in m2])
pi = (m0, m1, m2)

res = verif_pok(v, F, pi)
assert res == True

with open("flag.txt", "r") as f:
    print(f.read())

## Solve
Bài này mục tiêu của ta là gửi bộ `m0,m1,m2` sao cho thỏa mãn yêu cầu `verify` của đề bài , nhưng để làm được điểu đó thì ta cần phải có `s` tức `private key` :smiley:
Lúc đầu mình đã định giải s dựa vào `(v.T * F[i] * v)` vì s có 100 ẩn mà mình có 100 thằng `F` tức là 100 phương trình mình có 100 ẩn đúng không nào . Nghe chừng có vẻ khả thi nhưng nó khá no hope bơỉ vì phương trình nó khá phức tạp , mình thừ dùng `Ideal, Gro Basis` nhưng đều vô dụng :confused:
Xong rồi mình nhìn nhiều solve quá nên nghĩ nó không phức tạp đến vậy nên ngồi đọc lại code :disappointed_relieved: và mình đọc kỹ dòng này :

m0 = matrix(FF, m, 1, [list(FF)[i] for i in m0]

Ở đây các giá trị `i` của `m0` sẽ không lấy các giá trị `i` trong `m0` mà sẽ lấy giá trị tại `FF(i)` , tức là giờ nếu 1 giá trị m0 gốc có giá trị là 3 , thì mình gửi lên giá trị tương ứng là -2 thì nó sẽ vẫn là giá trị đó .
Ví dụ :

a = list(FF) # a = [0,1,2,3,4]
m0_true = [2]
m0_fake = [2-len(a)]
assert a[m0_true[0]] == a[m0_fake[0]]

Tương tự như vậy thì mình sẽ lấy các giá trị của `m0,m1,m2` mà mình nhận được rồi trừ đi cho `q` là mình sẽ bypass được hàm check của nó và gửi lại được các `m0,m1,m2` cũ để có thể `verify` được

assert(m0 != [list(FF).index(i[0]) for i in list(pok[0])])

Khá may mắn là nó không ép các giá trị m0 mình gửi lên về trường `GF(5)` nên cách làm này mới thực hiện được .

from pwn import *
import ast
from hashlib import sha256
from Crypto.Util.number import bytes_to_long
from random import SystemRandom


n = 100
m = 100
q = 5

F = []
io = remote("be.ax", 31105)
def recv_array() :
    m = io.recvline()[:-1].decode()
    m = m.split('=')[1].strip()
    m = ast.literal_eval(m)
    return m

print(io.recvline())
m0 = recv_array()
m1 = recv_array()
m2 = recv_array()
print(io.recvline())
seed = recv_array()
v = recv_array()
gen_seed = bytes(seed)
m0 = [i-q for i in m0]
m1 = [i-q for i in m1]
m2 = [i-q for i in m2]

m0 = ','.join(map(str, m0))
m1 = ','.join(map(str, m1))
m2 = ','.join(map(str, m2))


io.sendline(m0.encode())
io.sendline(m1.encode())
io.sendline(m2.encode())
io.interactive()

Flag : ```corctf{dont_forget_the_soundness_error}```
# anglerfish

#!/usr/bin/sage

import sys
print("I caught an anglerfish in the sea! ")
sys.stdout.flush()

from hashlib import sha256
from Crypto.Util.number import bytes_to_long
from random import SystemRandom
import ast

n = 100
m = 100
q = 5
FF.<x> = GF(q)

def apply(F, v):
    out = []
    for i in range(m):
        out.append((v.T * F[i] * v)[0, 0])
    return matrix(FF, m, 1, out)

def apply_verif_info(F, a, b):
    out = []
    for i in range(m):
        out.append((a.T * (F[i] + F[i].T) * b)[0, 0])
    return matrix(FF, m, 1, out)

def create_pok(v, s, F):
    proofs = []
    for i in range(64):
        t = matrix(FF, n, 1, [FF.random_element() for i in range(n)])
        com = apply(F, t)
        verif = apply_verif_info(F, t, s)
       
        a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
       
        proofs.append((com, t - a * s, verif))
    return proofs

def verif_pok(v, F, pis):
    coms = []
    for pi in pis:
        com = pi[0]
        assert com not in coms
        coms.append(com)
        resp = pi[1]
        verif = pi[2]
        a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
        out1 = apply(F, resp)
        out2 = com + (a * a) * v - a * verif
        assert out1 == out2

rng = SystemRandom()
gen_seed = []

for i in range(64):
    gen_seed.append(rng.randint(0, 255))

init_seed = gen_seed
gen_seed = bytes(gen_seed)

F = []

for i in range(m):
    cur = []
    for j in range(n):
        cur.append([])
        for k in range(n):
            cur[-1].append(list(FF)[sha256(gen_seed).digest()[0] % len(list(FF))])
            gen_seed = sha256(gen_seed).digest()
    F.append(matrix(FF, n, n, cur))

s = random_matrix(FF, n, 1)

v = apply(F, s)

pok = create_pok(v, s, F)

verif_pok(v, F, pok)

for pi in pok:
    print("m0 =", [list(FF).index(i[0]) for i in list(pi[0])])
    print("m1 =", [list(FF).index(i[0]) for i in list(pi[1])])
    print("m2 =", [list(FF).index(i[0]) for i in list(pi[2])])

print("Can you catch an anglerfish? ")
print("seed =", [int(i) for i in init_seed])
print("v =", [list(FF).index(i[0]) for i in v])

pis = []
for x in range(64):
    m0 = [int(i) for i in ast.literal_eval(input("m0 = "))]
    m1 = [int(i) for i in ast.literal_eval(input("m1 = "))]
    m2 = [int(i) for i in ast.literal_eval(input("m2 = "))]

    for pi in pok:
        assert(m0 != [list(FF).index(i[0]) for i in list(pi[0])])
        assert(m1 != [list(FF).index(i[0]) for i in list(pi[1])])
        assert(m2 != [list(FF).index(i[0]) for i in list(pi[2])])

    m0 = matrix(FF, m, 1, [list(FF)[i] for i in m0])
    m1 = matrix(FF, n, 1, [list(FF)[i] for i in m1])
    m2 = matrix(FF, m, 1, [list(FF)[i] for i in m2])

    assert m0 not in [pi[0] for pi in pok]
    assert m1 not in [pi[1] for pi in pok]
    assert m2 not in [pi[2] for pi in pok]

    pi = (m0, m1, m2)
    pis.append(pi)

verif_pok(v, F, pis)

with open("flag.txt", "r") as f:
    print(f.read())

## Solve
Bài này thì nó bảo mật hơn bài trước rồi , giờ đây ta không thử gửi các bộ `m0,m1,m2` cũ như trên nữa do có sự xuất hiện của câu lệnh check thử hai .

assert m0 not in [pi[0] for pi in pok]

Thay vào đó lúc này ta lại có nhiều bộ `pok` hơn để ta có thể nghịch :smiley_cat:

def create_pok(v, s, F):
    proofs = []
    for i in range(64):
        t = matrix(FF, n, 1, [FF.random_element() for i in range(n)])
        com = apply(F, t)
        verif = apply_verif_info(F, t, s)
      
        a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
        
        proofs.append((com, t - a * s, verif))
    return proofs

Ở đây ta cần chú ý đến hàm `create_pok` với các output của nó với :

t là random matrix
com = t.T*F*t 
verif = t.T*(F+F.T)*s
x = t - a*s

Như ta thấy thì ``` a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]``` là cái ta có thể recover lại được , từ việc biết đủ các dữ kiện từ `com,v,verif`
Mà a chỉ chạy từ `0->4` thì trong 64 trường hợp ta có thì sẽ tồn tại 1 trường hợp mà `a==0` tức lúc này `x==t` -> Lấy được `t`
Mà tại lại có ```verif = t.T*(F+F.T)*s```
Lúc này `F` ta hoàn toàn có thể recover lại do đã biết được `seed` từ server , tức giờ ta có phương trình ```verif = x*s``` với `x = t.T*(F+F.T)`
Lúc này ta chỉ cần `solve_right` là có thể tìm được `s` rồi tạo các bộ `m0,m1,m2` rồi gửi lên server là xong :smiley_cat:

from pwn import *
import ast
from hashlib import sha256
from Crypto.Util.number import bytes_to_long
from random import SystemRandom


n = 100
m = 100
q = 5

F = []
io = remote("be.ax",  "31106")
def recv_array() :
    m = io.recvline()[:-1].decode()
    m = m.split('=')[1].strip()
    m = ast.literal_eval(m)
    return m
pis = []
print(io.recvline())
for x in range(64) : 
    m0 = recv_array()
    m1 = recv_array()
    m2 = recv_array()
    pis.append((m0,m1,m2))

print(io.recvline())
seed = recv_array()
v = recv_array()
n = 100
m = 100
q = 5
FF.<x> = GF(q)

n = 100
m = 100
q = 5
FF.<x> = GF(q)


def apply(F, v):
    out = []
    for i in range(m):
        out.append((v.T * F[i] * v)[0, 0])
    return matrix(FF, m, 1, out)
def apply_verif_info(F, a, b):
    out = []
    for i in range(m):
        out.append((a.T * (F[i] + F[i].T) * b)[0, 0])
    return matrix(FF, m, 1, out)


def create_pok(v, s, F):
    proofs = []
    for i in range(64):
        t = matrix(FF, n, 1, [FF.random_element() for i in range(n)])
        com = apply(F, t)
        verif = apply_verif_info(F, t, s)
        # t.T*(F + F.T)*s
        a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
        proofs.append((com, t - a * s, verif))
    return proofs

gen_seed = bytes(seed)
F = []

for i in range(m):
    cur = []
    for j in range(n):
        cur.append([])
        for k in range(n):
            cur[-1].append(list(FF)[sha256(gen_seed).digest()[0] % len(list(FF))])
            gen_seed = sha256(gen_seed).digest()
    F.append(matrix(FF, n, n, cur))
v = Matrix(FF,v).transpose()
for z in range(len(pis)) :
    com = Matrix(FF,pis[z][0]).transpose()
    verif = Matrix(FF,pis[z][2]).transpose()
    a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
    if a == 0 :
        matrix_solve = []
        for lent in range(len(F)): 
            t = Matrix(FF,pis[z][1]).T
            
            tmp = t.T*(F[lent] + F[lent].T)
            matrix_solve.append(tmp.list())
        matrix_solve = matrix(FF,matrix_solve)
        tmp_vec = verif
        s = matrix_solve.solve_right(tmp_vec)
        s = matrix(FF,s)
        
        break
            # tmp0.1 , tmp0.2 ,.. tmp0.100 = ver[0]
            # tmp1.1 , tmo 1,2,..tmp1.100 = ver[1]
            #...
            # tmp99.1 ,tmp99.2,..tmp99.100 = ver[2]
pis = create_pok(v, s, F)

for pok in pis :
    
    io.sendline(str(pok[0].list()).encode())
    io.sendline(str(pok[1].list()).encode())
    io.sendline(str(pok[2].list()).encode())
    
io.interactive()

Flag : ```corctf{extra_equations_means_extra_information_isnt_zk}```
# Roots

from Crypto.Util.number import *
from random import getrandbits
from decimal import Decimal, getcontext
FLAG = b'corctf{extra_equations_means_extra_information_isnt_zk}'

N = 3
MSIZE = 64
PSIZE = 128

getcontext().prec = 2024

def chunk(inp: bytes, n: int) -> list[bytes]:
    return [inp[i:i + n] for i in range(0, len(inp), n)]

def generate() -> list[int]:
    return sorted(getPrime(PSIZE) for _ in range(N))

def otp(data: int) -> list[int]:
    key = [getrandbits(MSIZE) for _ in range(N - 1)]
    
    # Apply multiple times for extra security! ;)
    for k in key:
        data ^= k
    
    return key + [data]

def enc(data: int, key: list[int]) -> Decimal:
   
    return sum(a * Decimal(p).sqrt() for a, p in zip(otp(data), key))
    
def encrypt(plaintext: bytes, key: list[int]) -> Decimal:
    out = []
    for pt in chunk(plaintext, MSIZE // 8):
        out.append(enc(bytes_to_long(pt), key))

    return out

def main() -> None:
    key = generate()
    ct = encrypt(FLAG, key)

    print(ct)

if __name__ == "__main__":
    main()

Thật ra đây là 1 bài khá tiếc khi mình không giải được trong thời gian giải diễn ra , và đặc biệt khi nó giống một bài mình từng làm nưã :crying_cat_face:
Đầu tiên ta có các phương trình :
$out[0] = a_1*p_1 + a_2*p_2 + a_3*p_3$
$out[1] = a_4*p_1 + a_5*p_2 + a_6*p_3$
$out[2] = a_7*p_1 + a_8*p_2 + a_9*p_3$
$out[3] = a_{10}*p_1 + a_{11}*p_2 + a_{12}*p_3$
Giả sử mình tìm được `s1 , s2 , s3 , s4` sao cho $s1*o_1 + s2*o_2 + s3*o_3 + s4*o_4 == 0$ (o ở đây là output)
Lúc này tương đương : $p_1*(s_1*a_1 + s_2*a_4 + s_3*a_7 + s_4*a_{10}) + p_2*(s_1*a_2+s_2*a_5+s+3*a_8+s_4*a_{11}) + p_3*(s_1*a_3 + s_2*a_6 + s_3*a_9 + s_4*a_{12})$

Mà ta có $p_1,p_2,p_3 \ne 0$ nên phương trình trên bằng 0 khi và chỉ khi $(s_1*a_1 + s_2*a_4 + s_3*a_7 + s_4*a_{10}) == 0$
$(s_1*a_2+s_2*a_5+s_3*a_8+s_4*a_{11}) == 0$
$(s_1*a_3 + s_2*a_6 + s_3*a_9 + s_4*a_{12} == 0$
Vậy sau khi tìm được `s1,s2,s3,s4` bằng lattice , ta lại phải thêm 1 bài lattice nữa :crying_cat_face:
Nhưng mà giờ đây các output của mình không phải số nguyên nên không áp dụng ngay được mà phải nhân thêm bội số để biến nó về số nguyên để có thể áp dụng `LLL` .

Decimal = RealField(10000)
out = [Decimal('613865483278018068252699664344014709603.51690674693116605142775061636120046870769083140402021865687508441855022441399605307934286489840179576316516207824661811160477759304066064291205730622145206447227404607082151753919361349868545307462428210932437992623119255718054243534096986413211959304171135887211540587436459888779324151143025499619973135708235491605216411394962317959813656209629567607308778163987166821943423002154894970121188451784354115735408809579052563235078363998602200794840158081619720701643652284259066561050115602486569569690456649269369511972329349611423116985630502303784458447333880791258687570760036481989066910025496948546865951981177430643941260666483918647746947170525925083317666875914436471646901318749705595856856883346891726769074746650987330068104292614480104709810601198864073890537548001433033723615776224146304045036932985711688197452123005099236554526727107165691391180111605054039864164377438525310672107170437281478322426514683178129245151967154583110424925964982504343607726182942419964058684010006450471850408468724523024702559055514056791838218373955386876710426728739081458827252802226359687030921900842002785720726229892098824084346436742345912593840934579190526250607721076769764172513184565791506300616867803697312829413891917781663107526096475492046133891964020871514785931302212911910422061349227840920633130097807344731335384126657969326959305179863489255473137828869343169464391631468853227921632272791516165605848151467308601405844760824881338357444888188035204000407673339331919346899410420054651077086850532999310419256243385542853597931278472451318309939063364567112084455650629429599265528219435289213175349567467961574398181095962343974433190931067322110878499680729907288265465620467270493396020598011075090015918395921964211257921275263305336676548841001128867189130080538627211844161021733430009452985356108168888790283056201446152044771750329866340679923824523137794621308627512829896733426062792367679307468573465298446962647695970868442917945963296248995830871462803'), Decimal('245036407881857959287329830175942706463.41676802782442994887934627742200369945701412601647195354905097451178257098540606801565385675107318120460650888047274089786443222032370562593772359240722830861471549006005870906901656856743873456596259047367300567575908527230366385292440919562964298317812232800102576149495809413427952810634193186781922614214268017709482845572771078220390794231892763512491653218636267112852524278614145782738125962122310806946368712582799445479001874840170209715004731276988049273955290890839588161009103614134479683822558461311134193156291806539774288015592213012944114677791107334704048050248067790961044976635609645113466054839476916586971455181287563116833537875679872852426596500045916084590678852453213603747411621009244578584574321606967288315507350789499360210767971560504476491167021056575773203913674206412928683729647182751865762672106362511792516860263344700590671316013798899626125150168033775577935989491544189330151349377248071416776567110915867894841003988715963213282301539772548019203054604324657682585086974883293993693364621477765424253486620846417121914627069652179323747638053294808478946841684842391124370675090921956558456987438962361101647423473932215595029566302891192438202103166531605890363352381011015329475002801933772777494625189852526005526409489415563470356698119177369784245367090617016832725703245455210343971981483284742666226075984764682029024194412093587469973865623264825887838718407665448451327538641035583414835042280186524871430174844859199371418365330179156143049238655596474961217964906635309020982967098088279871772621354935094165104148277851308675528401723829872589324051699054275878133606165491429811386740566384976019587172015296076695877847670182335353621529186538640618471230538158759335554894682026973199860563823746052413212330496106907455577991532192244914548792485371507973770044500533179391911148716837049004674981572325374669719464763272448641196278444851808838959425053174592256179039838611577554410785172685506776747109456418706054407235309341'), Decimal('137345167246666152708695783992412451677.21558050568623481295196376367975242130555102201515580316330966697148890411534221923225952905285897183010922406175094262069208074739275097805536185634560982617648832780575658021059502299936366800046975825224832714908010519763833830348421655509168881358855533351044140363192436142763626456404652383592376546952793513967937938636543810723145564947948780573116974908526774605955951469943187865644596524139107481653386681950240101520692953876806620084423038367388560905871875836530739404184303742718262418117805718036122357051928716596276399762849629107495322882675719409051073299089695124393278836941013272789785477953131515760862594743832917404252472431732912434480355250761546326425334589230931109133966112698705631064298540629644087174339495451233415165784208154862632994746999100506080852291240231466075807689137982406781289386109243195384399444517321654449447540787541127685794368775611662723601685545144635953407926414192981817325925467123186823453700610674338813375219959042008201960857405988222431762449068615565770592161380029925528004633925411749903272512805896758350376028759094075163759541252996218647962921737695225607000672827355712319484834139082006323871120783473891599300315829557138141744616522321981481762618665822002496867084381222827633659627360022043393386819320488647893458122132426243653269827396864109912568570075611460793016682214280860824555257535036669613199445516497725227349649115460430628789851678786053832488469704975290639037623666238775508475503615248256142687325810589424170821237702234472583990907852983428072024771329547328770035145579513303770469872758505372515800860236159229593770017270383301142993264982903473737872532789578999358701823743117676045641159467315897055924399632998579024195194906804156820621748747515175782908138772828776041903750590418332731770693214602115172315637279313855936478443754676804416808777432960976763034716998360016818363826448918529745873789717604991019505220078545941396511331142324037841720139678985890298577830351331'), Decimal('248598813941244564314190366976956238846.21287154177193010973910605580779261210365984174749796180419923931211513873961571752231238459134695223104083276961569452018392982079324317136535206452261881826873414602629594471707660157457896214988591398626491707261264840694400878016171848489165321633160306766022332706508213328119352706170273262931280561423851178335709726505935522918272264480451898981178517451201483151591554008657960692345350455891365321593940275460890295306738282405071381298895783171740603832308867778448785711118127825021180253182388515151158156028351993831870085534975634188825697876813579914222802552156594566015228528827397850794636185597567790199750813063356917626291927109597628605896564415404785475255907843090500284371578116809505806089285850503289523274957689703557226650819188753255887580294403919233020671057076485044952433816771965385673494711771474126428651980119604119559562596188714862777544919355156232243652718517709528203262205358442941280815388198987743628689516005444663613668047007886122931571139930784688640045996582570962554713967405406762001906063378302125401898155550603489814135391137430186059041384496922239998747587303366147421038091369722510204804734395780572006815615350115111367222110517089689188974108653902029376056551397900019653419884380778042660817204485470749571339982927039079734483080043934563757326484950182811230031559346385457298240850154178951900739178353564235216322232791700369486112525607172179782914690610012323349746725297341069764127541218762893367556754429312136345943483494236203659704464226488931565438262759788872114208783818792121079840366002113316654063450919686404664767226446116187197107156555434824485171863955895656710114494285915504850382199832564322800850387423097212704670656698969249945269974571051395109564672354772654744585684053379753599154369914818372119637829894516195738013893515476266773802929361065238109305019468285763072333229080155510459572404321239788374283507107268753407976278020430629150787678790300001623259645896920037795093793915002')]
h = [int(i*10^1985) for i in out]
mat = matrix(ZZ, [
    [h[0] , 1, 0, 0, 0],
    [h[1] , 0, 1, 0, 0],
    [h[2] , 0, 0, 1, 0],
    [h[3] , 0, 0, 0, 1]
]).LLL()
s1,s2,s3,s4 = mat[0][1:]

mat = matrix(ZZ, [
    [s1 << 1000 ,1, 0, 0, 0],
    [s2 << 1000, 0, 1, 0, 0],
    [s3 << 1000, 0, 0, 1, 0],
    [s4 << 1000, 0, 0, 0, 1]
]).LLL()
print(list(mat))

[(0, -2704076375260901278, 2622843880913780206, 6495978242848471344, -666512641750303839), (0, 664302823439227080, -3490457635130658103, -2205946183691669711, -6440599186054658606), (0, -6728221938201536857, -2777926548143569583, -3523273592081980311, -352951208792993045), (10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376, 1764386526124214208, 2029201356714778765, 2646716099357679582, 1242236449097631309)]   

Theo như mình nghĩ thì kết quả phải là một bộ số đẹp cơ nhưng mà đời không như mơ :crying_cat_face: , nhưng không ảnh hưởng đến việc ta tìm tiếp các cặp $a$ thỏa mãn . Giờ đây ta xét ba hàng đầu , do 3 hàng đó có $0$ ở index 0 tức thỏa mãn điều kiện ta cần và thỏa mãn:
$(s_1*a_1 + s_2*a_4 + s_3*a_7 + s_4*a_{10}) == 0$ $(1)$
$(s_1*a_2+s_2*a_5+s_3*a_8+s_4*a_{11}) == 0$ $(2)$
$(s_1*a_3 + s_2*a_6 + s_3*a_9 + s_4*a_{12} == 0$ $(3)$
Giờ ta lấy $(1) - (2)$ thử thì sẽ thu được : $s_1*a_1^{'} + s_2*a_4^{'} + s_3*a_7^{'} + s_4*a_{10}^{'} == 0$ và giờ ta lại có 1 bộ $a$ mới , bộ $a$ mà ta có thể thực hiện phép xor là bộ $a$ mà các số cùng dấu nhau .
Tạo ra các bộ $a$ từ đó rồi dùng thư viện `itertools` để tính các trường hợp rồi `xor` thôi
Khá tiếc trong giải mình không nghĩ đến trường hợp này :crying_cat_face:.
Script được tài trợ từ @Quasar

mat2 = list(mat2)
for i in range(4):
    # if mat2[i] is all the same sign
    if all(mat2[i][j] > 0 for j in range(1,5)) or all(mat2[i][j] < 0 for j in range(1,5)):
        v = mat2[i][1:]
        break
for i in range(4):
    if mat2[i][0] != 0:
        mat2.pop(i)


b1 = -v
b2 = (-mat2[1] - mat2[2])[1:]
s = [b1, b2]
for i in range(-3, 3):
    for j in range(-3, 3):
        for k in range(-3, 3):
            v2 = (mat2[0]*i + mat2[1]*j + mat2[2]*k)[1:]
            if v2 not in s:
                if all(v2[j] > 0 for j in range(4)):
                    s.append(v2)
                elif all(v2[j] < 0 for j in range(4)):
                    s.append(-v2)

import itertools
combos = list(itertools.combinations(s, 3))
from tqdm import tqdm
from Crypto.Util.number import long_to_bytes as l2b
for v1,v2,v3 in tqdm(combos):
    if b'cor' in l2b(v1[0]^^v2[0]^^v3[0]):
        break


flag = [l2b(v1[i]^^v2[i]^^v3[i]) for i in range(4)]
flag = b"".join(flag).decode()

Flag : ```corctf{I'm_r00t1ng_f0R_U!!!!!!!}```
Còn bài mình bảo đã từng làm rồi là bài `apbq-rsa-ii` giải DownUnder 2023 nha :sweat: