[2018看雪] - 第七题 - 有限域数学变换

在之前插播一个数学知识：

一个在素数p下的有限域：GF(p) = {0,1,2,3,……,p-1}，加法运算是模p加，乘法运算是模p乘

数学上可以证明对于在GF(p)中的每一个元素都存在加法逆元和乘法逆元，因此是可以做四则运算的

加法 = 加法，减法 = 加上加法逆元，乘法 = 乘法，除法 = 乘以乘法逆元

在有限域里，会出现特殊的“循环”的现象：

任意一个数x属于GF(p)，一直加上某个数y，加p次后一定会回到x

举例如下：令p = 7，x = 3，y = 4

GF(p) = {0,1,2,3,4,5,6}，当x = 3，y = 4时，我们产生的数列会是3，0，4，1，5，2，6，3，……（7次一定返回）

知道这个数学特点，理解之后的官方wp比较好懂

贴几个链接：

https://bbs.pediy.com/thread-229393.htm

https://bbs.pediy.com/thread-229412.htm

自己在比赛的时候根据题目提示读明白了题，但是没想明白怎么做，赛后来复现

main中逻辑很简单，进入401050中，一堆赋值先不管，接下来是判断输入合法性（是否为字母加数字）

接下来这个循环理解很精髓，看图：

根据题目提示，每个人都会在其他两个人的帮助下去上楼，意思是说，（i，j，k）这个变化是有规律的，而且循环次数告诉我们，确实走了这么多层，之后进行的是正确性检查

所以，之前的赋值我们要去搞明白上楼该怎么理解

OD中下断，发现是在堆栈里赋值，观察之后发现连续四个DWORD之中只会出现3个1

16 * 16的表格，每行3个1，即3个有用的数据

然后回头看byte_40FEF0，这个数组大小为 262144 = 64 * 64 * 64，翻一翻数据，值为0 - 0x40

即（i，j，k）坐标控制字符在[0,0x3F]内变换

根据这样的规则变换20次，然后check一下，且中间有某个值会是正确性的显示，知道有限域的数学结论，所以可以大胆猜想，既然输入可以得到flag，flag在相同变换规则下，也可以得到输入

变换规则相同，数据会是一个循环，只是什么时候会出现相同数据我们不知道（也就是有限域中数据的个数不定）

#coding:utf-8
p = open('./Escape.exe','rb')
s = p.read()
p.close()
change_table = []
#offset = fef0 - e4f0, just find data in Winhex
for i in s[0xe4f0:0xe4f0 + 262144]:
	change_table.append(ord(i))
#print change_table[0:0x40]

result = []
#for i in s[0xfee0 - 0x1a00:0xfee0  -0x1a00 + 16]:
for i in s[0xe4e0:0xe4e0 + 16]:
	result.append(ord(i))
#print result

def reverse(num):
	i = num / (64 * 64)
	j = (num / 64) % 64
	k = num % 64
	return [i,j,k]

def realnum(i,j,k):
	return 64 * 64 * i + 64 * j + k

def con(n):
	ch = 'abcdefghijklmnopqrstuvwxyz+-ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'
	data = []
	for i in range(len(n)):
		for j in range(len(ch)):
			if n[i] == ch[j]:
				data.append(j)
				break
	return data

def recon(n):
	s = ''
	ch = 'abcdefghijklmnopqrstuvwxyz+-ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'
	for i in n:
		s += ch[i]
	return s

def encrypt(n):
    data=[]
    data.append(change_table[realnum(n[0x0],n[0x1],n[0x2])])
    data.append(change_table[realnum(n[0x3],n[0x4],n[0x0])])
    data.append(change_table[realnum(n[0x5],n[0x6],n[0x0])])
    data.append(change_table[realnum(n[0x5],n[0x7],n[0x1])])
    data.append(change_table[realnum(n[0x4],n[0x6],n[0x1])])
    data.append(change_table[realnum(n[0x8],n[0x2],n[0x3])])
    data.append(change_table[realnum(n[0x9],n[0x2],n[0x4])])
    data.append(change_table[realnum(n[0x7],n[0xa],n[0x3])])
    data.append(change_table[realnum(n[0x8],n[0xc],n[0x5])])
    data.append(change_table[realnum(n[0xb],n[0xd],n[0x6])])
    data.append(change_table[realnum(n[0xc],n[0xd],n[0x7])])
    data.append(change_table[realnum(n[0xb],n[0xe],n[0x9])])
    data.append(change_table[realnum(n[0xe],n[0x8],n[0xa])])
    data.append(change_table[realnum(n[0xf],n[0x9],n[0xa])])
    data.append(change_table[realnum(n[0xf],n[0xb],n[0xc])])
    data.append(change_table[realnum(n[0xf],n[0xd],n[0xe])])
    return data

tmp = result
for i in range(0x500):
	print tmp,recon(tmp)
	tmp = encrypt(tmp)

学到了几种姿势：怎么扣数据，怎么爆破把

把跑出来的结果放到一个txt中，然后搜索下~~