书接上文LFSR(一)，这里主要来介绍一下B-M算法

B-M算法：

如果我们已知长度为2n的输出序列，那么就可以通过构造矩阵来求出mask
$$
但是其实如果我们知道了长度为2n的序列，我们也可以用一种比较笨的方法来获得原来的序列。\
不妨假设已知序列为a_1,a_2,…,a_{2n},我们可以令\
S_1\ =\ (a_1,…,a_n)\
S_2\ =\ (a_2,…,a_{n+1})\
.\
.\
.\
S_{n+1}\ =\ (a_{n+1},…,a_{2n})\
那么我们可以构造矩阵X\ =\ (S_1,…,S_n),那么\
S_{n+1}\ =\ (c_n,…,c_1)X\
所以\ (c_n,…,c_1)\ =\ S_{n+1}X^{-1}\
进而我们也就知道了LFSR的反馈表达式，进而我们就可以推出初始化种子
$$

2018 CISCN 初赛 oldstreamgame

给出相应的B-M算法：

#Sage
mask = '10100100000010000000100010010100'
key = '00100000111111011110111011111000'

N = 32
F = GF(2)

R = [vector(F,N) for i in range(N)]
for i in range(N):
    R[i][N-1] = mask>>(31-i) & 1
for i in range(N-1):
    R[i+1][i] = 1
M = Matrix(F,R)
M = M ^ N

vec = vector(F,N)
row = 0
for i in range(N/8):
    t = ord(key[i])
    for j in xrange(7,-1,-1):
        vec[row] = t>>j & 1
        row += 1
print(rank(M))

num = int(''.join(map(str,list(M.solve_left(vec)))),2)
print(hex(num))

接下来我们来看一到专为B-M算法出的题目吧

[De1CTF2019]Babylfsr：

import hashlib
from secret import KEY,FLAG,MASK

assert(FLAG=="de1ctf{"+hashlib.sha256(hex(KEY)[2:].rstrip('L')).hexdigest()+"}")
assert(FLAG[7:11]=='1224')

LENGTH = 256

assert(KEY.bit_length()==LENGTH)
assert(MASK.bit_length()==LENGTH)

def pad(m):
    pad_length = 8 - len(m)
    return pad_length*'0'+m

class lfsr():
    def __init__(self, init, mask, length):
        self.init = init
        self.mask = mask
        self.lengthmask = 2**(length+1)-1

    def next(self):
        nextdata = (self.init << 1) & self.lengthmask 
        i = self.init & self.mask & self.lengthmask 
        output = 0
        while i != 0:
            output ^= (i & 1)
            i = i >> 1
        nextdata ^= output
        self.init = nextdata
        return output


if __name__=="__main__":
    l = lfsr(KEY,MASK,LENGTH)
    r = ''
    for i in range(63):
        b = 0
        for j in range(8):
            b = (b<<1)+l.next()
        r += pad(bin(b)[2:])
    with open('output','w') as f:
        f.write(r)

# output = 001010010111101000001101101111010000001111011001101111011000100001100011111000010001100101110110011000001100111010111110000000111011000110111110001110111000010100110010011111100011010111101101101001110000010111011110010110010011101101010010100101011111011001111010000000001011000011000100000101111010001100000011010011010111001010010101101000110011001110111010000011010101111011110100011110011010000001100100101000010110100100100011001000101010001100000010000100111001110110101000000101011100000001100010

1	len(output) = 504

题中的输出序列大小为504bit，而根据B-M算法，我们需要确定512bit(即长度为2n的序列，n为lfsr的度，此处为256)才能求出mask，

先考虑如何推出掩码，由于lfsr的性质，每一次生成的bit都会加到向量的最低位，同时丢弃掉最高位那个bit，于是在连续256次生成之后，原有的key所有的位都被丢弃了，lfsr的状态会转为我们已知的256个bit——也就是题目所给出的串的前256位。从此之后，我们完全知道了lfsr的状态，只需要在已知状态的情况下推出掩码。

每连续256个bit可以生成下一个bit，我们知道这256个bit，也知道下一个bit，但我们不知道掩码。

