第2章 流密码 2.1 流密码的基本概念 2.2 线性反馈移位寄存器 2.3 线性移位寄存器的一元多项式表示 2.4 m序列的伪随机性 第2章 流密码 2.1 流密码的基本概念 2.2 线性反馈移位寄存器 2.3 线性移位寄存器的一元多项式表示 2.4 m序列的伪随机性 2.5 m序列密码的破译 2.6 非线性序列

2.1 流密码(序列密码)的基本概念 明文: 密钥: 密文: 加密变换: 解密变换:

加法流密码体制模型

2.2 线性反馈移位寄存器 移位寄存器是流密码产生密钥流的一个主要组成部分。 2.2 线性反馈移位寄存器 移位寄存器是流密码产生密钥流的一个主要组成部分。 GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1,a2,…,an)组成，如图2所示。

存储器 存储器 存储器 存储器 图2 GF(2)上的n级反馈移位寄存器

在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于GF(2)上的一个n维向量，共有2n种可能的状态。 (a1,a2,…,an) 表示，其中ai是第i级存储器的内容。

初始状态由用户确定。 反馈函数f(a1,a2,…,an)是n元布尔函数，即函数的自变量和因变量只取0和1这两个可能的值。 函数中的运算有逻辑与、逻辑或、逻辑补等运算。

例 图3 是一个3级反馈移位寄存器，其初始状态为(a1,a2,a3)=(1,0,1)，输出可由表2.2求出。 1 0 1 1 1 0 1 1 1 0 1 1 1 表2.2 一个3级反馈移位寄存器的状态和输出 图3 一个3级反馈移位寄存器 即输出序列为101110111011…，周期为4。

线性反馈移位寄存器LFSR（linear feedback shift register） GF(2)上的n级线性反馈移位寄存器

输出序列{at}满足： 线性反馈移位寄存器：实现简单、速度快、有较为成熟的理论，成为构造密钥流生成器的最重要的部件之一。

例 下图是一个5级线性反馈移位寄存器，其初始状态为（a1,a2,a3,a4,a5）=(1,0,0,1,1) 可求出输出序列为 1001101001000010101110110001111100110… 周期为31。

总是假定c1,c2,…,cn中至少0，否则 f(a1,a2,…,an)≡0。 总是假定cn=1。 LFSR输出序列的性质：完全由其反馈函数决定。 n级LFSR状态数：最多有2n个。 n级LFSR的状态周期：  2n-1。 输出序列的周期=状态周期， 2n-1。 选择合适的反馈函数可使序列的周期达到最大值 2n-1，周期达到最大值的序列称为m序列。

an+k=c1an+k-1 c2an+k-2 … cnak (*) p(x)=1+c1x+…＋cn-1xn-1＋cnxn 2.3 线性移位寄存器的一元多项式表示 设n级线性移位寄存器的输出序列满足递推关系 an+k=c1an+k-1 c2an+k-2 … cnak (*) 用延迟算子 D(Dak=ak-1) 作为未定元，给出的反馈多项式为： p(D)=1+c1D+…＋cn-1Dn-1＋cnDn 这种递推关系 可用一个一元高次多项式 p(x)=1+c1x+…＋cn-1xn-1＋cnxn 表示，称这个多项式为LFSR的特征多项式或特征多项式。 记2n-1个非零序列的全体为G(p(x))

定义2.1 给定序列{ai}，幂级数 称为该序列的生成函数。

定理2.1 设p(x)=1+c1x+…+cn-1xn-1+cnxn是GF(2)上的多项式，G(p(x))中任一序列{ai}的生成函数A(x)满足： 其中

证明： 在等式 an+1=c1anc2an-1…cna1 an+2=c1an+1c2an…cna2 … 两边分别乘以xn,xn+1,…，再求和，可得 A(x)-(a1+a2x+…+anxn-1) =c1x[A(x)-(a1+a2x+…+an-1xn-2)] +c2x2[A(x)-(a1+a2x+…+an-2xn-3)]+…+cnxnA(x) (1+c1x+…+cn-1xn-1+cnxn)A(x) =(a1+a2x+…+anxn-1)+c1x(a1+a2x+…+an-1xn-2) +c2x2(a1+a2x+…+an-2xn-3)+…+cn-1xn-1a1 移项整理

(1+c1x+…+cn-1xn-1+cnxn)A(x) =(a1+a2x+…+anxn-1)+c1x(a1+a2x+…+an-1xn-2) +c2x2(a1+a2x+…+an-2xn-3)+…+cn-1xn-1a1 移项整理

