1
# !/usr/bin/env python3
2
import hashlib
3
import json
4
from pathlib import Path
5

6
import numpy as np
7
from fpylll import BKZ, CVP, IntegerMatrix, LLL
8

9
def centered(v, q):
10
    return ((v + q // 2) % q) - q // 2
11

12
def decrypt_flag(f_vec, enc_hex):
13
    key = hashlib.sha256(np.array(f_vec, dtype=np.int64).tobytes()).digest()
14
    ct = bytes.fromhex(enc_hex)
15
    return bytes(c ^ key[i % len(key)] for i, c in enumerate(ct))
16

17
def build_basis(A_samp, q, alpha):
18
    # L = {(qz + A x, alpha x)}
19
    m, n = A_samp.shape
20
    d = m + n
21
    rows = []
22
    for i in range(m):
23
        r = [0] * d
24
        r[i] = int(q)
25
        rows.append(r)
26
    for j in range(n):
27
        r = [0] * d
28
        col = A_samp[:, j]
29
        for i in range(m):
30
            r[i] = int(col[i])
31
        r[m + j] = int(alpha)
32
        rows.append(r)
33
    return IntegerMatrix.from_matrix(rows)
34

35
def score_x(x, M_all, c_all, q):
36
    e = centered((c_all + M_all @ x).astype(np.int64), q)
37
    return int(np.dot(e, e)), int(np.max(np.abs(e))), float(np.std(e)), e
38

39
def refine_x(x, M_all, c_all, q, lim=24, rounds=8):
40
    x = np.clip(x.astype(np.int64), -lim, lim)
41

42
    # alternating rounding least squares on quotient vars
43
    pinv = np.linalg.pinv(M_all.astype(np.float64))
44
    for _ in range(rounds):
45
        y = (c_all + M_all @ x).astype(np.float64)
46
        k = np.rint(y / float(q))
47
        rhs = (q * k - c_all).astype(np.float64)
48
        xn = np.rint(pinv @ rhs).astype(np.int64)
49
        xn = np.clip(xn, -lim, lim)
50
        if np.array_equal(xn, x):
51
            break
52
        x = xn
53

54
    # coordinate polish
55
    sc, _, _, expr = score_x(x, M_all, c_all, q)
56
    rng = np.random.default_rng(2026)
57
    for _ in range(10):
58
        improved = False
59
        for i in rng.permutation(len(x)):
60
            old = int(x[i])
61
            col = M_all[:, i]
62
            bestv, bests = old, sc
63
            for nv in (old - 2, old - 1, old + 1, old + 2):
64
                if nv < -lim or nv > lim:
65
                    continue
66
                expr2 = expr + col * (nv - old)
67
                e2 = centered(expr2, q)
68
                sc2 = int(np.dot(e2, e2))
69
                if sc2 < bests:
70
                    bests = sc2
71
                    bestv = nv
72
            if bestv != old:
73
                expr = expr + col * (bestv - old)
74
                x[i] = bestv
75
                sc = bests
76
                improved = True
77
        if not improved:
78
            break
79
    return x
80

81
def main():
82
    base = Path(__file__).resolve().parent
83
    data = json.loads((base / "challenge_data.json").read_text())
84
    enc_hex = (base / "challenge_flag.enc").read_text().strip()
85

86
    q = int(data["q"])
87
    nfull = int(data["n"])
88
    A = np.array(data["A"], dtype=np.int64)
89

90
    f_known = np.zeros(nfull, dtype=np.int64)
91
    known_mask = np.zeros(nfull, dtype=bool)
92
    for i, v in data["hints"]:
93
        i = int(i)
94
        f_known[i] = int(v)
95
        known_mask[i] = True
96

97
    missing = np.where(~known_mask)[0]
98
    n = len(missing)
99
    M_all = A[missing, :].T.astype(np.int64)  # 512 x 76
100
    c_all = (f_known @ A).astype(np.int64)
101

102
    print(f"[+] q={q}, unknown={n}, equations={M_all.shape[0]}")
103

104
    rng = np.random.default_rng(1337)
105
    best_sc = 10**100
106
    best_x = None
107

108
    trial = 0
109
    for m in [96, 112, 128, 144]:
110
        for alpha in [1, 2, 3, 4, 5, 6]:
111
            for beta in [22, 26, 30]:
112
                for _ in range(12):
113
                    trial += 1
114
                    idx = np.sort(rng.choice(M_all.shape[0], size=m, replace=False))
115
                    As = M_all[idx, :]
116
                    cs = c_all[idx]
117

118
                    B = build_basis(As, q, alpha)
119
                    LLL.reduction(B, delta=0.997)
120
                    BKZ.reduction(B, BKZ.Param(block_size=beta, max_loops=2))
121

122
                    # target is -c (NOT reduced mod q)
123
                    target = [int(-v) for v in cs.tolist()] + [0] * n
124
                    v = np.array(CVP.babai(B, target), dtype=np.int64)
125

126
                    x0 = np.rint(v[m:] / float(alpha)).astype(np.int64)
127
                    x0 = np.clip(x0, -28, 28)
128

129
                    for x in (x0, -x0):
130
                        x = refine_x(x, M_all, c_all, q, lim=24, rounds=8)
131
                        sc, mx, sd, _ = score_x(x, M_all, c_all, q)
132

133
                        if sc < best_sc:
134
                            best_sc = sc
135
                            best_x = x.copy()
136
                            print(
137
                                f"[+] best t={trial} m={m} a={alpha} bkz={beta} score={sc} max={mx} std={sd:.2f} xr=[{x.min()},{x.max()}]"
138
                            )
139

140
                        f_rec = f_known.copy()
141
                        for i, pos in enumerate(missing):
142
                            f_rec[pos] = int(x[i])
143
                        pt = decrypt_flag(f_rec.tolist(), enc_hex)
144
                        if b"BITSCTF{" in pt:
145
                            print("\n[+] FLAG FOUND")
146
                            print(pt.decode(errors="ignore"))
147
                            return
148

149
                    if trial % 20 == 0:
150
                        print(f"[*] trial={trial} current_best={best_sc}")
151

152
    print(f"[-] no flag. best_score={best_sc}")
153
    if best_x is not None:
154
        f_rec = f_known.copy()
155
        for i, pos in enumerate(missing):
156
            f_rec[pos] = int(best_x[i])
157
        pt = decrypt_flag(f_rec.tolist(), enc_hex)
158
        print(f"[+] best preview: {pt[:120]!r}")
159

160
if __name__ == "__main__":
161
    main()

1
python3 -m pip install fpylll cysignals numpy
2
python3 solve_primal_target.py

1
[+] best t=33 m=96 a=1 bkz=30 score=8716 max=14 std=4.11 xr=[-7,9]
2

3
[+] FLAG FOUND
4
BITSCTF{h1nts_4r3_p0w3rfu1_4nd_f4lc0ns_4r3_f4st}