2018 SUCTF magic

当时做题的时候得到的式子：

（m[0] & key） % 2 == ？

（m[1] & key） % 2 == *

其中？和 * 很明显，不是0就是1啊！所以不妨换一种思路，如果我们把m和key都转化为二进制数，会发生什么！

M表示m展开后的矩阵，K表示key展开之后的向量，C为cipher.txt转成的01向量，即有：MK = C

矩阵乘法！二进制下的！也就是说，在有限域GF(2)中，有已知的矩阵M和密文C，要求密钥K！

答案是：高斯消元

题解地址：

https://www.xctf.org.cn/library/details/2ff21f569a791e21cbd6ce0d4675a9de5ec2373a/

https://findneo.tech/180527suctf/#Magic

第二篇wp的写法姿势特别好：（论算法的重要性）

翻译一下这行代码：

read_to_int_array = lambda x:[map(int,list(bin(int(line,16))[2:].zfill(dim))) for line in open(x).readlines()]

举例：

s = "e6aec69625130b77330f5b5abaf4155c862b625dce1bbfbd3fb54ea3d914b91"
print int(s,16)
print bin(int(s,16))
print bin(int(s,16))[2:]
print bin(int(s,16))[2:].zfill(dim)
print list(bin(int(s,16))[2:].zfill(dim))
print map(int,list(bin(int(s,16))[2:].zfill(dim)))

结果是这样的：

6521297322318485135397962758917330134336256120928714851050733785157196663697
0b111001101010111011000110100101100010010100010011000010110111011100110011000011110101101101011010101110101111010000010101010111001000011000101011011000100101110111001110000110111011111110111101001111111011010101001110101000111101100100010100101110010001
111001101010111011000110100101100010010100010011000010110111011100110011000011110101101101011010101110101111010000010101010111001000011000101011011000100101110111001110000110111011111110111101001111111011010101001110101000111101100100010100101110010001
0000111001101010111011000110100101100010010100010011000010110111011100110011000011110101101101011010101110101111010000010101010111001000011000101011011000100101110111001110000110111011111110111101001111111011010101001110101000111101100100010100101110010001
['0', '0', '0', '0', '1', '1', '1', '0', '0', '1', '1', '0', '1', '0', '1', '0', '1', '1', '1', '0', '1', '1', '0', '0', '0', '1', '1', '0', '1', '0', '0', '1', '0', '1', '1', '0', '0', '0', '1', '0', '0', '1', '0', '1', '0', '0', '0', '1', '0', '0', '1', '1', '0', '0', '0', '0', '1', '0', '1', '1', '0', '1', '1', '1', '0', '1', '1', '1', '0', '0', '1', '1', '0', '0', '1', '1', '0', '0', '0', '0', '1', '1', '1', '1', '0', '1', '0', '1', '1', '0', '1', '1', '0', '1', '0', '1', '1', '0', '1', '0', '1', '0', '1', '1', '1', '0', '1', '0', '1', '1', '1', '1', '0', '1', '0', '0', '0', '0', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1', '1', '1', '0', '0', '1', '0', '0', '0', '0', '1', '1', '0', '0', '0', '1', '0', '1', '0', '1', '1', '0', '1', '1', '0', '0', '0', '1', '0', '0', '1', '0', '1', '1', '1', '0', '1', '1', '1', '0', '0', '1', '1', '1', '0', '0', '0', '0', '1', '1', '0', '1', '1', '1', '0', '1', '1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '1', '0', '1', '0', '0', '1', '1', '1', '1', '1', '1', '1', '0', '1', '1', '0', '1', '0', '1', '0', '1', '0', '0', '1', '1', '1', '0', '1', '0', '1', '0', '0', '0', '1', '1', '1', '1', '0', '1', '1', '0', '0', '1', '0', '0', '0', '1', '0', '1', '0', '0', '1', '0', '1', '1', '1', '0', '0', '1', '0', '0', '0', '1']
[0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1]

转为10进制，再转为二进制，去掉前面的0b，然后补全256位，再拆开成256个0或1，拼到另外一个list中

接下来就是处理高斯消元了

dim = 256
read_to_int_array = lambda x:[map(int,list(bin(int(line,16))[2:].zfill(dim))) for line in open(x).readlines()]
cipher = read_to_int_array('cipher.txt')[0]
magic = read_to_int_array('magic.txt')

'''
s = "e6aec69625130b77330f5b5abaf4155c862b625dce1bbfbd3fb54ea3d914b91"
print int(s,16)
print bin(int(s,16))
print bin(int(s,16))[2:]
print bin(int(s,16))[2:].zfill(dim)
print list(bin(int(s,16))[2:].zfill(dim))
print map(int,list(bin(int(s,16))[2:].zfill(dim)))
'''

for j in range(dim):
	for i in range(j,dim):
		if magic[i][j] == 1:
			magic[i],magic[j] = magic[j],magic[i]
			cipher[i],cipher[j] = cipher[j],cipher[i]
			break
	for i in range(dim):
		if magic[i][j] == 1 and i != j:
			for k in range(dim):
				magic[i][k] ^= magic[j][k]
			cipher[i] ^= cipher[j]

print "flag{%s}"%hex(int(''.join(map(str,cipher)),2))[2:-1].decode('hex')