25年湾区杯网络安全竞赛--Crypto

今天参加了25年湾区杯，我负责的是Crypto方向的题目，题目有两道，一道RSA加密、另一道结合了三种加密方式。博主只解出来了后者。来总结一下我的WriteUp。

题目内容

题目文件

  • task.py 加密脚本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
from hashlib import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secrets import flag, secret

assert secret < 2 ** 50
p = 115792089237316195423570985008687907853269984665640564039457584007913129639747
Q_components = (123456789, 987654321, 135792468, 864297531)

class Quaternion:
    def __init__(self, a, b, c, d):
        self.p = p
        self.a = a % self.p
        self.b = b % self.p
        self.c = c % self.p
        self.d = d % self.p

    def __repr__(self):
        return f"Q({self.a}, {self.b}, {self.c}, {self.d})"

    def __mul__(self, other):
        a1, b1, c1, d1 = self.a, self.b, self.c, self.d
        a2, b2, c2, d2 = other.a, other.b, other.c, other.d
        a_new = a1 * a2 - b1 * b2 - c1 * c2 - d1 * d2
        b_new = a1 * b2 + b1 * a2 + c1 * d2 - d1 * c2
        c_new = a1 * c2 - b1 * d2 + c1 * a2 + d1 * b2
        d_new = a1 * d2 + b1 * c2 - c1 * b2 + d1 * a2
        return Quaternion(a_new, b_new, c_new, d_new)

def power(base_quat, exp):
    res = Quaternion(1, 0, 0, 0)
    base = base_quat
    while exp > 0:
        if exp % 2 == 1:
            res = res * base
        base = base * base
        exp //= 2
    return res

Q = Quaternion(*Q_components)
R = power(Q,secret)

print("--- Public Parameters ---")
print(f"p = {p}")
print(f"Q = {Q}")
print(f"R = {R}")

'''
--- Public Parameters ---
p = 115792089237316195423570985008687907853269984665640564039457584007913129639747
Q = Q(123456789, 987654321, 135792468, 864297531)
R = Q(53580504271939954579696282638160058429308301927753139543147605882574336327145, 79991318245209837622945719467562796951137605212294979976479199793453962090891, 53126869889181040587037210462276116096032594677560145306269148156034757160128, 97368024230306399859522783292246509699830254294649668434604971213496467857155)
'''

key = md5(str(secret).encode()).hexdigest().encode()
cipher = AES.new(key=key,mode=AES.MODE_ECB)
print(cipher.encrypt(pad(flag,16)))

# b'(\xe4IJ\xfd4%\xcf\xad\xb4\x7fi\xae\xdbZux6-\xf4\xd72\x14BB\x1e\xdc\xb7\xb7\xd1\xad#e@\x17\x1f\x12\xc4\xe5\xa6\x10\x91\x08\xd6\x87\x82H\x9e'

目标
已知四元数 Q、模数 p 和 R = Q^secret，secret < 2⁵⁰，求出 secret 后解密 AES 密文。

题目分析

1. 题目的加密分析

  1. 在有限域 p = 115792089237316195423570985008687907853269984665640564039457584007913129639747 上定义四元数乘法
  2. 计算 R = Q^secret
  3. 取 key = MD5(str(secret)).hexdigest().encode()（32 字节 → 16 字节）
  4. AES-ECB 加密 flag

使用了四元数离散对数加密、MD5密钥派生、AES-ECB加密。

2. 解题思路

把「四元数」当做群元素，问题即 求离散对数 R = Q^secret。
secret 上限 2⁵⁰，可直接用 Baby-Step Giant-Step：

  • 令 m = 2^25 ≈ √2⁵⁰
  • Baby-Step：预先计算并存储 {Q^j : j=0…m-1}
  • Giant-Step：从 R 出发，每次乘 Q^(-m)，看是否命中表中某个 j
    一旦命中 ⇒ secret = i*m + j

