首页
论坛
课程
招聘
[原创]KCTF2021春季赛第四题 英雄救美
2021-5-15 11:41 7555

[原创]KCTF2021春季赛第四题 英雄救美

2021-5-15 11:41
7555

程序无壳,ida打开,流程很清晰

程序流程

  1. main 函数

    关键在两个验证函数:checkformat_401240和checksudoku_401000
  2. checkformat_401240
    此函数负责将输入根据字符表分段匹配,转换为1-9,再结合后面的checksudoku_401000函数,推测为数独游戏;
    数独的i行输入在字符表[i9:i9+9]段内查找,根据位置转为1-9,
    每行结束,添加本行已给出数据的个数
  3. checksudoku_401000
    此函数负责验证数独

    writeup

反推,先解数独,再转格式

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
import time
 
t0 = time.time()
 
 
class point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.available = []
        self.value = 0
 
 
def rowNum(p, sudoku):
    row = set(sudoku[p.y * 9:(p.y + 1) * 9])
    row.remove(0)
    return row  # set type
 
 
def colNum(p, sudoku):
    col = []
    length = len(sudoku)
    for i in range(p.x, length, 9):
        col.append(sudoku[i])
    col = set(col)
    col.remove(0)
    return col  # set type
 
 
def blockNum(p, sudoku):
    block_x = p.x // 3
    block_y = p.y // 3
    block = []
    start = block_y * 3 * 9 + block_x * 3
    for i in range(start, start + 3):
        block.append(sudoku[i])
    for i in range(start + 9, start + 9 + 3):
        block.append(sudoku[i])
    for i in range(start + 9 + 9, start + 9 + 9 + 3):
        block.append(sudoku[i])
    block = set(block)
    block.remove(0)
    return block  # set type
 
 
