VNCTF2026

发表于 更新于 阅读次数： Waline： 本文字数： 7.8k 阅读时长 ≈ 28 分钟

VNCTF2026——Crypto题解

AI发展真迅速啊

math RSA

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
from Crypto.Util.number import *
from secret import flag

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
phi = (p - 1) * (q - 1)

u = getPrime(16)
t = 2 * u 
x = phi - 1
y = t + 1
k = 485723311775451084490131424696603828503121391558424003875128327297219030209620409301965720801386755451211861235029553063690749071961769290228672699730274712790110328643361418488523850331864608239660637323505924467595552293954200495174815985511827027913668477355984099228100469167128884236364008368230807336455721259701674165150959031166621381089213574626382643770012299575625039962530813909883594225301664728207560469046767485067146540498028505317113631970909809355823386324477936590351860786770580377775431764048693195017557432320430650328751116174124989038139756718362090105378540643587230129563930454260456320785629555493541609065309679709263733546183441765688806201058755252368942465271917663774868678682736973621371451440269201543952580232165981094719134791956854961433894740133317928275468758142862373593473875148862015695758191730229010960894713851228770656646728682145295722403096813082295018446712479920173040974429645523244575300611492359684052455691388127306813958610152185716611576776736342210195290674162667807163446158064125000445084485749597675094544031166691527647433823855652513968545236726519051559119550903995500324781631036492013723999955841701455597918532359171203698303815049834141108746893552928431581707889710001424400

assert((x**2 + 1)*(y**2 + 1) - 2*(x - y)*(x*y - 1) == 4*(k + x*y))

m = bytes_to_long(flag)
c = pow(m, e, n)

print("n =", n)
print("e =", e)
print("c =", c)

'''
n = 14070754234209585800232634546325624819982185952673905053702891604674100339022883248944477908133810472748877029408864634701590339742452010000798957135872412483891523031580735317558166390805963001389999673532396972009696089072742463405543527845901369617515343242940788986578427709036923957774197805224415531570285914497828532354144069019482248200179658346673726866641476722431602154777272137461817946690611413973565446874772983684785869431957078489177937408583077761820157276339873500082526060431619271198751378603409721518832711634990892781578484012381667814631979944383411800101335129369193315802989383955827098934489
e = 65537
c = 12312807681090775663449755503116041117407837995529562718510452391461356192258329776159493018768087453289696353524051692157990247921285844615014418841030154700106173452384129940303909074742769886414052488853604191654590458187680183616318236293852380899979151260836670423218871805674446000309373481725774969422672736229527525591328471860345983778028010745586148340546463680818388894336222353977838015397994043740268968888435671821802946193800752173055888706754526261663215087248329005557071106096518012133237897251421810710854712833248875972001538173403966229724632452895508035768462851571544231619079557987628227178358
'''

给出
$$
(x^2 + 1)(y^2 + 1) - 2(x - y)(xy - 1) = 4(k + xy)
$$
其中$x = phi - 1,y = 2u+1$。把等式展开后
$$
x^2y^2 + x^2 + y^2 + 1 - 2x^2y + 2x + 2xy^2 - 2y = 4k + 4xy
$$

$$
x^2(y - 1)^2 + 2x(1 + y^2 - 2y) + (y^2 + 1 - 2y - 4k) = 0
$$

这是一个关于$x$的二次方程$ax^2 + bx + c = 0$

其中 $a = (y-1)^2$，$b = 2(1+y^2 - 2y)$，$c = y^2 + 1 - 2y -4k$

由于$y = 2u + 1$，且$u \in [2^{15},2^{16})$，可以枚举一下$u$，于是就可以用求根公式求出$x$，找到正确的$x$便有了$phi$

exp.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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
from Crypto.Util.number import *
import gmpy2

n = 14070754234209585800232634546325624819982185952673905053702891604674100339022883248944477908133810472748877029408864634701590339742452010000798957135872412483891523031580735317558166390805963001389999673532396972009696089072742463405543527845901369617515343242940788986578427709036923957774197805224415531570285914497828532354144069019482248200179658346673726866641476722431602154777272137461817946690611413973565446874772983684785869431957078489177937408583077761820157276339873500082526060431619271198751378603409721518832711634990892781578484012381667814631979944383411800101335129369193315802989383955827098934489
e = 65537
c = 12312807681090775663449755503116041117407837995529562718510452391461356192258329776159493018768087453289696353524051692157990247921285844615014418841030154700106173452384129940303909074742769886414052488853604191654590458187680183616318236293852380899979151260836670423218871805674446000309373481725774969422672736229527525591328471860345983778028010745586148340546463680818388894336222353977838015397994043740268968888435671821802946193800752173055888706754526261663215087248329005557071106096518012133237897251421810710854712833248875972001538173403966229724632452895508035768462851571544231619079557987628227178358
k = 485723311775451084490131424696603828503121391558424003875128327297219030209620409301965720801386755451211861235029553063690749071961769290228672699730274712790110328643361418488523850331864608239660637323505924467595552293954200495174815985511827027913668477355984099228100469167128884236364008368230807336455721259701674165150959031166621381089213574626382643770012299575625039962530813909883594225301664728207560469046767485067146540498028505317113631970909809355823386324477936590351860786770580377775431764048693195017557432320430650328751116174124989038139756718362090105378540643587230129563930454260456320785629555493541609065309679709263733546183441765688806201058755252368942465271917663774868678682736973621371451440269201543952580232165981094719134791956854961433894740133317928275468758142862373593473875148862015695758191730229010960894713851228770656646728682145295722403096813082295018446712479920173040974429645523244575300611492359684052455691388127306813958610152185716611576776736342210195290674162667807163446158064125000445084485749597675094544031166691527647433823855652513968545236726519051559119550903995500324781631036492013723999955841701455597918532359171203698303815049834141108746893552928431581707889710001424400


for u in range(2**15, 2**16):
    if not isPrime(u):
        continue
    
    y = 2 * u + 1
    
    a = (y - 1) ** 2
    b = 2 * (1 + y**2 - 2*y)
    c_coef = y**2 + 1 - 2*y - 4*k
    
    # 使用求根公式
    discriminant = b**2 - 4*a*c_coef
    
    if discriminant < 0:
        continue
    
    # 使用gmpy2计算大整数平方根
    sqrt_disc = gmpy2.isqrt(discriminant)
    if sqrt_disc * sqrt_disc != discriminant:
        continue
    
    x1 = (-b + sqrt_disc) // (2 * a)
    x2 = (-b - sqrt_disc) // (2 * a)
    
    for x in [x1, x2]:
        if x <= 0:
            continue
        
        lhs = (x**2 + 1)*(y**2 + 1) - 2*(x - y)*(x*y - 1)
        rhs = 4*(k + x*y)
        
        if lhs != rhs:
            continue
        
        phi = x + 1
        
        if abs(n - phi) > n // 1000:  # phi应该略小于n
            continue
        
        print(f"找到可能的解: u = {u}, y = {y}, x = {x}, phi = {phi}")
        
        p_plus_q = n - phi + 1
        
        disc = p_plus_q**2 - 4*n
        
        if disc < 0:
            continue
        
        sqrt_disc_pq = gmpy2.isqrt(disc)
        if sqrt_disc_pq * sqrt_disc_pq != disc:
            continue
        
        p = (p_plus_q + sqrt_disc_pq) // 2
        q = (p_plus_q - sqrt_disc_pq) // 2
        
        if p * q == n:
            print(f"成功分解n!")
            print(f"p = {p}")
            print(f"q = {q}")
            
            # 解密
            d = inverse(e, phi)
            m = pow(c, d, n)
            flag = long_to_bytes(m)
            print(f"Flag: {flag.decode()}")
            exit()

print("未找到解") 
# VNCTF{hell0_rsa_w0rld!}

Schnorr

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
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
from Crypto.Util.number import bytes_to_long, isPrime
from hashlib import sha256
from secret import flag, init_seed

