也是爆零了T_T。感触蛮多的,虽然比赛身有点草台班子,但还是蛮有意义的
第一次参观北理这种顶级高校,有一种农村人进城的感觉哈哈
再一个也是第一次参加线下的断网的比赛了,离了开始ai重新审视自己,发现自己其实没有预想的那么菜,说明平时对ai一把梭类题型的额外关照还是有意义的
好好努力吧
题目
import os |
分析
整体思路其实很清晰
要解aes就要找key
而:
进一步去求解randomkey1和randomkey2
randomkey2求解
last_key = key_expansion(random_key2) |
所以要先解aes拿last_key,再逆last_key=key_expansion(randomkey2)
拿回random_key2
rsa处理
p-1光滑攻击,拿板子打就行
from Crypto.Util.number import * |
逆key_expansion
w = [bytes_to_long(key[i:i+4]) for i in range(0, 16, 4)] |
待求而已知
从开始认真看代码:
for i in range(4, 44): |
而在已知w[k]的情况话求解f(w[k])是很简单的
由此便可以从开始解决这个递推问题:
SBOX = [……] |
randomkey1求解
题目定义的曲线是:
E: y^2 = x^3 + 4 over F_p |
其中:
p_ec = 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787 |
先把 o 分解一下:
o = 3 * 11 * 10177 * 859267 * 52437899 * 52435875175126190479447740508185965837690552500527637822603658699938581184513 |
题目给了:
n1 = 859267 |
然后生成 3 个阶都为 o 的点 G1, G2, G3,并定义:
P1 = (o // n1) * G1 |
因此:
ord(P1) = n1ord(P2) = n2ord(P3) = n3
加密的核心逻辑非常简单——每个 bit 用不同的"点组合"来表示:
if bit == '0': |
其中 a, b, c 是每次随机选取的标量(充当"一次性掩码")。
注意两种情况的区别:
- bit=0 时,点落在
⟨P1⟩ × ⟨P2⟩ × ⟨G3⟩张成的空间里 - bit=1 时,点落在
⟨P1⟩ × ⟨G2⟩ × ⟨P3⟩张成的空间里
虽然 a, b, c 每次都不同(看起来像随机掩码),但两种 bit 使用的"基础构件"不同,这就是漏洞的根源。
核心攻击:Torsion 投影
目标:
攻击者的目标是:只看密文点 C,判断它对应 bit 0 还是 bit 1。
==关键:乘以 T = o // n2==
关键操作是——把所有点乘以一个特定的标量 T:
T = o // n2 |
乘完之后会发生什么?我们来逐个分析每个基础构件:
| 点 | 原始阶 | T × 该点 | 结果 |
|---|---|---|---|
| P1 | n1 | T × P1 | O(原点) ✅ 因为 T 包含 n1 的因子 |
| P2 | n2 | T × P2 | 仍是 n2 阶点(T 不含 n2 因子) |
| P3 | n3 | T × P3 | O(原点) ✅ 因为 n3=33×n1,T 包含 n1 |
| G1 | o | T × G1 | n2 阶点 |
| G2 | o | T × G2 | n2 阶点 |
| G3 | o | T × G3 | n2 阶点 |
为什么 P3 也被消掉了?
因为 n3 = 33 × n1,而 T = o // n2 仍然包含 n1 这个因子。所以 T × P3 = (o//n2) × (o//n3) × G3,其中 o//n2 包含 n1,而 o//n3 把阶缩到 n3=33×n1,所以 (o//n2) × P3 的步长是 n1 的倍数,走 n3/n1=33 步就回原点了。
投影后,两种 bit 的密文变成:
bit = 0:
T × C = b × (T × P2) + c × (T × G3) |
bit = 1:
T × C = b × (T × G2) ← P3 被消掉了! |
为什么选 n2 而不是 n1 或 n3?
这是最容易卡住的地方:
- 选 n1? 不行。
n3 = 33 × n1,所以o // n1消不掉 P3(P3 带有 n1 成分),bit=1 会有残留分量。 - 选 n3? 不行。
o // n3不再包含 n1 因子,消不掉 P1,bit=0 会有残留分量。 - 选 n2? ✅ 完美!因为 n2 与 n1、n3 都互素,
o // n2同时包含 n1 和 n3 的因子,能一口气把 P1 和 P3 都消掉。
判定:
投影之后,问题变成了:判断一个点是否属于某个特定的循环子群 ⟨B⟩。
n2 = 52437899,平方根只有约 7242,所以直接用 Baby-step Giant-step (BSGS) 就够了:
- 预处理(Baby steps): 计算
B, 2B, 3B, ..., mB(m ≈ 7242),存入哈希表 - 查询(Giant steps): 对目标点 Q,检查
Q - i·(mB)是否在哈希表里 - 如果找到,说明 Q = k·B,即 Q 在 ⟨B⟩ 上 → bit = 1
- 如果找不到 → bit = 0
exp
randomkey2求解:
import os |
randomkey2求解:
import ast, math |
解aes
from Crypto.Cipher import AES |
写在最后:
出乎自己意料的是自己居然在赛场上完成了和的求解
可惜ecc倒是没怎么学,最终也是倒在了这个 子群投影攻击爆零了,可惜。
再接再励吧。😭😭😭