NewStar CTF 2024 - easy_ecc（W5）#

结论：无法获取完整题目数据/flag —— 附件数据内部不一致（损坏），官方题解对该数据同样失效。

题目内容#

附件 easy_ecc/easy_ecc/task.py（本地与官方 GitHub 归档 attachment-week5/easy_ecc.zip 中的文件 md5 逐字节一致）：

1
from Crypto.Util.number import *
2
from secret import flag
3

4
p = 64408890408990977312449920805352688472706861581336743385477748208693864804529
5
a = 111430905433526442875199303277188510507615671079377406541731212384727808735043
6
b = 89198454229925288228295769729512965517404638795380570071386449796440992672131
7
E = EllipticCurve(GF(p), [a, b])
8
m = E.random_point()
9
G = E.random_point()
10
k = 86388708736702446338970388622357740462258632504448854088010402300997950626097
11
K = k * G
12
r = getPrime(256)
13
c1 = m + r * K
14
c2 = r * G
15
c_left  = bytes_to_long(flag[:len(flag)//2]) * m[0]
16
c_right = bytes_to_long(flag[len(flag)//2:]) * m[1]
17

18
# 输出:
19
# c1 = (10968743933204598092696133780775439201414778610710138014434989682840359444219 : 50103014985350991132553587845849427708725164924911977563743169106436852927878 : 1)
20
# c2 = (16867464324078683910705186791465451317548022113044260821414766837123655851895 : 35017929439600128416871870160299373917483006878637442291141472473285240957511 : 1)
21
# c_left  = 15994601655318787407246474983001154806876869424718464381078733967623659362582
22
# c_right = 3289163848384516328785319206783144958342012136997423465408554351179699716569

预期解法（官方思路）#

ECC ElGamal 式加密，私钥 k 直接写在文件里：

1
m = c1 − r·K = c1 − r·(k·G) = c1 − k·(r·G) = c1 − k·c2
2
c_left = long(flag[:L]) × m[0]  →  flag[:L] = c_left // m[0]
3
c_right = long(flag[L:]) × m[1] →  flag[L:] = c_right // m[1]

验证过程与矛盾#

用三个互相独立的 EC 实现（手写仿射 double-and-add、ecdsa 库、Jacobian 射影坐标）计算 m = c1 − k·c2，结果一致：

1
m = (42473705116462428406202294102847935773542820132768934248776117467532517063207,
2
     28673652398806211089618369285265886256488311031977716002800065471137170688215)

往返校验 m + k·c2 == c1、(2k)·c2 == 2·(k·c2) 全部通过，算术无误。

但 m[0] ≈ 4.24e76 > c_left ≈ 1.60e76，而题目定义 c_left = long(flag[:L]) × m[0] ≥ m[0] —— 数学矛盾：c_left // m[0] = 0，无法得到任何有效的 flag 前半部分。

交叉证据（说明这是数据损坏，而非解法错误）#

官方 WP（newstar.wiki week5 crypto/easy_ecc）使用与本地完全相同的 p,a,b,k,c1,c2,c_left,c_right 数值，其 EXP 中 cipher_left // x 同样得 0 —— 官方题解对该数据本身失效；
官方归档的 easy_ecc.zip 与本地附件 md5 一致 —— 非本地解压损坏，而是题目分发时就携带了不一致的数据（文件内 k 常量 ≠ 生成该组密文时实际使用的私钥，疑似出题人修改 k 后未重新生成输出）；
“小群阶”兜底攻击 m_i = c1 − i·c2 迭代 1.6 亿次无命中（若真实私钥模 c2 的阶很小应能命中）；
G、K 未随附件输出，无法独立做 ECDLP 恢复真实 k。

结论#

在当前分发的附件数据下，无法获取完整题目/flag。要解出需重新获取一份数据一致的原始 task.py（例如从比赛平台原始发布包核对），或由出题人重新生成输出。

（已写 solves/crypto/easy_ecc/solve_easy_ecc.py 实现正确解法流程，数据一致时可直接运行出 flag；solve_iter_fast.py 为小群阶兜底搜索。）