Trong sự kiện tuyển thành viên gen 10 của CLB BKSEC năm 2026 , mình tập trung vào các challenge cryptography và có giải được 3 chall từ easy đến medium . Sau đó it ngày thì mình cũng đã giải được chall thứ 4 là LFSR . Đến đợt vừa rồi khi có tìm hiểu thêm về bài toán RLWE thì mình mới tìm lại chal thứ 5 để giải nốt và quyết định tổng hợp các write up chi tiết vào bài viết này .

Có thể xem chi tiết về challenge và write up trong github của mình https://github.com/ltnanh/ctf_crypto/tree/main/bksec

Hidden Structure

• Category: Crypto
• Difficulty : Easy

Chal Overview

Đây là hệ mật mã hóa RSA với quá trình generate key khác thường

from secrets import randbits
from Crypto.Util.number import *
  
flag = bytes_to_long(b"BKSEC{fake_flag}") # you lose aura if you submit this... (we are watching)

B = 1 << 256

def r256():
    x = randbits(256) | (1 << 255) | 1  
    return x

while True:
    x, y = r256(), r256()
    p = x * B + y       
    q = y * B + x       
    if isPrime(p) and isPrime(q):
        break

e = 65537
N = p * q
c = pow(flag, e, N)

print(f"{N = }")
print(f"{e = }")
print(f"{c = }")

Nhiệm vụ của ta là decrypt ra flag từ ciphertex được cho $c = flag^e \pmod N$

Attack Idea

Chắc chắn ta sẽ khai thác bất thường trong việc chọn các tham số của hệ mật:

$p = x \cdot 2^{256} + y$

$q = y \cdot 2^{256} + x$

Khi viết dưới dạng nhị phân, $p$ và $q$ sẽ có tính chất đối xứng: $x || y$ và $y || x$. Điều này dẫn đến $N$ sẽ có cấu trúc bit đặc biệt. Ta có:

$N = p \cdot q = (xB + y)(yB + x)$

$N = B^2xy + B(x^2 + y^2) + xy$

Với các số được viết dưới dạng nhị phân:

• $B^2xy = aa...aaa0000...0000$ (có 512 bit 0 ở cuối).
• $xy = aaa...aaa$ (khoảng 512 đến 513 bit).
• $B(x^2 + y^2) = bbb...bb000...000$ (có 256 bit 0 ở cuối).

Ta thấy rằng khi tổng 3 giá trị lại, 256 bit cuối của $N$ chính là 256 bit cuối của $xy$. 256 bit đầu của $N$ gần như tương ứng với 256 bit đầu của $xy$. Từ đó ta có thể lấy được giá trị của $xy$, từ đó khôi phục giá trị của $x, y$ và cuối cùng là $p, q$

Đầu tiên ta cần khôi phục $xy$ . Lấy 256 bit cuối của $N$ chính là 256 bit cuối của $xy$. 256 bit đầu của $xy$ gần bằng 256 bit đầu của $N$ vì $B(x^2 + y^2)$ có thể tạo ra carry sang phần high bits. Ta có thể brute-force một khoảng nhỏ quanh giá trị ước lượng.

Sau khi có các giá trị khả thi của $xy$ (gọi là $P$), ta có $x^2 + y^2 = \frac{N - P(B^2 + 1)}{B}$ .Từ đó tính tổng $S = x + y$ :

$S^2 = (x^2 + y^2) + 2P$

Nếu $S^2$ là một số chính phương , giá trị $S$ là hợp lệ.

Cuối cùng sau khi biết $x + y = S$ và $xy = P$ , ta giải pt bậc 2 để tìm $x$ , $y$

$t^2 - St + P = 0$

Code Exploit

from math import isqrt
from Crypto.Util.number import long_to_bytes

def recover_xy(S, P):
    D = S*S - 4*P
    if D < 0:
        return None

    r = isqrt(D)
    if r*r != D:
        return None

    x = (S + r) // 2
    y = (S - r) // 2

    return x, y

N = 107444638859099155759777187090231262569833054720517547475456101236477286061642951211232522980016935214117151901316067288134076019258357378153815894696105422994651894516549086845637403949534145390050746353299397783409065996987527927026314423191436300386280922075865669873754956335784354470237039709346406222789
e = 65537
c = 56143710973900761339774002971192037727375234874650436422245945684342980716505499471085786012340621409106405319356586450688993792522513823502401085339774194961300841598824881056390845294225756335102709315028822707701848497421372062559501439381841852116763699839771135406441292657937478625029095325072727620068

B = 1 << 256
bin_N = bin(N)[2:].zfill(1024)

# lấy low 256 bits của xy
low_xy = int(bin_N[-256:], 2)


# brute bits
for shift in range(-8, 9):
    approx_high = int(bin_N[:256], 2) + shift

    for mid in [0,1]:
        xy = (approx_high << 256) | (mid << 255) | low_xy
        rem = N - xy*(B*B + 1)

        if rem <= 0:
            continue

        if rem % B != 0:
            continue

        x2_y2 = rem // B
        S2 = x2_y2 + 2*xy

        if S2 < 0:
            continue

        S = isqrt(S2)
        if S*S != S2:
            continue

        res = recover_xy(S, xy)
        if res is None:
            continue

        x, y = res
        if x*y != xy:
            continue

        p = x*B + y
        q = y*B + x

        if p*q != N:
            continue

        phi = (p-1)*(q-1)
        d = pow(e, -1, phi)

        m = pow(c, d, N)
        print("FLAG:", long_to_bytes(m))
        exit()

print("not found")

FLAG: b'BKSEC{p4l1n_p0ly_1d3n717y_m47h}'

ZKRSA

• Category: Crypto
• Difficulty : Easy - Medium

Chal Overview

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

A = 2**1000
B = 2**80

FLAG = "BKSEC{Blahaj}"

def keygen():
    p = getPrime(512)
    q = getPrime(512)
    N = p * q
    PHI = (p - 1) * (q - 1)
    return N, PHI

def prove(z, N, PHI):
    r = getRandomRange(0, A)
    x = pow(z, r, N)
    e = int(input("CHALLENGE ME!!! "))
    if e >= B:
        raise ValueError("I refuse to prove that D:<!!!")
    y = r + (N - PHI) * e
    print(x, e, y)
    return (x, e, y)

def verify(z, x, e, y, N):
    return 0 <= y < A and pow(z, y - N * e, N) == x

print("I can prove to you that I can factorize N without revealing any knowledge :D")
print("The protocol is so secured in fact, I will even give you the FLAG!!!")
N, PHI = keygen()
print(N)
r = Random(1337)
for _ in range(500):
    try:
        z = r.randrange(2, N)
        x, e, y = prove(z, N, PHI)
        assert verify(z, x, e, y, N)
    except Exception as E:
        print(f"ERR: {E}")
