第4章(序列密码)课件.ppt

《第4章(序列密码)课件.ppt》由会员分享，可在线阅读，更多相关《第4章(序列密码)课件.ppt（84页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第4章 有关序列密码和移位寄存器4.1 引言4.2 序列密码的一般原理4.3 线性移位寄存器4.4 线性移位寄存器的一元多项式表示4.5 m序列的伪随机性4.6 m序列密码的破译4.7 非线性序列习题4.1 引言引言 人们试图用序列密码方式仿效”一次一密”密码.从而促成了序列密码的研究和发展.序列密码是世界军事,外交等领域应用的主流密码体制.在通常的序列密码中,加解密用的密钥序列是伪随机序列,它的产生容易且有较成熟的理论工具,所以序列密码是当前通用的密码系统.序列密码的安全性主要依赖于密钥序列,因而什么样的伪随机序列是安全可靠的密钥序列,以及如何实现这种序列就成了序列密码中研究的一个主要方面.

2、序列密码的基本思想是利用一个短密钥k通过一个算法来产生一个密钥流k=k0k1，并使用如下规则对明文串m=m0m1m2加密：c=c0c1c2=Ek0(m0)Ek1(m1)Ek2(m2)。密钥流由密钥流发生器A产生：k0k1=A(k)，4.2 序列序列 密码的一般原理密码的一般原理 二进制序列密码体制模型由此可见,序列密码的安全性主要依赖于密钥序列k0k1=A(k)，当k0k1是离散无记忆的随机序列时,则该系统就是一次一密密码,它是不可破的.但通常A(k)是一个由k通过确定性算法产生的伪随机序列,因而此时,该系统就不再是完全保密的.设计序列密码的关键是设计密钥序列A(k)，密钥序列A(k)的设计应

3、考虑如下几个因素:(1)系统的安全保密性;(2)密钥k易于分配、保管，更换简便；(3)产生密钥序列简单快速。目前最为流行和实用的密钥流产生器，其驱动部分是一个或多个线性反馈移位寄存器。常见的两种密钥流产生器因为确定性算法产生的序列是周期的或准周期的，为了使序列密码达到要求的安全保密性，使得密钥经其扩展成的密钥流序列具有如下性质：极大的周期、良好的统计特性、抗线性分析、抗统计分析。我们仅对实用中最感兴趣的二元情形即GF(2)上的序列密码原理进行介绍，但其理论是可以在任何有限域GF(q)中进行研究的。移位寄存器是序列密码产生密钥流的一个主要组成部分。GF(2)上一个n级反馈移位寄存器由n个二元存储

4、器与一个反馈函数f(a1,a2,an)组成，如图4.2所示。2.2 线性反馈移位寄存器线性反馈移位寄存器图4.2 GF(2)上的n级反馈移位寄存器每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于GF(2)上的一个n维向量，共有2n种可能的状态。每一时刻的状态可用n长序列a1,a2,an或n维向量(a1,a2,an)表示，其中ai是第i级存储器的内容。初始状态由用户确定，当第i个移位时钟脉冲到来时，每一级存储器ai都将其内容向下一级ai-1传递，并根据寄存器此时的状态a1,a2,an计算f(a1,a2,an)，作为下一时刻的an。反馈函数f(a1

5、,a2,an)是n元布尔函数，即n个变元a1,a2,an可以独立地取0和1这两个可能的值，函数中的运算有逻辑与、逻辑或、逻辑补等运算，最后的函数值也为0或1。例4.1 图4-3 是一个3级反馈移位寄存器，其初始状态为(a1,a2,a3)=(1,0,1)，求出输出序列。图 4-3 一个3级反馈移位寄存器一个3级反馈移位寄存器的状态和输出状态状态（a1,a2,a3)输出输出1 0 11 1 01 1 10 1 11 0 11 1 0 101110即输出序列为101110111011，周期为4。如果移位寄存器的反馈函数f(a1,a2,an)是a1，a2，an的线性函数，则称之为线性反馈移位寄存器LF

6、SR（linear feedback shift register）。此时f可写为f(a1,a2,an)=cna1cn-1a2c1an其中常数ci=0或1，是模2加法。ci=0或1可用开关的断开和闭合来实现，如图4-4所示。图4-4 GF(2)上的n级线性反馈移位寄存器输出序列at满足an+t=cnatcn-1at+1c1an+t-1其中t为非负正整数。线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最重要的部件之一。例4.2 图4-5是一个5级线性反馈移位寄存器，其初始状态为（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出输出序列为100

