湾区杯-2026

2026-09-12/更新于 2026-09-16

TinyNTRU

源码

#!/usr/bin/env python3
from __future__ import annotations

import random
from typing import NamedTuple


class NTRUParams(NamedTuple):
    N: int = 127
    p: int = 3
    q: int = 12289
    df: int = 7
    dg: int = 7
    dr: int = 6
    chunk_bytes: int = 24


class PublicKey(NamedTuple):
    h: list[int]


class PrivateKey(NamedTuple):
    f: list[int]
    g: list[int]


def _trim(poly: list[int], n: int) -> list[int]:
    return (poly + [0] * n)[:n]


def mod_center(x: int, modulus: int) -> int:
    x %= modulus
    if x > modulus // 2:
        x -= modulus
    return x


def center_lift(poly: list[int], modulus: int) -> list[int]:
    return [mod_center(x, modulus) for x in poly]


def poly_add(a: list[int], b: list[int], n: int, modulus: int | None = None) -> list[int]:
    out = [(_trim(a, n)[i] + _trim(b, n)[i]) for i in range(n)]
    if modulus is not None:
        out = [x % modulus for x in out]
    return out


def poly_mul(a: list[int], b: list[int], n: int, modulus: int | None = None) -> list[int]:
    a = _trim(a, n)
    b = _trim(b, n)
    out = [0] * n
    for i, ai in enumerate(a):
        if ai == 0:
            continue
        for j, bj in enumerate(b):
            if bj:
                out[(i + j) % n] += ai * bj
    if modulus is not None:
        out = [x % modulus for x in out]
    return out


def _inv_mod(x: int, modulus: int) -> int:
    return pow(x % modulus, -1, modulus)


def _solve_mod(matrix: list[list[int]], target: list[int], modulus: int) -> list[int]:
    n = len(target)
    aug = [[matrix[r][c] % modulus for c in range(n)] + [target[r] % modulus] for r in range(n)]
    row = 0
    for col in range(n):
        pivot = None
        for r in range(row, n):
            if aug[r][col] % modulus:
                pivot = r
                break
        if pivot is None:
            continue
        aug[row], aug[pivot] = aug[pivot], aug[row]
        inv = _inv_mod(aug[row][col], modulus)
        aug[row] = [(v * inv) % modulus for v in aug[row]]
        for r in range(n):
            if r == row:
                continue
            factor = aug[r][col] % modulus
            if factor:
                aug[r] = [(aug[r][c] - factor * aug[row][c]) % modulus for c in range(n + 1)]
        row += 1
    if row != n:
        raise ValueError("polynomial is not invertible")
    return [aug[i][-1] % modulus for i in range(n)]


def poly_inv(poly: list[int], n: int, modulus: int) -> list[int]:
    poly = _trim(poly, n)
    matrix = [[poly[(r - c) % n] for c in range(n)] for r in range(n)]
    target = [1] + [0] * (n - 1)
    inv = _solve_mod(matrix, target, modulus)
    if poly_mul(inv, poly, n, modulus) != target:
        raise ValueError("inverse verification failed")
    return inv


def sample_sparse_ternary(n: int, weight: int, rng: random.Random, avoid_zero: bool = False) -> list[int]:
    positions = list(range(1 if avoid_zero else 0, n))
    chosen = rng.sample(positions, weight)
    rng.shuffle(chosen)
    pos_count = (weight + 1) // 2
    poly = [0] * n
    for idx, coeff_index in enumerate(chosen):
        poly[coeff_index] = 1 if idx < pos_count else -1
    return poly


def keygen(params: NTRUParams, rng: random.Random) -> tuple[PublicKey, PrivateKey]:
    while True:
        F = sample_sparse_ternary(params.N, params.df, rng, avoid_zero=True)
        G = sample_sparse_ternary(params.N, params.dg, rng)
        f = [0] * params.N
        f[0] = 1
        f = poly_add(f, [params.p * x for x in F], params.N)
        g = [params.p * x for x in G]
        try:
            finv_q = poly_inv(f, params.N, params.q)
        except ValueError:
            continue
        h = poly_mul(finv_q, g, params.N, params.q)
        return PublicKey(h), PrivateKey(f, g)


