WHUCTF2026 校赛wp

目录

1. 签到
2. myHash
3. maybe_Wiener
4. Crychic-RSA
5. AIZO
6. teratera

---

签到

思路

已知输出是多轮随机 Base 编码并拼接 SHA1 校验后的结果，要求把它一层层拆回原文。

每一轮都是：

1. 从 b16 / b32 / b64 / b85 里随机选一个编码。
2. 计算 sha1(current)。
3. 把编码结果和 SHA1 拼起来继续下一轮。

逆向时就按这个过程倒着来，每次先把最后 20 字节拆出来，当成这一层附带的 SHA1，然后去试四种解码。谁解出来以后满足 sha1(prev) == chk，谁就是这一层对应的编码。

因为每层末尾拼的都是上一层明文的 SHA1，校验条件很强，正常情况下只会命中一种解法，所以可以稳定一层层反解。

‍完整 exp

from base64 import b16decode, b32decode, b64decode, b85decode
from hashlib import sha1

cur = open("output.txt", "rb").read()

DECS = [
    ("b16", b16decode),
    ("b32", b32decode),
    ("b64", b64decode),
    ("b85", b85decode),
]

path = []

for _ in range(16):
    data, chk = cur[:-20], cur[-20:]
    ok = []
    for name, dec in DECS:
        try:
            prev = dec(data)
        except Exception:
            continue
        if sha1(prev).digest() == chk:
            ok.append((name, prev))

    if len(ok) != 1:
        raise ValueError(f"ambiguous or failed: {[x[0] for x in ok]}")

    name, cur = ok[0]
    path.append(name)

print("decode path:", path)
print("flag:", cur.decode())

---

myHash

思路

已知服务端按 hash(secret || msg) 的方式给 token 签名，要求在不知道密钥的前提下伪造带 GetFlag 的合法请求。

题目核心代码是：

sig = whu_md5_hex(secret_key + msg, pad_lead=pad_byte)

虽然这里用的不是标准 MD5，而是题目自己写的 WHUHash128，但看 myhash.py 会发现它整体结构还是典型的迭代哈希：维护 128 bit 内部状态，按 64 字节分组做 _compress，最后把内部状态直接输出成摘要。

_compress() 末尾虽然多做了一层 cross-mixing，但那只是改了压缩函数本身，不影响“当前摘要可以当作下一轮初始状态继续处理后续分组”这个性质。所以只要能猜中原消息总长度和 padding 形式，这题照样可以做长度扩展。

本题比普通长度扩展多出来的一点，是 padding 的首字节不是固定 0x80，而是服务端随机选出来的 pad_byte。这会直接影响 glue padding，所以除了枚举 key_len，还得同时枚举 pad_lead。

利用过程就是：

1. 先拿 gift token。
2. 把返回的摘要当作哈希内部状态。
3. 在原消息后面补上合法 glue padding，再继续追加 &GetFlag=1，满足服务端检查。
4. 枚举 key_len 和 pad_lead，直到服务端接受伪造签名。

‍完整 exp

import socket
import base64
import re

from myhash import WHUHash128, md_style_padding

HOST = "127.0.0.1"
PORT = 44139

EXTRA = b"&GetFlag=1"


class Tube:
    def __init__(self, host, port):
        self.s = socket.create_connection((host, port))
        self.f = self.s.makefile("rwb", buffering=0)

    def recvuntil(self, delim: bytes):
        data = b""
        while not data.endswith(delim):
            ch = self.f.read(1)
            if not ch:
                raise EOFError("connection closed")
            data += ch
        return data

    def recvline(self):
        return self.f.readline()

    def sendline(self, data: bytes):
        self.f.write(data + b"\n")
        self.f.flush()

    def close(self):
        self.f.close()
        self.s.close()


def forge(sig_hex: str, known_msg: bytes, key_len: int, pad_lead: int, extra: bytes):
    total0 = key_len + len(known_msg)
    glue = md_style_padding(total0, pad_lead)

    h = WHUHash128(
        state=bytes.fromhex(sig_hex),
        count=total0 + len(glue),
        pad_lead=pad_lead,
    )
    new_sig = h.update(extra).hexdigest()
    forged_msg = known_msg + glue + extra
    return forged_msg, new_sig