定理2.2 p(x)|q(x)的充要条件是G(p(x))G(q(x))。 证明 (1)必要性：若p(x)|q(x)，可设q(x)=p(x)r(x)，因此 所以若{ai}∈G(p(x))，则{ai}∈G(q(x))，即G(p(x))G(q(x))。

上述定理说明可用n级LFSR产生的序列，也可用级数更多的LFSR来产生。 (2)充分性： 上述定理说明可用n级LFSR产生的序列，也可用级数更多的LFSR来产生。

定义2.2 设p(x)是GF(2)上的多项式，使p(x)|(xp-1)的最小p称为p(x)的周期或阶。

定理2.3 若序列{ai}的特征多项式p(x)定义在GF(2)上，p是p(x)的周期，则{ai}的周期r|p。 证明：

n级LFSR输出序列的周期r: 不依赖于初始条件，而依赖于特征多项式p(x)。 LFSR遍历2n-1个非零状态，这时序列的周期达到最大2n-1，这种序列就是m序列。 对于特征多项式一样，而仅初始条件不同的两个输出m序列，一个记为{a(1)i}，另一个记为{a(2)i}，其中一个必是另一个的移位，即存在一个常数k，使得 a(1)i=a(2)k+i, i=1,2,…

下面讨论特征多项式满足什么条件时，LFSR的输出序列为m序列。

定理2.4 设p(x)是n次不可约多项式，周期为m，序列{ai}∈G(p(x))，则{ai}的周期为m。 证明：设{ai}的周期为r，由定理2.3有r|m，所以r≤m。 设A(x)为{ai}的生成函数，A(x)=(x) / p(x)，即p(x)A(x)=(x)≠0，(x)的次数不超过n-1。而 A(x)=∑aixi-1=a1+a2x+…+arxr-1 +xr(a1+a2x+…+arxr-1) +(xr)2(a1+a2x+…+arxr-1)+… =a1+a2x+…+arxr-1/(1-xr) =a1+a2x+…+arxr-1/(xr-1)

定理2.5 n级LFSR产生的序列有最大周期2n-1的必要条件是其特征多项式为不可约的。 证明：设n级LFSR产生的序列周期达到最大2n-1。反证法：设特征多项式为p(x)，若p(x)可约，可设为p(x)=g(x)h(x)，其中g(x)不可约，且次数k<n。由于G(g(x))G(p(x))，而G(g(x))中序列的周期一方面不超过2k-1，另一方面又等于2n-1，这是矛盾的，所以p(x)不可约。（证毕） 该定理的逆不成立，即LFSR的特征多项式为不可约多项式时，其输出序列不一定是m序列。

ak=ak-1ak-2ak-3ak-4(k≥4) 例2.4 f(x)=x4+x3+x2+x+1为GF(2)上的不可约多项式，这可由x,x+1,x2+x+1都不能整除f(x)得到。以f(x)为特征多项式的LFSR的输出序列可由 ak=ak-1ak-2ak-3ak-4(k≥4) 和给定的初始状态求出，设初始状态为0001，则输出序列为000110001100011…，周期为5，不是m序列。

定义2.3 若n次不可约多项式p(x)的阶为 2n-1，则称p(x)是n次本原多项式。

定理2.6 设{ai}∈G(p(x))，{ai}为m序列的充要条件是p(x)为本原多项式。 证明：若p(x)是本原多项式，则其阶为2n-1，得{ai}的周期等于2n-1，即{ai}为m序列。 反之，若{ai}为m序列，即其周期等于2n-1，由定理2.5知p(x)是不可约的。由定理2.3知{ai}的周期2n-1整除p(x)的阶，而p(x)的阶不超过2n-1，所以p(x)的阶为2n-1，即p(x)是本原多项式。（证毕）

{ai}为m序列的关键在于p(x)为本原多项式，n次本原多项式的个数为 (2n-1)/n 其中为欧拉函数。已经证明，对于任意的正整数n，至少存在一个n次本原多项式。所以对于任意的n级LFSR，至少存在一种连接方式使其输出序列为m序列。

例2.5 设p(x)=x4+x+1，由于p(x)|(x15-1)，但不存在小于15的常数l，使得p(x)|(xl-1)，所以p(x)的阶为15。p(x)的不可约性可由x,x+1,x2+x+1都不能整除p(x)得到，所以p(x)是本原多项式。 若LFSR以p(x)为特征多项式，则输出序列的递推关系为 ak=ak-1ak-4(k≥4) 若初始状态为1001，则输出为 100100011110101100100011110101… 周期为24-1=15，即输出序列为m序列。

