ECC 等差点列 + 已知 flag 前缀:反推每字节乘数恢复明文
crypto/ecc · verified
一句话结论
当题目给出 a_i = (n_i·P).x · m_i mod p 和点 Q_i = n_i·G,其中 n_i 是等差数列、m_i 是 flag 的每个字节时,利用已知前缀 flag{ 可解出前 5 个 (d·Q_i).x,再按“点列仍为等差数列”恢复 d·Q_0 与步长 d·H,即可对每个 i 计算 m_i = a_i · (d·Q_i).x^{-1} mod p,还原完整 flag。
原理
- 题目结构:
a_i = (n_i · P).x * m_i mod p;同时给出Q_i = n_i · G的坐标;P = d·G是公钥,n_i = start + i·step是等差数列,m_i为 flag 字节。 - 因为
n_i·P = n_i·(d·G) = d·(n_i·G) = d·Q_i,所以(n_i·P).x = (d·Q_i).x。 - 已知 flag 前缀(如
flag{)时,前 5 个m_i已知,可算出T_i = a_i · m_i^{-1} mod p = (d·Q_i).x。 Q_i = Q_0 + i·H(H = step·G)是等差数列;乘以标量 d 后d·Q_i = d·Q_0 + i·(d·H)仍是等差数列。每个 x 坐标对应两个可能的 y(±y),对前 5 个 T_i 枚举2^5种符号组合,找出满足“相邻差相同”的点列,即得X = d·Q_0与K = d·H。- 之后对任意 i,
R_i = X + i·K = d·Q_i,其 x 坐标已知;m_i = a_i · R_i.x^{-1} mod p,若结果在 0–255 即为明文字节;逐字节恢复 flag。
触发条件
- 曲线参数已知(文章为
brainpoolP320r1,p、q、G、a、b 已知)。 - 给出至少 5 组
(a_i, x_i, y_i),且 flag 前缀已知(flag{5 字节)。 n_i为等差数列,m_i为小整数(flag 字节),保证m_i在模 p 下可逆。- p 满足可开平方(文章 p ≡ 3 mod 4,用
(p+1)//4求 y),且a_i非零。
利用步骤
- 解析
output.txt的(a, x, y)列表,构造Q_i = Point(x,y)。 - 用已知前缀
flag{计算T_i = a_i * pow(m_i, -1, p) % p(i=0..4)。 - 对每个
T_i解y^2 = x^3 + a*x + b mod p得到两个候选点(±y)。 - 枚举
2^5种组合,检查相邻点差Q_i - Q_{i-1}是否全部相同;找到X与K。 - 对 i=5..len-1 计算
R_i = X + i*K,m_i = a_i * pow(R_i.x, -1, p) % p,转成字符拼接。 - 验证 flag 格式/可打印性。
PoC
文章 exp 关键代码:
from fastecdsa.curve import brainpoolP320r1
from fastecdsa.point import Point
from itertools import product
import ast
curve = brainpoolP320r1
p, G = curve.p, curve.G
data = ast.literal_eval(open('output.txt').read())
known = [ord(c) for c in "flag{"]
T = []
for i in range(5):
a_val, x, y = data[i]
T.append((a_val * pow(known[i], -1, p)) % p)
def points_with_x(x):
y2 = (x**3 + curve.a * x + curve.b) % p
y = pow(y2, (p + 1) // 4, p)
return [Point(x, y, curve=curve), Point(x, (-y) % p, curve=curve)]
for combo in product(*[points_with_x(t) for t in T]):
diffs = [combo[i] - combo[i-1] for i in range(1, 5)]
if all(d == diffs[0] for d in diffs):
X, K = combo[0], diffs[0]
break
flag = "flag{"
for i in range(5, len(data)):
a_val, x, y = data[i]
R = X + i * K
m = (a_val * pow(R.x, -1, p)) % p
flag += chr(m) if 0 <= m <= 255 else "?"
print(flag)
变体与关联
- 变体:前缀未知但格式可猜(
flag{、ctf{、DASCTF{);可用前 1–2 字节先试,或枚举常见前缀。 - 变体:
n_i为等比/多项式序列时,d·Q_i也保持同样线性关系,可推广为“点列线性关系 + 已知前缀”。 - 变体:只给 x 坐标时,需处理 ±y 的符号歧义;用多组点的一致性筛选。
- 关联:[[crypto-ecc-unknown-curve-point-halving-recover-flag]]、[[crypto-ecc-unknown-curve-projective-cubic-fit-weierstrass-dlp]](未知曲线参数恢复)。
- 边界:flag 前缀未知、
a_i为 0、m_i不是小整数、点列不满足等差关系时,该攻击不成立。
检测与防御
- 检测:CTF/审计中看到“每字节乘数 + 点坐标 + 等差 n”的 ECC 题,即可尝试已知前缀攻击。
- 防御:不要把明文逐字节乘到点坐标上;使用标准 ECIES/ECDH + KDF + AEAD;对明文做填充/随机化。
- 加固:避免泄露同一私钥下等差数列倍点的坐标;对侧信道/已知明文攻击做盲化。