EC ElGamal 私钥 k 泄露:m=c1−k·c2 解出明文点,再按坐标分量做域除法恢复两段 flag
crypto/ecc · verified
一句话结论
在 EC ElGamal 加密 c1=m+rK、c2=rG、K=kG 中,只要题目泄露了私钥 k(或等价地给出了 k),直接计算 m=c1−k·c2 即得明文点;若明文被拆成 cipher_left=s2n(flag前半)·m[0]、cipher_right=s2n(flag后半)·m[1](在 GF(p) 内取模),再做域除法(乘坐标的模逆元)即可恢复两段字节并拼接出 flag。
原理
- EC ElGamal 加密:私钥
k、公钥K=kG;发送方选随机数r,密文c1=m+rK、c2=rG;接收方计算c1−k·c2 = m+rK−k(rG) = m+r(kG)−k(rG) = m。安全性依赖k保密与 ECDLP 困难。 - 题目直接打印
k(或通过其他漏洞泄露)时,ECDLP 被完全绕过,一次点运算即可恢复明文点m。 - 明文编码方式:把 flag 从中间切两半,分别
s2n(bytes→int)后与明文点m的 x、y 坐标相乘。注意m[0]/m[1]是GF(p)元素,乘积在有限域内取模后才是打印出的cipher_left/cipher_right;因此恢复时要按坐标做域除法(cipher_left * m[0]^{-1} mod p,cipher_right * m[1]^{-1} mod p),结果恰为小于 p 的s2n值,再long_to_bytes拼接。用普通整数 floor 除法会因模约减而不整除(本卡验证时用等价 Python 纯实现复算:域除法还原出hgame{Ecc$is!sO@HaRd},与原文一致)。 - 注意点运算要在 Sage 的
EllipticCurve(GF(p),[a,b])上构造点后做减法与标量乘,不能直接对坐标做整数运算;c1、c2的坐标来自输出,需要E([x,y])还原为曲线点。
触发条件
- 题目给出椭圆曲线参数
p,a,b、密文点c1,c2、cipher_left,cipher_right,并且泄露私钥k(或K与k同时给出)。 - 曲线定义在素域
GF(p)上,点可被 Sage 正常构造。 - 明文按坐标分量乘法编码(
flag两半分别乘m[0]、m[1])。 - 有 SageMath 环境。
利用步骤
- 用
E = EllipticCurve(GF(p),[a,b])建曲线,E([x,y])还原c1、c2为曲线点。 - 计算
m = c1 - k*c2,得到明文点。 - 分别做域除法并转
int:ml = int(cipher_left * m[0]^-1)、mr = int(cipher_right * m[1]^-1)(m[0]^-1为 GF(p) 逆元;若用普通整数//会得到错误结果)。 long_to_bytes(ml) + long_to_bytes(mr)拼接并输出 flag。- 若除法结果不可读,检查是否给出的
k对应K=kG、坐标顺序是否颠倒、或明文切分点是否按字节长度而非字符。
PoC
# SageMath
from Crypto.Util.number import long_to_bytes
p = 74997021559434065975272431626618720725838473091721936616560359000648651891507
a = 61739043730332859978236469007948666997510544212362386629062032094925353519657
b = 87821782818477817609882526316479721490919815013668096771992360002467657827319
k = 93653874272176107584459982058527081604083871182797816204772644509623271061231
cipher_left = 68208062402162616009217039034331142786282678107650228761709584478779998734710
cipher_right = 27453988545002384546706933590432585006240439443312571008791835203660152890619
E = EllipticCurve(GF(p), [a, b])
c1 = E([14455613666211899576018835165132438102011988264607146511938249744871964946084,
25506582570581289714612640493258299813803157561796247330693768146763035791942])
c2 = E([37554871162619456709183509122673929636457622251880199235054734523782483869931,
71392055540616736539267960989304287083629288530398474590782366384873814477806])
m = c1 - k * c2
# cipher_left/right 是 s2n(半段flag)*m[坐标] 在 GF(p) 中取模后的值,须做域除法
ml = int(cipher_left * m[0]^-1)
mr = int(cipher_right * m[1]^-1)
print(long_to_bytes(ml) + long_to_bytes(mr))
本卡验证时已用等价 Python 纯实现(自写仿射点加/倍点)复算:m=c1−k·c2 后经 GF(p) 域除法还原出 hgame{Ecc$is!sO@HaRd},与原文输出一致;上述 Sage 脚本本身未在本机执行。原文 solve 脚本中的 cipher_left//m[0] 在 Sage 里对 GF(p) 元素即域除法(作者也注明结果需 int() 转换),与显式乘逆元等价。
变体与关联
- 变体:若
k未泄露但r复用/可预测,可先恢复k再解密;若只泄露k的高位,见 ECDH/ECDSA 的 HNP 类卡。 - 变体:明文编码可能是
m + s2n(flag)(加法)而非分量乘法,此时直接m - s2n(...)或对坐标做减法恢复。 - 关联:[[crypto-ecc-recover-curve-parameter-a-from-g-and-2g]](同篇第一题的参数反解)、[[crypto-ecc-ecdh-small-nonce-brute-shared-point-key]](小 nonce 恢复共享点)、[[crypto-ecc-ecdsa-nonce-reuse-private-key-recovery]](nonce 复用恢复私钥)。
检测与防御
- 实战侧:绝不能在日志/响应中输出私钥
k;EC ElGamal 需配合安全随机数r与经过验证的曲线参数。 - 出题/测评侧:泄露
k等同于明文直接公开;若需考察解密流程,应让选手通过 ECDLP 或侧信道恢复k,而不是打印。 - 检测:输出字段中出现与
K=kG匹配的标量、或同时给出k与密文点时,先尝试直接解密。