扭曲爱德华曲线 DLP 归约:Add 即 F_p(√D) 乘法,映射到 F_p^* 后用 discrete_log 恢复共享密钥
crypto/ecc · verified
一句话结论
题目给的曲线加法 Add((x1,y1),(x2,y2)) = (x1x2 + D y1y2, x1y2 + y1x2) 实际是 F_p(√D) 中“范数为 1”元素的乘法;把所有点映射到 f(P) = (x + d·y)/(x − d·y)(d² = D)后,曲线上的离散对数变为 F_p^* 中的离散对数,用 Sage discrete_log(Pohlig-Hellman)求出私钥,再标量乘对方公钥得到共享密钥的 x 坐标,sha256 派生 AES-ECB 密钥即可解密 flag。
原理
- 加法公式的代数含义:把点
(x,y)视为x + y√D,则(x1 + y1√D)(x2 + y2√D) = (x1x2 + D y1y2) + (x1y2 + y1x2)√D,正是题目Add的两个坐标。因此“点”就是F_p(√D)中的元素,“加法”就是乘法;单位元(1,0)对应1。 - 曲线方程:这类元素满足范数
N(x + y√D) = x² − D y² = 1。题目给出的 G、A、B 都在该集合上;对每个点都有p | (x² − D y² − 1)。 - 恢复模数 p:取两个点 G、A,计算
gcd(gx² − D·gy² − 1, ax² − D·ay² − 1),得到p的倍数(本题g = 2p),除以 2 并检验素数即可。即使题目没给 p,也能从两个点恢复。 - 映射到乘法群:令
d = √D mod p(本题 D=841,d=29),f(P) = (x + d·y)/(x − d·y)。因为(x + y√D)(x − y√D) = 1,f(P)在F_p^*中;且f(P+Q) = f(P)·f(Q)(同态)。于是A = n_a·G变为f(A) = f(G)^{n_a},曲线 DLP 降为F_p^*的 DLP。 - 求私钥与共享密钥:
n_a = discrete_log(f(A), f(G));共享密钥是n_a·B的 x 坐标(也可用f(B)^{n_a}反查,但题目直接用 x 坐标)。key = sha256(long_to_bytes(shared_secret)),AES-ECB 解密 C 并去 PKCS#7 填充。 - 为什么可解:
F_p^*的阶为p−1,若其光滑或 Sage 的discrete_log能在可接受时间内分解,就能求出私钥;本题 p 的规模与光滑性满足 Sage 求解。 - 成立条件:能恢复 p;
D是模 p 的二次剩余(否则√D不在 F_p,映射需在扩域中理解);曲线点确实满足范数 1;共享密钥取 x 坐标的约定与加密端一致。
触发条件
- 题目给出
D、生成元 G、双方公钥 A/B、AES-ECB 密文;加法公式形如(x1x2 + D y1y2, x1y2 + y1x2)。 - 未直接给出模数 p,但给出至少两个曲线点;或 p 已知但曲线不是标准椭圆曲线。
- 曲线群可同态映射到
F_p^*(存在d² = D),且p−1的离散对数可解。
利用步骤
- 确认加法公式对应
F_p(√D)乘法,点满足x² − D y² = 1。 - 用两个点恢复 p:
g = gcd(gx²−D·gy²−1, ax²−D·ay²−1),取p = g // 2(或按实际倍数调整),验证isPrime(p)。 - 计算
d = sqrt(D) mod p(本题d=29),定义f(P) = (x + d*y)/(x − d*y) mod p。 - 计算
u=f(G)、v=f(A),用 Sagediscrete_log(v, u)求n_a;若阶光滑,也可用 Pohlig-Hellman/BSGS。 - 用题目
Add/标量乘计算S = n_a · B,取S[0]作为共享密钥。 key = sha256(long_to_bytes(shared_secret)).digest(),AES-ECB 解密并 unpad,得到 flag。- 闭环验证:用
f检查f(S) == f(B)^{n_a},或用恢复的 key 重新加密明文确认。
PoC
from hashlib import sha256
from math import gcd
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from Crypto.Util.number import long_to_bytes, isPrime
from sage.all import GF, discrete_log
D = 841
gx, gy = 1100598635269059922265259097431205826869659019985617812588900225256796699368319232, 269583433230904539404618502954816143916504972586573484672290485092817854594102981
ax, ay = 522493413431164541763578890114416187756743905387601370337657937604705331138537817, 1508871699477090073528276437418263853138631109882880455850153282479682759269308568
bx, by = 775700026584506740810283787673112405277484661261929762130750879159326080315752049, 164554371563691962332379023518848094645187895772638009983860665200242350372953279
C = bytes.fromhex("7727ceae1edbfa37f913e09b44c10e6fa846891f4b520c87d829fc55299b1f02621af77a1f1f1107d1159c4088250834")
g = gcd(gx**2 - D*gy**2 - 1, ax**2 - D*ay**2 - 1)
p = g // 2
assert isPrime(p)
F = GF(p)
d = F(29) # 29^2 = D
def f(P):
x, y = F(P[0]), F(P[1])
return (x + d*y) / (x - d*y)
n_a = discrete_log(f((ax, ay)), f((gx, gy)))
def add(P, Q):
return ((P[0]*Q[0] + D*P[1]*Q[1]) % p, (P[0]*Q[1] + P[1]*Q[0]) % p)
def mul(P, n):
Q = (1, 0)
while n:
if n & 1: Q = add(Q, P)
P = add(P, P); n >>= 1
return Q
S = mul((bx, by), n_a)
key = sha256(long_to_bytes(S[0])).digest()
flag = unpad(AES.new(key, AES.MODE_ECB).decrypt(C), 16)
print(flag.decode())
变体与关联
- p 的恢复:若
gcd得到的是k·p,可尝试用两个以上点、或对结果做小因子剥离;若 k 很大,可检查g的因子中哪个使d²=D有解且所有点满足范数 1。 - 不同曲线形式:标准 Twisted Edwards
a x² + y² = 1 + d x² y²的加法有分母;本题的无分母形式对应F_p(√D)乘法,映射公式不同,需先确认群结构。 - DLP 求解:
p−1光滑时用 Pohlig-Hellman;否则用 BSGS/Pollard rho;Sagediscrete_log会自动选择。 - 共享密钥约定:有的题用
f(S)而非S[0]作为共享密钥,需按加密端代码确认;本卡按题目get_shared_secret(P,n)=C_multiplication(P,n)[0]。 - 关联:[[ctf-crypto-quaternion-norm-dlp-bsgs]](范数同态把 DLP 降到素域)、[[crypto-ecc-ecdsa-smooth-order-pohlig-hellman]](光滑阶 DLP)、[[crypto-ecc-unknown-curve-projective-cubic-fit-weierstrass-dlp]](未知曲线恢复)。
- 边界:若
D非二次剩余、或群中存在非范数 1 的点、或 p 的离散对数不可解,该方法不成立;自定义曲线不应作为安全设计。
检测与防御
- 题目/设计侧:自定义 Edwards 曲线的加法若等价于
F_p(√D)乘法,DLP 会退化到乘法群,不能提供预期安全强度;应使用标准曲线(如 Curve25519/Ed25519)与标准 ECDH。 - 分析侧:看到
(x1x2 + D y1y2, x1y2 + y1x2)这种无分母加法,先尝试x² − D y² = 1与f(P)=(x+dy)/(x−dy)同态;优先恢复 p 再用discrete_log。 - 检测思路:自定义曲线参数、
D为平方数、点满足范数 1、共享密钥取 x 坐标、sha256(long_to_bytes(secret))派生 AES 密钥等特征。