从零到一：用Python实战拆解LFSR序列的脆弱性

如果你刚开始接触网络安全，可能会觉得密码学、加密算法这些概念离实际动手操作有点远。但我想告诉你，理解一个加密系统如何被攻破，往往比单纯学习它的构造更能让你看清安全的本质。今天我们不谈复杂的数学证明，也不讲那些让人望而生畏的理论，我们就从一个在CTF竞赛和实际安全评估中经常遇到的场景开始：当你面对一个使用线性反馈移位寄存器（LFSR）生成的“加密”序列时，如何仅凭一小段已知的明文和密文，就能一步步推导出整个系统的“钥匙”——也就是它的抽头位置和初始状态。

LFSR听起来像是硬件工程师的专属领域，但它在软件实现的伪随机数生成、早期流密码以及一些轻量级的安全协议中仍有踪迹。它的原理简单到令人惊讶，而正是这种简单，在缺乏足够随机性的设计下，会成为整个安全链条中最脆弱的一环。这篇文章，我将带你用Python和Jupyter Notebook，像侦探一样，通过已知明文攻击，亲手还原一次完整的“破译”过程。你会发现，所谓的“加密”，有时只是一层薄薄的窗户纸。

1. 理解目标：LFSR究竟是什么，又为何脆弱？

在开始动手之前，我们得先搞清楚要对付的是什么。线性反馈移位寄存器（Linear Feedback Shift Register, LFSR）本质上是一个状态机。你可以把它想象成一排灯泡（寄存器位），每个时钟周期，所有灯泡的亮灭（0或1）整体向右移动一位。最左边新空出来的那个灯泡的亮灭，则由预先选定的几个特定位置灯泡的当前状态，通过异或（XOR）运算来决定。这几个被选中的位置，就叫做“抽头”（Taps）。

举个例子，假设我们有一个4位的LFSR，抽头位置在第4位和第3位（通常从最右边为第1位开始计数）。那么，在每个时钟周期：

1. 第4位和第3位的值进行异或运算，得到一个新比特。
2. 所有位右移，原来的第3位变成第4位，第2位变成第3位，第1位变成第2位。
3. 第一步计算得到的新比特，填入最左边的第1位。
4. 原来最右边的第1位被移出，通常作为该时刻的输出比特。

这个过程可以用一个简单的特征多项式来表示，比如 x^4 + x^3 + 1，它对应了抽头在第4位和第3位。

LFSR的致命弱点在于它的“线性”。线性意味着它的下一个状态完全由当前状态的线性函数决定（在这里就是异或）。这种确定性带来了两个关键特性：

• 周期性：对于一个n位的LFSR，在非全零种子的情况下，它产生的序列周期最多为 2^n - 1。一旦你观察到的连续输出比特长度超过 2n，理论上你就能建立足够的方程来解出它的结构。
• 可预测性：输出序列中的任意一个比特，都可以表示为初始种子比特的线性组合。这意味着，如果你知道了足够多的连续输出比特，你就能通过解一个线性方程组，反推出抽头的位置（即特征多项式）和初始种子的值。

注意：这里讨论的脆弱性主要针对LFSR单独作为伪随机源或简单流密码的情况。在现代密码学中，LFSR通常会被非线性组合函数、过滤函数或者多个LFSR以更复杂的方式组合使用（如A5/1, E0等），以增强其安全性。但理解基础LFSR的破解，是分析这些更复杂系统的基础。

下面的表格对比了LFSR在理想设计与脆弱实现下的关键区别：

特性	理想/安全的设计考量	脆弱/易受攻击的实现
位数 (n)	足够大（如128位以上），使周期 2^n - 1 在计算上不可遍历。	位数过小（如8位、16位），周期很短，容易通过穷举或观察重复模式发现。
抽头配置	采用本原多项式，确保达到最大长度周期。	使用非本原多项式或随意选择的抽头，可能大幅缩短周期，甚至产生可预测的短循环。
输出使用	仅作为更复杂伪随机数生成器（PRNG）或密码算法的一个内部组件，经过非线性处理。	直接将其输出序列作为密钥流，与明文进行简单的逐比特异或加密。
密钥（种子）	种子是足够长、高熵的真随机数，且定期更换。	种子是弱随机数（如时间戳、简单常量），甚至固定不变，导致密钥流可复现。

