线性反馈移位寄存器：F2[x] 上的本原多项式与流密码

一句话版本

LFSR 是一排寄存器，每次把几个位置异或起来塞回队尾，就能吐出一长串"看起来随机"的比特。若反馈多项式是 $\mathbb{F}_2$ 上的本原多项式， $n$ 位寄存器的周期达到最大值 $2^n - 1$ 。但它是线性的：只要看到 $2n$ 个输出比特，Berlekamp–Massey 算法就能解出整个寄存器。所以 LFSR 单独使用不安全，必须加入非线性。

全文分三层：

通俗理解：一排会"传话"的格子
实际用处：GPS、Wi-Fi 扰码、CRC，以及 GSM、DVD 加密的失败
数学原理：线性递推、本原多项式与最大周期、Berlekamp–Massey，附手算例子

第一层：通俗理解

1.1 一排传话的格子

想象 4 个格子排成一排，每格放 0 或 1。每过一拍：

最左边的格子把数字"吐出去"，作为输出；
所有格子左移一格；
最右边空出来的格子，填上某几个格子的异或。

上图里新值 $= s_0 \oplus s_1$ 。电路只需要几个触发器和一个异或门，极其便宜，速度极快。

1.2 能转多久才重复

4 个格子一共 $2^4 = 16$ 种状态。全 0 状态会一直是 0，所以最多有 15 种状态轮流出现。选对反馈位置，就能让它把 15 种非零状态全部走一遍才重复；选错了，周期会短得多。哪些位置是"对的"，由一个多项式是否本原决定。

1.3 为什么用它做加密很诱人，又很危险

一次一密需要和消息一样长的随机密钥。LFSR 提供了一个诱惑：只记住初始的几十个比特（密钥），就能生成几乎无限长的"随机"密钥流，再和明文异或。

问题在于 LFSR 是线性的，输出比特之间满足一个简单的线性方程。攻击者只要知道一小段明文（因此知道一小段密钥流），解一个线性方程组就能把整个寄存器还原。

第二层：实际用处

非加密用途（LFSR 在这里很出色）

用途	说明
GPS 卫星信号	每颗卫星的 C/A 码由两个 10 位 LFSR 组合生成（Gold 码），周期 1023，不同卫星的码互相关很低，接收机能分辨
扰码	Wi-Fi、以太网、USB 3.0、PCIe 用 LFSR 序列打乱数据，避免长串的 0 或 1
CRC 校验	本质上就是用 LFSR 电路做 $\mathbb{F}_2[x]$ 上的多项式除法，见《弃九法与校验位》
芯片测试、伪随机测试数据	便宜、可复现

加密用途（教训多于成功）

系统	结局
GSM 手机 A5/1	3 个 LFSR 按"多数表决"不规则步进；2000 年代被攻破，后来出现了可在普通硬件上实时破解的彩虹表
DVD 的 CSS	两个 LFSR，有效密钥只有 40 位；1999 年被 DeCSS 破解
蓝牙 E0	4 个 LFSR 加非线性组合，已有多种理论攻击

现代流密码（ChaCha20、AES-CTR）不再以 LFSR 为核心。不过 SNOW 3G、ZUC（祖冲之算法，4G/5G 标准之一）仍然在 LFSR 外面加了强非线性部件。

第三层：数学原理

3.1 线性递推

$n$ 位 LFSR 的输出满足

$s_{t+n} = c_0 s_t + c_1 s_{t+1} + \cdots + c_{n-1} s_{t+n-1} \pmod 2,$

对应的特征多项式为 $f(x) = x^n + c_{n-1}x^{n-1} + \cdots + c_1 x + c_0 \in \mathbb{F}_2[x]$ 。

3.2 LFSR 就是"乘以 $x$ "

把状态看成商环 $\mathbb{F}_2[x]/(f(x))$ 中的元素，那么 LFSR 每走一步，相当于乘以 $x$ 。

若 $f$ 不可约，这个商环是有限域 $\mathbb{F}_{2^n}$ （抽象代数： $F[x]/(f)$ 是域当且仅当 $f$ 不可约）；
周期就是 $x$ 在乘法群 $\mathbb{F}_{2^n}^\times$ 中的阶；
$\mathbb{F}_{2^n}^\times$ 是 $2^n - 1$ 阶循环群。若 $x$ 恰好是生成元，周期就达到最大值 $2^n - 1$ 。这样的 $f$ 叫本原多项式。