print("Here's your FLAG hehehe")
print(pow(bytes_to_long(FLAG), 65537, N))

Đây là 1 hệ ZKP dựa trên RSA. Server proof nó biết cách phân tích nhân tử của mô-đun RSA $N$ mà không trực tiếp để lộ các số nguyên tố $p, q$ hay giá trị $\phi(N)$.

Challenge :Có 500 lượt, mỗi lượt client có thể gửi 1 giá trị $e$ tới server và nhận lại giá trị $x, y$:

• $x = z^r \pmod N$
• $y = r + (N - \phi(N)) \cdot e$

Với $z, r$ là 2 số random tương ứng với mỗi lượt . Ta cần phải dựa vào sample này để mà factor $N$ và decrypt flag bị mã hóa bỏi RSA

Attack Idea

Ở mỗi vòng lặp, server trả về $y$:

Đặt $S = N - \phi(N) = p + q - 1$. $\Rightarrow y = r + S \cdot e$

Ta thấy rằng, server chỉ cần giá trị $e < B = 2^{80}$ $\Rightarrow$ ta có thể gửi 1 số âm có giá trị tuyệt đối rất lớn. Ví dụ: gửi $e = -A = -2^{1000}$ $\Rightarrow$ ta sẽ nhận lại $y$ là 1 giá trị âm lớn: $y = r - S \cdot A$ $\Rightarrow \frac{-y}{A} = S - \frac{r}{A}$

Vì $r$ thường rất nhỏ so với $A$ $\Rightarrow \frac{r}{A} \approx 0 \Rightarrow \frac{-y}{A} \approx S$. Vì vậy, ta có thể khôi phục $S$ chính xác 100% bằng cách chia làm tròn lên: $S = \left\lceil \frac{-y}{A} \right\rceil$

Từ ý tưởng đó , ta có cách tấn công như sau :

• Ở lượt đầu tiên, ta gửi giá trị $e = -A$, từ đó có thể lấy được giá trị của $S$: $S = \left\lceil \frac{-y}{A} \right\rceil$

• Hàm verify ở serve sẽ ném ra lỗi, nhưng giá trị $y$ vẫn được gửi về và vòng lặp vẫn tiếp tục

• Ở các lượt sau, ta gửi các giá trị tùy ý cho đến khi lấy được ciphertext

• Sau khi có được $S$ từ vòng lặp đầu tiên , ta đã có $\Sigma = p + q = S + 1$. Khi này $p$ và $q$ là 2 nghiệm của phương trình bậc 2:$X^2 - \Sigma X + N = 0$ . Ta chỉ cần dùng công thức nghiệm giải pt này để tìm ra $p$ và $q$

• Có $p, q$, ta dễ dàng tính $\phi(N) = (p-1)(q-1)$ và khóa giải mã $d \equiv 65537^{-1} \pmod{\phi(N)}$ để decrypto flag $m \equiv c^d \pmod N$.

Code exploit

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

context.log_level = 'error'

HOST = '127.0.0.1' 
PORT = 1337

A = 2**1000

r = remote(HOST, PORT)

r.recvline()
r.recvline()

N = int(r.recvline().strip())
print(f"N ={N}")

malicious_y = 0
enc_flag = 0 

try:
    for i in range(500):
        r.recvuntil(b"CHALLENGE ME!!! ")

        if i == 0:
            e_challenge = -A
        else:
            e_challenge = 1 

        r.sendline(str(e_challenge).encode())

        response = r.recvline().decode().strip().split()

        x_val, e_val, y_val = map(int, response)
        if i == 0:
            malicious_y = y_val

    r.recvuntil(b"Here's your FLAG hehehe\n")
    flag_data = r.recvall().decode().strip() 
    
    if flag_data:
        enc_flag = int(flag_data)
        print(enc_flag) 
    else: 
        print("Không nhận được FLAG")

except Exception as e:
    print(f"Server đóng kết nối hoặc lỗi: {e}")

finally:
    r.close()

S = (-malicious_y + A - 1) // A
print(S)

p_plus_q = S + 1

delta = p_plus_q**2 - 4 * N

sqrt_delta = math.isqrt(delta)

p = (p_plus_q + sqrt_delta) // 2
q = (p_plus_q - sqrt_delta) // 2

print(f"p = {p}")
print(f"q = {q}")

if p * q == N:
    PHI = (p - 1) * (q - 1)
    e_rsa = 65537

    d = pow(e_rsa, -1, PHI)
    m = pow(enc_flag, d, N)

    print(long_to_bytes(m).decode())

Đây là kết quả thành công trên local server

N=167629805948328480856136662463024641078544529691492272664474940169464728000546260009523173466811359968916536687879188204759866327925891179582731061156232738902731111791596842791987178269624500992452823641069225953237087383044968734888184746389875147369211197267744646914195310550864372010990131043741023412271
146783221816191892832299181433716702896421731754997132955358938245262339518821028341445414172362993797673815785106931873973143584407734686950165723251703969194223859104640716116796457521713336617903799526816984305863361249467510375811532386148051196710157885384565862626449466229103636438730600643208795535543
25906298710408090870795323312593156135881716487327475646693436001925545300645964041921123146237490299054641066748402079570334742717567596771513191072756879
p = 13345924443383651307825783053348900030561990589036994089184077754058942705750224512019827345001244357228276340291843668986253908689641003932364724809374513
q = 12560374267024439562969540259244256105319725898290481557509358247866602594895739529901295801236245941826364726456558410584080834027926592839148466263382367
BKSEC{fake_flag_for_testing}

ZKRSA Revenger

• Category: Crypto
• Difficulty : Medium

Chal Overview

from Crypto.Util.number import getPrime, getRandomRange, bytes_to_long, long_to_bytes
from random import Random
import os
import hashlib

A = 2**1000
B = 2**80

FLAG = b"BKSEC{Evil_Blahaj}"

def keygen():
    p = getPrime(512)
    q = getPrime(512)
    N = p * q
    PHI = (p - 1) * (q - 1)
    return N, PHI

def prove(z, N, PHI):
    r = getRandomRange(0, A)
    x = pow(z, r, N)
    e = int(input("CHALLENGE ME!!! "))
    if e >= B:
        raise ValueError("I refuse to prove that D:<!!!")
    y = r + (N - PHI) * e
    check = int(hashlib.sha256(str(y).encode()).hexdigest(), 16) % B
    return (x, e, y, check)

def verify(z, x, e, y, N):
    return 0 <= y < A and pow(z, y - N * e, N) == x

print("Your mathematics shenanigans (should) not work this time... My Blahaj hath fixedyour antics!!!")
print("No more knowledge. No more negativity. Truly (maybe) secured")
N, PHI = keygen()
print(N)
r = Random(int.from_bytes(os.urandom(8), 'big'))
for _ in range(500):
    try:
        z = r.randrange(2, N)
        x, e, y, check = prove(z, N, PHI)
        print(check) # This should be enough, right...?
    except Exception as E:
        print(f"ERR: {E}")
