椭圆曲线与格攻击

引言

椭圆曲线与格是 CTF Crypto 方向的两座「进阶关卡」。它们与 RSA 的关系很像：RSA 题考的是数论基本功（分解、模运算、中国剩余定理），而 ECC 与格题考的是代数结构与几何直觉——曲线上的点构成一个群，格则是高维空间里的离散点阵，两者都要求你把「题目的条件」翻译成「某个数学对象上的方程」，再用专门的算法求解。

工程上的难点集中在三处。第一是抽象层级高：格约减（LLL）的原理涉及 Gram-Schmidt 正交化与向量长度界的证明，很多人能背出脚本却说不清「为什么这样构造格就能解出小根」。第二是构造的创造性：格攻击的难点从来不是调 LLL，而是如何把方程变成格的基向量，这一步没有通用公式，全靠对题目的理解与经验积累。第三是ECC 的陷阱分散：无效曲线、小子群、nonce 重用、参数异常，每一类都需要独立判断，而题目往往不会告诉你它在考哪一个。

本文按「ECC 基础 → 曲线参数攻击 → ECDSA 攻击 → 格理论 → 格攻击构造 → Coppersmith → 工具链 → 识别套路」的顺序组织，公式一律用纯文本记号书写，便于直接抄进 SageMath 脚本。RSA 侧的数学建模思路可对照 Crypto 方向 RSA 常见攻击手法 ；密码学基础概念可参考 Crypto 方向古典密码与现代密码 与 密码学基础 ；格在现代密码学中的正面用途可见 零知识证明 。

目录

1. 椭圆曲线基础与 ECDLP
2. 曲线参数、点运算与常见异常
3. 小子群与无效曲线攻击
4. ECDSA 的 nonce 重用与偏置
5. 格理论基础与 LLL 约减
6. 格攻击的构造方法
7. Coppersmith 与已知高位攻击
8. 脚本编写与工具链
9. 题目识别套路与防御启示

1. 椭圆曲线基础与 ECDLP

一条定义在有限域 F_p 上的椭圆曲线通常写成 Weierstrass 形式 y^2 = x^3 + a*x + b (mod p)，其中要求判别式 4*a^3 + 27*b^2 模 p 不为零（否则曲线退化）。曲线上的所有点加上一个「无穷远点」O 构成一个阿贝尔群，群运算定义为「两点连线与曲线的第三个交点关于 x 轴对称」——几何上直观，代数上就是一组有理分式。

标量乘 kP 定义为 P 自加 k 次，用「倍点-加」算法可以在 O(log k) 次群运算内算出。而反问题是：

ECDLP（椭圆曲线离散对数问题）：
  已知 P 与 Q = kP，求 k

ECDLP 之所以难，是因为曲线上没有「指数」这种结构，Pollard 的 rho 算法只能达到约 sqrt(n) 的复杂度（n 是群的阶）。一条 256 位的曲线，sqrt(n) 约等于 2^128，穷举不可行——这就是 ECC 用更短的密钥达到 RSA 同等安全强度的原因。

在 CTF 里，ECDLP 本身几乎不会直接考（因为无解），考的是曲线参数被配错导致 ECDLP 退化。退化的形式有几种，识别它们需要先会算群的基本量：

# 教学片段：曲线基本量与阶的检查
p  = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a, b = -3, 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
E = EllipticCurve(GF(p), [a, b])
print(E.order())               # 群阶 #E(F_p)
print(E.order().factor())      # 分解群阶，看有没有小因子
print(E.abelian_group())       # 群结构，判断是否循环

关键判断点：群阶 n 是否等于 p（称为「异常曲线」，此时 ECDLP 可用 Smart 攻击在多项式时间解决）；n 是否有小因子（可转到小子群上求解）；曲线的判别式是否非零（为 0 说明曲线退化成了别的形状）。这三条覆盖了 CTF 中 80% 的「参数错误型」ECC 题。

2. 曲线参数、点运算与常见异常

标准曲线的参数是固定的，CTF 题目则常常自己造一条曲线。判断「这条曲线有没有问题」有一份固定的检查清单：