class SecureSchnorrProver:
    def __init__(self, security_bits: int = 512):
        """
        Initialize Schnorr protocol with cryptographically secure randomness
        """
        self._init_deterministic_rng(init_seed)
        
        self.p = self._get_prime(security_bits)
        self.g = self._get_random_element()
        
        # Secret from flag (witness for discrete log problem)
        self.secret_a = bytes_to_long(flag.encode()) % (self.p - 1)
        
        # Public key (statement of the discrete log problem)
        self.A = pow(self.g, self.secret_a, self.p)
    
    def _init_deterministic_rng(self, seed):
        """
        Initialize CSPRNG with deterministic seed 
        """
        self.rng_state = sha256(str(seed).encode()).digest()
        self.counter = 0
    
    def _get_secure_random_bits(self, bits: int) -> int:
        """
        Get cryptographically secure random bits using seeded CSPRNG
        """
        data = self.rng_state + self.counter.to_bytes(8, 'big')
        self.counter += 1
        
        result = 0
        
        while len(bin(result)[2:]) < bits:
            hash_output = sha256(data).digest()
            result = (result << 256) | int.from_bytes(hash_output, 'big')
            data = hash_output + self.counter.to_bytes(8, 'big')
            self.counter += 1
        
        return result % (1 << bits)
    
    def _get_prime(self, bits: int) -> int:
        """
        Generate a random prime of specified bit length
        """
        while True:
            num = self._get_secure_random_bits(bits)
            num |= (1 << (bits - 1)) | 1
            
            if isPrime(num):
                return num
    
    def _get_random_element(self) -> int:
        """
        Get a random element in range [2, p-2]
        """
        return self._get_secure_random_bits(self.p.bit_length() - 1) % (self.p - 2) + 2
    
    def run(self):
        """
        Execute the Schnorr zero-knowledge proof protocol
        """
        # Opening statement
        print("=" * 10)
        print("I know the flag for this challenge!")
        print("But I will ONLY prove that I know it.")
        print("You CANNOT extract ANY information about the flag from my proof!")
        print("=" * 10)
        print()
        
        # Show public parameters
        print("[PUBLIC PARAMETERS]")
        print(f"p = {self.p}")
        print(f"g = {self.g}")
        print(f"A = {self.A}")
        print()
        print("Note: The flag is the witness 'a' such that A = g^a mod p")
        print("      where a = bytes_to_long(flag) mod (p-1)")
        print()
        
        round_num = 0
        
        while True:
            round_num += 1
            print(f"--- Round {round_num} ---")
            print()
            
            # Commitment phase
            print("[COMMITMENT]")
            b = self._get_secure_random_bits(self.p.bit_length() - 1) % (self.p - 2) + 1
            B = pow(self.g, b, self.p)
            print(f"B = {B}")
            print()
            
            # Challenge phase
            print("[CHALLENGE]")
            print("(If you are an HONEST verifier, you should provide a RANDOM challenge!)")
            print(f"Please provide challenge x (integer: 1 ≤ x ≤ {self.p - 2}):")
            
            while True:
                try:
                    x = int(input("x = ").strip())
                    if 1 <= x < self.p - 1:
                        break
                    print(f"Invalid! x must be between 1 and {self.p - 2}")
                except (ValueError, EOFError):
                    print("Invalid input!")
                    exit(0)
            
            print()
            
            # Response phase
            print("[RESPONSE]")
            z = (x * self.secret_a + b) % (self.p - 1)
            print(f"z = {z}")
            print()
            
            # Verification
            print("[VERIFICATION]")
            print("Check if: g^z ≡ A^x · B (mod p)")
            
            left = pow(self.g, z, self.p)
            right = (pow(self.A, x, self.p) * B) % self.p
            
            if left == right:
                print("✓ Equation holds! This round proves I know the secret with high probability!")
            else:
                print("✗ Verification failed!")
            
            print()
            
            # Ask to continue
            print("Continue to next round? (y/n):")
            choice = input().strip().lower()
            if choice != 'y':
                break
            print()
        
        print()
        print("=" * 10)
        print(f"Protocol completed after {round_num} round(s).")
        print("You learned ZERO knowledge about the flag!")
        print("=" * 10)

if __name__ == "__main__":
    prover = SecureSchnorrProver(security_bits=512)
    prover.run()

题目实现了一个 Schnorr 协议的证明者，声称知道 flag，但只提供零知识证明而不泄露 flag 本身。

Schnorr 协议流程如下：

  1. 公开参数：素数 $p$、生成元 $g$、公钥 $A = g^a \mod p$（其中 a 是从 flag 派生的秘密值）

  2. 每轮交互：

    • 承诺阶段：证明者生成随机数 b，计算 B = g^b mod p
    • 挑战阶段：验证者提供挑战 x
    • 响应阶段：证明者计算 $ z = x*a + b \mod (p-1)$
    • 验证阶段：验证 $g^z ≡ A^x · B \mod p$

题目的关键漏洞在于

1
2
3
4
5
6
def _init_deterministic_rng(self, seed):
    """
    Initialize CSPRNG with deterministic seed 
    """
    self.rng_state = sha256(str(seed).encode()).digest()
    self.counter = 0

init_seed是固定的，这导致RNG 状态完全确定，生成的随机数序列是固定，所以每次连接靶机，第1轮使用的随机数 $b$ 都相同

我们可以进行如下操作：

  1. 第一次连接服务器，在第1轮发送挑战$ x_1 = 2$，获得响应 $z_1$

    • $z_1 = x_1 · a + b \mod (p-1)$
    • $z_1 = 2a + b \mod (p-1)$

  2. 第二次连接服务器，在第1轮发送挑战 $x_2 = 3$，获得响应 $z_2$

    • $z_2 = x_2 · a + b \mod (p-1)$
    • $z_2 = 3a + b \mod (p-1)$
    • 由于 RNG 是确定性的，这里的 $b$ 与第一次相同！

  3. 消去 b，求解 a：
    $$
    \begin{align}
    z_1 - z_2 &= (x_1 - x_2)\cdot a \mod (p-1)\\
    &= (2 - 3)\cdot a \mod (p-1)\\
    &= -a \mod (p-1)
    \end{align}
    $$

    $$
    \therefore a = (z_1 - z_2)\cdot (x_1 - x_2)^{-1} \mod (p-1)
    $$

exp.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
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
91
92
93
94
95
96
97
98
99
100
from pwn import *
from Crypto.Util.number import long_to_bytes, inverse

context.log_level = 'info'

def get_response(x_challenge, host, port):
    io = remote(host, port)
    
    io.recvuntil(b'[PUBLIC PARAMETERS]\n')
    io.recvuntil(b'p = ')
    p = int(io.recvline().strip())
    io.recvuntil(b'g = ')
    g = int(io.recvline().strip())
    io.recvuntil(b'A = ')
    A = int(io.recvline().strip())
    
    log.info(f"p = {p}")
    log.info(f"g = {g}")
    log.info(f"A = {A}")
    
    # 接收第1轮的承诺
    io.recvuntil(b'[COMMITMENT]\n')
    io.recvuntil(b'B = ')
    B = int(io.recvline().strip())
    log.info(f"B = {B}")
    
    # 发送挑战
    io.recvuntil(b'x = ')
    io.sendline(str(x_challenge).encode())
    log.info(f"发送挑战: x = {x_challenge}")
    
    # 接收响应
    io.recvuntil(b'[RESPONSE]\n')
    io.recvuntil(b'z = ')
    z = int(io.recvline().strip())
    log.info(f"响应: z = {z}")
    
    # 等待验证完成
    io.recvuntil(b'Continue to next round? (y/n):\n')
    io.sendline(b'n')
    
    io.close()
    
    return p, g, A, B, z

def main():
    HOST = '114.66.24.228'
    PORT = 30397
    
    log.info("[第1次连接] 使用挑战 x1 = 2")
    p, g, A, B1, z1 = get_response(2, HOST, PORT)
    x1 = 2
    
    log.info("[第2次连接] 使用挑战 x2 = 3")
    p2, g2, A2, B2, z2 = get_response(3, HOST, PORT)
    x2 = 3
    
    assert p == p2 and g == g2 and A == A2, "参数不一致！"
    
    log.info("开始计算 secret_a (flag)")

    diff_z = (z1 - z2) % (p - 1)
    diff_x = (x1 - x2) % (p - 1)
    
    log.info(f"z1 - z2 = {diff_z}")
    log.info(f"x1 - x2 = {diff_x}")
    
    try:
        inv_diff_x = inverse(diff_x, p - 1)
        a = (diff_z * inv_diff_x) % (p - 1)
        
        log.success(f"计算得到 a = {a}")
        
        # 验证
        log.info("验证：检查 A = g^a mod p")
        A_calc = pow(g, a, p)
        
        if A_calc == A:
            log.success("✓ 验证成功！")
            
            try:
                flag_bytes = long_to_bytes(a)
                flag = flag_bytes.decode('utf-8', errors='ignore')
                
                log.success(f"FLAG: {flag}")
                
            except Exception as e:
                log.warning(f"解码失败: {e}")
        else:
            log.error("✗ 验证失败！")
            log.error(f"期望 A = {A}")
            log.error(f"计算 A = {A_calc}")
            
    except Exception as e:
        log.error(f"计算失败: {e}")
        log.error("可能 gcd(x1-x2, p-1) != 1，请尝试其他挑战值")

