非线性序列密码结构-尧图网站建设

📅 发布时间：2026/6/21 20:15:56

关于LFSR线性反馈移位寄存器和攻击方法B-M算法参考：序列密码概述部分：https://www.cnblogs.com/luminescence/p/18938331
下面内容主要围绕对LFSR进行非线性改造的四种经典方法展开，以克服LFSR序列线性复杂度低、易被B-M算法破解的缺陷

基本结构：
由一个LFSR和一个非线性过滤函数 \(f\) 构成。
LFSR负责生成线性序列，其内部状态（多个寄存器的值）作为非线性函数 \(f\) 的输入。
函数 \(f\) 对这些状态进行非线性运算，其输出才是最终的密钥流。

工作原理图：

LFSR状态 (a_{t}, a_{t+1}, ..., a_{t+n-1}) --> 非线性函数 f --> 密钥流比特 z_t

安全性：
过滤函数 \(f\) 必须是非线性的。
如果 \(f\) 是线性的，那么输出序列的线性复杂度不会超过LFSR的级数，无法抵抗B-M算法攻击。
设计目标是使输出序列的线性复杂度远高于LFSR本身的级数，同时具有良好的随机性。

基本结构：
使用多个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的序列，就可能逐个击破。

基本结构：
这是对NCG的增强，引入了记忆单元（通常为1比特或多比特）。
它使用两个组合函数 \(f_1\) 和 \(f_2\)
输入包括多个LFSR的输出和当前记忆单元的值。
工作原理：
函数 \(f_1\) 的输出用于生成当前的密钥流比特。
函数 \(f_2\) 的输出用于更新记忆单元的值，为下一时刻的计算做准备。
记忆的引入使得生成器的输出不仅依赖于当前的输入，还依赖于过去的历史，从而大大增加了序列的复杂度和安全性。
核心特点：
通过记忆单元将状态概念引入组合生成器，使其成为一个有限状态机。
能有效提高序列的线性复杂度和抵抗相关攻击的能力。

基本思想：
摒弃所有LFSR同步步进的传统方式，用一个（或一组）LFSR的输出来控制另一个（或另一组）LFSR的时钟脉冲。
被控的LFSR在某些时钟周期可能不步进（“停”），或在某些周期步进多次（“走”），从而产生不规则的输出。
常见控制方式：
一个LFSR控制另一个LFSR：最典型的模式。
自控制：一个LFSR参与控制它自己的时钟。
相互控制：两个LFSR互相控制对方的时钟（如MICKEY算法）。

工作原理图：

LFSR A (控制寄存器) --输出--> 控制逻辑 --时钟信号--> LFSR B (被控寄存器)---> 密钥流输出

控制逻辑根据LFSR A的当前输出值，决定LFSR B在本时钟周期内步进多少次。

所有这些结构都旨在通过非线性和增加复杂度来掩盖LFSR的线性本质，但其安全性高度依赖于非线性函数/时钟控制机制的具体设计。后期研究表明，这些经典结构若单独使用，在面对代数攻击等现代分析方法时仍显薄弱，因此现代序列密码（如Grain, Trivium）往往采用更复杂的混合结构

非线性序列密码结构