pediy CTF 2018 10.1 - 叹息之墙

好久没写blog了,水一篇。。。

说一下前面的ollvm

本来是想用deflat的脚本的。
但默认的貌似跑不了这个程序,稍微魔改了一下(只能跑这个程序)

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
#coding=utf8
from barf.barf import BARF
import angr
import simuvex
import pyvex
import claripy
import struct
import sys

def get_retn_predispatcher(cfg):
global main_dispatcher
for block in cfg.basic_blocks:
if len(block.branches) == 0 and block.direct_branch == None:
retn = block.start_address
elif block.direct_branch == main_dispatcher:
pre_dispatcher = block.start_address
return retn, pre_dispatcher

def get_relevant_nop_blocks(cfg):
global pre_dispatcher, prologue, retn
relevant_blocks = []
nop_blocks = []
for block in cfg.basic_blocks:
if block.direct_branch == pre_dispatcher and len(block.instrs) != 1:
relevant_blocks.append(block.start_address)
elif block.start_address != prologue and block.start_address != retn:
nop_blocks.append(block)
return relevant_blocks, nop_blocks

def statement_inspect(state):
global modify_value
expressions = state.scratch.irsb.statements[state.inspect.statement].expressions
try:
x = expressions.next()
if isinstance(x, pyvex.expr.ITE):
state.scratch.temps[x.cond.tmp] = modify_value
state.inspect._breakpoints['statement'] = []
except:
pass


def symbolic_execution(start_addr, hook_addr=None, modify=None, inspect=False):
global b, relevants, modify_value
if hook_addr != None:
b.hook(hook_addr, retn_procedure, length=5)
if modify != None:
modify_value = modify
state = b.factory.blank_state(addr=start_addr, remove_options={simuvex.o.LAZY_SOLVES})
if inspect:
state.inspect.b('statement', when=simuvex.BP_BEFORE, action=statement_inspect)
p = b.factory.path(state)
succ=p.step()
while succ.successors[0].addr not in relevants:
succ=succ.successors[0].step()
return succ.successors[0].addr

def retn_procedure(state):
global b
ip = state.se.eval(state.regs.ip)
b.unhook(ip)
return

def fill_nop(data, start, end):
global opcode
for i in range(start, end):
data[i] = opcode['nop']

def fill_jmp_offset(data, start, offset):
jmp_offset = struct.pack('<i', offset)
for i in range(4):
data[start + i] = jmp_offset[i]

if __name__ == '__main__':
if len(sys.argv) != 3:
print 'Usage: python deflat.py filename function_address(hex)'
exit(0)
opcode = {'a':'\x87', 'ae': '\x83', 'b':'\x82', 'be':'\x86', 'c':'\x82', 'e':'\x84', 'z':'\x84', 'g':'\x8F',
'ge':'\x8D', 'l':'\x8C', 'le':'\x8E', 'na':'\x86', 'nae':'\x82', 'nb':'\x83', 'nbe':'\x87', 'nc':'\x83',
'ne':'\x85', 'ng':'\x8E', 'nge':'\x8C', 'nl':'\x8D', 'nle':'\x8F', 'no':'\x81', 'np':'\x8B', 'ns':'\x89',
'nz':'\x85', 'o':'\x80', 'p':'\x8A', 'pe':'\x8A', 'po':'\x8B', 's':'\x88', 'nop':'\x90', 'jmp':'\xE9', 'j':'\x0F'}
filename = sys.argv[1]
start = int(sys.argv[2], 16)
barf = BARF(filename)
base_addr = barf.binary.entry_point >> 12 << 12
base_addr = 0x401000-0x400
b = angr.Project(filename, load_options={'auto_load_libs': False})
# b = angr.Project(filename, load_options={'auto_load_libs': False,'main_opts':{'custom_base_addr': 0}})
cfg = barf.recover_cfg(start=start)
blocks = cfg.basic_blocks
prologue = start
main_dispatcher = cfg.find_basic_block(prologue).direct_branch
retn, pre_dispatcher = get_retn_predispatcher(cfg)
relevant_blocks, nop_blocks = get_relevant_nop_blocks(cfg)
print '*******************relevant blocks************************'
print 'prologue:%#x' % start
print 'main_dispatcher:%#x' % main_dispatcher
print 'pre_dispatcher:%#x' % pre_dispatcher
print 'retn:%#x' % retn
print 'relevant_blocks:', [hex(addr) for addr in relevant_blocks]

print '*******************symbolic execution*********************'
relevants = relevant_blocks
relevants.append(prologue)
relevants_without_retn = list(relevants)
relevants.append(retn)
flow = {}
for parent in relevants:
flow[parent] = []
modify_value = None
patch_instrs = {}
for relevant in relevants_without_retn:
print '-------------------dse %#x---------------------' % relevant
block = cfg.find_basic_block(relevant)
has_branches = False
hook_addr = None
for ins in block.instrs:
if ins.mnemonic.startswith('cmov'):
patch_instrs[relevant] = ins
has_branches = True
elif ins.mnemonic.startswith('call'):
hook_addr = ins.address
if has_branches:
flow[relevant].append(symbolic_execution(relevant, hook_addr, claripy.BVV(1, 1), True))
flow[relevant].append(symbolic_execution(relevant, hook_addr, claripy.BVV(0, 1), True))
else:
flow[relevant].append(symbolic_execution(relevant, hook_addr))

print '************************flow******************************'
for (k, v) in flow.items():
print '%#x:' % k, [hex(child) for child in v]

print '************************patch*****************************'
flow.pop(retn)
origin = open(filename, 'rb')
origin_data = list(origin.read())
origin.close()
recovery = open(filename + '.recovered', 'wb')
for nop_block in nop_blocks:
print '=================================='
print 'debug:',hex(nop_block.start_address)
print 'debug:',hex(base_addr)
print 'debug:',hex(nop_block.start_address - base_addr)
print 'debug:',hex(nop_block.end_address - base_addr + 1)