奇异曲线是最容易被忽略的一类：若判别式为 0，曲线退化为一条带奇点的曲线，数学上同构于 F_p 的加法群或某个扩域上的乘法群，ECDLP 直接变成普通离散对数或加法方程，瞬间可解。判别式为 0 的典型情形是 b = 0 且 a = 0（尖点）或曲线可写成 (y - m*x - c)^2 = (x - s)^2 * (x - t) 的形状（自交点）。

异常曲线（n == p） 对应 Smart 攻击，它把 ECDLP 提升到 p-adic 域上用形式群对数求解，复杂度是多项式的。识别方式就是 E.order() == p。同类还有「接近异常」的曲线，可用 Smart 攻击的推广版本处理。

Pohlig-Hellman 是「分而治之」：若 n = q_1^e_1 * q_2^e_2 * ...，则可分别在每个 q_i 子群上求解（每个子问题规模是 q_i），再用中国剩余定理合并。因此群阶必须含一个大素数因子才安全——若 n 光滑（全是小因子），ECDLP 立刻可解。

# 教学片段：Pohlig-Hellman 的思路（群阶光滑时直接调用即可）
# SageMath 的 discrete_log 会自动选择最优算法
k = discrete_log(Q, P, operation='+')     # 在曲线群上求 P 的离散对数

MOV 攻击利用双线性配对（Weil 或 Tate pairing）把 F_p 上的 ECDLP 映射到 F_{p^k} 上的离散对数，其中 k 是嵌入度。当 k 很小时（例如 k = 2），扩域的规模不足以抵抗指数演算，ECDLP 就被削弱。安全曲线要求嵌入度接近 n 的量级，这也是为什么超奇异曲线（嵌入度极小）在密码学中一度被回避，后来才被配对密码学重新利用。

点的验证是另一条关键防线：若程序接受用户传入的点而不检查它是否在曲线上，就会引入「无效曲线攻击」。

3. 小子群与无效曲线攻击

无效曲线攻击（Invalid Curve Attack） 的成因是：某些实现计算标量乘时只用到 a（而 b 不参与），因此攻击者可以传入一个「不在原曲线上、但在另一条 y^2 = x^3 + a*x + b' 曲线上」的点。如果这条新曲线的群阶含小因子，攻击者就能通过观察结果把私钥 d 对某个小素数取模的值恢复出来，多次收集后用 CRT 拼出完整的 d。

无效曲线攻击的流程
1. 找一条与原曲线共享 a、但群阶含小素数 q 的曲线 E'
2. 构造 E' 上阶为 q 的点 P'
3. 把 P' 发给服务端（它会用私钥 d 计算 dP'）
4. 从返回结果里推出 d mod q
5. 换不同的 q 重复，最后用 CRT 合并出 d

# 教学片段：寻找共享 a 的小阶曲线与点（本地靶场）
p, a = 0x..., 0x...
while True:
    b2 = randint(1, p - 1)                     # 换一个 b'
    E2 = EllipticCurve(GF(p), [a, b2])
    order = E2.order()
    small = [q for q in small_primes if order % q == 0]
    if small:
        q = small[0]
        cof = order // q
        P2 = cof * E2.random_point()           # 把随机点投影到阶为 q 的子群
        if P2 != E2(0):
            break

防御方式很直接：在接受外部点之前验证它满足曲线方程（y^2 == x^3 + a*x + b mod p），并且验证它不在无穷远点、阶不为 1。现代库（如 OpenSSL 3.x、libsecp256k1）都做了这个检查。

小子群攻击是同族手法，区别在于攻击者不换曲线，而是利用原曲线群阶本身含有的小因子。例如群阶 n = q * h（h 是小的余因子），则存在阶为 q 的点，攻击者提交这样的点即可把私钥暴露 q 位的部分信息。防御方式是检查点是否在正确的大素数阶子群里（n * P == O 且 P != O）。

这两类攻击的共同教训是：ECDH 的实现必须验证输入点。这是密码学实现里「输入验证」重要性的经典案例——数学上正确的协议，实现时漏掉一次检查就全线崩溃。

