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

转载于（九）详解线性反馈移位寄存器（LFSR）

LFSR的由来

1. 移位寄存器：

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

2、反馈移位寄存器：

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

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

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

LFSR具体内容

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产生序列的周期（证明略）。
例如：
对于图9-5中的特征多项式，其对应的LFSR和反馈函数如图9-6所示。
图9-5说明了该特征多项式的阶为5，则可以验证发现，图9-6中LFSR的周期也为5（假设初始状态为0001）。
（可以看出，图中状态的周期为5，输出的周期也为5）

5、m序列：

6、本原多项式：

对LFSR的密钥流攻击

3、未知LFSR的反馈函数，也未知LFSR的级数n：

这时，我们不知道具体的反馈函数，也不知道其级数n，这就需要我们对截获的明密文序列获得的密钥序列进行分析。
如果求得的密钥序列有明显的周期，那么这个密钥序列一定是LFSR的生成序列，并且由周期，我们可以得出其级数n，并且确定其反馈函数。
我们把一个序列的最小周期称为它的线性复杂度。我们对序列密码的分析，即为求其线性复杂度和极小多项式。通常把线性复杂度和极小多项式称为这个序列的线性综合解。
一般来说，LFSR的线性复杂度越大，越不容易破解。但是LFSR的线性复杂度也不能太大，否则影响计算速度。另外，还要求LFSR生成的序列符合伪随机序列的条件。
受此限制，只使用LFSR来生成密钥流是不安全的，因此还需要使用非线性的生成方式。

延伸 书籍推荐

推荐读者查阅 <<应用密码学>> 这本书中的相应知识，讲的很清楚明白。还给出了 c 程序实现代码。