if __name__ == "__main__":
    main()
# VNCTF{TwO_DOckeR5_WITH_5p3CI4I_S0UnDne$5_ex7r4CTS_TH3_WItNeSs}

HD_is_what

task.sage

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
import os
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secret import FLAG

# ==========================================
a,b=82 ,57
p = 2**a * 3**b - 1
Fp2.<i> = GF(p^2, modulus=x^2+1)
R.<x> = PolynomialRing(Fp2)

E_start = EllipticCurve(Fp2, [0,6,0,1,0])
E_start.set_order((p+1)^2) 

def get_basis(E, l):
        n = (p+1) // l
        return (n*G for G in E.gens())

P2, Q2 = get_basis(E_start, 2**a)
P3, Q3 = get_basis(E_start, 3**b)


bobs_key = randint(0,3**b-1)
KB = P3 + bobs_key*Q3
phiB = E_start.isogeny(KB, algorithm="factored")
EB = phiB.codomain()
EB.set_order((p+1)**2, num_checks=0)
PB, QB = phiB(P2), phiB(Q2)


alices_key = randint(0,2**a-1)
KA = P2 + alices_key*Q2
phiA = E_start.isogeny(KA, algorithm="factored")
EA = phiA.codomain()
EA.set_order((p+1)**2, num_checks=0)
PA, QA = phiA(P3), phiA(Q3)


shared_kernel_B = PA + bobs_key * QA
phi_shared_B = EA.isogeny(shared_kernel_B, algorithm="factored")
E_shared_B = phi_shared_B.codomain()
shared_j = E_shared_B.j_invariant()


key = sha256(str(shared_j).encode()).digest()
iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC, iv)
ciphertext = cipher.encrypt(pad(FLAG, 16))

def point_to_list(P):
    return [int(c) for c in P[0].polynomial()] + [int(c) for c in P[1].polynomial()]

def fp2_to_list(x):
    return [int(c) for c in x.polynomial()]


bob_raw = []
bob_raw += fp2_to_list(EB.a4())
bob_raw += fp2_to_list(EB.a6())
bob_raw += point_to_list(PB)
bob_raw += point_to_list(QB)

alice_raw = []
alice_raw += fp2_to_list(EA.a4())
alice_raw += fp2_to_list(EA.a6())
alice_raw += point_to_list(PA)
alice_raw += point_to_list(QA)


state = int(p)
def next_rand():
    global state
    state = (state * 1664525 + 1013904223) % 2**32
    return state


dim = 12
M_bob = matrix(ZZ, dim, dim)
for r in range(dim):
    for c in range(dim):
        M_bob[r,c] = (next_rand() % 10 + 10) if r == c else (next_rand() % 5)
Y_bob = vector(ZZ, bob_raw) * M_bob 


M_alice = matrix(ZZ, dim, dim)
for r in range(dim):
    for c in range(dim):
        M_alice[r,c] = (next_rand() % 10 + 10) if r == c else (next_rand() % 5)
Y_alice = vector(ZZ, alice_raw) * M_alice 


output = {
    "params": {"a": a, "b": b},
    "points": { 
        "Pa": point_to_list(P2),
        "Qa": point_to_list(Q2),
        "Pb": point_to_list(P3),
        "Qb": point_to_list(Q3)
    },
    "bob_obfuscated": [int(x) for x in Y_bob],
    "alice_obfuscated": [int(x) for x in Y_alice],
    "iv": iv.hex(),
    "ciphertext": ciphertext.hex()
}

with open("output.txt", "w") as f:
    f.write(str(output))

题目实现了标准的SIDH协议，但对公钥信息进行了线性混淆。

Bob和Alice的公钥被线性变换混淆：

1
2
Y_bob = vector(ZZ, bob_raw) * M_bob
Y_alice = vector(ZZ, alice_raw) * M_alice

其中：

  • bob_raw 包含Bob的公钥信息（曲线参数和点坐标）
  • M_bob 是一个$12\times 12$的随机矩阵
  • 混淆矩阵由LCG伪随机数生成器生成，种子为 state = int(p)

由于随机数生成器的种子是已知的（p = 2^82 * 3^57 - 1），我们可以重建混淆矩阵：

1
2
3
4
5
6
7
8
9
10
state = int(p)
def next_rand():
    global state
    state = (state * 1664525 + 1013904223) % 2**32
    return state

M_bob = matrix(ZZ, 12, 12)
for r in range(12):
    for c in range(12):
        M_bob[r,c] = (next_rand() % 10 + 10) if r == c else (next_rand() % 5)

通过矩阵求逆恢复原始数据：

1
bob_raw = Y_bob * M_bob^(-1)

恢复的数据格式为 [a4_0, a4_1, a6_0, a6_1, PB_x0, PB_x1, PB_y0, PB_y1, QB_x0, QB_x1, QB_y0, QB_y1]

其中每个Fp2元素用两个整数表示：Fp2([实部, 虚部])

同源后的曲线保持Montgomery形式，方程为：
$$
y^2 = x^3 + 6x^2 + a_4x + a_6
$$
在SageMath中创建曲线时需要使用完整的Weierstrass参数：

1
EB = EllipticCurve(Fp2, [0, 6, 0, EB_a4, EB_a6])

对应 [a1, a2, a3, a4, a6]，其中 a2 = 6 是Montgomery常数。

用2022年发现的Castryck-Decru攻击来恢复Bob的密钥。这个攻击利用了SIDH协议中传输的辅助点信息（PB, QB）

GitHub上的实现：https://github.com/GiacomoPope/Castryck-Decru-SageMath

攻击步骤：

  1. 生成扭曲映射（distortion map）
  2. 逐位恢复Bob的密钥（三进制表示）
  3. 使用glue-and-split技术加速恢复过程

恢复Bob的密钥后：

  1. 恢复Alice的公钥（同样的混淆恢复过程）
  2. 计算共享密钥：shared_kernel = PA + bob_key * QA
  3. 计算同源得到共享曲线的j-invariant
  4. 使用j-invariant派生AES密钥
  5. 解密flag

exp.sage

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
# Local imports
import public_values_aux
from public_values_aux import *

# Load Sage files
load('castryck_decru_shortcut.sage')

from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import ast

# 读取数据
with open("../output.txt", "r") as f:
    data = ast.literal_eval(f.read())

# 参数
a, b = data["params"]["a"], data["params"]["b"]
p = 2**a * 3**b - 1
public_values_aux.p = p

print(f"Running attack against SIDH with parameters: 2^{a}*3^{b} - 1")

R_temp.<x> = PolynomialRing(GF(p))
Fp2.<i> = GF(p^2, modulus=x^2+1)
R.<x> = PolynomialRing(Fp2)

E_start = EllipticCurve(Fp2, [0,6,0,1,0])
E_start.set_order((p+1)^2)

# 恢复基点
def list_to_point(E, lst):
    x_coord = Fp2([lst[0], lst[1]])
    y_coord = Fp2([lst[2], lst[3]])
    return E(x_coord, y_coord)

P2 = list_to_point(E_start, data["points"]["Pa"])
Q2 = list_to_point(E_start, data["points"]["Qa"])
P3 = list_to_point(E_start, data["points"]["Pb"])
Q3 = list_to_point(E_start, data["points"]["Qb"])

print("基点恢复成功")

# 恢复Bob的公钥
state = int(p)
def next_rand():
    global state
    state = (state * 1664525 + 1013904223) % 2**32
    return state

dim = 12
M_bob = matrix(ZZ, dim, dim)
for r in range(dim):
    for c in range(dim):
        M_bob[r,c] = (next_rand() % 10 + 10) if r == c else (next_rand() % 5)

