走迷宫与数独逆向题目小结

笔记

3DMazeRunning.py

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
from queue import Queue

def bfs(map, start, end):
    # 1. 初始化队列
    q = Queue()
    q.put((start, ""))
    # 2. 开始搜索
    while not q.empty():
        cur, path = q.get()
        # 3. 判断是否到达终点
        if cur == end:
            return path
        # 4. 判断是否越界或者是墙壁
        if cur[0] < 0 or cur[0] >= len(map) or cur[1] < 0 or cur[1] >= len(map[0]) or map[cur[0]][cur[1]] == 1:
            continue
        # 5. 标记为已经走过
        map[cur[0]][cur[1]] = 1
        # 6. 向6个方向扩展
        q.put(((cur[0] - 1, cur[1]), path + "w"))
        q.put(((cur[0] + 1, cur[1]), path + "s"))
        q.put(((cur[0], cur[1] - 1), path + "a"))
        q.put(((cur[0], cur[1] + 1), path + "d"))
        q.put(((cur[0] + 8, cur[1]), path + "u"))
        q.put(((cur[0] - 8, cur[1]), path + "n"))

    # 7. 没有找到路径
    return None


gen = [0x7F, 0x7F, 0x1F, 0xDF, 0xDF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xF1, 0xFF, 0xDF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xC5, 0xDF, 0xDF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFD, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFD, 0xFD, 0xFD, 0xFC, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFE, 0xFE, 0xFC, 0xF9, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFB, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xF8]