def initPoint(sudoku):
    pointList = []
    length = len(sudoku)
    for i in range(length):
        if sudoku[i] == 0:
            p = point(i % 9, i // 9)
            for j in range(1, 10):
                if j not in rowNum(p, sudoku) and j not in colNum(p, sudoku) and j not in blockNum(p, sudoku):
                    p.available.append(j)
            pointList.append(p)
    return pointList
 
 
ret = None
 
 
def tryInsert(p, sudoku):
    global ret
    availNum = p.available
    for v in availNum:
        p.value = v
        if check(p, sudoku):
            sudoku[p.y * 9 + p.x] = p.value
            if len(pointList) <= 0:
                t1 = time.time()
                useTime = t1 - t0
                ret = showSudoku(sudoku)
                print('\nuse Time: %f s' % (useTime))
                # print(ret)
                return
                # exit()
            p2 = pointList.pop()
            tryInsert(p2, sudoku)
            sudoku[p2.y * 9 + p2.x] = 0
            sudoku[p.y * 9 + p.x] = 0
            p2.value = 0
            pointList.append(p2)
        else:
            pass
 
 
def check(p, sudoku):
    if p.value == 0:
        print('not assign value to point p!!')
        return False
    if p.value not in rowNum(p, sudoku) and p.value not in colNum(p, sudoku) and p.value not in blockNum(p, sudoku):
        return True
    else:
        return False
 
 
def showSudoku(sudoku):
    result = []
    for j in range(9):
        for i in range(9):
            result.append(sudoku[j * 9 + i])
            print('%d ' % (sudoku[j * 9 + i]), end='')
        print('')
    return result
 
 
v13 = r"$BPV:ubfYp}]DtN>aT^MGmJQ#*Hr`O'wjic0!hdy{oZz-@n+?&%s_/g<e[W)XUxRFSLRA;.l=CEkvK-(q"
 
 
# def checkformat(myinput=r":u$YBPf2pa]Dt4#QM^H4ic'j0`w2y{d-Zzo2%/n_s@+2<UW)e4AR;F.4=-qEkvC2"):
def checkformat(myinput):
    a3 = []
    i = 0
    j = 0
    k = 0
    strlens = len(myinput)
    while 1:
        tmpchr = myinput[j]
        if ord(tmpchr) > ord('0') and ord(tmpchr) <= ord('9'):
            # break
            if i + ord(tmpchr) == ord('9'):
                i = 0
                k += 9
                j += 1
                if j >= strlens:
                    printf(a3)
                    return 1
                continue
        m = k
        if (k >= 81):
            return 0
        while ord(tmpchr) != ord(v13[m]):
            m += 1
            if (m >= 81):
                return 0
        v9 = m % 9 + 1
        a3.append(v9)
        i += 1
        j += 1
        # if j >= strlens:
        #     print('##',a3)
        #     return 1
    return -1
 
 
DEBUG = True
 
 
def printf(*args):
    if DEBUG:
        print(*args)
 
 
if __name__ == '__main__':
    sudoku = [
        0, 4, 0, 7, 0, 0, 0, 0, 0,
        9, 2, 0, 0, 0, 0, 6, 0, 7,
        8, 3, 0, 0, 0, 5, 4, 0, 0,
        0, 1, 0, 0, 0, 3, 0, 0, 0,
        0, 0, 0, 2, 0, 1, 0, 0, 0,
        0, 0, 0, 5, 0, 0, 0, 4, 0,
        0, 0, 4, 9, 0, 0, 0, 7, 1,
        3, 0, 5, 0, 0, 0, 0, 9, 4,
        0, 0, 0, 0, 0, 8, 0, 6, 0
    ]
    pointList = initPoint(sudoku)
    showSudoku(sudoku)
    print('\n')
    p = pointList.pop()
    tryInsert(p, sudoku)
    result = ret
    #     result="""5 4 6 7 1 9 2 3 8
    # 9 2 1 8 3 4 6 5 7
    # 8 3 7 6 2 5 4 1 9
    # 7 1 8 4 6 3 9 2 5
    # 4 5 3 2 9 1 7 8 6
    # 6 9 2 5 8 7 1 4 3
    # 2 8 4 9 5 6 3 7 1
    # 3 6 5 1 7 2 8 9 4
    # 1 7 9 3 4 8 5 6 2 """.split()
    #     result = list(map(int, result))
    strdata = v13
    printf('#sudoku:', sudoku)
    printf('#result:', result)
    n = 0
    need = []
    my = ''
    currentsize = 0
    for i in range(81):
        if sudoku[i] != result[i]:
            currentsize += 1
            need.append(result[i])
            my += strdata[n * 9 + result[i] - 1]
        if (i + 1) % 9 == 0:
            my += chr(ord('9') - currentsize)
            currentsize = 0
            n += 1
    printf(need)
    r = checkformat(my)
    if r:
        print('checkov flag:\n', my, sep='')
    # from hashlib import md5
    # x=md5(my.encode()).hexdigest()
    # print(x)
    # print('########################')

输出:

0 4 0 7 0 0 0 0 0
9 2 0 0 0 0 6 0 7
8 3 0 0 0 5 4 0 0
0 1 0 0 0 3 0 0 0
0 0 0 2 0 1 0 0 0
0 0 0 5 0 0 0 4 0
0 0 4 9 0 0 0 7 1
3 0 5 0 0 0 0 9 4
0 0 0 0 0 8 0 6 0


5 4 6 7 1 9 2 3 8
9 2 1 8 3 4 6 5 7
8 3 7 6 2 5 4 1 9
7 1 8 4 6 3 9 2 5
4 5 3 2 9 1 7 8 6
6 9 2 5 8 7 1 4 3
2 8 4 9 5 6 3 7 1
3 6 5 1 7 2 8 9 4
1 7 9 3 4 8 5 6 2

use Time: 0.031022 s

#sudoku: [0, 4, 0, 7, 0, 0, 0, 0, 0, 9, 2, 0, 0, 0, 0, 6, 0, 7, 8, 3, 0, 0, 0, 5, 4, 0, 0, 0, 1, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 4, 0, 0, 0, 4, 9, 0, 0, 0, 7, 1, 3, 0, 5, 0, 0, 0, 0, 9, 4, 0, 0, 0, 0, 0, 8, 0, 6, 0]

#result: [5, 4, 6, 7, 1, 9, 2, 3, 8, 9, 2, 1, 8, 3, 4, 6, 5, 7, 8, 3, 7, 6, 2, 5, 4, 1, 9, 7, 1, 8, 4, 6, 3, 9, 2, 5, 4, 5, 3, 2, 9, 1, 7, 8, 6, 6, 9, 2, 5, 8, 7, 1, 4, 3, 2, 8, 4, 9, 5, 6, 3, 7, 1, 3, 6, 5, 1, 7, 2, 8, 9, 4, 1, 7, 9, 3, 4, 8, 5, 6, 2]
[5, 6, 1, 9, 2, 3, 8, 1, 8, 3, 4, 5, 7, 6, 2, 1, 9, 7, 8, 4, 6, 9, 2, 5, 4, 5, 3, 9, 7, 8, 6, 6, 9, 2, 8, 7, 1, 3, 2, 8, 5, 6, 3, 6, 1, 7, 2, 8, 1, 7, 9, 3, 4, 5, 2]
[5, 6, 1, 9, 2, 3, 8, 1, 8, 3, 4, 5, 7, 6, 2, 1, 9, 7, 8, 4, 6, 9, 2, 5, 4, 5, 3, 9, 7, 8, 6, 6, 9, 2, 8, 7, 1, 3, 2, 8, 5, 6, 3, 6, 1, 7, 2, 8, 1, 7, 9, 3, 4, 5, 2]
checkov flag:

 

:u$YBPf2pa]Dt4#QM^H4ic'j0`w2y{d-Zzo2%/n_s@+2<UW)e4AR;F.4=-qEkvC2


[2022夏季班]《安卓高级研修班(网课)》月薪两万班招生中~

收藏
点赞0
打赏
分享
最新回复 (1)
雪    币: 880
活跃值: 活跃值 (361)
能力值: ( LV4,RANK:40 )
在线值:
发帖
回帖
粉丝
System32 活跃值 2021-5-31 11:16
2
0

mark

最后于 2021-5-31 11:18 被System32编辑 ,原因:
游客
登录 | 注册 方可回帖
返回