第2章_流密码__现代密码学.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 为了使密钥流生成器输出的二元序列尽可能复杂，应保证其周期尽可能大、线性复杂度和不可预测性尽可能高，因此常使用多个LFSR来构造二元序列，称每个LFSR的输出序列为驱动序列。 显然，密钥流生成器输出序列的周期不大于各驱动序列周期的乘积，因此，提高输出序列的线性复杂度应从极大化其周期开始。 二元序列的线性复杂度指生成该序列的最短LFSR的级数，最短LFSR的特征多项式称为二元序列的极小特征多项式。 下面介绍4种由多个LFSR驱动的非线性序列生成器。 Geffe序列生成器由3个LFSR组成，其中LFSR2作为控制生成器使用，如图2.12所示。 图2.12 Geffe序列生成器图 2.6.1 Geffe序列生成器 当LFSR2输出1时，LFSR2与LFSR1相连接； 当LFSR2输出0时，LFSR2与LFSR3相连接。 若设LFSRi的输出序列为{a(i)k} (i=1,2,3)，则输出序列{bk}可以表示为 Geffe序列生成器也可以表示为图2.13的形式，其中 LFSR1和LFSR3作为多路复合器的输入 LFSR2控制多路复合器的输出 图2.13 多路复合器表示的Geffe序列生成器 设LFSRi的特征多项式分别为ni次本原多项式，且ni两两互素，则Geffe序列的周期为 线性复杂度为 Geffe序列的周期实现了极大化，且0与1之间的分布大体上是平衡的。 J-K触发器如图2.14所示，它的两个输入端分别用J和K表示，其输出ck不仅依赖于输入，还依赖于前一个输出位ck-1，即 其中x1和x2分别是J和K端的输入。 图2.14 J-K触发器 2.6.2 J-K触发器 由此可得J-K触发器的真值表，如表2.3。 J K ck 0 0 ck-1 0 1 0 1 0 1 1 1 利用J-K触发器的非线性序列生成器见图2.15。 图2.15 利用J-K触发器的非线性序列生成器 在图2.15中，令驱动序列{ak}和{bk}分别为m级和n级m序列，则有 如果令c-1=0，则输出序列的最初3项为 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生成器。 Pless生成器由8个LFSR、4个J-K触发器和1个循环计数器构成，由循环计数器进行选通控制，如图2.16所示。假定在时刻t输出第t(mod 4)个单元，则输出序列为 a0b1c2d3a4b5d6 2.6.3 Pless生成器 图2.16 Pless生成器 钟控序列最基本的模型是用一个LFSR控制另外一个LFSR的移位时钟脉冲，如图2.17所示。 图2.17 最简单的钟控序列生成器 2.6.4 钟控序列生成器 假设LFSR1和LFSR2分别输出序列{ak}和{bk}，其周期分别为p1和p2。 当LFSR1输出1时，移位时钟脉冲通过与门使LFSR2进行一次移位，从而生成下一位。 当LFSR1输出0时，移位时钟脉冲无法通过与门影响LFSR2。因此LFSR2重复输出前一位。 假设钟控序列{ck}的周期为p，可得如下关系： 其中 。 又设{ak}和{bk}的极小特征多项式分别为GF(2)上的m和n次本原多项式f1(x)和f2(x)，且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)，极小特