由于数值过大，相应的运算时间也会比较长。

3. 解题脚本要点

  • 手写四元数类，乘法全部模 p
  • 用 pow(norm, -1, p) 求逆，避免浮点
  • 字典键用 tuple(int)，速度远快于 str(matrix)
  • 最后按题目格式生成 32-字节 key：
    key = md5(str(secret).encode()).hexdigest().encode()

4. 脚本代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
from hashlib import md5
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import time

p = 115792089237316195423570985008687907853269984665640564039457584007913129639747
Q_c = (123456789, 987654321, 135792468, 864297531)
R_c = (
    53580504271939954579696282638160058429308301927753139543147605882574336327145,
    79991318245209837622945719467562796951137605212294979976479199793453962090891,
    53126869889181040587037210462276116096032594677560145306269148156034757160128,
    97368024230306399859522783292246509699830254294649668434604971213496467857155,
)

class Q:
    __slots__ = ("a", "b", "c", "d")
    def __init__(self, a, b, c, d):
        self.a, self.b, self.c, self.d = a % p, b % p, c % p, d % p
    def __mul__(self, o):
        a1, b1, c1, d1 = self.a, self.b, self.c, self.d
        a2, b2, c2, d2 = o.a, o.b, o.c, o.d
        return Q(
            (a1 * a2 - b1 * b2 - c1 * c2 - d1 * d2) % p,
            (a1 * b2 + b1 * a2 + c1 * d2 - d1 * c2) % p,
            (a1 * c2 - b1 * d2 + c1 * a2 + d1 * b2) % p,
            (a1 * d2 + b1 * c2 - c1 * b2 + d1 * a2) % p,
        )
    def inv(self):
        a, b, c, d = self.a, (-self.b) % p, (-self.c) % p, (-self.d) % p
        n = pow((self.a ** 2 + self.b ** 2 + self.c ** 2 + self.d ** 2) % p, -1, p)
        return Q(a * n % p, b * n % p, c * n % p, d * n % p)
    def tup(self):
        return (self.a, self.b, self.c, self.d)

def qpow(q, e):
    r = Q(1, 0, 0, 0)
    while e:
        if e & 1:
            r = r * q
        q = q * q
        e >>= 1
    return r

def bsgs(Q_base, R_target):
    m = 1 << 25  # sqrt(2^50)
    print("[+] Baby-step …")
    tbl = {}
    baby = Q(1, 0, 0, 0)
    for j in range(m):
        tbl[baby.tup()] = j
        baby = baby * Q_base
    print("[+] Giant-step …")
    Q_inv = Q_base.inv()
    Q_step = qpow(Q_inv, m)
    giant = R_target
    for i in range(m):
        tup = giant.tup()
        if tup in tbl:
            return i * m + tbl[tup]
        giant = giant * Q_step
    return None

if __name__ == "__main__":
    t0 = time.time()
    Q_base, R_target = Q(*Q_c), Q(*R_c)
    secret = bsgs(Q_base, R_target)
    if secret is None:
        print("[-] 未找到 secret")
        exit(1)
    print(f"[+] secret = {secret}  ({time.time()-t0:.1f}s)")
    key = md5(str(secret).encode()).hexdigest().encode()
    ct = bytes.fromhex(
        "28e4494afd3425cfadb47f69aedb5a7578362df4d7321442421edcb7b7d1ad236540171f12c4e5a6109108d68782489e"
    )
    print("[+] Flag:", unpad(AES.new(key, AES.MODE_ECB).decrypt(ct), 16).decode())

5. 运行结果

1
2
3
4
[+] Baby-step …
[+] Giant-step …
[+] secret = 895942422329  (104.6s)
[+] Flag: flag{ef9b2a64b3ead115a48ee0b842dc19ed}

博主的脚本感觉还是差点意思，运行时间有点长，因此相对来说解密的成本就会很高。继续努力！！