print("Here's your FLAG hehehe")
print(pow(bytes_to_long(FLAG), 65537, N))

Đây là phiên bản nâng cấp của challenge ZKRSA trước. Công thức tạo proof vẫn là $y = r + (N - \phi(N))e$, nhưng server không in trực tiếp $x, e, y$ nữa mà chỉ in một giá trị check tính từ hash của $y$. Seed để sinh $z$ cũng được lấy từ os.urandom thay vì cố định. Vì vậy, cách gửi $e = -2^{1000}$ rồi chia ngược từ $y$ ở bài trước không còn dùng được.

Challenge: Ta vẫn có 500 lượt gửi giá trị $e$ tới server. Với mỗi lượt, server tính:

• $x = z^r \pmod N$
• $y = r + (N - \phi(N)) \cdot e$
• $check = \operatorname{SHA256}(\operatorname{str}(y).\operatorname{encode}()) \bmod 2^{80}$

Trong đó $z, r$ được sinh mới ở mỗi lượt. Ta chỉ nhận được check hoặc thông báo lỗi; sau 500 lượt server mới gửi ciphertext của flag. Mục tiêu vẫn là tìm $p, q$ để giải mã RSA.

Attack Idea

Đặt $S = N - \phi(N) = p + q - 1$, khi đó $y = r + S \cdot e$.

Việc sửa các bug của chal cũ khiến cho việc sử dụng toán học để khai thác trở nên bế tắc . Tuy nhiên , 1 ý tưởng rất hay hiện ra khi tôi để ý việc hash $y$ để tạo ra check. Server phải gọi str(y) trước khi băm nó , và 1 giới hạn của hàm str(y) trong Python chỉ ra bug của bài này . Với Python 3.11+ ở cấu hình mặc định, phép chuyển số nguyên sang chuỗi chỉ cho phép tối đa 4300 chữ số thập phân. Vì vậy str(y) ném ValueError nếu $|y| \ge 10^{4300}$. Lỗi này nằm trong khối try...except, nên ta có một oracle từ phản hồi của server:

• Nếu $|y| < 10^{4300}$, server in ra check.
• Nếu $|y| \ge 10^{4300}$, server in ra ERR.

Ta có thể dùng oracle này để so sánh $S$ với một giá trị đoán $mid$. Đặt $T = 10^{4300}$ và gửi: $e = -\left\lfloor \frac{T-1}{mid} \right\rfloor$

Khi đó $y = r - S\lfloor (T-1)/mid \rfloor$. Ta dùng $T-1$ để trường hợp $S = mid$ luôn nằm dưới ngưỡng lỗi. Vì $0 \le r < 2^{1000}$, còn $T/mid$ lớn hơn rất nhiều, $r$ không làm thay đổi kết quả so sánh:

• Nếu $S \le mid$, ta có $|y| < T$, server in check.
• Nếu $S > mid$, ta có $|y| \ge T$, server in ERR.

Từ ý tưởng đó, ta dùng 500 lượt để binary search $S$:

• Ban đầu, $low = 2\lfloor\sqrt{N}\rfloor$ vì $p + q \ge 2\sqrt{N}$; chọn $high = 2^{513}$ vì $p, q$ đều là số nguyên tố 512 bit.
• Mỗi lượt lấy $mid = \lfloor(low + high)/2\rfloor$, gửi $e = -\lfloor(T-1)/mid\rfloor$.
• Nếu nhận ERR, đặt $low = mid + 1$; nếu nhận check, đặt $high = mid$.

Sau 500 lượt, khoảng cần tìm chỉ còn cỡ $2^{513-500} = 2^{13}$ giá trị. Ta có thể brute từng giá trị $S$ còn lại để tìm $p, q$

Code exploit

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

context.log_level = 'error'

HOST = '127.0.0.1'
PORT = 1337

r = remote(HOST, PORT)

r.recvline()
r.recvline()


N = int(r.recvline().strip())
print(f"N: {N}")

low = math.isqrt(N) * 2
high = 2**513


