软件安全区域线下赛后记

也是爆零了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 \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)]

$w_0,w_1,w_2,w_3$待求而$w_{43},w_{42},w_{41},w_{40}$已知
从$w_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])是很简单的
由此便可以从$w_{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()}")

写在最后：

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