2026-VNCTF-crypto-writeup

Crypto 方向

题目1：math_rsa

需要对等式左边进行化简,有：

(x^2 + 1)(y^2 + 1) = (x - y)^2 + (xy + 1)^2

接着，将 $(xy + 1)^2$ 展开并改写为含有 $(xy - 1)^2$ 的形式：

(xy + 1)^2 = (xy - 1)^2 + 4xy

将上述两个结论代入原等式的左边，替换掉 $(x^2 + 1)(y^2 + 1)$ ：

(x - y)^2 + (xy - 1)^2 + 4xy - 2(x - y)(xy - 1) = 4k + 4xy

等式两边同时消去 $4xy$ ：

(x - y)^2 - 2(x - y)(xy - 1) + (xy - 1)^2 = 4k

观察等式左边，这正好是一个完美的完全平方式 $a^2 - 2ab + b^2 = (a - b)^2$ ：

((x - y) - (xy - 1))^2 = 4k

展开括号内部进行因式分解：

(x - y - xy + 1)^2 = 4k

((1 - y)(x + 1))^2 = 4k

(1 - y)^2(x + 1)^2 = 4k

现在将题目中 $x$ 和 $y$ 的定义代入化简后的等式中。
已知 $x = \phi - 1$ ，所以：

x + 1 = \phi

已知 $y = 2u + 1$ ，所以：

1 - y = -2u

将这两个结果代入化简后的等式：

(-2u)^2(\phi)^2 = 4k

4u^2\phi^2 = 4k

u^2\phi^2 = k

两边同时开平方，得到了核心结论：

u\phi = \sqrt{k}

根据 $\phi = (p - 1)(q - 1) = n - p - q + 1$ ，因为 $p$ 和 $q$ 相比 $n$ 来说非常小（大约是 $\sqrt{n}$ 量级），所以 $\phi$ 的值非常接近 $n$ ，且略小于 $n$ 。
利用这一特性，我们可以得出：

u \approx \frac{\sqrt{k}}{n}

由于 $\phi < n$ ，所以实际的 $u$ 一定略大于 $\frac{\sqrt{k}}{n}$ 。
因此，我们可以先计算出估算值 u_estimate = isqrt(k) // n，然后从该估算值开始向上进行小范围的穷举爆破。一旦找到一个 $u$ 能够整除 $\sqrt{k}$ ，我们就可以计算出 $\phi = \frac{\sqrt{k}}{u}$ ，进而算出私钥 $d$ 并解密拿到 Flag。
exp：

from Crypto.Util.number import long_to_bytes, inverse
import math

# 题目提供的数据
n = 14070754234209585800232634546325624819982185952673905053702891604674100339022883248944477908133810472748877029408864634701590339742452010000798957135872412483891523031580735317558166390805963001389999673532396972009696089072742463405543527845901369617515343242940788986578427709036923957774197805224415531570285914497828532354144069019482248200179658346673726866641476722431602154777272137461817946690611413973565446874772983684785869431957078489177937408583077761820157276339873500082526060431619271198751378603409721518832711634990892781578484012381667814631979944383411800101335129369193315802989383955827098934489
e = 65537
c = 12312807681090775663449755503116041117407837995529562718510452391461356192258329776159493018768087453289696353524051692157990247921285844615014418841030154700106173452384129940303909074742769886414052488853604191654590458187680183616318236293852380899979151260836670423218871805674446000309373481725774969422672736229527525591328471860345983778028010745586148340546463680818388894336222353977838015397994043740268968888435671821802946193800752173055888706754526261663215087248329005557071106096518012133237897251421810710854712833248875972001538173403966229724632452895508035768462851571544231619079557987628227178358
k = 485723311775451084490131424696603828503121391558424003875128327297219030209620409301965720801386755451211861235029553063690749071961769290228672699730274712790110328643361418488523850331864608239660637323505924467595552293954200495174815985511827027913668477355984099228100469167128884236364008368230807336455721259701674165150959031166621381089213574626382643770012299575625039962530813909883594225301664728207560469046767485067146540498028505317113631970909809355823386324477936590351860786770580377775431764048693195017557432320430650328751116174124989038139756718362090105378540643587230129563930454260456320785629555493541609065309679709263733546183441765688806201058755252368942465271917663774868678682736973621371451440269201543952580232165981094719134791956854961433894740133317928275468758142862373593473875148862015695758191730229010960894713851228770656646728682145295722403096813082295018446712479920173040974429645523244575300611492359684052455691388127306813958610152185716611576776736342210195290674162667807163446158064125000445084485749597675094544031166691527647433823855652513968545236726519051559119550903995500324781631036492013723999955841701455597918532359171203698303815049834141108746893552928431581707889710001424400