4. ECDSA 的 nonce 重用与偏置

ECDSA 是 ECC 的签名算法，它的安全性高度依赖签名时使用的随机数 k（nonce）。签名过程：

签名（私钥 d，消息哈希 z，曲线阶 n，基点 G）：
  1. 随机取 k ∈ [1, n-1]
  2. 计算 R = kG，取 r = R.x mod n
  3. 计算 s = k^{-1} * (z + r*d) mod n
  4. 输出签名 (r, s)

验证：检查 ((z/s)G + (r/s)Q).x == r，其中 Q = dG

nonce 重用是最经典的攻击：若两次签名用了同一个 k，则 r 相同，两式相减可直接消去 k：

s1 = k^{-1} * (z1 + r*d)   =>   k*s1 = z1 + r*d
s2 = k^{-1} * (z2 + r*d)   =>   k*s2 = z2 + r*d
相减：k*(s1 - s2) = z1 - z2   =>   k = (z1 - z2) / (s1 - s2) mod n
再回代：d = (k*s1 - z1) / r mod n

# 教学片段：nonce 重用的私钥恢复（本地靶场）
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
k = (z1 - z2) * pow(s1 - s2, -1, n) % n
d = (k * s1 - z1) * pow(r, -1, n) % n
print(hex(d))

nonce 偏置是它的推广：即便 k 每次都不同，但只要 k 的高位可预测（例如实现用「随机数的高 128 位固定为 0」，或者 k 由一个已知的线性同余发生器生成），就能用格攻击恢复私钥。这正是格进入 ECC 题目的入口。

判断题目是否属于 nonce 偏置，看三个信号：签名数量多（通常 ≥ 4 组）；题目声称某个字段「只有部分随机」；或者给出的 k 由可预测的递推生成。收集到足够的签名后，构造一个格，让 LLL 找出那个「短向量」——也就是未知的高位。

HNP（隐藏数问题）的标准形式：
  已知 n 个签名，每个签名给出
      k_i = (z_i + r_i*d) / s_i mod n
  且 k_i = a_i + e_i，其中 a_i 已知（高位）、e_i 很小（未知低位）
  目标：恢复 d

检测与防御：ECDSA 的 nonce 必须是密码学安全的随机数，且绝不可重用。工业界的标准做法是确定性 ECDSA（RFC 6979）：用私钥与消息哈希派生 nonce，既保证唯一性又消除了随机数质量依赖。任何手写的签名实现都应当用成熟库（libsecp256k1、OpenSSL），不要自己实现。

5. 格理论基础与 LLL 约减

格（lattice）是 R^m 中由一组线性无关向量 b_1, ..., b_n 的所有整系数线性组合构成的集合：

L = { a_1*b_1 + a_2*b_2 + ... + a_n*b_n  |  a_i ∈ Z }

这组 b_i 称为格的一组基。同一个格有无穷多组基，其中「向量长度」差异巨大——LLL 算法的目标就是在多项式时间内把一组坏基化简成一组好基（向量更短、更接近正交）。

理解 LLL 的输出有两个关键概念。最短向量问题（SVP） 是求格中最短的非零向量，在一般格上是 NP-hard，但 LLL 能给出一个近似解（保证第一个基向量的长度不超过最短向量的 2^((n-1)/2) 倍）。最近向量问题（CVP） 是给定一个不在格中的目标点，求格中离它最近的点。

LLL 的输入输出：

# 教学片段：LLL 最小示例
from sage.all import Matrix, ZZ
B = Matrix(ZZ, [[1, 0, 0, 123], [0, 1, 0, 456], [0, 0, 1, 789]])
R = B.LLL()          # 约减后的基
print(R.rows())      # 每一行都是格中的向量，且比原来的短得多

CTF 里的格攻击几乎都是这个套路：把「求小未知数」的问题编码成一个格，使得「正确的解」对应格中一个特别短的向量，然后交给 LLL 找出它。所以难点从来不是 LLL 本身，而是如何设计基矩阵让正确解变短。

