现代密码学第2章.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 例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.6.4 钟控序列生成器 图2.17 最简单的钟控序列生成器 假设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)，极 小特征多项式为 。 例2.8 设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+x14x21，其线性复杂度为3·（23-1）=21，图2.18是其线性等价生成器。 图2.18 一个钟控序列的线性等价生成器 实际应用中，可以用上述最基本的钟控序列生成器构造复杂的模型，具体构造方式可参阅有关文献。 设计一个性能良好的序列密码是一项十分困难的任务。最基本的设计原则是“密钥流生成器的不可预测性”，它可分解为下述基本原则： ① 长周期。 ② 高线性复杂度。 ③ 统计性能良好。 ④ 足够的“混乱”。 ⑤ 足够的“扩散”。 ⑥ 抵抗不同形式的攻击。 本章作业 1、通过计算判断例2-5（P19）中线性反馈移位寄存器的输出序列的随机性 。 2、习题6（p33） 3、习题8（p33） 2-1 3级线性反馈移位寄存器在c3=1时可有4种线性反馈函数，设其初始状态为(a1,a2,a3)=(1,0,1)，求各线性反馈函数的输出序列及周期。 2-2 设n级线性反馈移位寄存器的特征多项式为p(x)，初始状态为(a1,a2,…,an-1,an)=(00…01)，证明输出序列的周期等于p(x)的阶。 2-3 设n=4, ，初始状态为(a1