1
#!/usr/bin/env python3
2
# -*- coding: utf-8 -*-
3

4
from pwn import remote, context
5
import re
6
import random
7
from Crypto.Cipher import AES
8
from Crypto.Util.Padding import unpad
9

10
context.log_level = "error"  # "info"/"debug" 可看细节
11

12
HOST = "114.66.24.228"
13
PORT = 32532
14

15
MASK32 = 0xFFFFFFFF
16

17
# ---------- MT19937 temper / untemper ----------
18
def temper(y: int) -> int:
19
    y &= MASK32
20
    y ^= (y >> 11)
21
    y ^= (y << 7) & 0x9D2C5680
22
    y ^= (y << 15) & 0xEFC60000
23
    y ^= (y >> 18)
24
    return y & MASK32
25

26
def unshift_right_xor(y: int, shift: int) -> int:
27
    x = y & MASK32
28
    for _ in range(10):
29
        x = y ^ (x >> shift)
30
    return x & MASK32
31

32
def unshift_left_xor_mask(y: int, shift: int, mask: int) -> int:
33
    x = y & MASK32
34
    for _ in range(10):
35
        x = y ^ ((x << shift) & mask)
36
    return x & MASK32
37

38
def untemper(y: int) -> int:
39
    y = unshift_right_xor(y, 18)
40
    y = unshift_left_xor_mask(y, 15, 0xEFC60000)
41
    y = unshift_left_xor_mask(y, 7, 0x9D2C5680)
42
    y = unshift_right_xor(y, 11)
43
    return y & MASK32
44

45
def twist_one(old_i: int, old_ip1: int, old_i397: int) -> int:
46
    y = (old_i & 0x80000000) | (old_ip1 & 0x7FFFFFFF)
47
    x = (old_i397 ^ (y >> 1)) & MASK32
48
    if y & 1:
49
        x ^= 0x9908B0DF
50
    return x & MASK32
51

52
# ---------- IO helpers ----------
53
HEX_RE = re.compile(rb"^[0-9a-fA-F]{32,}$")
54

55
def recv_ciphertext(io) -> bytes:
56
    io.recvuntil(b"Encrypted flag:")
57
    for _ in range(20):
58
        line = io.recvline(timeout=5)
59
        if not line:
60
            break
61
        line = line.strip()
62
        if HEX_RE.match(line):
63
            return bytes.fromhex(line.decode())
64
    raise ValueError("ciphertext line not found")
65

66
def query_hint(io, idx: int) -> int:
67
    io.recvuntil(b"Enter index")
68
    io.sendline(str(idx).encode())
69
    while True:
70
        line = io.recvline(timeout=5)
71
        if not line:
72
            raise EOFError("server closed while waiting hint")
73
        m = re.search(rb"hint\[(\d+)\]\s*=\s*(\d+)", line)
74
        if m:
75
            return int(m.group(2)) & MASK32
76

77
# ---------- validation ----------
78
def validate_seed(seed8: bytes, observed_hints: dict, key_int: int) -> bool:
79
    r = random.Random()
80
    r.seed(seed8)
81

82
    # 生成624个hint（跟服务端一致）
83
    gen = [r.getrandbits(32) for _ in range(624)]
84
    for idx, val in observed_hints.items():
85
        if gen[idx] != val:
86
            return False
87

88
    # 下一次 getrandbits(128) 必须等于我们推出来的 key
89
    k2 = r.getrandbits(128)
90
    return k2 == key_int
91

92
def main():
93
    # 9个足够推 key；第10个随便问一个不冲突的
94
    need9 = [0, 1, 2, 3, 4, 397, 398, 399, 400]
95
    dummy = 10 if 10 not in need9 else 11
96
    ask10 = need9 + [dummy]
97

98
    io = remote(HOST, PORT)
99
    try:
100
        ct = recv_ciphertext(io)
101

102
        observed = {}  # idx -> hint value (tempered output)
103
        for idx in ask10:
104
            val = query_hint(io, idx)
105
            if idx in need9:
106
                observed[idx] = val
107