def encrypt(message: list[int], public_key: PublicKey, params: NTRUParams, rng: random.Random) -> list[int]:
    r = sample_sparse_ternary(params.N, params.dr, rng)
    noisy = poly_mul(r, public_key.h, params.N, params.q)
    return poly_add(noisy, _trim(message, params.N), params.N, params.q)


def decrypt(ciphertext: list[int], private_key: PrivateKey, params: NTRUParams) -> list[int]:
    lifted = center_lift(poly_mul(private_key.f, ciphertext, params.N, params.q), params.q)
    return [x % params.p for x in lifted]


def bytes_to_poly_blocks(data: bytes, n: int, chunk_bytes: int) -> list[list[int]]:
    if 3**n <= 256**chunk_bytes:
        raise ValueError("chunk_bytes is too large for this polynomial degree")
    payload = len(data).to_bytes(2, "big") + data
    blocks = []
    for start in range(0, len(payload), chunk_bytes):
        chunk = payload[start : start + chunk_bytes]
        value = int.from_bytes(chunk, "little")
        trits = []
        for _ in range(n):
            trits.append(value % 3)
            value //= 3
        if value:
            raise ValueError("chunk does not fit into one polynomial")
        blocks.append(trits)
    return blocks


def poly_blocks_to_bytes(blocks: list[list[int]], chunk_bytes: int) -> bytes:
    raw = bytearray()
    for block in blocks:
        value = 0
        for coeff in reversed(block):
            value = value * 3 + (coeff % 3)
        raw.extend(value.to_bytes(chunk_bytes, "little"))
    if len(raw) < 2:
        raise ValueError("missing length prefix")
    size = int.from_bytes(raw[:2], "big")
    return bytes(raw[2 : 2 + size])

challenge.py

#!/usr/bin/env python3
from __future__ import annotations

import random
from typing import NamedTuple


class NTRUParams(NamedTuple):
    N: int = 127
    p: int = 3
    q: int = 12289
    df: int = 7
    dg: int = 7
    dr: int = 6
    chunk_bytes: int = 24


class PublicKey(NamedTuple):
    h: list[int]


class PrivateKey(NamedTuple):
    f: list[int]
    g: list[int]


def _trim(poly: list[int], n: int) -> list[int]:
    return (poly + [0] * n)[:n]


def mod_center(x: int, modulus: int) -> int:
    x %= modulus
    if x > modulus // 2:
        x -= modulus
    return x


def center_lift(poly: list[int], modulus: int) -> list[int]:
    return [mod_center(x, modulus) for x in poly]


def poly_add(a: list[int], b: list[int], n: int, modulus: int | None = None) -> list[int]:
    out = [(_trim(a, n)[i] + _trim(b, n)[i]) for i in range(n)]
    if modulus is not None:
        out = [x % modulus for x in out]
    return out


def poly_mul(a: list[int], b: list[int], n: int, modulus: int | None = None) -> list[int]:
    a = _trim(a, n)
    b = _trim(b, n)
    out = [0] * n
    for i, ai in enumerate(a):
        if ai == 0:
            continue
        for j, bj in enumerate(b):
            if bj:
                out[(i + j) % n] += ai * bj
    if modulus is not None:
        out = [x % modulus for x in out]
    return out


def _inv_mod(x: int, modulus: int) -> int:
    return pow(x % modulus, -1, modulus)


def _solve_mod(matrix: list[list[int]], target: list[int], modulus: int) -> list[int]:
    n = len(target)
    aug = [[matrix[r][c] % modulus for c in range(n)] + [target[r] % modulus] for r in range(n)]
    row = 0
    for col in range(n):
        pivot = None
        for r in range(row, n):
            if aug[r][col] % modulus:
                pivot = r
                break
        if pivot is None:
            continue
        aug[row], aug[pivot] = aug[pivot], aug[row]
        inv = _inv_mod(aug[row][col], modulus)
        aug[row] = [(v * inv) % modulus for v in aug[row]]
        for r in range(n):
            if r == row:
                continue
            factor = aug[r][col] % modulus
            if factor:
                aug[r] = [(aug[r][c] - factor * aug[row][c]) % modulus for c in range(n + 1)]
        row += 1
    if row != n:
        raise ValueError("polynomial is not invertible")
    return [aug[i][-1] % modulus for i in range(n)]