fill_nop(origin_data, nop_block.start_address - base_addr, nop_block.end_address - base_addr + 1)
for (parent, childs) in flow.items():
if len(childs) == 1:
last_instr = cfg.find_basic_block(parent).instrs[-1]
file_offset = last_instr.address - base_addr
origin_data[file_offset] = opcode['jmp']
file_offset += 1
fill_nop(origin_data, file_offset, file_offset + last_instr.size - 1)
fill_jmp_offset(origin_data, file_offset, childs[0] - last_instr.address - 5)
else:
instr = patch_instrs[parent]
file_offset = instr.address - base_addr
fill_nop(origin_data, file_offset, cfg.find_basic_block(parent).end_address - base_addr + 1)
origin_data[file_offset] = opcode['j']
origin_data[file_offset + 1] = opcode[instr.mnemonic[4:]]
fill_jmp_offset(origin_data, file_offset + 2, childs[0] - instr.address - 6)
file_offset += 6
origin_data[file_offset] = opcode['jmp']
fill_jmp_offset(origin_data, file_offset + 1, childs[1] - (instr.address + 6) - 5)
recovery.write(''.join(origin_data))
recovery.close()
print 'Successful! The recovered file: %s' % (filename + '.recovered')

我先尝试对一个小函数去平坦化,但是发现花还是没去掉,看起来还是特别的丑。。。
而且最大的那个函数貌似去平坦化也有问题,总是报奇怪的错。。。那就不去了。。

首先通过ida的框图功能,看出了一个函数的功能分别为printf,scanf,sscanf和sprintf,当然还有库函数strlen和strcmp能直接看到。

通过上面的脚本,虽然我们得不到解密的程序,但他在打log的时候能把所有程序主体块的地址打印出来。如下图中的relevant_blocks