我们的攻击场景，正是基于最后一种最危险的情况：一个位数不大、抽头未知、但直接将其输出用作密钥流的LFSR。

2. 搭建实验场：用Python模拟一个“黑盒”LFSR

在尝试破解之前，我们得先有一个可以攻击的目标。让我们用Python来模拟一个LFSR生成器，并把它封装成一个“黑盒”。我们只知道它能生成比特流，但不知道其内部的位数和抽头。

class BlackBoxLFSR:
    """
    一个模拟的LFSR黑盒。
    内部使用一个预设的抽头配置（特征多项式）和种子来生成序列。
    对外只提供 `generate_keystream` 方法。
    """
    def __init__(self, seed: int, taps: list, length: int):
        """
        初始化LFSR。
        :param seed: 初始状态（整数形式），必须非零。
        :param taps: 抽头位置列表，例如对于多项式 x^4 + x^3 + 1，taps=[4,3]。
                     注意：这里约定最高位（最左边）为索引1。
        :param length: LFSR的位数。
        """
        if seed == 0:
            raise ValueError("Seed must be non-zero for LFSR to operate.")
        self.state = seed & ((1 << length) - 1)  # 确保状态在length位内
        self.taps = taps
        self.length = length

    def _clock(self):
        """推动LFSR一个时钟周期，返回移出的输出比特。"""
        # 计算反馈比特：所有抽头位置的比特进行异或
        feedback = 0
        for tap in self.taps:
            feedback ^= (self.state >> (self.length - tap)) & 1

        # 获取输出比特（最低位或最高位，取决于实现。这里采用移出最低位的模型）
        output = self.state & 1

        # 状态右移一位，并将反馈比特放入最高位
        self.state = (self.state >> 1) | (feedback << (self.length - 1))

        return output

    def generate_keystream(self, num_bits: int):
        """生成指定长度的密钥流（比特列表）。"""
        keystream = []
        for _ in range(num_bits):
            keystream.append(self._clock())
        return keystream

# 实例化一个我们稍后要攻击的LFSR黑盒
# 假设它是一个5位的LFSR，抽头在第5位和第3位（多项式 x^5 + x^3 + 1），种子为0b10101 (21)
target_lfsr = BlackBoxLFSR(seed=0b10101, taps=[5, 3], length=5)
print("黑盒LFSR已创建。我们不知道它的 taps 和 seed。")

现在，target_lfsr 对象对我们来说就是一个黑盒。我们可以调用 generate_keystream 来获取一段比特流，但无法直接窥探其内部的 state、taps 或初始 seed。这模拟了真实攻击中，我们只能获得加密后的密文（或部分密钥流）的场景。

为了验证我们的黑盒工作正常，并观察一下它的输出模式，我们可以先让它生成一小段序列看看：

# 生成前20个比特的密钥流
sample_stream = target_lfsr.generate_keystream(20)
print(f"黑盒生成的前20比特密钥流: {sample_stream}")
print(f"二进制表示: {''.join(str(b) for b in sample_stream)}")

运行后，你可能会看到类似 [1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0] 的输出。单从这20个比特，肉眼很难看出明显的规律，这正是LFSR作为伪随机数生成器想要达到的效果——在不知道内部结构的情况下，输出看起来是随机的。

3. 发起攻击：利用已知明文还原密钥流与抽头

真正的攻击始于一个经典的密码分析场景：已知明文攻击。假设我们通过某种方式（比如协议格式固定、文件头已知、或部分信息可猜测）获得了一小段明文 P 和对应的密文 C。由于流密码通常是逐比特异或，密钥流 K = P ⊕ C（其中 ⊕ 表示异或）。

假设我们获取了31比特的已知明文和密文对：

# 模拟已知的明文片段 (31 bits)
known_plaintext = [1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1]
# 模拟对应的密文片段 (31 bits)
known_ciphertext = [0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0]

