线性反馈移位寄存器

线性反馈移位寄存器（linear feedback shift register, LFSR）是指，给定前一状态的输出，将该输出的线性函数再用作输入的移位寄存器。异或运算是最常见的单比特线性函数：对寄存器的某些位进行异或操作后作为输入，再对寄存器中的各比特进行整体移位。

简介移位寄存器是产生信号和序列的常用设备，它分为线性和非线性两大类著名的一序列和序列就是分别由线性和非线性反馈移位寄存器所生成的。线性反馈移位寄存器（Linear feedback shift register，LFSR）是

通常由动态或静态主从型触发器构成。反馈回路由异或门构成。其特性通常由一个特征多项式表征。使用二输入异或门计算反馈函数的最大长度或近最大长度不纠立寄存器的特征多项式。这种电路的特点是结构简单，它的上限移位速度取决于移位单元的延迟时间和二输入异或门的延迟时间，因此，能获得较高的速度1。线性反馈移位寄存器中的移位单元是由主一从型边沿触发器构成的。在这种结构的移位单元中，主从两极锁存器在两相不交叠时钟的控制下，使数据在时钟上升沿被采样，并一直保持到下一个时钟上升沿。电路中四个移位单元都是由动态主从边沿型触发器构成的，每次移位的操作都需要数据串行依次经过两级锁存器。

赋给寄存器的初始值叫做“种子”，因为线性反馈移位寄存器的运算是确定性的，所以，由寄存器所生成的数据流完全决定于寄存器当时或者之前的状态。而且，由于寄存器的状态是有限的，它最终肯定会是一个重复的循环。然而，通过本原多项式，线性反馈移位寄存器可以生成看起来是随机的且循环周期非常长的序列。移位寄存器结构简单，运行速度快，实用的密钥流产生器大多基于移位寄存器，移位寄存器理论也成了现代流密码体制的基础。

线性反馈移位寄存器的应用包括生成伪随机数，伪随机噪声序列，快速数字计数器，还有扰频器。线性反馈移位寄存器在硬件和软件方面的应用都非常得普遍。循环冗余校验中用于快速校验传输错误的数学原理，就与线性反馈移位寄存器密切相关。

斐波那契线性反馈移位寄存器影响下一个状态的比特位叫做抽头。图1中，抽头序列为[16,14,13,11]。LFSR最右端的比特为输出比特。抽头依次与输出比特进行异或运算，然后反馈回最左端的位。最右端位置所生成的序列被称为输出流。

影响LFSR下一个状态的比特位叫做抽头

最大长度的LFSR生成一个M序列（例如，只有与有一定抽序列的LFSR才能通过所有 2n − 1 个内部状态，不包括全零状态），除非它本身为全零，亦即状态永不改变

作为基于异或运算的LFSR的替换，LFSR也可以给予同或运算。与使用异或门的LFSR全零状态下为无效状态相应的，使用同或门的LFSR在全“1”状态下也是无效的。有LFSR或者基于同或门的LFSR生成的序列可以被认为是同格雷码或者自然二进制码同样有效的二进制序列。

在LFSR中，抽头的设定可以用有限域算数中模2的多项式来表示。这就意味着，多项式中的所有系数必须是“1”或者“0”。这个多项式被称作回授多项式或特征多项式。例如图中的抽头为在第16，14，13，11个比特，则相应的特征多项式为：

多项式中常数“1”并不代表某一个抽头，它所指的是一个比特位的输入（例如 等效为 1 ）。多项式中的指数代表从左至右的抽头位。第一个和最后一个比特一般相应的是输入和输出位。当且仅当相应的回授多项式是本原多项式时，LFSR才能达到最大长度。这表示以下条件是必须的：

抽头的数量必须为偶数。

抽头之间不能成对出现，必须是互质的。

生成最长LFSRs的本原多项式表可通过下部的链接找到。 这类型LFSR也被成为标准，多对一或外部异或门的LFSR。

本原多项式在不同的分支数学，本原多项式有不同的含义：

域论中，一个本原多项式是有限域GF(pm)有限扩张的本原元的最小多项式（域论）。

在代数（特别是环理论），如果一个整系数多项式的所有系数是互素的,则称它是一个本原多项式，本原多项式对判定不可约多项式有很大帮助，高次多项式的不可约多项式判定一直是个未完全解决的难题。

有限域的不可约多项式都是本原多项式，这点对通讯编码和密码学有重要作用。每个有理系数多项式都能写成一个有理数与一个本原多项式的乘积。高斯引理（环的）两个本原多项式的乘积仍是本原多项式。

流密码流密码是私钥密码体制的一类流密码与分组密码用固定变换处理明文序列的一组数据不同，其加密过程是先把报文、语音、图象等原始明文转换成数据，然后将它同密钥序列逐位加密生成密文序列发送给接收者接收者用相同的密钥序列对密文进行逐位解密来恢复明文现代数字电子技术的发展已使密钥序列可以方便地利用以移位寄存器为基础的电路来产生，加上有效的数学工具，使得流密码迅速发展并走向较成熟阶段同时，由于流密码不存在数据扩展和错误传播，其硬件加、解密速度快，且实现容易，因此流密码在实际中得到广泛的应用。密钥流序列必须满足的一些性质对作为密钥流生成器重要部件的反馈移位寄存器进行分析，包括线性反馈移位寄存器序列的特性和衡量流密码系统强度的重要指标等。在流密码中，由于明文序列与密钥序列逐位加密，密钥序列一定要具有与明文序列相当的长度但这样的密钥序列难于分配和管理，实际上密钥序列都是由密钥空间中较短的密钥经过某些算法生成的2。

本词条内容贡献者为:

何星 - 副教授 - 上海交通大学