ECDH 小 nonce 暴力:从 R=kG 枚举 k,S=kQ 的 x 坐标 SHA256 派生 XOR 密钥
crypto/ecc · verified
一句话结论
曲线参数 p=2^61-1、a=2、G=(5,1),R=kG 中 k 只有 247439;枚举 k 使 kG==R,再算 S=kQ,取 S.x 的十进制字符串 SHA256 作为 XOR 密钥,即可解出两段密文。
原理
- ECDH 共享点:发送方用私钥 k 计算
R=kG,并用接收方公钥 Q 计算S=kQ;接收方用私钥 d 计算S=dR,双方共享 S。安全性依赖 k 的熵。 - k 空间小:题目中 k 只有 6 位十进制量级,直接线性枚举
G, 2G, 3G, ...与 R 比较即可;EC 点加/倍乘用仿射坐标 + 模逆实现。 - 密钥派生:
key = sha256(str(S[0]).encode()).digest(),即取共享点 x 坐标的十进制字符串(不是字节)做 SHA256;两段密文用同一 keystream 循环 XOR。 - 为什么能解:知道 k 就能算 S;S.x 是双方共享秘密,派生规则已知,XOR 可逆。
触发条件
- 已知曲线参数、G、接收方公钥 Q、发送方
R=kG与密文。 - k 空间可枚举(小 nonce、低熵、部分泄露)。
- 密钥派生规则已知(S.x/S.y、哈希、HKDF)。
- 密文用流密钥/XOR 或可预测 keystream。
利用步骤
- 实现
ec_add、ec_mul(模 p 逆元用pow(x,p-2,p))。 - 从 1 开始累加 G,直到
cur == R,得到 k。 S = ec_mul(k, Q);按题目规则取S[0](x 坐标)。key = sha256(str(S[0]).encode()).digest();对密文逐字节c ^ key[i % len(key)]。- 检查明文是否为可打印文本/flag 格式;若规则用 S.y 或 compressed point,替换即可。
PoC
import hashlib
p, a, G = 2305843009213693951, 2, (5, 1)
Q = (1896662826602979990, 1425560687073180440)
R = (320761691192926716, 300507216662097367)
ct = bytes.fromhex("dcb9e7887358f88e5ba5c366b459f93889ed77a6")
def inv(x): return pow(x, p - 2, p)
def ec_add(P, Q):
if P is None: return Q
if Q is None: return P
x1, y1 = P; x2, y2 = Q
if x1 == x2 and (y1 + y2) % p == 0: return None
lam = ((3*x1*x1 + a) * inv(2*y1 % p)) % p if P == Q else ((y2-y1) * inv((x2-x1) % p)) % p
x3 = (lam*lam - x1 - x2) % p
return (x3, (lam*(x1-x3) - y1) % p)
def ec_mul(n, P):
R0, Q0 = None, P
while n:
if n & 1: R0 = ec_add(R0, Q0)
Q0 = ec_add(Q0, Q0); n >>= 1
return R0
cur, k = None, None
for i in range(1, 1_000_000):
cur = ec_add(cur, G)
if cur == R: k = i; break
S = ec_mul(k, Q)
key = hashlib.sha256(str(S[0]).encode()).digest()
print(bytes(c ^ key[i % len(key)] for i, c in enumerate(ct)))
变体与关联
- nonce 变体:k 由时间戳/计数器派生、k 部分比特泄露、k 重用;可用 HNP/格或直接枚举。
- 曲线变体:Curve25519/Ed25519、NIST P-256、自定义小域曲线;点加公式与压缩格式不同。
- 派生变体:S.x 字节串、S.y、
sha256(str(S))、HKDF、AES-GCM key;密文可能是 AES-CBC/CTR 而非 XOR。 - 关联卡片:[[crypto-ecc-ecdsa-nonce-reuse-private-key-recovery]](ECDSA nonce 复用)、[[crypto-ecc-ecdlp-80bit-prime-order-pollard-rho]](ECDLP)、[[crypto-ecc-ecdsa-partial-nonce-leak-lattice]](部分 nonce 泄露)。
- 边界:若 k 是 128 位以上随机数,枚举不可行;若派生规则未知,需要从上下文推断。
检测与防御
- CTF/验证:先确认
kG==R,再用S=kQ与接收方dR对比应一致;明文应符合 flag/业务格式。 - 防御:使用 CSPRNG 生成 nonce;优先 X25519/Ed25519;密钥派生用 HKDF 并绑定上下文;不要用低熵 k 或时间戳。
- 检测信号:R 点在不同会话重复/可预测;密文长度短且用 XOR;曲线参数异常小(p 约 61 位)。