# 计算密钥流片段 K = P XOR C
known_keystream = [p ^ c for p, c in zip(known_plaintext, known_ciphertext)]
print(f"已知明文 (P): {known_plaintext}")
print(f"已知密文 (C): {known_ciphertext}")
print(f"推导出的密钥流 (K): {known_keystream}")
print(f"密钥流长度: {len(known_keystream)} bits")

现在我们手上有了一段连续的、由目标LFSR生成的密钥流片段。接下来的核心问题变成了：如何根据这段输出序列，推断出生成它的LFSR的抽头位置？

这里需要用到 Berlekamp-Massey 算法。这个算法非常精妙，它可以在只知道输出序列的情况下，找到能生成该序列的最短线性反馈移位寄存器（即找到其特征多项式）。对于密码分析来说，这简直是量身定做的工具。

提示：Berlekamp-Massey 算法最初是为纠错码设计的，但在密码分析中用于重构线性序列生成器的反馈多项式。其输入是比特序列，输出是最短LFSR的反馈多项式系数。

我们不需要从头实现这个算法（虽然理解其原理很有益），可以直接使用 sympy 库中的相关函数。让我们在Jupyter Notebook中安装并应用它：

# 在Jupyter Notebook的一个单元格中运行
!pip install sympy

from sympy import berlekamp_massey, symbols, Poly

def find_lfsr_taps(sequence, max_length=10):
    """
    使用Berlekamp-Massey算法寻找生成给定序列的最短LFSR的抽头位置。
    :param sequence: 比特列表，例如 [1,0,1,1,0,...]
    :param max_length: 预估的LFSR最大可能长度。
    :return: 一个元组 (LFSR长度, 抽头位置列表)。抽头位置从1开始计数（对应最高位）。
    """
    # 将比特序列转换为整数域上的序列（GF(2)上的序列，这里用整数0/1表示）
    # Berlekamp-Massey需要域上的序列，对于二进制，我们可以用整数列表。
    # SymPy的berlekamp_massey函数期望一个多项式序列。
    x = symbols('x')
    # 创建一个多项式，其系数是我们的序列（最低次项对应序列第一个元素？需要注意顺序）
    # 通常，序列s0, s1, s2,... 对应多项式 s0 + s1*x + s2*x^2 + ...
    poly_seq = sequence

    # 调用Berlekamp-Massey算法
    # 注意：SymPy的berlekamp_massey函数返回的是最小多项式C(x)，满足 sum_{i=0}^{L} c_i * s_{n-i} = 0
    # 其中c_L = 1。多项式 C(x) = 1 + c_{L-1}*x + ... + c_0 * x^L
    C = berlekamp_massey(poly_seq, x)

    # 将多项式对象转换为系数列表
    coeffs = Poly(C, x).all_coeffs()
    # 系数列表是从最高次项到常数项，例如对于多项式 x^5 + x^3 + 1，coeffs = [1, 0, 1, 0, 0, 1]
    # 我们需要的是除了最高次项（总是1）以外的非零项的次数。
    length = Poly(C, x).degree()
    taps = []
    # 遍历从x^{length-1} 到 x^0 的系数（对应coeffs[1:]）
    for i, coeff in enumerate(coeffs[1:]): # coeffs[0]是最高次项系数1
        power = length - (i + 1) # 计算当前项对应的x的幂次
        if coeff != 0:
            # LFSR的抽头位置通常表示为从最低位（输出位）开始的偏移，或者从最高位（反馈输入位）开始。
            # 在常见的Galois配置（我们的模拟器模型）中，多项式 x^n + c_{n-1}x^{n-1}+...+c_1x+1
            # 系数c_i=1表示第 (n-i) 位（从最高位为1开始计数）是抽头。
            # 如果我们的状态是 (s_{n-1}, s_{n-2}, ..., s_0)，反馈到s_{n-1}，
            # 那么多项式项 x^k (k从0到n-1) 对应抽头位置 n-k。
            tap_position = length - power
            taps.append(tap_position)
    # 排序并返回
    taps.sort()
    return length, taps