LLL 的两个参数值得记住：delta（约减强度，Sage 默认 0.99，越接近 1 越慢但结果越好）与维度 n（维度越高 LLL 越慢，复杂度大致是 O(n^4 * log(B)) 量级）。因此构造格时应当用最小可行的维度，把不必要的信息合并掉。

6. 格攻击的构造方法

格构造有一套相对固定的模板。以「已知若干个 a_i 与 t_i，且 a_i * x + y_i = t_i mod p，其中 x 与 y_i 都很小」这类问题为例：

思路是构造一个格，使得「未知量向量」在格中。常用的两种基矩阵：

构造一（模方程消去模数）：把方程写成 a_i*x + y_i - t_i = k_i * p
  基矩阵的行形如 [p,   0, ..., 0]
                [a_1, 1, ..., 0]
                [a_2, 0, ..., 1]
  LLL 后短向量对应 (y_1, y_2, ...) 的线性组合

构造二（含缩放因子）：把大数值与未知量的不同量级用缩放系数平衡
  基矩阵的行形如 [K*p,   0,   ...]
                [K*a_1, 1/K, ...]
  缩放系数 K 的选择决定 LLL 能否找到目标向量

缩放系数的选择是构造的关键技巧。若方程里的未知量与已知量量级差很多（例如 x 是 128 位、p 是 512 位），直接构造出来的格会被大量级的分量主导，LLL 找不到短向量。解决办法是给不同的分量乘上不同的权重（如给「大」的分量乘大系数），让各分量在数值上可比。这个技巧没有公式，靠对题目量级的判断与试验。

# 教学片段：一个可运行的格构造（教学用最小模型）
from sage.all import Matrix, ZZ
p  = 0xdeadbeefcafe...         # 模数
A  = [a1, a2, a3, a4]          # 已知系数
T  = [t1, t2, t3, t4]          # 已知右端
n  = len(A)
K  = 2**64                      # 缩放系数，按未知量量级选择
M  = Matrix(ZZ, n + 1, n + 1)
for i in range(n):
    M[i, i] = p
    M[n, i] = A[i] * K
