【密码学】（七）非线性组合、非线性序列生成器

2026-08-12
作者魏欣怡
~3.32K 字

1. 一、非线性组合的工作方法
2. 二、非线性序列生成器

本文转载自：《现代密码学》课程笔记知乎专栏
仅作个人学习记录。

我们曾提到，密钥流生成器分为线性驱动部分和非线性组合部分。其中，线性驱动部分通常由LFSR产生的m序列或者其他LFSR长序列组成，为非线性组合部分提供随机性质良好的序列。非线性组合部分使生成的序列符合伪随机序列的条件。

线性驱动和非线性组合满足香农的“混淆”和“扩散”原则。线性驱动可以对初始密钥k进行“扩散”，非线性组合对LFSR生成的序列进行“混淆”。

我们接下来讲解非线性组合部分。

一、非线性组合的工作方法

1、非线性函数：

非线性组合部分可以表示为一个非线性布尔函数，这个函数的输入是阶（周期为）LFSR m序列的一个状态 $Xi=(x_i,x{i+1},\ldots,x_{i+n-1}) $（共$ n $位），输出为一位密钥$ z_i $。即$ z_i=f(X_i)$。

2、非线性前馈序列：

如果有一个阶LFSR产生m序列，则对于这个m序列的每一个状态（共位），都可以经过非线性函数得到一个密钥。让从1到正无穷连续取值，由此生成的一系列密钥序列被称为非线性前馈序列，其中m序列被称为驱动序列。

3、非线性前馈序列的初始密钥：

采用密钥流生成器产生符合伪随机序列条件的密钥序列时，一般会有一个原始密钥作为密钥产生器的输入。这个初始密钥一般有如下几种情况：

原始密钥只包含LFSR的初始状态，公开最小多项式、非线性布尔函数等信息。此时原始密钥最短，但布尔函数需要精心设计。
原始密钥包含了LFSR的初始状态和最小多项式等信息，公开了非线性布尔函数。此时原始密钥中等长，布尔函数的设计要求稍低。
原始密钥包含了LFSR的初始状态、最小多项式、非线性布尔函数等信息。此时原始密钥最长，布尔函数的设计要求最低。

4、非线性组合序列：

非线性组合序列的生成依赖多个LFSR，假设有个阶LFSR m序列，则他们生成的序列为。式中上标表示第个LFSR产生的序列，下标表示第个状态的序列，即表示第个LFSR产生的第个状态的序列。

以这个序列作为非线性函数的输入。其中第个密钥由每个LFSR的第位作为非线性函数的输入得出。有，这个密钥序列被称为非线性组合序列，这个阶LFSR m序列被称为驱动序列。非线性组合序列生成的流程如图所示：

图10-1 非线性组合序列生成器示意图

二、非线性序列生成器

1、Geffe序列发生器：

Geffe序列发生器和后面将要讲的J-K序列生成器都属于滤波生成器。滤波生成器一般由一个或多个LFSR和滤波函数组成。其中要求滤波函数有足够强的非线性性质。

Geffe序列发生器由3个级数两两互素的LFSR和一个滤波函数（复合器）组成。如图所示：

图10-2 Geffe序列发生器示意图

假设LFSR-1、LFSR-2、LFSR-3的输出序列分别为、、。则其输出可以表示为。

观察式子可以发现，LFSR-1主要起选择作用，当时，，输出LFSR-2的序列；当时，，输出LFSR-3的序列。如图所示：

图10-3 Geffe序列发生器真值表

如果LFSR-1、LFSR-2、LFSR-3的级数分别为（两两互素），则这个序列发生器的周期为（三者周期之积），线性复杂度为。

Geffe序列发生器是不安全的，观察真值表可以发现，有75%的输出与输入相同，也有75%的输出与输入相同。因此可以通过相关攻击破译Geffe序列发生器。

2、J-K触发器：

学过数电的同学应该已经对J-K触发器有了一定的了解。在J-K触发器中，有两个LFSR（m序列）作为触发器的输入，在触发器的作用下，产生输出序列。

其中，LFSR-1的输出序列直接输入到J-K触发器的J端，LFSR-2的输出序列直接输入到J-K触发器的K端。在触发器的作用下，产生输出序列。如下图所示：

