• LFSR英文名为Linear feedback shift register，中文翻译过来就是线性反馈移位寄存器，其伪随机数生成的特点已经包含在LFSR的名称中，也就是线性、反馈这两个词。
  • 由于LFSR是非常容易使用硬件实现的，所以在以前很多流密码的密钥都是通过LFSR伪随机数生成算法来实现的，但是该伪随机数生成的算法在密码学体制中是比较不安全的，容易被预测到。
  • 本篇文章写于2025.6.16但是写的不怎么好，而在2025.9.11在图书馆随便看看，看到了这本书，从数学原理讲LSFR，于是决定重写博客，重新学习LSFR相关的。

image-20250911104035350

LFSR初步认识

  • LFSR是指给定前一状态的输出，将该输出的线性函数在用作输入的移位寄存器。其中异或运算是最常见的单比特线性函数，对寄存器的某些位进行异或操作后作为输入，再对寄存器中的各比特进行整体移位。也就是先进行异或运算再进行位移运算
  • LFSR是计算机可以比较快的构造出一个拟完美序列。

LFSR的两种形式

  • LFSR其实不止上面介绍的一种形式，其实还有另一种形式。
  • 对于上面介绍的这种，是比较经典的，将其称为Fibonacci型，其实就是指定抽头影响输入位。

image-20250622160519756

  • 还有一种LFSR类型，该类型为Galois型，这种类型是输出位送给输入位后逐位异或，从而影响其他位，得到伪随机。

image-20250622160529128

  • 大致介绍一下LFSR的工作流程：
    • 首先FF0、FF1、FF2、...、FFn会被初始化bit位。
    • 接着CLK时钟，发出一个脉冲，这就会使得
      • FFnFF_n的值输出出去（其中输出其实还要画一个箭头，这边只有参与异或的箭头），FFnFF_n的值会输出到两个地方，其中一个地方是输出给用户使用，另一个输出是参与生成下一个FF0的运算。
      • 接着FFn−1FF_{n-1}的值就会被输出（移动）到FFnFF_{n}这个寄存器中，FFn−2FF_{n-2}的值就会被输出（移动）到FFn−1FF_{n-1}这个寄存器中，以此类推，这就是移位
    • 输出的过程中，其实还会将输出的值输出给g1、g2、...、gng_1、g_2、...、g_{n}就会参与运算，运算的结果就是FF0FF_0的值，这就是反馈。
  • 上面就是LFSR的大致过程，接下来展示一个真实的LFSR电路图，由于LFSR的特性，其是比较容易在硬件中实现的，逻辑电路图并不复杂。其组成其实就是n个触发器，加上一些异或门再通过导线连接即可得到一个硬件的LFSR。

image-20250622160904448

LFSR算法描述

  • 我们先来给出一张图片，这张图片就简单介绍了LFSR算法。这张图主要做了一下几个事情：

    • 对于初始的状态anan−1...a2a1a_na_{n-1}...a_{2}a_{1}，经过一个线性函数f(a1,a2,...,an)f(a_1,a_2,...,a_n)的运算，其实f(a1,a2,...,an)f(a_1,a_2,...,a_n)这个线性函数就是异或操作，即f(a1,a2,...,an)=a1⊕a2⊕...⊕anf(a_1,a_2,...,a_n)=a_1\oplus a_2 \oplus ...\oplus a_n,得到一个结果作为我们后续的输入的bit值，所以这个函数运算结果只有0或者1，先暂时保存这个值

    • 之后将anan−1...a2a1a_na_{n-1}...a_2a_1经过位移后整体就变成an−1an−2...a1a0a_{n-1}a_{n-2}...a_1a_0，此时a0a_0其实就是作为输出值了

    • 最后我们再将f(a1,a2,...,an)f(a_1,a_2,...,a_n)运算得到的结果传递给ana_n，此时就构成了新的一组anan−1...a2a1a_na_{n-1}...a_2a_1序列

    • 之后像这样不断的线性位移计算，我们就能得到这些二进制序列，我们每线性位移n次取一次序列，这样就得到了n位伪随机数

    • 注意：不一定所有的位都参与线性运算，一般只选择几个位参与线性运算

image-20250622160603602

有几个注意点：

  1. 将参与线性运算f(a1,a2,...,an)f(a_1,a_2,...,a_n)的位称为抽头，也就是LFSR状态下影响输入的位
  2. LFSR最右边的位为输出位，同时它始终也是抽头。
  3. 抽头是有顺序的异或，然后反馈到最左边的位。
  4. 最右边的位序列称为输出流，如上图所示其实我们的输出流其实是a1a_1先输出出来,然后a2a_2，最后才是ana_n
  5. 最大长度LFSR产生m序列具有2m−12^m-1种状态，寄存器全零状态的时候线性位移后还是全零（关于m序列的概念这里不多说）
  • 接下来我们使用Python实现一下简单的32位LFSR伪随机数：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def _int32(x):
    return x & 0xFFFFFFFF