# 1. 计算 sqrt(k)
sqrt_k = math.isqrt(k)

# 2. 估算 u 的值
# 根据推导：sqrt_k = u * phi，且 phi 略小于 n
# 所以 u 略大于 sqrt_k / n
u_estimate = sqrt_k // n
print(f"[*] 估算的 u 初始值 (Approximated u): {u_estimate}")

# 3. 在估算值附近爆破 u
print("[*] 开始尝试向下解密...")
for delta in range(0, 5000):
    u = u_estimate + delta  # 尝试比估算值大的数
    
    # 如果找到了能整除的 u，即找到真正的 phi
    if sqrt_k % u == 0:
        phi = sqrt_k // u
        try:
            d = inverse(e, phi)
            m = pow(c, d, n)
            flag = long_to_bytes(m)
            
            # 只有当解密出的明文包含 flag 格式时才认为是正确的
            if b'VNCTF' in flag or b'flag' in flag:
                print(f"[+] 成功找到正确的 u: {u}")
                print(f"[+] 解密成功！Flag: {flag.decode('utf-8')}")
                break
        except Exception:
            pass

题目2：Schnorr

分析源代码,关键漏洞在这两部分里：

1	self._init_deterministic_rng(init_seed)

和

1
2
3

def _init_deterministic_rng(self, seed):
    self.rng_state = sha256(str(seed).encode()).digest()
    self.counter = 0

init_seed是一个从外部库导入的变量，每次重新与容器建立连接时，_init_deterministic_rng这个函数都会以相同的初始化状态（种子）重新重置成0
也就意味着后续生成的p，g，A和b都完全一样，也就可以通过查分攻击来解密出私钥a
基于这个缺陷，我们可以发起两次连接，并针对两次不同的挑战值 $x_1$ 和 $x_2$ ，构建如下的同余方程组：

\begin{cases} z_1 \equiv x_1 \cdot a + b \pmod{p-1} \\ z_2 \equiv x_2 \cdot a + b \pmod{p-1} \end{cases}

将第二式减去第一式，即可直接消去未知的临时随机数 $b$ ：

z_2 - z_1 \equiv (x_2 - x_1) \cdot a \pmod{p-1}

在模 $p-1$ 的域下，等式两边同时乘上 $(x_2 - x_1)$ 的逆元，即可解出私钥 $a$ （即 Flag 转换而成的整数）：

a \equiv (z_2 - z_1) \cdot (x_2 - x_1)^{-1} \pmod{p-1}

令x2=2，x1=1即可
exp:

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

def get_z(x_val):
    # 连接题目
    io = remote('114.66.24.228', 34119)
    
    # 接收公开参数 p
    io.recvuntil(b'p = ')
    p = int(io.recvline().strip())
    
    # 接收 g, A, B 等直到提示输入 x
    io.recvuntil(b'x = ')
    
    # 发送 Challenge x
    io.sendline(str(x_val).encode())
    
    # 接收响应 z
    io.recvuntil(b'z = ')
    z = int(io.recvline().strip())
    
    io.close()
    return p, z

def solve():
    print("[-] Connecting first time (x=1)...")
    p, z1 = get_z(1)
    
    print("[-] Connecting second time (x=2)...")
    p2, z2 = get_z(2)
    
    # 确保两次连接的 P 是相同的（验证环境是否如预期）
    assert p == p2, "Error: p changed between connections!"
    
    print("[+] Parameters captured. Calculating flag...")
    
    # 数学推导:
    # z1 = 1*a + b (mod p-1)
    # z2 = 2*a + b (mod p-1)
    # z2 - z1 = a (mod p-1)
    
    modulus = p - 1
    a = (z2 - z1) % modulus
    
    try:
        flag = long_to_bytes(a)
        print(f"\n[SUCCESS] Flag: {flag.decode()}")
    except Exception as e:
        print(f"\n[ERROR] Failed to decode flag: {e}")
        print(f"Raw integer a: {a}")