def poly_inv(poly: list[int], n: int, modulus: int) -> list[int]:
    poly = _trim(poly, n)
    matrix = [[poly[(r - c) % n] for c in range(n)] for r in range(n)]
    target = [1] + [0] * (n - 1)
    inv = _solve_mod(matrix, target, modulus)
    if poly_mul(inv, poly, n, modulus) != target:
        raise ValueError("inverse verification failed")
    return inv


def sample_sparse_ternary(n: int, weight: int, rng: random.Random, avoid_zero: bool = False) -> list[int]:
    positions = list(range(1 if avoid_zero else 0, n))
    chosen = rng.sample(positions, weight)
    rng.shuffle(chosen)
    pos_count = (weight + 1) // 2
    poly = [0] * n
    for idx, coeff_index in enumerate(chosen):
        poly[coeff_index] = 1 if idx < pos_count else -1
    return poly


def keygen(params: NTRUParams, rng: random.Random) -> tuple[PublicKey, PrivateKey]:
    while True:
        F = sample_sparse_ternary(params.N, params.df, rng, avoid_zero=True)
        G = sample_sparse_ternary(params.N, params.dg, rng)
        f = [0] * params.N
        f[0] = 1
        f = poly_add(f, [params.p * x for x in F], params.N)
        g = [params.p * x for x in G]
        try:
            finv_q = poly_inv(f, params.N, params.q)
        except ValueError:
            continue
        h = poly_mul(finv_q, g, params.N, params.q)
        return PublicKey(h), PrivateKey(f, g)


def encrypt(message: list[int], public_key: PublicKey, params: NTRUParams, rng: random.Random) -> list[int]:
    r = sample_sparse_ternary(params.N, params.dr, rng)
    noisy = poly_mul(r, public_key.h, params.N, params.q)
    return poly_add(noisy, _trim(message, params.N), params.N, params.q)


def decrypt(ciphertext: list[int], private_key: PrivateKey, params: NTRUParams) -> list[int]:
    lifted = center_lift(poly_mul(private_key.f, ciphertext, params.N, params.q), params.q)
    return [x % params.p for x in lifted]


def bytes_to_poly_blocks(data: bytes, n: int, chunk_bytes: int) -> list[list[int]]:
    if 3**n <= 256**chunk_bytes:
        raise ValueError("chunk_bytes is too large for this polynomial degree")
    payload = len(data).to_bytes(2, "big") + data
    blocks = []
    for start in range(0, len(payload), chunk_bytes):
        chunk = payload[start : start + chunk_bytes]
        value = int.from_bytes(chunk, "little")
        trits = []
        for _ in range(n):
            trits.append(value % 3)
            value //= 3
        if value:
            raise ValueError("chunk does not fit into one polynomial")
        blocks.append(trits)
    return blocks


def poly_blocks_to_bytes(blocks: list[list[int]], chunk_bytes: int) -> bytes:
    raw = bytearray()
    for block in blocks:
        value = 0
        for coeff in reversed(block):
            value = value * 3 + (coeff % 3)
        raw.extend(value.to_bytes(chunk_bytes, "little"))
    if len(raw) < 2:
        raise ValueError("missing length prefix")
    size = int.from_bytes(raw[:2], "big")
    return bytes(raw[2 : 2 + size])

分析

简易版的 NTRU 密码体制。多项式在 $R = Z [x] / (x^{N} - 1)$ 上运算，溢出回绕（ $x^{N} = 1$ ）。小模数 $p = 3$ 用于解密时消去杂项，大模数 $q = 12289$ 用于混淆，且其本身需要足够大以保证解密时不回绕。一次标准的加解密流程如下：

采样稀疏多项式 $F, G$ （在 $N = 127$ 的最高次数下只有 $d_{f} = d_{g} = 7$ 项系数不为零。生成 $F$ 时传入 avoid_zero=True 以使后续构造 $f = p F + 1$ 时常数项一定为 $1$ ）
构造私钥多项式 $f = p F + 1, g = p G$ 。 $f$ 的这种特殊形式保证了 $f \equiv 1 (\mod p)$ ，进而直接得到 $f_{p}^{- 1} \equiv 1 (\mod p)$ 。保密私钥 $(f, g)$ 。
计算 $f_{q}^{- 1} mod q$ ，公开公钥 $h = f_{q}^{- 1} \cdot g (\mod q)$ 。
针对明文多项式（系数属于 $0, 1, 2$ ）采样稀疏的扰动多项式 $r$ （只有 $d_{r} = 6$ 项非零系数），计算密文 $c = r \cdot h + m (\mod q)$ 。

