ECC基础

本文适合

CTF 密码学 入门学习者。学完你能：理解 ECC基础 的核心概念和基本用法

一句话判断

ECC 题要先看曲线和点是否“真”，再看阶是否安全；只要出现小阶、无效曲线、异常曲线、nonce 复用或参数泄露，就可能转化为可解问题。

题目中常见信号

给出 p,a,b,G,n,Q

说明：标准 ECC 参数

曲线阶很小或可分解

说明：Pohlig-Hellman 机会

只做点乘、不验证点是否在曲线上

说明：无效曲线/小子群风险

签名字段里 r 重复

说明：ECDSA nonce 复用

参数像异常曲线、超奇异曲线

说明：Smart/特殊攻击方向

核心概念

ECC 的安全性基于椭圆曲线离散对数问题。曲线上的点加法、倍点和标量乘法构成群运算；如果曲线阶不大、可分解，或者输入点没有验证，离散对数就可能被拆成多个小问题。

S 级分析要把曲线、点、阶、基点、私钥、公钥和验签关系分别写清楚，而不是只写“椭圆曲线是个群”。

最小分析流程

1. 记录曲线方程和模数 p，确认是否真的是非奇异曲线。
2. 检查基点 G 是否在曲线上，阶 n 是否足够大。
3. 对公开点 Q 试验标量乘法或离散对数条件。
4. 如果有签名，检查 r、s 是否重复或异常。
5. 如果点不合法或阶过小，转向无效曲线、小子群或 Smart 攻击。

最小验证示例

from sageall import *

p = 9739
E = EllipticCurve(GF(p), [497, 1768])
G = E(1804, 5368)
Q = 1337 * G

print(G in E)
print(G.order())
print(Q)

如果 G 不在曲线上、阶很小或 Q 的关系可通过小范围枚举验证，就要重新判断题型。

常见利用 / 解题路线

路线总览：

• 小子群：阶分解后 CRT 合并离散对数。
• 无效曲线：提交不在原曲线上的点，利用未验证输入。
• 异常曲线/Smart：特定曲线可快速求 DLP。
• ECDSA 复用 nonce：转向 签名算法与nonce复用。
• 部分泄露/偏差 nonce：转向 格密码与LLL入门。

常见失败原因

Sage 报点不在曲线上

排查动作：检查参数抄写、模数和坐标大小端

离散对数无解

排查动作：阶可能太大，先分解阶再试

无效曲线攻击失败

排查动作：服务端可能已经做了 on-curve 检查

签名公式代不进去

排查动作：确认 hash 是否截断到曲线阶长度

迷你案例

题目给了一个 Q = dG 和曲线阶 n = 35 = 5 * 7。先分解阶，在 5 阶和 7 阶子群上分别求离散对数，再用 CRT 合并得到 d。这比直接 brute-force d 快得多，也体现了 ECC 题为什么要先看阶。