try:
    for i in range(500):
        r.recvuntil(b"CHALLENGE ME!!! ")

        mid = (low + high) // 2
        e_val = -((10**4300 - 1) // mid)

        r.sendline(str(e_val).encode())
        response = r.recvline().decode().strip()

        if "ERR" in response:
            low = mid + 1
        else:
            high = mid


    r.recvuntil(b"Here's your FLAG hehehe\n")
    enc_flag = int(r.recvall().decode().strip())
    print("Enc flag: ",enc_flag)

except Exception as E:
    print(E)

finally:
    r.close()

p = 0
q = 0


for S_candidate in range(low, high + 1):
    p_plus_q = S_candidate + 1

    delta = p_plus_q**2 - 4 * N

    if delta < 0:
        continue
    sqrt_delta = math.isqrt(delta)
    if sqrt_delta**2 == delta:
        p = (p_plus_q + sqrt_delta) // 2
        q = (p_plus_q - sqrt_delta) // 2

        if p * q == N:
            break

if p and q:

    PHI = (p - 1) * (q - 1)
    e_rsa = 65537
    d = pow(e_rsa, -1, PHI)
    m = pow(enc_flag, d, N)

    print(long_to_bytes(m).decode())

Đây là kết quả thành công trên local server:

N:145969836915009028574884415219575953536366858889859356205542800445012138778425447433430313614471191573042943247039847180900962456896321305446838629594099890867237667420048577051350014585983463460901655558009198513004857165769770261027305485378749318791174847807561607256956580207610294822304775420574328597859
Enc flag:  112464274008268880605434356398753809883465308334599653876167892486876139832193670508490084518595728094457599189032901987219007080818043707274744430752113529399094996908964109352705072602691654039862086507316771400071154180553222046073605971076713364775178406587509920671003448338664291790775272746012258247888
BKSEC{Evil_Blahaj}

LFSR

Category : Crypto

Challenge overview

Source code

import secrets
import threading
import sys
import os

def kill_switch():
    print("Time expired!")
    sys.exit()

SECRET_FLAG = os.environ.get("FLAG", "BKSEC{REDEACT}").encode()

Ns = [14, 32, 24, 48, 8, 8, 8, 8, 10]
MASKS = [1959, 3487505359, 12175963, 144894747199363, 39, 101, 99, 43, 579]
Filters = [
    43673535323473607050899647551732188151,
    69474900172976843852504521249820447513188207961992185137442753975916133181030,
    28448620439946980695145546319125628439828158154718599921182092785732019632576,
    16097126481514198260930631821805544393127389525416543962503447728744965087216,
    7283664602255916497455724627182983825601943018950061893835110648753003906240,
    55629484047984633706625341811769132818865100775829362141410613259552042519543,
    4239659866847353140850509664106411172999885587987448627237497059999417835603,
    106379335904610565198575784689340408012917012758379923896044369424798179675586
]

extract = lambda x,b: sum(((x >> p) & 1) << i for i, p in enumerate(b))
blur = lambda x,i: (Filters[i] >> x) & 1

class LFSR:
    def __init__(self, n, key, mask):
        self.n = n
        self.state = key & ((1 << n) - 1)
        self.mask = mask

    def __call__(self):
        b = self.state & 1
        self.state = (self.state >> 1) | (
            ((self.state & self.mask).bit_count() & 1) << (self.n - 1)
        )
        return b

class Cipher:
    def __init__(self, key):
        self.lfsrs = []
        for i in range(len(Ns)):
            self.lfsrs.append(LFSR(Ns[i], key, MASKS[i]))
            key >>= Ns[i]

    def bit(self):
        x = blur(extract(self.lfsrs[0].state, [5, 9, 1, 0, 4, 11, 13]), 0)
        y = self.lfsrs[1].state & 1
        z = blur(extract(self.lfsrs[2].state, [20, 2, 16, 11, 1, 23, 22, 8]), 1)
        w = blur(extract(self.lfsrs[3].state, [1, 46, 21, 7, 43, 0, 27, 39]), 2)
        v = blur(extract(self.lfsrs[4].state, [1, 3, 7, 4, 5, 0, 6, 2]), 3)
        u = blur(self.lfsrs[5].state, 4) ^ blur(self.lfsrs[6].state, 5) ^ blur(self.lfsrs[7].state, 6)
        t = blur(extract(self.lfsrs[8].state, [5, 8, 9, 3, 1, 0, 2, 4]), 7)
        for lfsr in self.lfsrs: lfsr()
        return x ^ y ^ z ^ w ^ v ^ u ^ t

    def stream(self):
        while True:
            b = 0
            for i in reversed(range(8)):
                b |= self.bit() << i
            yield b

    def encrypt(self, pt: bytes):
        return bytes([x ^ y for x, y in zip(pt, self.stream())])

key = secrets.randbits(160)
cipher = Cipher(key)
tk = secrets.token_bytes(15)
print("Token:", tk.hex())
time_guard = threading.Timer(60, kill_switch) 
time_guard.start()
print("ct:", cipher.encrypt(b"\x00"*80+tk).hex())
if input("Gimme Token: ") == tk.hex():
    print("Here is your flag:", SECRET_FLAG)

Thử thách cho 1 hệ mã hóa Cipher kết hợp 9 bộ LFSR với độ dài khác nhau với

Mỗi lfsr (class LFSR) gồm :

• state: Trạng thái hiện tại của thanh ghi.
• mask: Xác định các vị trí (taps) để thực hiện phép XOR nhằm tạo ra bit feedback.
• chu kì của các bộ lfsr này sẽ tạo bit feed back như truyền thống

Main cipher (class Cipher) gộp các lfst tạo keystream phi tuyến tính (hàm bit())

• extract(x, b) : Trích xuất các bit tại các vị trí cụ thể b từ state x để tạo thành một số nguyên mới.

• blur(x, i) : Sử dụng số nguyên vừa trích xuất làm chỉ số (index) để lấy một bit từ danh sách Filters.

• với mỗi bộ lfsr tại 1 clock với state tương ứng sẽ thông qua các các hàm này để trích xúât ra một bit tương ứng để tham giá xor tạo feedforward bit ==> Keystream có tính phi tuyến

Main challenge thì server sẽ encrypt 1 token và gửi ta ciphertext , nhiệm vụ của ta là decrypt ra token và gửi về cho server để lấy flag

Quan sát challenge & hệ mã

Known plaintext attack: server chèn 80 bytes 00 đầu vào token trước khi giải mã. Với mật mã dòng (plaintext xor keystream) , 80 bytes đầu của ciphertext chính là của keystream

=> Ta có thể lập 1 hệ phương trình 640 ẩn. Nếu ta có thể biểu diễn được feed forward của lfsr bằng 1 quan hệ tuyến tính giữa các biến bit => ta có thể giải hệ phương trình tuyến tính bằng Gauss

Quan sát chu kì của các bộ lfsr

Có state của các bộ lfsr , tôi sẽ tính đa thức đặc trưng và chu kì của chúng

import time

Ns = [14, 32, 24, 48, 8, 8, 8, 8, 10]
MASKS = [1959, 3487505359, 12175963, 144894747199363, 39, 101, 99, 43, 579]

def simulate_period(n, mask, timeout=10):
    start_state = 1
    state = start_state
    period = 0
    start_time = time.time()
    
    while True:
        state = (state >> 1) | (((state & mask).bit_count() & 1) << (n - 1))
        period += 1
        
        if state == start_state:
            return period
            
        #  Chỉ check thời gian mỗi 100.000 vòng lặp
        if period % 100000 == 0:
            if time.time() - start_time > timeout:
                return f"Timeout, Đã chạy được {period} bước"


for i, (n, mask) in enumerate(zip(Ns, MASKS)):
    print(f"LFSR {i} (N={n:<2}) ", end=" ", flush=True)
    actual_period = simulate_period(n, mask, 10)
    print(f" => Chu kỳ: {actual_period}")

LFSR 0 (N=14)   => Chu kỳ: 16383
LFSR 1 (N=32)   => Chu kỳ: Timeout, Đã chạy được 34800000 bước
LFSR 2 (N=24)   => Chu kỳ: 16646017
LFSR 3 (N=48)   => Chu kỳ: 63
LFSR 4 (N=8 )   => Chu kỳ: 63
LFSR 5 (N=8 )   => Chu kỳ: 255
LFSR 6 (N=8 )   => Chu kỳ: 255
LFSR 7 (N=8 )   => Chu kỳ: 255
LFSR 8 (N=10)   => Chu kỳ: 1023

Ta thấy lfsr3 và lfsr4 đều có chu kì là 63 => bit w , bit u có chu kì là 63 => bit w⊕v có chu kì là 63 => các bit w⊕v tạo thành chu kì f0, f1, … , f63 => Tạo thành 63 biến trong hệ phương trình 640 ẩn vì tại mỗi clock thì 1 trong các biến này sẽ xor tạo key bit

Tương tự với lfsr5 ,6,7 thì bit u có chu kì là 255 , tạo thành 255 biến trong hệ

Biểu diễn đại số cho feedforward của các lfsr

Các con số khổng lồ trong mảng Filters trông có vẻ ngẫu nhiên. nhưng thực chất chúng chính là Bảng chân trị (Truth Table) .Khi hàm extract ghép 8 bit lại thành số nguyên X => (Filters[i] >> X) & 1 chính là hành động tra cứu bit thứ X . Biến đổi Möbius (Fast Algebraic Transform) giúp chuyển bảng chân trị sang đa thức đại số

def generate_anf(lfsr_idx, filter_val, extract_positions):
    k = len(extract_positions)
    tt = [(filter_val >> i) & 1 for i in range(1 << k)]
    anf = list(tt)
    for i in range(k):
        for j in range(1 << k):
            if (j & (1 << i)) != 0:
                anf[j] ^= anf[j ^ (1 << i)]
    terms = []
    if anf[0] == 1:
        terms.append("1")
    degree = 0
    for j in range(1, 1 << k):
        if anf[j] == 1:
            term_vars = []
            current_degree = bin(j).count('1')
            degree = max(degree, current_degree)
            for bit_idx in range(k):
                if (j >> bit_idx) & 1:
                    state_pos = extract_positions[bit_idx]
                    term_vars.append(f"s_{state_pos}")
            terms.append(" * ".join(term_vars))
    if not terms:
        equation = "0"
    else:
        equation = " + ".join(terms)
    print(f"[*] LFSR {lfsr_idx}")
    print(f"Degree: {degree}")
    print(f"f(S) = {equation}\n")

chạy code sẽ ra kết quả với lfsr 2 là hoàn toàn tuyến tính

[*] LFSR 2
Degree: 1
f(S) = s_20 + s_2 + s_1 + s_23 + s_8

Feedforward của lfsr 2 có thể biểu diễn tuyến tính , ta sẽ thêm 24 ẩn bit của lfsr 2 vào hệ phương trình

Ngoài ra lfsr 1 implement theo cách chuẩn của lfsr tức là cũng tuyến tính . Ta sẽ thêm 32 ẩn bit vào hệ phương trình

Hệ đã xây được

Ta có 1 hệ gồm 640 phương trình với 374 ẩn số bao gồm:

• 32 ẩn của hệ LFSR 1 ($x_{1} \rightarrow x_{32}$)
• 24 ẩn của hệ LFSR 2 ($x_{33} \rightarrow x_{56}$)
• 63 ẩn của hệ LFSR 3 và 4 ($x_{57} \rightarrow x_{119}$)
• 255 ẩn của hệ LFSR 5, 6, 7 ($x_{120} \rightarrow x_{374}$)

Với mỗi clock i, hệ phương trình sẽ có dạng : $p_1x_1 + ⋯ + p_{32}x_{32} + p_{33}x_{33} + ⋯ + p_{374}x_{374} = a_i$ . Ta chỉ cần mô phỏng lại cipher để xác định hệ số của các ẩn tại từng clock

Xử lí phi tuyến

Điều khó khăn ở đây là ta hoàn toàn ko biết RHS của hệ vì còn vướng Lfsr 0 và 8, biểu thức của 2 hệ này phi tuyến và nhiều ẩn khiến cho việc đưa vào hệ gần như ko thể . Tôi nghĩ đến việc brute 2 initial state của LFSR 0 và LFSR 8 còn lại, gen stream bit $x⊕s$ của 2 bộ đó qua 640 clock và XOR với keystream sinh ra stream $a_1, … , a_{640}$ . Case brute đúng thì hệ sẽ có nghiệm , tuy nhiên ta phải đối mặt với bài toán về thời gian . LFSR 0 có 14 bit state, LFSR 8 có 10 bit state => để đoán 24 bit sẽ có 16 triệu trường hợp, 16 triệu lần giải hệ . Implement của tôi cho thấy cần vài tiếng để hoàn thành việc này .

Kỹ thuật Meet-in-the-Middle

Vậy nên để tối ưu hóa, ta sử dụng kỹ thuật Meet-in-the-Middle: Với $K$ là keystream (640), $M$ là ma trận của hệ (640×374), $X$ là vector nghiệm (374), $L_0$ là stream của LFSR 0, $L_8$ là stream của LFSR 8, ta có: $K = (M ⋅ X) ⊕ (L0 ⊕ L8)$

• Ta tính $H$ là left kernel của $M$: ($H ⋅ M = 0$)

• Nhân 2 vế pt trên với $H$:

Từ đẳng thức trên , ta có thể :

• Tạo 1 hash map, duyệt qua $2^{14}$ case của LFSR 0 và lưu vào bảng hash các giá trị $H ⋅ L_0$.

• Sau đó brute qua $2^{10}$ case của LFSR 8, với mỗi case tính $H ⋅ K ⊕ H ⋅ L_8$ và kiểm tra xem có giá trị đó trong hash table không. Nếu có thì đó chính là 2 giá trị $L_0$ và $L_8$ cần tìm.

• Việc dùng bảng hash mỗi lần tìm kiếm chỉ tốn O(1), nhanh hơn rất nhiều so với việc brute cả 24 bit cùng lúc.

Decryption

Khi đã có initial state của LFSR 0 và LFSR 8, ta chỉ cần gen ra RHS của hệ phương trình và giải hệ đó .Với bộ nghiệm có được:

• Với bit u và w⊕v theo chu kì, ta chỉ cần gen tiếp các bit đó
• Với LFSR 1 và 2, các nghiệm tương ứng chính là initial state của 2 hệ đó, chỉ cần gen tiếp stream của 2 hệ này.

Ta đã có thể gen toàn bộ keystream của hệ 9 LFSR và decrypt được phần token.

Exploit

Dưới đây là toàn bộ code sage dùng để giải challenge

from sage.all import *
from pwn import *

context.log_level = 'error'


HOST = "localhost"
PORT = 1337
r = remote(HOST, PORT)


r.recvuntil(b"ct: ")
ct_hex = r.recvline().strip().decode()



Ns = [14, 32, 24, 48, 8, 8, 8, 8, 10]
MASKS = [1959, 3487505359, 12175963, 144894747199363, 39, 101, 99, 43, 579]
FILTERS = [
    43673535323473607050899647551732188151,
    69474900172976843852504521249820447513188207961992185137442753975916133181030,
    28448620439946980695145546319125628439828158154718599921182092785732019632576,
    16097126481514198260930631821805544393127389525416543962503447728744965087216,
    7283664602255916497455724627182983825601943018950061893835110648753003906240,
    55629484047984633706625341811769132818865100775829362141410613259552042519543,
    4239659866847353140850509664106411172999885587987448627237497059999417835603,
    106379335904610565198575784689340408012917012758379923896044369424798179675586
]

E0 = [5, 9, 1, 0, 4, 11, 13]
E2 = [20, 2, 16, 11, 1, 23, 22, 8]
E8 = [5, 8, 9, 3, 1, 0, 2, 4]


ct_bytes = bytes.fromhex(ct_hex)
known_bits = [(byte >> i) & 1 for byte in ct_bytes[:80] for i in reversed(range(8))]
Z = vector(GF(2), known_bits)



def clock_sym(state, mask):
    fb = sum([state[i] for i in range(len(state)) if (mask >> i) & 1])
    return state[1:] + [fb]


print("Xây dựng Ma trận Tuyến tính (M) cho 374 biến ,640 eqn\n")
state_L1 = [vector(GF(2), 374, {i: 1}) for i in range(32)]
state_L2 = [vector(GF(2), 374, {32+i: 1}) for i in range(24)]

# Bóc tách cấu trúc tuyến tính của L2
tt2 = [(FILTERS[1] >> j) & 1 for j in range(256)]
C2_const = tt2[0]
C2_coeffs = [tt2[1<<i] ^^ C2_const for i in range(8)]

M = matrix(GF(2), 640, 374)
C2_vec = vector(GF(2), 640)

for i in range(640):
    row = vector(GF(2), 374)
    row += state_L1[0] # L1
    row += sum([C2_coeffs[k] * state_L2[E2[k]] for k in range(8)]) # L2
    C2_vec[i] = C2_const
    row[56 + (i % 63)] = 1 # V63
    row[119 + (i % 255)] = 1 # V255
    
    M[i] = row
    state_L1 = clock_sym(state_L1, MASKS[1])
    state_L2 = clock_sym(state_L2, MASKS[2])



H = M.left_kernel().basis_matrix()
print(f"Left kernel H kích thước {H.nrows()} x {H.ncols()}\n")



# to gen feed forward stream for lfsr 0,8 and 1,2 
def gen_lfsr_stream(n, mask, filter_val, ext_pos, seed):
    state = seed
    stream = vector(GF(2), 640)
    for i in range(640):
        idx = 0
        for j, p in enumerate(ext_pos):
            if (state >> p) & 1: idx |= (1 << j)
        stream[i] = (filter_val >> idx) & 1
        fb = bin(state & mask).count('1') & 1
        state = (state >> 1) | (fb << (n - 1))
    return stream



print("Meet-in-the-Middle")
hash_L0 = {}
for seed0 in range(1, 1 << 14):
    stream0 = gen_lfsr_stream(14, MASKS[0], FILTERS[0], E0, seed0)
    Y0 = H * stream0
    hash_L0[tuple(Y0)] = seed0
print(f"      Đã có hashtable {len(hash_L0)} trạng thái của L0.")


seed_L0, seed_L8 = None, None
T = H * (Z + C2_vec)
for seed8 in range(1, 1 << 10):
    stream8 = gen_lfsr_stream(10, MASKS[8], FILTERS[7], E8, seed8)
    Y8 = H * stream8
    target_Y0 = Y8 + T
    
    if tuple(target_Y0) in hash_L0:
        seed_L0 = hash_L0[tuple(target_Y0)]
        seed_L8 = seed8
        print(f"      Tìm ra seed L8 khớp" )
        print(f"      Seed L0 = {seed_L0}")
        print(f"      Seed L8 = {seed_L8}\n")
        break



print("Hoàn thiện hệ pt , giải và trích xuất seed/period seq")

stream0 = gen_lfsr_stream(14, MASKS[0], FILTERS[0], E0, seed_L0)
stream8 = gen_lfsr_stream(10, MASKS[8], FILTERS[7], E8, seed_L8)

RHS = Z + C2_vec + stream0 + stream8
    
try:
    X = M.solve_right(RHS)

    seed_L1 = sum(int(X[i]) << i for i in range(32))
    seed_L2 = sum(int(X[32 + i]) << i for i in range(24))
    seq_63 = [int(X[56 + i]) for i in range(63)]
    seq_255 = [int(X[119 + i]) for i in range(255)]
    
    print(f"       Seed L1 = {seed_L1}")
    print(f"       Seed L2 = {seed_L2}")
    print("       seq 63 = ",seq_63)
    print("       seq 255 = ",seq_255)
    print()

except ValueError:
    print("Hệ pt vô nghiệm")
    sys.exit()





print("Decypt flag token")

extract = lambda x,b: sum(((int(x) >> p) & 1) << i for i, p in enumerate(b))
blur = lambda x,i: (FILTERS[i] >> int(x)) & 1

class LFSR:
    def __init__(self, n, key, mask):
        self.n = n
        self.state = int(key) & ((1 << n) - 1)
        self.mask = int(mask)

    def __call__(self):
        b = self.state & 1
        fb = int(self.state & self.mask).bit_count() & 1
        self.state = (self.state >> 1) | (fb << (self.n - 1))
        return b

class Cipher:
    def __init__(self, s0, s1, s2, s8, seq63, seq255):
        self.lfsr0 = LFSR(Ns[0], s0, MASKS[0])
        self.lfsr1 = LFSR(Ns[1], s1, MASKS[1])
        self.lfsr2 = LFSR(Ns[2], s2, MASKS[2])
        self.lfsr8 = LFSR(Ns[8], s8, MASKS[8])
        
        self.seq63 = seq63
        self.seq255 = seq255
        self.clock = 0

    def bit(self):
        x = blur(extract(self.lfsr0.state, E0), 0)
        y = self.lfsr1.state & 1
        z = blur(extract(self.lfsr2.state, E2), 1)
        t = blur(extract(self.lfsr8.state, E8), 7)
        
        w_v = int(self.seq63[self.clock % 63])
        u = int(self.seq255[self.clock % 255])
        
        self.lfsr0()
        self.lfsr1()
        self.lfsr2()
        self.lfsr8()
        self.clock += 1
        
        return x ^^ y ^^ z ^^ w_v ^^ u ^^ t

    def stream(self):
        while True:
            b = 0
            for i in reversed(range(8)):
                b |= self.bit() << i
            yield b

    def decrypt(self, ct: bytes):
        return bytes([int(c) ^^ int(k) for c, k in zip(ct, self.stream())])


cipher = Cipher(seed_L0, seed_L1, seed_L2, seed_L8, seq_63, seq_255)
decrypted_bytes = cipher.decrypt(ct_bytes)

token = decrypted_bytes[80:]
print(f"FLAG TOKEN : {token.hex()}")

r.recvuntil(b"Gimme Token: ")
r.sendline(token.hex().encode())
flag = r.recvall(timeout=5).decode().strip()
print(flag)
r.close()

Lord of the error ring

• category : Crypto
• Difficulty : Hard

1. Challenge overview

Source code

import os
import random
import ast

proof.arithmetic(False)

flag = os.environ.get("FLAG","BKSEC{testing}")
p = 8380417
F = GF(p)
R.<x> = F[]

fs = []
degree = [8,16,32,64]
errs = random.sample(range(p), 3)
print(errs)

for d in degree:
    f = R.irreducible_element(d)
    if f not in fs:
        fs.append(f)

f = prod(fs)

def parse_poly(user_in):
    coeffs = ast.literal_eval(user_in)
    if not isinstance(coeffs, (list, tuple)):
        raise ValueError
    if not all(isinstance(c, int) for c in coeffs):
        raise ValueError
    return R([c % p for c in coeffs])


def poly_crt(res, fs):
    M = prod(fs)
    a = R(0)
    for i, fi in enumerate(fs):
        Mi = M // fi
        Ni = Mi.inverse_mod(fi)   
        a += res[i] * Mi * Ni
    return a % M
    
def poly_sample(lb, ub):
    es = [R([random.randint(lb,ub) for _ in range(d)]) for d in degree]
    
    return poly_crt(es, fs)

def error_sample(errs):
    es = [R([random.choice(errs) for _ in range(d)]) for d in degree]
    
    return poly_crt(es, fs)


print("Welcome to RLWE challenge!")
print("I will let u sample at most 10 samples this time  :DDDDD")
print("num sample:")

num_sample = int(input("> "))
if num_sample > 10:
    print("You are too greedy !!!")
    exit()

a_s = [poly_sample(0, p - 1) for _ in range(num_sample)]
s = poly_sample(0, p - 1)
e_s = [error_sample(errs) for _ in range(num_sample)]

samples = [(list(a % f), list((a * s + e) % f)) for a, e in zip(a_s, e_s)]

print("Here is your polynomial f:")
print(list(f))
print("Here are your samples:")
print(samples)


print("Submit your guess for my secret :<<<<")

try:
    guess = R(parse_poly(input("> ")))
    print('Guess:', guess)
    if guess == s:
        print("Congrats! Here is your flag: " + flag)
except:
    print("Don't be that desperate :v")
    exit()

Ta có thể thấy hệ mã trong challenge là 1 biến thể base trên Ring LWE

• hệ mã RLWE được xây trên vành đa thức $R[x] = Z_p[x]/f$ với p = 8380417 . Thay vì dùng đa thức $f = x^n + 1$ thì hệ mã chọn ra 4 đa thức bất khả quy $f_i$ với bậc lần lượt là 8,16,32,64 và ghép lại $f = f_1.f_2.f_3.f_4$ .Thay vì chọn nhiễu $e$ nhỏ như là RLWE thông thường , chal random 4 vecto nhiễu thành phần trên $Z_p[x]/f_i$ sau đó ghép lại bằng CRT để thành $e\pmod {f}$ , và các hệ số của mỗi đa thức $e_i$ được chọn từ 1 trong 3 số được random trên $Z_q$ của tập errs
• Về phần thử thách , dựa trên công thức $b = as + e \pmod f$ của RLWE , chal gen khóa bí mật $s$ sau đó random ra nhiều nhất 10 cặp đa thức ($a_i,e_i$) để tính ra $b_i$ . Server sẽ cho ta 10 sample $(a_i,b_i)$ này và bắt ta khôi phục lại secret $s$ để lấy được flag

Attack Idea

Ta sẽ tận dụng các điểm khác thường của hệ mã này so với bài toán RLWE gốc để tìm hướng khai thác . Dễ thấy là ta có thể tìm các giá trị $s \pmod{f_i}$ trên các cành đa thức nhỏ hơn sau đó construct lại thành $s \pmod{f}$ bằng CRT . Tiếp theo là việc ko dùng random nhiễu nhỏ mà các nhiễu thành phần $e \pmod{f_i}$ có các hệ số chỉ nhận 1 trong 3 giá trị .

Trước tiên thì ta cần phải factor được đa thức $f(x)$ mà server gửi đến thành 4 đa thức thành phần , việc này khác dễ dàng khi dùng hàm factor trong sagemath . Hơn nữa thì như source code server thì hàm random ra các đa thức con là deterministic , tức là các $f_i(x)$ cũng như $f(x)$ là cố định , ta ko cần đợi $f$ từ server .

p = 8380417
F = GF(p)
R.<x> = F[]

f_coeffs = [2020240, 265213, 8152448, 1535330, 2302708, 188378, 4856268, 706694, 3888509, 892985, 7354552, 8172644, 1821287, 6012562, 6214552, 4620009, 269958, 2713660, 6902035, 3946856, 6610444, 6339, 4376878, 2650537, 6107091, 7884244, 8134050, 3585005, 8215254, 3058088, 4326325, 5780968, 5620643, 2045529, 1853649, 5820996, 7252971, 942616, 4123236, 1999542, 29601, 1823190, 7009514, 7392312, 6110635, 662596, 7578109, 7314550, 4536439, 2713935, 65615, 433806, 7852665, 8277309, 4578221, 7331417, 8115130, 1817320, 5330933, 2820207, 6925175, 5269501, 6986417, 4270840, 1541104, 5120143, 7500981, 7954515, 6482335, 4292987, 6993323, 2535234, 3576325, 1074488, 201808, 2324864, 2397710, 2824968, 1576746, 4847844, 2163136, 6229964, 3964077, 6820186, 3800330, 1077806, 7453108, 779773, 7713008, 4192884, 2125242, 2268313, 813588, 2250814, 5876952, 7155218, 2157270, 3818794, 5683869, 5492251, 3832114, 210892, 8145760, 6901089, 4085414, 7192824, 1194351, 4847602, 2522996, 5620900, 4856679, 7441652, 56020, 65652, 17006, 8379720, 8379664, 8380226, 4, 4, 1]
f = R(f_coeffs)

factors = f.factor()

fs = [fac[0] for fac in factors]
fs.sort(key=lambda poly: poly.degree())

for i, fi in enumerate(fs):
    print(f"f{i+1} , degree =", fi.degree())
    print(list(fi))
    print()

Về phần implement , ta sẽ phải tính toán trên từng hệ số của đa thức , vậy nên tốt nhất là nên chuyển đổi đa thức thành vecto cũng như phép nhân đa thức thành phép nhân với ma trận để dễ lập hệ . Sau đây là hàm để biến phép nhân với đa thức $a(x)$ thành nhân ma trận A

# convert mul a(x) to mul matrix A 
def poly_to_matrix(a_poly, mod_poly, degree):
    cols = []
    for j in range(degree):
        term = (a_poly * (x**j)) % mod_poly
        c = term.list()
        c += [0] * (degree - len(c))
        cols.append(c)
    return matrix(F, cols).transpose()

Phase 1 : s mod f1 và errs

Để khôi phục lại $s_1 = s \pmod {f_1}$ , đương nhiên đầu tiên ta sẽ đi từ đa thức $f_1(x)$ nhỏ nhất với bậc 8 . Đa thức nhiễu là 1 thách thức lớn , tuy nhiên với việc từng hệ số trong đa thức chỉ có 3 giá trị có thể trong tập errs, ta đặt ẩn 3 giá trị này là $c_1,c_2,c_3$ => mỗi vecto nhiễu ( 8x1) là 1 pattern và ta có thể nghĩ đến việc brute force pattern này chỉ với hơn 3000 case . Chiến lược tìm $c_1,c_2,c_3$ diễn ra như sau : Ta có 10 sample $(a_i,b_i)$ , ta sẽ brute force pattern của $e_0$ . Với mỗi case pattern của $e_0$ ta sẽ:

• Biễu diễn vecto $s_1$ qua công thức $s_1 = A_0^{-1} \cdot (b_0 - e_0) \pmod p$ , khi này thì mỗi hệ số $s_1[i]$ của vecto là bậc nhất của $c_1,c_2,c_3$

• Tiếp theo thì với các sample $(a_i,b_i)$ còn lại ta có $e_i = b_i - A_i \cdot s_1(c_1, c_2, c_3) \pmod{f_1}$

  • Khi này thì mỗi hệ số của vecto $e_i$ là bậc nhất của $c_1,c_2,c_3$
  • Hơn nữa với việc mỗi hệ số trong vecto $e_i$ chỉ có 1 trong 3 giá trị , điều này có nghĩa là $(e_{i, k} - c_1)(e_{i, k} - c_2)(e_{i, k} - c_3) = 0 \pmod p$ => Dễ thấy đây là 1 pt bậc 3 3 ẩn $c_1,c_2,c_3$
  • Một phương trình đa thức bậc 3 với 3 ẩn số chỉ có tổng cộng 20 đơn thức $1, c_1, c_2, c_3, c_1^2, c_1c_2, \dots, c_3^3$ => Ta có thể tuyến tính hóa thành 20 ẩn

• Từ idea này , với mỗi sample i , ta có thể lập được 8 phương trình $(e_{i, k} - c_1)(e_{i, k} - c_2)(e_{i, k} - c_3) = 0 \pmod p$ với mỗi hệ số $e_{i, k}$ , mỗi pt 20 ẩn => Ta chỉ cần 4 sample để lập thành hệ 32x20 quá đủ để giải ra được $c_1,c_2,c_3$ .

Khi mà pattern đó là đúng , hệ sẽ có nghiệm và ta sẽ có đc tập errs , từ đó khôi phục $s_1$ dễ dàng . Dưới đây là implement của phase 1

# SOLVE PHASE1 
def solve_phase1(fi, degree, samples):
    print(f"\nSolving phase 1 with f1 of deg {degree}")

    samples_5 = samples[:5]
    
    A_matrices = []
    B_vectors = []
    for a_list, b_list in samples_5:
        A_matrices.append(poly_to_matrix(R(a_list) % fi, fi, degree))
        b_coeffs = (R(b_list) % fi).list()
        B_vectors.append(vector(F, b_coeffs + [0] * (degree - len(b_coeffs))))

    A0_inv = A_matrices[0].inverse()
    v0 = A0_inv * B_vectors[0]
    M0 = A0_inv
    
    T_matrices = [A_matrices[i] * M0 for i in range(1, 5)]
    V_vectors = [B_vectors[i] - A_matrices[i] * v0 for i in range(1, 5)]

    PR.<c1, c2, c3> = PolynomialRing(F, 3)
    monomials = [PR(1), c1, c2, c3, c1^2, c1*c2, c1*c3, c2^2, c2*c3, c3^2,c1^3, c1^2*c2, c1^2*c3, c1*c2^2, c1*c2*c3, c1*c3^2,c2^3, c2^2*c3, c2*c3^2, c3^3]
    C_var = [c1, c2, c3]

    patterns = [p for p in itertools.product([0, 1, 2], repeat=degree) 
                    if set(p) == {0, 1, 2} and p.index(0) < p.index(1) and p.index(1) < p.index(2)]

    errs = []
    s1 = []
    
    for pat in patterns:
        e0_sym = vector(PR, [C_var[idx] for idx in pat])
        equations = []
        for i in range(4):
            ei_sym = V_vectors[i-1] + T_matrices[i-1] * e0_sym
            for k in range(degree):
                E = ei_sym[k]
                equations.append((E - c1) * (E - c2) * (E - c3))
                
        M_lin = matrix(F, 32, 20)
        for row_idx, eq in enumerate(equations):
            for col_idx, mon in enumerate(monomials):
                M_lin[row_idx, col_idx] = eq.monomial_coefficient(mon)
                

        ker = M_lin.right_kernel()
        if ker.dimension() > 0:
            for vec in ker.basis():
                if vec[0] != 0:
                    vec = vec / vec[0]
                    ans_c1, ans_c2, ans_c3 = vec[1], vec[2], vec[3]
                    
                    # check valid solution of c1, c2, c3
                    if vec[4] == ans_c1**2 and vec[7] == ans_c2**2:
                        errs = [int(ans_c1), int(ans_c2), int(ans_c3)]
                        e0_val = vector(F, [ans_c1 if idx==0 else (ans_c2 if idx==1 else ans_c3) for idx in pat])
                        
                        s1_val = M0 * (B_vectors[0] - e0_val)
                        s1 = list(s1_val) +  [0] * (degree - len(list(s1_val))) 
                        break
        if errs: 
            break

    if not errs:
        print("Can't find errs and s mod f1")
        sys.exit(1)
    
    print("Solved phase 1")
    print(f"errs = {errs}")
    print(f"s mod f1 = {s1}")
    
    return errs, s1

errs,s1 = solve_phase1(f1, 8, samples)

Phase 2,3,4

Việc có thể tìm ra $s \pmod {f_1}$ và tìm ra tập errs là 1 bước tiến lớn của bài toán , tuy nhiên thì việc tìm $s \pmod {f_i}$ trên các vành đa thức với $f_i$ càng lớn (16,32,64) vẫn là thử thách khó nhằn . Việc đi từ Đi từ $f$ bậc thấp lên $f$ bậc cao dường như là không thể vì định lý Số dư Trung Hoa đảm bảo các phần dư $s \pmod{f_i}$ là hoàn toàn độc lập về mặt đại số => $s \pmod{f_8}$ không rò rỉ bất kỳ một bit thông tin nào về $s \pmod{f_{64}}$ . Tôi cũng ko thể tìm ra được cách lập hệ nào để có thể giải luôn được ra vecto $s$ cũng như các vecto nhiễu . với $f_2$ có bậc 16 , ta vẫn có thể brute force 1 vector nhiễu , tuy nhiên việc này sẽ thực sự bất khả thi với bậc 32 và 64 . Tôi cũng đã tìm cách tôi ưu cân bằng giữa brute force và giải hệ nhưng việc càng lấy nhiều sample , có nhiều phương trình đồng nghĩa với số ẩn từ nhiễu $e_i$ sẽ tăng lên theo hoàn toàn dập tắt ý tưởng . Vậy nên idea cuối cùng là cố đưa bài toán về nghiệm nhỏ => dùng lattice và các thuật toán lattice reduction để giải nghiệm . Chi tiết cách làm sẽ như sau , tôi sẽ lấy ví dụ giải $f_3$ bậc 32