解密时，计算：

a \equiv f \cdot c \equiv f \cdot (f_{q}^{- 1} g \cdot r + m) \equiv g \cdot r + f \cdot m (\mod q)

根据 $f = p F + 1, g = p G$ 展开：

a \equiv p G \cdot r + p F \cdot m + m \equiv p (G r + F m) + m (\mod q)

由于 $G, F, r, m$ 都是稀疏或小因子多项式，系数项的绝对值远小于 $q / 2$ 。进行中心化提升后模 $q$ 带来的影响被抹平，此时的 $a$ 在整数环上。最终计算 $a mod p = m$ ，得到明文多项式。

为什么要做中心化提升？在有限域上，当最终多项式的系数产生负数时会发生回绕（ $k_{n e w} = k + q$ ）。根据模运算，相加后取模等于取模后相加。 $q mod p = 1$ ，导致算出来的系数等于真实系数加 1，解密产生错误。而中心化提升就是把大于 $q / 2$ 的系数看作负数，只要参数选取正确，最终得到的 $a$ 没有能够达到 $q / 2$ 的系数项，负数依然是负数，不会发生回绕，解密也就准确无误。

调用原代码，看一下最终多项式 $g \cdot r + f \cdot m$ 的真实大小（单个明文多项式最多能编码的字节数为 22，即 chunk_bytes 减去 2 字节的长度前缀）：

[-8, 7, -2, 0, 1, 12, 0, 5, 14, 1, 3, 14, 3, 17, -2, 10, 7, 9, 6, -10, 0, 7, -4, 7, -1, 5, 2, 13, 5, -1, 7, 4, 10, 11, -3, 2, 3, 10, 6, 2, -8, -8, 7, -1, 3, -1, -5, 9, -4, 13, 0, 6, 9, 7, -5, 11, -6, 10, 8, 10, 0, 0, 15, 4, 11, 5, 1, 1, 13, 10, -4, 8, 6, -6, 11, 12, 4, 12, 4, 4, -4, 2, 10, 8, 13, 1, 1, 10, 8, -7, -5, 1, 10, 8, 14, -1, -5, 1, -3, 10, 6, -4, 3, 3, -8, 6, 2, 4, 0, 2, 6, -1, -5, 0, 5, 5, 6, 9, 16, 13, 6, -6, 3, 12, 9, 0, -6]

可以看到系数远小于 $q / 2$ 。

本题中参数太小了，直接 LLL 做约简找最短向量就能还原出私钥 $(f, g)$ 。讲一下造格基的思路：

根据 NTRU 的公钥生成式 $h \equiv f^{- 1} \cdot g (\mod q)$ 推出等式 $f \cdot h - g = k \cdot q$ 。如果 $f, g$ 是标量，那么显然：

L = (\begin{matrix} 1 & h \\ 0 & q \end{matrix})

但它们都是 127 项的多项式。那么核心问题在于，如何用向量与矩阵的乘法完全等价代替两个多项式的循环乘法？

根据环的定义，多项式运算是在模 $x^{N} - 1$ 下进行的：

f (x) \cdot h (x) = (\sum_{i = 0}^{N - 1} f_{i} x^{i}) \cdot h (x) = f_{0} \cdot h (x) + f_{1} \cdot [x \cdot h (x)] + f_{2} \cdot [x^{2} \cdot h (x)] + \dots

观察每一项，当系数为 $f_{i}$ 时，它乘的是 $x^{i} \cdot h (x)$ 。在模 $x^{N} - 1$ 下， $x \cdot h (x)$ 会发生回绕：

x \cdot h (x) = h_{N - 1} + h_{0} x + h_{1} x^{2} + \dots + h_{N - 2} x^{N - 1}

$x^{2} \cdot h (x)$ 可以看作 $x \cdot (x \cdot h (x))$ ，此时结果为 $h_{N - 2} + h_{N - 1} x + h_{0} x^{2} + \dots + h_{N - 3} x^{N - 1}$ 。

发现多项式每乘以一个 $x$ ，其系数向量就会循环右移一位。

