关于LFSR线性反馈移位寄存器和攻击方法B-M算法参考：序列密码概述部分：https://www.cnblogs.com/luminescence/p/18938331
下面内容主要围绕对LFSR进行非线性改造的四种经典方法展开，以克服LFSR序列线性复杂度低、易被B-M算法破解的缺陷
非线性序列密码结构
一、 非线性过滤生成器（Non-linear Filter Generator, NFG）
-
基本结构：
由一个LFSR和一个非线性过滤函数 \(f\) 构成。
LFSR负责生成线性序列，其内部状态（多个寄存器的值）作为非线性函数 \(f\) 的输入。
函数 \(f\) 对这些状态进行非线性运算，其输出才是最终的密钥流。 -
工作原理图：
LFSR状态 (a_{t}, a_{t+1}, ..., a_{t+n-1}) --> 非线性函数 f --> 密钥流比特 z_t -
安全性：
过滤函数 \(f\) 必须是非线性的。
如果 \(f\) 是线性的，那么输出序列的线性复杂度不会超过LFSR的级数，无法抵抗B-M算法攻击。
设计目标是使输出序列的线性复杂度远高于LFSR本身的级数，同时具有良好的随机性。
二、 非线性组合生成器（Non-linear Combining Generator, NCG）
-
基本结构：
使用多个LFSR（如LFSR 1, LFSR 2, ..., LFSR M） 并行运行。
每个LFSR的输出（而不是内部状态）作为一个组合函数 \(g\) 的输入。
函数 \(g\) 对这些多个线性序列进行组合，其输出是最终的密钥流。 -
工作原理图：
LFSR 1 输出 x1_t -> LFSR 2 输出 x2_t --> 非线性组合函数 g --> 密钥流比特 z_t ... LFSR M 输出 xM_t -> -
安全性：
组合函数 \(g\) 必须是非线性的。
如果 \(g\) 是线性的，输出序列的线性复杂度至多是所有LFSR级数之和，仍然不够安全。
NFG可以被视为NCG的一个特例（只有一个LFSR，但函数作用于其多个状态）。
这种结构容易遭受相关攻击，即如果攻击者能通过输出序列推测出某个LFSR的序列，就可能逐个击破。
三、 有记忆非线性组合生成器（Non-linear Combining Generator with Carry, NCGC）
-
基本结构：
这是对NCG的增强，引入了记忆单元（通常为1比特或多比特）。
它使用两个组合函数 \(f_1\) 和 \(f_2\)
输入包括多个LFSR的输出和当前记忆单元的值。 -
工作原理：
函数 \(f_1\) 的输出用于生成当前的密钥流比特。
函数 \(f_2\) 的输出用于更新记忆单元的值，为下一时刻的计算做准备。
记忆的引入使得生成器的输出不仅依赖于当前的输入，还依赖于过去的历史，从而大大增加了序列的复杂度和安全性。 -
核心特点：
通过记忆单元将状态概念引入组合生成器，使其成为一个有限状态机。
能有效提高序列的线性复杂度和抵抗相关攻击的能力。
四、 钟控生成器（Clock Controlled Generator, CCG）
-
基本思想：
摒弃所有LFSR同步步进的传统方式，用一个（或一组）LFSR的输出来控制另一个（或另一组）LFSR的时钟脉冲。
被控的LFSR在某些时钟周期可能不步进（“停”），或在某些周期步进多次（“走”），从而产生不规则的输出。 -
常见控制方式：
一个LFSR控制另一个LFSR：最典型的模式。
自控制：一个LFSR参与控制它自己的时钟。
相互控制：两个LFSR互相控制对方的时钟（如MICKEY算法）。 -
工作原理图：
LFSR A (控制寄存器) --输出--> 控制逻辑 --时钟信号--> LFSR B (被控寄存器)---> 密钥流输出控制逻辑根据LFSR A的当前输出值，决定LFSR B在本时钟周期内步进多少次。
-
核心特点与安全性：
通过制造不规则的运动，极大地增加了输出序列的线性复杂度和不可预测性。
能有效破坏LFSR序列的线性结构，使其难以用标准的代数方法分析。
设计思想
所有这些结构都旨在通过非线性和增加复杂度来掩盖LFSR的线性本质，但其安全性高度依赖于非线性函数/时钟控制机制的具体设计。后期研究表明，这些经典结构若单独使用，在面对代数攻击等现代分析方法时仍显薄弱，因此现代序列密码（如Grain, Trivium）往往采用更复杂的混合结构