I春秋360_Reverse_登山_Writeup
这个题的Hint：求二维矩阵左上往下走，可以向下，也可以向右下的最大值
（打过ACM的话，就知道是dp的数字三角形模型题）
IDA里静态分析，发现程序逻辑比较简单，先有一个init的初始化函数，然后就是对我们的输入进行check
分析init：
两个for循环得到了一个1014*1014的矩阵，根据我们的hint，这就是我们需要运算的矩阵，所以我们需要构造出矩阵
这儿有个my_rand（）函数，但是没有关系，进去看一下，发现随机种子固定，所以每次生成的都是同一个矩阵
OD中下断点，观察数的变化
根据地址的变化，我们可以算偏移，得到运算完毕之后的结束地址：
所以我们等程序跑完，然后把矩阵从数据窗口扣出来
右键，二进制，二进制复制，然后弄到txt中去
然后就是数据格式处理，需要整理成矩阵的形式，这个没啥特别的，等会有代码，先说逻辑
看到check：
进去就是v6的一个赋值，猜测是矩阵最终的最大值
然后有个getstep，有个map，我们在init里面也看到这个map了，说明输入的字符集合只可能ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/里面，而且顺序已经被打乱，所以我们要弄明白，进入init，有64次打乱，我们只需要知道最终的结果，可以不理会打乱的过程
找到这个地方：
发现与原来字符串不一样了，那么很明显是执行了某种变换操作，那我们让它执行64次，然后把得到的字符串抠出来，得到一个对应关系：
temp = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
string = 'EIFd6gwN42LR1vGrBYCnzHTStDqm+kxZpQVioj9O78es3UlAKhXcfybPM5W/0aJu'
来分析程序逻辑：总共是1014个位，1个字符决定6个01，那么我们的输入长度是1014/6=169个
要逆向得到原来的字符串，首先需要处理矩阵，然后使用dp得到最大值的地方，然后6个01为一组，得到一个字符
先说下dp的理论：（可自行百度：数字三角形dp）
怎么走才是最大：一个位置的最大值，只可能由两个位置过来：上面，或者左上，那么比较一下就好
6个01怎么得到一个字符呢？联想到2的6次方是64正好是0-63的范围，然后看到这个地方：
这个a2是从0到5不断循环的，当a2等于0，就是判断*v2&32，那就是判断*v2有没有32这个位（二进制中2^5这个位）
所以就相当于是判断32，16，8，4，2，1这六个数在不在*v2里面
然后反向查询下
代码如下：
'''
f = open('matrix.txt','r')
a = [[0 for i in range(1020)] for i in range(1020)]
index = 0
while True:
line = f.readline()
line = line.replace(' ','')
line = line.replace('\n','')
s = line[6:8] + line[4:6] + line[2:4] + line[0:2]
a[index/1014][index%1014]=int(s,16)
index += 1
s = line[22:24] + line[20:22] + line[18:20] + line[16:18]
a[index/1014][index%1014]=int(s,16)
index += 1
s = line[38:40] + line[36:38] + line[34:36] + line[32:34]
a[index/1014][index%1014]=int(s,16)
index += 1
s = line[54:56] + line[52:54] + line[50:52] + line[48:50]
a[index/1014][index%1014]=int(s,16)
index += 1
#if index % 100000 == 0:
# print index
if index >= 1014 * 1014:
break
f.close()
dp = [[0 for i in range(1020)] for i in range(1020)]
choose = [[0 for i in range(1020)] for i in range(1020)]
dp[0][0] = a[0][0]
for i in xrange(1,1014):
dp[i][0] = dp[i-1][0] + a[i][0]
for j in xrange(1,i+1):
dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + a[i][j]
if dp[i-1][j-1] > dp[i-1][j]:
choose[i][j] = 1
else:
choose[i][j] = 0
Max = 0
Pos = 0
for i in range(0,1014):
if dp[1013][i] > Max:
Max = dp[1013][i]
Pos = i
print Max
step = [0 for i in range(1020)]
i = 1013
while (i > 0):
step[i] = choose[i][Pos]
Pos -= choose[i][Pos]
i -= 1
for i in range(0,1014):
print step[i],',',
'''
step = [0 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 1 , 0 , 1 , 1 , 0 , 0 , 0 , 1 , 1 , 1 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 0 , 1 , 1 , 1 , 1 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 0 , 1 , 1 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 1 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 1 , 0 , 0 , 1 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 1 , 0 , 1 , 1 , 1 , 0 , 1 , 0 , 1 , 1 , 0 , 0 , 0 , 1 , 0 , 1 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 0 , 0 , 1 , 1 , 1 , 1 , 0 , 1 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 0 , 0 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 1 , 1 , 1 , 0 , 0 , 1 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 1 , 1 , 0 , 1 , 0 , 0 , 1 , 1 , 1 , 0 , 1 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 , 1 , 0 , 1 , 1 , 1 , 1 , 1 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 0 , 1 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 1 , 1 , 0 , 1 , 1 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 1 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 0 , 0 , 0 , 1 , 1 , 1 , 0 , 1 , 0 , 1 , 1 , 0 , 0 , 1 , 0 , 1 , 0 , 1 , 1 , 1 , 0 , 1 , 0 , 1 , 0 , 0 , 1 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 1 , 1 , 0 , 1 , 1 , 1 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 0 , 1 , 1 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , 0 , 1 , 1 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 1 , 1 , 0 , 0 , 1 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 1 , 0 , 1 , 1 , 0 , 1 , 1 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 1 , 1 , 1 , 0 , 1 , 1 , 1 , 0 , 1 , 1 , 1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 1 , 1 , 0 , 1 , 0 , 1 , 1 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 0 , 1 , 0 , 0 , 1 , 1 , 1 , 1 , 0 , 1 , 1 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 1 , 0 , 0 , 1 , 1 , 1 , 1 , 0 , 0 , 1 , 0 , 1 , 0 , 1 , 1 , 1 , 1 , 0 , 0 , 1 , 0 , 1 , 1 , 1 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , 0 , 1 , 0 , 1 , 1 , 0 , 1 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 1 , 0 , 0 , 1 , 0 , 1 , 1 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 1 , 0 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 1 , 0 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 0 , 1 , 0 , 1 , 1 , 1 , 1 , 0 , 0 , 0 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 1 , 1 , 0 , 1 , 1 , 1 , 1 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 0 , 0 , 1 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 1 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 1 , 1 , 0 , 1 , 1 , 1 , 0 , 1 , 0 , 1 , 1 , 0 , 1 , 0 , 0 , 1 , 0]
print len(step)
temp = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
num = [0x2f,0x10,0x12,0x19,0,0x2,0xE,0x15,0x1,0x3E,0x30,0x0A,0x38,0x7,0x27,0x37,
0x21,0x0B,0x17,0x16,0x2D,0x22,0x3A,0x32,0x11,0x1F,0x3D,0x36,0x33,0x3,0x2A,
0x34,0x05,0x31,0x23,0x25,0x1D,0x2E,0x1B,0x13,0x24,0x20,0x1A,0x0F,0x2B,0x18,
0x3F,0x0D,0x06,0x1E,0x35,0x14,0x3C,0x0C,0x09,0x2C,0x08,0x39,0x04,0x28,0x29,
0x26,0x1C,0x3B]
flag = ''
for i in range(0,1014,6):
number = step[i] * 32 + step[i+1] * 16 + step[i+2] * 8 + step[i+3] * 4 + step[i+4] * 2 + step[i+5]
for pos in range(0,64):
if number==num[pos]:
flag += temp[pos]
print flag
string = 'EIFd6gwN42LR1vGrBYCnzHTStDqm+kxZpQVioj9O78es3UlAKhXcfybPM5W/0aJu'
print hex(string.find('A'))
腾讯二面846人在聊
查看18道真题和解析