Y_bob = vector(ZZ, data["bob_obfuscated"])
bob_raw = list(Y_bob * M_bob.change_ring(QQ).inverse())
bob_raw = [Integer(round(x)) for x in bob_raw]

def list_to_fp2(lst, idx):
    return Fp2([lst[idx], lst[idx+1]])

EB_a4 = list_to_fp2(bob_raw, 0)
EB_a6 = list_to_fp2(bob_raw, 2)
EB = EllipticCurve(Fp2, [0, 6, 0, EB_a4, EB_a6])
EB.set_order((p+1)**2, num_checks=0)

PB = EB(list_to_fp2(bob_raw, 4), list_to_fp2(bob_raw, 6))
QB = EB(list_to_fp2(bob_raw, 8), list_to_fp2(bob_raw, 10))

print("Bob的公钥恢复成功")

# 生成扭曲映射
print("生成扭曲映射...")
two_i = generate_distortion_map(E_start)

# 运行攻击
print("\n开始Castryck-Decru攻击...")
print("这可能需要一些时间（对于这个参数大小，可能需要15-30分钟）...")

try:
    recovered_key = CastryckDecruAttack(E_start, P2, Q2, EB, PB, QB, two_i, num_cores=1)

    print(f"\n✓ 攻击成功！")
    print(f"恢复的Bob密钥: {recovered_key}")

    # 验证密钥
    KB_recovered = P3 + recovered_key*Q3
    phi_test = E_start.isogeny(KB_recovered, algorithm="factored")
    EB_test = phi_test.codomain()

    print(f"\n验证: EB == EB_test? {EB.j_invariant() == EB_test.j_invariant()}")

    if EB.j_invariant() == EB_test.j_invariant():
        print("✓ 密钥验证成功！")

        # 现在计算共享密钥
        # 恢复Alice的公钥
        M_alice = matrix(ZZ, dim, dim)
        for r in range(dim):
            for c in range(dim):
                M_alice[r,c] = (next_rand() % 10 + 10) if r == c else (next_rand() % 5)

        Y_alice = vector(ZZ, data["alice_obfuscated"])
        alice_raw = list(Y_alice * M_alice.change_ring(QQ).inverse())
        alice_raw = [Integer(round(x)) for x in alice_raw]

        EA_a4 = list_to_fp2(alice_raw, 0)
        EA_a6 = list_to_fp2(alice_raw, 2)
        EA = EllipticCurve(Fp2, [0, 6, 0, EA_a4, EA_a6])
        EA.set_order((p+1)**2, num_checks=0)

        PA = EA(list_to_fp2(alice_raw, 4), list_to_fp2(alice_raw, 6))
        QA = EA(list_to_fp2(alice_raw, 8), list_to_fp2(alice_raw, 10))

        # 计算共享密钥
        shared_kernel_B = PA + recovered_key * QA
        phi_shared_B = EA.isogeny(shared_kernel_B, algorithm="factored")
        E_shared_B = phi_shared_B.codomain()
        shared_j = E_shared_B.j_invariant()

        print(f"\n共享j-invariant计算完成")

        # 解密flag
        key = sha256(str(shared_j).encode()).digest()
        iv = bytes.fromhex(data["iv"])
        ciphertext = bytes.fromhex(data["ciphertext"])

        cipher = AES.new(key, AES.MODE_CBC, iv)
        plaintext = unpad(cipher.decrypt(ciphertext), 16)

        print(f"\n" + "="*60)
        print(f"FLAG: {plaintext.decode()}")
        print("="*60)

except Exception as e:
    print(f"\n✗ 攻击失败: {e}")
    import traceback
    traceback.print_exc()
    # VNCTF{wo_buzhidao_shuoshenmo_zhejiushiFLAG}

NumberGuesser

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
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secret import flag
import random
import os

class NumberGuesser:
    def __init__(self,MAX_CHANCES: int = 10, n: int = 624):
        self.MAX_CHANCES = MAX_CHANCES
        self.n = n
        self.seed = os.urandom(8)
        random.seed(self.seed)

        self.hints = [random.getrandbits(32) for _ in range(self.n)]
        self.enc = self.encrypt_flag(flag,self.seed)

    def encrypt_flag(self,flag: str, iv:bytes) -> bytes:
        key = random.getrandbits(128).to_bytes(16,'big')
        ct = AES.new(key,AES.MODE_CBC,iv*2).encrypt(pad(flag.encode(), AES.block_size))
        return ct
    
    def banner(self):
        print("=== Number Guess Challenge ===")
        print(f"- Internally generates {self.n} 32-bit random numbers")
        print(f"- You may query at most {self.MAX_CHANCES} indices (0 ~ {self.n - 1})")
        print("- The seed is 8 bytes of true randomness, influencing AES-CBC key generation\n")
        print("Encrypted flag:")
        print(self.enc.hex(), "\n")

    def query_loop(self):
        for CHANCES in range(1, self.MAX_CHANCES + 1):
            print(f"[{CHANCES}/{self.MAX_CHANCES}]")
            try:
                index = int(input(f"Enter index (0~{self.n - 1}): ").strip())
                if 0 <= index < self.n:
                    print(f"hint[{index}] = {self.hints[index]}\n")
                else:
                    print("Index out of range.\n")
            except ValueError:
                print("Invalid input. Please enter an integer.\n")       
        print("Query phase ended. Use the hints to recover the PRNG state and decrypt the flag.")

    def run(self):
        self.banner()
        self.query_loop()

if __name__ == "__main__":
    NumberGuesser().run()

题目先用长度为8的字节串作为seed，然后生成624个getrandbits(32)，然后生成一个128bits的数作为AES的key，seed*2作为iv加密flag，我们能获得624个getrandbits(32)中任意10个位置的值。

1. MT19937 的内部机制

MT19937 的结构：

  • 内部状态：624 个 32 位整数的数组 MT[0..623]
  • 索引：当前位置指针 index
  • 输出函数：temper(MT[index]) 生成一个 32 位随机数

getrandbits(32) 的工作流程：

1
2
3
4
5
6
def getrandbits(32):
    if index >= 624:
        twist()  # 更新整个状态数组
    y = MT[index]
    index += 1
    return temper(y)  # 应用可逆的位运算

Temper 函数（可逆的位运算）：

1
2
3
4
5
6
def temper(y):
    y ^= (y >> 11)
    y ^= (y << 7) & 0x9d2c5680
    y ^= (y << 15) & 0xefc60000
    y ^= (y >> 18)
    return y

关键点：

  1. Temper 是可逆的 → 可以从输出恢复内部状态
  2. 状态转移是线性的 → 可以从部分状态推导其他状态
  3. 初始化过程是确定性的 → 可以从状态反推 seed

2. Python 对 Bytes Seed 的特殊处理

Python random.seed() 的源码逻辑：

根据 Python 源码（Lib/random.py 和 Modules/_randommodule.c）：

1
2
3
4
5
6
7
8
9
def seed(self, a=None, version=2):
    if version == 2 and isinstance(a, (str, bytes, bytearray)):
        if isinstance(a, str):
            a = a.encode()
        # 关键：bytes 会被特殊处理
        a = int.from_bytes(a + _sha512(a).digest(), 'big')
    
    # 然后调用 C 层的 init_by_array
    super().seed(a)

Bytes Seed 的处理流程：

  1. 哈希扩展：

    1
    2
    3
    seed_bytes = b'\x93\x22\x79\x6b\x7e\x3a\xc1\x93'  # 8 字节
    extended = seed_bytes + sha512(seed_bytes).digest()
    # extended 现在是 8 + 64 = 72 字节

  2. 转换为大整数：

    1
    2
    seed_int = int.from_bytes(extended, 'big')
    # 这是一个 72*8 = 576 位的大整数

  3. 分割为 32 位数组：

    1
    2
    3
    4
    5
    6
    7
    8
    # C 代码中的逻辑
    keyused = (bits - 1) // 32 + 1
    # 对于 72 字节：keyused = (576-1)//32 + 1 = 18

    key = []
    for i in range(keyused):
        key.append((seed_int >> (32*i)) & 0xFFFFFFFF)
    # key 是 18 个 32 位整数的数组

公式推导：

1
2
3
4
n 字节 bytes seed → k = ⌈(n + 64) * 8 / 32⌉ = ⌈(n + 64) / 4⌉

对于 8 字节：
k = ⌈(8 + 64) / 4⌉ = ⌈72 / 4⌉ = 18