图10-4 J-K触发器

其真值表如下图所示：

图10-5 J-K触发器的真值表

这里的J-K触发器真值表与数电中的完全相同。观察可以发现，当时，输出保持上一个输出的状态；当时，输出置0；当，输出置1；当时，输出翻转（取反）。

[!note] 补充：
在数电中，常常把这四种情况称为：保持、置0、置1、翻转。

通过真值表，还可以得出输入序列 $ai $、输入序列$ b_i $、输出序列$ z_i $之间的关系为$ z{i+1}=ai\overline{z_i}\oplus\overline{b_i}z_i $。其中$ z_i $表示$ z{i+1}$ 的上一个输出字符。

当两个输入LFSR的级数分别为，且（互素），那么输出序列的周期为（两者周期之积）。

J-K触发器输出序列的随机性要比Geffe序列发生器的好，但是也仍然不太安全。理由如下：

假设我们能够知道输出序列的连续两个字符，那我们就可以根据真值表对和中的一个进行判断。

当 $zi z{i+1}=00 $时，前后两次输出都为，则可能是置，也可能是保持，因此一定有$ a_i=0$；
当 $zi z{i+1}=10 $时，前面为，后面为，则可能是翻转，也可能是置，因此一定有$ b_i=1$；
当 $zi z{i+1}=01 $时，前边为，后边为，则可能是翻转，也可能是置，因此一定有$ a_i=1$；
当 $zi z{i+1}=11 $时，前后两次输出都为，则可能是置，也可能是保持，因此一定有$ b_i=0$。

3、钟控序列生成器：

钟控序列生成器的基本原理就是利用一个LFSR生成的序列来控制另一个LFSR的移位。（都为m序列）如图所示：

图10-6 钟控序列生成器示意图

其中，左端有一个时钟脉冲来控制两个LFSR移位和输出，时钟脉冲每到来一次，LFSR1就移位输出一次。中间的与门起选择作用，只有当LFSR1输出1时，LFSR2才会移位，并且输出新位；当LFSR1输出0时，时钟脉冲没有到达LFSR2，LFSR2不移位，只重复输出前一位。

例如，假设一个7阶LFSR1输出序列为1110100，7阶LFSR2输出序列为1110010。求最终的输出序列

为方便表示，这里采用从1开始的[i]序号，来表示当前移位到了输出序列的第i位

初始输出：首先因为LFSR2[1]=1，输出1（这里要注意：LFSR-2先输出，然后再移位）。当前输出：1
第1个时钟脉冲：LFSR1移位并输出，LFSR1[1]=1，LFSR2移位，又LFSR2[2]=1，输出1。当前输出：11
第2个时钟脉冲：LFSR1再次移位并输出，LFSR1[2]=1，LFSR2移位，LFSR2[3]=1，输出1。当前输出：111
第3个时钟脉冲：LFSR1再次移位并输出，LFSR1[3]=1，LFSR2移位，LFSR2[4]=0，输出0。当前输出：1110
第4个时钟脉冲：LFSR1再次移位并输出，LFSR1[4]=0，LFSR2不移位，保持原输出LFSR2[4]=0，输出0。当前输出：11100
第5个时钟脉冲：LFSR1再次移位并输出，LFSR1[5]=1，LFSR2移位，LFSR2[5]=0，输出0。当前输出：111000
第6个时钟脉冲：LFSR1再次移位并输出，LFSR1[6]=0，LFSR2不移位，保持原输出LFSR2[5]=0，输出0。当前输出：1110000
第7个时钟脉冲：LFSR1再次移位并输出，LFSR1[7]=0，LFSR2不移位，保持原输出LFSR2[5]=0，输出0。当前输出：11100000
第8个时钟脉冲：LFSR1再次移位并输出，此时LFSR1完成了一个周期的循环，回到第一位，LFSR[1]=1，LFSR2移位，LFSR[6]=1，输出1。当前输出：111000001
……以此类推

假设两个LFSR1的级数为，LFSR2的级数为，则两者组合而成的钟控序列生成器的周期为（周期之积），线性复杂度为。

[!faq]- 课堂练习

[!NOTE]- 参考答案

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可

魏欣怡的博客

一、非线性组合的工作方法

二、非线性序列生成器