（九）详解线性反馈移位寄存器（LFSR）

Question

如题所述

Answer 1

详解线性反馈移位寄存器（LFSR）

本文探讨线性反馈移位寄存器（LFSR）在密码学中的应用，LFSR常用于生成密钥流。LFSR由线性驱动和非线性组合两部分组成，线性驱动部分通过线性反馈移位寄存器实现。

移位寄存器（SR）是一个存储二进制数的序列，每次移位后输出最右端的数字。反馈移位寄存器在每次移位后，通过反馈函数填充左端，形成连续输出。

线性反馈移位寄存器（LFSR）采用线性函数作为反馈函数，因此称为线性反馈移位寄存器。反馈函数选择寄存器中的某些位进行异或运算，并将结果填充到左端。参与异或的位称为抽头。

LFSR的级数表示寄存器的个数，决定可存储的最大状态数。一个3级LFSR最多存储7种状态。状态序列的长度决定了LFSR的周期。

LFSR的特征多项式表示反馈函数关系。对于3级LFSR，特征多项式为x^3 + x + 1。周期为多项式的阶，即LFSR状态序列重复的次数。

达到足够大的周期是生成安全密钥流的关键，m序列是周期为2^n - 1的LFSR生成序列。周期性可以通过特征多项式的阶来判断。

LFSR在密码学中的易攻破性：已知反馈函数和级数时，通过连续n位明文和密文可计算出密钥流。未知反馈函数但已知级数时，通过2n位明文和密文，求解线性方程组可还原LFSR。

若反馈函数和级数均未知，可通过密钥序列分析求取线性复杂度和极小多项式，进而确定LFSR结构。线性复杂度越大，密钥流越难破解。

LFSR生成的密钥流受到线性复杂度、周期性和伪随机性限制，只使用LFSR生成密钥流存在安全风险。应结合非线性方式提升安全性。