第2章流密码¶

2.1 流密码的基本概念¶

流密码 (Stream Cipher) 是一类重要的对称加密算法。与分组密码 (Block Cipher) 将明文分割成固定大小的块分别加密不同，流密码则是对明文数据流以最小单位（通常是单个比特或字节）进行连续处理。其核心思想是利用一个密钥（称为种子密钥）通过密钥流产生器 (Keystream Generator) 生成一个看似随机的、与明文长度相同的序列，这个序列被称为密钥流 (Keystream)。然后，将密钥流与明文数据流通过某种运算（通常是异或 (XOR) 操作）结合起来，产生密文流。

工作流程：

密钥流生成： 发送方和接收方使用共享的种子密钥 \(K\) 初始化各自的密钥流产生器。
加密： 设明文为 \(P = p_1p_2p_3p_4\dots\)，密钥流为 \(S = s_1s_2s_3s_4\dots\)。加密操作通常为：\(C_i = p_i \oplus s_i\)，其中 \(C_i\) 是密文的第 \(i\) 个单元，\(\oplus\) 表示异或运算。
解密： 接收方使用相同的种子密钥 \(K\) 和相同的密钥流产生器生成与发送方完全一致的密钥流 \(S\)。解密操作为：\(p_i = C_i \oplus s_i\)。

异或 (XOR) 运算的关键特性：

\(A \oplus B = B \oplus A\) (交换律)
\((A \oplus B) \oplus C = A \oplus (B \oplus C)\) (结合律)
\(A \oplus 0 = A\) (任何数与0异或等于其本身)
\(A \oplus A = 0\) (任何数与自身异或等于0)
因此，在解密时：\(C_i \oplus s_i = (p_i \oplus s_i) \oplus s_i = p_i \oplus (s_i \oplus s_i) = p_i \oplus 0 = p_i\)。这保证了只要密钥流相同，就能正确解密。

理想密钥流的特性：

一个理想的密钥流应该与真正的随机序列在统计上无法区分，并且对于不知道种子密钥的攻击者来说是不可预测的。具体来说：

随机性 (Randomness)： 密钥流中的0和1应该大致等概率出现，各种比特模式（如游程）的分布应符合随机序列的统计规律。
不可预测性 (Unpredictability)： 即使已知密钥流的一部分，也无法预测后续的密钥流比特，或者推断出种子密钥。
长周期 (Long Period)： 密钥流在重复之前应该有非常长的周期。如果周期太短，攻击者可能通过收集足够长的密文来发现重复的密钥流段，从而破解密码。理想情况下，周期应远大于所有可能加密消息的总长度。
与明文无关 (Plaintext Independence)： 密钥流的生成不应依赖于明文内容。
抗已知明文攻击 (Resistance to Known-Plaintext Attack)： 如果攻击者获得了部分明文及其对应的密文，他们就能得到相应的密钥流片段 (\(s_i = p_i \oplus C_i\))。密钥流产生器必须能够抵抗基于这些已知密钥流片段的攻击。

应用场景：

流密码由于其加密和解密速度快、错误传播性较低（对于同步流密码而言，一个比特的错误通常只影响对应的一个比特的解密），常用于需要低延迟和高吞吐量数据流加密的场景，例如：

无线通信 (如 GSM 网络中的 A5/1, A5/2 算法，蓝牙的 E0 算法)
安全套接层/传输层安全 (SSL/TLS) 中的某些加密套件 (如 RC4，尽管 RC4 已被发现存在严重漏洞，不再推荐使用)
实时音视频加密

2.1.1 同步流密码 (Synchronous Stream Ciphers)¶

在同步流密码中，密钥流的生成完全独立于明文流和密文流。密钥流的产生仅依赖于初始的种子密钥和某种确定的算法（通常由时钟脉冲驱动）。

关键特点：

