题目源码

强网杯官方附件 theorezhnp_2ca30345b20024baf4aa65470a9279ed.zip 里的 server.py 如下。

from Crypto.Cipher import AES
from ecdsa import NIST521p
from ecdsa.ecdsa import Public_key
from ecdsa.ellipticcurve import Point
from random import randrange
from sys import stdin
from hashlib import *
from secret import seed_token, flag
import time, signal

signal.alarm(600)

def read(l):
    return stdin.read(l + 1).strip()

def pr(msg, key=None):
    if not key:
        print(msg)
    else:
        key = sha256(str(key).encode()).digest()
        print(AES.new(key, AES.MODE_ECB).encrypt(msg.encode()).hex())

def inp():
    try:
        return Point(E, int(read(131), 16), int(read(131), 16))
    except:
        pass
    return None

def DH(priv, pub):
    shared = priv * pub
    return shared.x()

token = input("Please input your team token: ")

if not token:
    exit()

def generate_token(seed, token):
    return sha256((seed + '&' + sha1(token[::-1].encode()).hexdigest()[:10]).encode()).hexdigest()

to_encrypted_token = generate_token(seed_token, token)

E = NIST521p.curve
G = NIST521p.generator
m = 235
n = G.order()
Alice_sk = randrange(n)
Alice_pk = Public_key(G, Alice_sk * G).point
pr(f'Hi, Bob! Here is my public key: {Alice_pk.x() :x}')

Bob_sk = randrange(n)
Bob_pk = Public_key(G, Bob_sk * G).point
pr(f'Hi, Alice! Here is my public key: {Bob_pk.x() :x}')

shared_AB = DH(Alice_sk, Bob_pk)
shared_BA = DH(Bob_sk, Alice_pk)
assert shared_AB == shared_BA

pr('Now, it is your turn:')
for _ in range(19):
    Mallory_pk = inp()
    if not Mallory_pk:
        pr('Invalid pk!')
        exit()
    shared_AC = DH(Alice_sk, Mallory_pk)
    pr(f'Leak: {shared_AC >> m :x}')

pr(to_encrypted_token, shared_AB)

pr("Give me your token:")
Guess_Token = input()
if Guess_Token == to_encrypted_token:
    pr("Win for flag: " + flag)
else:
    pr("You Lose")

0x01

先固定 ECDH 的记号。设椭圆曲线 $E$ 定义在 $\mathbb{F}_p$ 上，并满足

$$y^2 = x^3 + a_E x + b_E$$

基点为 $G$，其阶为 $n$。Alice 的私钥记为 $\alpha$，Bob 的私钥记为 $\beta$，对应公钥为

$$A = [\alpha]G,\qquad B = [\beta]G$$

共享点为

$$S = [\alpha]B = [\beta]A = [\alpha\beta]G$$

题目实际使用的是共享点的横坐标

$$x(S)$$

本题中的应用

题目打印了 Alice 和 Bob 公钥的横坐标，也就是 $x(A)$ 和 $x(B)$，目标是恢复

$$x(S) = x([\alpha]B)$$

同时，攻击者可以自己提交点 $Q$，服务端返回

$$\left\lfloor \frac{x([\alpha]Q)}{2^{235}} \right\rfloor$$

这表示对任意提交点 $Q$，已知的是 $x([\alpha]Q)$ 的最高位，未知的是最后的 $235$ 个低位。

这题最关键的取样方式和 BabyDH2 一样。围绕 Bob 公钥 $B$ 做一组对称采样

$$Q_0 = B,\qquad Q_i^+ = B + [i]G,\qquad Q_i^- = B - [i]G,\qquad 1 \le i \le 9$$

因为 Alice 的秘密标量固定为 $\alpha$，所以

$$[\alpha]Q_i^+ = [\alpha]B + [i][\alpha]G = S + [i]A$$ $$[\alpha]Q_i^- = [\alpha]B - [i][\alpha]G = S - [i]A$$

而 $A = [\alpha]G$ 已知，因此本地可以算出