7、1101001000010101110110001111100110周期为31。图4-5 一个5级线性反馈移位寄存器在线性反馈移位寄存器中总是假定c1,c2,cn中至少有一个不为0，否则f(a1,a2,an)0，这样的话，在n个脉冲后状态必然是000，且这个状态必将一直持续下去。若只有一个系数不为0，设仅有cj不为0，实际上是一种延迟装置。一般对于n级线性反馈移位寄存器，总是假定cn=1。线性反馈移位寄存器输出序列的性质完全由其反馈函数决定。n级线性反馈移位寄存器最多有2n个不同的状态。若其初始状态为0，则其状态恒为0。若其初始状态非0，则其后继状态不会为0。因此n级线性反馈移位寄存器的状态周

8、期小于等于2n-1。其输出序列的周期与状态周期相等，也小于等于2n-1。只要选择合适的反馈函数便可使序列的周期达到最大值2n-1，周期达到最大值的序列称为m序列。设n级线性移位寄存器的输出序列满足递推关系an+k=c1an+k-1 c2an+k-2 cnak (*)对任何 成立。这种递推关系可用一个一元高次多项式P(x)=1+c1x+cn-1xn-1cnxn表示，称这个多项式为LFSR的联系多项式或特征多项式。4.4 线性移位寄存器的一元多项式表示设n级线性移位寄存器对应于递推关系(*)，由于aiGF(2)(i=1,2,n)，所以共有2n组初始状态，即有2n个递推序列，其中非恒为零的序列 有

