【密码学】（六）详解线性反馈移位寄存器（LFSR）

本文转载自：《现代密码学》课程笔记知乎专栏
仅作个人学习记录。

上节课提到，流密码的流密钥产生器可以通过线性驱动和非线性组合两部分来实现。而线性驱动部分可以由线性反馈移位寄存器（LFSR）来实现。

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

1、移位寄存器：

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

图9-1 移位寄存器示意图

2、反馈移位寄存器：

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

图9-2 反馈移位寄存器示意图

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

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

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

1、LFSR的反馈函数：

LFSR的反馈函数就是简单地对移位寄存器中的某些位进行异或，并将异或的结果填充到LFSR的最左端，如图所示。对于LFSR中每一位的数据，可以参与异或，也可以不参与异或。其中，我们把参与异或的位称为抽头。

图9-3 线性反馈移位寄存器示意图

如果移位寄存器中的值为 $a1,a_2,\ldots,a_nn+1a{n+1}=c1a_1\oplus c_2a_2\oplus\cdots\oplus c_na_n=\sum{i=1}^n c_ia_i\pmod2a_i$ 表示移位寄存器中的数据（0或1）； 表示第 位是否是抽头，如果是，则 ，表示该位将参与运算；如果不是，则 ，表示该位将不参与运算。上式表示了LFSR的一种递推关系，在这个式子中，可以明显看出， 将抽头位选出并留下来参与运算，并且将不是抽头的位剔除掉。

2、LFSR的级数：

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

图9-4 一个3级LFSR

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

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

3、LFSR的特征多项式：

如果一个LFSR的第 位可以表示为 （即上文提到的递推关系），则这个递推关系可以对应一个特征多项式 ，（这里的 与上文的 相同），即只保留抽头位次项，==最后还要加1。

[!example] 例子
对于上图9-4中的3级LFSR，其反馈函数为 $a{i+3}=a{i+1}\oplus a_if(x)=x^3+x+1$。

4、LFSR的周期：

同大多数密钥流产生器一样，LFSR也具有周期。由于一个 级LFSR最多只能遍历 种状态，因此，当LFSR移位到一定程度时，一定会出现重复的状态。而相同状态生成的反馈函数结果总是相同的，因此，LFSR会陷入一种循环，即LFSR存在周期。

可以明显看出，LFSR的周期与其反馈函数有很密切的关系，反馈函数决定了LFSR的循环序列。

我们先引入阶的概念：假设 是 上的多项式，使 成立的最小的 即为这个多项式的阶。（这里的 与上文提到的级数 不是一回事）阶往往也被称为周期。如下图所示，有 ，故 的周期为5。

图9-5 特征多项式的阶

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

图9-6 LFSR的周期

5、m序列：

为了能够产生足够安全的密钥，我们通常要求LFSR的周期能够足够大。上文提到，一个 级LFSR最多只能遍历 个状态，这也就是说，一个 级LFSR的最大周期就是 。

我们把周期为 的LFSR所生成的序列称为m序列。

6、本原多项式：

m序列LFSR反馈函数对应的特征多项式被称为本原多项式。

很明显， 级m序列LFSR的本原多项式的阶一定为 。

同理，如果一个 级LFSR的特征多项式的阶为 ，则这个多项式为本源多项式，并且这个LFSR生成的序列为m序列。

例如，对于一个3级LFSR，如果其反馈函数为 $a{i+3}=a{i+1}\oplus a_if(x)=x^3+x+1x^7\equiv1\pmod{f(x)}2^3-1$ 相等。因此这个LFSR的周期为7，其特征多项式为本原多项式，其生成的序列为m序列。如图所示：

图9-7 m序列举例

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

只使用LFSR来产生密钥是非常不安全的。下文将在几种情况下说明LFSR的易攻破性。

1、已知LFSR的反馈函数和级数n：

在这种情况下，如果破译者已知连续 位明文 ，和其对应的 位密文 ，则可以计算得出 位密钥 。这时，就已知了LFSR的一个状态，再根据反馈函数，即可计算出LFSR的全部密钥流，从而破解LFSR。

2、未知LFSR的反馈函数，但已知其级数n：

尽管这时我们失去了反馈函数的信息，但我们仍然可以拦截其连续 位的明文 $p1,p_2,\ldots,p{2n}2nc1,c_2,\ldots,c{2n}2nki=p_i\oplus c_i$。在这 个密钥中，蕴含着LFSR的 种状态，分别为 ，$(k_2,\ldots,k{n+1})(k3,\ldots,k{n+2})(k{n+1},\ldots,k{2n})k{n+1}k_1,\ldots,k_nk{2n}kn,\ldots,k{2n-1}nc_ic_i=1c_i=0$。

图9-8 状态之间的线性方程组

由这个线性方程组（ 个方程， 个未知数），可以唯一解出 个 的值。由此，我们可以得知LFSR中哪些位是抽头，也就可以确定LFSR的反馈函数了。从而，我们可以使用1中的方法，攻破LFSR。

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

这时，我们不知道具体的反馈函数，也不知道其级数n，这就需要我们对截获的明密文序列获得的密钥序列进行分析。

如果求得的密钥序列有明显的周期，那么这个密钥序列一定是LFSR的生成序列，并且由周期，我们可以得出其级数n，并且确定其反馈函数。

我们把一个序列的最小周期称为它的线性复杂度。我们对序列密码的分析，即为求其线性复杂度和极小多项式。通常把线性复杂度和极小多项式称为这个序列的线性综合解。

一般来说，LFSR的线性复杂度越大，越不容易破解。但是LFSR的线性复杂度也不能太大，否则影响计算速度。另外，还要求LFSR生成的序列符合伪随机序列的条件。

受此限制，只使用LFSR来生成密钥流是不安全的，因此还需要使用非线性的生成方式。（见下一篇）