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

2021-5-15 11:41 8612

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

堂前燕

2021-5-15 11:41

8612

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

程序流程

main 函数

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

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

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

[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界

收藏・2

点赞・1

打赏

最新回复 (1)
System32 雪币： 546 活跃值： (539) 能力值： ( LV4，RANK：40 ) 在线值：发帖 14 回帖 27 粉丝 1 关注私信	System32 2021-5-31 11:16 2 楼 0 mark 最后于 2021-5-31 11:18 被System32编辑，原因：
	游客登录 \| 注册方可回帖　回帖　表情雪币赚取及消费高级回复