map = []
puzzle = [0] * 64 * 8
for i in range(8):
	print("第{}层迷宫：".format(i))
	conut  = 64 * i
	for row in range(8):
		for col in range(8):
			puzzle[8 * row + conut + 7 - col] = (gen[row + conut // 8] >> col) & 1
		map.append(puzzle[8 * row + conut : 8 * row + conut + 8])
	for row in range(8):
		for col in range(8):
			print(puzzle[8 * row + col + conut], end=" ")
		print()

print("路径:", bfs(map, (0, 0), (63, 7)))

笔记

走迷宫脚本.py

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
maze=[] #1是墙 0可走
from hashlib import md5
def finda(d):
    x,y=d[0],d[1]-1
    return (x,y,'a')
def findw(d):
    x,y=d[0]-1,d[1]
    return (x,y,'w')
def finds(d):
    x,y=d[0]+1,d[1]
    return (x,y,'s')
def findd(d):
    x,y=d[0],d[1]+1
    return (x,y,'d')
def find0(d,row,column):
    if d[0]==0:
        t=[finda(d),findd(d),finds(d)]
    elif d[0]==row-1:
        t=[findw(d),finda(d),findd(d)]
    elif d[1]==0:
        t=[findw(d),findd(d),finds(d)]
    elif d[1]==column-1:
        t=[findw(d),finda(d),finds(d)]
    else: t=[findw(d),finda(d),finds(d),findd(d)]
    tmp=[]
    for x,y,r in t:
        if maze[x][y]==0:
            tmp.append((x,y,r))
    return tmp
def get(o,O,row,column):#起点，终点，行，列

    Road = [('', o)]
    while True:
        road=[]
        for (r_pre,d) in Road:
            if d==O:#终点
                print('NSSCTF{'+md5(r_pre.encode()).hexdigest()+'}')
                exit()
            next=find0(d,row,column)
            for x,y,r in next:
                if len(r_pre)>=1:
                    if 'ws'in r_pre[-1]+r or 'sw' in r_pre[-1]+r:
                        continue
                    if 'ad' in r_pre[-1] + r or 'da' in r_pre[-1] + r:
                        continue
                road.append((r_pre+r,(x,y)))
        Road=road
row,column=16,16
maze = [maze[i:i + column] for i in range(0, len(maze), column)]
get((15,1),(13,15),row,column)

做题

[SWPUCTF 2021 新生赛]老鼠走迷宫

python逆向：pyinstxtractor uncompyle6…

简单的走迷宫，但是payload长这样：

sssssddssddssaaaassssddwwddddssssssaawwaassssddssaassddddwwddssddwwwwwwwwaawwddwwwwaaaawwddwwwwddssssddwwwwddddwwddddssaassaassddddssddssaassssssddsssssss

[HUBUCTF 2022 新生赛]help

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
using namespace std;
int map[]={65535,33783,48119,47895,47959,47191,48983,48919,49079,49079,34321,63413,63413,34740,49031,49151},j,tmp;
char output[16][16];
int main(void){
    for(register int i=0;i<16;i++){
        tmp=map[i];
        j=0;
        while(tmp!=0){
            if(tmp&1==1)
                output[i][j]='1';
            else
                output[i][j]='0';
            tmp>>=1,
            j++;
        };
    };
    for(register int i=0;i<16;i++){
        for(register int j=15;j>=0;j--)
            printf("%c,",output[i][j]);
        putchar('\n');
    };
    return 0;
};

这是嫖的wp的跑迷宫脚本：

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
maze=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,0,0,0,0,0,1,1,1,1,1,1,0,1,1,1,
1,0,1,1,1,0,1,1,1,1,1,1,0,1,1,1,
1,0,1,1,1,0,1,1,0,0,0,1,0,1,1,1,
1,0,1,1,1,0,1,1,0,1,0,1,0,1,1,1,
1,0,1,1,1,0,0,0,0,1,0,1,0,1,1,1,
1,0,1,1,1,1,1,1,0,1,0,1,0,1,1,1,
1,0,1,1,1,1,1,1,0,0,0,1,0,1,1,1,
1,0,1,1,1,1,1,1,1,0,1,1,0,1,1,1,
1,0,1,1,1,1,1,1,1,0,1,1,0,1,1,1,
1,0,0,0,0,1,1,0,0,0,0,1,0,0,0,1,
1,1,1,1,0,1,1,1,1,0,1,1,0,1,0,1,
1,1,1,1,0,1,1,1,1,0,1,1,0,1,0,1,
1,0,0,0,0,1,1,1,1,0,1,1,0,1,0,0,
1,0,1,1,1,1,1,1,1,0,0,0,0,1,1,1,
1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
from hashlib import md5
def finda(d):
    x,y=d[0],d[1]-1
    return (x,y,'a')
def findw(d):
    x,y=d[0]-1,d[1]
    return (x,y,'w')
def finds(d):
    x,y=d[0]+1,d[1]
    return (x,y,'s')
def findd(d):
    x,y=d[0],d[1]+1
    return (x,y,'d')
def find0(d,row,column):
    if d[0]==0:
        t=[finda(d),findd(d),finds(d)]
    elif d[0]==row-1:
        t=[findw(d),finda(d),findd(d)]
    elif d[1]==0:
        t=[findw(d),findd(d),finds(d)]
    elif d[1]==column-1:
        t=[findw(d),finda(d),finds(d)]
    else: t=[findw(d),finda(d),finds(d),findd(d)]
    tmp=[]
    for x,y,r in t:
        if maze[x][y]==0:
            tmp.append((x,y,r))
    return tmp
def get(o,O,row,column):#起点，终点，行，列

    Road = [('', o)]
    while True:
        road=[]
        for (r_pre,d) in Road:
            if d==O:#终点
                print('NSSCTF{'+md5(r_pre.encode()).hexdigest()+'}')
                exit()
            next=find0(d,row,column)
            for x,y,r in next:
                if len(r_pre)>=1:
                    if 'ws'in r_pre[-1]+r or 'sw' in r_pre[-1]+r:
                        continue
                    if 'ad' in r_pre[-1] + r or 'da' in r_pre[-1] + r:
                        continue
                road.append((r_pre+r,(x,y)))
        Road=road
row,column=16,16
maze = [maze[i:i + column] for i in range(0, len(maze), column)]
get((15,1),(13,15),row,column)

[GDOUCTF 2023]doublegame

第一步走迷宫，程序还改了地图

第二步逆向找key

[HNCTF 2022 WEEK4]ez_maze

经典走迷宫。

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
maze=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
      1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,
      1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,
      1,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,
      1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,
      1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,
      1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,
      1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,
      1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1,
      1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,
      1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,
      1,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,
      1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,
      1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,
      1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,
      1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,
      1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,
      1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,
      1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,
      1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,1,
      1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,
      1,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,
      1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,
      1,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,
      1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,
      1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1,
      1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,
      1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,1,
      1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,
      1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,
      1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
from hashlib import md5
def finda(d):
    x,y=d[0],d[1]-1
    return (x,y,'a')
def findw(d):
    x,y=d[0]-1,d[1]
    return (x,y,'w')
def finds(d):
    x,y=d[0]+1,d[1]
    return (x,y,'s')
def findd(d):
    x,y=d[0],d[1]+1
    return (x,y,'d')
def find0(d,row,column):
    if d[0]==0:
        t=[finda(d),findd(d),finds(d)]
    elif d[0]==row-1:
        t=[findw(d),finda(d),findd(d)]
    elif d[1]==0:
        t=[findw(d),findd(d),finds(d)]
    elif d[1]==column-1:
        t=[findw(d),finda(d),finds(d)]
    else: t=[findw(d),finda(d),finds(d),findd(d)]
    tmp=[]
    for x,y,r in t:
        print("("+str(x)+","+str(y)+")")
        if maze[x][y]==0:
            tmp.append((x,y,r))
    return tmp
def get(o,O,row,column):#起点，终点，行，列

    Road = [('', o)]
    while True:
        road=[]
        for (r_pre,d) in Road:
            if d==O:#终点
                print('NSSCTF{'+md5(r_pre.encode()).hexdigest()+'}')
                exit()
            next=find0(d,row,column)
            for x,y,r in next:
                if len(r_pre)>=1:
                    if 'ws'in r_pre[-1]+r or 'sw' in r_pre[-1]+r:
                        continue
                    if 'ad' in r_pre[-1] + r or 'da' in r_pre[-1] + r:
                        continue
                road.append((r_pre+r,(x,y)))
        Road=road
row,column=31,31
maze = [maze[i:i + column] for i in range(0, len(maze), column)]
get((1,1),(29,29),row,column)

[GDOUCTF 2023]润！

魔改UPX壳，3D走迷宫8x8x8。

动调找出地图，借用脚本：

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
from queue import Queue

def bfs(map, start, end):
    # 1. 初始化队列
    q = Queue()
    q.put((start, ""))
    # 2. 开始搜索
    while not q.empty():
        cur, path = q.get()
        # 3. 判断是否到达终点
        if cur == end:
            return path
        # 4. 判断是否越界或者是墙壁
        if cur[0] < 0 or cur[0] >= len(map) or cur[1] < 0 or cur[1] >= len(map[0]) or map[cur[0]][cur[1]] == 1:
            continue
        # 5. 标记为已经走过
        map[cur[0]][cur[1]] = 1
        # 6. 向6个方向扩展
        q.put(((cur[0] - 1, cur[1]), path + "w"))
        q.put(((cur[0] + 1, cur[1]), path + "s"))
        q.put(((cur[0], cur[1] - 1), path + "a"))
        q.put(((cur[0], cur[1] + 1), path + "d"))
        q.put(((cur[0] + 8, cur[1]), path + "u"))
        q.put(((cur[0] - 8, cur[1]), path + "n"))

    # 7. 没有找到路径
    return None


gen = [0x7F, 0x7F, 0x1F, 0xDF, 0xDF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xF1, 0xFF, 0xDF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xC5, 0xDF, 0xDF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFD, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFD, 0xFD, 0xFD, 0xFC, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFE, 0xFE, 0xFC, 0xF9, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFB, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xF8]

map = []
puzzle = [0] * 64 * 8
for i in range(8):
	print("第{}层迷宫：".format(i))
	conut  = 64 * i
	for row in range(8):
		for col in range(8):
			puzzle[8 * row + conut + 7 - col] = (gen[row + conut // 8] >> col) & 1
		map.append(puzzle[8 * row + conut : 8 * row + conut + 8])
	for row in range(8):
		for col in range(8):
			print(puzzle[8 * row + col + conut], end=" ")
		print()

print("路径:", bfs(map, (0, 0), (63, 7)))

[MoeCTF 2021]A_game

数独解密、异或。

1
2
3
4
5
s='8291767138932581849755263447186268341129653538127'
data1=[ord(ch)for ch in s]
data2=[0x6B,0x02,0x66,0x70,0x44,0x69,0x7E,0x6E,0x43,0x4A,0x78,0x4A,0x6D,0x60,0x56,0x00,0x51,0x59,0x50,0x43,0x50,0x51,0x6D,0x74,0x02,0x55,0x50,0x52,0x6E,0x6F,0x79,0x40,0x5D,0x4B,0x1E,0x19,0x1C,0x74,0x03,0x54,0x07,0x4C,0x52,0x6A,0x60,0x50,0x58,0x40,0x58]
for i in range(len(data1)):
    print(chr(data1[i]^data2[i]),end='')

[强网杯 2022]easyre

运行，看到图标闪过，动调，把re3文件扒下来。

0x401F2F函数存在主逻辑，即SMC加密，加密函数为0x401BB1，看到为异或加密，找到加密表：

1
2
3
4
5
6
7
import idc
key = {8723: 2533025110152939745, 8739: 5590097037203163468, 8755: 17414346542877855401, 8771: 17520503086133755340, 8787: 12492599841064285544, 8803: 12384833368350302160, 8819: 11956541642520230699, 8835: 12628929057681570616, 8851: 910654967627959011, 8867: 5684234031469876551, 8883: 6000358478182005051, 8899: 3341586462889168127, 8915: 11094889238442167020, 8931: 17237527861538956365, 8947: 17178915143649401084, 8963: 11176844209899222046, 8979: 18079493192679046363, 8995: 7090159446630928781, 9011: 863094436381699168, 9027: 6906972144372600884, 9043: 16780793948225765908, 9059: 7086655467811962655, 9075: 13977154540038163446, 9091: 7066662532691991888, 9107: 15157921356638311270, 9123: 12585839823593393444, 9139: 1360651393631625694, 9155: 2139328426318955142, 9171: 2478274715212481947, 9187: 12876028885252459748, 9203: 18132176846268847269, 9219: 17242441603067001509, 9235: 8492111998925944081, 9251: 14679986489201789069, 9267: 13188777131396593592, 9283: 5298970373130621883, 9299: 525902164359904478, 9315: 2117701741234018776, 9331: 9158760851580517972}
for addr in range(0x2213,9331+16,16):
    data = get_qword(addr)
    key1 = key[addr]
    dec = data ^ key1
    idc.patch_qword(addr, dec)

在re3中运行该脚本patch掉re3，逻辑比较难发现，为数织游戏。

两个盒分别导出，塞到这里：https://handsomeone.github.io/Nonogram/#solver。

[长安杯 2021学生组]snake

第一个点在0x14F4处，改为jnz。改之前为碰到“$”才算下一关，改之后走一步就算过。

第二个点在0x158B处，改为jz，show_score意味着结束。

然后他会一关一关跑，当正好碰到“$”时会停下来。因为初始化后蛇是横着的，左右走不好说，一般选择上下走。