详细计算过程：

  1. SHA-512 输出：64 字节（512 位）

    1
    2
    3
    4
    from hashlib import sha512
    seed_bytes = b'\x93\x22\x79\x6b\x7e\x3a\xc1\x93'  # 8 字节
    hash_output = sha512(seed_bytes).digest()
    print(len(hash_output))  # 64 字节

  2. Extended Seed：原始 seed + SHA-512 hash

    1
    2
    extended = seed_bytes + hash_output
    print(len(extended))  # 8 + 64 = 72 字节

  3. 转换为大整数：

    1
    2
    3
    seed_int = int.from_bytes(extended, 'big')
    bits = seed_int.bit_length()
    print(bits)  # 约 576 位 (72 * 8)

  4. 分割为 32 位整数数组：

    1
    2
    3
    4
    5
    6
    7
    8
    # Python 源码中的计算（_randommodule.c 第 265 行）
    keyused = (bits - 1) // 32 + 1

    # 对于 72 字节 = 576 位：
    keyused = (576 - 1) // 32 + 1
           = 575 // 32 + 1
           = 17 + 1
           = 18

源码验证：

在 Modules/_randommodule.c 中：

1
2
/* Figure out how many 32-bit chunks this gives us. */
keyused = bits == 0 ? 1 : (bits - 1) / 32 + 1;

这个公式等价于：keyused = ⌈bits / 32⌉

实际验证代码：

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
import random
from hashlib import sha512

seed_bytes = b'\x93\x22\x79\x6b\x7e\x3a\xc1\x93'

# 模拟 Python 的处理
extended = seed_bytes + sha512(seed_bytes).digest()
print(f"Extended length: {len(extended)} bytes")  # 72 bytes

seed_int = int.from_bytes(extended, 'big')
bits = seed_int.bit_length()
print(f"Bits: {bits}")  # 576 bits

k = (bits - 1) // 32 + 1
print(f"k = {k}")  # 18

# 验证：分割为 32 位整数
key_array = []
for i in range(k):
    chunk = (seed_int >> (32 * i)) & 0xFFFFFFFF
    key_array.append(chunk)

print(f"Key array length: {len(key_array)}")  # 18
print(f"K[16] = {hex(key_array[16])}")  # 原始 seed 的低 32 位
print(f"K[17] = {hex(key_array[17])}")  # 原始 seed 的高 32 位

# 验证 K[16] 和 K[17] 确实对应原始 seed
original_low = int.from_bytes(seed_bytes[0:4], 'little')
original_high = int.from_bytes(seed_bytes[4:8], 'little')
print(f"\nOriginal seed low:  {hex(original_low)}")
print(f"Original seed high: {hex(original_high)}")
print(f"K[16] matches: {key_array[16] == original_low}")
print(f"K[17] matches: {key_array[17] == original_high}")

输出结果：

1
2
3
4
5
6
7
8
9
10
Extended length: 72 bytes
Bits: 576
k = 18
Key array length: 18
K[16] = 0x7e3ac193
K[17] = 0x9322796b
Original seed low:  0x7e3ac193
Original seed high: 0x9322796b
K[16] matches: True
K[17] matches: True

为什么是 K[16] 和 K[17]？

因为 extended seed 的内存布局（little-endian）：

1
2
3
4
5
Byte position:  0  1  2  3  4  5  6  7  8  9  ... 68 69 70 71
                ├──────────┤├──────────┤├─────...─┤├──────────┤
                   K[0]       K[1]        ...       K[16]  K[17]
                                                    └─────┬─────┘
                                                    原始 seed

Extended seed 的最后 8 字节（位置 64-71）就是原始 seed，对应 K[16] 和 K[17]。

对比整数 Seed：

1
2
3
4
5
6
7
8
9
10
# 整数 seed（如 0xDEADBEEF000533D0）
random.seed(0xDEADBEEF000533D0)
# 直接分割：k = 2
# K[0] = 0x000533D0 (低 32 位)
# K[1] = 0xDEADBEEF (高 32 位)

# Bytes seed（如 b'\xd0\x33\x05\x00\xef\xbe\xad\xde'）
random.seed(b'\xd0\x33\x05\x00\xef\xbe\xad\xde')
# 经过 SHA-512：k = 18
# K[0..17] = 18 个 32 位整数

init_by_array：从 Key 数组初始化 MT 状态

C 代码逻辑（简化）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void init_by_array(uint32_t key[], int keylen) {
    // 1. 用常数初始化
    init_genrand(19650218);  // MT[0..623] = 初始常数状态 C
    
    // 2. 混入 key 数组
    for (i = 1; i < 624; i++) {
        j = (i - 1) % keylen;
        MT[i] = (MT[i] ^ ((MT[i-1] ^ (MT[i-1] >> 30)) * 1664525)) + key[j] + j;
    }
    
    // 3. 再次混合
    for (i = 1; i < 624; i++) {
        MT[i] = (MT[i] ^ ((MT[i-1] ^ (MT[i-1] >> 30)) * 1566083941)) - i;
    }
    
    MT[0] = 0x80000000;  // 确保非零
}

状态演化：

1
常数状态 C → 中间状态 J (混入 key) → 初始状态 I (最终混合)

3. Stackered 方法的数学原理

MT19937 的状态转移（Twist）

1
2
3
4
5
6
7
def twist():
    for i in range(624):
        x = (MT[i] & 0x80000000) + (MT[(i+1) % 624] & 0x7FFFFFFF)
        xA = x >> 1
        if x & 1:
            xA ^= 0x9908B0DF
        MT[i] = MT[(i + 397) % 624] ^ xA

数学表示：

1
2
3
4
定义 f(x, y) = ((x & 0x80000000) | (y & 0x7FFFFFFF)) >> 1
             ^ (0x9908B0DF if y & 1 else 0)

则：S[i] = I[i+397] ^ f(I[i], I[i+1])

其中：

  • I = 初始状态（seeding 后）
  • S = 第一次 twist 后的状态（生成 hints 时的状态）

状态转移的线性关系

对于 i < 227：

1
2
3
S[i] = I[i+397] ^ f(I[i], I[i+1])
S[i+227] = I[i+624] ^ f(I[i+227], I[i+228])
         = S[i] ^ f(I[i+227], I[i+228])  # 因为 i+624 = i (mod 624)

因此：

1
S[i] ^ S[i+227] = f(I[i+227], I[i+228])

关键：已知 S[i] 和 S[i+227]，可以恢复 I[i+227] 的 MSB 和 I[i+228] 的低 31 位！

invertStep 函数的原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def invertStep(si, si227):
    X = si ^ si227  # 得到 f(I[i+227], I[i+228])
    
    # f 的定义：
    # temp = (I[i+227] & 0x80000000) | (I[i+228] & 0x7FFFFFFF)
    # result = temp >> 1
    # if I[i+228] & 1: result ^= 0x9908B0DF
    
    # 反推：
    # 1. 检查是否有 XOR 0x9908B0DF（通过 MSB）
    if X & 0x80000000:
        X ^= 0x9908B0DF
        lsb_of_I228 = 1
    else:
        lsb_of_I228 = 0
    
    # 2. 撤销右移
    X <<= 1
    
    # 3. 提取信息
    msb_of_I227 = X & 0x80000000
    low31_of_I228 = (X & 0x7FFFFFFF) | lsb_of_I228
    
    return msb_of_I227, low31_of_I228

从初始状态恢复 Seed

逆向 init_by_array 的第三步（最终混合）：

1
2
3
4
def recover_Ji_from_Ii(Ii, Ii_1, i):
    # 原始：I[i] = (J[i] ^ ((I[i-1] ^ (I[i-1] >> 30)) * 1566083941)) - i
    # 逆向：J[i] = (I[i] + i) ^ ((I[i-1] ^ (I[i-1] >> 30)) * 1566083941)
    return (Ii + i) ^ ((Ii_1 ^ (Ii_1 >> 30)) * 1566083941)

逆向 init_by_array 的第二步（混入 key）：

1
2
3
4
5
6
7
8
9
def recover_Kj_from_Ji(Ji, Ji_1, i):
    # 原始：J[i] = (C[i] ^ ((J[i-1] ^ (J[i-1] >> 30)) * 1664525)) + K[j] + j
    # 其中 j = (i-1) % k
    # 逆向：K[j] + j = J[i] - (C[i] ^ ((J[i-1] ^ (J[i-1] >> 30)) * 1664525))
    
    C = init_genrand(19650218)  # 预计算常数状态
    j = (i - 1) % k
    Kj_plus_j = Ji - (C[i] ^ ((Ji_1 ^ (Ji_1 >> 30)) * 1664525))
    return Kj_plus_j - j

