从部分已知序列求解m位LFSR初始状态：可行性与高效方法问询

可行性分析 #

当LFSR的反馈多项式已知时，完全可以从部分生成序列反推出初始状态。只要已知序列包含连续的m位输出（m为LFSR位数），即可通过建立线性方程组求解；序列长度越长，求解结果的可靠性越高（可做冗余验证）。

最小序列长度 #

对于m位LFSR，所需已知序列的最小长度为m位连续输出。初始状态是m维向量，对应m个未知数，通过m位输出可建立m个线性无关的方程，足以唯一解出初始状态（前提是反馈多项式为非退化多项式，示例中的多项式满足该条件）。

求解思路 #

1. 转换反馈多项式为递推关系：示例中反馈多项式为$x^{16}+x{12}+x^3+x+1$，对应模2下的递推关系为：
   $$s_n = s_{n-16} \oplus s_{n-15} \oplus s_{n-13} \oplus s_{n-4}$$
   其中$s_n$是LFSR的第n位状态，输出序列的第k位$b_k = s_{k+15}$（初始状态为$s_0$到$s_{15}$，第一个输出为$s_{15}$）。
2. 构造线性方程组：从已知序列中取连续m位输出，代入递推关系得到关于初始状态的线性方程组。
3. 模2高斯消元求解：在二进制域内通过高斯消元法解方程组，得到初始状态。

Python实现代码 #

import numpy as np

def solve_lfsr_init_state(seq_str, m, taps):
    """
    从LFSR生成序列求解初始状态
    参数:
        seq_str: 已知二进制序列字符串（仅含'0'和'1'）
        m: LFSR的位数
        taps: 反馈多项式的非零项指数（最高次为m，如[16,12,3,1]对应x^16+x^12+x^3+x+1）
    返回:
        初始状态字符串（长度为m，由'0'和'1'组成）
    """
    # 将序列转换为二进制数组（模2）
    seq = np.array([int(c) for c in seq_str], dtype=np.int8)
    if len(seq) < m:
        raise ValueError(f"序列长度不足，至少需要{m}位连续序列")
    
    # 构造系数矩阵A和常数项向量b（模2）
    A = np.zeros((m, m), dtype=np.int8)
    b = np.zeros(m, dtype=np.int8)
    
    # 根据反馈多项式构造方程组：b[k+1] = 初始状态对应位的异或
    for k in range(m):
        b[k] = seq[k+1] if (k+1) < len(seq) else 0
        # 对应多项式中的非零项（除最高次外）
        for tap in taps[1:]:
            pos = tap - 1  # 转换为0-based索引
            if k + (m - tap) < m:
                A[k][k + (m - tap)] = 1
        # 对应最高次项的系数
        A[k][k] = 1
    
    # 模2下的高斯消元法
    def gauss_jordan_mod2(matrix, vector):
        n = len(vector)
        for i in range(n):
            # 寻找主元行
            pivot_row = i
            while pivot_row < n and matrix[pivot_row][i] == 0:
                pivot_row += 1
            if pivot_row == n:
                raise ValueError("方程组无解，序列与反馈多项式不匹配")
            
            # 交换主元行与当前行
            matrix[[i, pivot_row]] = matrix[[pivot_row, i]]
            vector[[i, pivot_row]] = vector[[pivot_row, i]]
            
            # 消去其他行的当前列
            for j in range(n):
                if j != i and matrix[j][i] == 1:
                    matrix[j] ^= matrix[i]
                    vector[j] ^= vector[i]
        return vector
    
    # 求解方程组
    init_bits = gauss_jordan_mod2(A, b)
    return ''.join(str(bit) for bit in init_bits)

# 示例测试
if __name__ == "__main__":
    input_seq = '0010100010000110010011100011100100001000110111000000011010001001100101110101001100000011111010111000100001101011101011011011101111110000000001111111010010110100001011000101011111100110101010001110000000'
    lfsr_m = 16
    feedback_taps = [16, 12, 3, 1]
    
    init_state = solve_lfsr_init_state(input_seq, lfsr_m, feedback_taps)
    print("求解得到的初始状态:", init_state)
    
    # 验证结果正确性
    import pylfsr
    lfsr = pylfsr.LFSR(fpoly=feedback_taps, initstate=init_state)
    generated_seq = lfsr.runKCycle(len(input_seq))
    generated_seq_str = lfsr.arr2str(generated_seq)
    print("序列匹配验证:", generated_seq_str == input_seq)

代码说明 #

1. 模2高斯消元：手动实现二进制域内的高斯消元，确保线性方程组求解符合LFSR的运算规则。
2. 输入校验：检查序列长度是否满足最小要求，避免无解场景。
3. 结果验证：通过pylfsr生成对应初始状态的序列，与输入序列对比，验证求解结果的正确性。

内容的提问来源于stack exchange，提问作者VComm