a ctfer on the load

1
__int64 sub_401D1D()
2
{
3
  int v0; // er8
4
  int v1; // er9
5
  __int64 result; // rax
6
  int v3; // er8
7
  int v4; // er9
8
  int i; // [rsp+0h] [rbp-10h]
9
  int j; // [rsp+4h] [rbp-Ch]
10
  __int64 v7; // [rsp+8h] [rbp-8h]
11

12
  v7 = sub_41A910("./data", "r");
13
  if ( !v7 )
14
  {
15
    sub_41AD00("Failed to open file...");
16
    sub_40B390(1LL);
17
  }
18
  result = sub_40C120(v7, (unsigned int)"%lld", (unsigned int)&qword_4E83A0, (unsigned int)"%lld", v0, v1);
19
  for ( i = 0; i <= 23; ++i )
20
    result = sub_40C120(v7, (unsigned int)"%lld", (unsigned int)&qword_4E8220[i], (unsigned int)"%lld", v3, v4);
21
  for ( j = 0; j <= 23; ++j )
22
    result = sub_40C120(v7, (unsigned int)"%lld", (unsigned int)&qword_4E82E0[j], (unsigned int)"%lld", v3, v4);
23
  return result;
24
}

1
printf("Please enter your answer: ");
2
scanf("%lld", &user_input);
3

4
if (user_input != ans) {
5
    puts("Wrong answer!");
6
    exit(1);
7
}
8

9
fp = fopen("./flag", "r");
10
if (!fp) {
11
    puts("Failed to open file...");
12
    exit(1);
13
}
14

15
fgets(buf, 0x40, fp);
16
printf("Congratulations! Here is your flag: %s\n", buf);
17
fclose(fp);

1
long long get_hint_bits(int n) {
2
    assert(n <= 60);
3

4
    long long nxt = 0;
5
    for (int i = 0; i < 24; i++) {
6
        nxt = (nxt + mulmod(X[i], A[i])) % m; // nxt = (nxt + A[i] * X[i]) mod m
7
    }
8

9
    // 左移状态窗口
10
    for (int i = 0; i < 23; i++) {
11
        X[i] = X[i + 1];
12
    }
13
    X[23] = nxt;
14

15
    return nxt >> (60 - n);
16
}
17
long long hint = get_hint_bits(0x28); // 0x28 = 40
18
printf("Here is your hint: %lld\n", hint);

1
from Crypto.Util.number import long_to_bytes
2
import time
3

4
N =
5
e =
6
c =
7
S =
8

9
A = N - S + 1
10
X = 2^338
11
Y = 2^399
12
m = 5
13
t = 2
14

15
PR.<x, y> = PolynomialRing(ZZ)
16
f = x*y - A*x - 1
17

18
original_polys = []
19
for i in range(m + 1):
20
    for j in range(m - i + 1):
21
        original_polys.append(y^j * f^i * e^(m - i))
22

23
for i in range(m + 1):
24
    for j in range(1, t + 1):
25
        original_polys.append(x^j * f^i * e^(m - i))
26

27
def LM_key(monom):
28
    degs = monom.degrees()
29
    return (degs[1], degs[0])
30

31
def get_LM(p):
32
    return max(p.monomials(), key=LM_key)
33

34
poly_dict = {}
35
all_monomials = set()
36

37
for p in original_polys:
38
    lm = get_LM(p)
39
    poly_dict[lm] = p
40
    all_monomials.update(p.monomials())
41

42
for monom in list(all_monomials):
43
    if monom not in poly_dict:
44
        extra_p = monom * (e^m)
45
        poly_dict[monom] = extra_p
46
        all_monomials.update(extra_p.monomials())
47

48
sorted_monomials = sorted(list(all_monomials), key=LM_key)
49
dim = len(sorted_monomials)
50

51
M = Matrix(ZZ, dim, dim)
52

53
for i in range(dim):
54
    lm = sorted_monomials[i]
55
    p_scaled = poly_dict[lm](x*X, y*Y)