$$P_i = [i]A$$

特别是

$$u_i = x(P_i)$$

也是已知量。这样所有查询都被统一到同一个共享点 $S$ 上，真正被观察的是

$$x(S),\ x(S+P_i),\ x(S-P_i)$$

这一组彼此相关的横坐标。

0x02

Hidden Number Problem 的基本形式是，固定一个隐藏量 $\alpha$，攻击者通过多个样本拿到

$$\alpha t_i \bmod q$$

的部分信息，再利用这些样本恢复 $\alpha$ 或某个目标值。核心点在于所有样本都由同一个隐藏量生成。

到了椭圆曲线环境，这个模型对应为 EC-HNP。样本从模乘法变成

$$x([\alpha]Q_i)$$

攻击者拿到的是这些横坐标的部分信息。这里常用的比赛写法是 ECHNP。

本题中的应用

把本题里的泄露写成适合 EC-HNP 建模的形式。设

$$x_0 = x(S)$$ $$x_i^+ = x(S + P_i),\qquad x_i^- = x(S - P_i)$$

并设服务端返回的高位分别是

$$H_0,\qquad H_i^+,\qquad H_i^-$$

由于泄露的是右移 $235$ 位以后的值，可以把未知部分统一写成低位误差

$$x_0 = 2^{235} H_0 + e_0,\qquad 0 \le e_0 < 2^{235}$$ $$x_i^+ = 2^{235} H_i^+ + e_i^+,\qquad 0 \le e_i^+ < 2^{235}$$ $$x_i^- = 2^{235} H_i^- + e_i^-,\qquad 0 \le e_i^- < 2^{235}$$

这样就把高位泄露改写成了有界低位误差模型。

接下来利用椭圆曲线的 differential-addition 关系。对于短 Weierstrass 曲线

$$y^2 = x^3 + a_E x + b_E$$

设 $u_i = x(P_i)$，则 $x_0, x_i^+, x_i^-$ 满足

$$(x_0-u_i)^2(x_i^+ + x_i^-) = 2(x_0u_i + a_E)(x_0 + u_i) + 4b_E \pmod p$$ $$(x_0-u_i)^2 x_i^+ x_i^- = x_0^2u_i^2 - 2a_E x_0u_i - 4b_E(x_0 + u_i) + a_E^2 \pmod p$$

这里真正未知的只有

$$e_0,\ e_i^+,\ e_i^-$$

因为 $H_0, H_i^\pm, u_i, a_E, b_E, p$ 都是已知量。把

$$x_0 = 2^{235}H_0 + e_0,\qquad x_i^\pm = 2^{235}H_i^\pm + e_i^\pm$$

代入之后，每个 $i$ 都会给出一到两条模 $p$ 的多项式方程，例如

$$f_i(e_0, e_i^+, e_i^-) \equiv 0 \pmod p$$ $$g_i(e_0, e_i^+, e_i^-) \equiv 0 \pmod p$$

并且所有变量满足统一界

$$0 \le e_\star < 2^{235}$$

这样就把本题组织成了标准的 EC-HNP 实例。

0x03

模小根问题的标准形式是已知模数 $N$ 和一个或多个多项式

$$f_j(\mathbf{z}) \equiv 0 \pmod N$$

并且已知根满足界

$$|z_i| < X_i$$

目标是求出这个带界的根。

Coppersmith 方法就是把这种带界模根问题送进格中处理。放到这题里，可以拆成四个步骤：

1. 写出模方程和变量界。
2. 选择 shift polynomials。
3. 按变量界缩放，构格并做格基约化。
4. 从短向量恢复整数方程，再做求根。

关于位泄露界，相关工作一直在放宽每个样本需要泄露的位数。早期严格结果要求已知位数比例接近 $5/6$。DCC 2020 把启发式界推进到大约一半位数。ASIACRYPT 2022 说明，对任意正整数 $d$，启发式地说，已知

$$\left(\frac{1}{d+1} + \varepsilon\right)\log_2 p$$

