非线性反馈移位寄存器

非线性反馈移位寄存器(NLFSR, Nonlinear feedback shift register)是一种移位寄存器,和线性反馈移位暂存器(LFSR)相对。NLFSR的大体电路逻辑和LFSR相似,但是其反馈逻辑是由异或门 (xor) 和与门 (and) 构成的,而LFSR中仅存在异或门 (xor)。

从代数表达式来看,异或门是加法 (+),而与门是乘法 (*)。由加法构成的反馈逻辑,其反馈表达式的最高项次数不会增长,而由乘法参与的反馈表达式项次数会增长、并可能超过定义多项式的最高项。NLFSR 的设计巧妙地结合了异或门和与门,这种结构使其在生成伪随机序列方面表现出非线性的特性。异或门的使用确保了反馈逻辑中不引入高次数的项,从而保持了较低阶的表达式形式。而与门的引入则使得反馈逻辑的非线性度增强,这对于提高 NLFSR 的复杂性和抵抗密码分析攻击具有重要意义。

Janusz Szmidt在"The Search and Construction of Nonlinear Feedback Shift Registers"这篇文章中给出了较为详尽的讨论,具体请参见 https://web.archive.org/web/20140529084401/http://www.math.uni-magdeburg.de/~fq11/talks/Szmidt.pdf

参考文献