软件安全区域线下赛后记

也是爆零了T_T。感触蛮多的,虽然比赛身有点草台班子,但还是蛮有意义的

第一次参观北理这种顶级高校,有一种农村人进城的感觉哈哈

再一个也是第一次参加线下的断网的比赛了,离了开始ai重新审视自己,发现自己其实没有预想的那么菜,说明平时对ai一把梭类题型的额外关照还是有意义的

好好努力吧

题目

import os
import hashlib
from Crypto.Util.number import getPrime, isPrime, bytes_to_long, long_to_bytes, sieve_base
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from sage.all import *
import random
import json
from Secret import flag

p_ec = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
K_field = GF(p_ec)
E = EllipticCurve(K_field, [0, 4])
o = 793479390729215512516507951283169066088130679960393952059283337873017453583023682367384822284289

n1 = 859267
n2 = 52437899
n3 = 28355811

def generate_base_points():
while True:
G1 = E.random_point()
G2 = E.random_point()
G3 = E.random_point()
if G1.order() == o and G2.order() == o and G3.order() == o:
P1 = (o // n1) * G1
P2 = (o // n2) * G2
P3 = (o // n3) * G3
return G1, G2, G3, P1, P2, P3

G1, G2, G3, P1, P2, P3 = generate_base_points()

while True:
a0 = random.randrange(0, o)
b0 = random.randrange(0, o)
c0 = random.randrange(1, o)
K_point = a0 * P1 + b0 * P2 + c0 * G3
if K_point != E(0):
break

def encrypt_bytes_with_weil(data_bytes, K_point, P1, P2, P3, G1, G2, G3, o):
bits = bin(bytes_to_long(data_bytes))[2:].zfill(len(data_bytes) * 8)

cs = [K_point.xy()]
for bit in bits:
a = random.randrange(0, o)
b = random.randrange(0, o)
c = random.randrange(0, o)
if bit == '0':
C = a * P1 + b * P2 + c * G3
else:
C = a * P1 + b * G2 + c * P3
cs.append(C.xy())
return cs

SBOX = [
0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16
]

RCON = [0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36]

def key_expansion(key):
w = [bytes_to_long(key[i:i+4]) for i in range(0, 16, 4)]
for i in range(4, 44):
temp = w[i-1]
if i % 4 == 0:
temp = ((temp << 8) & 0xffffffff) | (temp >> 24)
temp = (SBOX[temp >> 24] << 24) | (SBOX[(temp >> 16) & 0xff] << 16) | \
(SBOX[(temp >> 8) & 0xff] << 8) | SBOX[temp & 0xff]
temp ^= (RCON[i // 4] << 24)
w.append(w[i-4] ^ temp)
return b"".join([long_to_bytes(x, 4) for x in w[40:]])

def generate_prime(bits):
while True:
p_sub = 2
for prime in sieve_base:
p_sub *= prime
if p_sub.bit_length() > bits - 2:
break

for k in range(2, 10000, 2):
p = p_sub * k + 1
if isPrime(p):
return p

p = generate_prime(1024)
q = getPrime(1024)
n = p * q
e = 65537

random_key1 = os.urandom(16)
random_key2 = os.urandom(16)

key = bytes([a ^ b for a, b in zip(random_key1, random_key2)])

cs = encrypt_bytes_with_weil(random_key1, K_point, P1, P2, P3, G1, G2, G3, o)

last_key = key_expansion(random_key2)
c_rsa = pow(bytes_to_long(last_key), e, n)

iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC, iv)
c_aes = cipher.encrypt(pad(flag, 16))

print(f"n = {n}")
print(f"c_rsa = {c_rsa}")
print(f"iv = {iv.hex()}")
print(f"c_aes = {c_aes.hex()}")

print(f"p_ec = {p_ec}")
print(f"o = {o}")
print(f"n1 = {n1}")
print(f"n2 = {n2}")
print(f"n3 = {n3}")
print(f"cs_length = {len(cs)}")

cs_str = str(cs)
with open("cs_data.txt", "w") as f:
f.write(cs_str)

# n = 146850411704422049184055831603438103611273998641574344539157187822470117111192441822840285426092531590494443560512774359361222760041102810475251420012967345253310508075313669874255385146463705376624174846090693327299696444447299357816218235953977513356010849073754388380066627173946423160005852531719468703482395149740126750238839756212987902673933340616278193564739329403982414297244500133278306869727068946995267433133315170300944475227726688168414050083748281907770360887506262390792675100088131056162503296688058603163204412988395608692569420997582022237320094219469054284986095923802700263866210516176584677461256983
# c_rsa = 74231514119138617803996275719518567011575633515104945151215552023045037756701780526260789061976755658325418843994780806559238907177047055473949449639134295693377584046710895240662122821981567353777690859611002522560646785856006740342985854904695610475038620729237499009395199224056982292128775251998161390549676312977578250989501803335573269265794244598105444939510585700441331525728789380327207222547771575094896363209815599271832390676431405381466011192298785646752634683579526124097356770748495318358864466168591744819079230251579490595399596992924889730056630225282899769366237095274859047801524294366610885266499330
# iv = 9ee38737a1bdaaa5f665b4d91988e8d6
# c_aes = 8533aeeb80395a4dc344ca9e4fe036463e6563b3acc3ad85087c166a4e497c516b8cda153dbe3ab2d59999d61195b16e
# p_ec = 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787
# o = 793479390729215512516507951283169066088130679960393952059283337873017453583023682367384822284289
# n1 = 859267
# n2 = 52437899
# n3 = 28355811
# cs_length = 129

分析

整体思路其实很清晰
要解aes就要找key
而:

key=randomkey1⊕randomkey2key = randomkey1 \oplus randomkey2

进一步去求解randomkey1和randomkey2

randomkey2求解

last_key = key_expansion(random_key2) 
c_rsa = pow(bytes_to_long(last_key), e, n)

所以要先解aes拿last_key,再逆last_key=key_expansion(randomkey2)
拿回random_key2

rsa处理

p-1光滑攻击,拿板子打就行

from Crypto.Util.number import *
from gmpy2 import *

n = 146850411704422049184055831603438103611273998641574344539157187822470117111192441822840285426092531590494443560512774359361222760041102810475251420012967345253310508075313669874255385146463705376624174846090693327299696444447299357816218235953977513356010849073754388380066627173946423160005852531719468703482395149740126750238839756212987902673933340616278193564739329403982414297244500133278306869727068946995267433133315170300944475227726688168414050083748281907770360887506262390792675100088131056162503296688058603163204412988395608692569420997582022237320094219469054284986095923802700263866210516176584677461256983
c = 74231514119138617803996275719518567011575633515104945151215552023045037756701780526260789061976755658325418843994780806559238907177047055473949449639134295693377584046710895240662122821981567353777690859611002522560646785856006740342985854904695610475038620729237499009395199224056982292128775251998161390549676312977578250989501803335573269265794244598105444939510585700441331525728789380327207222547771575094896363209815599271832390676431405381466011192298785646752634683579526124097356770748495318358864466168591744819079230251579490595399596992924889730056630225282899769366237095274859047801524294366610885266499330
e = 65537

a = 2
m = 2
while True:
a = powmod(a, m, n)
p = gcd(a-1, n)
if p != 1 and p != n:
break
m += 1

q = n // p
phi = (p-1)*(q-1)
d = invert(e, phi)
m = powmod(c, d, n)
print(m)
逆key_expansion
w = [bytes_to_long(key[i:i+4]) for i in range(0, 16, 4)]

w0,w1,w2,w3w_0,w_1,w_2,w_3待求而w43,w42,w41,w40w_{43},w_{42},w_{41},w_{40}已知
从w4w_4开始认真看代码:

for i in range(4, 44):
if i整除4有:
w[i] = w[i-4] ^ f(w[i-1])
否则:
w[i] = w[i-4] ^ w[i-1]

而在已知w[k]的情况话求解f(w[k])是很简单的
由此便可以从w43,w42,w41,w40w_{43},w_{42},w_{41},w_{40}开始解决这个递推问题:

SBOX = [……]
RCON = [……]
def f(temp,i):
temp = ((temp << 8) & 0xffffffff) | (temp >> 24)
temp = (SBOX[temp >> 24] << 24) | (SBOX[(temp >> 16) & 0xff] << 16) | \
(SBOX[(temp >> 8) & 0xff] << 8) | SBOX[temp & 0xff]
temp ^= (RCON[i // 4] << 24)
return temp
w1 = [
int.from_bytes(m[i*4 : (i+1)*4],byteorder= 'big')
for i in range(4)
]

w = [0]*44

w[43] = w1[3]
w[42] = w1[2]
w[41] = w1[1]
w[40] = w1[0]
w[39] = w[43] ^ w[42]
w[38] = w[42] ^ w[41]
w[37] = w[41] ^ w[40]

for i in range(40,3,-1):
print(i)
if(i % 4 == 0):
w[i-4] = w[i] ^ f(w[i-1],i)
else:
w[i-4] = w[i] ^ w[i-1]

random_key2 = b''.join(x.to_bytes(4, 'big') for x in w[:4])
print(random_key2)

randomkey1求解

题目定义的曲线是:

E: y^2 = x^3 + 4  over F_p

其中:

p_ec = 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787
o = 793479390729215512516507951283169066088130679960393952059283337873017453583023682367384822284289

先把 o 分解一下:

o = 3 * 11 * 10177 * 859267 * 52437899 * 52435875175126190479447740508185965837690552500527637822603658699938581184513

题目给了:

n1 = 859267
n2 = 52437899
n3 = 28355811 = 3 * 11 * 859267 = 33 * n1

然后生成 3 个阶都为 o 的点 G1, G2, G3,并定义:

P1 = (o // n1) * G1
P2 = (o // n2) * G2
P3 = (o // n3) * G3

因此:

  • ord(P1) = n1
  • ord(P2) = n2
  • ord(P3) = n3

加密的核心逻辑非常简单——每个 bit 用不同的"点组合"来表示:

if bit == '0':
C = a*P1 + b*P2 + c*G3 # 用 P2(n2阶)和 G3(满阶)
else:
C = a*P1 + b*G2 + c*P3 # 用 G2(满阶)和 P3(n3阶)

其中 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) 就够了:

  1. 预处理(Baby steps): 计算 B, 2B, 3B, ..., mB(m ≈ 7242),存入哈希表
  2. 查询(Giant steps): 对目标点 Q,检查 Q - i·(mB) 是否在哈希表里
  3. 如果找到,说明 Q = k·B,即 Q 在 ⟨B⟩ 上 → bit = 1
  4. 如果找不到 → bit = 0

exp

randomkey2求解:

import os
import hashlib
from Crypto.Util.number import getPrime, isPrime, bytes_to_long, long_to_bytes, sieve_base
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from sage.all import *
import random

SBOX = [……]
RCON = [……]

def f(temp):
temp = ((temp << 8) & 0xffffffff) | (temp >> 24)
temp = (SBOX[temp >> 24] << 24) | (SBOX[(temp >> 16) & 0xff] << 16) | \
(SBOX[(temp >> 8) & 0xff] << 8) | SBOX[temp & 0xff]
temp ^= (RCON[i // 4] << 24)
return temp

p = 894362857559026179331137858163171244692330458686691817147151686510138149072629249805192610194955887268699493489986644358985787792306571138913751852781817242442738855876105832075630899193066030625707102105504045626592721137734508220949338971288835675616912857960168109434993252017362153522216335262904453411430681
q = 164195561637274513624887610551974984147755026728071046612407624393580153089770421357022468998374000595941309295832877857222182069508330024208472529516349141526061897950124208213207208111413766515578529057421593475166390267575929133248186079526793072302069326041987231069697444034924311986098794311055615181743
n = p*q
e = 65537
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(m)
m = long_to_bytes(m)
print(m)

w1 = [
int.from_bytes(m[i*4 : (i+1)*4],byteorder= 'big')
for i in range(4)
]

w = [0]*44
print(long_to_bytes(w1[3]))
w[43] = w1[3]
w[42] = w1[2]
w[41] = w1[1]
w[40] = w1[0]
w[39] = w[43] ^ w[42]
w[38] = w[42] ^ w[41]
w[37] = w[41] ^ w[40]

for k in range(36,0,-1):
if(k % 4 == 0):
w[k] = w[k+4] ^ f(w[k+3])
w[k] = w[k+4] ^ w[k+3]
print(w)
random_key2 = b''.join(x.to_bytes(4, 'big') for x in w[:4])
print(random_key2)

randomkey2求解:

import ast, math
from pathlib import Path

p_ec = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
o = 793479390729215512516507951283169066088130679960393952059283337873017453583023682367384822284289
n2 = 52437899
T = o // n2 # 投影标量:消掉 P1 和 P3,只保留 n2 阶分量

# ── 椭圆曲线运算
inv = lambda x: pow(x % p_ec, -1, p_ec)

def add(P, Q):
if P is None: return Q
if Q is None: return P
x1, y1 = P; x2, y2 = Q
if x1 == x2:
if (y1 + y2) % p_ec == 0: return None
s = 3 * x1 * x1 * inv(2 * y1) % p_ec
else:
s = (y2 - y1) * inv(x2 - x1) % p_ec
x3 = (s * s - x1 - x2) % p_ec
return x3, (s * (x1 - x3) - y1) % p_ec

def mul(k, P):
R = None
while k:
if k & 1: R = add(R, P)
P = add(P, P); k >>= 1
return R

# ── 读入密文点
cs = ast.literal_eval(Path("cs_data.txt").read_text())
pts = [tuple(p) for p in cs[1:]] # 跳过 cs[0](K_point)

# ── 投影到 n2-torsion
proj = [mul(T, pt) for pt in pts]

# ── BSGS 子群成员判定
m = math.isqrt(n2) + 1
base = proj[0]

# baby steps: {j*base : 0 <= j < m}
baby = {}
cur = None
for j in range(m):
baby[cur] = j
cur = add(cur, base)

# giant step: -m*base
giant_step = (mul(m, base)[0], (-mul(m, base)[1]) % p_ec)

def on_line(Q):
"""判断 Q 是否在 <base> 上"""
cur = Q
for i in range(m + 1):
if cur in baby:
k = i * m + baby[cur]
if k < n2 and mul(k, base) == Q:
return True
cur = add(cur, giant_step)
return False


bits = "".join("1" if on_line(pt) else "0" for pt in proj)
key1 = int(bits, 2).to_bytes(16, "big")

print(f"random_key1 = {key1.hex()}")

解aes

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

random_key1 = bytes.fromhex("8df563a823b3add6e0a4da31f2555ebe")
random_key2 = bytes.fromhex("51ded1088be2bfd82291a04a42f6cd32")

iv = bytes.fromhex("9ee38737a1bdaaa5f665b4d91988e8d6")
c_aes = bytes.fromhex("8533aeeb80395a4dc344ca9e4fe036463e6563b3acc3ad85087c166a4e497c516b8cda153dbe3ab2d59999d61195b16e")

key = bytes(a ^ b for a, b in zip(random_key1, random_key2))
flag = unpad(AES.new(key, AES.MODE_CBC, iv).decrypt(c_aes), 16)

print(f"key = {key.hex()}")
print(f"flag = {flag.decode()}")

写在最后:

出乎自己意料的是自己居然在赛场上完成了rsarsa和randomkey2randomkey2的求解
可惜ecc倒是没怎么学,最终也是倒在了这个ECCECC 子群投影攻击爆零了,可惜。
再接再励吧。😭😭😭