位就有希望恢复共享秘密。Journal of Cryptology 2026 又进一步放宽了这类要求。

这些结论建立在大参数分析之上，不能直接当作当前参数的成功保证。

第二步得到的方程已经是标准模小根系统：

1. 模数是字段素数 $p$。
2. 多项式来自 differential-addition 关系。
3. 根就是低位误差向量。
4. 每个变量的界都是 $2^{235}$。

因此这题在这一层的任务，就是把 EC-HNP 写成小根问题，再用 Coppersmith。

四个具体步骤在本题里的对应关系如下：

1. 模方程和变量界就是上面的 $f_i(\mathbf{e})$、$g_i(\mathbf{e})$ 以及 $|e_\star| < 2^{235}$。

2. shift polynomials 取形如

   $$\mathbf{z}^{\boldsymbol{\alpha}} f(\mathbf{z})^j p^{t-j}$$

   的移位多项式。

3. 把 monomial 按界 $X_i$ 缩放，把这些多项式的系数向量组织成格基，再用 LLL 或 flatter 规约。

4. 从短向量构造出辅助多项式，在整数环里做求根。

这一题已知的是最高 $286$ 位，未知的是最低 $235$ 位，比例为

$$\frac{286}{521} \approx 0.549$$

从公开文献给出的理论界来看，这个比例已经不低，但实际是否成功还取决于格的维数、shift 选择、dual 优化，以及规约器的输出质量。

0x04

q-ary 格是由模 $q$ 线性约束导出的整数格。Coppersmith 构造出的格，经过合适排布之后，通常会出现模数幂次与单位阵组成的块结构，所以文献里常把这类格叫作 q-ary 格。

对偶格给出的是同一个问题的 dual 视角。它不是一个新问题，而是把 primal lattice 改写成对偶的系数关系格。

在 multivariate Coppersmith 问题里，原始 primal 构造往往会把一些无关方向和 dense sublattice 一起带进去，于是有效维数偏大，规约质量也会受影响。对偶格的优化重点是减少这些无关方向。

本题中的应用

这题里的 primal lattice 来自 shift polynomial 的系数向量。其本质是对若干 shift polynomial 的整数线性组合做搜索。

为什么这里要从原始 q-ary 格切到对偶格，原因有三点：

1. 原始构造常常高于最小必要维度。
2. 无关的 dense sublattice 会干扰真正有用的短向量。
3. 理论估计里的体积信息会被这些无关方向放大。

放到这题里，对偶格的优化主要体现为：

1. 有效维数降低。
2. 对应辅助多项式的短向量更容易区分。
3. 理论估计和实测结果更接近。

这一步对本题很重要，因为本题本来就靠近理论阈值。有限维下多出来的无效维度和近似损失，足以改变最后的成败。

0x05

LLL 的经典保证大致是

$$\|b_1\| \le 2^{(n-1)/4}\det(\Lambda)^{1/n}$$

其中 $n$ 是格维数。随着维数上升，这个近似因子会快速变差。

flatter 在工程上很快，输出通常处在 LLL 这一层级，有时略好一些，但它并不会消除有限维下的近似损失。

因此，大参数下的可行性判断一旦落到有限维、近似规约器和具体 shift 参数上，往往会留下明显的实现损失。

本题中的应用

这题的已知比例虽然已经达到

$$\frac{286}{521} \approx 0.549$$

但实际求解时还存在如下问题：

1. 只有 $19$ 个样本。
2. 多变量、多项式次数和格维数都不小。
3. NIST521p 的系数尺度和变量界不平衡。
4. 实际规约器是 LLL 和 flatter。

因此会出现理论估计看起来接近阈值，但实际规约输出不足以直接恢复整根的情况。

这题真正卡住的位置在最后的 root-finding。标准目标是得到

$$h(\mathbf{e}) = 0$$

但边界参数上更常见的是

$$h(\mathbf{e}) = k p$$

或者

$$h(\mathbf{e}) = k p^t$$