附从其他文章看到的解密脚本：2025湾区杯网络安全竞赛WriteUP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
from hashlib import md5
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import math
from collections import defaultdict
import time

# ---------------- Public parameters ----------------
p = 115792089237316195423570985008687907853269984665640564039457584007913129639747
Q_components = (123456789, 987654321, 135792468, 864297531)
R_components = (
    53580504271939954579696282638160058429308301927753139543147605882574336327145,
    79991318245209837622945719467562796951137605212294979976479199793453962090891,
    53126869889181040587037210462276116096032594677560145306269148156034757160128,
    97368024230306399859522783292246509699830254294649668434604971213496467857155
)

ciphertext = b'(\xe4IJ\xfd4%\xcf\xad\xb4\x7fi\xae\xdbZux6-\xf4\xd72\x14BB\x1e\xdc\xb7\xb7\xd1\xad#e@\x17\x1f\x12\xc4\xe5\xa6\x10\x91\x08\xd6\x87\x82H\x9e'

# ---------------- Quaternion arithmetic ----------------
class Quaternion:
    __slots__=("a","b","c","d")
    def __init__(self,a,b,c,d):
        self.a=a%p;self.b=b%p;self.c=c%p;self.d=d%p
    def __mul__(self,other):
        a1,b1,c1,d1 = self.a,self.b,self.c,self.d
        a2,b2,c2,d2 = other.a,other.b,other.c,other.d
        return Quaternion(
            (a1*a2 - b1*b2 - c1*c2 - d1*d2)%p,
            (a1*b2 + b1*a2 + c1*d2 - d1*c2)%p,
            (a1*c2 - b1*d2 + c1*a2 + d1*b2)%p,
            (a1*d2 + b1*c2 - c1*b2 + d1*a2)%p
        )
    def __eq__(self,other): return (self.a,self.b,self.c,self.d)==(other.a,other.b,other.c,other.d)
    def __hash__(self): return hash((self.a,self.b,self.c,self.d))
    def conjugate(self):
        return Quaternion(self.a,-self.b,-self.c,-self.d)
    def norm(self):
        return (self.a*self.a + self.b*self.b + self.c*self.c + self.d*self.d) % p
    def inverse(self):
        n=self.norm()
        n_inv=pow(n,-1,p)
        qc=self.conjugate()
        return Quaternion(qc.a*n_inv, qc.b*n_inv, qc.c*n_inv, qc.d*n_inv)

def power(base,exp):
    res = Quaternion(1,0,0,0)
    while exp>0:
        if exp&1: res=res*base
        base=base*base
        exp//=2
    return res

Q=Quaternion(*Q_components)
R=Quaternion(*R_components)

# ---------------- Optimized BSGS ----------------
def bsgs(base, target, bound):
    m=int(math.isqrt(bound))+1
    baby={}
    cur=Quaternion(1,0,0,0)
    for j in range(m):
        # 存储时只存 tuple，避免 Quaternion 对象占内存
        baby[(cur.a,cur.b,cur.c,cur.d)]=j
        cur=cur*base
        if j%500000==0 and j>0:
            print(f"[*] Baby step {j}/{m}")
    # giant step
    factor = power(base.inverse(), m)
    cur=target
    for i in range(m+1):
        t=(cur.a,cur.b,cur.c,cur.d)
        if t in baby:
            return i*m+baby[t]
        cur=cur*factor
        if i%100000==0 and i>0:
            print(f"[*] Giant step {i}/{m}")
    return None

# ---------------- Run ----------------
t0 = time.time()
N=1<<50
secret=bsgs(Q,R,N)
print(f"[+] secret = {secret}  ({time.time()-t0:.1f}s)")

# ---------------- Decrypt ----------------
key=md5(str(secret).encode()).hexdigest().encode()
cipher=AES.new(key,AES.MODE_ECB)
plaintext=unpad(cipher.decrypt(ciphertext),16)
print("[+] FLAG:",plaintext.decode())