从部分已知序列中寻找LFSR的初始状态

Question

有没有更快的方法（或者说是否可能）来找到m位LFSR的初始状态，如果我知道生成序列的一部分呢？

举个例子：假设m=16，反馈多项式是x^16 + x^12 + x^3 + x^1 + 1，而已知的序列部分是'0010100010000110010011100011100100001000110111000000011010001001100101110101001100000011111010111000100001101011101011011011101111110000000001111111010010110100001011000101011111100110101010001110000000'

我们能找到LFSR的初始状态吗？如果可以，所需的已知序列的最小长度是多少？

上面的例子中，初始状态全是1，并且是通过以下方式生成的：

import pylfsr
L1 = pylfsr.LFSR(fpoly=[16,12,3,1], initstate='ones')
seq = L1.runKCycle(2**16)
seq = L1.arr2str(seq)

我希望：我希望任何知道如何编写程序和代码的人能帮我找到初始状态。

Answer 1

原则上这是可能的。你可以查看这个链接了解更多信息：https://en.wikipedia.org/wiki/Berlekamp–Massey_algorithm。如果想要更详细的背景知识，可以参考这个链接：https://crypto.stackexchange.com/questions/16203/berlekamp-massey-to-construct-minimal-lfsr。

在Python中，你可以根据观察到的比特位，建立一个合适的线性方程组，然后使用像z3-solver这样的工具来尝试解决它们。

这里有一种方法，使用pylfsr来进行初始的“秘密”设置，并使用在https://github.com/thewhiteninja/lfsr-berlekamp-massey中实现的LFSR类。请注意，BerlekampMassey类并不知道你的多项式。如果你有这个信息，那么重建初始状态（或者一个可能生成与原始初始状态相同序列的状态）会更容易。

import pylfsr

L1 = pylfsr.LFSR(fpoly=[16,12,3,1], initstate="ones")
print("Initial state:", L1.initstate)
    
seq = L1.runKCycle(2**16)
bits = L1.arr2str(seq)
print("Bits:", bits[:256], "...")
    
bm = BerlekampMassey(bytes_to_bin(bits[:17]))
poly2 = LFSR(bm.get_polynomial(), 
             bytes_to_bin(bits)[:bm.get_polynomial_degree()])
    
bits = "".join([chr(poly2.next_byte()) for _ in range(16)])
print("LFSR initialstate    :", bits)

如果初始状态全是1，那么在这种情况下，你只需要17个比特位。 如果是随机的，你可能需要更多的观察比特位。我不知道具体需要多少。