56
    for j in range(dim):
57
        monom = sorted_monomials[j]
58
        M[i, j] = p_scaled.monomial_coefficient(monom)
59

60
M_lll = M.LLL()
61

62
roots_polys = []
63
for row in M_lll:
64
    if row.is_zero():
65
        continue
66
    p_scaled = sum(row[j] * sorted_monomials[j] for j in range(dim))
67
    p_unscaled = p_scaled(x/X, y/Y)
68
    roots_polys.append(p_unscaled)
69

70
var_x, var_y = roots_polys[0].parent().gens()
71

72
k_val = None
73
x_val = None
74
found = False
75

76
for i in range(len(roots_polys)):
77
    if found:
78
        break
79
    p1 = roots_polys[i]
80
    if p1.is_constant():
81
        continue
82
    for j in range(i + 1, min(i + 4, len(roots_polys))):
83
        p2 = roots_polys[j]
84
        if p2.is_constant():
85
            continue
86
        res = p1.resultant(p2, var_y)
87
        if res.is_zero() or res.is_constant():
88
            continue
89
        res_uni = res.univariate_polynomial()
90
        roots = res_uni.roots()
91
        for root, _ in roots:
92
            if root == 0:
93
                continue
94
            k_guess = int(root)
95
            p1_sub = p1.subs({var_x: k_guess})
96
            y_roots = p1_sub.univariate_polynomial().roots()
97
            for y_root, _ in y_roots:
98
                if y_root != 0:
99
                    k_val = k_guess
100
                    x_val = int(y_root)
101
                    found = True
102
                    break
103
            if found:
104
                break
105

106
if k_val is not None:
107
    p_plus_q = S + x_val
108
    PR_Z.<z> = PolynomialRing(ZZ)
109
    eqn = z^2 - p_plus_q * z + N
110
    p_q_roots = eqn.roots()
111
    if len(p_q_roots) >= 2:
112
        p = int(p_q_roots[0][0])
113
        q = int(p_q_roots[1][0])
114
        phi = (p - 1) * (q - 1)
115
        d = inverse_mod(e, phi)
116
        m_pt = pow(c, d, N)
117
        print(long_to_bytes(int(m_pt)).decode(errors='ignore'))

1
import json
2
import re
3
from hashlib import sha3_512
4

5
import numpy as np
6

7
from pwn import remote
8

9
HOST = "101.245.107.149"
10
PORT = 10019
11
RNG = np.random.default_rng(0)
12

13

14
def h(msg: str) -> np.ndarray:
15
    return np.array(list(sha3_512(msg.encode()).digest()), dtype=int).reshape(8, 8)
16

17

18
def trop_mul(a: np.ndarray, b: np.ndarray) -> np.ndarray:
19
    n, k = a.shape
20
    k2, m = b.shape
21
    assert k == k2
22
    out = np.full((n, m), 10**9, dtype=int)
23
    for i in range(n):
24
        for j in range(m):
25
            out[i, j] = min(int(a[i, t]) + int(b[t, j]) for t in range(k))
26
    return out
27

28

29
def build_ab(
30
    row_min: np.ndarray, col_min: np.ndarray
31
) -> tuple[np.ndarray, np.ndarray, np.ndarray]:
32
    target = np.minimum(row_min.reshape(8, 1) + 1, col_min.reshape(1, 8) + 1)
33
    for _ in range(10000):
34
        a_extra = 129 + RNG.integers(0, 2, size=(8, 5), dtype=int)
35
        b_extra = 129 + RNG.integers(0, 2, size=(5, 8), dtype=int)
36
        a = np.column_stack([row_min, np.ones(8, dtype=int), a_extra])
37
        b = np.vstack([np.ones((1, 8), dtype=int), col_min.reshape(1, 8), b_extra])
38
        if np.linalg.matrix_rank(a) != 7 or np.linalg.matrix_rank(b) != 7:
39
            continue
40
        if np.array_equal(trop_mul(a, b), target):