其中 $k$ 很小。

这表示格已经恢复出了正确根附近的信息，只是没有短到满足直接整数为零的阈值。因此更合适的做法是：

1. 只做一次格基约化。
2. 在最后求根时搜索较小的 $k$。
3. 对每个候选根回代全部泄露方程，再做共享秘密和 token 的最终检查。

from pwn import remote
from Crypto.Cipher import AES
from hashlib import sha256
from ecdsa import NIST521p
from sage.all import EllipticCurve, GF, ZZ
from optimized_echnp_solver import echnp_coppersmith_solver_optimized

io = remote("47.105.112.224", 11421)
io.sendlineafter(b"Please input your team token: ", b"test")

def submit_pk(Qx, Qy):
    io.sendline(hex(int(Qx))[2:].zfill(131).encode())
    io.sendline(hex(int(Qy))[2:].zfill(131).encode())
    io.recvuntil(b"Leak: ")
    return ZZ(int(io.recvline().strip().decode(), 16))

def gen_samples(sample_n, A, B, G):
    H0 = submit_pk(B[0], B[1])
    positiveH, negativeH, xQ = [], [], []
    for i in range(1, sample_n + 1):
        Q = i * G + B
        positiveH.append(submit_pk(Q[0], Q[1]))
        Q = -i * G + B
        negativeH.append(submit_pk(Q[0], Q[1]))
        xQ.append(ZZ((i * A)[0]))
    return H0, positiveH, negativeH, xQ

curve = NIST521p.curve
p = curve.p()
a = curve.a()
b = curve.b()
SageCurve = EllipticCurve(GF(p), [a, b])
R = GF(p)

io.recvuntil(b"Hi, Bob! Here is my public key: ")
Ax = R(int(io.recvline().strip().decode(), 16))
io.recvuntil(b"Hi, Alice! Here is my public key: ")
Bx = R(int(io.recvline().strip().decode(), 16))

A = SageCurve.lift_x(Ax)
B = SageCurve.lift_x(Bx)
G = SageCurve.lift_x(R(NIST521p.generator.x()))

io.recvuntil(b"Now, it is your turn:\n")

sample_n = 9
d = 3
t = 2
kbit = 235
H0, positiveH, negativeH, xQ = gen_samples(sample_n, A, B, G)

shared_AB = echnp_coppersmith_solver_optimized(
    SageCurve,
    G,
    A,
    B,
    kbit,
    H0,
    positiveH,
    negativeH,
    xQ,
    d,
    t,
    True,
    "XHS22",
    20,
)

enc_token = bytes.fromhex(io.recvline().strip().decode())
key = sha256(str(shared_AB).encode()).digest()
derived_token = AES.new(key, AES.MODE_ECB).decrypt(enc_token).decode()

io.sendlineafter(b"Give me your token:\n", derived_token.encode())
io.interactive()

参考资料

• 强网杯 2025 官方题目列表
• 强网杯 2025 题面镜像（theorezhnp）
• 强网杯 2025 官方附件汇总
• AliyunCTF 2024 BabyDH2 官方源码与求解器实现
• Boneh, Venkatesan, Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes
• Coppersmith, Finding a Small Root of a Univariate Modular Equation
• Howgrave-Graham, Finding Small Roots of Univariate Modular Equations Revisited
• Xu, Hu, Sarkar, Cryptanalysis of Elliptic Curve Hidden Number Problem from PKC 2017
• Xu, Sarkar, Wang, Hu, Improving Bounds on Elliptic Curve Hidden Number Problem for ECDH Key Exchange
• Xu, Sarkar, Wang, Hu, New Results on Elliptic Curve Hidden Number Problem for ECDH Key Exchange
• Aono, Agrawal, Satoh, Watanabe, On the Optimality of Lattices for the Coppersmith Technique
• Ryan, Heninger, Wustrow, Solving Multivariate Coppersmith Problems with Known Moduli
• Ryan, Heninger, Fast Practical Lattice Reduction Through Iterated Compression