d3ctf-LFSR

2022-03-10

由于异或的可逆性和相消性，推到可以得到message的前34位就是myResult的1-35位，而剩余30位未知，就可以利用矩阵方程组来解。

from Crypto.Util.number import *
from sage.all import *
from functools import reduce

def xor(a,b):
    return a^b

def right_reduce(a,b):
    return reduce(xor,[ a[i]&b[i] for i in range(len(a))])

mask = '1010010000001000000010001001010010100100000010000000100010010100'
xor_output = '00100110001000110001101010101001001'
and_output = '01111101111010111000010010111001101'
message = ''
#可以证明，message的前34位就是xor_output的1-34位
for i in range(1,35):
    message += str(int(xor_output[i]))

and_output=and_output[:-5]
#矩阵方程等号左边系数矩阵
r_and=[int(i) for i in and_output]
r_xor=[int(i) for i in xor_output[1:35]]
A = [int(i) for i in mask[34:]]
AA = []
for i in range(30):
    A = [int(i) for i in mask[(34-i):(64-i)]]
    AA.append(A)
print(AA)
AA=matrix(GF(2),AA)

r = []
for i in range(30):
    a = [r_xor[j] for j in range(i,34)]
    b = [int(mask[k]) for k in range(0,34-i)]
    if i == 0:
        c = [0]
        d = [0]
    else:
        c = [r_and[l] for l in range(0,i)]
        d = [int(mask[p]) for p in range(63,63-i,-1)]
    r.append(right_reduce(a,b) ^ right_reduce(c,d) ^ r_and[i])

rr =  vector(GF(2),r)
print(rr)
ans = AA.solve_right(rr)
print(ans)

ans = list(ans)
low_bit = ''
for i in ans:
    low_bit += str(i)
message = message + low_bit
print(long_to_bytes(int(message,2)))
#LF5Rsuk!