把多项式记为 $f = (\begin{matrix} f_{0}, & f_{1}, & f_{2}, & \dots, & f_{N - 1} \end{matrix})$ 。根据循环右移的性质，我们把 $x^{i} \cdot h (x)$ 产生的基准多项式系数一行一行拼接为循环矩阵：

H = (\begin{matrix} h_{0} & h_{1} & h_{2} & \dots & h_{N - 1} \\ h_{N - 1} & h_{0} & h_{1} & \dots & h_{N - 2} \\ h_{N - 2} & h_{N - 1} & h_{0} & \dots & h_{N - 3} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ h_{1} & h_{2} & h_{3} & \dots & h_{0} \end{matrix})

用行向量 $f$ 左乘，得到的行向量恰好等于最终多项式的系数向量。对于原本的标量公式 $k \times 1 = k$ 来说，要让行向量 $f$ 乘完依然是 $f$ ，这个变换就是 $N \times N$ 的单位矩阵 $I_{N}$ 。对于 $k \times q = k q$ ，设 $k (x)$ 的系数行向量为 $k = (k_{0}, k_{1}, \dots, k_{N - 1})$ ，那么它乘上对角线均为 $q$ 的矩阵就会得到 $k \cdot (q I_{N}) = (k_{0} q, k_{1} q, \dots, k_{N - 1} q)$ ，也恰好等于多项式 $k (x) \cdot q$ 的系数向量。而关于 $f \cdot h$ ，上方的循环矩阵已经能代表二者相乘的特征。

最终得到格基：

L = (\begin{matrix} I_{N} & H \\ 0_{N} & q I_{N} \end{matrix})

(f, - k) (\begin{matrix} I_{N} & H \\ 0_{N} & q I_{N} \end{matrix}) = (f, g)

接下来讲一下 LLL 算法生效的条件。由高斯启发式和斯特林公式得到一般格基中最短向量的估计值：

GH (L) \approx \sqrt{\frac{d}{2 π e}} \cdot (det L)^{1 / d}

最短向量上界为：

λ (L) \leq \sqrt{d} \cdot (det L)^{1 / d}

当格基维度增加时，LLL 算法面临着 Unique-SVP 问题：其能寻找到的最短向量相比于理论估计值具有放大倍数的关系。对于随机格或高维密码学格，LLL 输出向量长度的实证模型为：

‖ b_{1} ‖ \approx δ_{root}^{d} \cdot (det L)^{1 / d}

其中 $δ_{root} \approx 1.021 \sim 1.022$ 。也就是说在实际表现中，平均每增加一个维度，实际找到的向量相对于真实最短向量就会额外放大约 $2.1 % \sim 2.2 %$ 。换成容易理解的话来说，如果想让 LLL 把你需要的目标向量抓出来，目标向量的长度至少要比普通向量短 $δ_{r o o t}^{d}$ 倍。

本题中 $N = 127, q = 12289$ ，格维度 $d = 2 N = 254$ ， $det L = q^{N} = 12289^{127}$ ，归一化体积 $(det L)^{1 / d} = q^{1 / 2} \approx 110.85$ 。

由高斯启发式， $GH (L) = 427.5$ ，即普通向量的长度在 400 到 500 之间。目标向量长度 $λ = ‖ (f, g) ‖ = \sqrt{‖ f ‖^{2} + ‖ g ‖^{2}} \approx \sqrt{64 + 63} = \sqrt{127} \approx 11.27$ ，可知私钥向量长度比格中的普通向量短了 $427.5 / 11.27 \approx 37.93$ 倍。当维度 $d = 254$ 时，理论倍率 $δ_{r o o t}^{d} = 1.015 254 = 44.2$ ，二者接近。

EXP

很神奇啊， $(\begin{matrix} I_{N} & H \\ 0_{N} & q I_{N} \end{matrix})$ 跑不出来，换成 $(\begin{matrix} q I_{N} & 0_{N} \\ H & I_{N} \end{matrix})$ 就能出来，要么就 BKZ，太玄学了

from ntru import *

with open("public_key.txt") as f:
    exec(f.read())
with open("output.txt") as f:
    exec(f.read())
params = NTRUParams(N=N, p=p, q=q)

# 构建循环矩阵 H
H = [h[-i:] + h[:-i] if i else h for i in range(N)]
L = block_matrix(
    ZZ, [[identity_matrix(N), matrix(H)], [zero_matrix(N), q * identity_matrix(N)]]
)
L = L.BKZ(block_size=20)