108
        # ---- recover old state words (untemper) ----
109
        old = {i: untemper(observed[i]) for i in need9}
110

111
        # ---- compute new state words after twist ----
112
        new0 = twist_one(old[0], old[1], old[397])
113
        new1 = twist_one(old[1], old[2], old[398])
114
        new2 = twist_one(old[2], old[3], old[399])
115
        new3 = twist_one(old[3], old[4], old[400])
116

117
        out0 = temper(new0)
118
        out1 = temper(new1)
119
        out2 = temper(new2)
120
        out3 = temper(new3)
121

122
        # 关键：CPython getrandbits(128) 是“低位先来”
123
        key_int = (out0) | (out1 << 32) | (out2 << 64) | (out3 << 96)
124
        key = key_int.to_bytes(16, "big")
125

126
        # ---- brute 2 bytes for P1[6..7] to recover seed8 and iv ----
127
        c1 = ct[:16]
128
        d1 = AES.new(key, AES.MODE_ECB).decrypt(c1)
129

130
        prefix6 = b"VNCTF{"
131

132
        for guess in range(0x10000):
133
            g2 = guess.to_bytes(2, "big")
134
            p0_7 = prefix6 + g2  # 8 bytes
135

136
            # seed8 = D1[0..7] xor P1[0..7]
137
            seed8 = bytes([d1[i] ^ p0_7[i] for i in range(8)])
138
            iv = seed8 + seed8
139

140
            try:
141
                pt = AES.new(key, AES.MODE_CBC, iv).decrypt(ct)
142
                pt = unpad(pt, 16)
143
            except ValueError:
144
                continue
145

146
            if not (pt.startswith(b"VNCTF{") and pt.endswith(b"}")):
147
                continue
148

149
            # 最关键：用 seed8 复验是否能生成同一组 hints & key
150
            if not validate_seed(seed8, observed, key_int):
151
                continue
152

153
            # 到这里基本就是唯一真解
154
            print("FLAG (repr):", repr(pt))
155
            print("FLAG:", pt.decode(errors="strict"))
156
            return
157

158
        print("[-] Not found. (unexpected)")
159

160
    finally:
161
        io.close()
162

163
if __name__ == "__main__":
164
    main()

1
FLAG (repr): b'VNCTF{6R3AK1N6_PyThoN_$_pRNg_W1tH_A_feW_Va1uE$_AnD_no_bRuteforCe}'
2
FLAG: VNCTF{6R3AK1N6_PyThoN_$_pRNg_W1tH_A_feW_Va1uE$_AnD_no_bRuteforCe}

1
#!/usr/bin/env python3
2
# -*- coding: utf-8 -*-
3
"""
4
Solve for ezov (balanced Oil-Vinegar over GF(65537)).
5

6
Requires: numpy, sympy (both commonly available in CTF env)
7
"""
8

9
import ast
10
import hashlib
11
import socket
12
import numpy as np
13
import sympy as sp
14

15
HOST = "114.66.24.228"
16
PORT = 32499
17

18
p = 65537
19
v = o = 64
20
n = v + o
21

22
# ---------- basic modular linear algebra (GF(p)) ----------
23

24
def inv_mod_mat(A, mod=p):
25
    A = (A.copy() % mod).astype(np.int64)
26
    n = A.shape[0]
27
    I = np.eye(n, dtype=np.int64)
28
    aug = np.concatenate([A, I], axis=1)
29
    for col in range(n):
30
        pivot = None
31
        for r in range(col, n):
32
            if aug[r, col] % mod != 0:
33
                pivot = r
34
                break
35
        if pivot is None:
36
            raise ValueError("matrix is singular")
37
        if pivot != col:
38
            aug[[col, pivot]] = aug[[pivot, col]]
39
        inv_piv = pow(int(aug[col, col] % mod), mod - 2, mod)
40
        aug[col, :] = (aug[col, :] * inv_piv) % mod
41
        for r in range(n):
42
            if r == col:
43
                continue
44
            f = aug[r, col] % mod
45
            if f:
46
                aug[r, :] = (aug[r, :] - f * aug[col, :]) % mod
47
    return aug[:, n:]
48

49
def solve_linear(A, b, mod=p):
50
    """Solve A x = b over GF(mod). Return x or None if singular."""
51
    A = (A.copy() % mod).astype(np.int64)
52
    b = (b.copy() % mod).astype(np.int64).reshape(-1, 1)
53
    n = A.shape[0]
54
    aug = np.concatenate([A, b], axis=1)
55

56
    row = 0
57
    for col in range(n):
58
        pivot = None
59
        for r in range(row, n):
60
            if aug[r, col] % mod != 0:
61
                pivot = r
62
                break
63
        if pivot is None:
64
            return None
65
        if pivot != row:
66
            aug[[row, pivot]] = aug[[pivot, row]]
67
        inv_piv = pow(int(aug[row, col] % mod), mod - 2, mod)
68
        aug[row, :] = (aug[row, :] * inv_piv) % mod
69
        for r in range(n):
70
            if r == row:
71
                continue
72
            f = aug[r, col] % mod
73
            if f:
74
                aug[r, :] = (aug[r, :] - f * aug[row, :]) % mod
75
        row += 1
76

77
    return aug[:, -1].reshape(-1)
78

79
def col_space_basis(A, mod=p):
80
    """Return a column-space basis of A over GF(mod) as an (n,rank) matrix."""
81
    A = (A.copy() % mod).astype(np.int64)
82
    M = A.copy()
83
    r, c = M.shape
84
    row = 0
85
    pivcols = []
86
    for col in range(c):
87
        pivot = None
88
        for rr in range(row, r):
89
            if M[rr, col] % mod != 0:
90
                pivot = rr
91
                break
92
        if pivot is None:
93
            continue
94
        if pivot != row:
95
            M[[row, pivot]] = M[[pivot, row]]
96
        inv_piv = pow(int(M[row, col] % mod), mod - 2, mod)
97
        M[row, :] = (M[row, :] * inv_piv) % mod
98
        for rr in range(row + 1, r):
99
            f = M[rr, col] % mod
100
            if f:
101
                M[rr, :] = (M[rr, :] - f * M[row, :]) % mod
102
        pivcols.append(col)
103
        row += 1
104
        if row == r:
105
            break
106
    basis_cols = [A[:, j].copy() % mod for j in pivcols]
107
    return np.column_stack(basis_cols)
108

109
def rank_mod(A, mod=p):
110
    A = (A.copy() % mod).astype(np.int64)
111
    r, c = A.shape
112
    row = 0
113
    rank = 0
114
    for col in range(c):
115
        pivot = None
116
        for rr in range(row, r):
117
            if A[rr, col] % mod != 0:
118
                pivot = rr
119
                break
120
        if pivot is None:
121
            continue
122
        if pivot != row:
123
            A[[row, pivot]] = A[[pivot, row]]
124
        inv_piv = pow(int(A[row, col] % mod), mod - 2, mod)
125
        A[row, :] = (A[row, :] * inv_piv) % mod
126
        for rr in range(row + 1, r):
127
            f = A[rr, col] % mod
128
            if f:
129
                A[rr, :] = (A[rr, :] - f * A[row, :]) % mod
130
        row += 1
131
        rank += 1
132
        if row == r:
133
            break
134
    return rank
135

136
# ---------- load public key matrices ----------
137

138
def load_pub(path="pub.txt"):
139
    mats = []
140
    with open(path, "r", encoding="utf-8") as f:
141
        for _ in range(o):
142
            _ = f.readline()  # header like "P_0 ="
143
            s = "".join([f.readline().strip() for _ in range(n)])
144
            data = ast.literal_eval(s)
145
            arr = (np.array(data, dtype=np.int64) % p)
146
            assert arr.shape == (n, n)
147
            mats.append(arr)
148
    return mats
149

150
# ---------- characteristic polynomial mod p (Faddeev–LeVerrier) ----------
151

152
def charpoly_mod(A, mod=p):
153
    A = (A.copy() % mod).astype(np.int64)