# 对我们推导出的密钥流应用算法
lfsr_length, predicted_taps = find_lfsr_taps(known_keystream)
print(f"Berlekamp-Massey算法分析结果：")
print(f"  推测的LFSR长度 (n): {lfsr_length}")
print(f"  推测的抽头位置 (从最高位为1计数): {predicted_taps}")
print(f"  对应的特征多项式: x^{lfsr_length} + " + " + ".join([f"x^{lfsr_length - tap}" for tap in predicted_taps]) + " + 1")

运行这段代码，算法很可能会正确地输出：LFSR长度为5，抽头位置为[5, 3]（对应多项式 x^5 + x^3 + 1）。这意味着，仅凭31比特的已知密钥流，我们就完全揭示了黑盒LFSR的内部结构！ 这正是线性复杂度的可怕之处——所需的信息量仅仅是LFSR长度的两倍左右（对于n位LFSR，通常需要2n个连续比特就能可靠地恢复）。

4. 完成攻击链：从抽头到种子，并预测未来

拿到了抽头配置（特征多项式），我们只完成了一半。要完全模拟目标LFSR并预测所有未来的密钥流，我们还需要它的初始状态（种子）。幸运的是，由于LFSR是线性的，一旦我们知道了它的结构，就可以利用已知的密钥流片段，通过解线性方程组来反推种子。

具体来说，LFSR的输出序列 s0, s1, s2, ... 与初始状态 (s_{n-1}, s_{n-2}, ..., s_0) 存在线性关系。对于已知的抽头多项式，我们可以建立一系列方程。例如，对于一个5位LFSR（抽头5,3），其反馈关系为 s_{i+5} = s_{i+3} ⊕ s_i。如果我们有前10个输出比特 s0 到 s9，我们可以将它们表示为初始状态比特 a4, a3, a2, a1, a0 的方程，然后求解这个方程组。

让我们用Python来实现这个求解过程，采用更通用的矩阵方法（使用 numpy）：

import numpy as np

def recover_initial_state(keystream, length, taps):
    """
    根据已知的密钥流开头片段、LFSR长度和抽头位置，恢复初始状态。
    :param keystream: 已知的密钥流比特列表（至少需要 `length` 个比特）。
    :param length: LFSR的位数。
    :param taps: 抽头位置列表（从最高位为1开始计数）。
    :return: 初始状态（整数形式）。
    """
    # 我们需要至少 `length` 个方程来求解 `length` 个未知数（初始状态比特）。
    # 实际上，利用线性递推关系，我们可以构造方程组。
    # 对于 Galois 型LFSR，输出序列 s_k 满足：s_{k+n} = sum_{t in taps} s_{k+n-t}  (mod 2)
    # 我们可以为 k = 0 到 length-1 建立方程，但这样方程可能不够独立。
    # 更稳健的方法是构建一个线性系统：M * initial_state = output_vector (mod 2)
    # 其中 M 是一个 length x length 的矩阵。

    # 构建矩阵 M 和向量 V
    M = []
    V = []
    for i in range(length):
        # 对于第i个方程，我们利用已知的 keystream[i] 到 keystream[i+length-1] 之间的关系
        # 但更直接的方法是利用：初始状态 (s0, s1, ..., s_{n-1}) 就是前n个输出比特吗？
        # 注意：这取决于LFSR的实现模型。在我们的BlackBoxLFSR模型中，输出比特是状态的最低位。
        # 在时钟推进过程中，初始状态的第一位输出就是种子的最低位。
        # 因此，最直接的方法是：如果我们有连续n个输出比特，并且知道抽头，
        # 我们可以通过反向推导（逆向时钟）来恢复状态。
        # 这里采用一种更通用的方法：建立关于初始状态比特的线性方程组。

        # 方程：对于每个时间点 t (从0开始)，输出 s_t 是初始状态的线性函数。
        # 我们可以通过模拟LFSR的线性变换来构建这个关系。
        pass # 此处为简化，采用另一种更直观的方法。

    # 实际上，对于已知抽头的LFSR，恢复种子有一个更简单的方法：
    # 1. 用我们推测的抽头配置，初始化一个LFSR实例，但种子设为任意值（如1）。
    # 2. 驱动这个LFSR，生成一段序列。
    # 3. 由于LFSR是线性的，我们生成的序列与目标序列之间只差一个由初始种子决定的线性变换。
    # 4. 我们可以通过比较已知序列段，解出正确的种子。

    # 让我们换一种思路：既然我们已经知道了抽头，我们可以尝试“同步”一个LFSR。
    # 即，寻找一个初始状态，使得其生成的前 len(keystream) 个比特与已知密钥流完全匹配。
    # 由于状态空间只有 2^length - 1 种（非零），对于较小的length（如5，31种可能），甚至可以暴力尝试。

    if length <= 10:  # 对于小长度LFSR，暴力搜索是可行的
        for possible_seed in range(1, 1 << length):  # 遍历所有非零种子
            test_lfsr = BlackBoxLFSR(seed=possible_seed, taps=taps, length=length)
            # 重置状态
            test_lfsr.state = possible_seed
            generated = test_lfsr.generate_keystream(len(keystream))
            if generated == keystream:
                return possible_seed
        raise ValueError("未能找到匹配的种子。可能密钥流长度不足或抽头有误。")
    else:
        # 对于更长的LFSR，需要使用线性代数方法求解。
        # 构建方程组：A * S = B (mod 2)，其中S是初始状态向量。
        # 这里省略具体实现，通常可以调用Berlekamp-Massey的同时得到多项式，然后通过矩阵求逆或高斯消元求解。
        # 作为演示，我们假设是小长度LFSR。
        print("警告：LFSR长度较大，暴力搜索不可行，需要使用线性代数求解。本例中我们假设长度小。")
        return None

