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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
|
from pwn import remote
import itertools
from sage.all import Matrix, QQ
from tqdm import tqdm
from Crypto.Util.number import isPrime
HOST = "62.234.144.69"
PORT = 31080
def split_master(B_decimal, segment_bits):
if len(segment_bits) < 3:
raise ValueError("no")
if sum(segment_bits) != 512:
raise ValueError("no")
n = len(segment_bits)
found_combination = None
from itertools import combinations
for k in range(n,1,-1):
for indices in combinations(range(n), k):
if sum(segment_bits[i] for i in indices) > 30:
continue
valid = True
for i in range(len(indices)):
for j in range(i+1, len(indices)):
if abs(indices[i] - indices[j]) <= 1:
valid = False
break
if not valid:
break
if not valid:
continue
if 0 in indices and (n-1) in indices:
continue
if any(segment_bits[i]>=25 for i in indices):
continue
found_combination = indices
break
if found_combination is not None:
break
if found_combination is None:
raise ValueError("no")
binary_str = bin(B_decimal)[2:].zfill(512)
if len(binary_str) > 512:
raise ValueError("no")
segments_binary = []
start = 0
for bits in segment_bits:
end = start + bits
segments_binary.append(binary_str[start:end])
start = end
segments_decimal = [int(segment, 2) for segment in segments_binary]
return [segments_decimal[i] for i in found_combination]
def collect(seg_input=b"481 6 1 24", rounds=20):
io = remote(HOST, PORT)
_ = io.recvline()
q_line = io.recvline().decode().strip()
qq = int(q_line.split(":",1)[1].strip())
A = []
gifts = []
for _ in range(rounds):
io.recvuntil(b"> ")
io.sendline(seg_input)
a_line = io.recvline().decode().strip()
gift_line = io.recvline().decode().strip()
a = int(a_line.split(":",1)[1].strip())
gift = eval(gift_line.split(":",1)[1].strip())
A.append(a)
gifts.append(gift)
return io, qq, A, gifts
def recover_B(N, A, B, n=20):
try:
inv1 = pow(2**31, -1, N)
inv2 = pow(2**24, -1, N)
except Exception as e:
return None
scale = 2**7
M1 = Matrix(QQ, n+2, n+2)
for i in range(10):
M1[i, i] = N * scale
M1[i+10, i+10] = N
M1[-2, i] = A[i] * inv1 * scale
M1[-1, i] = B[i] * inv1 * scale
M1[-2, i+10] = A[i+10] * inv2
M1[-1, i+10] = B[i+10] * inv2
t = QQ(2**488 / N)
K = 2**488
M1[-2, -2] = t
M1[-1, -1] = K
try:
L = M1.LLL()
except Exception:
return None
for row in L:
try:
if abs(row[-1]) == K:
x2 = int(abs(row[-2]) // t)
return x2
except Exception:
continue
return None
if __name__ == "__main__":
io, qq, A, gifts = collect()
if len(A) < 20 or len(gifts) < 20:
print("[!] collected less than 20 groups")
io.close()
raise SystemExit(1)
seg6_list = [g[0] for g in gifts]
seg24_list = [g[1] for g in gifts]
def make_candidate31(seg6, seg24, midbit):
return (seg6 << 25) | (midbit << 24) | seg24
N_groups = 20
total = 1 << 10
print(f"[*] Trying {total} combinations for the 10 unknown middle bits (2^10 = {total})")
found_key = None
for mask in tqdm(range(total), desc="Brute forcing 10 mid-bits", ncols=80):
B_candidates = []
for i in range(10):
midbit = (mask >> i) & 1
val = make_candidate31(seg6_list[i], seg24_list[i], midbit)
B_candidates.append(val)
for i in range(10, 20):
B_candidates.append(seg24_list[i])
x2 = recover_B(qq, A[:20], B_candidates, n=20)
if x2 is None:
continue
for k in range(8):
candidate_key = x2 + k * qq
if candidate_key.bit_length() != 512:
continue
if not isPrime(candidate_key):
continue
ok = True
for idx in range(20):
a_val = A[idx]
b_calc = a_val * candidate_key % qq
try:
segs = split_master(b_calc, [481,6,1,24])
except Exception:
ok = False
break
seg6_calc, seg24_calc = segs[0], segs[1]
if idx < 10:
if seg6_calc != seg6_list[idx] or seg24_calc != seg24_list[idx]:
ok = False
break
else:
if seg24_calc != seg24_list[idx]:
ok = False
break
if ok:
found_key = candidate_key
print("[*] Found key:", found_key)
break
if found_key is not None:
break
if found_key is not None:
try:
io.recvuntil(b"the key to the flag is: ")
except Exception:
pass
io.sendline(str(found_key).encode())
try:
flag = io.recvall(timeout=10)
print("[*] Flag:", flag.decode(errors='ignore'))
except Exception as e:
print("[!] Failed to receive flag:", e)
else:
print("[!] No key found after trying all 2^10 combos")
io.close()
|