154
    n = A.shape[0]
155
    B = np.eye(n, dtype=np.int64)
156
    coeffs = []
157
    for k in range(1, n + 1):
158
        B = (A.dot(B)) % mod
159
        tr = int(np.trace(B) % mod)
160
        ck = (-tr * pow(k, mod - 2, mod)) % mod
161
        coeffs.append(ck)
162
        if ck:
163
            idx = np.arange(n)
164
            B[idx, idx] = (B[idx, idx] + ck) % mod
165
    # x^n + c1 x^(n-1) + ... + cn
166
    return [1] + coeffs
167

168
def poly_eval_mat(coeffs_high_to_low, A, mod=p):
169
    """Evaluate polynomial at matrix A via Horner: coeffs are [a0..ad] for a0*x^d + ... + ad."""
170
    A = (A.copy() % mod).astype(np.int64)
171
    n = A.shape[0]
172
    res = np.zeros((n, n), dtype=np.int64)
173
    I = np.eye(n, dtype=np.int64)
174
    for c in coeffs_high_to_low:
175
        res = (A.dot(res)) % mod
176
        if c:
177
            idx = np.arange(n)
178
            res[idx, idx] = (res[idx, idx] + int(c)) % mod
179
    return res
180

181
# ---------- recover Oil subspace U ----------
182

183
def recover_oil_basis(pub):
184
    P0 = pub[0]
185
    P0_inv = inv_mod_mat(P0)
186

187
    # Similarity matrix: A = P0^{-1} P1  ~  [[Z^T, 0],[*, Z]]
188
    A = (P0_inv.dot(pub[1])) % p
189

190
    # charpoly(A) = f(x)^2 (because diag blocks have same charpoly); the squarefree part is gcd(cp, cp')
191
    x = sp.Symbol("x")
192
    cp_coeffs = charpoly_mod(A)
193
    cp = sp.Poly(sum(int(c) * x ** (n - i) for i, c in enumerate(cp_coeffs)), x, modulus=p)
194
    f = sp.gcd(cp, cp.diff())          # deg 64
195
    f_coeffs = [int(c) % p for c in f.all_coeffs()]
196

197
    # N = f(A) has image exactly the Oil subspace (dim 64)
198
    N = poly_eval_mat(f_coeffs, A)
199
    U = col_space_basis(N)
200
    assert U.shape == (n, o)
201
    return U
202

203
# ---------- signing (forge admin) ----------
204

205
def hash_vec(msg: bytes, mod=p):
206
    h = hashlib.shake_128(msg).hexdigest(128)  # 128 bytes -> 256 hex chars -> 64 * 16-bit
207
    out = []
208
    for i in range(0, 4 * o, 4):
209
        out.append(int(h[i:i + 4], 16) % mod)
210
    return np.array(out, dtype=np.int64)
211

212
def transform_key(pub, S):
213
    ST = S.T % p
214
    Q = []
215
    for P in pub:
216
        Q.append((ST.dot(P).dot(S)) % p)
217
    return Q
218

219
def sign_message(target_vec, Qmats, S, max_tries=300):
220
    # In transformed coordinates y=(vinegar,oil):
221
    # q_i(y)= v^T A_i v + 2 v^T B_i o  (since oil-oil block = 0)
222
    As = [Q[:v, :v] for Q in Qmats]
223
    Bs = [Q[:v, v:] for Q in Qmats]
224

225
    rng = np.random.default_rng()
226
    for _ in range(max_tries):
227
        vv = rng.integers(0, p, size=v, dtype=np.int64)
228
        vv_row = vv.reshape(1, -1)
229

230
        L = np.zeros((o, o), dtype=np.int64)
231
        c = np.zeros(o, dtype=np.int64)
232
        for i in range(o):
233
            quad = int((vv_row.dot(As[i]).dot(vv) % p).item())
234
            c[i] = (int(target_vec[i]) - quad) % p
235
            L[i, :] = (2 * (vv_row.dot(Bs[i]) % p)) % p
236

237
        oo = solve_linear(L, c)
238
        if oo is None:
239
            continue
240

241
        y = np.concatenate([vv, oo]) % p
242
        sig = (S.dot(y)) % p
243
        return sig
244

245
    raise RuntimeError("sign failed (try increasing max_tries)")
246

247
# ---------- remote io helpers ----------
248

249
def recvuntil(sock, token: bytes, max_bytes=1 << 20):
250
    data = b""
251
    while token not in data:
252
        chunk = sock.recv(4096)
253
        if not chunk:
254
            break
255
        data += chunk
256
        if len(data) > max_bytes:
257
            break
258
    return data
259

260
def main():
261
    pub = load_pub("pub.txt")
262

263
    # 1) recover Oil subspace
264
    U = recover_oil_basis(pub)
265

266
    # 2) build basis S = [V | U], where V = P0*U (the shared Vinegar subspace image)
267
    V = (pub[0].dot(U)) % p
268
    S = np.concatenate([V, U], axis=1) % p
269
    assert rank_mod(S) == n
270

271
    # 3) transform public key into (Vinegar,Oil) coordinates
272
    Qmats = transform_key(pub, S)
273

274
    # 4) forge signature for "admin"
275
    target = hash_vec(b"admin")
276
    sig = sign_message(target, Qmats, S)
277
    sig_list = "[" + ",".join(str(int(x)) for x in sig.tolist()) + "]"
278

279
    # 5) send to remote
280
    with socket.create_connection((HOST, PORT)) as s:
281
        # service prompt is '>' (see main.sage input('>'))
282
        recvuntil(s, b">")
283
        s.sendall(b"2\n")
284
        recvuntil(s, b"signature")
285
        s.sendall(sig_list.encode() + b"\n")
286
        out = s.recv(4096)
287
        print(out.decode(errors="ignore"), end="")
288

289
if __name__ == "__main__":
290
    main()

1
(latt) ➜  Crypto python solve_fixed.py
2
VNCTF{2eccef4f-da1b-4292-83a1-a81148f06f88}
3
[+] 1. sign
4
[+] 2. verify
5
>%

1
#!/usr/bin/env sage
2
# -*- coding: utf-8 -*-
3
#
4
# HD_is_what — final solve
5
# Usage: sage solve.sage
6
#
7
# Needs: output.txt, pycryptodome
8
# Auto-downloads GiacomoPope/Castryck-Decru-SageMath if missing.
9

10
import ast, os, sys, tarfile, subprocess, io, re, inspect
11
from contextlib import redirect_stdout
12
from hashlib import sha256
13

14
from Crypto.Cipher import AES
15
from Crypto.Util.Padding import unpad
16

17
OUT_PATH = "output.txt"
18
REPO_DIR = "Castryck-Decru-SageMath-main"
19
ARCHIVE  = "cd_attack_repo.tar.gz"
20

21

22
# ============================================================
23
# 0) Read output
24
# ============================================================
25
data = ast.literal_eval(open(OUT_PATH, "r").read())
26
a = int(data["params"]["a"])
27
b = int(data["params"]["b"])
28
p = (2**a) * (3**b) - 1
29

30
print("[+] a,b =", a, b)
31
print("[+] p bits =", p.nbits())
32

33

34
# ============================================================
35
# 1) Reproduce task.sage LCG + matrices, deobfuscate
36
#    Y = raw * M  => raw = Y * M^{-1}
37
# ============================================================
38
state = int(p)
39
MOD32 = 2**32
40

41
def next_rand():
42
    global state
43
    state = (state * 1664525 + 1013904223) % MOD32
44
    return state
45

46
dim = 12
47
def make_matrix():
48
    M = Matrix(ZZ, dim, dim)
49
    for r in range(dim):
50
        for c in range(dim):
51
            x = next_rand()
52
            M[r, c] = (x % 10 + 10) if r == c else (x % 5)
53
    return M
54

55
M_bob   = make_matrix()
56
M_alice = make_matrix()
57

58
Y_bob   = vector(ZZ, list(map(int, data["bob_obfuscated"])))
59
Y_alice = vector(ZZ, list(map(int, data["alice_obfuscated"])))
60