# 使用我们已知的密钥流片段、推测的长度和抽头来恢复种子
recovered_seed = recover_initial_state(known_keystream, lfsr_length, predicted_taps)
print(f"\n恢复出的LFSR初始种子 (整数): {recovered_seed}")
print(f"恢复出的LFSR初始种子 (二进制): {bin(recovered_seed)[2:].zfill(lfsr_length)}")

如果我们的推测正确（抽头为[5,3]），并且已知密钥流片段足够，recover_initial_state 函数应该能返回种子 21 (二进制10101)，这与我们创建黑盒时使用的种子一致。

至此，攻击链已经完成：

1. 信息收集：获取了一段明文-密文对，推导出密钥流片段。
2. 结构分析：使用Berlekamp-Massey算法，从密钥流片段中分析出LFSR的位数和抽头位置。
3. 状态恢复：利用已知的密钥流片段和已识别的结构，恢复出LFSR的初始种子。

现在，我们可以完全克隆目标LFSR了：

# 使用恢复出的参数构建一个“克隆”LFSR
clone_lfsr = BlackBoxLFSR(seed=recovered_seed, taps=predicted_taps, length=lfsr_length)

# 验证克隆体生成的密钥流是否与目标黑盒后续输出一致
# 首先，重置目标黑盒到初始状态（在真实攻击中我们无法做到，这里仅用于验证）
target_lfsr.state = 0b10101  # 重置内部状态
target_future_stream = target_lfsr.generate_keystream(50)
clone_future_stream = clone_lfsr.generate_keystream(50)

print("\n验证攻击结果：")
print(f"目标黑盒后续50比特密钥流: {target_future_stream[:20]}...") # 打印前20个
print(f"克隆LFSR生成的50比特密钥流: {clone_future_stream[:20]}...")
print(f"两者是否完全匹配? {target_future_stream == clone_future_stream}")

如果输出显示完全匹配，那么恭喜你，你已经成功“破解”了这个基于LFSR的弱加密系统。你现在拥有的这个 clone_lfsr 可以预测目标LFSR未来产生的所有密钥比特，从而解密任何使用同一密钥流加密的后续信息。

5. 实战延伸：在CTF竞赛中识别与利用LFSR漏洞

在CTF（Capture The Flag）夺旗赛中，LFSR相关的题目非常常见，通常出现在Crypto（密码学）和Reverse（逆向工程）类别。识别这类题目的关键在于寻找线性递归的特征。以下是一些实战技巧和解题模式：

1. 题目特征识别：