完整攻击流程

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
91
92
93
94
95
96
97
98
┌─────────────────────────────────────────────────────────────────┐
│                    完整攻击流程                                  │
└─────────────────────────────────────────────────────────────────┘

1. 题目生成过程：
   ┌──────────────┐
   │ os.urandom(8)│ → 8 字节随机 seed
   └──────┬───────┘
          │
          ▼
   ┌──────────────────────────────────────────┐
   │ random.seed(seed_bytes)                  │
   │                                          │
   │ seed_bytes + SHA512(seed_bytes)          │
   │ → 72 字节 extended seed                  │
   │ → 转换为大整数                            │
   │ → 分割为 K[0..17] (18 个 32 位整数)      │
   └──────┬───────────────────────────────────┘
          │
          ▼
   ┌──────────────────────────────────────────┐
   │ init_by_array(K, 18)                     │
   │                                          │
   │ 常数 C → 中间状态 J → 初始状态 I         │
   └──────┬───────────────────────────────────┘
          │
          ▼
   ┌──────────────────────────────────────────┐
   │ twist()  # 状态转移                      │
   │                                          │
   │ I[0..623] → S[0..623]                    │
   └──────┬───────────────────────────────────┘
          │
          ▼
   ┌──────────────────────────────────────────┐
   │ hints[i] = temper(S[i])                  │
   │                                          │
   │ 生成 624 个 32 位随机数                   │
   └──────────────────────────────────────────┘

2. 攻击过程（逆向）：
   ┌──────────────────────────────────────────┐
   │ 查询 8 个特定索引的 hints                 │
   │                                          │
   │ hints[3,4,5,6,230,231,232,233]           │
   └──────┬───────────────────────────────────┘
          │
          ▼
   ┌──────────────────────────────────────────┐
   │ untemper(hints[i]) → S[i]                │
   │                                          │
   │ 恢复内部状态                              │
   └──────┬───────────────────────────────────┘
          │
          ▼
   ┌──────────────────────────────────────────┐
   │ invertStep(S[i], S[i+227])               │
   │                                          │
   │ S[3]^S[230] → I[230], I[231]             │
   │ S[4]^S[231] → I[231], I[232]             │
   │ S[5]^S[232] → I[232], I[233]             │
   │ S[6]^S[233] → I[233], I[234]             │
   │                                          │
   │ 合并得到完整的 I[231,232,233,234]        │
   └──────┬───────────────────────────────────┘
          │
          ▼
   ┌──────────────────────────────────────────┐
   │ recover_Ji_from_Ii()                     │
   │                                          │
   │ I[231,232,233,234] → J[231,232,233,234]  │
   └──────┬───────────────────────────────────┘
          │
          ▼
   ┌──────────────────────────────────────────┐
   │ recover_Kj_from_Ji()                     │
   │                                          │
   │ J[233] → K[16]                           │
   │ J[234] → K[17] (两个候选)                │
   └──────┬───────────────────────────────────┘
          │
          ▼
   ┌──────────────────────────────────────────┐
   │ 重构 seed_bytes                          │
   │                                          │
   │ seed_int = (K[17] << 32) | K[16]         │
   │ seed_bytes = bytes.fromhex(hex(seed_int))│
   └──────┬───────────────────────────────────┘
          │
          ▼
   ┌──────────────────────────────────────────┐
   │ 验证并解密                                │
   │                                          │
   │ random.seed(seed_bytes)                  │
   │ 生成 624 个随机数 → 验证匹配              │
   │ 生成第 625 个 → AES 密钥                 │
   │ 用 seed*2 作为 IV → 解密 flag            │
   └──────────────────────────────────────────┘

对于 k=18（8 字节 bytes seed）：

  1. 查询索引：3, 4, 5, 6, 230, 231, 232, 233

    • 这些索引能恢复 I[231], I[232], I[233], I[234]

  2. Untemper：

    1
    2
    3
    S[3] = untemper(hints[3])
    S[230] = untemper(hints[230])
    # ... 其他索引

  3. 恢复初始状态：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    I_230, I_231 = invertStep(S[3], S[230])
    I_231_, I_232 = invertStep(S[4], S[231])
    I_232_, I_233 = invertStep(S[5], S[232])
    I_233_, I_234 = invertStep(S[6], S[233])

    # 合并部分信息
    I_231 += I_231_  # 完整的 I[231]
    I_232 += I_232_  # 完整的 I[232]
    I_233 += I_233_  # 完整的 I[233]
    # I_234 只有低 31 位

  4. 恢复中间状态 J：

    1
    2
    3
    4
    J_231 = recover_Ji_from_Ii(I_231, I_230, 231)
    J_232 = recover_Ji_from_Ii(I_232, I_231, 232)
    J_233 = recover_Ji_from_Ii(I_233, I_232, 233)
    J_234 = recover_Ji_from_Ii(I_234, I_233, 234)

  5. 恢复 Key 数组：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    # K[16] + 16
    K16_plus_16 = recover_Kj_from_Ji(J_233, J_232, 233)
    K16 = K16_plus_16 - 16

    # K[17] + 17（两个候选，因为 I_234 的 MSB 未知）
    K17_plus_17_1 = recover_Kj_from_Ji(J_234, J_233, 234)
    K17_plus_17_2 = recover_Kj_from_Ji(J_234 + 0x80000000, J_233, 234)

    K17_1 = K17_plus_17_1 - 17
    K17_2 = K17_plus_17_2 - 17

  6. 重构 Seed：

    1
    2
    3
    4
    5
    6
    7
    # K[16] 是低 32 位，K[17] 是高 32 位
    seed_int_1 = (K17_1 << 32) | K16
    seed_int_2 = (K17_2 << 32) | K16

    # 转换为 bytes（注意：这是 extended seed 的最后 8 字节）
    seed_bytes_1 = bytes.fromhex(hex(seed_int_1)[2:].zfill(16))
    seed_bytes_2 = bytes.fromhex(hex(seed_int_2)[2:].zfill(16))

  7. 验证：

    1
    2
    3
    random.seed(seed_bytes_1)
    if all(random.getrandbits(32) == hints[i] for i in range(10)):
        # 找到正确的 seed！
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
from functions import untemper, invertStep, recover_Kj_from_Ii
from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES
from pwn import *
import random
import sys
sys.path.append('python-random-playground')

context.log_level = 'info'
HOST = '114.66.24.228'
PORT = 30518

def try_decrypt(enc_hex, key, seed):
    try:
        ct = bytes.fromhex(enc_hex)
        cipher = AES.new(key, AES.MODE_CBC, seed * 2)
        pt = unpad(cipher.decrypt(ct), AES.block_size)
        text = pt.decode('utf-8', errors='strict')
        if text.isprintable() and ('VNCTF{' in text or 'flag{' in text):
            return text
        return None
    except:
        return None

def recover_8byte_seed(outputs):
    log.info("恢复 8 字节 bytes seed (k=18)...")
    
    # Untemper
    S = {}
    for idx, output in outputs.items():
        S[idx] = untemper(output)
    
    # 对于 k=18，需要恢复 I[233], I[234]
    # 查询索引：3, 4, 5, 6, 230, 231, 232, 233
    I_230, I_231 = invertStep(S[3], S[230])
    I_231_, I_232 = invertStep(S[4], S[231])
    I_232_, I_233 = invertStep(S[5], S[232])
    I_233_, I_234 = invertStep(S[6], S[233])
    
    I_231 += I_231_
    I_232 += I_232_
    I_233 += I_233_
    
    log.debug(f"I_231 = {hex(I_231)}")
    log.debug(f"I_232 = {hex(I_232)}")
    log.debug(f"I_233 = {hex(I_233)}")
    log.debug(f"I_234 = {hex(I_234)}")
    
    # K[16] + 16 (低 32 位)
    seed_l = recover_Kj_from_Ii(I_233, I_232, I_231, 233) - 16
    
    # K[17] + 17 (高 32 位)
    seed_h1 = recover_Kj_from_Ii(I_234, I_233, I_232, 234) - 17
    seed_h2 = recover_Kj_from_Ii(I_234 + 0x80000000, I_233, I_232, 234) - 17
    
    seed1 = (seed_h1 << 32) + seed_l
    seed2 = (seed_h2 << 32) + seed_l
    
    log.info(f"候选 seed 1: {hex(seed1)}")
    log.info(f"候选 seed 2: {hex(seed2)}")
    
    # 转换为 bytes
    candidates = []
    for seed_int in [seed1, seed2]:
        try:
            seed_bytes = bytes.fromhex(hex(seed_int)[2:])
            if len(seed_bytes) <= 8:
                # 补齐到 8 字节
                seed_bytes = seed_bytes.rjust(8, b'\x00')
                candidates.append(seed_bytes)
                log.info(f"  -> bytes: {seed_bytes.hex()}")
        except:
            pass
    
    return candidates

