注意：此方法很暴力！

这道题，逆向起来逻辑其实很简单，但是，难算……回去要好好学一学算法了……

逆向

程序的逻辑非常简单，程序将输入映射为0-63的数字，按确定的次序去查一个646464的三维数组，类似于M[a0][a1][a2] = b1这样的规律，顺序可以经过动态调试提取出来：

pos = [[0, 1, 2], [3, 4, 0], [5, 6, 0], [5, 7, 1], [4, 6, 1], [8, 2, 3], [9, 2, 4], [7, 10, 3], [8, 0xC, 5], [0xB, 0xD, 6], [0xC, 0xD, 7], [0xB, 0xE, 9], [0xE, 0x8, 0xA], [0xF, 0x9, 0xA], [0xF, 0xB, 0xC], [0xF, 0xD, 0xE]]

查完一轮以后，将这次的结果作为下一轮的输入，这样重复查20轮，最后和一个固定数组进行比较。

计算

三维的表反查是比较困难的，因为每一个数字都出现了64*64次，而且输入中的一字节会和输出的三字节有关，同理输出相对输入也是一样。我首先的想法是暴力搜索，但是64^16的复杂度有点太高了。然后尝试数学拟合那个表的函数，搞了七八个小时都没搞出来……还是尝试搜索，发现可以剪枝，先找每一位出现的最后位置，再生成一个数组，表示确定这一位的搜索范围最多到多少，然后……暴力DFS……

脚本

s = [......]  # 64*64*64的表格

pos = [[0, 1, 2], [3, 4, 0], [5, 6, 0], [5, 7, 1], [4, 6, 1], [8, 2, 3], [9, 2, 4], [7, 10, 3], [8, 0xC, 5], [0xB, 0xD, 6], [0xC, 0xD, 7], [0xB, 0xE, 9], [0xE, 0x8, 0xA], [0xF, 0x9, 0xA], [0xF, 0xB, 0xC], [0xF, 0xD, 0xE]]


correct = [
  0x14, 0x22, 0x1E, 0x10, 0x38, 0x30, 0x18, 0x10, 0x04, 0x1A, 
  0x24, 0x08, 0x02, 0x26, 0x38, 0x2A
]

chars = [
  0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 0x68, 0x69, 0x6A, 
  0x6B, 0x6C, 0x6D, 0x6E, 0x6F, 0x70, 0x71, 0x72, 0x73, 0x74, 
  0x75, 0x76, 0x77, 0x78, 0x79, 0x7A, 0x2B, 0x2D, 0x41, 0x42, 
  0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4A, 0x4B, 0x4C, 
  0x4D, 0x4E, 0x4F, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 
  0x57, 0x58, 0x59, 0x5A, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 
  0x36, 0x37, 0x38, 0x39, 0x00
]

def get_xyz(x, y, z):
    return s[64 * 64 * x + 64 * y + z]

current = list(correct)
prev = [0] * 16

search_range = []

for i in xrange(16):
    search_range.append(max(pos[i][0], pos[i][1], pos[i][2]))
    if (i > 1):
        search_range[i] = max(search_range[i], search_range[i-1])

search_pos = [0] * 16

for i in xrange(16):
    search_pos[search_range[i]] = i + 1

for i in xrange(1, 16):
    search_pos[i] = max(search_pos[i], search_pos[i - 1])

print search_range

print search_pos

def dfs(x):
    if (x and search_pos[x-1] != search_pos[x-2]):
        for i in xrange(search_pos[x - 2], search_pos[x - 1]):
            if (get_xyz(prev[pos[i][0]], prev[pos[i][1]], prev[pos[i][2]]) != current[i]):
                return 0
    if (x == 16):
        return 1
    for i in xrange(64):
        prev[x] = i
        if (dfs(x + 1)):
            return 1
    return 0

for i in xrange(19):
    dfs(0)
    print prev
    current = list(prev)
    prev = [0] * 16

在我的机器上大概20分钟算一组出来……
暴力出来最后需要的数字是

17, 43, 33, 5, 63, 1, 37, 11, 57, 19, 51, 9, 63, 57, 53, 37

换算成字符得到Flag

rPFf9bJl3tXj93ZJ

ps

虽然数学方法没有拟合出来，但是我推出了F(0, y, z)=a满足的关系式：

((y) * (16 * (y % 2) + (1 - 4 * a)) + z0 + (32 * ((1+a) % 4 / 2) + 8) * (y % 2)) % 64 == z

而且这些数字中有着非常不自然的等差关系，猜测出题人的预期解是数学方法？

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