同步要求： 发送方和接收方的密钥流产生器必须严格同步。这意味着它们必须使用相同的种子密钥，并且必须在同一时刻开始生成密钥流，以相同的速率产生密钥流的比特。
无错误传播 (Error Non-Propagation)： 如果密文在传输过程中发生单个比特的翻转错误（例如，0 变成 1 或 1 变成 0），那么在解密时，只有对应位置的明文比特会出错。这个错误不会影响到后续比特的正确解密。
对丢失/插入敏感： 如果密文在传输过程中发生比特的丢失或插入，会导致发送方和接收方的密钥流与密文流之间的对应关系错位。从错误发生点开始，后续所有的解密都将失败，直到双方重新进行同步。例如，如果密文中丢失了一个比特，接收方会用 \(s_k\) 去解密 \(C_{k+1}\)，导致后续全部解密错误。
主动攻击的风险： 由于密文的特定比特直接对应于明文的特定比特，攻击者如果能够精确地修改密文中的某些比特，就可以有针对性地改变解密后的明文对应比特。例如，如果攻击者知道某一位明文是0，并且想把它改成1，只需翻转密文中的对应比特 (\(C_i' = C_i \oplus 1\))，那么解密后 \(p_i' = C_i' \oplus s_i = (C_i \oplus 1) \oplus s_i = (p_i \oplus s_i \oplus 1) \oplus s_i = p_i \oplus 1\)。

对比：自同步流密码 (Self-Synchronizing Stream Ciphers) / 异步流密码 (Asynchronous Stream Ciphers)

虽然本章重点是同步流密码，但简单对比有助于理解。在自同步流密码中，密钥流的生成不仅依赖于种子密钥，还依赖于先前固定数量的密文比特。这意味着如果传输中发生比特丢失或插入，一旦接收到正确数量的后续密文比特，接收方可以自动重新同步。但其缺点是错误会传播：一个密文比特的错误会影响后续若干个明文比特的解密。

分组密码与流密码的区别就在于有无记忆性。流密码是有记忆性的。

2.1.2 有限状态自动机 (Finite State Automaton, FSA)¶

有限状态自动机 (FSA)，也称为有限状态机 (Finite State Machine, FSM)，是一种计算的数学模型，它包含有限数量的状态。它可以被看作是一个抽象的机器，在任何给定时间点都处于其有限状态集合中的某一个状态。当它接收到输入时，会根据当前的状态和接收到的输入，转换到另一个状态（或保持当前状态），并可能产生输出。

在流密码中的应用：

密钥流产生器可以被精确地建模为一个有限状态自动机。

状态 (States)： 密钥流产生器的内部存储单元（例如 LFSR 中的寄存器内容）构成了 FSA 的状态。由于存储单元的数量和每个单元能存储的值是有限的，所以总状态数是有限的。
初始状态 (Initial State)： 由种子密钥决定的产生器的初始配置。
输入 (Input)： 对于典型的同步流密码中的密钥流产生器，主要的“输入”可以看作是时钟脉冲，它驱动产生器从一个状态转换到下一个状态。在某些设计中，也可能有外部输入。
状态转移函数 (Transition Function)： 定义了产生器如何从当前状态根据（隐式的）时钟输入转换到下一个状态。例如，在 LFSR 中，这是由移位操作和反馈逻辑决定的。
输出函数 (Output Function)： 定义了在每个状态（或每次状态转换时）产生哪些密钥流比特。通常是当前状态的某个函数，例如 LFSR 输出其最末端（或某个特定抽头）的比特。

有限状态的必然结果——周期性：

由于状态的数量是有限的，当密钥流产生器连续运行时，它必然会在某个时刻回到一个曾经出现过的状态。一旦回到一个旧状态，由于状态转移函数是确定的，后续的状态序列和输出序列也将与之前完全相同，从而导致密钥流呈现周期性。这个周期的长度对密码的安全性至关重要。一个 \(N\) 个状态的 FSA，其输出序列的周期最大为 \(N\)。

2.1.3 密钥流产生器 (Keystream Generator)¶

密钥流产生器是流密码的核心和灵魂，其设计的安全性直接决定了整个流密码系统的安全性。所以说流密码的核心是密钥流生成器的设计。它的任务是接收一个相对较短的种子密钥，并将其扩展成一个非常长的、在密码学意义上安全的伪随机序列，即密钥流。

优秀密钥流产生器的设计目标和特性详解：

安全性高 (High Security)：
- 抗已知明文攻击： 如前所述，即使攻击者知道一段密钥流（通过已知明文和对应密文异或得到），也应该极其困难（计算上不可行）去推断出种子密钥或密钥流产生器的内部结构，或者预测密钥流的其余部分。
- 抗选择明文攻击/选择密文攻击： 在这些攻击模型下，攻击者有能力选择明文进行加密或选择密文进行解密。产生器应能抵抗这些更强的攻击。
- 不可区分性 (Indistinguishability)： 产生的密钥流在统计上应与真正的随机序列无法区分。任何有效的统计检验都无法区分密钥流和真随机流。
- 没有弱密钥 (No Weak Keys)： 不应存在某些种子密钥，使得它们产生的密钥流具有可利用的弱点（例如周期过短、统计特性差等）。
周期长 (Long Period)：
- 密钥流的周期是指密钥流序列开始重复之前的长度。
- 避免密钥重用： 如果密钥流的周期 \(L\) 小于明文长度，那么密钥流将会被重复使用。例如，如果明文是 \(P_1P_2\dots P_L P_{L+1}\dots P_{2L}\)，密钥流是 \(S_1S_2\dots S_L S_1\dots S_L\)。那么密文 \(C_i = P_i \oplus S_i\) 和 \(C_{L+i} = P_{L+i} \oplus S_i\)。如果攻击者获得这两段密文，他们可以计算 \(C_i \oplus C_{L+i} = (P_i \oplus S_i) \oplus (P_{L+i} \oplus S_i) = P_i \oplus P_{L+i}\)。这消除了密钥流，使得攻击者可以直接分析两个明文段之间的关系，极大地降低了破解难度（例如，通过频率分析或已知部分明文）。这就是所谓的“两时一密”(two-time pad) 问题，是致命的。
- 周期长度应远大于系统预期加密的数据总量。对于一个有 \(N\) 个内部状态的产生器，其最大周期可以达到 \(N\)（如果所有状态构成一个大环）或者 \(2^k-1\)（对于 \(k\) 级线性反馈移位寄存器）。
良好的统计特性 (Good Statistical Properties)：
- 均衡性： 在一个周期内，0 和 1 的数量应大致相等。
- 游程分布： 连续相同比特的子序列（游程）的长度分布应符合随机序列的期望。例如，长度为 1 的游程应最多，长度为 2 的游程数量约为长度为 1 的一半，以此类推。
- 低自相关性： 密钥流与其自身的移位版本之间的相关性应尽可能低（除了零移位）。
- 高线性复杂度 (Linear Complexity)： 线性复杂度是指能够生成该序列的最短 LFSR 的级数。低线性复杂度的序列容易被 Berlekamp-Massey 算法等方法分析和重构。一个好的密钥流产生器应产生具有高线性复杂度的密钥流。
实现高效 (Efficient Implementation)：
- 无论是硬件实现还是软件实现，密钥流的生成速度都应该足够快，以满足应用需求，如高速网络通信或实时数据处理。
- 硬件实现通常追求门电路少、功耗低。
- 软件实现通常追求执行指令少、内存占用小。
对种子密钥敏感 (Sensitivity to Seed Key)：
- 种子密钥的微小改变（例如只改变一个比特）应该导致生成的密钥流完全不同，这种特性称为雪崩效应。

流密码强度依赖于密钥流产生器生成序列的随机性和不可预测性。一个好的密钥流产生器应具备上述所有特性，从而提供高度的安全性。

常见的密钥流产生器构造方法包括基于线性反馈移位寄存器 (LFSR) 的设计（如 LFSR 的组合、滤波或时钟控制）以及基于数学难题（如离散对数）的设计等。

2.2 线性反馈移位寄存器 (Linear Feedback Shift Register, LFSR)¶

线性反馈移位寄存器 (LFSR) 因其结构简单、易于硬件实现以及能够产生具有良好统计特性的长周期序列，而成为密钥流产生器设计中的一个基础和核心的构建模块。

结构组成：

一个 LFSR 由两个主要部分组成：

移位寄存器 (Shift Register)： 由 \(L\) 个串联的存储单元（或称为级，stages）组成，每个单元通常存储一个比特 (0 或 1)。这些单元通常由触发器 (flip-flops) 实现。
反馈函数 (Feedback Function)： 这是一个线性函数，它从移位寄存器的某些特定位置（称为抽头 (taps)）取出比特值，通过异或 (XOR) 运算组合这些比特，并将结果反馈到寄存器的输入端（通常是第一级）。

工作原理：

在每个时钟脉冲的驱动下，LFSR 进行如下操作：

移位 (Shift)： 寄存器中的所有比特向一个方向（例如，从左到右或从右到左，这里假设从右到左，新的输入在最右端）移动一个位置。
- \(s_0 \leftarrow s_1\)
- \(s_1 \leftarrow s_2\)
- ...
- \(s_{L-2} \leftarrow s_{L-1}\)
输出 (Output)： 最末端（例如 \(s_0\)）的比特被移出，这个比特通常作为密钥流的一个输出比特。
反馈 (Feedback)： 根据预设的抽头位置，从移位后的寄存器状态中（即 \(s_1, s_2, \dots, s_{L-1}\) 的新值）选取若干比特进行异或运算。
- 设抽头位置为 \(t_1, t_2, \dots, t_k\) (这些是寄存器级的索引，例如第 \(j\) 级的内容是 \(s_j\))。
- 新的输入比特 \(s_{new}\) 计算为： \(s_{new} = s_{t_1} \oplus s_{t_2} \oplus \dots \oplus s_{t_k}\)。
输入 (Input)： 计算得到的反馈比特 \(s_{new}\) 被送入移位寄存器的始端（例如 \(s_{L-1} \leftarrow s_{new}\)）。

示例 (一个3级LFSR)：

假设有一个3级LFSR (\(L=3\))，状态为 \((s_2, s_1, s_0)\)。反馈函数由 \(s_2\) 和 \(s_0\) (移位前的 \(s_0\)，即当前输出位) 的异或决定，并反馈到 \(s_2\) 的位置 (斐波那契结构)。或者，更常见的伽罗瓦结构中，反馈来自当前状态的某些位，影响下一状态的输入位。

我们以伽罗瓦 (Galois) 配置为例，反馈影响输入端：设寄存器为 \((s_{L-1}, s_{L-2}, \dots, s_1, s_0)\)。输出为 \(s_0\)。新的 \(s_{L-1}\) 是由某些 \(s_i\) (其中 \(i\) 对应抽头位置) 异或而成。其他位 \(s_{i-1} \leftarrow s_i\)。

更清晰的斐波那契 (Fibonacci) 配置：状态 \((s_{L-1}, s_{L-2}, \dots, s_1, s_0)\)。 1. 比特 \(s_0\) 作为输出。 2. 寄存器右移一位: \(s_0\) 丢弃， \(s_1 \rightarrow s_0, s_2 \rightarrow s_1, \dots, s_{L-1} \rightarrow s_{L-2}\)。 3. 新的 \(s_{L-1}\) (最左边的位) 由反馈函数决定: \(s_{L-1} = c_1 s_{L-1}' \oplus c_2 s_{L-2}' \oplus \dots \oplus c_L s_0'\) (其中 \(s_i'\) 是移位前的状态，而 \(c_i\) 是反馈多项式的系数)。更通用的写法是 \(s_{L-1} = \bigoplus_{j \in T} s_j'\)，T是抽头集合。

例如，一个3级LFSR，抽头在第3位和第1位 (即 \(s_2\) 和 \(s_0\)，移位前的)。初始状态: \((1, 0, 0)\) (即 \(s_2=1, s_1=0, s_0=0\)) 输出位是 \(s_0\)。反馈到 \(s_2\) 的是 \(s_2 \oplus s_0\) (移位前的)。

时钟	状态 \((s_2, s_1, s_0)\)	输出 (\(s_0\))	反馈 (\(s_2 \oplus s_0\))	下一状态 \((s_2 \oplus s_0, s_2, s_1)\)
0	\((1, 0, 0)\)	0	\(1 \oplus 0 = 1\)	\((1, 1, 0)\)
1	\((1, 1, 0)\)	0	\(1 \oplus 0 = 1\)	\((1, 1, 1)\)
2	\((1, 1, 1)\)	1	\(1 \oplus 1 = 0\)	\((0, 1, 1)\)
3	\((0, 1, 1)\)	1	\(0 \oplus 1 = 1\)	\((1, 0, 1)\)
4	\((1, 0, 1)\)	1	\(1 \oplus 1 = 0\)	\((0, 1, 0)\)
5	\((0, 1, 0)\)	0	\(0 \oplus 0 = 0\)	\((0, 0, 1)\)
6	\((0, 0, 1)\)	1	\(0 \oplus 1 = 1\)	\((1, 0, 0)\)
7	\((1, 0, 0)\)	0	\(1 \oplus 0 = 1\)	\((1, 1, 0)\)

输出序列 (取 \(s_0\)) 为: \(0, 0, 1, 1, 1, 0, 1, (0, 0, 1, \dots)\) 周期为 \(2^3 - 1 = 7\) (输出序列为m序列)。

初始状态 (Seed)：

LFSR 的输出序列完全由其反馈逻辑和初始状态 (种子密钥) 决定。如果初始状态为全零，并且反馈函数中没有常数项 (纯线性反馈)，则 LFSR 将永远输出零。因此，全零状态通常是一个需要避免的初始状态。对于一个 \(L\) 级的 LFSR，它有 \(2^L\) 个可能的状态。

重要性：

LFSR容易用数字逻辑电路实现，速度快。
通过选择合适的反馈函数，可以产生具有很长周期的序列（最大长度序列，即m序列）。
其输出序列具有良好的伪随机统计特性。
LFSR 的数学理论（基于有限域上的多项式代数）非常成熟，便于分析其性质。

然而，由于其固有的线性特性，单个 LFSR 直接用作密钥流产生器是不安全的，容易受到已知明文攻击（如使用 Berlekamp-Massey 算法）。因此，在实际的流密码设计中，通常会使用多个 LFSR 进行非线性组合，或者对 LFSR 的输出进行非线性滤波，以增强其安全性。

2.3 线性移位寄存器的一元多项式表示¶

LFSR 的行为和其输出序列的特性可以通过有限域 GF(2)（即系数为0或1的域）上的一元多项式来精确描述和分析。这种表示方法是理解 LFSR 理论性质（如周期、线性复杂度）的关键。

对于一个 \(L\) 级的 LFSR，其特征多项式 (Characteristic Polynomial) 或反馈多项式 (Feedback Polynomial) 定义为：

\[ P(x) = 1 + c_1x + c_2x^2 + \dots + c_{L-1}x^{L-1} + c_Lx^L \]

或者，有时也写成（特别是在伽罗瓦配置中，表示抽头位置）：

\[ P(x) = x^L + c_{L-1}x^{L-1} + \dots + c_1x + c_0 \]

(其中 \(c_0=1\) 总是成立，因为第0级总是被反馈影响或作为输出基准)

我们以上面 Fibonacci 结构中更常见的形式为例：

\[ P(x) = 1 + \sum_{i=1}^{L} c_i x^i \]

其中：

\(L\) 是 LFSR 的级数（寄存器的长度）。
\(x^i\) 表示寄存器的第 \(i\) 个位置（通常 \(x^1\) 对应离反馈输入点最近的第一个参与反馈的抽头，而 \(x^L\) 对应最远的一个抽头，即寄存器的长度）。
系数 \(c_i \in \{0, 1\}\)。如果 \(c_i = 1\)，则表示寄存器的第 \(i\) 个位置（或其输出）参与反馈运算（即有一个抽头）。如果 \(c_i = 0\)，则不参与。
常数项 '1' (或 \(x^0\)) 在这种表示法中通常代表反馈的输入点或者序列的递推关系。

多项式与反馈连接的关系：

如果 LFSR 的下一状态 \(s_t\) 的最左边的比特（即新输入的比特）是由当前状态 \((s_{t-1}, s_{t-2}, \dots, s_{t-L})\) 的某些位 \(s_{t-i}\) 异或而成，即：

\(s_t = c_1 s_{t-1} \oplus c_2 s_{t-2} \oplus \dots \oplus c_L s_{t-L}\)

那么其特征多项式是 \(P(x) = 1 + c_1x + c_2x^2 + \dots + c_Lx^L\)。

输出序列 \(S = \{s_0, s_1, s_2, \dots\}\) 满足递推关系 \(\sum_{i=0}^{L} c_i s_{k-i} = 0\) (其中 \(c_0=1\)) for \(k \ge L\)。

本原多项式 (Primitive Polynomial)：

特征多项式 \(P(x)\) 的性质直接决定了 LFSR 输出序列的性质，尤其是周期。

不可约多项式 (Irreducible Polynomial)： 如果一个多项式不能被分解为两个次数更低的多项式之积（在 GF(2) 上），则称其为不可约多项式。为了使 LFSR 具有良好的长周期特性，其特征多项式必须是不可约的。
本原多项式 (Primitive Polynomial)： 一个 \(L\) 次的不可约多项式 \(P(x)\) 被称为本原多项式，如果它是 GF(\(2^L\)) 的本原元 (primitive element) 的最小多项式。换句话说，如果 \(x\) 是方程 \(P(x)=0\) 的一个根，则 \(x\) 的阶 (multiplicative order) 是 \(2^L - 1\)。这意味着 \(x^k \neq 1\) 对于所有 \(1 \le k < 2^L - 1\)，且 \(x^{2^L-1} = 1\)。
最大长度序列 (m-sequence)： 如果一个 \(L\) 级 LFSR 的特征多项式 \(P(x)\) 是 GF(2) 上的一个 \(L\) 次本原多项式，并且 LFSR 的初始状态非全零，则该 LFSR 会产生一个周期为 \(2^L - 1\) 的序列。这个序列称为最大长度序列或 m序列。这是 LFSR 能产生的最长周期（因为有 \(2^L-1\) 个非零状态）。

选择本原多项式的重要性：

为了获得具有密码学价值的长周期和良好随机性的密钥流，选择一个本原的特征多项式至关重要。对于给定的级数 \(L\)，可能存在多个本原多项式。

状态转移的矩阵表示：

LFSR 的状态转移也可以用矩阵来表示。如果 LFSR 的当前状态（内容）为一个行向量 \(S_t = (s_{t,L-1}, s_{t,L-2}, \dots, s_{t,0})\)，则下一个状态 \(S_{t+1}\) 可以通过乘以一个 \(L \times L\) 的转移矩阵 (Transition Matrix) \(T\) 得到： \(S_{t+1} = S_t \cdot T\) (或者列向量 \(S_{t+1} = T \cdot S_t\) 取决于定义)。

对于特征多项式 \(P(x) = 1 + c_1x + \dots + c_{L-1}x^{L-1} + x^L\) ，其转移矩阵 \(T\) (对于行向量状态，新位在最左边，输出最右边) 通常形如：

\[ T = \begin{pmatrix} c_{L-1} & 1 & 0 & \dots & 0 \\ c_{L-2} & 0 & 1 & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ c_0 & 0 & 0 & \dots & 1 \\ 1 & 0 & 0 & \dots & 0 \end{pmatrix} \]

或者更常见的（新位在最高位，输出最低位，多项式 \(P(x) = x^L + c_{L-1}x^{L-1} + \dots + c_1x + c_0\)，\(c_i\) 是抽头系数）：

\[ S_t = (s_{L-1}, s_{L-2}, \dots, s_0) \]

\[ S_{t+1} = ( \sum_{i=0}^{L-1} c_i s_i, s_{L-1}, s_{L-2}, \dots, s_1 ) \]

其转移矩阵 \(T\) (伴随矩阵的转置) 为：

\[ T = \begin{pmatrix} c_{L-1} & 1 & 0 & \dots & 0 \\ c_{L-2} & 0 & 1 & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ c_1 & 0 & 0 & \dots & 1 \\ c_0 & 0 & 0 & \dots & 0 \end{pmatrix} \]

(这里的 \(c_i\) 来自 \(P(x) = x^L - \sum_{i=0}^{L-1} c_i x^i\) 的递推关系 \(s_k = \sum_{i=0}^{L-1} c_i s_{k-L+i}\))。

如果 \(P(x)\) 是特征多项式，那么 \(T\) 的特征多项式也与 \(P(x)\) 相关 (通常就是 \(P(x)\) 或其倒数多项式)。如果 \(P(x)\) 是本原的，那么 \(T\) 的周期是 \(2^L-1\)。

连续 \(k\) 步的状态 \(S_{t+k} = S_t \cdot T^k\)。

多项式表示法为分析 LFSR 的周期、输出序列的代数结构以及构造具有特定性质的序列提供了强大的数学工具。

2.4 m序列的伪随机性¶

由 \(L\) 级 LFSR 且其特征多项式为本原多项式所产生的序列，称为 m序列 (Maximum-length sequence)。其周期为 \(2^L - 1\)。m序列之所以在密码学和通信领域受到广泛关注，是因为它们具有许多类似于真正随机序列的优良统计特性，这些特性使得它们成为优秀的伪随机序列。

以下是 m序列主要的伪随机性质：

均衡性 (Balance Property) / 平衡性：
- 在一个完整的周期 (\(2^L-1\) 位) 内，数字 "1" 的个数与数字 "0" 的个数非常接近。
- 具体来说，在一个周期内，"1" 的个数为 \(2^{L-1}\)，而 "0" 的个数为 \(2^{L-1} - 1\)。
- 直观解释： 这意味着序列中 0 和 1 的出现概率几乎相等，没有明显的偏向。对于一个长的随机序列，我们期望 0 和 1 的数量大致相同。
游程特性 (Run Property)：
- 游程是指序列中连续出现的相同比特的子串。例如，在序列 111001000 中，111 是一个长度为3的1-游程，00 是一个长度为2的0-游程。
- m序列的游程分布具有明确的规律，非常接近理想随机序列的游程分布：
  - 在一个周期内，总共有 \(2^{L-1}\) 个游程（包括1-游程和0-游程）。
  - 对于长度为 \(k\) 的游程 (\(1 \le k \le L-2\))：0-游程和1-游程的数量均为 \(2^{L-k-1}\)。
  - 对于长度为 \(L-1\) 的游程：存在一个长度为 \(L-1\) 的0-游程，和一个长度为 \(L-1\) 的1-游程 (如果 \(P(x)\) 是特定形式，可能只有一个，例如 \(L-1\) 的 0-游程和长度 \(L\) 的 1-游程)。
  - 更准确地说：
    - 长度为1的游程占总游程数的一半。
    - 长度为2的游程占总游程数的四分之一。
    - 长度为 \(k\) 的游程占总游程数的 \(1/2^k\)。
    - 有一个长度为 \(L\) 的1-游程 (对应于寄存器内容为 \(00\dots01\) 之后生成的全1序列)。
    - 有一个长度为 \(L-1\) 的0-游程 (对应于寄存器内容为 \(10\dots00\) 之前生成的全0序列)。
- 直观解释： 这种分布模式防止了序列中出现过多长串的0或长串的1，使得序列看起来更“混乱”和不可预测，类似于随机抛硬币序列中连续正面或反面的分布。
自相关特性 (Autocorrelation Property)：
- 自相关函数衡量一个序列与其自身经过不同移位（时延 \(\tau\)）后的相似程度。对于一个m序列 \(\{s_i\}\)，其自相关函数 \(R(\tau)\) 定义为在一个周期内，序列 \(\{s_i\}\) 与其移位 \(\tau\) 位的序列 \(\{s_{i+\tau}\}\) 对应位相等的次数减去相异的次数，再除以周期长度 \(N = 2^L-1\)。
- 或者更常见的定义是基于异或的：计算 \(s_i \oplus s_{i+\tau}\) 形成的序列在一个周期内0的个数减去1的个数。
- m序列具有理想的双值自相关函数（对于周期归一化形式）：

\[R(\tau) = \frac{1}{N} \sum_{i=0}^{N-1} (-1)^{s_i \oplus s_{i+\tau}} = \begin{cases} 1 & \text{if } \tau \equiv 0 \pmod{N} \\ -\frac{1}{N} & \text{if } \tau \not\equiv 0 \pmod{N} \end{cases}\]

这意味着：

当移位 \(\tau = 0\) 时（序列与自身完全重合），自相关函数值为1（或 \(N\) 未归一化时），表示完全相关。
当移位 \(\tau \neq 0 \pmod{N}\) 时（任何非零移位），自相关函数值是一个非常小的负常数 \(-1/(2^L-1)\)（或 -1 未归一化时）。这表示序列与其自身的任意非平凡移位版本都只有很低的（几乎是恒定的负）相关性。在一个周期内，其移位版本与原序列相比，对应位相同和相异的次数几乎相等，相差仅为1。
直观解释： 这个特性非常重要。它表明 m序列与其移位版本“看起来非常不同”，除非移位是周期的整数倍。这在通信系统中用于码分多址 (CDMA) 和同步，在密码学中则意味着序列的不同部分之间没有简单的线性依赖关系可以被轻易利用。尖锐的自相关峰值使得它很容易检测到序列的存在和同步点。
移相特性 (Shift-and-Add Property) / 叠加特性：
- 一个 m序列 \(\{s_i\}\) 与其自身的某个循环移位版本 \(\{s_{i+\tau}\}\) 逐比特异或 (相加，因为是在 GF(2) 上) 后，得到的序列仍然是该 m序列的另一个循环移位版本，或者是全零序列（当两个序列完全相同时，即 \(\tau = 0\) 或 \(\tau\) 是周期的倍数）。
- 即，如果 \(S\) 是一个 m序列， \(S'\) 是 \(S\) 的一个循环移位，则 \(S \oplus S'\) 也是 \(S\) 的一个循环移位 (或全零)。
- 直观解释： 这个特性反映了 m序列的代数结构。虽然它是一个优点（保持了序列家族的封闭性），但在密码学上，如果这种结构被不当使用，也可能成为一个弱点，因为它揭示了序列之间的线性关系。

为什么称为“伪”随机：

尽管 m序列具有上述优良的统计特性，非常接近真随机序列，但它们终究是确定性的。只要知道了 LFSR 的特征多项式（即反馈连接）和任意 \(L\) 个连续的比特（足以确定当前状态），就可以完全预测后续的所有比特。这是“伪”随机的根本含义——它们是由确定性算法生成的，只是看起来随机。真随机序列则是不可预测的。

这些伪随机性使得 m序列在需要可复现的、具有良好统计特性的二进制序列的场合非常有用，如：

通信系统中的扩频码 (如 GPS、CDMA)
数字系统的测试和故障诊断 (生成测试向量)
密码学中的流密码密钥流组件 (但需与其他非线性操作结合)
蒙特卡洛模拟中的随机数源 (尽管更复杂的生成器现在更常用)

2.5 m序列密码的破译¶

尽管 m序列具有诸多优良的伪随机特性，但如果直接将单个 LFSR 产生的 m序列用作流密码的密钥流，这样的密码体制是非常不安全的，很容易被密码分析者攻破，特别是通过已知明文攻击 (Known-Plaintext Attack, KPA)。

核心弱点：线性性

LFSR 的根本特性是其线性性。输出序列的每一位都是由寄存器先前状态的某些位的线性组合（异或）得到的。这种线性关系使得即使只知道密钥流的一小部分，也可能恢复整个 LFSR 的结构和初始状态。

Berlekamp-Massey 算法 (B-M 算法)：

Berlekamp-Massey 算法是破译基于 LFSR 的流密码（特别是那些直接使用 m序列的密码）最著名和最有效的工具。

功能： 给定一个二进制序列（例如，通过已知明文和对应密文异或得到的密钥流片段），B-M 算法能够找到一个能生成该序列的最短线性反馈移位寄存器 (shortest LFSR)。它会输出这个最短 LFSR 的特征多项式（即反馈连接）和其初始状态。
效率： B-M 算法非常高效。对于一个由 \(L\) 级 LFSR 生成的序列，只需要大约 \(2L\) 个连续的密钥流比特，B-M 算法就几乎肯定能够唯一地确定这个 LFSR 的特征多项式（如果序列的线性复杂度确实是 \(L\)）。
- 线性复杂度 (Linear Complexity)： 一个序列的线性复杂度是指能够生成该序列的最短 LFSR 的级数 \(L_C\)。对于一个 m序列，其线性复杂度等于其 LFSR 的级数 \(L\) (\(L_C = L\))。
工作原理简述： B-M 算法是一个迭代算法。它逐个处理输入的序列比特。在每一步，它尝试用当前估计的 LFSR 来预测下一个比特。如果预测正确，则 LFSR 保持不变。如果预测错误，算法会修正 LFSR 的反馈多项式，使其能够正确生成到目前为止的所有比特，并确保新的 LFSR 仍然是当前已知序列片段的最短 LFSR。修正过程涉及到之前某个预测错误的“差异序列”和当时的 LFSR 状态。

破译过程 (已知明文攻击)：

获取密钥流片段： 攻击者假设目标系统使用了基于 LFSR 的流密码。如果攻击者能够获得一段明文 \(P = p_1p_2\dots p_k\) 及其对应的密文 \(C = C_1C_2\dots C_k\)，他们就可以通过逐比特异或轻松恢复出相应的密钥流片段 \(S = s_1s_2\dots s_k\)，因为 \(s_i = p_i \oplus C_i\)。
应用 B-M 算法： 攻击者将获取到的密钥流片段 \(S\) 作为 B-M 算法的输入。
重构 LFSR： 如果密钥流确实是由一个 \(L\) 级的 LFSR 生成的（例如一个 m序列），并且攻击者获得的密钥流片段长度至少为 \(2L\) 比特，B-M 算法就能成功地计算出这个 LFSR 的特征多项式 \(P(x)\) 和一个有效的初始状态。
密钥流重现与解密： 一旦 LFSR 的结构和初始状态被确定，攻击者就可以：
- 运行这个重构的 LFSR，生成与原始加密时完全相同的密钥流。
- 使用这个密钥流解密所有截获的、使用相同密钥流加密的密文。

为什么 \(2L\) 比特通常足够？

一个 \(L\) 级的 LFSR 由 \(L\) 个反馈系数 (定义其特征多项式) 和 \(L\) 个比特的初始状态所唯一确定。总共需要确定 \(2L\) 个未知参数。因此，直观上，需要大约 \(2L\) 个方程（即 \(2L\) 个密钥流比特提供的约束）来解出这些参数。B-M 算法系统地解决了这个问题。

结论与对策：

直接使用单个 LFSR（即使是产生 m序列的 LFSR）作为密钥流是非常不安全的。其线性特性使得它无法抵抗基于 B-M 算法的已知明文攻击。

为了构建安全的流密码，密码设计者必须引入非线性 (Non-linearity) 来破坏这种可被 B-M 算法利用的线性结构。常用的增强方法包括：

非线性组合生成器 (Non-linear Combination Generator)： 使用多个（通常是参数互质的）LFSR，它们的输出通过一个非线性布尔函数进行组合，以产生最终的密钥流。例如，Geffe 生成器使用三个 LFSR，其输出 \(x, y, z\) 通过 \(f(x,y,z) = (x \land y) \oplus ((\neg x) \land z)\) 或 \(xy \oplus yz \oplus z\) (后者是另一版本) 等函数组合。目标是使得组合后的密钥流具有高的线性复杂度，并且难以从输出反推各个 LFSR 的状态。
非线性滤波器生成器 (Non-linear Filter Generator)： 只使用一个 LFSR，但不是直接输出其某个比特，而是将 LFSR 的多个状态位（抽头）输入到一个非线性布尔函数中，该函数的输出作为密钥流比特。例如，Pless 生成器。关键在于选择能够产生高线性复杂度、良好统计特性且能抵抗特定攻击（如相关攻击）的非线性滤波函数。
钟控生成器 (Clock-Controlled Generator)： 使用一个或多个 LFSR 来控制另一个（或多个）主要 LFSR 的时钟。例如，一个 LFSR 的输出决定另一个 LFSR 是否在当前时钟周期进行移位。这会引入不规则的移位，使得输出序列与单个 LFSR 的输出行为有很大差异，从而大大增加其分析难度。例如，A5/1 算法中就使用了不规则时钟控制。

这些方法旨在通过引入非线性，使得密钥流的线性复杂度远大于构成它的 LFSR 的级数之和，并且使得密钥流与内部 LFSR 状态之间的关系变得复杂，从而有效抵抗 B-M 算法以及其他针对线性系统的分析方法。

第2章 流密码¶