privK = None
for row in L.rows():
    # 取目标向量 (f, g) 中的 f
    v = list(row[:N])
    # f 的长度平方最大值为 64
    if 0 < sum(x * x for x in v) <= 64:
        # 处理反转
        for sign in [-1, 1]:
            cur = [sign * x for x in v]
            # 循环移位 x^s * f(x) 得到的向量长度可能相同，需要全部遍历
            for s in range(N):
                cand = cur[-s:] + cur[:-s] if s else cur
                # 校验是否满足 f = 3F + 1 的特征，即常数项为 1
                if [x % 3 for x in cand] == [1] + [0] * (N - 1):
                    privK = PrivateKey(f=cand, g=[])
                    break

blocks = [decrypt(c, privK, params) for c in ciphertexts]
print(poly_blocks_to_bytes(blocks, params.chunk_bytes).decode())
'''
flag{27dec48f-f9c7-4bad-9a1b-f7aa77badc5f}
[Done] exited with code=0 in 72.721 seconds
'''

cold_forge

源码

frost_telemetry.json

{
  "format": "cold-forge/frost-telemetry-v1",
  "curve": "secp256k1",
  "group_order": "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141",
  "threshold": 2,
  "participants": [
    1,
    2
  ],
  "lagrange_coefficients": {
    "1": "0000000000000000000000000000000000000000000000000000000000000002",
    "2": "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364140"
  },
  "group_public": {
    "x": "9c667444f507046070c61bc438f793bdd8e4696b6545a1896fc7a6abb3fac7a1",
    "y": "840c5e20b263d46baecd45feaddb5b872e8c722f343eb504de5bf4da4987bc7a"
  },
  "message_hex": "436f6c6420466f7267652072656c65617365206d616e69666573742076313a20617070726f7665207468726573686f6c64207265636f76657279",
  "leak_model": {
    "kind": "msb_quantisation_with_bucket_jitter",
    "discarded_low_bits": 104,
    "maximum_bucket_drift": 1
  },
  "transcripts": [
    {
      "signer": 1,
      "session": "e24f7b73194268b9",
      "D": {
        "x": "779a97e86ba89abafbb3bfa6be7733144d883bfba10605a4e3517f1cf0531f2a",
        "y": "66014d7a31623cfd83fe6a58de85fa10f8138e7728b9820095fc8ddbdaea8bc2"
      },
      "E": {
        "x": "2ca4abfa2e4c26404cc86c1e5fc09fa75e78c728dddae5370dfe1c462a6b7ce3",
        "y": "791f7378d9ee2cc2551649d0c885af6c793c9170d93197af3ddf14dc27bad46f"
      },
      "rho": "26f7ed0417b211bb18343d5d18fb9ab30e873cc90bff926e821acd042e865d0c",
      "challenge": "6e259b807bc64c2020e69e30f3cd598cc63902616f5d459b984f84c9772727e5",
      "z": "c6e6777030750c37b6b275f90af51a10dfcb6a00dd146e5a709f87653cdc7f41",
      "nonce_msb": "fdfc1129b384779fbb5a64bedac6fca84aeeb8"
    },
    // 共 20 条
  ],
  "release_kdf": "SHA256('cold-forge/release/v1' || bip340_signature)",
  "release_aead": "ChaCha20-Poly1305"
}

sealed_release.json

{
  "format": "cold-forge/sealed-release-v1",
  "nonce": "UdfpASn/7RhHRhS4",
  "aad": "Y29sZC1mb3JnZS9yZWxlYXNlL3Yx",
  "ciphertext": "SXEKxWHV+BU0GEDMRCHQV8tmpPkx/22mecX+trCCu4IZcSoIyNfG5zWZViYNKKw1Y9x0TZcX+ODIcA=="
}

分析

只给了两份 JSON，没看出来是什么，问了 AI 知道是 Schnorr 门限签名的多人版，即 FROST 协议。先浅析一下单人版的 Schnorr 签名算法，感觉比 ECDSA 更优雅（

单人版 Schnorr 签名的前身是一个交互式的零知识身份认证协议，后来被 Fiat-Shamir 变换改写为新的非交互式数字签名，因此它的各项变量名和 ECDSA 一样，带有零知识证明的色彩。算法运行在阶为素数的椭圆曲线群上（本题中是 secp256k1），基点为 $G$ 。私钥是 $Z_{n}$ 上随机选取的标量 $x$ ，公钥为 $P = x \cdot G$ 。