def get_token(io: Tube):
    io.recvuntil(b"Choice> ")
    io.sendline(b"1")
    line = io.recvline().decode().strip()
    m = re.search(
        r"data=([A-Za-z0-9+/=]+)\s+sig=([0-9a-fA-F]{32})",
        line
    )
    if not m:
        raise ValueError(f"bad token line: {line}")

    data_b64 = m.group(1)
    sig = m.group(2).lower()
    msg = base64.b64decode(data_b64)
    return msg, sig


def submit(io: Tube, msg: bytes, sig: str):
    io.recvuntil(b"Choice> ")
    io.sendline(b"2")
    io.recvuntil(b"DATA_B64> ")
    io.sendline(base64.b64encode(msg))
    io.recvuntil(b"SIG> ")
    io.sendline(sig.encode())
    return io.recvline().decode(errors="replace").strip()


def main():
    io = Tube(HOST, PORT)
    known_msg, sig = get_token(io)

    print("[+] token msg =", known_msg)
    print("[+] token sig =", sig)

    key_order = [16, 24, 32] + [
        i for i in range(1, 129)
        if i not in {16, 24, 32}
    ]

    tries = 0

    for key_len in key_order:
        for pad_lead in range(256):
            tries += 1

            forged_msg, forged_sig = forge(
                sig,
                known_msg,
                key_len,
                pad_lead,
                EXTRA
            )

            resp = submit(io, forged_msg, forged_sig)

            if "flag=" in resp:
                print("[+] FOUND!")
                print(resp)
                io.close()
                return

            if tries % 50 == 0:
                print(
                    f"[*] tried {tries} combos | "
                    f"key_len={key_len} pad={pad_lead} | {resp}"
                )

    print("[-] not found")
    io.close()


if __name__ == "__main__":
    main()

---

maybe_Wiener

思路

已知 RSA 的 n、e、c，同时从出题脚本能看出：

1. p,q 共享同一大段高位，所以非常接近。
2. d 是 640 bit 素数，相对这个规模的 n 来说偏小。

这题不完全是经典的 Wiener，而是“相近 p,q + 小 d”同时用，因为经典 Wiener 依赖的是 k/d ≈ e / phi(n)。

这题里 phi(n) 没有直接给，但因为 p,q 很接近，可以先把它近似出来。

设 p = sqrt(n) + Δ, q = sqrt(n) - Δ，那么：

phi(n) = n - (p + q) + 1

而当 p,q 足够接近时，p + q ≈ 2 * sqrt(n)，于是：

phi(n) ≈ n - 2 * sqrt(n) + 1

所以可以先取：

phi0 = n - 2 * isqrt(n) + 1

把它当成 phi(n) 的近似值。这样一来，e / phi0 就会比较接近 e / phi(n)，对应的正确 k/d 仍有机会作为连分数展开中的某个收敛分数出现。

后面就按这个思路枚举收敛分数 (k, d)。如果某个候选满足：

phi = (e * d - 1) // k

再由：

p + q = n - phi + 1

推出判别式是完全平方数，并且最后能分解出 p * q = n，那这个 d 就是正确私钥。

‍完整 exp

from math import isqrt

n = 17079018232808856067759806896114156006035260880529876703723447659393496283478201040923003333160879323726172516597328180592740445782891248592832973151588182694130186175560504571057050228583199912558095180105547162773821264700567048697544514756031554953114080666328123646020447717075949675481162915086794145966045958528912457586491543973100856504194850697212533276101242655317321400312912530454494436861361594597738601281888659726708408140633053642954347870180416537472211586094132956476514970349225818899404491298095580517329113541701906189838915098526295390186689894462402334584033079700369305245153155714854636740747
e = 8925869711664293536254602790463280743603760308506333949895606365931982218910820552426976256404583292492206546362764711584430317620172342124616467959379575615120554699968276245961341947796097539609348476545129575739108904173024770423677994628015335335992787403958397205188884225599392110494029824568071570836383019857631780702084113807108723220705416286167963132119355463369756779563436048307894171012085117374094657697626086292629116792557083550670652075625174888012628706314609962385870196899561651017020024720067962045007159879342788058332124886006606916982960642980111386769354849304539381622448603860508598998387
c = 4640353323945972405587567333756911962447367346231774125060369865617631840140571335224373411764499376181563371040019628189933647339386564746727914251559717021167190277582537863057377110891810804154231518510379764349164762061682864854987321067834025578639931793733483863144837785008633112246643044094834234641831941199473862132712285063170952456578783023595969472882637161663574813104285665434923026814932593351947088259880944836224237697410438532541941823204304495503816145598398356306083830136080917957371539069236179003305527360968685496469511277872672160542847389344059045667645192804640968565347661098006757847627