41
            return a, b, target
42
    raise RuntimeError("failed to build A/B")
43

44

45
def build_pr(
46
    m: np.ndarray, row_min: np.ndarray, col_min: np.ndarray, target: np.ndarray
47
) -> tuple[np.ndarray, np.ndarray]:
48
    row_arg = np.argmin(m, axis=1)
49
    col_arg = np.argmin(m, axis=0)
50
    need_x = np.zeros((8, 8), dtype=bool)
51
    need_y = np.zeros((8, 8), dtype=bool)
52

53
    for i in range(8):
54
        for j in range(8):
55
            if row_min[i] < col_min[j]:
56
                need_x[row_arg[i], j] = True
57
            elif row_min[i] > col_min[j]:
58
                need_y[i, col_arg[j]] = True
59

60
    for _ in range(20000):
61
        x = RNG.integers(0, 2, size=(8, 8), dtype=int)
62
        y = RNG.integers(0, 2, size=(8, 8), dtype=int)
63
        x[need_x] = 0
64
        y[need_y] = 0
65

66
        ok = True
67
        for i in range(8):
68
            for j in range(8):
69
                if row_min[i] == col_min[j] and x[row_arg[i], j] and y[i, col_arg[j]]:
70
                    ok = False
71
                    break
72
            if not ok:
73
                break
74
        if not ok:
75
            continue
76

77
        p = 1 + x
78
        r = 1 + y
79
        if np.linalg.matrix_rank(p) != 8 or np.linalg.matrix_rank(r) != 8:
80
            continue
81
        z = np.minimum(trop_mul(m, p), trop_mul(r, m))
82
        if np.array_equal(z, target):
83
            return p, r
84
    raise RuntimeError("failed to build P/R")
85

86

87
def build_s(target: np.ndarray) -> np.ndarray:
88
    mask_256 = target == 256
89
    for _ in range(10000):
90
        s = 255 + RNG.integers(0, 2, size=(8, 8), dtype=int)
91
        s[mask_256] = 256
92
        if (
93
            np.all(s >= target)
94
            and np.linalg.matrix_rank(s) == 8
95
            and not np.array_equal(s, target)
96
        ):
97
            return s
98
    raise RuntimeError("failed to build S")
99

100

101
def forge(msg: str) -> dict[str, list[list[int]]]:
102
    m = h(msg)
103
    row_min = m.min(axis=1)
104
    col_min = m.min(axis=0)
105
    a, b, target = build_ab(row_min, col_min)
106
    p, r = build_pr(m, row_min, col_min, target)
107
    s = build_s(target)
108

109
    left = trop_mul(a, b)
110
    right = np.minimum(np.minimum(trop_mul(m, p), trop_mul(r, m)), s)
111
    assert np.array_equal(left, target)
112
    assert np.array_equal(right, target)
113
    assert np.linalg.matrix_rank(a) == 7
114
    assert np.linalg.matrix_rank(b) == 7
115
    assert np.linalg.matrix_rank(p) == 8
116
    assert np.linalg.matrix_rank(r) == 8
117
    assert np.linalg.matrix_rank(s) == 8
118

119
    return {
120
        "A": a.tolist(),
121
        "B": b.tolist(),
122
        "P": p.tolist(),
123
        "R": r.tolist(),
124
        "S": s.tolist(),
125
    }
126

127

128
def solve_remote() -> str:
129
    io = remote(HOST, PORT)
130
    io.recvuntil(b">>> ")
131
    io.sendline(b"2")
132
    line = io.recvline().decode()
133
    match = re.search(r"Please make (.*) for me!", line)
134
    if not match:
135
        raise RuntimeError(line)
136
    payload = json.dumps(forge(match.group(1))).encode()
137
    io.recvuntil(b">>> ")
138
    io.sendline(payload)
139
    out = io.recvall(timeout=3).decode(errors="ignore")
140
    io.close()
141
    return out
142

143

144
if __name__ == "__main__":
145
    print(solve_remote())