签名流程

签名者持有私钥 $x$ 和待签名消息 $m$ ，进行以下步骤：

选取随机数。从 $Z_{n}$ 上随机选取一个标量 $k$ ，绝对保密。
计算承诺。计算 $k$ 对应的椭圆曲线点 $R = k \cdot G$ 。
生成挑战。利用哈希函数绑定承诺，公钥与消息，计算标量 $e = Hash (R | | P | | m) (\mod n)$ 。
计算响应。计算最终的标量响应 $s = k + e \cdot x (\mod n)$ 。
输出签名。签名通常为元组 $(R, s)$ 。

验签流程

验证者持有消息 $m$ ，公钥 $P$ 和签名 $(R, s)$ ，执行验证：

重新计算挑战值 $e = Hash (R | | P | | m)$ 。
验证等式 $s \cdot G = R + e \cdot P$ 是否成立。若成立则验签成功，反之则证明数据被篡改。

为什么叫做承诺-挑战-应答？为什么明明是一个人在签名，却需要所谓的挑战？在交互式系统中：

验签的本质是校验等式 $s \cdot G = R + e \cdot P$ 能否成立。如果没有挑战值，任何没有私钥的攻击者都可以先随便挑一个数字 $s$ ，接着通过简单的移项解方程倒推出 $R$ 。因此，挑战是一个活性化校验规则的因子。注意，虽然挑战在交互式系统中是一个完全随机且公开的数字，但是服务端下发挑战的顺序在客户端提交承诺 $R$ 之后，这意味着预先固定 $s$ ，接着从 $s$ 反推 $R$ 的路线从时序上就天然被否定了。

那如果固定 $R$ 反推 $s$ 呢？原始等式 $s \cdot G = R + e \cdot P$ 的右边此时全部已知，此时求解 $s$ 相当于求解离散对数问题，不可行。攻击者有且仅有这两种伪造的方式，且均被否定了，因此证明只有持有私钥者才能生成签名。

但是在单机签名生成过程中没有网络时序。Fiat-Shamir 变换将服务端换为了哈希函数，并将完全随机的挑战 $e$ 换为了由 $R$ 和 $m$ 经过单向变换得到的值。若攻击者想从 $s$ 反推 $R$ ，它就需要求解 $f (R) = Hash (R)$ ，这是一个求哈希自洽点的问题，不可能实现，同样保证了只有持有私钥者才能够生成签名。Schnorr 门限签名通常也使用 Fiat–Shamir 哈希，但它还需要额外的分布式协议来保证多个签名者之间的 nonce 生成、承诺、部分签名聚合和恶意行为防御。

最终总结一下，承诺用于声明自己已经固定了某个随机数，挑战用于不可预测地激活验证规则，响应用来给知晓私钥者一个快捷的计算途径，同时证明能够计算出它的人持有私钥。

再说一下 FROST 门限签名，它与普通 Schnorr 生成的最终签名完全不可区分，但是私钥被拆成 $n$ 份，需要至少 $t$ 个参与者协作才能进行签名，且在被攻陷的参与者少于 $t$ 时依然被认为安全。

FROST 通过分布式密钥生成技术将一个主私钥拆分后分发给参与者，它的巧妙之处在于使用了多项式插值法。一个 $t - 1$ 次多项式，需要至少 $t$ 个点才能唯一确定。每个参与者的密钥份额就是多项式上的一个点，任意 $t$ 个份额都能通过拉格朗日插值重构出用于签名的秘密，但少于 $t$ 个则无法获得任何信息。完整签名需要一个组织者，组织者可以不可信。流程如下：

分布式密钥生成。每个参与者 $P_{i}$ 得到私钥分片 $s_{i}$ ，全局私钥 $s = \sum λ_{i} s_{i}$ 隐式存在，无任何人知晓。

公开全局聚合公钥 $P = s \cdot G$ ，以及每个参与者各自的公钥 $P_{i} = s_{i} \cdot G$ 。
部分承诺生成。为了抵御并行攻击，FROST 要求每个参与者必须一次性生成两对随机数与承诺。