本原多项式的个数是 $\varphi(2^n - 1)/n$ （ $\varphi$ 是欧拉函数），所以总是存在，而且不少。

手算例子： $f(x) = x^4 + x + 1$ （本原）

递推 $s_{t+4} = s_t + s_{t+1}$ ，初始状态 $0001$ 。

$\underbrace{0\,0\,0\,1\ 0\,0\,1\,1\ 0\,1\,0\,1\ 1\,1\,1}_{15\ \text{位}}\ 0\,0\,0\,1\ \cdots$

第 16 位开始重复，周期 $15 = 2^4 - 1$ 。这 15 位里有 8 个 1、7 个 0；长度为 4 的窗口恰好把 15 个非零 4 位串各走过一遍，这些都是"m 序列"的典型性质。

对比： $f(x) = x^4 + x^3 + x^2 + x + 1$ 不可约但不本原（它整除 $x^5 - 1$ ，所以 $x$ 的阶只有 $5$ ），从 $0001$ 出发周期只有 $5$ 。（两者都已用 Python 验算。）

3.3 Berlekamp–Massey： $2n$ 个比特就够了

假设攻击者知道寄存器长度 $n$ ，看到连续 $2n$ 个输出比特，就能列出 $n$ 个关于 $c_0, \dots, c_{n-1}$ 的线性方程，在 $\mathbb{F}_2$ 上解出来。

从 8 个比特还原 4 位 LFSR

截获前 8 位： $s_0 \dots s_7 = 0\,0\,0\,1\,0\,0\,1\,1$ 。设 $s_{t+4} = c_0 s_t + c_1 s_{t+1} + c_2 s_{t+2} + c_3 s_{t+3}$ ：

$t$	方程	结果
0	$s_4 = c_0 \cdot 0 + c_1 \cdot 0 + c_2 \cdot 0 + c_3 \cdot 1$ ，即 $0 = c_3$	$c_3 = 0$
1	$s_5 = c_2 \cdot 1 + c_3 \cdot 0$ ，即 $0 = c_2$	$c_2 = 0$
2	$s_6 = c_1 \cdot 1 + c_2 s_4 + c_3 s_5$ ，即 $1 = c_1$	$c_1 = 1$
3	$s_7 = c_0 \cdot 1 + c_1 s_4 + c_2 s_5 + c_3 s_6$ ，即 $1 = c_0$	$c_0 = 1$

解出 $s_{t+4} = s_t + s_{t+1}$ ，即 $f(x) = x^4 + x + 1$ 。现在攻击者可以预测之后的所有密钥流。

Berlekamp–Massey 算法更进一步：不需要事先知道 $n$ ，以 $O(N^2)$ 的时间找出能生成给定序列的最短 LFSR。这个最短长度叫序列的线性复杂度。一个 128 位密钥的 LFSR，线性复杂度最多 128，只要 256 位已知明文就会被看穿。

有趣的是，这个算法最初是为了 Reed–Solomon 码和 BCH 码的解码而发明的。

3.4 怎么补救：加入非线性

非线性组合：几个 LFSR 的输出通过一个非线性布尔函数合并（如 Geffe 生成器，但设计不好会被相关攻击）；
非线性过滤：从一个 LFSR 的多个位置取值，送进非线性函数；
不规则步进：用一个 LFSR 控制另一个是否前进（A5/1 的做法）。

目标都是把线性复杂度推到接近序列长度，同时避免输出和单个 LFSR 之间的统计相关性。

总结

层次	要点
直觉	格子左移，异或回填，几个门就能生成长序列
代数	每步 $=$ 在 $\mathbb{F}_2[x]/(f)$ 中乘 $x$ ；本原多项式给出最大周期 $2^n - 1$
弱点	线性： $2n$ 个比特就能解出整个寄存器（Berlekamp–Massey）
现实	GPS、扰码、CRC 很好用；加密必须加非线性，A5/1、CSS 是反面教材

线性反馈移位寄存器：F2[x]\mathbb{F}_2[x]F2​[x] 上的本原多项式与流密码