3.6 线性反馈移位寄存器（LFSR）

实际序列密码使用的密钥位序列s_1, s_2, …是通过具有某些属性的密钥流生成器得到的。一种得到长伪随机序列的简单方法就是使用线性反馈移位寄存器（LFSR）。LFSR 很容易使用硬件实现，许多序列密钥都是利用 LFSR 来实现的，但并不是全部。最典型的例子就是 A5/1 密码，它也是 GSM 中的语音加密标准。我们将看到，尽管一个简单 LFSR 就可以产生良好统计属性的序列，但该序列在密码密码体制中确实非常脆弱的。然而，LFSR 组合可以得到安全的序列密码。

线性反馈移位寄存器（LFSR）

一个 LFSR 由若干存储元件（触发器）和一个反馈路径组成。存储元件的数目给出了 LFSR 的度。换而言之，一个拥有 m 个触发器的 LFSR 可以称为 “度为 m”。反馈网络计算移位寄存器中某些触发器的 XOR 和，并将其作为上一个触发器的输入。

LFSR 的数学描述

下图显示了一个度为m的 LFSR 的通用形式。从图中可以看出，此 LFSR 拥有m个触发器和m个可能的反馈位置，并且这些触发器和反馈位置之间通过 XOR 操作连接。某条反馈路径是否活跃则取决于反馈系数p_0, p_1, …, p_{m-1}：
1.如果p_i = 1（关闭开关），此反馈是活跃的。
2.如果p_i = 0（打开开关），对应触发器的输出将不会被反馈。
使用这种数学方法，我们可以得到反馈路径精准的数学描述。反馈系数的值对 LFSR 产生的输出序列非常重要。

该图为初始值为s_{m-1}, …, s_0、反馈系数为p_i的通用的 LFSR。
假设某个 LFSR 初始加载的值为s_0, …,s_{m-1}，则 LFSR 的下一个输出位s_m(即最左边触发器的输入)可以通过触发器的输出与对应的反馈系数的积的 XOR 和计算出来：

s_m = s_{m-1}p_{m-1} + ... + s_1p_1 + s_0p_0\ mod\ 2

下一个 LSFR 输出的计算式为：

s_{m +1} \equiv s_{m}p_{m-1} + ... +s_2p_1 + s_1p_0\ mod\ 2

归纳可以得出，输出序列可以描诉为：

s_{i+m} \equiv

归纳可以得出，输出序列可以描诉为：

\displaystyle s_{i+m}\equiv\sum_{j=0}^{m-1}p_j\cdot s_{i+j}\ mod\ 2;s_{i},p_{j}\epsilon\{0,1\};\\i=0,1,2...

显然，输出值都是前面一些输出值的组合形式。因此，LFSR 有时也称为线性递归。
由于可重复出现状态的数量有限，所以 LFSR 的输出系列会周期性重复。此外，LFSR 可以生成不同长度的输出序列，集体屈居于反馈系数。以下定理将 LFSR 的最大长度定义为其度的函数。

定理：度为\ m\ 的\ LFSR\ 可以产生的最大序列长度为 2^m-1

这个定理的证明非常简单。LFSR 的状态是由 m 个内部寄存器位唯一确定。给定某个状态，LFSR 可以推断出它的下一个状态。正因为如此，LFSR 只要得到了前一个状态，它马上开始重复，由于一个 m 位状态向量只能得到2^m-1个非零状态，因此在出现重复序列的最长长度为2^m-1.注意，必须排除所有为零的状态。如果某个 LFSR 的状态全零，它将会陷在这个状态中，即它永远都不可能离开这个状态。请记住，只有特定的设置(p_0,p_1,..,p_{m-1})才能得到最大长度的 LFSR。