phi0 = n - 2 * isqrt(n) + 1

def cont_frac(num, den):
    a = []
    while den:
        q, r = divmod(num, den)
        a.append(q)
        num, den = den, r
    return a

def convergents(cf):
    n0, d0 = cf[0], 1
    yield n0, d0
    if len(cf) == 1:
        return
    n1, d1 = cf[0] * cf[1] + 1, cf[1]
    yield n1, d1
    for a in cf[2:]:
        n0, n1 = n1, a * n1 + n0
        d0, d1 = d1, a * d1 + d0
        yield n1, d1

cf = cont_frac(e, phi0)

for k, d in convergents(cf):
    if k == 0:
        continue
    if (e * d - 1) % k != 0:
        continue

    phi = (e * d - 1) // k
    s = n - phi + 1
    delta = s * s - 4 * n
    if delta < 0:
        continue

    rt = isqrt(delta)
    if rt * rt != delta:
        continue

    p = (s + rt) // 2
    q = (s - rt) // 2
    if p * q == n:
        m = pow(c, d, n)
        flag = m.to_bytes((m.bit_length() + 7) // 8, 'big')
        print(flag.decode())
        break

---

Crychic-RSA

思路

已知三素数 RSA 的 n、e、c，并满足 q = p^2 + p + 1，要求分解 n 并还原明文。

题目表面上是多素数 RSA，但观察到 p,q 之间带了一个很强的代数关系：

q = p^2 + p + 1
n = p * q * r

如果硬从 n = p(p^2+p+1)r 直接做，式子会很难解，更自然的处理方式是把相关因子放进一个三次整系数多项式 f(X) 对应的 companion matrix 里，再利用矩阵在模因子意义下的退化性质提因子。

这里取的矩阵是：

A = [
    [0, 0, -53],
    [1, 0, -41],
    [0, 1, -25],
]

它对应多项式：

f(X) = X^3 + 25X^2 + 41X + 53

对这类矩阵，A^n mod n 的若干矩阵项会在某个素因子模下发生退化，于是这些位置往往会带上非平凡公因子。

因此只要算出 A^n mod n，然后把若干明显应该一起退化的位置拿出来做 gcd，就能把公共因子 p 提出来。

拿到 p 以后，剩下就很直接了：

q = p^2 + p + 1
r = n // (p * q)

之后按普通三素数 RSA 求 phi、求 d、解密即可。

完整 exp

from math import gcd

def matmul3(A, B, mod):
    return [[
        (
            A[i][0] * B[0][j]
            + A[i][1] * B[1][j]
            + A[i][2] * B[2][j]
        ) % mod
        for j in range(3)
    ] for i in range(3)]


def matpow3(A, e, mod):
    R = [
        [1, 0, 0],
        [0, 1, 0],
        [0, 0, 1]
    ]

    while e:
        if e & 1:
            R = matmul3(R, A, mod)

        A = matmul3(A, A, mod)
        e >>= 1

    return R


A = [
    [0, 0, (-53) % n],
    [1, 0, (-41) % n],
    [0, 1, (-25) % n],
]

M = matpow3(A, n, n)

vals = [
    M[0][1],
    M[0][2],
    M[1][0],
    M[1][2],
    M[2][0],
    M[2][1],
    (M[1][1] - M[0][0]) % n,
    (M[2][2] - M[0][0]) % n,
]

p = 0

for v in vals:
    p = gcd(p, int(v))

q = p * p + p + 1
r = n // (p * q)

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

m = pow(c, d, n)

flag = m.to_bytes(
    (m.bit_length() + 7) // 8,
    "big"
)

print(flag.decode())

---

AIZO

思路

已知签名服务的公开参数以及 p、q，并且可以对自选消息签名，要求伪造 kenjaku 的合法签名。

服务端签名结构是：

S1 = (g1^e1 * g2^e2) mod N
S2 = (h - s * S1) * inverse(e1, lambdaN) mod lambdaN
S3 = (h - t * S1 - e2 * S2) mod lambdaN

关键点有两个：

1. 题目把 p,q 直接给出来了，所以 lambdaN = lcm(p - 1, q - 1) 是已知的。
2. 私钥 s,t < 2^250，相对模数来说都很小。

所以这题应该把签名式子整理成“小未知量模方程”，再交给 HNP/LLL。

先把等式改写一下：

h - S3 ≡ t * S1 + e2 * S2 (mod lambdaN)

h ≡ s * S1 + e1 * S2 (mod lambdaN)

如果某次签名里 S2 在某个合适的模数下可逆，就能把它进一步整理成：

t * A_i ≡ C_i (mod M)
s * A_i ≡ C'_i (mod M)

这种标准的小未知量同余形式。

这里 exp 里实际用的是：

M = lambdaN // 2

原因是源码里 p = 2rp + 1, q = 2rq + 1，于是 lambdaN 天然带一个因子 2。exp 里改在 M = lambdaN / 2 = rp*rq 下整理同余，是因为对小未知量 s,t < 2^250 来说，这个模数已经足够大，仍能保留有效信息；同时去掉公共因子 2 后，S2 的可逆性条件也更干净，更适合直接套 HNP。

每拿到一组签名，就能得到一条关于 s 或 t 的模方程。由于未知量本身只有 250 bit，而模数规模接近 500 bit，三组样本就已经够构出一个很小的 HNP 格，LLL 可以直接把 s,t 恢复出来。

恢复出 s,t 以后，先本地验证：

pk == g1^s * g2^t mod N

确认私钥没算错，再自己构造 kenjaku 的合法签名提交即可。

完整 exp

#!/usr/bin/env python3

from pwn import remote, context
from hashlib import sha256
from math import gcd
from fractions import Fraction
from random import randint

context.log_level = "info"

HOST, PORT = "47.98.246.64", 13337


def lcm(a, b):
    return a // gcd(a, b) * b


def lll(basis, delta=Fraction(3, 4)):
    B = [list(r) for r in basis]
    n = len(B)

    def dot(u, v):
        return sum(a * b for a, b in zip(u, v))

    def gso():
        mu = [[Fraction(0)] * n for _ in range(n)]
        Bs = [list(b) for b in B]
        Bn = [Fraction(0)] * n

        for i in range(n):
            for j in range(i):
                mu[i][j] = Fraction(dot(B[i], Bs[j])) / Bn[j]
                Bs[i] = [
                    Bs[i][k] - mu[i][j] * Bs[j][k]
                    for k in range(n)
                ]

            Bn[i] = dot(Bs[i], Bs[i])

        return Bs, Bn, mu

    Bs, Bn, mu = gso()
    k = 1

    while k < n:
        for j in range(k - 1, -1, -1):
            if abs(mu[k][j]) > Fraction(1, 2):
                q = mu[k][j]
                r = int(q) if q >= 0 else -int(-q)
                f = q - r

                if f > Fraction(1, 2):
                    r += 1
                elif f < -Fraction(1, 2):
                    r -= 1

                if r:
                    B[k] = [
                        B[k][i] - r * B[j][i]
                        for i in range(n)
                    ]

                    Bs, Bn, mu = gso()

        if Bn[k] >= (
            delta - mu[k][k - 1] ** 2
        ) * Bn[k - 1]:
            k += 1
        else:
            B[k], B[k - 1] = B[k - 1], B[k]
            Bs, Bn, mu = gso()
            k = max(k - 1, 1)

    return B


def hnp(A, C, mod, Bnd):
    k = len(A)
    d = k + 2

    L = [[0] * d for _ in range(d)]

    for i in range(k):
        L[i][i] = mod

    for i in range(k):
        L[k][i] = A[i]
        L[k + 1][i] = C[i]

    L[k][k] = 1
    L[k + 1][k + 1] = Bnd

    for row in lll(L):
        last = row[k + 1]

        if abs(last) == Bnd:
            x = (
                1 if last > 0 else -1
            ) * row[k]

            if 0 < x < Bnd:
                return int(x)

    return None


io = remote(HOST, PORT)


def recv_int(tag):
    io.recvuntil(tag.encode() + b":")
    return int(io.recvline().strip())


pk = recv_int("pk")
g1 = recv_int("g1")
g2 = recv_int("g2")
N = recv_int("N")
p = recv_int("p")
q = recv_int("q")

print(f"[*] N has {N.bit_length()} bits")

assert p * q == N

lambdaN = lcm(p - 1, q - 1)
M = lambdaN // 2
bound = 2 ** 250


def query(msg: bytes):
    io.sendlineafter(
        b"make your choice :",
        b"LUV ME"
    )

    io.sendlineafter(
        b"your message:",
        msg
    )

    io.recvuntil(b"your sign:")

    return eval(
        io.recvline().strip().decode()
    )


sigs = []

for m in [b"a", b"b", b"c"]:
    S1, S2, S3 = query(m)
    sigs.append((m, S1, S2, S3))
    print(f"[+] got sig for {m!r}")


A, Ct, Cs = [], [], []

for m, S1, S2, S3 in sigs:
    h = int(
        sha256(m).hexdigest(),
        16
    )

    inv = pow(S2, -1, M)

    A.append(
        (-inv * S1) % M
    )

    Ct.append(
        (inv * (h - S3)) % M
    )

    Cs.append(
        (inv * h) % M
    )


print("[*] running LLL for t ...")

t = hnp(
    A,
    Ct,
    M,
    bound
)

print(f"[+] t = {t}")

print("[*] running LLL for s ...")

s = hnp(
    A,
    Cs,
    M,
    bound
)

print(f"[+] s = {s}")

assert s is not None and t is not None
assert (
    pow(g1, s, N) * pow(g2, t, N)
) % N == pk

print("[+] pk verified, secret keys recovered")


h = int(
    sha256(b"kenjaku").hexdigest(),
    16
)

while True:
    e1 = randint(1, bound - 1)
    e2 = randint(1, bound - 1)

    if gcd(e1, lambdaN) == 1 and gcd(e2, N) == 1:
        break


S1 = (
    pow(g1, e1, N)
    * pow(g2, e2, N)
) % N

S2 = (
    (h - s * S1)
    * pow(e1, -1, lambdaN)
) % lambdaN

S3 = (
    h - t * S1 - e2 * S2
) % lambdaN


Y1 = (
    pow(pk, S1, N)
    * pow(S1, S2, N)
    * pow(g2, S3, N)
) % N

Y2 = pow(
    (g1 * g2) % N,
    h,
    N
)

assert Y1 == Y2

print("[+] forged signature passes local verify")

io.sendlineafter(
    b"make your choice :",
    b"HATE ME"
)

io.sendlineafter(
    b"your sign:",
    f"({e1}, {e2}, {S2}, {S3})".encode()
)

data = io.recvall(
    timeout=5
).decode(errors="replace")

print("---- server output ----")
print(data)
print("-----------------------")

for line in data.splitlines():
    if (
        "KILL ME" in line
        or "flag" in line.lower()
        or "{" in line
    ):
        print("[FLAG?]", line)

---

teratera

思路

已知 Ring-LWE 形式的公开数据 a、b、e_list、ct，要求恢复隐藏多项式 s，再据此解出密文。

表面上看是：

b = a * s + E mod (x^256 - 1, p)

从公开的 e_list 里把误差结构拆出来，发现误差项 E 根本不随机，实际上是由两个固定整数线性组合出来的。再做降维和 LLL。

做法：

1. 先把 e[i] 写成 BASE + C1 * v + C2 * w 这种低维形式。
2. 再模 x^128 - 1 降维，并用左核把 s 消掉。
3. 最后对剩下的量做 Kannan embedding，用 LLL 找回 s。

最后再按题目的 md5(str(s)) 还原 AES key，CTR 解密。

完整 exp

#!/usr/bin/env sage

from sage.all import *
from Crypto.Cipher import AES
from hashlib import md5
import re
import time

p = 2313495809
N = 256
length = N // 4

Fp = GF(p)
R = PolynomialRing(Fp, "x")
x = R.gen()

with open("output.txt") as fh:
    data = fh.read()

a_poly = R(
    sage_eval(
        re.search(
            r"^a = (.+)$",
            data,
            re.M
        ).group(1),
        locals={"x": x}
    )
)

b_poly = R(
    sage_eval(
        re.search(
            r"^b = (.+)$",
            data,
            re.M
        ).group(1),
        locals={"x": x}
    )
)

e_list = eval(
    re.search(
        r"^e = (\[[^\]]*\])",
        data,
        re.M
    ).group(1)
)

ct = bytes.fromhex(
    re.search(
        r"^ct = (\w+)$",
        data,
        re.M
    ).group(1)
)

a_c = [int(a_poly[i]) for i in range(N)]
b_c = [int(b_poly[i]) for i in range(N)]

A_sc = 1418509
T_sc = 13658124

Tinv_A = inverse_mod(
    T_sc,
    A_sc
)

decs = []

for v in e_list:
    r_ = (
        v * Tinv_A
    ) % A_sc

    k_ = (
        v - r_ * T_sc
    ) // A_sc

    decs.append(
        (k_, r_)
    )

mink = min(
    d[0] for d in decs
)

minr = min(
    d[1] for d in decs
)

BASE_orig = (
    mink * A_sc
    + minr * T_sc
)

inv2 = inverse_mod(
    2,
    p
)

C1 = (
    (7 * A_sc + 2 * T_sc)
    * inv2
) % p

C2 = (
    A_sc * inv2
) % p

for i in range(5):
    k_, r_ = decs[i]

    u_ = k_ - mink
    v_ = r_ - minr

    w_ = 2 * u_ - 7 * v_

    assert (
        BASE_orig
        + C1 * v_
        + C2 * w_
    ) % p == e_list[i]

BASE = (
    BASE_orig - 3 * C2
) % p

print(
    f"[+] BASE={BASE} "
    f"C1={C1} C2={C2}"
)

N_r = 128

a_r_c = [
    (a_c[i] + a_c[i + N_r]) % p
    for i in range(N_r)
]

b_r_c = [
    (b_c[i] + b_c[i + N_r]) % p
    for i in range(N_r)
]

c_r = [
    (b_r_c[i] - 2 * BASE) % p
    for i in range(N_r)
]

M_A_r = Matrix(
    ZZ,
    N_r,
    length
)

for i in range(N_r):
    for j in range(length):
        M_A_r[i, j] = (
            a_r_c[(i - j) % N_r]
        )

M_A_r_Fp = M_A_r.change_ring(Fp)

K_basis = (
    M_A_r_Fp
    .left_kernel()
    .basis()
)

assert len(K_basis) == N_r - length

K = Matrix(
    ZZ,
    len(K_basis),
    N_r
)

for i, row in enumerate(K_basis):
    for j in range(N_r):
        K[i, j] = int(row[j])

assert (
    K * M_A_r
).change_ring(Fp) == 0

print(
    f"[+] left-kernel K: "
    f"{K.nrows()}x{K.ncols()}"
)

d_vec = vector(
    ZZ,
    [
        int(t) % p
        for t in K * vector(ZZ, c_r)
    ]
)

V_MAX = 246
Wp_MAX = 26

V_c = V_MAX // 2
W_c = Wp_MAX // 2

S_eq = 1 << 30

V_WT = 1
W_WT = 10
K_scale = 1

num_eq = K.nrows()

dV = dW = N_r
dim = num_eq + dV + dW

B = Matrix(
    ZZ,
    dim + 1,
    dim + 1,
    0
)

for j in range(num_eq):
    B[j, j] = p * S_eq

for i in range(dV):
    for j in range(num_eq):
        B[num_eq + i, j] = (
            C1 * int(K[j, i]) % p
        ) * S_eq

    B[
        num_eq + i,
        num_eq + i
    ] = V_WT

for i in range(dW):
    for j in range(num_eq):
        B[
            num_eq + dV + i,
            j
        ] = (
            C2 * int(K[j, i]) % p
        ) * S_eq

    B[
        num_eq + dV + i,
        num_eq + dV + i
    ] = W_WT

for j in range(num_eq):
    B[dim, j] = (
        -int(d_vec[j]) * S_eq
    )

for i in range(dV):
    B[
        dim,
        num_eq + i
    ] = -V_c * V_WT

for i in range(dW):
    B[
        dim,
        num_eq + dV + i
    ] = -W_c * W_WT

B[dim, dim] = K_scale

print(
    f"[+] lattice dim = {dim + 1}, "
    f"LLL running..."
)

t0 = time.time()

B_red = B.LLL()

print(
    f"    LLL done in "
    f"{time.time() - t0:.1f}s"
)

e_set = set(e_list)
modulus = x ** N - 1


def try_row(row):
    last = int(row[dim])

    if abs(last) != K_scale:
        return None

    if last < 0:
        row = -row

    if any(
        int(row[j]) != 0
        for j in range(num_eq)
    ):
        return None

    V_rec = [
        (
            int(row[num_eq + i])
            // V_WT
        ) + V_c
        for i in range(dV)
    ]

    Wp_rec = [
        (
            int(row[num_eq + dV + i])
            // W_WT
        ) + W_c
        for i in range(dW)
    ]

    if not (
        0 <= min(V_rec)
        and max(V_rec) <= V_MAX
    ):
        return None

    if not (
        0 <= min(Wp_rec)
        and max(Wp_rec) <= Wp_MAX
    ):
        return None

    return V_rec, Wp_rec


solved = False

for i in range(B_red.nrows()):
    parsed = try_row(
        B_red.row(i)
    )

    if parsed is None:
        continue

    V_rec, Wp_rec = parsed

    rhs = vector(
        Fp,
        [
            (
                c_r[i]
                - C1 * V_rec[i]
                - C2 * Wp_rec[i]
            ) % p
            for i in range(N_r)
        ]
    )

    try:
        s_vec = (
            M_A_r_Fp
            .solve_right(rhs)
        )
    except ValueError:
        continue

    s_coeffs = [
        int(s_vec[j])
        for j in range(length)
    ]

    s_poly = R(s_coeffs)

    prod = (
        a_poly * s_poly
    ) % modulus

    E_poly_red = (
        b_poly - prod
    ) % modulus

    E_coeffs = [
        int(E_poly_red[i])
        for i in range(N)
    ]

    matched = sum(
        1
        for v in E_coeffs
        if v in e_set
    )

    print(
        f"    candidate: "
        f"E in e-set = {matched}/{N}"
    )

    if matched != N:
        continue

    key = md5(
        str(s_poly).encode()
    ).hexdigest()

    cipher = AES.new(
        bytes.fromhex(key),
        AES.MODE_CTR,
        nonce=b"teratera"
    )

    flag = cipher.decrypt(ct)

    print("=" * 60)
    print(f"FLAG: {flag}")
    print("=" * 60)

    solved = True
    break


if not solved:
    print(
        "[debug] Shortest rows "
        "in reduced basis:"
    )

    rows_by_norm = sorted(
        [
            (
                float(B_red.row(i).norm()),
                i
            )
            for i in range(
                B_red.nrows()
            )
        ]
    )

    for norm, i in rows_by_norm[:5]:
        row = B_red.row(i)

        eq_nz = sum(
            1
            for j in range(num_eq)
            if int(row[j]) != 0
        )

        vs = [
            int(row[num_eq + k])
            for k in range(dV)
        ]

        ws = [
            int(row[num_eq + dV + k])
            for k in range(dW)
        ]

        print(
            f"  row {i}: "
            f"norm={norm:.1f}, "
            f"last={int(row[dim])}, "
            f"eq nonzero={eq_nz}, "
            f"V slot range="
            f"[{min(vs)},{max(vs)}], "
            f"W slot range="
            f"[{min(ws)},{max(ws)}]"
        )

    print(
        "\nIf this still doesn't work, "
        "try upgrading LLL to BKZ:"
    )

    print(
        "  replace B.LLL() with "
        "B.BKZ(block_size=20)"
    )

‍