曲线点当密文的指数加密:用 e 在曲线阶上的模逆乘回 eG 还原明文点,借 Edwards↔Weierstrass 双有理映射取曲线阶
crypto/ecc · verified
一句话结论
当题目把明文编码成曲线点 G、用 eG 当密文公开(e 是公开指数)时,整个问题根本不是 ECDLP:只要 gcd(e, #E) = 1,就可以算出 t = e⁻¹ mod #E,用 t·(eG) = G 直接把明文点乘回来,再取其 x 坐标转字节即得明文。麻烦只在两处——曲线是 twisted Edwards 形式、#E 要在 Weierstrass 模型上算,所以要用一组固定的双有理映射把参数与点在两个模型之间来回搬。
原理
- 为什么不需要解离散对数:加密是标量乘
C = e·G,而曲线点的标量乘构成#E阶循环群(或它的子群)。若e在模#E下可逆,则t·C = t·e·G = (t·e mod #E)·G = G。攻击者不掌握任何私钥,只需要#E——这是公开可算的量(Schoof 等算法),于是"解密"退化为一次模逆加一次标量乘。 - 可逆性的判据:
gcd(e, #E) == 1。CTF 里e常取0x10001这类小素数,而#E是随机大数,冲突概率极低;但必须显式校验——若不互素,只能恢复G所在的子群分量,需要额外处理(见变体)。 - 为什么必须换模型:Sage 的
EllipticCurve只认 Weierstrass 形式,而题目给的是 twisted Edwardsa·x² + y² = 1 + d·x²·y²。群阶只有在 Weierstrass 模型上才能直接E.order()得到;同一个群在不同模型下的阶相同,所以"映射 → 求阶 → 求逆 → 乘 → 映射回去"是合法闭环。 - 映射公式的来源:先做缩放把
c与常数项归一(x1 = x/c、y1 = y/c,曲线化为a·x²+y² = 1+d·x²y²),再用分式线性变换把四次曲线化为三次:x2 = (1+y1)/(1-y1)、y2 = x2/x1,得到B·y² = x³ + A·x² + x,其中A = 2(a+d)/(a-d)、B = 4/(a-d);最后按 Weierstrass 短形式配方x3 = (3x2 + A)/(3B)、y3 = y2/B,系数为a_w = (3-A²)/(3B²)、b_w = (2A³-9A)/(27B³)。反向只需把每一步解出来,公式在卡内 PoC 里给出。 - x 坐标当明文的代价:明文被塞进一个坐标后不再保证是"合法点",因此题目只会取 x;反解时要记得
long_to_bytes(int(G[0])),并注意 Sage 的F(x)元素要先int()再转字节,否则会带进制信息。
触发条件
- 题目给出非 Weierstrass 曲线(twisted Edwards / Hessian / Montgomery)的参数与一个点
eG,并给出整数e。 e是公开的加密指数(不是私钥),且gcd(e, #E) == 1。- 明文就是点(或其某个坐标)本身,而不是"私钥 × 基点"之类需要解 DLP 的形式。
- 能用 Sage 计算
EllipticCurve(...).order();曲线系数变换中出现的分母(a-d、B、c、1-y1、x1)在F_p上非零。
利用步骤
- 识别模型:确认方程是
a·x² + y² = c²(1 + d·x²·y²)(带缩放常数c),记下a、d、c、p与点eG、指数e。 - 归一化:
dd = d·c⁴、A = 2(a+dd)/(a-dd)、B = 4/(a-dd),得到B·y² = x³ + A·x² + x;再算 Weierstrass 系数a_w = (3-A²)/(3B²)、b_w = (2A³-9A)/(27B³)。 - 映射密文点:
x1 = x/c、y1 = y/c→x2 = (1+y1)/(1-y1)、y2 = x2/x1→x3 = (3x2+A)/(3B)、y3 = y2/B;用E(x3, y3)构造点(构造失败说明公式或分母出错)。 E = EllipticCurve(GF(p), [a_w, b_w]);order = E.order();断言gcd(e, order) == 1。t = inverse(e, order);G_w = t * eG_w,再按第 3 步的逆变换映射回 twisted Edwards 模型。- 取
G_edwards[0],long_to_bytes(int(...))得明文;用 flag 格式校验。 - 若第 3 步构造点失败或第 5 步得到无穷远点,优先检查
a-d是否为 0(此时曲线退化,映射不成立)与y1 == 1的例外点。
PoC
from Crypto.Util.number import long_to_bytes
p = ... # 题目给的素模数
a, d, c = ..., ..., 1
e = 0x10001
eG = (...) # 题目给的密文点
F = GF(p)
dd = F(d * c**4)
A = F(2) * F(a + dd) / F(a - dd)
B = F(4) / F(a - dd)
aw = F(3 - A**2) / F(3 * B**2)
bw = F(2 * A**3 - 9 * A) / F(27 * B**3)
def edwards_to_weierstrass(x, y):
x1 = F(x) / F(c); y1 = F(y) / F(c) # a*x^2 + y^2 = 1 + dd*x^2*y^2
x2 = F(1 + y1) / F(1 - y1)
y2 = F(x2) / F(x1) # B*y^2 = x^3 + A*x^2 + x
return ((F(3 * x2) + F(A)) / F(3 * B), F(y2) / F(B))
def weierstrass_to_edwards(x, y):
x2 = (F(x) * F(3 * B) - F(A)) / F(3)
y2 = F(y) * F(B)
x1 = F(x2) / F(y2)
y1 = F(1) - F(2) / F(x2 + 1)
return (F(x1) * F(c), F(y1) * F(c))
E = EllipticCurve(GF(p), [aw, bw])
order = E.order()
assert gcd(e, int(order)) == 1
eG_w = E(edwards_to_weierstrass(eG[0], eG[1]))
G_w = inverse(e, int(order)) * eG_w # t·(eG) = G
G_ed = weierstrass_to_edwards(G_w[0], G_w[1])
print(long_to_bytes(int(G_ed[0])))
判据只有一条:gcd(e, #E) == 1 → 求逆即可,无需 discrete_log。
顺序:换模型 → 求阶 → 模逆 → 标量乘 → 换回 → 取 x。
变体与关联
- 变体一(
e与阶不互素):gcd(e, #E) = g > 1时只能恢复G在g-部分的模糊解,需要枚举g个候选并用 flag 格式/二次校验筛选;实战中先factor(g)看清结构。 - 变体二(阶不光滑但确实需要 DLP):若加密形式是"私钥 × 基点"而
e不可逆或未知,则要回到 DLP:光滑阶用 Pohlig–Hellman,见 [[crypto-ecc-twisted-edwards-small-scalar-pohlig-hellman-aes-cbc]]、[[crypto-ecc-twisted-hessian-curve-weierstrass-pohlig-hellman]]。 - 变体三(映射换成加法群同态):某些题的曲线加法等价于
F_p(√D)的乘法,可直接映射到乘法群做discrete_log,见 [[crypto-ecc-twisted-edwards-map-multiplicative-group-dlp]]。 - 变体四(求解阶的其他来源):
#E也可由题目直接给出,或用E.order()之外的cardinality()/order_from_multiple交叉验证;曲线若退化(判别式为 0)则群结构变成乘法群/加法群,映射失效。 - 关联:[[crypto-ecc-twisted-hessian-curve-weierstrass-pohlig-hellman]](同为"非 Weierstrass 模型 + 双有理映射到 Weierstrass"的骨架,但目标是把 ECDLP 交给 PH 分解;本条完全不解 DLP,只做指数求逆)、[[crypto-ecc-unknown-curve-point-halving-recover-flag]](同样把明文塞进点坐标,但未知参数靠点减半恢复)。
检测与防御
- 对出题/协议设计方:把点当密文且指数公开可逆,等价于不加密——只能当"编码"用。若真要保密,必须用 ECIES 一类带随机数与 KDF 的方案,或至少让指数私密、并把明文先映射到随机化后的点。
- 实现侧:Edwards→Weierstrass 的映射存在例外点(分母为 0),实现要显式拒绝退化输入;曲线参数需校验
a ≠ d、c ≠ 0,并验证已知点在曲线上(a·x²+y² == c²(1+d·x²y²))。 - 检测信号:协议里出现"公开指数 + 点密文 + 无随机数"的组合;
e与#E的 gcd 恒为 1 的固定小指数(如0x10001);同一明文重复加密得到完全相同的点(确定性加密)。 - 修复:改用标准 ECC 加密原语;若只是要"把数据编码到曲线点",明确其安全性来自后续的 KDF 而非曲线运算本身。