1
2
3
4
5
6
7
^[[C^[[C*******************relevant blocks************************
prologue:0x409ff0
main_dispatcher:0x40a09b
pre_dispatcher:0x45c132
retn:0x45104d
relevant_blocks: ['0x40bdc1', '0x40bff3', '0x40d599', '0x40d5a8', '0x40d7f5', '0x40e544', '0x40e565', '0x40e95f', '0x40edf7', '0x40ee18', '0x40fd16', '0x410e18', '0x411101', '0x411dec', '0x411dfb', '0x412080', '0x413095', '0x4130a4', '0x4130c5', '0x41311f', '0x413140', '0x413161', '0x413182', '0x4131a3', '0x413630', '0x4144f3', '0x414502', '0x414523', '0x414544', '0x414565', '0x41555b', '0x416a65', '0x416a74', '0x4178c6', '0x417b6a', '0x417cf9', '0x418c1d', '0x418c2c', '0x418c3b', '0x418c4a', '0x419d61', '0x41ae49', '0x41bf3a', '0x41ce9e', '0x41cead', '0x41d22c', '0x41d3d5', '0x41d3e4', '0x41d405', '0x41d426', '0x41d447', '0x41d990', '0x41ea18', '0x41ea27', '0x41eacd', '0x41eadc', '0x41fc47', '0x420939', '0x420948', '0x420c35', '0x420ec1', '0x420ed0', '0x4212e4', '0x4220df', '0x4220ee', '0x42210f', '0x422130', '0x422151', '0x422607', '0x422b48', '0x422dc4', '0x4232f7', '0x423306', '0x4233a5', '0x4233b4', '0x42413f', '0x4245e5', '0x4245f4', '0x42575b', '0x426464', '0x426473', '0x426482', '0x426491', '0x4264a0', '0x4268ca', '0x427acc', '0x427adb', '0x427ef0', '0x42835d', '0x428385', '0x429469', '0x42a3ba', '0x42b00d', '0x42b2a6', '0x42c57d', '0x42dd57', '0x42dd74', '0x42dd93', '0x42e1d3', '0x42e5c6', '0x42e5d5', '0x42e5fb', '0x42e9ca', '0x42f12c', '0x42f13b', '0x430530', '0x4311b6', '0x431e7a', '0x43225b', '0x43226a', '0x43262c', '0x432a70', '0x432f28', '0x433db0', '0x434e40', '0x435cce', '0x435cef', '0x43712f', '0x437da3', '0x437db2', '0x437ddb', '0x438067', '0x438314', '0x438335', '0x43922e', '0x43a9c5', '0x43a9d4', '0x43a9ef', '0x43ac0d', '0x43afae', '0x43b19d', '0x43b329', '0x43cc3f', '0x43dd68', '0x43ee27', '0x43f06c', '0x43f08d', '0x440277', '0x4405d3', '0x4405f4', '0x441371', '0x4418a1', '0x442a87', '0x443c31', '0x444c61', '0x4457e7', '0x446acd', '0x447812', '0x447821', '0x4479a9', '0x447eb9', '0x448373', '0x44877c', '0x448926', '0x448c7e', '0x448c8d', '0x448d09', '0x448f60', '0x44a144', '0x44a153', '0x44b0e1', '0x44c174', '0x44c195', '0x44c1d5', '0x44c285', '0x44d170', '0x44e753', '0x44e774', '0x44ec31', '0x44f12e', '0x44f13d', '0x44f166', '0x44f516', '0x44f78f', '0x44fb98', '0x44ffa3', '0x4502bf', '0x450812', '0x450cf7', '0x451055', '0x4513a6', '0x452a8d', '0x452a9c', '0x452aab', '0x453a75', '0x453d05', '0x453d14', '0x453d23', '0x453f5a', '0x454dfb', '0x454e0a', '0x455252', '0x45552e', '0x45553d', '0x45554c', '0x455567', '0x4559b7', '0x455e21', '0x455e30', '0x456cee', '0x45710e', '0x45711d', '0x457414', '0x4577bd', '0x4577cc', '0x4588ba', '0x458cf6', '0x458d05', '0x458d14', '0x459c97', '0x45a2ae', '0x45a2bd', '0x45a2e4', '0x45a30d', '0x45a31c', '0x45a4c4', '0x45b4cc', '0x45b4db', '0x45b4ea', '0x45b4f9', '0x45b65b', '0x45b66a', '0x45b679', '0x45b694', '0x45b6a3', '0x45b6b2', '0x45b6c1', '0x45b6dc', '0x45b6eb', '0x45b6fa', '0x45b715', '0x45b724', '0x45b733', '0x45b742', '0x45b751', '0x45b76c', '0x45b77b', '0x45b8d5', '0x45b96e', '0x45babc', '0x45bacb', '0x45baf4', '0x45bb03', '0x45bb1e', '0x45bb2d', '0x45bb3c', '0x45bb62', '0x45bb71', '0x45bb80', '0x45bb8f', '0x45bbbd', '0x45bbd5', '0x45bbfb', '0x45bc0a', '0x45bc19', '0x45bc28', '0x45bcff', '0x45bdbc', '0x45bdcb', '0x45bdda', '0x45bf11', '0x45bfba', '0x45c0d3', '0x45c0e2', '0x45c0fa']
*******************symbolic execution*********************

因此我们通过对所有主体块下断,通过od脚本或者x64dbg的脚本自动trace调用的顺序。

od script:

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
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
bp 40bdc1
bp 40bff3
bp 40d599
bp 40d5a8
bp 40d7f5
bp 40e544
bp 40e565
bp 40e95f
bp 40edf7
bp 40ee18
bp 40fd16
bp 410e18
bp 411101
bp 411dec
bp 411dfb
bp 412080
bp 413095
bp 4130a4
bp 4130c5
bp 41311f
bp 413140
bp 413161
bp 413182
bp 4131a3
bp 413630
bp 4144f3
bp 414502
bp 414523
bp 414544
bp 414565
bp 41555b
bp 416a65
bp 416a74
bp 4178c6
bp 417b6a
bp 417cf9
bp 418c1d
bp 418c2c
bp 418c3b
bp 418c4a
bp 419d61
bp 41ae49
bp 41bf3a
bp 41ce9e
bp 41cead
bp 41d22c
bp 41d3d5
bp 41d3e4
bp 41d405
bp 41d426
bp 41d447
bp 41d990
bp 41ea18
bp 41ea27
bp 41eacd
bp 41eadc
bp 41fc47
bp 420939
bp 420948
bp 420c35
bp 420ec1
bp 420ed0
bp 4212e4
bp 4220df
bp 4220ee
bp 42210f
bp 422130
bp 422151
bp 422607
bp 422b48
bp 422dc4
bp 4232f7
bp 423306
bp 4233a5
bp 4233b4
bp 42413f
bp 4245e5
bp 4245f4
bp 42575b
bp 426464
bp 426473
bp 426482
bp 426491
bp 4264a0
bp 4268ca
bp 427acc
bp 427adb
bp 427ef0
bp 42835d
bp 428385
bp 429469
bp 42a3ba
bp 42b00d
bp 42b2a6
bp 42c57d
bp 42dd57
bp 42dd74
bp 42dd93
bp 42e1d3
bp 42e5c6
bp 42e5d5
bp 42e5fb
bp 42e9ca
bp 42f12c
bp 42f13b
bp 430530
bp 4311b6
bp 431e7a
bp 43225b
bp 43226a
bp 43262c
bp 432a70
bp 432f28
bp 433db0
bp 434e40
bp 435cce
bp 435cef
bp 43712f
bp 437da3
bp 437db2
bp 437ddb
bp 438067
bp 438314
bp 438335
bp 43922e
bp 43a9c5
bp 43a9d4
bp 43a9ef
bp 43ac0d
bp 43afae
bp 43b19d
bp 43b329
bp 43cc3f
bp 43dd68
bp 43ee27
bp 43f06c
bp 43f08d
bp 440277
bp 4405d3
bp 4405f4
bp 441371
bp 4418a1
bp 442a87
bp 443c31
bp 444c61
bp 4457e7
bp 446acd
bp 447812
bp 447821
bp 4479a9
bp 447eb9
bp 448373
bp 44877c
bp 448926
bp 448c7e
bp 448c8d
bp 448d09
bp 448f60
bp 44a144
bp 44a153
bp 44b0e1
bp 44c174
bp 44c195
bp 44c1d5
bp 44c285
bp 44d170
bp 44e753
bp 44e774
bp 44ec31
bp 44f12e
bp 44f13d
bp 44f166
bp 44f516
bp 44f78f
bp 44fb98
bp 44ffa3
bp 4502bf
bp 450812
bp 450cf7
bp 451055
bp 4513a6
bp 452a8d
bp 452a9c
bp 452aab
bp 453a75
bp 453d05
bp 453d14
bp 453d23
bp 453f5a
bp 454dfb
bp 454e0a
bp 455252
bp 45552e
bp 45553d
bp 45554c
bp 455567
bp 4559b7
bp 455e21
bp 455e30
bp 456cee
bp 45710e
bp 45711d
bp 457414
bp 4577bd
bp 4577cc
bp 4588ba
bp 458cf6
bp 458d05
bp 458d14
bp 459c97
bp 45a2ae
bp 45a2bd
bp 45a2e4
bp 45a30d
bp 45a31c
bp 45a4c4
bp 45b4cc
bp 45b4db
bp 45b4ea
bp 45b4f9
bp 45b65b
bp 45b66a
bp 45b679
bp 45b694
bp 45b6a3
bp 45b6b2
bp 45b6c1
bp 45b6dc
bp 45b6eb
bp 45b6fa
bp 45b715
bp 45b724
bp 45b733
bp 45b742
bp 45b751
bp 45b76c
bp 45b77b
bp 45b8d5
bp 45b96e
bp 45babc
bp 45bacb
bp 45baf4
bp 45bb03
bp 45bb1e
bp 45bb2d
bp 45bb3c
bp 45bb62
bp 45bb71
bp 45bb80
bp 45bb8f
bp 45bbbd
bp 45bbd5
bp 45bbfb
bp 45bc0a
bp 45bc19
bp 45bc28
bp 45bcff
bp 45bdbc
bp 45bdcb
bp 45bdda
bp 45bf11
bp 45bfba
bp 45c0d3
bp 45c0e2
bp 45c0fa
wrt "out_func0.txt", "======analysis1 log======"
myloop:
wrta "out_func0.txt",eip
run
jmp myloop

对主函数分析如下:

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
log 11x22x33x44x55x66x77X 
48141A

40BDC1 - init
40BFF3 - print_banner&get_input
40D599 - direct_nop

for i in range(7):
# loop_main_log
40D5A8 nop
40D7F5 cmp flag1 == zero
40E544 nop
40E565 nop
40E95F %d%n sscanf
40EDF7 test [303Bh],1
411DFB nop
412080 nop
413095 direct_nop
4130A4 cmp flag1 == zero
4130C5 %c sscanf ,inc flag1
41311F cmp [303Ch],1
413182 cmp [303Ch],0
4131A3 nop
413630 nop
4144F3 direct_nop
414502 cmp [3040h],'x'

# loop_continue
414523 cmp [3040h],'x'
414565 nop
41555B nop
416A65 direct_nop
418C4A nop
419D61 nop
41AE49 nop
41BF3A nop
41CE9E direct_nop
426491 direct_nop
4264A0 nop
4268CA nop
427ACC direct_nop
427ADB nop
427EF0 nop
42835D test [304Ch],1

428385 nop
429469 nop
42A3BA nop
42B00D nop
42B2A6 nop
42C57D nop
42DD57 mov [301Bh], [301Ch]&1
42DD74 test [301Bh],1

#loop_end
414544 cmp [3040h],'X'
416A74 nop
4178C6 nop
417B6A nop
417CF9 nop
418C1D direct_nop

418C4A nop
419D61 nop
41AE49 nop
41BF3A nop
41CE9E direct_nop
426491 direct_nop
4264A0 nop
4268CA nop
427ACC direct_nop
427ADB nop
427EF0 nop
42835D test [304Ch],1
42DD74 test [301Bh],1

42DD93 nop
42E1D3 %d strlen input_tbl ,sprintf
42E5C6 direct_nop

for i in range(7):
#main log
42E5D5 cmp [[esi+302Ch]], idx_tbl
#continue
42E5FB nop
42E9CA 'x%d', strlen input_tbl ,sprintf
42F12C direct_nop
42F13B nop
430530 nop
4311B6 nop
431E7A nop
43225B direct_nop

#loop_end
43226A nop
43262C nop
432A70 'X', strlen ,sprintf
432F28 nop
433DB0 nop
434E40 nop
435CCE test [esi+304Eh],1
437DDB nop
438067 nop
438314 test [esi+304Fh],1
43A9D4 mov [[esi+302Ch]], 0

for i in range(7)
#main log
43A9EF nop
43AC0D nop
43AFAE nop
43B19D nop
43B329 idx_tbl
43CC3F nop
43DD68 nop
43EE27 nop
43F06C test [esi+3050h],1
#continue
43F08D nop
440277 input_tbl (0x0049FE40)
4405D3
447821
4479A9
447EB9
448373
44877C
448926
448C7E
448C8D

#loop end
448D09
448F60
44A144

for i in range(8):
#main log
44A153 nop
44B0E1 cmp [[esi+302Ch]],idx_tbl
44C174 test [esi+3052h],1

#continue
44C195 [esi+302Ch]->idx, some_tbl[input_tbl[idx]] (351), adc [esi+3024h] , 64位累加
44C1D5 nop

#loop end
44C285 nop
44D170 val1,func2333,val2
44E753 test [esi+3053h],1
44E774 nop
44EC31 输入错误
44F12E
44F166
44F516
44F78F
44FB98
44FFA3
4502BF
450812
450CF7


=============

input "11x22x33x44X"
idx = [11,22,33,44]
int64 sum = 0
for iidx in idx:
sum += tbl[idx]

int64 val1 = 0x65757832
int ret_val = func2333(val1,sum)

cmp ret_val, 0x6E616B34??

然后我又对func233(最前面的一个function)分析了一下:

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
======analysis2 log======
48141A start

401410 nop
401761 nop
4019CE nop
401BF3 push what?
4020FB direct_nop

40210A mov eax, [esi+5B0h],mov ecx, [eax],mov eax, [eax+4],or ecx, eax
402135 nop
402DF2
403FD1
404499
4055FB
405685 x32次(bit)

40210A
402135
402DF2
403FD1
404499
4055FB
40561C imul allrem(取余) 0FFA1CF8Fh
405685

...


40210A
402135
402DF2
403FD1
404499
4055FB
40561C
405685

40210A
40570C
406548
407759
408B62
408FC7
409BC5

然后再通过半黑盒测试,我们得到其算法如下:

pow(1702197298,x,4288794511)=1851878196

其中x是一个总和,来自一张有351个元素的表,我们输入的每一个数都是这张表的元素下标。

可以发现,4288794511是一个质数,所以我们可以考虑大小步算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def bsgs(g, h, p):
"""
Baby-Step-Giant-Step
h = g^x mod p
"""
if not gmpy2.is_prime(p):
return "p is not prime, you shouldn't use BSGS anyway."
N = int(gmpy2.ceil(gmpy2.sqrt(p - 1)))
tbl = {pow(g, i, p): i for i in range(N)}
c = pow(g, N * (p - 2), p)
for j in range(N):
y = (h * pow(c, j, p)) % p
if y in tbl: return j * N + tbl[y]
return None

这样我们就能得到解1427250197。

但实际上,x肯定是会大于1427250197的,且运算的时候x是一个64位的数。而这个1427250197肯定不是唯一解。

因为4288794511是质数,$phi(p)=p-1$,

也就是说pow(1702197298,(p-1)*k+1427250197,p)=1851878196

所以得到x的通解(p-1)*k+1427250197 = 4288794510k+1427250197

现在来看这张表

1
tbl=[0xB42B31EE, 0x8B9B7068, 0x5F45C09A, 0xD077AD0A, 0xB0F9DE76, 0x77CC4D6E, 0xD2854184, 0xE80CBE4C, 0xDCBAF374, 0xEDB5A3B8, 0x301B9E16, 0x1D3DF6AE, 0xC37BBCD6, 0x0C43466A, 0x0B51CAD8, 0x6128B7BE, 0xC6175DC4, 0xAA6BDFB4, 0x44DC3CA2, 0xB9EA0B50, 0xA14D8A86, 0x47B0AF58, 0x83F06B20, 0xBE8B8134, 0xF45004B6, 0x840F93D8, 0x29813D18, 0x45CDB834, 0x4A373C42, 0x7C83B748, 0x6D8E7D86, 0xAF73C814, 0x48A22AEA, 0x083F06B2, 0x078BDC90, 0xB7F12036, 0xE6E4BB78, 0xBD9A05A2, 0x0A604F46, 0x99C1ADF6, 0x6B33570A, 0x55D6ECE6, 0x6C7A8296, 0x5C714DE4, 0xDDAC6F06, 0x527642F4, 0xA604F460, 0xDAD7FC50, 0x78BDC900, 0xDEA5B4C6, 0xCCB1BEC2, 0x46BF33C6, 0x93274CF8, 0xDF8F662A, 0xCE94B5E6, 0xEF23C22A, 0x100934B2, 0x9418C88A, 0xC8EBD07A, 0xDB1CFB0C, 0x33205CB6, 0x1A6983F8, 0xBCA88A10, 0x599CDB2E, 0x74F7DAB8, 0xD8F5052C, 0xE080E1BC, 0x58AB5F9C, 0x9D4FE230, 0x6942A0C2, 0x2C55AFCE, 0x02D472B6, 0x8049A590, 0x57B9E40A, 0xC15FF3EA, 0xB06543A6, 0xA6F66FF2, 0x2484D482, 0x087D5822, 0xAD90D0F0, 0x3B6D68EE, 0x95FBBFAE, 0x7F5829FE, 0x1F20EDD2, 0x621A3350, 0x2D1C8E0A, 0x8C8CEBFA, 0x42F9457E, 0x68B4944E, 0x19780866, 0xBDA999FE, 0xEBD2AC94, 0xB51CAD80, 0x03C5EE48, 0xAC9F555E, 0xE629C728, 0x65E02198, 0x5CF505A8, 0x3898F638, 0x86E4068E, 0xF632FBDA, 0x54E57154, 0x5B7FD252, 0x74065F26, 0x8E6FE31E, 0x99611622, 0x9235D166, 0xC342EB0E, 0xE18EC632, 0xA568B37A, 0x784C2570, 0x13CF22FA, 0x6A978B72, 0x20126964, 0x89A5E5EA, 0xFDBED86A, 0x34D307F0, 0x72236802, 0xC7FA54E8, 0x8C2F71D2, 0x9C9620AC, 0x173D416A, 0xA2ACC9E6, 0xA8D96716, 0xA51378CE, 0xAE824C82, 0xDBC977E2, 0x813B2122, 0x3D506012, 0x2A72B8AA, 0x18868CD4, 0xBBB70E7E, 0x05A8E56C, 0x7FD0E7C7, 0xF17B9200, 0x950A441C, 0x75FBE9A4, 0x6D6BFE28, 0x0F0984AE, 0x87D58220, 0x6B890704, 0x9F6A9362, 0x25BB4ED0, 0xFBDBE146, 0x14C09E8C, 0x4A85220E, 0xE8FE39DE, 0x3E41DBA4, 0xCF863178, 0xF815F2FE, 0xE71B42BA, 0x946E7884, 0x62F45058, 0x60373C2C, 0xF9076E90, 0xABADD9CC, 0xA05C0EF4, 0xD1274CBA, 0x4207C9EC, 0x2F2A2284, 0x85F28AFC, 0x92135208, 0xC43466A0, 0xE263D8E0, 0x56C86878, 0x22E6DC1A, 0xBAC592EC, 0x5AB549A6, 0x53F3F5C2, 0x5D62C976, 0x4B769DA0, 0x1B5AFF8A, 0x0E263D8E, 0x9D879C3E, 0xBF7CFCC6, 0x3AFDF4D2, 0x5A8E56C0, 0x8755AA1E, 0xCC8172D8, 0x3C2612B8, 0x63FD2A74, 0xB156BF38, 0xCBC04330, 0x37A77AA6, 0x35C48382, 0x9E7917D0, 0x21F56088, 0x3C5EE480, 0xD169289C, 0x1E2F7240, 0x17951142, 0xB698268A, 0x3F335736, 0xC9DD4C0C, 0x79AF4492, 0x39B92EDE, 0x13A9FC46, 0x9CAD7F36, 0x4E4B1056, 0xA23F0618, 0x36B5FF14, 0xAD2B8C9A, 0xD34C1FC0, 0xB339B65C, 0xD25AA42E, 0x1C4C7B1C, 0x97DEB6D2, 0x4F3C8BE8, 0x2753F88C, 0xB56A934C, 0x6251ED5E, 0x4909A904, 0x704070DE, 0xCE27A762, 0x2B64343C, 0xF26D0D92, 0x5E544508, 0xA7E7EB84, 0x32F010CC, 0x4D5994C4, 0x2E7A82D4, 0xF762C8DC, 0x98D03264, 0xF5418048, 0x7D7532DA, 0xE3555472, 0x18BD1416, 0x88C6FDB2, 0x45B7C43E, 0x9052DA42, 0x12DDA768, 0x9AB32988, 0xD7120E08, 0x41F83590, 0xF0984AE0, 0xEF989ADC, 0x96ED3B40, 0xA4EC85E8, 0xD9E680BE, 0x069A60FE, 0xE9EFB570, 0x822C9CB4, 0x8D7E678C, 0x20FC1AC8, 0x75E9564A, 0x8F615EB0, 0xFAEA65B4, 0xB2483ACA, 0x914455D4, 0x43EAC110, 0x10FAB044, 0xC2516F7C, 0x2D472B60, 0x7AA0C024, 0xFCCD5CD8, 0xC4A3DABC, 0xB60E2912, 0x01E2F724, 0x6640B96C, 0xD52F16E4, 0x31FE953A, 0xF9F8EA22, 0x288FC186, 0x317A282C, 0x965F2ECC, 0xD84DD702, 0x6F4EF54C, 0x53027A30, 0x4024D2C8, 0x1E13095C, 0x4EA7F118, 0x4B2F9766, 0xD43D9B52, 0x8AA9F4D6, 0x33E18C5E, 0xB8E29BC8, 0x279E45F4, 0x398A71CA, 0xEEA71F4A, 0x0F17B920, 0x23D857AC, 0x26ACCA62, 0xE446D004, 0xC708D956, 0x0D34C1FC, 0xE8648E24, 0x85010F6A, 0xC5E8A0B0, 0x89B87944, 0x107E0D64, 0x69A60FE0, 0x67C318BC, 0xB4723828, 0x293B217A, 0x66D19D2A, 0x00F17B92, 0x11EC2BD6, 0x7BB1646E, 0xF08A166E, 0xDE9DEA98, 0x310D19A8, 0x7B923BB6, 0x831E1846, 0xEAE13102, 0x630BAEE2, 0xA9CAE2A8, 0x7314E394, 0xD666AE14, 0xCACEC79E, 0xEBF7D348, 0xE5384B96, 0x3A7BED5C, 0x24C9D33E, 0x2E38A6F2, 0x04B769DA, 0x096ED3B4, 0xA33081AA, 0xC525E232, 0xD803899A, 0x73725DBC, 0x15B21A1E, 0x4C681932, 0x64EEA606, 0xFEB053FC, 0x5535EFDA, 0xB9D4175A, 0xC06E7858, 0xF35E8924, 0x5210FE9E, 0x76DAD1DC, 0xCDA33A54, 0x16A395B0, 0xF724776C, 0x7E66AE6C, 0x8B6F887C, 0x511F830C, 0x41164E5A, 0x4993A67C, 0xECC42826, 0x9BA4A51A, 0xD6209276, 0xA421FD3C, 0xAABC5E3A, 0x5A391C14, 0xE1725D4E, 0x74324712, 0xB6FFA4A4, 0x2103E4F6, 0x7131EC70, 0x6E5D79BA, 0x502E077A]

这张表里其实有很多要素。

比如我们sort一下,会发现首位相加都等于4288794510,
而且除了5个个位数分别为2,4,5,6,8的,其他都是10的倍数,
最小的数是15825810,其中有一大半是这个数的倍数,不是倍数的数如下。

1
tbl2=[2969165430, 3531948420, 3279666390, 2859196340, 3119123280, 2213571360, 1245133890, 1838054790, 138348210, 3873749880, 1798526730, 1383482100, 3735401670, 4012098090, 3676109580, 857758902, 2639258160, 1765974210, 612684930, 756846090, 3182008830, 1559561640, 2573276706, 3784230450, 2775102330, 2018256240, 2309350890, 2351919570, 389890410, 2729232870, 2144397255, 1979443620, 252282030, 2490267780, 1660178520, 3509013690, 2450739720, 1521830310, 989721810, 2270538270, 3431035608, 1009128120, 3063424650, 968437470, 329907270, 2628615990, 2905312410, 659814540, 3043660620, 1649536350, 1225369860, 3458705250, 779780820, 4150446300, 415044630, 1169671230, 1106785680, 4036512480, 2766964200, 553392840, 3299072700, 1715517804, 830089260, 2522820300, 3628979970, 504564060, 1319629080, 1261410150, 3898904100, 3320357040, 276696420, 3027384360, 691741050, 2075223150, 3597053460, 3958887240, 1936874940, 1429598170, 2339342460, 1513692180, 1949452050]

现在我们再来读一遍题目:

1
2
3
正确的序列号由不超过9整数构成,每个整数取值范围是 [0,351)   
请按照顺序输入数字,用字符'x'隔开,用字符'X'结尾
例如:0x1x23x45x67x350X

不超过9个数,我们猜就是由9个数构成,因为要按顺序排序,所以不存在同一个数用两遍的情况。

因为这个通解的个位数是7,所以各位为5的肯定需要,又因为个位为2的+8和4+6的结果都是4288794510,而要组成7只有2,8+4,2+4+6这几种了。4+6没有意义,因此只有2和4+8。我们先假设是2吧。。

因为多次使用那些最小数的倍数没有意义,因此只有1个是最小数的倍数,其他都不是倍数,也就是tbl2里的数了。

那么总结一下,现在的解为6个tbl2的值,857758902,2144397255,一个15825810的倍数。

跑暴力长这样:

1
2
3
4
5
6
7
8
for a1 in tbl2:
for a2 in tbl2:
for a3 in tbl2:
for a4 in tbl2:
for a5 in tbl2:
for a6 in tbl2:
if 7675040 == (a1+a2+a3+a4+a5+a6)%15825810:
print a1,a2,a3,a4,a5,a6

但复杂度还是太高。。。

考虑meet in the middle

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
arr1=[]
arr2=[]
for a1 in tbl2:
for a2 in tbl2:
for a3 in tbl2:
arr1.append((7675040-a1-a2-a3)%15825810)
arr2.append((a1+a2+a3)%15825810)

arr1 = sorted(arr1)
arr2 = sorted(arr2)

print len(arr1)
print len(arr2)
leng=len(arr2)
idx=0
for i in xrange(leng):
val1 = arr1[i]
for j in xrange(idx,leng):
if val1 == arr2[j]:
print val1
exit(0)
elif val1 < arr2[j]:
break
else: #val > arr2[j]
idx+=1

几分钟后能看到相等的值为1096160

重跑一边拿到6个数

1
2
3
4
5
6
7
8
9
10
equ_val = 1096160

for a1 in tbl2:
for a2 in tbl2:
for a3 in tbl2:
if (7675040-a1-a2-a3)%15825810 == equ_val:
print 'typ1: ',a1,a2,a3
if (a1+a2+a3)%15825810 == equ_val:
print 'typ2: ',a1,a2,a3
#2859196340,1559561640,2450739720,553392840,3027384360,3958887240

得到那个倍数

1
2
3
4
5
6
7
8
9
10
11
12
#test
s = [2859196340,1559561640,2450739720,553392840,3027384360,3958887240]
ssum=0
for i in s:
ssum+=i
ssum+=857758902+2144397255

for x in tbl:
for k in range(10):
if 4288794510*k+1427250197 == x+ssum:
print k,x,ssum
#print 4 1171109940 17411318297

倍数为1171109940

现在我们得到了9个数:

1
1171109940,2859196340,1559561640,2450739720,553392840,3027384360,3958887240,857758902,2144397255

用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
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
#include<stdio.h>
#include<assert.h>
long long modulo(long long x,long long N){
return (x % N + N) %N;
}
long long lists[]={0xB42B31EE, 0x8B9B7068, 0x5F45C09A, 0xD077AD0A, 0xB0F9DE76, 0x77CC4D6E, 0xD2854184, 0xE80CBE4C, 0xDCBAF374, 0xEDB5A3B8, 0x301B9E16, 0x1D3DF6AE, 0xC37BBCD6, 0x0C43466A, 0x0B51CAD8, 0x6128B7BE, 0xC6175DC4, 0xAA6BDFB4, 0x44DC3CA2, 0xB9EA0B50, 0xA14D8A86, 0x47B0AF58, 0x83F06B20, 0xBE8B8134, 0xF45004B6, 0x840F93D8, 0x29813D18, 0x45CDB834, 0x4A373C42, 0x7C83B748, 0x6D8E7D86, 0xAF73C814, 0x48A22AEA, 0x083F06B2, 0x078BDC90, 0xB7F12036, 0xE6E4BB78, 0xBD9A05A2, 0x0A604F46, 0x99C1ADF6, 0x6B33570A, 0x55D6ECE6, 0x6C7A8296, 0x5C714DE4, 0xDDAC6F06, 0x527642F4, 0xA604F460, 0xDAD7FC50, 0x78BDC900, 0xDEA5B4C6, 0xCCB1BEC2, 0x46BF33C6, 0x93274CF8, 0xDF8F662A, 0xCE94B5E6, 0xEF23C22A, 0x100934B2, 0x9418C88A, 0xC8EBD07A, 0xDB1CFB0C, 0x33205CB6, 0x1A6983F8, 0xBCA88A10, 0x599CDB2E, 0x74F7DAB8, 0xD8F5052C, 0xE080E1BC, 0x58AB5F9C, 0x9D4FE230, 0x6942A0C2, 0x2C55AFCE, 0x02D472B6, 0x8049A590, 0x57B9E40A, 0xC15FF3EA, 0xB06543A6, 0xA6F66FF2, 0x2484D482, 0x087D5822, 0xAD90D0F0, 0x3B6D68EE, 0x95FBBFAE, 0x7F5829FE, 0x1F20EDD2, 0x621A3350, 0x2D1C8E0A, 0x8C8CEBFA, 0x42F9457E, 0x68B4944E, 0x19780866, 0xBDA999FE, 0xEBD2AC94, 0xB51CAD80, 0x03C5EE48, 0xAC9F555E, 0xE629C728, 0x65E02198, 0x5CF505A8, 0x3898F638, 0x86E4068E, 0xF632FBDA, 0x54E57154, 0x5B7FD252, 0x74065F26, 0x8E6FE31E, 0x99611622, 0x9235D166, 0xC342EB0E, 0xE18EC632, 0xA568B37A, 0x784C2570, 0x13CF22FA, 0x6A978B72, 0x20126964, 0x89A5E5EA, 0xFDBED86A, 0x34D307F0, 0x72236802, 0xC7FA54E8, 0x8C2F71D2, 0x9C9620AC, 0x173D416A, 0xA2ACC9E6, 0xA8D96716, 0xA51378CE, 0xAE824C82, 0xDBC977E2, 0x813B2122, 0x3D506012, 0x2A72B8AA, 0x18868CD4, 0xBBB70E7E, 0x05A8E56C, 0x7FD0E7C7, 0xF17B9200, 0x950A441C, 0x75FBE9A4, 0x6D6BFE28, 0x0F0984AE, 0x87D58220, 0x6B890704, 0x9F6A9362, 0x25BB4ED0, 0xFBDBE146, 0x14C09E8C, 0x4A85220E, 0xE8FE39DE, 0x3E41DBA4, 0xCF863178, 0xF815F2FE, 0xE71B42BA, 0x946E7884, 0x62F45058, 0x60373C2C, 0xF9076E90, 0xABADD9CC, 0xA05C0EF4, 0xD1274CBA, 0x4207C9EC, 0x2F2A2284, 0x85F28AFC, 0x92135208, 0xC43466A0, 0xE263D8E0, 0x56C86878, 0x22E6DC1A, 0xBAC592EC, 0x5AB549A6, 0x53F3F5C2, 0x5D62C976, 0x4B769DA0, 0x1B5AFF8A, 0x0E263D8E, 0x9D879C3E, 0xBF7CFCC6, 0x3AFDF4D2, 0x5A8E56C0, 0x8755AA1E, 0xCC8172D8, 0x3C2612B8, 0x63FD2A74, 0xB156BF38, 0xCBC04330, 0x37A77AA6, 0x35C48382, 0x9E7917D0, 0x21F56088, 0x3C5EE480, 0xD169289C, 0x1E2F7240, 0x17951142, 0xB698268A, 0x3F335736, 0xC9DD4C0C, 0x79AF4492, 0x39B92EDE, 0x13A9FC46, 0x9CAD7F36, 0x4E4B1056, 0xA23F0618, 0x36B5FF14, 0xAD2B8C9A, 0xD34C1FC0, 0xB339B65C, 0xD25AA42E, 0x1C4C7B1C, 0x97DEB6D2, 0x4F3C8BE8, 0x2753F88C, 0xB56A934C, 0x6251ED5E, 0x4909A904, 0x704070DE, 0xCE27A762, 0x2B64343C, 0xF26D0D92, 0x5E544508, 0xA7E7EB84, 0x32F010CC, 0x4D5994C4, 0x2E7A82D4, 0xF762C8DC, 0x98D03264, 0xF5418048, 0x7D7532DA, 0xE3555472, 0x18BD1416, 0x88C6FDB2, 0x45B7C43E, 0x9052DA42, 0x12DDA768, 0x9AB32988, 0xD7120E08, 0x41F83590, 0xF0984AE0, 0xEF989ADC, 0x96ED3B40, 0xA4EC85E8, 0xD9E680BE, 0x069A60FE, 0xE9EFB570, 0x822C9CB4, 0x8D7E678C, 0x20FC1AC8, 0x75E9564A, 0x8F615EB0, 0xFAEA65B4, 0xB2483ACA, 0x914455D4, 0x43EAC110, 0x10FAB044, 0xC2516F7C, 0x2D472B60, 0x7AA0C024, 0xFCCD5CD8, 0xC4A3DABC, 0xB60E2912, 0x01E2F724, 0x6640B96C, 0xD52F16E4, 0x31FE953A, 0xF9F8EA22, 0x288FC186, 0x317A282C, 0x965F2ECC, 0xD84DD702, 0x6F4EF54C, 0x53027A30, 0x4024D2C8, 0x1E13095C, 0x4EA7F118, 0x4B2F9766, 0xD43D9B52, 0x8AA9F4D6, 0x33E18C5E, 0xB8E29BC8, 0x279E45F4, 0x398A71CA, 0xEEA71F4A, 0x0F17B920, 0x23D857AC, 0x26ACCA62, 0xE446D004, 0xC708D956, 0x0D34C1FC, 0xE8648E24, 0x85010F6A, 0xC5E8A0B0, 0x89B87944, 0x107E0D64, 0x69A60FE0, 0x67C318BC, 0xB4723828, 0x293B217A, 0x66D19D2A, 0x00F17B92, 0x11EC2BD6, 0x7BB1646E, 0xF08A166E, 0xDE9DEA98, 0x310D19A8, 0x7B923BB6, 0x831E1846, 0xEAE13102, 0x630BAEE2, 0xA9CAE2A8, 0x7314E394, 0xD666AE14, 0xCACEC79E, 0xEBF7D348, 0xE5384B96, 0x3A7BED5C, 0x24C9D33E, 0x2E38A6F2, 0x04B769DA, 0x096ED3B4, 0xA33081AA, 0xC525E232, 0xD803899A, 0x73725DBC, 0x15B21A1E, 0x4C681932, 0x64EEA606, 0xFEB053FC, 0x5535EFDA, 0xB9D4175A, 0xC06E7858, 0xF35E8924, 0x5210FE9E, 0x76DAD1DC, 0xCDA33A54, 0x16A395B0, 0xF724776C, 0x7E66AE6C, 0x8B6F887C, 0x511F830C, 0x41164E5A, 0x4993A67C, 0xECC42826, 0x9BA4A51A, 0xD6209276, 0xA421FD3C, 0xAABC5E3A, 0x5A391C14, 0xE1725D4E, 0x74324712, 0xB6FFA4A4, 0x2103E4F6, 0x7131EC70, 0x6E5D79BA, 0x502E077A};
int main() {
char* tab = malloc(0x100000000);
for(int i1 = 0;i1 < 351;i1++) {
for(int i2 = 0;i2 < 351;i2++) {
for(int i3 = 0;i3 < 351;i3++) {
if(i1 != i2) {
if(i1 != i3) {
if(i2 != i3) {
unsigned int index = (0x5ddf2868+lists[i1]+lists[i2]+lists[i3])%0xffa1cf8e;
tab[index]=1;
}
}
}
}
}
}
printf("table done\n");
int k1,k2,k3,k4;
for(int i1 = 0; i1 < 351;i1++) {
for(int i2 = 0; i2 < 351;i2++) {
for(int i3 = 0; i3 < 351;i3++) {
for(int i4 = 0; i4 < 351;i4++) {
unsigned int index =modulo((-(lists[i1]+lists[i2]+lists[i3]+lists[i4])),0xffa1cf8e);
if(tab[index] == 1) {
printf("%d %d %d %d\n",i1,i2,i3,i4);
k1=i1;
k2=i2;
k3=i3;
k4=i4;
goto next;
}
}
}
}
}
next:;
unsigned long long n;
printf("k: %d %d %d %d\n",k1,k2,k3,k4);
long long v = modulo((-(lists[k1]+lists[k2]+lists[k3]+lists[k4])),0xffa1cf8e);
n=v;
printf("num: %p %p %p %p\n",lists[k1],lists[k2],lists[k3],lists[k4]);
for(int i1 = 0;i1 < 351;i1++) {
for(int i2 = 0;i2 < 351;i2++) {
for(int i3 = 0;i3 < 351;i3++) {
if((0x5ddf2868+lists[i1]+lists[i2]+lists[i3])%0xffa1cf8e == n) {
printf("%p %p %p\n", lists[i1],lists[i2],lists[i3]);
assert((lists[i1]+lists[i2]+lists[i3]+lists[k1]+lists[k2]+lists[k3]+lists[k4]+857758902+2144397255)%0xffa1cf8e == 1427250197);
printf("done");
exit(1);
}
}
}
}
printf("err");
}

算flag:

1
2
3
4
5
6
7
8
9
s=[1171109940,2859196340,1559561640,2450739720,553392840,3027384360,3958887240,857758902,2144397255]

flag=''
for idx in range(len(tbl)):
if tbl[idx] in s:
flag+=str(idx)+'x'

print flag[:-1]+'X'
# 17x27x60x97x133x161x243x292x309X