M[n, n] = K
R = M.LLL()
for row in R.rows():
    if row[-1] == K:            # 找到含目标缩放分量的行
        print([abs(v) // K for v in row[:-1]])

Coppersmith 方法的格构造是另一条主线：它处理「多项式方程的小根」问题——已知 f(x) ≡ 0 (mod p) 且 x < p^(1/d)（d 是多项式次数），可以构造一个格把 f 的幂次与 x 的幂次组合起来，让「f(x) = 0」对应一个短向量，从而解出 x。SageMath 内置了 small_roots，多数情况下直接调用即可：

# 教学片段：Coppersmith 求小根
P.<x> = PolynomialRing(Zmod(p))
f = x**3 + a*x + b - c        # 构造出「根是秘密」的多项式
roots = f.small_roots(X=2**128, beta=0.5)
print(roots)

HNP（隐藏数问题） 是 ECDSA nonce 偏置的形式化，也是格攻击在 ECC 上的主要应用：把每个签名写成一个「未知高位 + 已知误差」的方程，构造格恢复高位，进而算出私钥。SageMath 社区有大量现成的 HNP 求解脚本，理解其基矩阵构造是这一节的核心收获。

7. Coppersmith 与已知高位攻击

Coppersmith 的思想可以概括成一句话：把「模 p 下的小根」问题松弛成「整数上的小根」问题，再用格约减求解。它的价值在于 RSA 侧的应用——已知明文高位、已知私钥低位、小指数广播攻击等，全都是 Coppersmith 的实例。

在 ECC 语境里，Coppersmith 常用于两个场景：部分私钥泄露（已知 d 的低若干位，求完整的 d）；部分 nonce 泄露（已知每次签名的 nonce 高位，求私钥）。这两个场景的形式与 HNP 一致。

几个必须记住的界：

# 教学片段：已知 p 的高位时用 Coppersmith 分解 N
N = p_high * 2**512 + 0x...    # 只知道 p 的高位
P.<x> = PolynomialRing(Zmod(N))
f = p_high * 2**512 + x        # p = p_high*2^k + x，x 是未知低位
x0 = f.monic().small_roots(X=2**512, beta=0.4)[0]
p = int(f(x0))
assert N % p == 0

beta 参数表示「因子的大小比例」：当 p 约为 N^0.4 时取 beta=0.4。设错 beta 会导致求不出根——这是 Coppersmith 脚本最常见的失败原因，比格构造错误更常见。X 参数则是未知量的上界，设得过大会让格维度暴增导致超时，设得过小会漏掉真解，正确做法是按题目给出的位数信息反推。

小指数攻击与 Coppersmith 的关系值得澄清：RSA 的「低加密指数 + 小明文」攻击（m^e < N 时直接开整数方）不需要 Coppersmith；只有明文被填充或部分已知时才需要。很多初学者会把两者混淆，导致在不需要格的题目上强行构造格。

部分密钥泄露是另一个高频场景：若已知私钥 d 的低 t 位，可以构造方程 d = d_low + 2^t * x，代入 e*d ≡ 1 (mod phi) 消元后得到一个关于 x 的小根方程，再用 small_roots 求解。识别信号是题目给出的 d 长度明显短于正常值，或者题目明确说「私钥的低 N 位被泄露」。

8. 脚本编写与工具链

CTF Crypto 的标配环境是 SageMath，它内置了椭圆曲线、数论、格约减的全部原语。本地搭建用 Docker 最省事：

# 本地教学：SageMath 环境（Docker 方式）
docker run -it --rm -v "$PWD":/work sagemath/sagemath:latest sage
# 或在容器内运行脚本
docker run --rm -v "$PWD":/work sagemath/sagemath:latest sage /work/solve.sage

核心 API 速查：

# 教学片段：SageMath 中最高频的几组调用
E = EllipticCurve(GF(p), [a, b])
P = E(x, y)
Q = k * P                                  # 标量乘
k = discrete_log(Q, P, operation='+')      # 求离散对数（自动选算法）
R = Matrix(ZZ, B).LLL()                    # 格约减
f.small_roots(X=2**128, beta=0.5)          # Coppersmith

ECC 参数异常的自动检查脚本应当成为做题的第一个动作：

# 教学片段：拿到题目参数后的标准检查
def check_curve(p, a, b, G, n):
    assert (4*a**3 + 27*b**2) % p != 0, "曲线奇异！"
    E = EllipticCurve(GF(p), [a, b])
    print("群阶 =", E.order())
    print("是否异常曲线(n==p) =", E.order() == p)
    print("群阶分解 =", factor(E.order()))
    print("基点是否在曲线上 =", E.is_on_curve(G[0], G[1]))
    print("n*G 是否为无穷远点 =", (n * E(G)) == E(0))

对格攻击而言，fpylll 比 Sage 内置的 LLL 更快，处理高维格（维度 > 50）时差异明显；flatter 与 fplll 也是可选后端。但对于 CTF 题目的维度（通常 < 30），Sage 的 LLL() 完全够用。若遇到 LLL 超时，第一反应应当是降低格维度而不是换更快的后端——多数情况下维度里有冗余。

工具链的取舍：Sage 是「一站式」方案，缺点是安装体积大（约 2 GB）且某些 API 与 Python 生态隔离；pycryptodome 加 sympy 的组合轻量但缺少格与曲线的高级封装；gmpy2 提供快速大整数运算，常与 Sage 配合使用。做题时建议直接用 Sage 的 Docker 镜像，把时间花在数学构造上而不是环境配置上。

9. 题目识别套路与防御启示

把 ECC 与格题目的识别压缩成一张决策表：

三条实战经验：第一，先做量级判断——若题目的未知量比模数小很多（例如 128 位对 512 位），那大概率是格；若未知量与模数同级，多半不是格攻击能解决的。第二，先试现成脚本——SageMath 与社区脚本覆盖了绝大多数标准题型，改动参数比从零构造快得多。第三，LLL 跑完要验证——短向量不一定是解，必须代回原方程验证；很多「求解失败」其实是拿到了错误的行。

从防御视角看，这一篇的每个攻击都对应一条实现要求：

• 曲线参数必须来自标准（P-256、secp256k1、Curve25519），不要自造曲线；自造曲线极易在群阶或嵌入度上留下破绽。
• 必须验证输入点：检查点在曲线上、不在无穷远点、且阶为大素数（n * P == O）。这一条同时挡掉无效曲线与小子群攻击。
• nonce 必须唯一且不可预测：使用 RFC 6979 的确定性 ECDSA，或使用经过审计的 CSPRNG；绝不用时间戳、计数器或低熵源。
• 偏置必然致命：任何「nonce 高位固定」的优化都会把私钥拱手让人，因为 HNP 对偏置的容忍度极低。
• 密钥管理侧：私钥的存储与使用应放在 HSM 或安全元件里，避免侧信道（时序、功耗）泄露额外信息。

关于公钥密码学整体的安全边界与工程实践，可延伸阅读 密码学基础 ；而格攻击在现代密码学中同样是建设性工具——同态加密、格基签名（如 Dilithium）与零知识证明的安全性都建立在格的困难性之上，这也是「攻击与防御共用同一套数学」的最佳例证。

权衡取舍

选择的核心判断是「未知量相对于模数有多小」。小到约模数的 1/d 量级就上 Coppersmith，稍大但有多个线性方程就上 HNP 或一般格攻击，若未知量与模数同级则说明思路错了，应当回去重新理解题目在问什么。

常见坑清单

1. 忘记检查曲线判别式：奇异曲线上的 ECDLP 平凡可解，跳过这一步会在错误的方向上耗时间。
2. 只算群阶不分解：群阶光滑时 Pohlig-Hellman 秒解，factor(E.order()) 是必做动作。
3. 点没验证就参与运算：Sage 会直接抛异常，而真实实现不会——分析协议时要问「实现有没有验证点」。
4. small_roots 的 beta 设错：beta 表示因子占 N 的比例，设大了求不出根、设小了不成立；按题目给的位数反推。
5. LLL 出来的短向量不验证：必须代回原方程确认，否则会把噪声当成解。
6. 缩放系数给错：分量量级差异大时不给权重，LLL 会找到「数值大但结构错」的向量。
7. 格维度堆太高：维度越高 LLL 越慢，超出必要维度会导致超时且未必更准；先用最小可行维度验证。
8. 混淆「低指数开方」与「Coppersmith」：明文小到 m^e < N 时直接开整数方即可，不需要格。
9. nonce 重用题只看到一组签名：需要至少两组 r 相同的签名才能消元，先确认收集够。
10. 用时间戳或计数器当 nonce：这是把私钥直接送人的做法；实现 ECDSA 必须用 RFC 6979 或经审计的随机源。

小结

ECC 与格攻击的知识结构可以概括成「两层检查 + 一条构造线」。两层检查是：拿到曲线参数先查异常（判别式、n 对 p、群阶分解、点验证），拿到 ECDSA 签名先查 nonce（是否重用、是否偏置）。一条构造线是：把所有「求小未知量」的问题翻译成格，用 LLL 找短向量，再用 Coppersmith 或 HNP 的具体形式落地。绝大多数 CTF 题目都落在这两个框架里。

学习路径上，建议先把手写的曲线检查脚本与 nonce 重用求解跑通（这两类不需要格），再进入 Coppersmith 的 small_roots 调用（理解参数含义），最后才手工构造基矩阵（这一步最需要练习）。每道题都应当写出「未知量是什么、模数是什么、量级比是多少」这三句话，写不出来就说明还没理解题目。

最后是视野的拓展：格不是只能用来攻击的数学工具。同态加密、格基签名（Dilithium、Falcon）、以及部分零知识证明系统的安全性都建立在格问题的困难性之上。把攻击手法学透，反过来就能理解这些新方案在设计时为什么要小心翼翼地控制参数——同一个困难性问题，既是防线的根基，也是攻击的入口。