生成 $d_{i}, e_{i}$ ，计算 $D_{i} = d_{i} \cdot G$ ， $E_{i} = e_{i} \cdot G$ ，将 $(D_{i}, E_{i})$ 发送给组织者。
聚合承诺生成。当有具体消息 $M$ 需要签名时，组织者收集到 $t$ 个节点的承诺，拼装为承诺列表 $L$ ，并为每个参与者计算一个结合系数 $ρ_{i} = H_{1} (i, M, L)$ ，并计算全局聚合承诺 $R = \sum (D_{i} + ρ_{i} \cdot E_{i})$ 。组织者将 $(M, L)$ 下放给参与集合中的所有节点。
全局挑战计算。每个参与者接收到 $(M, L)$ 后在本地计算并验证 $ρ_{i}, R$ ，接着利用 Fiat-Shamir 变换计算全局挑战值 $c = H_{2} (R | | P | | M)$ 。
插值系数计算。参与者计算插值系数 $λ_{i} = \prod_{j \in S, j \neq i} \frac{j}{j - i}$ ，其中 $S$ 为参与者集合。
部分应答生成。参与者计算部分应答 $z_{i} = (d_{i} + ρ_{i} \cdot e_{i}) + λ_{i} \cdot s_{i} \cdot c (\mod q)$ （其中 $d_{i} + ρ_{i} \cdot e_{i}$ 也被记为复合随机数 $k_{i}$ ），将 $z_{i}$ 返回给组织者。
个体验证。协调者利用每个人的公钥验证谁提交了错误数据（ $z_{i} \cdot G = D_{i} + ρ_{i} \cdot E_{i} + c \cdot λ_{i} \cdot P_{i}$ ），以剔除恶意节点。
签名聚合。产出 $z = \sum z_{i} (\mod q)$ ，以 $(R, z)$ 为签名。

验签逻辑和普通 Schnorr 完全等同，且外部验证者完全无法知道签名的参与者组成。

回到题目。参照前面的 FROST 签名协议，本题公开了 2-of-2 门限下对应参与者的插值系数 $λ_{1} = 2, λ_{2} = - 1 (\mod n)$ 。在 transcripts 中，每一笔都有承诺点 $(D, E)$ 、结合系数 $ρ$ 、挑战值 $c$ 和部分响应 $z$ ，另外注意到 nonce_msb 字段给出了复合随机数 $k_{i}$ 的高位泄露。根据部分响应公式 $z_{i} = k_{i} + λ_{i} s_{i} c (\mod q)$ （其中 $k_{i}$ 已知高位），目标是恢复部分私钥 $s_{i}$ 。这是一个 HNP 问题，使用格约简求解即可。

FROST 的第 $i$ 次响应等式为：

z_{i} \equiv k_{i} + λ \cdot c_{i} \cdot x (\mod q)

随机数低 104 位丢失。记高位为 $M_{i}$ ，低位为 $δ_{i}$ ：

k_{i} = M_{i} \cdot 2^{104} + δ_{i}

将 $k_{i}$ 代入原始等式后整理，未知小量 $δ_{i}$ 固定在右侧：

- λ \cdot c_{i} \cdot x + (z_{i} - M_{i} \cdot 2^{104}) \equiv δ_{i} (\mod q)

记 $A_{i} = - λ \cdot c_{i} (\mod q)$ ， $B_{i} = z_{i} - M_{i} \cdot 2^{104} (\mod q)$ 。转化模方程为整数域方程，模数系数记为 $u_{i}$ ：

u_{i} \cdot q + x \cdot A_{i} + B_{i} = δ_{i}

直接就是标准格基（平衡系数为 $C = 2^{104}$ ）：

M = (\begin{matrix} q & 0 & \dots & 0 & 0 \\ 0 & q & \dots & 0 & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ 0 & 0 & \dots & q & 0 \\ A_{0} & A_{1} & \dots & A_{n - 1} & 0 \\ B_{0} & B_{1} & \dots & B_{n - 1} & C \end{matrix})

构建基向量 $w = (u_{0}, u_{1}, \dots, u_{n - 1}, x, 1)$ ，得到目标向量 $v = (δ_{0}, δ_{1}, \dots, δ_{n - 1}, C)$ 。其欧几里得范数为 $\sqrt{n + 1} \cdot 2^{104}$ ，远小于高斯启发式估计的普通向量长度 $2^{238.6}$ ，直接 LLL 约简就能成功。