• 题目描述：常出现“stream cipher”、“pseudo-random generator”、“linear recurrence”、“predict the next number”等关键词。
• 提供的数据：可能会给出一长串数字（通常是二进制、十进制或十六进制），或者一个可以交互的服务器，它输出“随机”数序列。
• 逆向工程：在逆向题中，你可能会在反汇编代码或伪代码中看到典型的移位、异或操作循环，以及一个固定的常量数组（可能是抽头表）。

2. 典型的攻击步骤：

1. 数据收集：从题目中获取尽可能长的输出序列。如果是交互题，就多连接几次，收集输出。
2. 猜测LFSR长度：长度 n 通常是未知的。你可以尝试用不同长度的假设，运行Berlekamp-Massey算法，观察哪个长度能产生一个稳定的、阶数合理的多项式。或者，如果序列周期明显，周期长度可能等于 2^n - 1。
3. 应用Berlekamp-Massey：将输出序列（转换为比特流）输入算法，得到特征多项式。
4. 验证与预测：用得到的多项式生成序列，与已知序列对比验证。验证成功后，即可预测后续输出，生成Flag所需的密钥或直接得到答案。

3. 常见变体与加固方式（及如何应对）：

• 非线性组合：使用多个LFSR，并通过一个非线性函数（如AND、OR、MAJORITY）组合它们的输出。攻击难度大增，通常需要更复杂的相关攻击或代数攻击。在CTF中，如果LFSR数量少（如2-3个），可以尝试暴力枚举所有LFSR的初始状态。
• 不规则时钟控制：一个LFSR的输出控制另一个LFSR的时钟步进。这破坏了输出序列的线性复杂度均匀性。分析时需要识别时钟控制模式。
• 过滤函数：LFSR的状态通过一个非线性过滤函数产生输出，而不是直接输出某一位。这需要分析过滤函数的代数性质。

4. 一个简化的CTF风格示例： 假设题目给你一个十六进制字符串，说是LFSR生成的序列，要求预测下一个值。

# 模拟CTF题目
ctf_output_hex = "A2F81C4B9"  # 假设这是一段16进制表示的输出
# 1. 转换为比特流
ctf_output_bits = []
for char in ctf_output_hex:
    byte = int(char, 16)
    ctf_output_bits.extend([(byte >> i) & 1 for i in range(3, -1, -1)]) # 每个16进制字符转4个比特
print(f"CTF输出序列（比特）: {ctf_output_bits}")

# 2. 假设我们不知道长度，尝试几种可能
for n in [4, 5, 6, 7, 8]:
    try:
        length, taps = find_lfsr_taps(ctf_output_bits[:2*n], max_length=n) # 使用前2n个比特分析
        if length == n: # 如果分析出的长度与我们假设的一致
            print(f"尝试长度 n={n}: 分析出长度 {length}, 抽头 {taps}")
            # 3. 恢复种子（假设长度小，暴力）
            recovered_seed_ctf = recover_initial_state(ctf_output_bits, length, taps)
            if recovered_seed_ctf:
                # 4. 克隆并预测下一个输出
                clone_ctf = BlackBoxLFSR(recovered_seed_ctf, taps, length)
                # 先生成与已知等长的序列，验证
                clone_bits = clone_ctf.generate_keystream(len(ctf_output_bits))
                if clone_bits == ctf_output_bits:
                    print(f"  验证成功！种子: {recovered_seed_ctf}({bin(recovered_seed_ctf)})")
                    # 预测下一个字节（4个比特，一个16进制字符）
                    next_bits = clone_ctf.generate_keystream(4)
                    next_hex = hex(int(''.join(map(str, next_bits)), 2))[2:].upper()
                    print(f"  预测的下一个16进制字符: {next_hex}")
                    break
    except Exception as e:
        continue

在实际CTF比赛中，题目可能会将LFSR的输出进行各种编码（如base64、作为随机数生成器的种子等），但核心攻击逻辑——获取足够长的线性序列并应用Berlekamp-Massey算法——是不变的。

我最初接触这类题目时，总觉得需要非常高深的数学知识，但动手实现一遍后发现，核心工具就是一个现成的算法。真正的挑战往往在于从复杂的题目描述和数据处理中，剥离出那个最本质的线性序列。下次当你遇到一个看似随机的序列时，不妨先用Berlekamp-Massey算法试试，说不定会有惊喜。