def attack():    
    io = remote(HOST, PORT)
    
    io.recvuntil(b"Encrypted flag:\n")
    enc_hex = io.recvline().strip().decode()
    log.success(f"加密的 flag: {enc_hex}")
    
    # 查询特定索引 - 对于 k=18
    required_indices = [3, 4, 5, 6, 230, 231, 232, 233]
    outputs = {}
    
    log.info("查询特定索引...")
    for idx in required_indices:
        io.recvuntil(b"Enter index")
        io.sendline(str(idx).encode())
        io.recvuntil(f"hint[{idx}] = ".encode())
        value = int(io.recvline().strip().decode())
        outputs[idx] = value
        log.info(f"  hints[{idx}] = {value}")
    
    # 还有 2 次查询机会
    extra_indices = [0, 1]
    for idx in extra_indices:
        io.recvuntil(b"Enter index")
        io.sendline(str(idx).encode())
        io.recvuntil(f"hint[{idx}] = ".encode())
        value = int(io.recvline().strip().decode())
        outputs[idx] = value
        log.info(f"  hints[{idx}] = {value}")
    
    io.close()
    
    # 恢复 seed
    candidate_seeds = recover_8byte_seed(outputs)
    
    # 尝试每个候选 seed
    log.info("尝试候选 seed...")
    for seed_bytes in candidate_seeds:
        log.info(f"尝试 seed: {seed_bytes.hex()}")
        
        # 验证
        random.seed(seed_bytes)
        generated = {}
        for idx in range(max(outputs.keys()) + 1):
            generated[idx] = random.getrandbits(32)
        
        matches = sum(1 for idx, expected in outputs.items() if generated.get(idx) == expected)
        log.info(f"  匹配度: {matches}/{len(outputs)}")
        
        if matches < len(outputs):
            log.warning(f"  Seed 不匹配，跳过")
            continue
        
        log.success(f"  Seed 匹配！")
        
        # 生成密钥
        random.seed(seed_bytes)
        for _ in range(624):
            random.getrandbits(32)
        key = random.getrandbits(128).to_bytes(16, 'big')
        
        log.info(f"  密钥: {key.hex()}")
        
        # 尝试解密
        flag = try_decrypt(enc_hex, key, seed_bytes)
        
        if flag:
            log.success(f"找到正确的 seed: {seed_bytes.hex()}")
            log.success(f"Flag: {flag}")
            
            with open("flag.txt", "w") as f:
                f.write(flag)
            log.info("Flag 已保存到 flag.txt")
            
            return flag
    
    log.warning("所有候选 seed 都失败了")
    return None

def main():
    try:
        flag = attack()
        
        if flag:
            print()
            log.info("=" * 70)
            log.success("攻击成功！")
            log.success(f"Flag: {flag}")
            log.info("=" * 70)
        else:
            log.warning("攻击失败")
    
    except KeyboardInterrupt:
        log.warning("用户中断")
    except Exception as e:
        log.warning(f"发生错误: {e}")
        import traceback
        traceback.print_exc()

if __name__ == "__main__":
    main()
# VNCTF{6rEaKlng_PYTh#n_$_Prng_wI7h_4_F3w_V4LUEs_and_n#_6ruTE1orCe}

参考

  1. Python 源码：

  2. Stackered 的研究：

ez_ov

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
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
from hashlib import shake_128
import sys
import os

class OV:
    def __init__(self, o, v, q, key=None):
        self.params = (o, v, q)
        self.F = GF(q)
        self.pub, self.priv = self.keygen() if key == None else key

    def Hash(self, msg):
        h = shake_128(msg).hexdigest(128)
        return vector(self.F, [int(h[i:i+4], 16) for i in range(0,len(h),4)])
        
    def keygen(self):
        o, v, q = self.params
        n = o + v
        Fs = []
        Ps = []

        while True:
            T = random_matrix(self.F, n, n)
            if T.is_invertible():
                break

        for _ in range(o):
            while True:
                Qvv = random_matrix(self.F, v, v)
                Qvv = self.F(2)^(-1) * (Qvv + Qvv.transpose()) 
                Qvo = random_matrix(self.F, v, o)
                Q = block_matrix(self.F, [[Qvv, Qvo], [Qvo.transpose(), 0]])
                if Q.is_invertible():
                    break

            Fs.append(Q)
            Ps.append(T.transpose() * Q * T)

        return Ps, (Fs, T)

    def sign(self, msg):
        o, v, q = self.params
        Fs, T = self.priv
        n = o + v
        M = self.Hash(msg.encode())
        PR = PolynomialRing(self.F, 'x', o)
        X_oil = PR.gens()

        while True:
            V = random_vector(self.F, v).list()
            Y = vector(PR, V + list(X_oil))
            
            L = []
            B = []
            for i in range(o):
                tmp = Y*Fs[i]*Y
                L.append([tmp.coefficient(X_oil[j]) for j in range(o)])
                B.append(tmp([0 for _ in range(o)]))

            L = matrix(self.F, L)
            B = vector(B)
            target = M - B

            if L.is_invertible():
                X_oil = L.solve_right(target)
                Y = vector(self.F, V + list(X_oil))
                return T.inverse() * Y
        

    def verify(self, msg, token):
        msg = self.Hash(msg.encode())
        t = vector(token)
        for i in range(self.params[0]):
            if t*self.pub[i]*t != msg[i]:
                return False
        return True

def menu():
    print('[+] 1. sign')
    print('[+] 2. verify')

def main():
    flag = os.getenv('A1CTF_FLAG')
    o, v = 64, 64
    n = o+v
    q = 0x10001

    pub = []
    with open('pub.txt', 'r') as file:
        for i in range(o):
            file.readline()
            pub.append(matrix(GF(q), eval(''.join([file.readline().strip() for _ in range(n)]))))

    Fs = []
    T = None
    with open('secret.txt', 'r') as file:
        for i in range(o):
            file.readline()
            Fs.append(matrix(GF(q), eval(''.join([file.readline().strip() for _ in range(n)]))))

        file.readline()
        T = matrix(GF(q), eval(''.join([file.readline().strip() for _ in range(n)])))

    priv = (Fs, T)

    ov = OV(o, v, q, key=(pub, priv))

    while True:
        menu()
        try:
            choice = int(input('>'))
    
            if choice == 1: 
                msg = input('your msg:')
                if isinstance(msg, bytes): msg = msg.decode()
                if msg == 'admin': raise RuntimeError
                sig = ov.sign(msg)
                print(f' signature: {sig}')

            if choice == 2:
                sig = input('your signature:').strip()[1:-1]
                if isinstance(sig, bytes): sig = sig.decode()
                sig = vector(GF(q), [int(_.strip()) for _ in sig.split(',')])
                if ov.verify('admin', sig): print(flag)
        except:
            print('error!')
            sys.exit()

if __name__ == "__main__":
    main()

考点: 平衡 Oil and Vinegar 签名方案、Kipnis-Shamir 攻击、OneVector 攻击

题目实现了一个 平衡 Oil and Vinegar (OV) 签名方案：

  • 参数: o = v = 64（oil 和 vinegar 变量数量相等）
  • 有限域: GF(0x10001) = GF(65537)
  • 总维度: n = o + v = 128

给出一个公钥: 64 个 $128\times 128$ 的矩阵 $P_1, …, P_{64}$，还能通过靶机获取除了admin以外任意消息的签名，目标是伪造消息admin的签名。

