LFSR伪随机数生成器
LFSR英文名为Linear feedback shift register，中文翻译过来就是线性反馈移位寄存器，其伪随机数生成的特点已经包含在LFSR的名称中，也就是线性、反馈这两个词。- 由于
LFSR是非常容易使用硬件实现的，所以在以前很多流密码的密钥都是通过LFSR伪随机数生成算法来实现的，但是该伪随机数生成的算法在密码学体制中是比较不安全的，容易被预测到。 - 本篇文章写于
2025.6.16但是写的不怎么好，而在2025.9.11在图书馆随便看看，看到了这本书，从数学原理讲LSFR，于是决定重写博客，重新学习LSFR相关的。
LFSR初步认识
LFSR是指给定前一状态的输出，将该输出的线性函数在用作输入的移位寄存器。其中异或运算是最常见的单比特线性函数，对寄存器的某些位进行异或操作后作为输入，再对寄存器中的各比特进行整体移位。也就是先进行异或运算再进行位移运算LFSR是计算机可以比较快的构造出一个拟完美序列。
LFSR的两种形式
- LFSR其实不止上面介绍的一种形式，其实还有另一种形式。
- 对于上面介绍的这种，是比较经典的，将其称为Fibonacci型，其实就是指定抽头影响输入位。
- 还有一种LFSR类型，该类型为Galois型，这种类型是输出位送给输入位后逐位异或，从而影响其他位，得到伪随机。
- 大致介绍一下
LFSR的工作流程：- 首先
FF0、FF1、FF2、...、FFn会被初始化bit位。 - 接着
CLK时钟，发出一个脉冲，这就会使得- $FF_n$的值输出出去（其中输出其实还要画一个箭头，这边只有参与异或的箭头），$FF_n$的值会输出到两个地方，其中一个地方是输出给用户使用，另一个输出是参与生成下一个
FF0的运算。 - 接着$FF{n-1}$的值就会被输出（移动）到$FF{n}$这个寄存器中，$FF{n-2}$的值就会被输出（移动）到$FF{n-1}$这个寄存器中，以此类推，这就是移位
- $FF_n$的值输出出去（其中输出其实还要画一个箭头，这边只有参与异或的箭头），$FF_n$的值会输出到两个地方，其中一个地方是输出给用户使用，另一个输出是参与生成下一个
- 输出的过程中，其实还会将输出的值输出给$g1、g_2、…、g{n}$就会参与运算，运算的结果就是$FF_0$的值，这就是反馈。
- 首先
- 上面就是LFSR的大致过程，接下来展示一个真实的
LFSR电路图，由于LFSR的特性，其是比较容易在硬件中实现的，逻辑电路图并不复杂。其组成其实就是n个触发器，加上一些异或门再通过导线连接即可得到一个硬件的LFSR。
LFSR算法描述
我们先来给出一张图片，这张图片就简单介绍了
LFSR算法。这张图主要做了一下几个事情：对于初始的状态$ana{n-1}…a{2}a{1}$，经过一个线性函数$f(a_1,a_2,…,a_n)$的运算，其实$f(a_1,a_2,…,a_n)$这个线性函数就是异或操作，即$f(a_1,a_2,…,a_n)=a_1\oplus a_2 \oplus …\oplus a_n$,得到一个结果作为我们后续的输入的
bit值，所以这个函数运算结果只有0或者1，先暂时保存这个值之后将$ana{n-1}…a2a_1$经过位移后整体就变成$a{n-1}a_{n-2}…a_1a_0$，此时$a_0$其实就是作为输出值了
最后我们再将$f(a1,a_2,…,a_n)$运算得到的结果传递给$a_n$，此时就构成了新的一组$a_na{n-1}…a_2a_1$序列
之后像这样不断的线性位移计算，我们就能得到这些二进制序列，我们每线性位移
n次取一次序列，这样就得到了n位伪随机数注意：不一定所有的位都参与线性运算，一般只选择几个位参与线性运算
有几个注意点：
- 将参与线性运算$f(a_1,a_2,…,a_n)$的位称为抽头，也就是LFSR状态下影响输入的位
- LFSR最右边的位为输出位，同时它始终也是抽头。
- 抽头是有顺序的异或，然后反馈到最左边的位。
- 最右边的位序列称为输出流，如上图所示其实我们的输出流其实是$a_1$先输出出来,然后$a_2$，最后才是$a_n$
- 最大长度LFSR产生m序列具有$2^m-1$种状态，寄存器全零状态的时候线性位移后还是全零（关于
m序列的概念这里不多说）
- 接下来我们使用Python实现一下简单的
32位LFSR伪随机数：
1 | def _int32(x): |
- 在实际过程中，一般会有一个
mask，这个mask的作用一般就是作为反馈系数进行异或操作，将初始序列和mask进行与操作这样 - 下面是带有
mask的LFSR简单实现代码：
1 | 1 |
LFSR数学表示
LFSR例子
先举一个例子看看：$Z_2$上周期为7的拟完美序列如下：
- $\alpha=1001011…=a_0a_1a_2a_3a_4a_5a_6….$，观察$a_0、….、a_7$这七个数之间的关系。
- 注意到有如下关系，发现前三位$a_0、a_1、a_2$确定下来了，这个序列的关系就可以确定了：
- 这样我们可以通过递推公式写出来关系式：$a{k+3}=a{k+1}+a_{k},(k=0,1,2…)$，这是一个三阶递推公式。
LFSR数学推导
- 从上面的LFSR例子可以看到，我们用递推关系很好表示出来这个序列，所以一开始我们就使用递推公式来描述LFSR。
- 对于LFSR来说，需要有周期，并且周期长，这样才是好的LFSR，所以接下来需要研究它的周期。在研究周期之前，除了递推这个数学描述之外，LFSR还可以用矩阵描述、特征多项式描述，接下来通过递推公式逐渐引入这两个描述。
- 考虑一个$Z_2$上的n阶线性常系数齐次递推关系式，可以用LFSR实现这个递推序列，接下来要研究它是否有周期，周期是否很大：
- $a{k+n}=c_1a{k+n-1}+c2a{k+n-2}+…+c{n-1}a{k+1}+cna{k},(k=0,1,2,…,c_n≠0)$该式子记为①
- 设正整数$d$是序列$\alpha=a0a_1a_2…$的一个周期，定义式子为：$a{i+d}=a_{i}$该式子记为②，满足②式的最小正整数$l$称为$\alpha$的最小正周期。
- 等价条件：$u$是$\alpha$的周期$\Leftrightarrow u$是最小正周期$l$的正整数倍
- 目前来说只有一个递推式子研究周期还是比较困难的，所以我们引入如下方程组：
- 这样一来就可以写成向量矩阵的形式，描述如下，从而记$A = \begin{bmatrix}
c1&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}$称为递推关系①式的生成矩阵：
接下来对于初始值$a0,a_1,…,a{n-1}$如果确定了，我们希望各个位数求出来，
- 对于上述式子，我们令$k=0$那么我们就有：
- 令$k=1$就有：
- 以此类推就有，这样不就有了个类似于通项公式的东西了么，我们将下面的式子记为④式
命题1：
$d$是由$n$阶递推关系①式产生的$Z2$上序列$\alpha=a_0a_1a_2…a{n-1}…$的一个周期的充分必要条件是$\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：
若$A^{d}-I=0$，则$d$是①式产生的任意序列的周期
证明：
- 由$d$是序列的周期就可以得到：$a_{i+d}=a_i,i=0,1,2…$
- 利用递推关系①式$\Rightarrow$$\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}$，这个式子再由④式得到：$\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}$ - 这就得到了$\begin{pmatrix}a{n-1} \a{n-2}\a{n-3}\\vdots \a{0}
\end{pmatrix}$是$A^{d}$的属于特征值1的一个特征向量。 - 从而就有$(A^{d}-I)\begin{pmatrix}a{n-1} \ a{n-2} \ a{n-3} \ \vdots \ a{0}
\end{pmatrix}=0$
回过来看式子①：
- 通过一系列的递推我们就可以得到如下的方程组：
- 写成向量的的形式，这一看这个结构不就是线性表出
- 再使用④式$\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,a_1,…,a{n-1}\in Z_2$都成立，记下面的式子为⑤式
- 由一个矩阵乘上任意一向量都是零矩阵，那么这个矩阵一定是零矩阵，可以得到，记该式子为⑥式：
- 令$f(x)=x^{n}-c1x^{n-1}-…-c{n-1}x-c_n\in Z_2[x]$，此时$f(A)=0$，只要递推关系式①给了，我们就能确定这个多项式。而多项式和递推关系可以互推，这样的多项式我们就称为递推关系式①的特征多项式。从而有命题⑥
命题2
设$f(x)$是$n$阶递推关系式①的特征多项式，A是①的生成矩阵则$f(A)=A^{n}-c1A^{n-1}-…-C{n-1}A-c_nI=0$
定理1
设$f(x)$是$n$阶递推关系式①的特征多项式，A是①的生成矩阵，若$f(x)|x^{d}-1$，则$d$是$n$阶递推关系①产生的任意序列的周期。
- 证明：
- 存在$h(x)\in Z_2[x]$使得$x^{d}-1=h(x)f(x)$，用生成矩阵$A$带入$x$得到
- 可以得到：$A^{d}-I=h(A)f(A)=0$
- 由推论1可以得到$d$是$n$阶递推关系①产生的任意序列的周期。
定理2
设$f(x)$是$n$阶递推关系式①的特征多项式，A是①的生成矩阵，设$f(x)$在$Z2$上不可约，若$d$是$n$阶递推关系①产生的一个非零序列$\alpha = a_0a_1…a{n-1}a_n…$的一个周期，则$f(x)|x^{d}-1$
- 证明：使用反证法证明
- 假设$f(x)\not|x^d-1$，则$(f(x),x^{d}-1)=1$
- 从而存在$u(x),v(x)\in Z_2[x]$，使得$u(x)f(x)+v(x)(x^{d}-1)=1$，这个式子就是裴蜀定理在多项式中的推广
- $x$用生成矩阵$A$带入，就有$u(A)f(A)+v(A)(A^{d}-I)=I$
- 由命题2可以得到$v(A)(A^{d}-I)=I$，$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}$ - 从而得到$\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$是非零序列矛盾。
- 我们还希望这个$n$阶递公式的生成的任意序列都有周期，接下来我们就要从特征多项式入手：
- 由⑥式$A^{n}-c1A^{n-1}-…-c{n-1}A-cnI=0$可以得到：$A^{n}=c_1A^{n-1}+…+c{n-1}A+c_nI$记为式子⑦
- 从而：$A^{n+1}=c1A^{n}+c_2A^{n-1}+…+c{n-1}A^2+CnA=c_1(c_1A^{n-1}+…+c{n-1}A+c_nI)+…+c_nA$
- 说明$A$的任意非负整数次幂都可以属于下面这个集合：$\Omega={b1A^{n-1}+b_2A^{n-2}+…+b{n-1}A+b_nI|b_i \in Z_2,i=1,2,….}$
- 而$\Omega$这个集合中元素个数有$2^{n}$个，但是有些$A$的次幂可以由多个多项式生成相同的结果，所以$|\Omega|≤2^n$
- 从而$\Omega$中的非零矩阵至多有$2^{n}-1$个，下述$2^{n}$个矩阵，$I,A,A^{2},…,A^{2^{n}-1}$，由于生成矩阵$|A|=c_n≠0$，因此$A$可逆矩阵。
- 从而上述$2^n$个矩阵都是非零矩阵，于是存在一对$i,j$满足：$A^{i}=A^{j},0≤i<j≤2^{n}-1$，从而就有$I=A^{j-i}$，即$A^{j-i}-I=0$
- 由推论1可以得到，$j-i$是$n$阶递推关系①产生的任意序列的周期
- 从而任何一个①产生的任意序列的最小正周期$l≤j-i≤2^{n}-1$，于是得到定理3
定理3
$n$阶递推关系①产生的任一序列都有周期，并且最小正周期不超过$2^{n}-1$
- 我们希望周期越大越好，所以引入了如下的定义
定义1
设$\alpha$是$Z_2$上$n$阶常系数线性齐次递推关系产生的序列，如果$\alpha$的最小正周期达到$2^{n}-1$，那么称$\alpha$是$Z_2$上的一个
m序列。
- 最后我们还要分析，这个线性递推关系满足的什么条件才会是
m序列，于是推导出了定理4，接下来先分析一下：- 由定理1可以得到若$f(x)|x^{2^n-1}-T$则$2^{n-1}$是$\alpha$的一个周期。
- $\alpha$的最小正周期$l|2^{n}-1$
- 那么我们希望：对于$d|2^{n}-1$，且$0<d<2^{n}-1$，$d$不是$\alpha$的周期。若$f(x)$在$Z_2$上不可约，且$f(x)\not|x^{d}-1$则根据定理2得到，$d$不是$\alpha$的周期。
定理4
设$f(x)$是$n$阶递推关系①的特征多项式，如果满足：
- $f(x)$在$Z_2$上不可约
- $f(x)|x^{2^{n}-1}-T$
- 对于$d|2^{n}-1$，且$0＜d＜2^{n-1}$，都有$f(x)\not|x^{d}-1$
那么①产生的任一非零序列$\alpha$是
m序列定义2
$Z_2$上的一个$n$次多项式$f(x)$如果满足定理4中的三个条件，那么称$f(x)$是$Z_2$上的一个本原多项式（这个本原多项式与有理数上的本原多项式是不同的概念）
注：从定义2出发，我们可以重新这样叙述定理4，如果$n$阶递推关系①的多项式是$Z_2$上的本原多项式，那么①产生的任何序列都是
m序列。定理5
$Z_2$上的
m序列都是拟完美序列。
总结
命题1：
$d$是由$n$阶递推关系①式产生的$Z2$上序列$\alpha=a_0a_1a_2…a{n-1}…$的一个周期的充分必要条件是$\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：
若$A^{d}-I=0$，则$d$是①式产生的任意序列的周期
命题2
设$f(x)$是$n$阶递推关系式①的特征多项式，A是①的生成矩阵则$f(A)=A^{n}-c1A^{n-1}-…-C{n-1}A-c_nI=0$
定理1
设$f(x)$是$n$阶递推关系式①的特征多项式，A是①的生成矩阵，若$f(x)|x^{d}-1$，则$d$是$n$阶递推关系①产生的任意序列的周期。
定理2
设$f(x)$是$n$阶递推关系式①的特征多项式，A是①的生成矩阵，设$f(x)$在$Z2$上不可约，若$d$是$n$阶递推关系①产生的一个非零序列$\alpha = a_0a_1…a{n-1}a_n…$的一个周期，则$f(x)|x^{d}-1$
定理3
$n$阶递推关系①产生的任一序列都有周期，并且最小正周期不超过$2^{n}-1$
定义1
设$\alpha$是$Z_2$上$n$阶常系数线性齐次递推关系产生的序列，如果$\alpha$的最小正周期达到$2^{n}-1$，那么称$\alpha$是$Z_2$上的一个
m序列。定理4
设$f(x)$是$n$阶递推关系①的特征多项式，如果满足：
- $f(x)$在$Z_2$上不可约
- $f(x)|x^{2^{n}-1}-T$
- 对于$d|2^{n}-1$，且$0＜d＜2^{n-1}$，都有$f(x)\not|x^{d}-1$
那么①产生的任一非零序列$\alpha$是
m序列定义2
$Z_2$上的一个$n$次多项式$f(x)$如果满足定理4中的三个条件，那么称$f(x)$是$Z_2$上的一个本原多项式（这个本原多项式与有理数上的本原多项式是不同的概念）
注：从定义2出发，我们可以重新这样叙述定理4，如果$n$阶递推关系①的多项式是$Z_2$上的本原多项式，那么①产生的任何序列都是
m序列。定理5
$Z_2$上的
m序列都是拟完美序列。
LFSR相关题目
- 大概了解完
LFSR的代码实现以及数学表示了，那么就可以来牛刀小试一下一些题目。 - 题目难度依次递增，比较适合
LFSR入门。
LFSR 题目1 求反馈系数
- 题目来源：
简单的LFSR，题目地址：攻防世界 - 题目附件如下：
1 | from secret import secret |
LFSR 题目2 求初始状态
- 题目来源：
[CISCN2018]oldstreamgame，题目地址：CISCN 2018 oldstreamgame - NSSCTF - 题目附件如下：
1 | flag = "flag{xxxxxxxxxxxxxxxx}" |
key文件如下：
1 |
LFSR破解
- 对于
LFSR的破解需要用上一个经典的算法也就是Berlekamp-Massey算法。这里建议先去学习一下Berlekamp-Massey算法，先从它的数学抽象出来的问题入手，在破解LFSR的时候会更有助于理解。Berlekamp–Massey 算法 - OI Wiki - 对于
Berlekamp-Massey算法，就不在这里详细介绍，这里只介绍Berlekamp-Massey算法在破解LFSR中的应用。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 iyheart的博客！
wechat