if __name__ == '__main__':
    solve()

题目3：NumberGuesser

先生成624个32bits的hint，然后用同一个PRNGtwist得到新的一轮，生成128bits的key，并用iv=seed*2AES_CBC加密flag
目的是通过624个hint恢复key，然后利用flag头已知的VNCTF{局部爆破出seed，但是只有10次查询机会
在CPython实现MT19937的“twist”更新中，状态长度n=624，参数M=397，每一轮的新状态new_mt[kk]只由旧状态的mt[kk]，mt[kk+1]和mt[kk+M]决定
因此想要恢复新一轮的前4个32bit，只需要查询旧一轮的0,1,2,3,4，397,398,399，400即可，这样可以得到完整的key
然后利用key解密第一块密文，明文开头前6字节固定是VNCTF{，可以和密文做XOR恢复6字节的IV，剩下两个字节爆破然后验证即可
exp：

#!/usr/bin/env python3
import socket
import re
import random
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

HOST = "114.66.24.228"
PORT = 34123

# 9 个关键下标 + 第10次随便填一个合法的
QUERY_IDXS = [0, 1, 2, 3, 4, 397, 398, 399, 400, 0]
NEED_IDXS = {0, 1, 2, 3, 4, 397, 398, 399, 400}

# MT19937 常量（与 CPython _randommodule.c 一致）
N = 624
M = 397
MATRIX_A = 0x9908B0DF
UPPER_MASK = 0x80000000
LOWER_MASK = 0x7FFFFFFF

def temper(y: int) -> int:
    y &= 0xffffffff
    y ^= (y >> 11)
    y &= 0xffffffff
    y ^= (y << 7) & 0x9d2c5680
    y &= 0xffffffff
    y ^= (y << 15) & 0xefc60000
    y &= 0xffffffff
    y ^= (y >> 18)
    return y & 0xffffffff

def unshift_right_xor(y: int, shift: int) -> int:
    x = y
    for _ in range(5):
        x = y ^ (x >> shift)
    return x & 0xffffffff

def unshift_left_xor_mask(y: int, shift: int, mask: int) -> int:
    x = y
    for _ in range(5):
        x = y ^ ((x << shift) & mask)
    return x & 0xffffffff

def untemper(y: int) -> int:
    y = unshift_right_xor(y, 18)
    y = unshift_left_xor_mask(y, 15, 0xefc60000)
    y = unshift_left_xor_mask(y, 7, 0x9d2c5680)
    y = unshift_right_xor(y, 11)
    return y & 0xffffffff

def twist_one(st: list[int], i: int) -> int:
    # new_mt[i] = st[i+M] ^ (y>>1) ^ mag01[y&1]
    # y = (st[i] & UPPER_MASK) | (st[i+1] & LOWER_MASK)
    y = (st[i] & UPPER_MASK) | (st[(i + 1) % N] & LOWER_MASK)
    return (st[(i + M) % N] ^ (y >> 1) ^ (MATRIX_A if (y & 1) else 0)) & 0xffffffff

def recover_aes_key_from_9_hints(hints: dict[int, int]) -> bytes:
    # 只填我们需要的 9 个位置，其余位置不会被用到
    st = [0] * N
    for idx in NEED_IDXS:
        st[idx] = untemper(hints[idx])

    # 下一轮 twist 之后的前 4 个 state word
    new_words = [twist_one(st, i) for i in range(4)]
    r = [temper(x) for x in new_words]  # 这就是 genrand_int32 的输出

    # CPython getrandbits(128)：32-bit word 从低位到高位拼起来
    key_int = r[0] + (r[1] << 32) + (r[2] << 64) + (r[3] << 96)
    return key_int.to_bytes(16, "big")

def derive_seed_prefix_6bytes(key: bytes, ct: bytes) -> bytes:
    prefix = b"VNCTF{"
    x = AES.new(key, AES.MODE_ECB).decrypt(ct[:16])  # X = D_k(C0)
    return bytes([x[i] ^ prefix[i] for i in range(len(prefix))])  # seed[0..5]

def seed_matches_hints(seed8: bytes, hints: dict[int, int]) -> bool:
    r = random.Random()
    r.seed(seed8)

    # 先验 0..4：极快过滤
    for i in range(5):
        if r.getrandbits(32) != hints[i]:
            return False

    # 再验 397..400：确保唯一
    for _ in range(397 - 5):
        r.getrandbits(32)

    for i in range(397, 401):
        if r.getrandbits(32) != hints[i]:
            return False

    return True

def brute_force_seed(seed_prefix6: bytes, hints: dict[int, int]) -> bytes:
    for b6 in range(256):
        for b7 in range(256):
            seed = seed_prefix6 + bytes([b6, b7])
            if seed_matches_hints(seed, hints):
                return seed
    raise RuntimeError("seed brute-force failed (check parsing / key recovery).")

class Tube:
    def __init__(self, host: str, port: int, timeout: float = 10.0):
        self.s = socket.create_connection((host, port), timeout=timeout)
        self.s.settimeout(timeout)
        self.buf = b""

    def _recv_more(self):
        chunk = self.s.recv(4096)
        if not chunk:
            raise EOFError("connection closed")
        self.buf += chunk

    def recvuntil(self, token: bytes) -> bytes:
        while token not in self.buf:
            self._recv_more()
        pos = self.buf.index(token) + len(token)
        out = self.buf[:pos]
        self.buf = self.buf[pos:]
        return out

    def recvline(self) -> bytes:
        return self.recvuntil(b"\n")

    def sendline(self, line: str):
        self.s.sendall(line.encode() + b"\n")

    def close(self):
        try:
            self.s.close()
        except Exception:
            pass

def main():
    t = Tube(HOST, PORT)

    # 读到密文
    t.recvuntil(b"Encrypted flag:\n")
    hexline = t.recvline().strip()  # 注意服务端 print(hex, "\n") 会带空格/换行
    ct = bytes.fromhex(hexline.decode())
    _ = t.recvline()  # 吃掉空行

    # 拿 9 个关键 hints
    hints: dict[int, int] = {}
    for idx in QUERY_IDXS:
        t.recvuntil(b": ")          # 等待 "Enter index ...: "
        t.sendline(str(idx))
        resp = t.recvuntil(b"\n\n") # hint 行后面会有空行
        m = re.search(rb"hint\[%d\] = (\d+)" % idx, resp)
        if m and idx in NEED_IDXS:
            hints[idx] = int(m.group(1))

    t.close()

    # sanity check
    missing = sorted(list(NEED_IDXS - set(hints.keys())))
    if missing:
        raise RuntimeError(f"missing hints: {missing}")

    key = recover_aes_key_from_9_hints(hints)
    seed_prefix6 = derive_seed_prefix_6bytes(key, ct)
    seed8 = brute_force_seed(seed_prefix6, hints)

    iv = seed8 * 2
    pt = unpad(AES.new(key, AES.MODE_CBC, iv=iv).decrypt(ct), 16)
    print(pt.decode(errors="replace"))

if __name__ == "__main__":
    main()

题目4：ezov

学习这篇文章https://zhuanlan.zhihu.com/p/440168430，利用o=v的漏洞，生成伪造签名
exp：

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
ezov (Balanced OV) exploit:
1) parse pub.txt (64 public quadratic forms, n=128, GF(65537))
2) recover oil subspace W using annihilator polynomial of M = P0^{-1} P1
3) build change-of-basis S = [U|W] so oil becomes last 64 coords
4) forge signature for msg="admin"
5) connect remote and submit choice=2 + signature WITHOUT waiting for prompts
"""

import argparse
import ast
import hashlib
import os
import random
import re
import socket
import time
from typing import List, Optional, Tuple

import numpy as np
import sympy as sp


P = 0x10001
O = 64
V = 64
N = 128


# -----------------------
# GF(p) helpers
# -----------------------
def modinv(a: int, p: int = P) -> int:
    a %= p
    if a == 0:
        raise ZeroDivisionError("inv(0)")
    # since p is prime
    return pow(a, p - 2, p)


def mat_inv_mod(A: np.ndarray, p: int = P) -> np.ndarray:
    """Gauss-Jordan inversion over GF(p)."""
    A = (A % p).astype(np.int64)
    n = A.shape[0]
    I = np.eye(n, dtype=np.int64)
    aug = np.concatenate([A, I], axis=1) % p

    for col in range(n):
        pivot = None
        for r in range(col, n):
            if aug[r, col] % p != 0:
                pivot = r
                break
        if pivot is None:
            raise ValueError("singular matrix")

        if pivot != col:
            aug[[col, pivot]] = aug[[pivot, col]]

        inv_piv = modinv(int(aug[col, col]), p)
        aug[col, :] = (aug[col, :] * inv_piv) % p

        for r in range(n):
            if r == col:
                continue
            f = int(aug[r, col] % p)
            if f:
                aug[r, :] = (aug[r, :] - f * aug[col, :]) % p

    return aug[:, n:] % p


def rref_mod(A: np.ndarray, p: int = P) -> Tuple[np.ndarray, List[int]]:
    """RREF over GF(p). Return (RREF, pivot_cols)."""
    A = (A % p).astype(np.int64)
    m, n = A.shape
    pivots: List[int] = []
    row = 0

    for col in range(n):
        if row >= m:
            break

        pivot = None
        for r in range(row, m):
            if A[r, col] % p != 0:
                pivot = r
                break
        if pivot is None:
            continue

        if pivot != row:
            A[[row, pivot]] = A[[pivot, row]]

        inv_piv = modinv(int(A[row, col]), p)
        A[row, :] = (A[row, :] * inv_piv) % p

        for r in range(m):
            if r == row:
                continue
            f = int(A[r, col] % p)
            if f:
                A[r, :] = (A[r, :] - f * A[row, :]) % p

        pivots.append(col)
        row += 1

    return A, pivots


def nullspace_basis_mod(A: np.ndarray, p: int = P) -> np.ndarray:
    """
    Right nullspace basis of A over GF(p).
    Return basis vectors as rows: shape (nullity, ncols).
    """
    R, piv = rref_mod(A, p)
    m, n = R.shape
    piv_set = set(piv)
    free_cols = [c for c in range(n) if c not in piv_set]

    basis = []
    for fc in free_cols:
        x = np.zeros(n, dtype=np.int64)
        x[fc] = 1
        for r, pc in enumerate(piv):
            x[pc] = (-R[r, fc]) % p
        basis.append(x)

    return np.array(basis, dtype=np.int64)


def solve_linear_mod(A: np.ndarray, b: np.ndarray, p: int = P) -> Optional[np.ndarray]:
    """
    Solve A x = b over GF(p) with Gauss-Jordan (A must be square).
    Return x or None if singular.
    """
    A = (A % p).astype(np.int64)
    b = (b % p).astype(np.int64).reshape(-1, 1)
    n = A.shape[0]
    aug = np.concatenate([A, b], axis=1) % p

    row = 0
    for col in range(n):
        pivot = None
        for r in range(row, n):
            if aug[r, col] % p != 0:
                pivot = r
                break
        if pivot is None:
            return None

        if pivot != row:
            aug[[row, pivot]] = aug[[pivot, row]]

        inv_piv = modinv(int(aug[row, col]), p)
        aug[row, :] = (aug[row, :] * inv_piv) % p

        for r in range(n):
            if r == row:
                continue
            f = int(aug[r, col] % p)
            if f:
                aug[r, :] = (aug[r, :] - f * aug[row, :]) % p

        row += 1

    return aug[:, n].reshape(-1) % p


# -----------------------
# parse pub / hash
# -----------------------
def load_pub(path: str) -> List[np.ndarray]:
    pub = []
    with open(path, "r", encoding="utf-8", errors="ignore") as f:
        for _ in range(O):
            f.readline()  # header line
            s = "".join(f.readline().strip() for __ in range(N))
            mat = np.array(ast.literal_eval(s), dtype=np.int64) % P
            pub.append(mat)
    return pub


def hash_vec(msg: str) -> np.ndarray:
    h = hashlib.shake_128(msg.encode()).hexdigest(128)
    arr = [int(h[i:i + 4], 16) % P for i in range(0, len(h), 4)]
    assert len(arr) == O
    return np.array(arr, dtype=np.int64)


# -----------------------
# oil space recovery
# -----------------------
def krylov_annihilator_poly(M: np.ndarray, v: np.ndarray) -> sp.Poly:
    """
    Find non-zero poly a(x)=a0+...+ad x^d s.t. a(M)v=0 by
    solving K*c=0 for K=[v, Mv, ..., M^N v], K in GF(p)^{N x (N+1)}.
    """
    cols = []
    w = v.copy() % P
    for _ in range(N + 1):
        cols.append(w.copy())
        w = (M @ w) % P
    K = np.stack(cols, axis=1) % P  # (N, N+1)

    ns = nullspace_basis_mod(K, P)
    if ns.shape[0] == 0:
        raise RuntimeError("unexpected: nullspace empty")
    c = ns[0] % P

    # trim to highest non-zero degree
    nz = np.nonzero(c)[0]
    d = int(nz.max())
    c = c[:d + 1] % P

    # normalize lead coef to 1
    inv_lead = modinv(int(c[-1]), P)
    c = (c * inv_lead) % P

    x = sp.Symbol("x")
    # sympy wants high->low, while c is low->high
    return sp.Poly([int(t) for t in c[::-1]], x, modulus=P)


def poly_eval_matrix(poly: sp.Poly, M: np.ndarray) -> np.ndarray:
    """Compute poly(M) mod P with Horner."""
    coeffs = [int(c) % P for c in poly.all_coeffs()]  # high->low
    I = np.eye(N, dtype=np.int64)
    R = (coeffs[0] * I) % P
    for a in coeffs[1:]:
        R = (R @ M + (a % P) * I) % P
    return R % P


def recover_oil_space(pub: List[np.ndarray], max_tries: int = 30) -> np.ndarray:
    """
    Recover W (128x64) oil subspace columns.
    Strategy:
      M = P0^{-1} P1
      get annihilator poly f(x) for random v
      g = squarefree(f) = f / gcd(f, f')
      W = ker(g(M)) ; then verify W^T P_i W = 0 for all i
    """
    inv0 = mat_inv_mod(pub[0], P)
    M = (inv0 @ pub[1]) % P
    x = sp.Symbol("x")

    for t in range(1, max_tries + 1):
        v = np.random.randint(0, P, size=N, dtype=np.int64)
        f = krylov_annihilator_poly(M, v)

        # squarefree part
        g = f.quo(sp.gcd(f, f.diff()))
        if g.degree() != O:
            # often we need the factor that corresponds to the repeated eigen-space
            continue

        GM = poly_eval_matrix(g, M)
        ns = nullspace_basis_mod(GM, P)  # rows: 64 x 128 expected
        if ns.shape[0] != O:
            continue
        W = (ns.T) % P  # 128 x 64

        # verify isotropic: W^T P_i W == 0
        ok = True
        for i in range(O):
            K = (W.T @ pub[i] @ W) % P
            if not np.all(K == 0):
                ok = False
                break
        if ok:
            return W

    raise RuntimeError("failed to recover oil space; try rerun / increase max_tries")


def extend_to_full_basis(W: np.ndarray) -> np.ndarray:
    """
    Build invertible S = [U|W] where W is last 64 columns.
    Method: start with columns=W, add standard basis vectors that increase rank.
    """
    cols = [W[:, i].copy() for i in range(W.shape[1])]
    cur = np.column_stack(cols) % P
    _, piv = rref_mod(cur.copy(), P)
    cur_rank = len(piv)

    # add from standard basis
    for i in range(N):
        if len(cols) >= N:
            break
        e = np.zeros(N, dtype=np.int64)
        e[i] = 1
        cand = np.column_stack([cur, e]) % P
        _, piv2 = rref_mod(cand.copy(), P)
        if len(piv2) == cur_rank + 1:
            cols.append(e)
            cur = cand
            cur_rank += 1

    # if still not full rank, add random
    while len(cols) < N:
        e = np.random.randint(0, P, size=N, dtype=np.int64)
        cand = np.column_stack([cur, e]) % P
        _, piv2 = rref_mod(cand.copy(), P)
        if len(piv2) == cur_rank + 1:
            cols.append(e)
            cur = cand
            cur_rank += 1

    B = np.column_stack(cols) % P  # [W | U] but full basis
    U = B[:, O:] % P
    S = np.column_stack([U, W]) % P  # [U | W] oil last
    return S


def transform_pub(pub: List[np.ndarray], S: np.ndarray) -> List[np.ndarray]:
    St = S.T % P
    return [((St @ Pm @ S) % P) for Pm in pub]


# -----------------------
# forge signature
# -----------------------
def verify(pub: List[np.ndarray], sig: np.ndarray, h: np.ndarray) -> bool:
    sig = sig % P
    for i in range(O):
        if int((sig @ pub[i] @ sig) % P) != int(h[i]) % P:
            return False
    return True


def forge_admin_signature(pub: List[np.ndarray]) -> np.ndarray:
    h = hash_vec("admin")
    print("[*] Recovering oil space ...")
    W = recover_oil_space(pub)
    print("[+] Oil space recovered!")

    print("[*] Building basis transform ...")
    S = extend_to_full_basis(W)
    pub_t = transform_pub(pub, S)

    inv2 = modinv(2, P)

    print("[*] Forging signature for 'admin' ...")
    tries = 0
    while True:
        tries += 1
        x = np.random.randint(0, P, size=V, dtype=np.int64)  # vinegar (first 64)
        L = np.zeros((O, O), dtype=np.int64)
        rhs = np.zeros(O, dtype=np.int64)

        for i in range(O):
            Pi = pub_t[i]
            A = Pi[:V, :V]   # Qvv
            B = Pi[:V, V:]   # Qvo
            const = int((x @ A @ x) % P)
            row = (x @ B) % P  # length 64
            L[i, :] = row
            rhs[i] = ((int(h[i]) - const) % P) * inv2 % P

        y = solve_linear_mod(L, rhs, P)
        if y is None:
            continue

        z = np.concatenate([x, y]) % P
        sig = (S @ z) % P
        if verify(pub, sig, h):
            print(f"[+] Signature forged! (tries={tries})")
            return sig


def fmt_signature(sig: np.ndarray) -> str:
    sig = sig % P
    return "(" + ",".join(str(int(t)) for t in sig.tolist()) + ")"


# -----------------------
# network interaction (robust: do not wait prompts)
# -----------------------
def recv_some(sock: socket.socket, total_timeout: float = 1.0) -> bytes:
    """
    Try to read as much as possible within total_timeout.
    """
    end = time.time() + total_timeout
    data = b""
    while time.time() < end:
        sock.settimeout(0.2)
        try:
            chunk = sock.recv(4096)
        except socket.timeout:
            continue
        if not chunk:
            break
        data += chunk
        # extend slightly if we just got data
        end = max(end, time.time() + 0.2)
    return data


def submit_and_get_flag(host: str, port: int, sig_str: str, verbose: bool = True) -> Optional[str]:
    """
    The server script does:
        menu(); choice=int(input('>'))
        if choice==2: sig=input('your signature:')
                     if verify('admin',sig): print(flag)
    Some deployments may buffer stdout, so we send inputs without waiting:
        "2\n" + "<sig>\n"
    Then read output and regex VNCTF{...}.
    """
    s = socket.create_connection((host, port), timeout=8.0)
    try:
        # best effort read initial banner (may be empty)
        if verbose:
            b0 = recv_some(s, total_timeout=0.8)
            if b0:
                print(b0.decode(errors="ignore"), end="")

        payload = f"2\n{sig_str}\n".encode()
        s.sendall(payload)

        out = b""
        deadline = time.time() + 12.0
        while time.time() < deadline:
            out += recv_some(s, total_timeout=0.8)
            m = re.search(rb"VNCTF\{.*?\}", out)
            if m:
                flag = m.group(0).decode(errors="ignore")
                if verbose:
                    print(out.decode(errors="ignore"), end="")
                    print("\n[FLAG] " + flag)
                return flag

        if verbose:
            if out:
                print(out.decode(errors="ignore"), end="")
            print("\n[!] No VNCTF{...} found in output.")
        return None
    finally:
        s.close()


# -----------------------
# main
# -----------------------
def main():
    ap = argparse.ArgumentParser(description="ezov auto exploit (forge admin sig + fetch flag)")
    ap.add_argument("--host", default="114.66.24.228")
    ap.add_argument("--port", default=34122, type=int)
    ap.add_argument("--pub", default="pub.txt")
    ap.add_argument("--no-remote", action="store_true", help="only forge signature, don't connect")
    ap.add_argument("--verbose", action="store_true", help="print remote outputs")
    args = ap.parse_args()

    if not os.path.exists(args.pub):
        raise FileNotFoundError(f"pub file not found: {args.pub}")

    print("[*] Loading pubkey ...")
    pub = load_pub(args.pub)
    print("[+] pub loaded.")

    sig = forge_admin_signature(pub)
    sig_str = fmt_signature(sig)
    print("[*] admin signature:")
    print(sig_str)

    if args.no_remote:
        return

    print(f"[*] Connecting to {args.host}:{args.port} and submitting ...")
    submit_and_get_flag(args.host, args.port, sig_str, verbose=True or args.verbose)


if __name__ == "__main__":
    main()

题目5：HD_is_what

一个简单的sidh算法，具体攻击方式参照以下仓库：https://github.com/GiacomoPope/Castryck-Decru-SageMath
首先从 output.txt 中读取系统参数
Alice 和 Bob 的公钥被一个基于LCG的矩阵 M 混淆了
但是LCG 种子已知，可以构造矩阵:
对角线元素：next_rand() % 10 + 10
非对角线元素：next_rand() % 5
通过求解线性方程组 V = Y M^{-1} 恢复原始向量 V
然后就可以参照仓库中的示例进行Castryck-Decru 攻击
获得私钥后计算共享同源获取 j-invariant进行AES解密
exp：

import ast

# 1) 读输出
data = ast.literal_eval(open("output.txt","r").read())
bob_obf   = data["bob_obfuscated"]
alice_obf = data["alice_obfuscated"]

# 2) 参数
a=82; b=57
p = 2**a * 3**b - 1
dim=12
MOD=2**32
state = p % MOD

def next_rand():
    global state
    state = (state * 1664525 + 1013904223) % MOD
    return state

def gen_matrix():
    vals = [next_rand()%15 for _ in range(dim*dim)]
    return [vals[i*dim:(i+1)*dim] for i in range(dim)]

M_bob   = gen_matrix()
M_alice = gen_matrix()

# 3) 矩阵逆（模 p）
def mat_inv_mod(M, mod):
    n=len(M)
    A=[[M[i][j]%mod for j in range(n)] + [1 if i==j else 0 for j in range(n)] for i in range(n)]
    for col in range(n):
        pivot=None
        for r in range(col,n):
            if A[r][col] % mod != 0:
                pivot=r; break
        if pivot is None:
            raise ValueError("not invertible")
        A[col],A[pivot]=A[pivot],A[col]
        inv_p = pow(A[col][col], mod-2, mod)
        for c in range(2*n):
            A[col][c]=(A[col][c]*inv_p) % mod
        for r in range(n):
            if r==col: continue
            f=A[r][col]
            if f:
                for c in range(2*n):
                    A[r][c]=(A[r][c]-f*A[col][c])%mod
    return [row[n:] for row in A]

def vec_mat_mul(v, M, mod):
    n=len(v); m=len(M[0])
    out=[0]*m
    for j in range(m):
        s=0
        for i in range(n):
            s = (s + (v[i]%mod)*M[i][j]) % mod
        out[j]=s
    return out

inv_bob   = mat_inv_mod(M_bob, p)
inv_alice = mat_inv_mod(M_alice, p)

bob_raw_vec   = vec_mat_mul([x%p for x in bob_obf],   inv_bob,   p)
alice_raw_vec = vec_mat_mul([x%p for x in alice_obf], inv_alice, p)

print("bob_raw_vec =", bob_raw_vec)
print("alice_raw_vec =", alice_raw_vec)