目前面临的问题等价于：在GF(2)上，256位的已知的状态向量，点乘上256位的掩码向量，得到的数已知。现在求掩码向量

上面是一个方程，而状态向量有256维，我们需要256组方程才能解出整个掩码向量。但我们现在只有504 - 256 = 248个方程可用，显然秩是不够用的。

容易想到，直接猜测lfsr此后生成的8个bit，于是就有了256组方程了；当然求出的答案只有一条为正解，我们只需要逐一筛选即可

解方程组的问题可以转化为矩阵求逆的问题，把lfsr的状态一行一行地写在矩阵上，形成的矩阵记为M，把lfsr每次所生成的结果也拼成一个向量，记为T，那么掩码向量v使得：

$$
M·v\ =\ T
$$

于是两边左乘M^-1^，可以得到掩码向量：
$$
v\ =\ M^{-1}·T
$$

爆破掩码的脚本如下：

def test(padding):
    s = [int(x) for x in '001010010111101000001101101111010000001111011001101111011000100001100011111000010001100101110110011000001100111010111110000000111011000110111110001110111000010100110010011111100011010111101101101001110000010111011110010110010011101101010010100101011111011001111010000000001011000011000100000101111010001100000011010011010111001010010101101000110011001110111010000011010101111011110100011110011010000001100100101000010110100100100011001000101010001100000010000100111001110110101000000101011100000001100010'] + padding
	M = matrix(GF(2),256,256)
    T = vector(GF(2),256)
    
    for i in range(len(s)-256):
        M[i] = s[i:i+256]
        T[i] = s[i+256]
        
    try:
        mask = M.inverse() * T
        print(hex(int(''.join(map(str,(mask))),base = 2)))
    except:
        return
for x in itertools.product([0,1],repeat = 8):
    test(list(x))

接下来考虑求出初始状态 KEY. 我们目前有的东西是：（猜测的）连续 512 个 lfsr 输出，以及与之对应的掩码。注意到第 256 个输出，是由 KEY 的末位，拼接上前 255 个输出所形成的；第 255 个输出，是由 KEY 的倒数两位，拼接上前 254 个输出所形成的。我们可以先求出 KEY 的末位，再求出倒数第二位……以此类推，整个 key 就求出来了。

完整脚本：

import itertools,hashlib,numpy as np

def int2bin(a,n):
    assert 0<= n and a<2**n
    res = np.zeros(n,dtype = int)
    
    for x in range(n):
        res[n-x-1] = a % 2
        a = a // 2
    return res.tolist()

def bin2int(a):
    return reduce(lambda x,y: x*2+y , a)

def bitAnd(a,b):
    assert len(a) == len(b)
    return list(map(lambda x,y: int(x)&int(y),a,b))

def test(padding):
    s = [int(x) for x in '001010010111101000001101101111010000001111011001101111011000100001100011111000010001100101110110011000001100111010111110000000111011000110111110001110111000010100110010011111100011010111101101101001110000010111011110010110010011101101010010100101011111011001111010000000001011000011000100000101111010001100000011010011010111001010010101101000110011001110111010000011010101111011110100011110011010000001100100101000010110100100100011001000101010001100000010000100111001110110101000000101011100000001100010'] + padding
    M = matrix(GF(2),256,256)
    T = vector(GF(2),256)
    
    for i in range(len(s)-256):
        M[i] = s[i:i+256]
        T[i] = s[i+256]
        
    try:
        mask = M.inverse() * T
        print(hex(int(''.join(map(str,(mask))),base = 2)))
    except:
        return
	
    suf = []
    for i in range(256):
        if bitAnd([0]+suf+s[0:255-i],mask).count(1)%2 == s[255-i]:
            suf = [0] + suf
        else:
            suf = [1] + suf
    
    key = hex(bin2int(suf))[2:]
    sha = hashlib.sha256(key.encode()).hexdigest()
    
    if sha[:4] == '1224':
        print('de1ctf{'+ sha +'}')
        
for x in itertools.product([0,1],repeat = 8):
    test(list(x))

得到flag:de1ctf{1224473d5e349dbf2946353444d727d8fa91da3275ed3ac0dedeb7e6a9ad8619}

感谢：ruanx永远滴神