9、2n-1个，记 2n-1个 非 零 序 列 的 全 体 为G(p(x)。定义定义 给定序列ai，幂级数A(x)=aixi-1称为该序列的生成函数或母函数。定理定理4.1 设p(x)=1+c1x+cn-1xn-1+cnxn是GF(2)上的多项式，G(p(x)中任一序列ai的生成函数A(x)满足：A(x)=(x)/p(x)其中证明：证明：在等式an+1=c1anc2an-1cna1an+2=c1an+1c2ancna2 两边分别乘以xn,xn+1,，再求和，可得A(x)-(a1+a2x+anxn-1)=c1xA(x)-(a1+a2x+an-1xn-2)+c2x2A(x)-(a1+a2x+an-2x

10、n-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即p(x)A(x)=(证毕)注意在GF(2)上有a+a=0。引理:定理定理4.2 p(x)|q(x)的充要条件是G(p(x)G(q(x)。证明：证明：若p(x)|q(x)，可设q(x)=p(x)r(x)，因此A(x)=(x)/p(x)=(x)r(x)/p(x)r(x)=(x)r(x)/q(x)所以若aiG(p(x)，则aiG(q(x)，即G(p(x)G(q(x)。反之，若

11、G(p(x)G(q(x)，则对于多项式(x)，存在序列aiG(p(x)以 A(x)=(x)/p(x)为生成函数。特别地，对于多项式(x)=1，存在序列aiG(p(x)以1/p(x)为生成函数。由于G(p(x)G(q(x)，序列aiG(q(x)，所以存在函数r(x)，使得ai的生成函数也等于r(x)/q(x)，从而1/p(x)=r(x)/q(x)，即q(x)=p(x)r(x)，所以p(x)|q(x)。(证毕)上述定理说明可用n级LFSR产生的序列，也可用级数更多的LFSR来产生。定义定义4.2 设p(x)是GF(2)上的多项式，使p(x)|(xp-1)的最小p称为p(x)的周期或阶。定理定理4.

12、3 若序列ai的特征多项式p(x)定义在GF(2)上，p是p(x)的周期，则ai的周期r|p。证明证明：由p(x)周期的定义得p(x)|(xp-1)，因此存在q(x)，使得xp-1=p(x)q(x)，又由p(x)A(x)=(x)可得p(x)q(x)A(x)=(x)q(x)，所以(xp-1)A(x)=(x)q(x)。由于q(x)的次数为p-n，(x)的次数不超过n-1，所以(xp-1)A(x)的次数不超过(p-n)+(n-1)=p-1。这就证明了对于任意正整数i都有ai+p=ai。设p=kr+t,0tr，则ai+p=ai+kr+t=ai+t=ai，所以t=0，即r|p。（证毕）n级LFSR输出序

13、列的周期r不依赖于初始条件，而依赖于特征多项式p(x)。我们感兴趣的是LFSR遍历2n-1个非零状态，这时序列的周期达到最大2n-1，这种序列就是m序列。显然对于特征多项式一样，而仅初始条件不同的两个输出序列，一个记为a(1)i，另一个记为a(2)i，其中一个必是另一个的移位，即存在一个常数k，使得a(1)i=a(2)k+i,i=1,2,下面讨论特征多项式满足什么条件时，LFSR的输出序列为m序列。定理定理4.4 设p(x)是n次不可约多项式，周期为m，序列aiG(p(x)，则ai的周期为m。证明：证明：设ai的周期为r，由定理4.3有r|m，所以rm.设A(x)为ai的生成函数,A(x)=(

14、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)于是A(x)=a1+a2x+arxr-1/(xr-1)=(x)/p(x)，即p(x)(a1+a2x+arxr-1)=(x)(xr-1)因p(x)是不可约的，所以gcd(p(x),(x)=1，p(x)|(xr-1)，因此mr。综上r=m。（证毕）定理定理4.5 n级LFSR产生的序列有最大周期2n-1的必要条件

15、是其特征多项式为不可约的。证明：证明：设n级LFSR产生的序列周期达到最大2n-1，除0序列外，每一序列的周期由特征多项式惟一决定，而与初始状态无关。设特征多项式为p(x)，若p(x)可约，可设为p(x)=g(x)h(x)，其中g(x)不可约，且次数k2，当1in-2时，n长m序列的一个周期内，长为i的0游程数目等于序列中如下形式的状态数目：10001*，其中n-i-2个*可任取0或1。这种状态共有2n-i-2个。同理可得长为i的1游程数目也等于 2n-i-2，所以长为i的游程总数为2n-i-1。由于寄存器中不会出现全0状态，所以不会出现0的n游程，但必有一个1的n游程，而且1的游程不会更大，

16、因为若出现1的n+1游程，就必然有两个相邻的全1状态，但这是不可能的。这就证明了1的n游程必然出现在如下的串中：当这n+2位通过移位寄存器时，便依次产生以下状态：由于 ，这两个状态只能各出现一次，所以不会有1的n-1游程。于是在一个周期内，总游程数为 ai是周期为2n-1的m序列，对于任一正整数(02n-1)，ai+ai+在一个周期内为0的位的数目正好是序列ai和ai+对应位相同的位的数目。设序列ai满足递推关系：ah+n=c1ah+n-1c2ah+n-2cnah故ah+n+=c1ah+n+-1c2ah+n+-2cnah+ah+nah+n+=c1(ah+n-1ah+n+-1)c2(ah+n-2

17、ah+n+-2)cn(ahah+)令bj=ajaj+，由递推序列ai可推得递推序列bi，bi满足bh+n=c1bh+n-1c2bh+n-2cnbhbi也是m序列。为了计算R()，只要用bi在一个周期中0的个数减去1的个数，再除以2n-1，即（证毕）上面说过，有限域上的二元加法序列密码是目前最为常用的序列密码体制(图4-6)，设滚动密钥生成器是线性反馈移位寄存器，产生的密钥是m序列。又设Sh和Sh+1是序列中任意两个连续的向量，其中4.6 m序列密码的破译设序列ai满足线性递推关系：可表示为或Sh+1=MSh，其中又设敌手知道一段长为2n的明密文对，即已知于是可求出一段长为2n的密钥序列其中 ,

18、由此可推出线性反馈移位寄存器连续的n+1个状态：做矩阵而若X可逆，则下面证明X的确是可逆的。因为X是由S1,S2,Sn作为列向量，要证X可逆，只要证明这n个向量线性无关。由序列递推关系：可推出向量的递推关系：设m(mn+1)是使S1,S2,Sm线性相关的最小整数，即存在不全为0的系数l1,l2,lm，其中不妨设l1=1，使得即对于任一整数i有由此又推出密钥流的递推关系：即密钥流的级数小于m。若mn，则得出密钥流的级数小于n，矛盾。所以m=n+1，从而矩阵X必是可逆的。例4.5 设敌手得到密文串101101011110010和相应的明文串011001111111001，因此可计算出相应的密钥流为

19、110100100001011。进一步假定敌手还知道密钥流是使用5级线性反馈移位寄存器产生的，那么敌手可分别用密文串中的前10个比特和明文串中的前10个比特建立如下方程即而从而得到所以密钥流的递推关系为目前研究得比较充分的方法有非线性移位寄存器序列,对多个线性反馈移位寄存器进行非线性组合,利用非线性分组密码产生非线性序列,存储变换等.4.7 非线性序列一.非线性移位寄存器序列根据图4-2可知,令反馈函数f(a1,a2,an)为非线性函数便构成非线性移位寄存器,其输出序列为非线性序列.输出序列的周期最大可达 ,并称周期达到最大值的非线性移位寄存器序列为M序列,M序列具有下面定理所述的随机统计特性

20、:定理定理4.8 GF(2)上的n级M序列 具有如下性质：在一个周期内，0、1出现的次数各为 。在一个周期内，总游程数为 ；对1in-2，长为i的游程有 个，且0、1游程各半；长为n-1的游程不存在，长为n的0游程和1游程各一个。称两个周期序列为不同的,若其中一个不能由另一个经适当移位而得到.定理定理4.9 GF(2)上的n级M序列的数目为 个.例例4.6 令n=3,设初态为(101),则输出序列 为1011100010它是周期为8的序列,为M序列.一般的非线性移位寄存器尚处于艰难的研究之中,所以目前研究更多的还是在LFSR基础上的非线性化问题.为了使密钥流生成器输出的二元序列尽可能复杂，应保

21、证其周期尽可能大、线性复杂度和不可预测性尽可能高，因此常使用多个LFSR来构造二元序列，称每个LFSR的输出序列为驱动序列，显然密钥流生成器输出序列的周期不大于各驱动序列周期的乘积，因此，提高输出序列的线性复杂度应从极大化其周期开始。二二.对线性移位寄存器进行非线性对线性移位寄存器进行非线性组合组合二元序列的线性复杂度指生成该序列的最短LFSR的级数，最短LFSR的特征多项式称为二元序列的极小特征多项式。下面介绍几种由多个LFSR驱动的非线性序列生成器。图 利用J-K触发器的非线性序列生成器 J-K触发器令驱动序列ak和bk分别为m级和n级m序列，则有如果令c-1=0，则输出序列的最初3项为当

22、m与n互素且a0+b0=1时，序列ck的周期为(2m-1)(2n-1)。例4.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+1+bk)ck-1+ak可得因此，如果知道ck中相邻位的值ck-1和ck，就可以推断出ak和bk中的一个。而一旦知道足够多的这类信息，就可通过密码分析的方法得到序列ak和bk。为了克服上述缺点，Pless提出了由多个J-K触发器序列驱动的多路复合序列方案，称为

23、Pless生成器。Pless生成器由8个LFSR、4个J-K触发器和1个循环计数器构成，由循环计数器进行选择控制，如图4-8所示。假定在时刻t输出第t(mod 4)个单元，则输出序列为a0b1c2d3a4b5d6 Pless生成器图4-8 Pless生成器当8个线性移位寄存器的级数都互素时,且满足定理4.10的条件,输出序列周期可达它们各自周期的乘积.Pless体制的一个直观上的弱点是最后的选择器依次轮换输出,如果改为随机方式,似乎要好些.钟控序列最基本的模型是用一个LFSR控制另外一个LFSR的移位时钟脉冲。钟控序列基本钟控序列它由两个不同的线性移位寄存器LFSR1和LFSR2以及一个采样函

24、数S组成,通常 ,i=0,1,2,而输出的钟控序列其中 ,用于产生密钥序列的钟控序列产生器一般由多个基本钟控序列产生器的级联组成.移位-删除钟控序列两个不同的线性移位寄存器LFSR1和LFSR2各自单独运行,且有相同的时钟脉冲控制移位.LFSR1的最后两级输出相乘后控制LFSR2的输出,如果 ,LFSR2移位一步,但不输出;如果 ,则LFSR2移位一步,且输出 得到的序列 称为移位-删除钟控序列.例4.8 给定 和 的特征多项式分别为 和初态分别为 和 ,则有j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 aj 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1cj 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0bj 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1zj 1 0 1 1 0 1 0 1 1 0 0 1实际应用中，可以用上述最基本的钟控序列生成器构造复杂的模型，具体构造方式可参阅有关文献。设计一个性能良好的序列密码是一项十分困难的任务。最基本的设计原则是“密钥流生成器的不可预测性”，它可分解为下述基本原则：长周期。高线性复杂度。统计性能良好。足够的“混乱”。足够的“扩散”。抵抗不同形式的攻击。