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

(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')
就可以看到flag了咯!~