61
bob_raw_QQ   = Y_bob.change_ring(QQ)   * M_bob.change_ring(QQ).inverse()
62
alice_raw_QQ = Y_alice.change_ring(QQ) * M_alice.change_ring(QQ).inverse()
63

64
def to_int_list(v):
65
    out = []
66
    for x in list(v):
67
        if x.denominator() != 1:
68
            raise ValueError("Non-integer recovered component: %s" % x)
69
        out.append(int(x))
70
    return out
71

72
bob_raw   = to_int_list(bob_raw_QQ)
73
alice_raw = to_int_list(alice_raw_QQ)
74

75
print("[+] deobfuscation OK (all integers)")
76

77

78
# ============================================================
79
# 2) Rebuild F_{p^2}, curves and points
80
# ============================================================
81
Fp = GF(p)
82
R.<X> = PolynomialRing(Fp)
83
Fp2.<i> = GF(p^2, modulus=X^2 + 1)
84

85
def fp2_from_pair(c0, c1):
86
    return Fp2(int(c0)) + Fp2(int(c1))*i
87

88
def point_from_list(E, L4):
89
    x = fp2_from_pair(L4[0], L4[1])
90
    y = fp2_from_pair(L4[2], L4[3])
91
    return E(x, y)
92

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

96
# Bob public: EB, PB, QB
97
EB_a4 = fp2_from_pair(bob_raw[0], bob_raw[1])
98
EB_a6 = fp2_from_pair(bob_raw[2], bob_raw[3])
99
EB = EllipticCurve(Fp2, [0, 6, 0, EB_a4, EB_a6])
100
EB.set_order((p+1)^2, num_checks=0)
101
PB = point_from_list(EB, bob_raw[4:8])
102
QB = point_from_list(EB, bob_raw[8:12])
103

104
# Alice public: EA, PA, QA
105
EA_a4 = fp2_from_pair(alice_raw[0], alice_raw[1])
106
EA_a6 = fp2_from_pair(alice_raw[2], alice_raw[3])
107
EA = EllipticCurve(Fp2, [0, 6, 0, EA_a4, EA_a6])
108
EA.set_order((p+1)^2, num_checks=0)
109
PA = point_from_list(EA, alice_raw[4:8])
110
QA = point_from_list(EA, alice_raw[8:12])
111

112
# torsion bases on E_start
113
P2 = point_from_list(E_start, list(map(int, data["points"]["Pa"])))
114
Q2 = point_from_list(E_start, list(map(int, data["points"]["Qa"])))
115
P3 = point_from_list(E_start, list(map(int, data["points"]["Pb"])))
116
Q3 = point_from_list(E_start, list(map(int, data["points"]["Qb"])))
117

118
print("[+] reconstructed curves and points")
119

120

121
# ============================================================
122
# 3) Download + load CD core only
123
# ============================================================
124
def ensure_cd_repo():
125
    if os.path.isdir(REPO_DIR):
126
        return
127
    url = "https://github.com/GiacomoPope/Castryck-Decru-SageMath/archive/refs/heads/main.tar.gz"
128
    print("[*] downloading Castryck-Decru-SageMath ...")
129
    try:
130
        subprocess.check_call(["bash", "-lc", f"curl -L {url} -o {ARCHIVE}"])
131
    except Exception:
132
        subprocess.check_call(["bash", "-lc", f"wget -O {ARCHIVE} {url}"])
133
    with tarfile.open(ARCHIVE, "r:gz") as tf:
134
        tf.extractall(".")
135
    if not os.path.isdir(REPO_DIR):
136
        cands = [d for d in os.listdir(".") if d.lower().startswith("castryck-decru-sagemath")]
137
        if not cands:
138
            raise RuntimeError("Cannot find extracted Castryck-Decru-SageMath dir")
139
        os.rename(cands[0], REPO_DIR)
140

141
def load_cd_core():
142
    repo_abs = os.path.abspath(REPO_DIR)
143
    if repo_abs not in sys.path:
144
        sys.path.insert(0, repo_abs)
145

146
    old = os.getcwd()
147
    os.chdir(repo_abs)
148
    try:
149
        # speedup is useful and safe
150
        if os.path.exists("speedup.sage"):
151
            print("[*] load speedup.sage")
152
            load("speedup.sage")
153

154
        # ONLY core attack files (avoid demo/test .sage that auto-runs)
155
        for f in ["castryck_decru_attack.sage", "castryck_decru_shortcut.sage"]:
156
            if os.path.exists(f):
157
                print("[*] load", f)
158
                load(f)
159
    finally:
160
        os.chdir(old)
161

162
def extract_bob_key(txt):
163
    m = re.search(r"Bob's secret key revealed as:\s*([0-9]+)", txt)
164
    if m:
165
        return ZZ(m.group(1))
166
    m = re.search(r"Bob.*key.*:\s*([0-9]+)", txt)
167
    if m:
168
        return ZZ(m.group(1))
169
    return None
170

171
ensure_cd_repo()
172
load_cd_core()
173

174

175
# ============================================================
176
# 4) Build two_i = generate_distortion_map(E_start)
177
#    IMPORTANT: two_i is a callable endomorphism, NOT an integer
178
# ============================================================
179
import public_values_aux
180
public_values_aux.p = p
181

182
if not hasattr(public_values_aux, "generate_distortion_map"):
183
    raise RuntimeError("public_values_aux.generate_distortion_map not found (repo mismatch).")
184

185
two_i = public_values_aux.generate_distortion_map(E_start)
186

187

188
# ============================================================
189
# 5) Call CastryckDecruAttack with correct named args
190
# ============================================================
191
if "CastryckDecruAttack" not in globals():
192
    raise RuntimeError("CastryckDecruAttack not found after loading core files.")
193

194
attack = globals()["CastryckDecruAttack"]
195
spec = inspect.getfullargspec(attack)
196

197
pool = {
198
    "a": a, "b": b, "p": p,
199
    "E_start": E_start, "E0": E_start, "E": E_start,
200
    "EA": EA, "PA": PA, "QA": QA,
201
    "EB": EB, "PB": PB, "QB": QB,
202
    "P2": P2, "Q2": Q2, "P3": P3, "Q3": Q3,
203
    "two_i": two_i,
204
}
205

206
kwargs = {}
207
for name in spec.args:
208
    if name in pool:
209
        kwargs[name] = pool[name]
210
    else:
211
        lname = name.lower()
212
        if lname in pool:
213
            kwargs[name] = pool[lname]
214

215
print("[+] running Castryck–Decru on this instance ...")
216

217
buf = io.StringIO()
218
with redirect_stdout(buf):
219
    ret = attack(**kwargs)
220
out = buf.getvalue()
221

222
bobs_key = None
223
try:
224
    if ret is not None:
225
        bobs_key = ZZ(ret)
226
except Exception:
227
    pass
228
if bobs_key is None:
229
    bobs_key = extract_bob_key(out)
230

231
if bobs_key is None:
232
    print("[!] Attack output:\n", out)
233
    raise RuntimeError("Attack did not return/print Bob key.")
234

235
print("[+] recovered Bob secret key =", bobs_key)
236

237

238
# ============================================================
239
# 6) shared j + decrypt
240
#    shared_kernel_B = PA + skB*QA   on EA
241
# ============================================================
242
shared_kernel = PA + bobs_key * QA
243
phi_shared = EA.isogeny(shared_kernel, algorithm="factored")
244
shared_j = phi_shared.codomain().j_invariant()
245
print("[+] shared j =", shared_j)
246

247
key = sha256(str(shared_j).encode()).digest()
248
iv = bytes.fromhex(data["iv"])
249
ct = bytes.fromhex(data["ciphertext"])
250

251
pt = AES.new(key, AES.MODE_CBC, iv).decrypt(ct)
252
pt = unpad(pt, 16)
253

254
print("[+] plaintext (bytes):", pt)
255
try:
256
    print("[+] plaintext (utf-8):", pt.decode())
