参考博客：3.6 线性反馈移位寄存器（LFSR） | 第三章：序列密码 |《密码学入门》| Python 技术论坛
参考博客：线性反馈移位寄存器 - 维基百科，自由的百科全书
参考博客：线性反馈移位寄存器（LFSR） - 生活的高手 - 博客园
参考博客：cdcq的密码学教程四——BM算法 | cdcq
LFSR英文名为Linear feedback shift register，中文翻译过来就是线性反馈移位寄存器，其伪随机数生成的特点已经包含在LFSR的名称中，也就是线性、反馈这两个词。
由于LFSR是非常容易使用硬件实现的，所以在以前很多流密码的密钥都是通过LFSR伪随机数生成算法来实现的，但是该伪随机数生成的算法在密码学体制中是比较不安全的，容易被预测到。但是LFSR组合其实可以得到安全的流密码。
本篇文章写于2025.6.16但是写的不怎么好，而在2025.9.11在图书馆随便看看，看到了这本书，从数学原理讲LSFR，于是决定重写博客，重新学习LSFR相关的。

LFSR

LFSR是指给定前一状态的输出，将该输出的线性函数在用作输入的移位寄存器。
其中异或运算是最常见的单比特线性函数，对寄存器的某些位进行异或操作后作为输入，再对寄存器中的各比特进行整体移位。也就是先进行异或运算再进行位移运算

LFSR的两种形式

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

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

LFSR算法描述(Fibonacci型)

我们先来给出一张图片，这张图片就简单介绍了LFSR算法。这张图主要做了一下几个事情：
- 对于初始的状态$a_na_{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，先暂时保存这个值
- 之后将$a_na_{n-1}…a_2a_1$经过位移后整体就变成$a_{n-1}a_{n-2}…a_1a_0$，此时$a_0$其实就是作为输出值了
- 最后我们再将$f(a_1,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$种状态，寄存器全零状态的时候线性位移后还是全零

接下来我们使用Python实现一下简单的32位LFSR伪随机数：

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())

LFSR数学表示(Fibonacci型)

LFSR有三种数学表示分别是递推公式、多项式表示、矩阵表示，其转换为数学符号，在有的时候更有利于推导公式之类的。
首先我们来介绍这张图所有位都参与异或的情况：
- 设初始序列为$a_{n-1}a_{n-2}…a_1a_0$，由于我们每个位都参与运算，所以每个位都影响了最终结果
- 所以此时我们就可以写成这样一个模2的方程$a_{n+1}=a_{n}+a_{n-1}+…+a_2+a_1~mod~2$
- 此时我们还可以使用多项式的形式来表示$P(x)=x^{n}+x^{n-1}+…+x^{2}+x+1~mod~2$
对于上图我们还可以使用矩阵来表示，我们可以定义状态向量$A_n$和转移矩阵$B_n$

$$
A_n=\begin{bmatrix}a_n\a_{n-1}\ \vdots \ a_2 \ a_1 \end{bmatrix}\

B_n=\begin{bmatrix}1&&1 && \cdots &&1 &&1\ 1 && 0 && \cdots && 0 && 0\ 0 && 1 && \cdots && 0&&0\ \vdots && \vdots && \ddots && \vdots && \vdots\ 0 && 0 && \dots &&1&&0 \end{bmatrix}
$$

最后得到结果

$$
A_{n+1}=B_nA_n=\begin{bmatrix}a_n+a_{n-1}+…+a_2+a_1~mod~2\a_n\ \vdots \ a_3 \ a_2 \end{bmatrix}
$$

但是由于在设计LFSR的时候我们并不会每一位都参与异或，此时我们就在$a_i$的前面添加一个系数，如果该位是抽头的话$a_i$前面的系数就为1，该位不是抽头的话$a_i$前面的系数就是0
例如上面使用Python编写的LFSR，就选用的是$a_{26}、a_{16}、a_{11}、a_{1}$作为抽头这样的话，就可以使用数学表达式得到这么一个序列

$$
a_{n+1}=a_{26}+a_{16}+a_{11}+a_1~mod~2\
P(x)=x^{26}+x^{16}+x^{11}+x+1~mod~2
$$

使用矩阵表示就如下，$B_n$太大写不下：

$$
A_n=\begin{bmatrix}a_{32}\a_{31}\ \vdots \ a_2 \ a_1 \end{bmatrix}\
$$

最后的结果要如下：

$$
A_{n+1}=B_nA_n=\begin{bmatrix}a_{26}+a_{16}+a_{11}+a_1~mod~2\a_{32}\ \vdots \ a_3 \ a_2 \end{bmatrix}
$$

所以归纳出输出序列，执行第m次的线性位移操作后的输出值的递推如下：

$$
a_{i+m}=\sum^{m+1}{j=0}p_j *a{i+j}~mod~2\s_i,p_i\in{0,1},i=0,1,2,…
$$

多项式表示为，如果第i位为抽头$p_i$就为1，否则为0：
这里注意有的多项式表达最高次数位始终为1，但是这里我们是将最低次数位默认为输出位，所以这里多项式始终有个1，具体情况再具体定义这个多项式就行了

$$
P(x) = p_{n-1}x^{n-1}+p_{n-2}x^{n-2}+…+p_{2}x^{2}+p_1x+1~mod~2
$$

最后矩阵状态转移就不写了，写矩阵太麻烦了。

LFSR的逻辑图(Fibonacci型)

由于LFSR的特性，其是比较容易在硬件中实现的，逻辑电路图并不复杂。其组成其实就是n个触发器，加上一些异或门再通过导线连接即可得到一个硬件的LFSR。
如下图所示：

LFSR破解

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

LFSR深入理解

接下来要介绍一些相关的定义和定理作为学习Berlekamp-Massey算法的前置知识。

知识点1

假设一个LFSR长度为L，LFSR的最初状态其实就等于LFSR所产生的序列的前L位输出。如下图所示，序列$a_0、a_1、…、a_n$其实就是长度为N的LFSR的初始状态。

从第$L+1$位开始的所有输出，完全由LFSR的反馈结构和初始状态决定，说明了一旦LFSR的反馈结构确定并且设置了初始状态，那么输出序列就唯一确定

知识点2

当我们要用阶(其实是LFFR的长度)为L的LFSR，来生成长度为$N$的序列其实会出现以下两种情况：

当L>=N时，该LFSR一定能生成长度为$N$的序列，但是并不是最短的一个LFSR

当L<N时，如果该LFSR能生成长度为$$N$$的序列，那么从第$L+1$位开始就必须满足递推式$s_n=\sum^{L}{i=1}c{i}s_{n-i}~mod~2$