class LFSR:
    def __init__(self,seed):
        # seed作为初始化寄存器的一个种子
        # 规定二进制序列是这样的an an-1 ... a2 a1与上图描述一致
        self.seed = _int32(seed)

    def xor(self):
        # 规定a26 a16 a11 a1都作为抽头
        x = bin(self.seed)[2:].zfill(32)
        tap = [25,15,10,0]
        tmp = 0
        for i in tap:
            tmp ^=int(x[i],2)
        return tmp

    def lshift(self,an,reg):
        # 进行位移运算
        return _int32((an<<31)|(reg>>1))

    def LSF(self):
        # 生成32位的随机数
        # 其实也可以直接LSF一次,而不用32次
        for i in range(32):
            an = self.xor()
            self.seed=self.lshift(an,self.seed)
        return self.seed

LFSR = LFSR(0xF75a15663499)
for i in range(10):
    print(LFSR.LSF())

  • 在实际过程中，一般会有一个mask，这个mask的作用一般就是作为反馈系数进行异或操作，将初始序列和mask进行与操作这样
  • 下面是带有mask的LFSR简单实现代码：
1
1

LFSR数学表示

LFSR例子

  • 先举一个例子看看：Z2Z_2上周期为7的拟完美序列如下：

    • α=1001011...=a0a1a2a3a4a5a6....\alpha=1001011...=a_0a_1a_2a_3a_4a_5a_6....，观察a0、....、a7a_0、....、a_7这七个数之间的关系。
    • 注意到有如下关系，发现前三位a0、a1、a2a_0、a_1、a_2确定下来了，这个序列的关系就可以确定了：

    a3=a1+a0a4=a2+a1a5=a3+a2a6=a4+a3a7=a0=a5+a4a_3=a_1+a_0\\a_4=a_2+a_1\\a_5=a_3+a_2\\a_6=a_4+a_3\\a_7=a_0=a_5+a_4

    • 这样我们可以通过递推公式写出来关系式：ak+3=ak+1+ak,(k=0,1,2...)a_{k+3}=a_{k+1}+a_{k},(k=0,1,2...)，这是一个三阶递推公式。

LFSR数学推导

  • 从上面的LFSR例子可以看到，我们用递推关系很好表示出来这个序列，所以一开始我们就使用递推公式来描述LFSR。
  • 对于LFSR来说，需要有周期，并且周期长，这样才是好的LFSR，所以接下来需要研究它的周期。在研究周期之前，除了递推这个数学描述之外，LFSR还可以用矩阵描述、特征多项式描述，接下来通过递推公式逐渐引入这两个描述。
  • 考虑一个Z2Z_2上的n阶线性常系数齐次递推关系式，可以用LFSR实现这个递推序列，接下来要研究它是否有周期，周期是否很大：
    • ak+n=c1ak+n−1+c2ak+n−2+...+cn−1ak+1+cnak,(k=0,1,2,...,cn≠0)a_{k+n}=c_1a_{k+n-1}+c_2a_{k+n-2}+...+c_{n-1}a_{k+1}+c_na_{k},(k=0,1,2,...,c_n≠0)该式子记为①
    • 设正整数dd是序列α=a0a1a2...\alpha=a_0a_1a_2...的一个周期，定义式子为：ai+d=aia_{i+d}=a_{i}该式子记为②，满足②式的最小正整数ll称为α\alpha的最小正周期。
    • 等价条件：uu是α\alpha的周期⇔u\Leftrightarrow u是最小正周期ll的正整数倍
  • 目前来说只有一个递推式子研究周期还是比较困难的，所以我们引入如下方程组：