257
except Exception:
258
    pass

1
(latt) ➜  Crypto sage solve.sage
2
[+] a,b = 82 57
3
[+] p bits = 173
4
[+] deobfuscation OK (all integers)
5
[+] reconstructed curves and points
6
[*] load speedup.sage
7
[*] load castryck_decru_attack.sage
8
[*] load castryck_decru_shortcut.sage
9
[+] running Castryck–Decru on this instance ...
10
[+] recovered Bob secret key = 10886546902217234201381501
11
[+] shared j = 1142866251494327722024722943408357092304346310508060*i + 475127538965250882165412064274589165530169435364320
12
[+] plaintext (bytes): b'VNCTF{wo_buzhidao_shuoshenmo_zhejiushiFLAG}'
13
[+] plaintext (utf-8): VNCTF{wo_buzhidao_shuoshenmo_zhejiushiFLAG}

1
from math import isqrt
2
from Crypto.Util.number import long_to_bytes
3
from sympy import primerange
4

5
# ====== paste challenge numbers ======
6
n = 14070754234209585800232634546325624819982185952673905053702891604674100339022883248944477908133810472748877029408864634701590339742452010000798957135872412483891523031580735317558166390805963001389999673532396972009696089072742463405543527845901369617515343242940788986578427709036923957774197805224415531570285914497828532354144069019482248200179658346673726866641476722431602154777272137461817946690611413973565446874772983684785869431957078489177937408583077761820157276339873500082526060431619271198751378603409721518832711634990892781578484012381667814631979944383411800101335129369193315802989383955827098934489
7
e = 65537
8
c = 12312807681090775663449755503116041117407837995529562718510452391461356192258329776159493018768087453289696353524051692157990247921285844615014418841030154700106173452384129940303909074742769886414052488853604191654590458187680183616318236293852380899979151260836670423218871805674446000309373481725774969422672736229527525591328471860345983778028010745586148340546463680818388894336222353977838015397994043740268968888435671821802946193800752173055888706754526261663215087248329005557071106096518012133237897251421810710854712833248875972001538173403966229724632452895508035768462851571544231619079557987628227178358
9
k = 485723311775451084490131424696603828503121391558424003875128327297219030209620409301965720801386755451211861235029553063690749071961769290228672699730274712790110328643361418488523850331864608239660637323505924467595552293954200495174815985511827027913668477355984099228100469167128884236364008368230807336455721259701674165150959031166621381089213574626382643770012299575625039962530813909883594225301664728207560469046767485067146540498028505317113631970909809355823386324477936590351860786770580377775431764048693195017557432320430650328751116174124989038139756718362090105378540643587230129563930454260456320785629555493541609065309679709263733546183441765688806201058755252368942465271917663774868678682736973621371451440269201543952580232165981094719134791956854961433894740133317928275468758142862373593473875148862015695758191730229010960894713851228770656646728682145295722403096813082295018446712479920173040974429645523244575300611492359684052455691388127306813958610152185716611576776736342210195290674162667807163446158064125000445084485749597675094544031166691527647433823855652513968545236726519051559119550903995500324781631036492013723999955841701455597918532359171203698303815049834141108746893552928431581707889710001424400
10
# ================================
11

12
# 1) r = sqrt(k) = u * phi
13
r = isqrt(k)
14
assert r * r == k
15

16
# 2) 找 16-bit prime u，使 u | r
17
u_found = None
18
for u in primerange(2**15, 2**16):   # 16-bit primes
19
    if r % u == 0:
20
        u_found = u
21
        break
22
assert u_found is not None
23

24
phi = r // u_found
25

26
# 3) 用 phi 分解 n
27
s = n - phi + 1          # p+q
28
D = s*s - 4*n
29
sqrtD = isqrt(D)
30
assert sqrtD * sqrtD == D
31

32
p = (s + sqrtD) // 2
33
q = (s - sqrtD) // 2
34
assert p * q == n
35

36
# 4) RSA 解密
37
d = pow(e, -1, phi)
38
m = pow(c, d, n)
39
print(long_to_bytes(m))