2.4 m序列的伪随机性 流密码的安全性取决于密钥流的安全性，要求密钥流序列有好的随机性，以使密码分析者对它无法预测。也就是说，即使截获其中一段，也无法推测后面是什么。如果密钥流是周期的，要完全做到随机性是困难的。严格地说，这样的序列不可能做到随机，只能要求截获比周期短的一段时不会泄露更多信息，这样的序列称为伪随机序列。

为讨论序列的随机性，先讨论随机序列的一般特性。 游程: 设{ai}=(a1a2a3…)为0、1序列，例如00110111，其前两个数字是00，称为0的2游程；接着是11，是1的2游程；再下来是0的1游程和1的3游程。

定义2.4：GF(2)上周期为T的序列{ai}的自相关函数定义为 当τ=0时，R(τ)=1；当τ≠0时，称R(τ)为异相自相关函数。

Golomb对伪随机周期序列提出了应满足的如下3个随机性公设： ① 在序列的一个周期内，0与1的个数相差至多为1。 ② 在序列的一个周期内，长为i的游程占游程总数的1/2i (i=1,2,…)，且在等长的游程中0的游程个数和1的游程个数相等。 ③ 异相自相关函数是一个常数。 ①说明{ai}中0与1出现的概率基本上相同; ②说明0与1在序列中每一位置上出现的概率相同; ③意味着通过对序列与其平移后的序列做比较，不能给出其他任何信息。

从密码系统的角度看，一个伪随机序列还应满足下面的条件： ① {ai}的周期相当大。 ② {ai}的确定在计算上是容易的。 ③ 由密文及相应的明文的部分信息，不能确定整个{ai}。

m序列满足Golomb的3个随机性公设。 定理2.7 GF(2)上的n长m序列{ai}具有如下性质： ① 在一个周期内，0、1出现的次数分别为2n-1-1和2n-1。 ② 在一个周期内，总游程数为2n-1；对1≤i≤n-2，长为i的游程有2n-i-1个，且0、1游程各半；长为n-1的0游程一个，长为n的1游程一个。 ③ {ai}的自相关函数为

证明： ① 在n长m序列的一个周期内，除了全0状态外，每个n长状态（共2n-1个）都恰好出现一次，这些状态中有2n-1个在a1位是1，其余2n-1-2n-1=2n-1-1个状态在a1位是0。 对n>2，当1≤i≤n-2时，n长m序列的一个周期内，长为i的0游程数目等于序列中如下形式的状态数目： 100…01*… … *，其中n-i-2个*可任取0或1。这种状态共有2n-i-2个。同理可得长为i的1游程数目也等于 2n-i-2，所以长为i的游程总数为2n-i-1。

由于寄存器中不会出现全0状态，所以不会出现0的n游程，但必有一个1的n游程，而且1的游程不会更大，因为若出现1的n+1游程，就必然有两个相邻的全1状态，但这是不可能的。这就证明了1的n游程必然出现在如下的串中： 当这n+2位通过移位寄存器时，便依次产生以下状态：

由于 ， 这两个状态只能各出现 一次，所以不会有1的n-1游程。 由于 ， 这两个状态只能各出现 一次，所以不会有1的n-1游程。 0的n-1游程只有一个: 于是在一个周期内，总游程数为

③ {ai}是周期为2n-1的m序列，对于任一正整数τ(0<τ<2n-1)，{ai}+{ai+τ}在一个周期内为0的位的数目正好是序列{ai}和{ai+τ}对应位相同的位的数目。

有限域上的二元加法流密码是目前最为常用的流密码体制，设滚动密钥生成器是线性反馈移位寄存器，产生的密钥是m序列。

设序列{ai}满足线性递推关系： 可表示为

或 Sh+1=M·Sh，其中 又设敌手知道一段长为2n的明文--密文对，即已知

于是可求出一段长为2n的密钥序列 其中 ,由此可推出线性反馈移位寄存器连续的n+1个状态：

做矩阵 而 则

例 设敌手得到密文串: 101101011110010 和相应的明文串: 011001111111001 相应的密钥流: 110100100001011 进一步假定敌手还知道密钥流是使用5级线性反馈移位寄存器产生的，那么敌手可分别用密文串中的前10个比特和明文串中的前10个比特建立如下方程

即 而

从而得到 所以 密钥流的递推关系为

2.6 非线性序列 为了使密钥流生成器输出的二元序列尽可能复杂，应保证其周期尽可能大、线性复杂度和不可预测性尽可能高，因此常使用多个LFSR来构造二元序列，称每个LFSR的输出序列为驱动序列，显然密钥流生成器输出序列的周期不大于各驱动序列周期的乘积，因此，提高输出序列的线性复杂度应从极大化其周期开始。

二元序列的线性复杂度: 指生成该序列的最短LFSR的级数。