{ak+n=c1ak+n−1+c2ak+n−2+...+cn−1ak+1+cnakak+n−1=ak+n−1ak+n−2=ak+n−2⋮ak+1=ak+1\begin{cases} \begin{array}{l} a_{k+n}&=c_1a_{k+n-1}+&c_2a_{k+n-2}+&...+&c_{n-1}a_{k+1}+&c_na_{k}\\ a_{k+n-1}&=a_{k+n-1}\\ a_{k+n-2}&=&a_{k+n-2}\\ \vdots\\ a_{k+1}&=&&&a_{k+1} \end{array} \end{cases}

  • 这样一来就可以写成向量矩阵的形式，描述如下，从而记A=[c1c2…cn−1cn10…0001…00⋮⋮⋱⋮⋮00…10]A = \begin{bmatrix} c_1&c_2&\dots&c_{n-1}&c_n\\ 1&0&\dots&0&0\\ 0&1&\dots&0&0\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&\dots&1&0 \end{bmatrix}称为递推关系①式的生成矩阵：

(ak+nak+n−1ak+n−2⋮ak+1)=[c1c2…cn−1cn10…0001…00⋮⋮⋱⋮⋮00…10](ak+n−1ak+n−2ak+n−3⋮ak)\begin{pmatrix} a_{k+n} \\ a_{k+n-1}\\ a_{k+n-2}\\ \vdots \\ a_{k+1} \end{pmatrix}=\begin{bmatrix} c_1&c_2&\dots&c_{n-1}&c_n\\ 1&0&\dots&0&0\\ 0&1&\dots&0&0\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&\dots&1&0 \end{bmatrix} \begin{pmatrix} a_{k+n-1} \\ a_{k+n-2}\\ a_{k+n-3}\\ \vdots \\ a_{k} \end{pmatrix}

  • 接下来对于初始值a0,a1,...,an−1a_0,a_1,...,a_{n-1}如果确定了，我们希望各个位数求出来，

    • 对于上述式子，我们令k=0k=0那么我们就有：

    (anan−1an−2⋮a1)=A(an−1an−2an−3⋮a0)\begin{pmatrix} a_{n} \\ a_{n-1}\\ a_{n-2}\\ \vdots \\ a_{1} \end{pmatrix}=\mathbf{A} \begin{pmatrix} a_{n-1} \\ a_{n-2}\\ a_{n-3}\\ \vdots \\ a_{0} \end{pmatrix}

    • 令k=1k=1就有：

    (an+1anan−1⋮a2)=A(anan−1an−2⋮a1)=A2(an−1an−2an−3⋮a0)\begin{pmatrix} a_{n+1} \\ a_{n}\\ a_{n-1}\\ \vdots \\ a_{2} \end{pmatrix}=\mathbf{A} \begin{pmatrix} a_{n} \\ a_{n-1}\\ a_{n-2}\\ \vdots \\ a_{1} \end{pmatrix}=\mathbf{A}^{2}\begin{pmatrix} a_{n-1} \\ a_{n-2}\\ a_{n-3}\\ \vdots \\ a_{0} \end{pmatrix}

    • 以此类推就有，这样不就有了个类似于通项公式的东西了么，我们将下面的式子记为④式

    (ak+n−1ak+n−2ak+n−3⋮ak)=Ak(an−1an−2an−3⋮a0)\begin{pmatrix} a_{k+n-1} \\ a_{k+n-2}\\ a_{k+n-3}\\ \vdots \\ a_{k} \end{pmatrix}=\mathbf{A}^{k} \begin{pmatrix} a_{n-1} \\ a_{n-2}\\ a_{n-3}\\ \vdots \\ a_{0} \end{pmatrix}

命题1：

dd是由nn阶递推关系①式产生的Z2Z_2上序列α=a0a1a2...an−1...\alpha=a_0a_1a_2...a_{n-1}...的一个周期的充分必要条件是Ad(an−1an−2an−3⋮a0)=(an−1an−2an−3⋮a0)\mathbf{A}^{d}\begin{pmatrix}a_{n-1} \\ a_{n-2} \\ a_{n-3} \\ \vdots \\ a_{0} \end{pmatrix} = \begin{pmatrix} a_{n-1} \\ a_{n-2} \\ a_{n-3} \\ \vdots \\ a_{0} \end{pmatrix}

推论1：

若Ad−I=0A^{d}-I=0，则dd是①式产生的任意序列的周期

  • 证明：

    • 由dd是序列的周期就可以得到：ai+d=ai,i=0,1,2...a_{i+d}=a_i,i=0,1,2...
    • 利用递推关系①式⇒\Rightarrow(ad+n−1ad+n−2ad+n−3⋮ad)=(an−1an−2an−3⋮a0)\begin{pmatrix}a_{d+n-1} \\ a_{d+n-2} \\ a_{d+n-3} \\ \vdots \\ a_{d} \end{pmatrix}=\begin{pmatrix}a_{n-1} \\ a_{n-2} \\ a_{n-3} \\ \vdots \\ a_{0} \end{pmatrix}，这个式子再由④式得到：Ad(an−1an−2an−3⋮a0)=(an−1an−2an−3⋮a0)\mathbf{A}^{d}\begin{pmatrix}a_{n-1} \\a_{n-2}\\a_{n-3}\\\vdots \\a_{0}\end{pmatrix}=\begin{pmatrix}a_{n-1} \\a_{n-2}\\a_{n-3}\\\vdots \\a_{0} \end{pmatrix}
    • 这就得到了(an−1an−2an−3⋮a0)\begin{pmatrix}a_{n-1} \\a_{n-2}\\a_{n-3}\\\vdots \\a_{0} \end{pmatrix}是AdA^{d}的属于特征值1的一个特征向量。
    • 从而就有(Ad−I)(an−1an−2an−3⋮a0)=0(A^{d}-I)\begin{pmatrix}a_{n-1} \\ a_{n-2} \\ a_{n-3} \\ \vdots \\ a_{0} \end{pmatrix}=0

  • 回过来看式子①：

    • 通过一系列的递推我们就可以得到如下的方程组：

    {an+n−1=c1an+n−2+...+cn−1an+cnan−1⋮an+1=c1an+...+cn−1a2+cna1an=c1an−1+...+cn−1a1+cna0\begin{cases} \begin{array}{l} a_{n+n-1}&=c_1a_{n+n-2}+...+c_{n-1}a_{n}+c_na_{n-1}\\ \vdots\\ a_{n+1}&=c_1a_n+...+c_{n-1}a_2+c_{n}a_1\\ a_{n}&=c_1a_{n-1}+...+c_{n-1}a_1+c_na_0 \end{array} \end{cases}

    • 写成向量的的形式，这一看这个结构不就是线性表出

    (an+n−1an+n−2an+n−3⋮an)=c1(an+n−2an+n−3an+n−3⋮an−1)+...+cn−1(anan−1an−2⋮a1)+cn(an−1an−2an−3⋮a0)\begin{pmatrix} a_{n+n-1} \\ a_{n+n-2} \\ a_{n+n-3} \\ \vdots \\ a_{n} \end{pmatrix}= c_1\begin{pmatrix}a_{n+n-2} \\ a_{n+n-3} \\ a_{n+n-3} \\ \vdots \\ a_{n-1} \end{pmatrix} +...+c_{n-1}\begin{pmatrix}a_{n} \\ a_{n-1} \\ a_{n-2} \\ \vdots \\ a_{1} \end{pmatrix} +c_n\begin{pmatrix}a_{n-1} \\ a_{n-2} \\ a_{n-3} \\ \vdots \\ a_{0} \end{pmatrix}

    • 再使用④式(ak+n−1ak+n−2ak+n−3⋮ak)=Ak(an−1an−2an−3⋮a0)\begin{pmatrix} a_{k+n-1} \\ a_{k+n-2}\\ a_{k+n-3}\\ \vdots \\ a_{k} \end{pmatrix}=\mathbf{A}^{k} \begin{pmatrix} a_{n-1} \\ a_{n-2}\\ a_{n-3}\\ \vdots \\ a_{0} \end{pmatrix}带入到上面的向量形式的方程就有如下，对于一切a0,a1,...,an−1∈Z2a_0,a_1,...,a_{n-1}\in Z_2都成立，记下面的式子为⑤式

    (An−c1An−1−...−cn−1A1+cnI)(an−1an−2an−3⋮a0)=(000⋮0)(A^{n}-c_1A^{n-1}-...-c_{n-1}A^{1}+c_nI)\begin{pmatrix}a_{n-1} \\a_{n-2}\\a_{n-3}\\\vdots \\a_{0} \end{pmatrix}=\begin{pmatrix}0 \\0\\0\\\vdots \\0 \end{pmatrix}

    • 由一个矩阵乘上任意一向量都是零矩阵，那么这个矩阵一定是零矩阵，可以得到，记该式子为⑥式：

    An−c1An−1−...−cn−1A1+cnI=0A^{n}-c_1A^{n-1}-...-c_{n-1}A^{1}+c_nI=0

    • 令f(x)=xn−c1xn−1−...−cn−1x−cn∈Z2[x]f(x)=x^{n}-c_1x^{n-1}-...-c_{n-1}x-c_n\in Z_2[x]，此时f(A)=0f(A)=0，只要递推关系式①给了，我们就能确定这个多项式。而多项式和递推关系可以互推，这样的多项式我们就称为递推关系式①的特征多项式。从而有命题⑥

命题2

设f(x)f(x)是nn阶递推关系式①的特征多项式，A是①的生成矩阵则f(A)=An−c1An−1−...−Cn−1A−cnI=0f(A)=A^{n}-c_1A^{n-1}-...-C_{n-1}A-c_nI=0

定理1

设f(x)f(x)是nn阶递推关系式①的特征多项式，A是①的生成矩阵，若f(x)∣xd−1f(x)|x^{d}-1，则dd是nn阶递推关系①产生的任意序列的周期。

  • 证明：
    • 存在h(x)∈Z2[x]h(x)\in Z_2[x]使得xd−1=h(x)f(x)x^{d}-1=h(x)f(x)，用生成矩阵AA带入xx得到
    • 可以得到：Ad−I=h(A)f(A)=0A^{d}-I=h(A)f(A)=0
    • 由推论1可以得到dd是nn阶递推关系①产生的任意序列的周期。

定理2

设f(x)f(x)是nn阶递推关系式①的特征多项式，A是①的生成矩阵，设f(x)f(x)在Z2Z_2上不可约，若dd是nn阶递推关系①产生的一个非零序列α=a0a1...an−1an...\alpha = a_0a_1...a_{n-1}a_n...的一个周期，则f(x)∣xd−1f(x)|x^{d}-1

  • 证明：使用反证法证明
    • 假设f(x)∤xd−1f(x)\not|x^d-1，则(f(x),xd−1)=1(f(x),x^{d}-1)=1
    • 从而存在u(x),v(x)∈Z2[x]u(x),v(x)\in Z_2[x]，使得u(x)f(x)+v(x)(xd−1)=1u(x)f(x)+v(x)(x^{d}-1)=1，这个式子就是裴蜀定理在多项式中的推广
    • xx用生成矩阵AA带入，就有u(A)f(A)+v(A)(Ad−I)=Iu(A)f(A)+v(A)(A^{d}-I)=I
    • 由命题2可以得到v(A)(Ad−I)=Iv(A)(A^{d}-I)=I，v(A)(Ad−I)(an−1an−2an−3⋮a0)=(an−1an−2an−3⋮a0)v(A)(A^{d}-I)\begin{pmatrix} a_{n-1} \\ a_{n-2}\\ a_{n-3}\\ \vdots \\ a_{0} \end{pmatrix}=\begin{pmatrix} a_{n-1} \\ a_{n-2}\\ a_{n-3}\\ \vdots \\ a_{0} \end{pmatrix}
    • 从而得到(000⋮0)=(an−1an−2an−3⋮a0)\begin{pmatrix}0 \\ 0 \\ 0 \\ \vdots \\0\end{pmatrix}=\begin{pmatrix}a_{n-1} \\a_{n-2}\\a_{n-3}\\ \vdots \\ a_{0} \end{pmatrix}，与α\alpha是非零序列矛盾。
  • 我们还希望这个nn阶递公式的生成的任意序列都有周期，接下来我们就要从特征多项式入手：
    • 由⑥式An−c1An−1−...−cn−1A−cnI=0A^{n}-c_1A^{n-1}-...-c_{n-1}A-c_nI=0可以得到：An=c1An−1+...+cn−1A+cnIA^{n}=c_1A^{n-1}+...+c_{n-1}A+c_nI记为式子⑦
    • 从而：An+1=c1An+c2An−1+...+cn−1A2+CnA=c1(c1An−1+...+cn−1A+cnI)+...+cnAA^{n+1}=c_1A^{n}+c_2A^{n-1}+...+c_{n-1}A^2+C_nA=c_1(c_1A^{n-1}+...+c_{n-1}A+c_nI)+...+c_nA
    • 说明AA的任意非负整数次幂都可以属于下面这个集合：Ω={b1An−1+b2An−2+...+bn−1A+bnI∣bi∈Z2,i=1,2,....}\Omega=\{b_1A^{n-1}+b_2A^{n-2}+...+b_{n-1}A+b_nI|b_i \in Z_2,i=1,2,....\}
    • 而Ω\Omega这个集合中元素个数有2n2^{n}个，但是有些AA的次幂可以由多个多项式生成相同的结果，所以∣Ω∣≤2n|\Omega|≤2^n
    • 从而Ω\Omega中的非零矩阵至多有2n−12^{n}-1个，下述2n2^{n}个矩阵，I,A,A2,...,A2n−1I,A,A^{2},...,A^{2^{n}-1}，由于生成矩阵∣A∣=cn≠0|A|=c_n≠0，因此AA可逆矩阵。
    • 从而上述2n2^n个矩阵都是非零矩阵，于是存在一对i,ji,j满足：Ai=Aj,0≤i<j≤2n−1A^{i}=A^{j},0≤i<j≤2^{n}-1，从而就有I=Aj−iI=A^{j-i}，即Aj−i−I=0A^{j-i}-I=0
    • 由推论1可以得到，j−ij-i是nn阶递推关系①产生的任意序列的周期
    • 从而任何一个①产生的任意序列的最小正周期l≤j−i≤2n−1l≤j-i≤2^{n}-1，于是得到定理3

定理3

nn阶递推关系①产生的任一序列都有周期，并且最小正周期不超过2n−12^{n}-1

  • 我们希望周期越大越好，所以引入了如下的定义

定义1

设α\alpha是Z2Z_2上nn阶常系数线性齐次递推关系产生的序列，如果α\alpha的最小正周期达到2n−12^{n}-1，那么称α\alpha是Z2Z_2上的一个m序列。

  • 最后我们还要分析，这个线性递推关系满足的什么条件才会是m序列，于是推导出了定理4，接下来先分析一下：
    • 由定理1可以得到若f(x)∣x2n−1−Tf(x)|x^{2^n-1}-T则2n−12^{n-1}是α\alpha的一个周期。
    • α\alpha的最小正周期l∣2n−1l|2^{n}-1
    • 那么我们希望：对于d∣2n−1d|2^{n}-1，且0<d<2n−10<d<2^{n}-1，dd不是α\alpha的周期。若f(x)f(x)在Z2Z_2上不可约，且f(x)∤xd−1f(x)\not|x^{d}-1则根据定理2得到，dd不是α\alpha的周期。

定理4

设f(x)f(x)是nn阶递推关系①的特征多项式，如果满足：

  1. f(x)f(x)在Z2Z_2上不可约
  2. f(x)∣x2n−1−Tf(x)|x^{2^{n}-1}-T
  3. 对于d∣2n−1d|2^{n}-1，且0＜d＜2n−10＜d＜2^{n-1}，都有f(x)∤xd−1f(x)\not|x^{d}-1

那么①产生的任一非零序列α\alpha是m序列

定义2

Z2Z_2上的一个nn次多项式f(x)f(x)如果满足定理4中的三个条件，那么称f(x)f(x)是Z2Z_2上的一个本原多项式（这个本原多项式与有理数上的本原多项式是不同的概念）

注：从定义2出发，我们可以重新这样叙述定理4，如果nn阶递推关系①的多项式是Z2Z_2上的本原多项式，那么①产生的任何序列都是m序列。

定理5

Z2Z_2上的m序列都是拟完美序列。

总结

命题1：

dd是由nn阶递推关系①式产生的Z2Z_2上序列α=a0a1a2...an−1...\alpha=a_0a_1a_2...a_{n-1}...的一个周期的充分必要条件是Ad(an−1an−2an−3⋮a0)=(an−1an−2an−3⋮a0)\mathbf{A}^{d}\begin{pmatrix}a_{n-1} \\a_{n-2}\\a_{n-3}\\\vdots \\a_{0}\end{pmatrix}=\begin{pmatrix}a_{n-1} \\a_{n-2}\\a_{n-3}\\\vdots \\a_{0} \end{pmatrix}

推论1：

若Ad−I=0A^{d}-I=0，则dd是①式产生的任意序列的周期

命题2

设f(x)f(x)是nn阶递推关系式①的特征多项式，A是①的生成矩阵则f(A)=An−c1An−1−...−Cn−1A−cnI=0f(A)=A^{n}-c_1A^{n-1}-...-C_{n-1}A-c_nI=0

定理1

设f(x)f(x)是nn阶递推关系式①的特征多项式，A是①的生成矩阵，若f(x)∣xd−1f(x)|x^{d}-1，则dd是nn阶递推关系①产生的任意序列的周期。

定理2

设f(x)f(x)是nn阶递推关系式①的特征多项式，A是①的生成矩阵，设f(x)f(x)在Z2Z_2上不可约，若dd是nn阶递推关系①产生的一个非零序列α=a0a1...an−1an...\alpha = a_0a_1...a_{n-1}a_n...的一个周期，则f(x)∣xd−1f(x)|x^{d}-1

定理3

nn阶递推关系①产生的任一序列都有周期，并且最小正周期不超过2n−12^{n}-1

定义1

设α\alpha是Z2Z_2上nn阶常系数线性齐次递推关系产生的序列，如果α\alpha的最小正周期达到2n−12^{n}-1，那么称α\alpha是Z2Z_2上的一个m序列。

定理4

设f(x)f(x)是nn阶递推关系①的特征多项式，如果满足：

  1. f(x)f(x)在Z2Z_2上不可约
  2. f(x)∣x2n−1−Tf(x)|x^{2^{n}-1}-T
  3. 对于d∣2n−1d|2^{n}-1，且0＜d＜2n−10＜d＜2^{n-1}，都有f(x)∤xd−1f(x)\not|x^{d}-1

那么①产生的任一非零序列α\alpha是m序列

定义2

Z2Z_2上的一个nn次多项式f(x)f(x)如果满足定理4中的三个条件，那么称f(x)f(x)是Z2Z_2上的一个本原多项式（这个本原多项式与有理数上的本原多项式是不同的概念）

注：从定义2出发，我们可以重新这样叙述定理4，如果nn阶递推关系①的多项式是Z2Z_2上的本原多项式，那么①产生的任何序列都是m序列。

定理5

Z2Z_2上的m序列都是拟完美序列。

LFSR相关题目

  • 大概了解完LFSR的代码实现以及数学表示了，那么就可以来牛刀小试一下一些题目。
  • 题目难度依次递增，比较适合LFSR入门。

LFSR 题目1 求反馈系数

  • 题目来源：简单的LFSR，题目地址：攻防世界
  • 题目附件如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from secret import secret
for b in secret: assert(b == '0' or b == '1')
assert(len(secret) == 128)
# a 01 string with length 128
# your flag is flag{md5(secret).hexdigest()}

def string2bits(s):
    return [int(b) for b in s]

def lfsr(state, mask):
    assert(len(state) == 128)
    assert(len(mask)  == 128)

    output = 0
    for i in range(128):
        output = output + (state[i] * mask[i])

    return output

if __name__ == '__main__':
    initState = [0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0]
    mask = string2bits(secret)

    for i in range(256):
        state = initState[i:]
        output = lfsr(state, mask)
        initState += [output]

    outputState = initState[128:]
    print('outputState =', outputState)
    #
    # outputState = [31, 66, 128, 222, 385, 664, 1143, 2000, 3458, 6003, 10379, 17942, 31047, 53687, 92924, 160797, 278304, 481638, 833479, 1442422, 2496163, 4319845, 7475835, 12937561, 22389578, 38746915, 67054735, 116043520, 200822710, 347539886, 601445745, 1040850538, 1801275628, 3117252874, 5394657302, 9335889442, 16156509611, 27960142496, 48387281659, 83738092531, 144915522009, 250787996657, 434008851435, 751087316130, 1299817167363, 2249438425629, 3892834588915, 6736864173067, 11658686709797, 20176297502410, 34916709837729, 60426182042628, 104572380769600, 180970937597032, 313184800936842, 541991553121913, 937960088661442, 1623215570164618, 2809105439634215, 4861383488449105, 8413016146818879, 14559402864389777, 25196220721365800, 43604091771673155, 75460397027739861, 130590302153314191, 225997048627046433, 391106116962451401, 676840674047358730, 1171327366605398299, 2027076463289970382, 3508019282374090135, 6070910253447116278, 10506199749411485204, 18181825882182859769, 31465115864423937634, 54452920337985370536, 94235169707018163674, 163081560265112209496, 282225790871820528073, 488414489680745790033, 845240659945376349091, 1462757121910708796880, 2531419155626961478438, 4380824981460105751921, 7581370898424646092677, 13120173698498971899800, 22705518590912550882405, 39293730885686099313323, 68000969928723717268434, 117681162033195064953557, 203656740661184789826464, 352444412513853856490154, 609933476834387348179796, 1055539066458205919344242, 1826695472762162772755920, 3161243819621244340994611, 5470787351316040252901913, 9467638673598260118507327, 16384512191330329194463349, 28354719587732695891973236, 49070128760035595469947547, 84919814815174884654495265, 146960587438213290271803310, 254327147405947343219170013, 440133637427387650641676733, 761686751771954639615932308, 1318160346062225166536927204, 2281182774793880566386854202, 3947770745464875128215489476, 6831935621711193478803584270, 11823215517979626989252654459, 20461027873324936552011726278, 35409458704049766870463574070, 61278923692217093991616774374, 106048118957748860598268928024, 183524821535095103500935105397, 317604503036094959823791626415, 549640204006492782256703506357, 951196695803666227643791343005, 1646122586216645151673646795131, 2848747878127492747395146497119, 4929987925010971381846789176787, 8531741656523753626888968333475, 14764866932914585711739993009471, 25551792860485990447357753377411, 44219438031623458174827090101591, 76525303351860239321171606062486, 132433208420836012247860425341878, 229186346534231007543300455047052, 396625454174562824696341867974807, 686392332170111774628387415187708, 1187857281228776953526538661167132, 2055682813511567389589959681437591, 3557524878237416677051445431119245, 6156583679200434562674367324375645, 10654464521349051207718915685250792, 18438410026033851006551039004948926, 31909155416202798852780253976608864, 55221366589513932226781115179478434, 95565027912492621164419094117570641, 165382987128929746587819720020389833, 286208595645816231325692474821432127, 495307054513959920117280296979778603, 857168799202977606481906830566592959, 1483399728776458203402121501599814357, 2567142851419860475561591348189292465, 4442647717774532025797522076302827645, 7688360128977964468508623330874749520, 13305327189541069887965447505836108943, 23025941637865784521234444191415083701, 39848248807227476288131461546822173104, 68960607908058729168472941626927516912, 119341892941264496254850267375680858596, 206530769418287872448439164819365157712, 357418151038572249261836365381689027787, 618540932431735991718001801386896334770, 1070434962471260463170389697079661487176, 1852474022011964581139009223827365513544, 3205855677870125101423860144920010424249, 5547991769498476629256700835469967207037, 9601247144996961660705018593534913225922, 16615732425220501988109900409620796156745, 28754864847988594478375696246052761203187, 49762612400465240380187427652132912229336, 86118213596547492163397334421181607606370, 149034513167786192667574788821667110253623, 257916243121530494722068502259305736264048, 446344856986474817826595353109273441918350, 772435768089263602359077702861161388353409, 1336762385595787378549468975393213339116484, 2313375104267880490155624917599100889633507, 4003482167596451918353914186255524345816532, 6928348730257112541629154203810355027525535, 11990066177033590775605142065871666200189459, 20749776393589512464840020374644649655647874, 35909161302935015278730531942138798319507636, 62143699335409560081369603141161471393159562, 107544682943462043814216772302622710407400704, 186114746194704481727730115452186541297539854, 322086576510057527551600558671512063007190557, 557396793585831655018738502556644467159583633, 964620099559052960425720416252526682882655111, 1669352868873354804885622348664567494237803783, 2888949755545809136243688064556192446919868175, 4999560515746991945989073252770067125902428535, 8652142635098861248148452777057412533362877977, 14973230535426489152060521332311783517581989420, 25912382876992006096351135796067625851883928825, 44843468133024591960270046213401958144446811548, 77605237763877474989955856305494246316739147127, 134302122006319171731632762048131880552676359659, 232420652202367984596938247872208285088912788686, 402222680946414142984184322215356821073359953948, 696078784456971603910909918744734815016448573082, 1204620468022900362280402553035290601874308600586, 2084692860035604927076197374205039877760447754956, 3607729103106034863624554004184342562208475089341, 6243466138784576918107250594832177417637788944304, 10804821623826866941723224844111388709787418308073, 18698615116609470739339911758664365362637188157227, 32359461308280335893458609544003265039362932173740, 56000657248244594858300036379967633467510318826268, 96913653239119041752111865895809664169241405330164, 167716892009274048794745102986623447430717183044189, 290247606246426020117292750048691625438809474898504, 502296888062545512718475829352732508523042936581530, 869265269816240261877029457458234318249621243667628, 1504333646627354107869007496936781479204707239575364, 2603370684363759081777877568090078592049534352669947, 4505342904082185194291963661562434728467247085801567, 7796859204598587173314308958000104480418858953375158, 13493093589225451977147040588861591346827624626553088, 23350886533928418622148518003626067086836308029229306, 40410592153292809121198774051487713973447271440824879, 69933788415571610361075397290260005189363125951186151, 121026060286409890014591649872661507384922097295622585, 209445356819655999941471437498154462693217873859873519, 362462079567824464738504374835340908769751488853277318, 627269857492024846036766185061792395514128412691597750, 1085541071185182881358902065797900004206275433304525877, 1878616361292087979017649753948129817575491489985996469, 3251097104102362704835900720328806405351210311448488910, 5626285705844227224482132571164442587287950705132698177, 9736741115435595736854097976874400909429981720207988487, 16850215667245180941552990697851306753178430167486844006, 29160657006948951882262364132481449161390275730087294685, 50464868454466647556267645846637274956572498586114427735, 87333524327649631040132103644841977096784627243509857937, 151137706390139040826448707126591974417399010694640174718, 261555988593488478677610370284679511774525269175612894617, 452643730033345117036459086235348615186246366652477694168, 783336475835524143955537154153262203019092265959952337070, 1355626939379487620769121922144227585175531097052439217983, 2346021735820790423533561047507688175516954900918138334291, 4059979796110323903393797058491537625611005518946149411026, 7026122432346967683382009847205881024752630926437218981740, 12159271452933065576710291263470354882115951853620136774055, 21042599768180623908382939506716338579508214228553692875423, 36415915765826987773364669427220163018133640081486671468436, 63020678797925209300085103082659626905494796721119527734083, 109062366622625198169859916735972641477602693706580750774247, 188741220186912829686057249397861922209555075583934877024777, 326631901551406455092777938653826814900794821912935940782874, 565262845103114204256414747869081614169923740442179762058936, 978232936025018959853100287323851115023773163216042197843195, 1692910980111501346802672231436092377546116455476214539222026, 2929718966760270262844895994547637314231078419236801672684198, 5070114923366815738216357619638190602226980891746062079428250, 8774242726964718704518978915749604855301897112378619823447909, 15184534590503864395968205111669668293209355696392197598100449, 26278061583779512058870924747917968681797893736357134971437061, 45476304623307832769415233578427592641287934525440233150419102, 78700412341998941621862709864667467345902574612843786168968091, 136197409928206718914848388530217366761295027423898231594892758, 235700600786468895717413188934153824796333855958950958366797470]

LFSR 题目2 求初始状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
flag = "flag{xxxxxxxxxxxxxxxx}"
assert flag.startswith("flag{")
assert flag.endswith("}")
assert len(flag)==14

def lfsr(R,mask):
    output = (R << 1) & 0xffffffff
    i=(R&mask)&0xffffffff
    lastbit=0
    while i!=0:
        lastbit^=(i&1)
        i=i>>1
    output^=lastbit
    return (output,lastbit)


R=int(flag[5:-1],16)
mask = 0b10100100000010000000100010010100

f=open("key","w")
for i in range(100):
    tmp=0
    for j in range(8):
        (R,out)=lfsr(R,mask)
        tmp=(tmp << 1)^out
    f.write(chr(tmp))
f.close()

  • key文件如下：
1

LFSR破解

  • 对于LFSR的破解需要用上一个经典的算法也就是 Berlekamp-Massey算法。这里建议先去学习一下Berlekamp-Massey算法，先从它的数学抽象出来的问题入手，在破解LFSR的时候会更有助于理解。Berlekamp–Massey 算法 - OI Wiki
  • 对于Berlekamp-Massey算法，就不在这里详细介绍，这里只介绍Berlekamp-Massey算法在破解LFSR中的应用。