密码学补完计划[第十九期] 非线性反馈移位寄存器NLFSR

线性在密码学中往往是危险的。本文深入探讨了非线性反馈移位寄存器（NLFSR）如何通过引入非线性，指数级提升安全性，解决传统线性反馈移位寄存器（LFSR）的固有缺陷，为构建更安全的流密码提供核心思路。

智能速览

• LFSR 的线性结构使其极易被 Berlekamp-Massey 算法攻破

• NLFSR 通过非线性反馈函数，将攻击复杂度提升至指数级别

• 非线性引入导致了 NLFSR 的周期计算成为 PSPACE-complete 难题

• Trivium 和 ZUC 等现代密码算法利用 NLFSR 的思想增强安全性

精华内容

既然线性结构是密码安全的致命弱点，那么引入非线性反馈函数的 NLFSR，究竟是如何将攻击者的难度从多项式时间提升到指数级别的？其代价又是什么？

LFSR 的线性困境

线性反馈移位寄存器（LFSR）的核心在于其线性反馈函数，这使其生成的序列具有可预测性。攻击者仅需观测 2L 个连续比特流，即可通过 Berlekamp-Massey 等算法构建并求解线性方程组，从而反推出 L 位的本原多项式。这种脆弱性源于其本质上的线性结构，使得攻击复杂度与寄存器长度 L 呈线性关系，这在密码学中是致命的缺陷。

NLFSR 的安全飞跃

非线性反馈移位寄存器（NLFSR）的关键改变在于将反馈函数 F 替换为非线性函数。攻击者试图破解时，必须先将非线性方程线性化，这一过程会引入大量新变量。例如，引入二次项会使变量数从 L 膨胀到 L²，三次项则达到 L³ 级别。这种指数级的变量增长，使得求解复杂度从线性时间剧增至不可行的指数时间，安全性得到本质提升。

周期的代价

然而，非线性也带来了代价：周期的确定性消失了。LFSR 的周期由本原多项式保证为 2^L-1，但 NLFSR 的周期求解被证明是 PSPACE-complete 问题，其难度甚至超过了著名的 NP 问题。这意味着，在平均情况下，不存在高效的数学捷径来计算其周期。如何确保 NLFSR 不会陷入短周期，成为设计者必须面对的挑战。

现实的应对

面对周期不确定性，现代密码学采取了务实的策略。例如，Trivium 算法的安全性基于其陷入短周期的概率极低，通过精心设计来保证统计上的安全。而 ZUC 算法则采用混合结构，利用 LFSR 保证长周期，同时用非线性部件打破线性规律，巧妙地结合了二者的优点。这些设计展示了 NLFSR 思想在现实世界中的强大生命力。

从 LFSR 到 NLFSR 的演进，是密码学领域用复杂性对抗脆弱性的典范。虽然 NLFSR 带来了新的挑战，但它也指明了构建更安全系统的方向。未来，如何更高效地设计与分析 NLFSR，仍将是密码学研究的重要课题。