解题思路

  1. 平衡 OV 的弱点:

    • 当 o = v 时，方案存在已知的多项式时间攻击（Kipnis-Shamir 攻击，1998）
    • 这也是为什么实际应用中使用”不平衡” OV (v > o)

  2. OneVector 攻击（One vector to rule them all: Key recovery from one vector in UOV schemes） ：

    • 只需要找到 一个 oil 空间的向量
    • 就能在多项式时间内恢复整个 64 维 oil 空间
    • 然后可以伪造任意消息的签名

  3. 核心问题:

    • 如何找到第一个 oil 空间向量？
    • Oil 空间是满足 $v^T \cdot P_i \cdot v = 0$ (对所有 $i$) 的向量集合

攻击步骤

步骤 1: MinRank 攻击找到第一个 Oil 向量

MinRank 问题: 找到公钥矩阵的线性组合，使得秩最小。

对于平衡 OV，理论复杂度是 $O(m^4) = O(64^4) \approx 2^24 \approx 1600\cdot 10^4$万次操作。

方法: 系统地枚举小系数的线性组合：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 尝试所有小系数组合
for c0 in range(16):
    for c1 in range(16):
        for c2 in range(16):
            for c3 in range(16):
                # 计算线性组合
                M = c0*P_0 + c1*P_1 + c2*P_2 + c3*P_3
                
                # 检查秩
                if M.rank() < 128:
                    # 检查核空间中的向量
                    for v in M.right_kernel().basis():
                        # 验证是否为 oil 向量
                        if all(v^T * P_i * v == 0 for all i):
                            # 找到了！

结果: 在系数组合 [5, 3, 11, 2] 时，找到秩为 127 的矩阵，其核空间包含一个 oil 向量。

步骤 2: OneVector 攻击恢复完整 Oil 空间

使用论文中的算法，从一个 oil 向量恢复整个 64 维 oil 空间：

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
def attack(G, v):
    """
    OneVector 攻击
    输入: G = 公钥矩阵列表, v = 一个 oil 向量
    输出: Oil 空间的完整基
    """
    m = len(G)
    
    # 1. 计算 Jacobian: J = [v^T * P_1, ..., v^T * P_m]
    J = matrix([v*g for g in G])
    
    # 2. 计算 J 的右核空间
    B = matrix(J.right_kernel().basis())
    
    # 3. 对每个公钥矩阵，限制到核空间并找到其核
    B2 = []
    for g in G:
        ghat = B*g*B.transpose()
        for b in ghat.kernel().basis():
            if b not in span(B2):
                B2.append(b)
        if len(B2) == m:
            break
    
    # 4. 恢复完整 oil 空间
    B3 = matrix(B2)
    C = B3*B
    return C

步骤 3: 伪造签名

有了完整的 oil 空间基 O，可以伪造任意消息的签名：

原理: 对于目标哈希 h，寻找签名 s 使得 $s^T \cdot P_i \cdot s = h_i$

方法:

  1. 随机选择向量 c
  2. 在 oil 空间中找到 $δ$，使得 $(c + δ)^T \cdot P_i \cdot (c + δ) = h_i$
  3. 展开得到线性方程组（因为 $δ^T \cdot P_i \cdot δ = 0$）
  4. 求解得到 δ，则 $s = c + δ$ 就是有效签名
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
for attempt in range(10000):
    c = random_vector(F, n)
    
    # 构建线性系统: c^T * P_i * δ = (h_i - c^T*P_i*c) / 2
    A = []
    b = []
    for i in range(o):
        row = c * pub[i] * O_basis.transpose()
        A.append(row)
        rhs = (target_hash[i] - c * pub[i] * c) / 2
        b.append(rhs)
    
    A = matrix(F, A)
    b = vector(F, b)
    
    if A.rank() == o:
        x = A.solve_right(b)
        delta = O_basis.transpose() * x
        forged_sig = c + delta
        
        # 验证并提交
        if verify(forged_sig):
            submit_to_server(forged_sig)
            break

解题代码

找到第一个 Oil 向量

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
# sage
from hashlib import shake_128
import sys
import time

# 参数
o, v = 64, 64
n = o + v
q = 0x10001
F = GF(q)

print("[*] Loading public key...")
pub = []
with open('pub.txt', 'r') as file:
    for i in range(o):
        file.readline()
        pub.append(matrix(F, eval(''.join([file.readline().strip() for _ in range(n)]))))

print("[*] Systematic MinRank Attack")
print("[*] Trying combinations with small coefficients...")

min_rank = n
best_kernel = None

# 阶段 1: 4个矩阵，系数 0-15
for c0 in range(16):
    for c1 in range(16):
        for c2 in range(16):
            for c3 in range(16):
                if c0 == 0 and c1 == 0 and c2 == 0 and c3 == 0:
                    continue
                
                # 线性组合
                M = c0 * pub[0] + c1 * pub[1] + c2 * pub[2] + c3 * pub[3]
                rank = M.rank()
                
                if rank < min_rank:
                    min_rank = rank
                    best_kernel = M.right_kernel()
                    
                    print(f"[+] New min rank: {rank}, coeffs: [{c0},{c1},{c2},{c3}]")
                    
                    # 检查核向量
                    if best_kernel.dimension() > 0:
                        for vec in best_kernel.basis():
                            vals = [vec * pub[i] * vec for i in range(o)]
                            num_zeros = sum(1 for v in vals if v == 0)
                            
                            if num_zeros == o:
                                print(f"[+] FOUND OIL VECTOR!")
                                
                                with open('oil_vector_found.txt', 'w') as f:
                                    f.write(str(list(vec)))
                                
                                print(f"[+] Saved to oil_vector_found.txt")
                                sys.exit(0)

print(f"[*] Best rank found: {min_rank}")

伪造签名

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
91
92
93
94
#sage
from hashlib import shake_128
import sys

# 参数
o, v = 64, 64
n = o + v
q = 0x10001
F = GF(q)

print("[*] Loading public key...")
pub = []
with open('pub.txt', 'r') as file:
    for i in range(o):
        file.readline()
        pub.append(matrix(F, eval(''.join([file.readline().strip() for _ in range(n)]))))

print("[*] Loading oil vector...")
with open('oil_vector_found.txt', 'r') as f:
    oil_vec = vector(F, eval(f.read()))

# OneVector 攻击实现
def attack(G, v):
    m = len(G) 
    J = matrix([v*g for g in G]) 
    B = matrix(J.right_kernel().basis())
    B2 = []
    
    for g in G:
        ghat = B*g*B.transpose()
        for b in ghat.kernel().basis():
            if len(B2) == 0 or b not in span(B2):
                B2.append(b)
        if len(B2) == m:
            break
    
    B3 = matrix(B2)
    C = B3*B
    return C

print("[*] Running OneVector attack...")
O_basis = attack(pub, oil_vec)
print(f"[+] Recovered {O_basis.nrows()}-dimensional oil space")

# 伪造签名
def Hash(msg):
    h = shake_128(msg).hexdigest(128)
    return vector(F, [int(h[i:i+4], 16) for i in range(0,len(h),4)])

target_hash = Hash(b'admin')

for attempt in range(10000):
    c = random_vector(F, n)
    
    # 构建线性系统
    A = []
    b = []
    for i in range(o):
        row = c * pub[i] * O_basis.transpose()
        A.append(row)
        rhs = (target_hash[i] - c * pub[i] * c) * F(2)^(-1)
        b.append(rhs)
    
    A = matrix(F, A)
    b = vector(F, b)
    
    if A.rank() == o:
        try:
            x = A.solve_right(b)
            delta = O_basis.transpose() * x
            forged_sig = c + delta
            
            # 验证
            vals = [forged_sig * pub[i] * forged_sig for i in range(o)]
            if vector(vals) == target_hash:
                print(f"[+] FORGED SIGNATURE!")
                
                # 提交到服务器
                from pwn import remote
                io = remote('114.66.24.228', 30840, level='warn')
                io.recvuntil(b'>')
                io.sendline(b'2')
                io.recvuntil(b'your signature:')
                sig_str = '(' + ', '.join(map(str, forged_sig)) + ')'
                io.sendline(sig_str.encode())
                response = io.recvall(timeout=2).decode()
                print(response)
                io.close()
                sys.exit(0)
        except:
            pass

print("[-] Failed to forge")
# VNCTF{08bb1333-9e7a-4bdd-ae80-672b0933ba27}
-------------已经到底啦！-------------