Geffe序列生成器由3个LFSR组成，其中LFSR2作为控制生成器使用，如图2.12所示。

设LFSRi的特征多项式分别为ni次本原多项式，且ni 两两互素 图2.12 Geffe序列生成器 则Geffe序列的周期= 线性复杂度=

Geffe序列的周期实现了极大化，且0与1之间的分布大体上是平衡的。

2.6.2 J-K触发器 J-K触发器如图2.14所示，它的两个输入端分别用J和K表示，其输出ck不仅依赖于输入，还依赖于前一个输出位ck-1，即 其中x1和x2分别是J和K端的输入。由此可得J-K触发器的真值表，如表2.3。

图2.14 J-K触发器

利用J-K触发器的非线性序列生成器见图2.15。 {ak} :m级m序列 {bk}:n级m序列

当m与n互素且a0+b0=1时，序列{ck}的周期为(2m-1)(2n-1)。

例2.7 令m=2,n=3，两个驱动m序列分别为 {ak}=0,1,1,… 和 {bk}=1,0,0,1,0,1,1,… 于是，输出序列{ck}是0,1,1,0,1,0,0,1,1,1,0,1,0,1,0,0,1,0,0,1,0,…,其周期为(22-1)(23-1)=21。

由ck=(ak+bk+1)ck-1+ak可得 因此，如果知道{ck}中相邻位的值ck-1和ck，就可以推断出ak和bk中的一个。而一旦知道足够多的这类信息，就可通过密码分析的方法得到序列{ak}和{bk}。为了克服上述缺点，Pless提出了由多个J-K触发器序列驱动的多路复合序列方案，称为Pless生成器。

2.6.3 Pless生成器 Pless生成器由8个LFSR、4个J-K触发器和1个循环计数器构成，由循环计数器进行选通控制，如图2.16所示。假定在时刻t输出第t(mod 4)个单元，则输出序列为 a0b1c2d3a4b5d6

图2.16 Pless生成器

钟控序列最基本的模型是用一个LFSR控制另外一个LFSR的移位时钟脉冲，如图2.17所示。 2.6.4 钟控序列生成器 钟控序列最基本的模型是用一个LFSR控制另外一个LFSR的移位时钟脉冲，如图2.17所示。

图2.17 最简单的钟控序列生成器

假设LFSR1和LFSR2分别输出序列{ak}和{bk}，其周期分别为p1和p2。假设钟控序列{ck}的周期为p，可得如下关系：

f1(x): {ak} 的极小特征多项式, GF(2)上m次本原 f2(x): {bk}的极小特征多项式, GF(2)上n次本原 且m|n。 因此，p1=2m-1,p2=2n-1。又w1=2m-1， gcd(w1,p2)=1，所以p=p1p2=(2m-1)(2n-1)。 此外 {ck}的线性复杂度=n(2m-1) 极小特征多项式:

例 设LFSR1为3级m序列生成器，其特征多项式为f1(x)=1+x+x3。设初态为a0=a1=a2=1，于是输出序列为{ak}=1,1,1,0,1,0,0,…。 又设LFSR2为3级m序列生成器，且记其状态向量为σk，则在图2.17的构造下σk的变化情况如下：

{ck}的周期为(23-1)2=49，在它的一个周期内，每个σk恰好出现7次。 设f2(x)=1+x2+x3为LFSR2的特征多项式，且初态为b0=b1=b2=1，则{bk}=1,1,1,0,0,1,0，…。 由σk的变化情况得 {ck}=1,1,1,0,0,0,0,0, 1,0,1,1,1,1,1, 1,0,0,0,1,1,1, 0,1,1,1,1,1,1, 0,0,1,1,0,0,0, 1,1,1,1,0,0,0, 0,1,0,0,1,1,…

{ck}的极小特征多项式为1+x14+x21，其线性复杂度为 3·（23-1）=21，图2.18是其线性等价生成器。 图2.18 一个钟控序列的线性等价生成器

实际应用中，可以用上述最基本的钟控序列生成器构造复杂的模型，具体构造方式可参阅有关文献。

设计一个性能良好的序列密码是一项十分困难的任务。最基本的设计原则是“密钥流生成器的不可预测性”，它可分解为下述基本原则： ① 长周期。 ② 高线性复杂度。 ③ 统计性能良好。 ④ 足够的“混乱”。 ⑤ 足够的“扩散”。 ⑥ 抵抗不同形式的攻击。

第2章重点 流密码的加密和解密过程； 线性反馈移位寄存器及一元多项式表示； m序列具有伪随机性； m序列的破译方法； 非线性序列：Geffe生成器，J-K触发器，Pless生成器，钟控序列生成器。