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

上节课提到，流密码的流密钥产生器可以通过线性驱动和非线性组合两部分来实现。

而线性驱动部分可以由线性反馈移位寄存器（LFSR）来实现。

一、线性反馈移位寄存器（LFSR）引入

1、移位寄存器：

移位寄存器（Shift Register，SR）曾在SM4中提到过，是指有若干个寄存器排成一行，每个寄存器中都存储着一个二进制数（0或1）。移位寄存器每次把最右端（末端）的数字输出，然后整体向右移动一位。假设一个5位移位寄存器中存储着数据10110，则不断移位、输出的效果如图所示：

2、反馈移位寄存器：

在移位寄存器向右移位一位以后，左边就会空出一位（如上图所示），这时如果采用一个反馈函数，以寄存器中已有的某些序列作为反馈函数的输入，在函数中经过一定的运算后，将反馈函数输出的结果填充到移位寄存器的最左端，那么这样的移位寄存器就会有源源不断的输出。

这样的，拥有反馈函数的移位寄存器称为反馈移位寄存器（Feedback Shift Register，FSR）

3、线性反馈移位寄存器：

如果反馈移位寄存器的反馈函数是线性函数（即只进行简单线性运算的函数），那么这种寄存器就被称为线性反馈移位寄存器（Linear Feedback Shift Register，LFSR）。

二、线性反馈移位寄存器（LFSR）、m序列

1、LFSR的反馈函数：

LFSR的反馈函数就是简单地对移位寄存器中的某些位进行异或，

并将异或的结果填充到LFSR的最左端，如图所示。对于LFSR中每一位的数据，可以参与异或，也可以不参与异或。其中，我们把参与异或的位称为抽头。

2、LFSR的级数：

我们通常把LFSR中的寄存器个数称为LFSR的级数。一个3级的LFSR最多同时存放3位的数据，如下图所示：

状态的概念：
一个LFSR寄存器中当前存储的序列被称为一个状态。在LFSR输出一位，由反馈函数补充一位后，LFSR就移动到了下一个状态。

一个n级的LFSR最多只能存储2^n - 1种状态（为什么要减1？这里是减去了LFSR中全为0的情况。因为当LFSR中只有000时，这是反馈函数反馈回的值也永远是0，输出序列将一直是0。这是不可用的，因此要减1）例如，一个3级LFSR最多可以遍历001，010，011，100，101，110，111共7种状态。

3、LFSR的特征多项式：

4、LFSR的周期：

反馈函数特征多项式的阶，就是LFSR产生序列的周期（证明略）。
(GF(2)就是限制多项式的系数只能为0或者1)
例如：对于图9-5中的特征多项式，其对应的LFSR和反馈函数如图9-6所示。

图9-5说明了该特征多项式的阶为5，则可以验证发现，图9-6中LFSR的周期也为5（假设初始状态为0001）。（可以看出，图中状态的周期为5，输出的周期也为5）

5、m序列：

6、本原多项式：

三、对线性反馈移位寄存器（LFSR）的密钥流攻击