《现代密码学第2章.ppt》由会员分享，可在线阅读，更多相关《现代密码学第2章.ppt（112页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第2章章 流密码流密码2.1 流密码的基本概念流密码的基本概念2.2 线性反馈移位寄存器线性反馈移位寄存器2.3 线性移位寄存器的一元多项式表示线性移位寄存器的一元多项式表示2.4 m序列的伪随机性序列的伪随机性2.5 m序列密码的破译序列密码的破译2.6 非线性序列非线性序列习题习题流密码可以认为是起源于流密码可以认为是起源于20世纪世纪20年代的年代的Vernam密码体制。当密码体制。当Vernam密码中的密钥序列是随机的密码中的密钥序列是随机的（0，1）序列时，它就是）序列时，它就是“一次一密一次一密”密码体制。密码体制。Shannon已经证明了已经证明了“一次一密一次一密”密码体制在
2、理论密码体制在理论上上是不可破译的。这给予序列密码技术的研究和应用是不可破译的。这给予序列密码技术的研究和应用于强大的支持。于强大的支持。由于随机的密钥的产生、存储和分配等方面存由于随机的密钥的产生、存储和分配等方面存在一定的困难，在一定的困难，Vernam密码在当时并没有得到广密码在当时并没有得到广泛的应用。随着微电子技术和数学理论的发展与完泛的应用。随着微电子技术和数学理论的发展与完善，基于伪随机序列的流密码得到了长足的发展和善，基于伪随机序列的流密码得到了长足的发展和2.1 流密码的基本概念流密码的基本概念应用，在流密码中，加密和解密所用的密钥序列都应用，在流密码中，加密和解密所用的密钥
3、序列都是伪随机序列。伪随机序列的产生比较容易并且有是伪随机序列。伪随机序列的产生比较容易并且有比较成熟的数学理论工具。目前，流密码是世界各比较成熟的数学理论工具。目前，流密码是世界各国的军事和外交等领域中使用的主要密码体制之一。国的军事和外交等领域中使用的主要密码体制之一。流密码的基本思想是利用密钥流密码的基本思想是利用密钥k产生一个密钥流产生一个密钥流z=z0z1，并使用如下规则对明文串并使用如下规则对明文串x=x0 x1x2加加密：密：y=y0y1y2=Ez0(x0)Ez1(x1)Ez2(x2)。密钥密钥流由密钥流发生器流由密钥流发生器f产生：产生：zi=f(k,i)，这里这里i是加密是加
4、密器中的记忆元件（存储器）在时刻器中的记忆元件（存储器）在时刻i的状态，的状态，f是由密是由密钥钥k和和i产生的函数。产生的函数。分组密码与流密码的区别就在于有无记忆性（如图分组密码与流密码的区别就在于有无记忆性（如图2.1）。流密码的滚动密钥）。流密码的滚动密钥z0=f(k,0)由函数由函数f、密钥密钥k和指定的初态和指定的初态0完全确定。此后，由于输入加密器完全确定。此后，由于输入加密器的明文可能影响加密器中内部记忆元件的存储状态，的明文可能影响加密器中内部记忆元件的存储状态，因而因而i(i0)可能依赖于可能依赖于k，0，x0，x1，xi-1等参等参数。数。图图2.1 分组密码和流密码的比
5、较分组密码和流密码的比较根据加密器中记忆元件的存储状态根据加密器中记忆元件的存储状态i是否依赖于输是否依赖于输入的明文字符，流密码可进一步分成同步和自同步入的明文字符，流密码可进一步分成同步和自同步两种。两种。i独立于明文字符的叫做同步流密码，否则独立于明文字符的叫做同步流密码，否则叫做自同步流密码。由于自同步流密码的密钥流的叫做自同步流密码。由于自同步流密码的密钥流的产生与明文有关，因而较难从理论上进行分析。目产生与明文有关，因而较难从理论上进行分析。目前大多数研究成果都是关于同步流密码的。在同步前大多数研究成果都是关于同步流密码的。在同步流密码中，由于流密码中，由于zi=f(k,i)与明文
6、字符无关，因而此与明文字符无关，因而此时密文字符时密文字符yi=Ezi(xi)也不依赖于此前的明文字符。也不依赖于此前的明文字符。因此，可将同步流密码的加密器分成密钥流产生器因此，可将同步流密码的加密器分成密钥流产生器和加密变换器两个部分。如果与上述加密变换对应和加密变换器两个部分。如果与上述加密变换对应的解密变换为的解密变换为xi=Dzi(yi)，则可给出同步流密码体制则可给出同步流密码体制的模型如图的模型如图2.2所示。所示。2.1.1 同步流密码同步流密码图图2.2 同步流密码体制模型同步流密码体制模型 同步流密码的加密变换同步流密码的加密变换Ezi可以有多种选择，只要保可以有多种选择，
7、只要保证变换是可逆的即可。实际使用的数字保密通信系证变换是可逆的即可。实际使用的数字保密通信系统一般都是二元系统，因而在有限域统一般都是二元系统，因而在有限域CF(2)上讨论上讨论的二元加法流密码（如图的二元加法流密码（如图2.3）是目前最为常用的流）是目前最为常用的流密码体制，其加密变换可表示为密码体制，其加密变换可表示为yi=zi xi。图图2.3 加法流密码体制模型加法流密码体制模型一次一密密码是加法流密码的原型。事实上，如果一次一密密码是加法流密码的原型。事实上，如果z zi i=k=ki i（即密钥用作滚动密钥流），则加法流密码就（即密钥用作滚动密钥流），则加法流密码就退化成一次一密
8、密码。实际使用中，密码设计者的退化成一次一密密码。实际使用中，密码设计者的最大愿望是设计出一个滚动密钥生成器，使得密钥最大愿望是设计出一个滚动密钥生成器，使得密钥经其扩展成的密钥流序列具有如下性质：极大的周经其扩展成的密钥流序列具有如下性质：极大的周期、良好的统计特性、抗线性分析、抗统计分析。期、良好的统计特性、抗线性分析、抗统计分析。有限状态自动机是具有离散输入和输出（输入集和有限状态自动机是具有离散输入和输出（输入集和输出集均有限）的一种数学模型，由以下输出集均有限）的一种数学模型，由以下3部分组部分组成：成：有限状态集有限状态集S=si|i=1,2,l。有限输入字符集有限输入字符集A1=
9、A(1)j|j=1,2,m和有限输出和有限输出字符集字符集A2=A(2)k|k=1,2,n。转移函数转移函数A(2)k=f1(si,A(1)j)，sh=f2(si,A(1)j)即在状态即在状态为为si，输入为输入为A(1)j时，输出为时，输出为A(2)k，而状态转移为而状态转移为sh。2.1.2 有限状态自动机有限状态自动机例例2.1 S=s1,s2,s3，A1=A(1)1,A(1)2,A(1)3，A2=A(2)1,A(2)2,A(2)3，转移函数由表转移函数由表2.1给出。（见给出。（见16页表页表2.1）有限状态自动机可用有向图表示，称为转移图。转有限状态自动机可用有向图表示，称为转移图。
10、转移图的顶点对应于自动机的状态，若状态移图的顶点对应于自动机的状态，若状态si在输入在输入A(1)i时转为状态时转为状态sj，且输出一字符且输出一字符A(2)j，则在转移图则在转移图中，从状态中，从状态si到状态到状态sj有一条标有有一条标有(A(1)i,A(2)j)的弧线，的弧线，见图见图2.4。图图2.4 有限状态自动机的转移图有限状态自动机的转移图例例2.1中，若输入序列为中，若输入序列为A(1)1A(1)2A(1)1A(1)3A(1)3A(1)1，初始状态为初始状态为s1，则得到状态序列则得到状态序列s1s2s2s3s2s1s2输出字符序列输出字符序列A(2)1A(2)1A(2)2A(
11、2)1A(2)3A(2)1同步流密码的关键是密钥流产生器。一般可将其看同步流密码的关键是密钥流产生器。一般可将其看成一个参数为成一个参数为k的有限状态自动机，由一个输出符的有限状态自动机，由一个输出符号集号集Z、一个状态集一个状态集、两个函数、两个函数和和以及一个初以及一个初始状态始状态0组成（如图组成（如图2.5）。状态转移函数）。状态转移函数:ii+1，将当前状态将当前状态i变为一个新状态变为一个新状态i+1，输出函数输出函数:izi，当前状态当前状态i变为输出符号集中的一个元素变为输出符号集中的一个元素zi。这种密钥流生成器设计的关键在于找出适当的这种密钥流生成器设计的关键在于找出适当的
12、状态转移函数状态转移函数和输出函数和输出函数，使得输出序列使得输出序列z满足满足密钥流序列密钥流序列z应满足的几个条件，并且要求在设备应满足的几个条件，并且要求在设备上是节省的和容易实现的。为了实现这一目标，必上是节省的和容易实现的。为了实现这一目标，必须采用非线性函数。须采用非线性函数。2.1.3 密钥流产生器密钥流产生器图图2.5 作为有限状态自动机的密钥流生成器作为有限状态自动机的密钥流生成器由于具有非线性的由于具有非线性的的有限状态自动机理论很不完的有限状态自动机理论很不完善，相应的密钥流产生器的分析工作受到极大的限善，相应的密钥流产生器的分析工作受到极大的限制。相反地，当采用线性的制
13、。相反地，当采用线性的和非线性的和非线性的时，将时，将能够进行深入的分析并可以得到好的生成器。为方能够进行深入的分析并可以得到好的生成器。为方便讨论，可将这类生成器分成驱动部分和非线性组便讨论，可将这类生成器分成驱动部分和非线性组合部分（如图合部分（如图2.6）。驱动部分控制生成器的状态转）。驱动部分控制生成器的状态转移，并为非线性组合部分提供统计性能好的序列；移，并为非线性组合部分提供统计性能好的序列；而非线性组合部分要利用这些序列组合出满足要求而非线性组合部分要利用这些序列组合出满足要求的密钥流序列。的密钥流序列。图图2.6 密钥流生成器的分解密钥流生成器的分解目前最为流行和实用的密钥流产
14、生器如图目前最为流行和实用的密钥流产生器如图2.7所示，所示，其驱动部分是一个或多个线性反馈移位寄存器。其驱动部分是一个或多个线性反馈移位寄存器。图图2.7 常见的两种密钥流产生器常见的两种密钥流产生器移位寄存器是流密码产生密钥流的一个主要组成部移位寄存器是流密码产生密钥流的一个主要组成部分。分。GF(2)上一个上一个n级反馈移位寄存器由级反馈移位寄存器由n个二元存个二元存储器与一个反馈函数储器与一个反馈函数f(a1,a2,an)组成，如图组成，如图2.8所所示。示。2.2 线性反馈移位寄存器线性反馈移位寄存器图图2.8 GF(2)上的上的n级反馈移位寄存器级反馈移位寄存器每一存储器称为移位寄
15、存器的一级，在任一时刻，每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一这些级的内容构成该反馈移位寄存器的状态，每一状态对应于状态对应于GF(2)上的一个上的一个n维向量，共有维向量，共有2n种可能种可能的状态。每一时刻的状态可用的状态。每一时刻的状态可用n长序列长序列a1,a2,an或或n维向量维向量(a1,a2,an)表示，其中表示，其中ai是第是第i级存储器的内容。级存储器的内容。初始状态由用户确定，当第初始状态由用户确定，当第i个移位时钟脉冲到来时个移位时钟脉冲到来时，每一级存储器，每一级存储器ai都将其内容向下一级都将其内容向下一级ai-1传递
16、，并传递，并根据寄存器此时的状态根据寄存器此时的状态a1,a2,an计算计算f(a1,a2,an)，作为下一时刻的作为下一时刻的an。反馈函数反馈函数f(a1,a2,an)是是n元元布尔函数，即布尔函数，即n个变元个变元a1,a2,an可以独立地取可以独立地取0和和1这两个可能的值，函数中的运算有逻辑与、逻辑或、这两个可能的值，函数中的运算有逻辑与、逻辑或、逻辑补等运算，最后的函数值也为逻辑补等运算，最后的函数值也为0或或1。例例2.2 图图2.9是一个是一个3级反馈移位寄存器，其初始状态级反馈移位寄存器，其初始状态为为(a1,a2,a3)=(1,0,1)，输出可由表输出可由表2.2求出。求出
17、。图图2.9 一个一个3级反馈移位寄存器级反馈移位寄存器表表2.2 一个一个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的线性函数，则称之为线性反馈移位寄存器的线性函数，则称之为线性反馈移位寄存器LFSR（linear feedback shift register）。）。此时此时f可写可写为为f(a1,a2,an)
18、=cna1 cn-1a2 c1an其中常数其中常数ci=0或或1，是模是模2加法。加法。ci=0或或1可用开关可用开关的断开和闭合来实现，如图的断开和闭合来实现，如图2.10所示。所示。图图2.10 GF(2)上的上的n级线性反馈移位寄存器级线性反馈移位寄存器输出序列输出序列at满足满足an+t=cnat cn-1at+1 c1an+t-1其中其中t为非负正整数。为非负正整数。线性反馈移位寄存器因其实现简单、速度快、有较线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最为成熟的理论等优点而成为构造密钥流生成器的最重要的部件之一。重要的部件之一。例例2.3
19、图图2.11是一个是一个5级线性反馈移位寄存器，其初级线性反馈移位寄存器，其初始状态为（始状态为（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出输出可求出输出序列为序列为1001101001000010101110110001111100110周期为周期为31。图图2.11 一个一个5级线性反馈移位寄存器级线性反馈移位寄存器在线性反馈移位寄存器中总是假定在线性反馈移位寄存器中总是假定c1,c2,cn中至少中至少有一个不为有一个不为0，否则，否则f(a1,a2,an)0，这样的话，在这样的话，在n个脉冲后状态必然是个脉冲后状态必然是000，且这个状态必将一直，且这个状态必将一直持
20、续下去。若只有一个系数不为持续下去。若只有一个系数不为0，设仅有，设仅有cj不为不为0，实际上是一种延迟装置。一般对于，实际上是一种延迟装置。一般对于n级线性反馈级线性反馈移位寄存器，总是假定移位寄存器，总是假定cn=1。线性反馈移位寄存器输出序列的性质完全由其反馈线性反馈移位寄存器输出序列的性质完全由其反馈函数决定。函数决定。n级线性反馈移位寄存器最多有级线性反馈移位寄存器最多有2n个不个不同的状态。若其初始状态为同的状态。若其初始状态为0，则其状态恒为，则其状态恒为0。若。若其初始状态非其初始状态非0，则其后继状态不会为，则其后继状态不会为0。因此。因此n级级线性反馈移位寄存器的状态周期小
21、于等于线性反馈移位寄存器的状态周期小于等于2n-1。其其输出序列的周期与状态周期相等，也小于等于输出序列的周期与状态周期相等，也小于等于2n-1。只要选择合适的反馈函数便可使序列的周期达到最只要选择合适的反馈函数便可使序列的周期达到最大值大值2n-1，周期达到最大值的序列称为周期达到最大值的序列称为m序列。序列。设级线性移位寄存器的输出序列满足递推关系设级线性移位寄存器的输出序列满足递推关系an+k=c1an+k-1 c2an+k-2 cnak (*)对对任任何何成成立立。这这种种递递推推关关系系可可用用一一个个一一元元高高次次多多项项式式P(x)=1+c1x+cn-1xn-1cnxn表表示示
22、，称称这这个个多多项项式式为为LFSR的的特特征征多多项项式式或或特特征征多项式。多项式。2.3 线性移位寄存器的一元多项式表示线性移位寄存器的一元多项式表示设设n级级线线性性移移位位寄寄存存器器对对应应于于递递推推关关系系(*)，由由于于aiGF(2)(i=1,2,n)，所所以以共共有有2n组组初初始始状状态态，即即有有2n个个递递推推序序列列，其其中中非非恒恒零零的的有有2n-1个个，记记2n-1个非零序列的全体为个非零序列的全体为G(p(x)。定义定义2.1 给定序列给定序列ai，幂级数幂级数A(x)=aixi-1 称为该序列的生成函数。称为该序列的生成函数。定理定理2.1设设p(x)=
23、1+c1x+cn-1xn-1+cnxn是是GF(2)上的上的多项式，多项式，G(p(x)中任一序列中任一序列ai的生成函数的生成函数A(x)满满足：足：A(x)=(x)/p(x)其中其中(x)=(cn-ixn-iajxj-1)证明：证明：在等式在等式an+1=c1an c2an-1 cna1an+2=c1an+1 c2an cna2 两边分别乘以两边分别乘以xn,xn+1,，再求和，可得再求和，可得A(x)-(a1+a2x+anxn-1)=c1xA(x)-(a1+a2x+an-1xn-2)+c2x2A(x)-(a1+a2x+an-2xn-3)+cnxnA(x)移项整理得移项整理得(1+c1x+
24、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)=cn-ixn-iajxj-1=(x)(证毕证毕)注意在注意在GF(2)上有上有a+a=0。定理定理2.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
25、(x)G(q(x)。反之，若反之，若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
26、级级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。证明：由证明：由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)=(
27、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输出序列的周期输出序列的周期r不依赖于初始条件，而不依赖于初始条件，而依赖于特征多项式依赖于特征多项式p(x)。我们感兴趣的是我们感兴趣的是LFSR遍遍历历2n-1个非零状
28、态，这时序列的周期达到最大个非零状态，这时序列的周期达到最大2n-1，这种序列就是这种序列就是m序列。显然对于特征多项式一样，序列。显然对于特征多项式一样，而仅初始条件不同的两个输出序列，一个记为而仅初始条件不同的两个输出序列，一个记为a(1)i，另一个记为另一个记为a(2)i，其中一个必是另一个的其中一个必是另一个的移位，即存在一个常数移位，即存在一个常数k，使得使得a(1)i=a(2)k+i,i=1,2,下面讨论特征多项式满足什么条件时，下面讨论特征多项式满足什么条件时，LFSR的输的输出序列为出序列为m序列。序列。定义定义2-3 仅能被非仅能被非0常数或自身的常数倍除尽，但不常数或自身的
29、常数倍除尽，但不能被其它多项式除尽的多项式称为即约多项式或不能被其它多项式除尽的多项式称为即约多项式或不可约多项式。可约多项式。不可约多项式与讨论的域有关。例如不可约多项式与讨论的域有关。例如f（x）x21，在实数域上是不可约多项式，而在复数域，在实数域上是不可约多项式，而在复数域上可分解为上可分解为f（x）（）（xi）（）（xi）。）。定理定理2.4 设设p(x)是是n次不可约多项式，周期为次不可约多项式，周期为m，序序列列aiG(p(x)，则则ai的周期为的周期为m。证明：设证明：设ai的周期为的周期为r，由定理由定理2.3有有r|m，所以所以rm。设设A(x)为为ai的生成函数，的生成函
30、数，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)于是于是A(x)=a1+a2x+arxr-1/(xr-1)=(x)p(x)，即即p(x)(a1+a2x+arxr-1)=(x)(xr-1)因因p(x)是不可约的，并且是不可约的，并且(x)的次数不超过的次数不超过n1，所以所以gcd(p(x),(x)=1，p(x)|(xr-1)
31、，因此因此mr。综上综上r=m。（。（证毕）证毕）定理定理2.5 n级级LFSR产生的序列有最大周期产生的序列有最大周期2n-1的必的必要条件是其特征多项式为不可约的。要条件是其特征多项式为不可约的。证明：设证明：设n级级LFSR产生的序列周期达到最大产生的序列周期达到最大2n-1，除除0序列外，每一序列的周期由特征多项式惟一决序列外，每一序列的周期由特征多项式惟一决定，而与初始状态无关。设特征多项式为定，而与初始状态无关。设特征多项式为p(x)，若若p(x)可约，可设为可约，可设为p(x)=g(x)h(x)，其中其中g(x)不可约，不可约，且次数且次数k2，当当1in-2时，时，n长长m序列
32、的一个周期内，序列的一个周期内，长为长为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的游程不会更的游程不会更大，因为若出现大，因为若出现1的的n+1游程，就必然有两个相
33、邻的游程，就必然有两个相邻的全全1状态，但这是不可能的。这就证明了状态，但这是不可能的。这就证明了1的的n游程游程必然出现在如下的串中：必然出现在如下的串中：当这当这n+2位通过移位寄存器时，便依次产生以下状位通过移位寄存器时，便依次产生以下状态：态：由于由于 ，这两个状态只能各出现这两个状态只能各出现一次，所以不会有一次，所以不会有1的的n-1游程。游程。于是在一个周期内，总游程数为于是在一个周期内，总游程数为 ai是周期为是周期为2n-1的的m序列，对于任一正整数序列，对于任一正整数(02n-1)，ai+ai+在一个周期内为在一个周期内为0的位的数的位的数目正好是序列目正好是序列ai和和a
34、i+对应位相同的位的数目。对应位相同的位的数目。设序列设序列ai满足递推关系：满足递推关系：ah+n=c1ah+n-1 c2ah+n-2 cnah故故ah+n+=c1ah+n+-1 c2ah+n+-2 cnah+ah+n ah+n+=c1(ah+n-1 ah+n+-1)c2(ah+n-2 ah+n+-2)cn(ah ah+)令令bj=aj aj+，由递推序列由递推序列ai可推得递推序列可推得递推序列bi，bi满足满足bh+n=c1bh+n-1 c2bh+n-2 cnbhbi也是也是m序列。为了计算序列。为了计算R()，只要用只要用bi在一个在一个周期中周期中0的个数减去的个数减去1的个数，再除
35、以的个数，再除以2n-1，即即（证毕）（证毕）上上面面说说过过，有有限限域域上上的的二二元元加加法法流流密密码码（如如图图2.3）是是目目前前最最为为常常用用的的流流密密码码体体制制，设设滚滚动动密密钥钥生生成成器器是是线线性性反反馈馈移移位位寄寄存存器器，产产生生的的密密钥钥是是m序序列列。又又设设Sh和和Sh+1是序列中两个连续的是序列中两个连续的n长向量，其中长向量，其中2.5 m序列密码的破译序列密码的破译设序列设序列ai满足线性递推关系：满足线性递推关系：可表示为可表示为或或Sh+1=MSh，其中其中又设敌手知道一段长为又设敌手知道一段长为2n的明密文对，即已知的明密文对，即已知于是
36、可求出一段长为于是可求出一段长为2n的密钥序列的密钥序列其中其中 ,由此可推出线性由此可推出线性反馈移位寄存器连续的反馈移位寄存器连续的n+1个状态：个状态：做矩阵做矩阵而而若若X可逆，则可逆，则下面证明下面证明X的确是可逆的。的确是可逆的。因为因为X是由是由S1,S2,Sn作为列向量，要证作为列向量，要证X可逆，只可逆，只要证明这要证明这n个向量线性无关。个向量线性无关。由序列递推关系：由序列递推关系：可推出向量的递推关系：可推出向量的递推关系：设设m(mn+1)是使是使S1,S2,Sm线性相关的最小整数，线性相关的最小整数，即存在不全为即存在不全为0的系数的系数l1,l2,lm，其中不妨设
37、其中不妨设l1=1，使得使得即即对于任一整数对于任一整数i有有由此又推出密钥流的递推关系：由此又推出密钥流的递推关系：即密钥流的级数小于即密钥流的级数小于m。若若mn，则得出密钥流的则得出密钥流的级数小于级数小于n，矛盾。所以矛盾。所以m=n+1，从而矩阵从而矩阵X必是必是可逆的。可逆的。例例2.6 设敌手得到密文串设敌手得到密文串101101011110010和相应的和相应的明文串明文串011001111111001，因此可计算出相应的密钥，因此可计算出相应的密钥流为流为110100100001011。进一步假定敌手还知道密。进一步假定敌手还知道密钥流是使用钥流是使用5级线性反馈移位寄存器产
38、生的，那么级线性反馈移位寄存器产生的，那么敌手可分别用密文串中的前敌手可分别用密文串中的前10个比特和明文串中的个比特和明文串中的前前10个比特建立如下方程个比特建立如下方程即即而而从而得到从而得到所以所以密钥流的递推关系为密钥流的递推关系为在在2.1.3节节已已介介绍绍密密钥钥流流生生成成器器可可分分解解为为驱驱动动子子系系统统和和非非线线性性组组合合子子系系统统，如如图图2.6所所示示。驱驱动动子子系系统统常常用用一一个个或或多多个个线线性性反反馈馈移移位位寄寄存存器器来来实实现现，非非线线性性组组合合子子系系统统用用非非线线性性组组合合函函数数F来来实实现现，如如图图2.7所所示。本节介
39、绍第示。本节介绍第2部分非线性组合子系统。部分非线性组合子系统。2.6 非线性序列非线性序列为了使密钥流生成器输出的二元序列尽可能复杂，为了使密钥流生成器输出的二元序列尽可能复杂，应保证其周期尽可能大、线性复杂度和不可预测性应保证其周期尽可能大、线性复杂度和不可预测性尽可能高，因此常使用多个尽可能高，因此常使用多个LFSR来构造二元序列，来构造二元序列，称每个称每个LFSR的输出序列为驱动序列，显然密钥流的输出序列为驱动序列，显然密钥流生成器输出序列的周期不大于各驱动序列周期的乘生成器输出序列的周期不大于各驱动序列周期的乘积，因此，提高输出序列的线性复杂度应从极大化积，因此，提高输出序列的线性
40、复杂度应从极大化其周期开始。其周期开始。二元序列的线性复杂度指生成该序列的最短二元序列的线性复杂度指生成该序列的最短LFSR的级数，最短的级数，最短LFSR的特征多项式称为二元序列的的特征多项式称为二元序列的极小特征多项式。极小特征多项式。下面介绍下面介绍4种由多个种由多个LFSR驱动的非线性序列生成器。驱动的非线性序列生成器。Geffe序列生成器由序列生成器由3个个LFSR组成，其中组成，其中LFSR2作作为控制生成器使用，如图为控制生成器使用，如图2.12所示。所示。2.6.1 Geffe序列生成器序列生成器图图2.12 Geffe序列生成器图序列生成器图当当LFSR2输出输出1时，时，L
41、FSR2与与LFSR1相连接；当相连接；当LFSR2输出输出0时，时，LFSR2与与LFSR3相连接。若设相连接。若设LFSRi的输出序列为的输出序列为a(i)k(i=1,2,3)，则输出序列则输出序列bk可以表示为可以表示为Geffe序列生成器也可以表示为图序列生成器也可以表示为图2.13的形式，其中的形式，其中LFSR1和和LFSR3作为多路复合器的输入，作为多路复合器的输入，LFSR2控控制多路复合器的输出。设制多路复合器的输出。设LFSRi的特征多项式分别的特征多项式分别为为ni次本原多项式，且次本原多项式，且ni两两互素，则两两互素，则Geffe序列的序列的周期为周期为线性复杂度为线
42、性复杂度为图图2.13 多路复合器表示的多路复合器表示的Geffe序列生成器序列生成器Geffe序列的周期实现了极大化，且序列的周期实现了极大化，且0与与1之间的分之间的分布大体上是平衡的。布大体上是平衡的。虽然这个发生器从理论上来看似乎很好，但实虽然这个发生器从理论上来看似乎很好，但实质上这是一个很弱的密码，它不能抵抗相关攻击。质上这是一个很弱的密码，它不能抵抗相关攻击。这是因为发生器的输出有这是因为发生器的输出有75与与LFSR-1的时的时间相同。因此，若已知间相同。因此，若已知LFSR的级数的级数n1和其各级的和其各级的系数系数c1,c2,cn2,便能猜出便能猜出LFSR-1的初始值和寄
43、存的初始值和寄存器所输出的序列，就可以猜出器所输出的序列，就可以猜出LFSR-2的输出中与的输出中与这个发生器的相同的次数。如果猜对了，两个序列这个发生器的相同的次数。如果猜对了，两个序列相同的概率为相同的概率为75，若猜错了，两个序列相同的概，若猜错了，两个序列相同的概率为率为50。类似的，发生器输出与类似的，发生器输出与LFSR-3的输出相等的输出相等的概率为的概率为75。有了这种相关性，密钥序列发。有了这种相关性，密钥序列发生器很容易被破译。例如，如果三个本原多项生器很容易被破译。例如，如果三个本原多项式都是三项式，其中最大长度为式都是三项式，其中最大长度为n，那么仅需要，那么仅需要37
44、n的一段输出序列就能重构这三个的一段输出序列就能重构这三个LFSR的内的内部状态。部状态。J-K触发器如图触发器如图2.14所示，它的两个输入端分别用所示，它的两个输入端分别用J和和K表示，其输出表示，其输出ck不仅依赖于输入，还依赖于前不仅依赖于输入，还依赖于前一个输出位一个输出位ck-1，即即其中其中x1和和x2分别是分别是J和和K端的输入。由此可得端的输入。由此可得J-K触触发器的真值表，如表发器的真值表，如表2.3。（见。（见26页表页表2.3）2.6.2 J-K触发器触发器图图2.14 J-K触发器触发器利用利用J-K触发器的非线性序列生成器见图触发器的非线性序列生成器见图2.15。
45、图图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,其周期
46、为其周期为(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触发
47、器和触发器和1个循环个循环计数器构成，由循环计数器进行选通控制，如图计数器构成，由循环计数器进行选通控制，如图2.16所示。假定在时刻所示。假定在时刻t输出第输出第t(mod 4)个单元，则个单元，则输出序列为输出序列为a0b1c2d3a4b5d62.6.3 Pless生成器生成器图图2.16 Pless生成器生成器钟控序列最基本的模型是用一个钟控序列最基本的模型是用一个LFSR控制另外一控制另外一个个LFSR的移位时钟脉冲，如图的移位时钟脉冲，如图2.17所示。所示。2.6.4 钟控序列生成器钟控序列生成器图图2.17 最简单的钟控序列生成器最简单的钟控序列生成器假设假设LFSR1和和LFS
48、R2分别输出序列分别输出序列ak和和bk，其其周期分别为周期分别为p1和和p2。当当LFSR1输出输出1时，移位时钟时，移位时钟脉冲通过与门使脉冲通过与门使LFSR2进行一次移位，从而生成下进行一次移位，从而生成下一位。当一位。当LFSR1输出输出0时，移位时钟脉冲无法通过时，移位时钟脉冲无法通过与门影响与门影响LFSR2。因此因此LFSR2重复输出前一位。假重复输出前一位。假设钟控序列设钟控序列ck的周期为的周期为p，可得如下关系：可得如下关系：其中其中 。又设又设ak和和bk的极小特征多项式分别为的极小特征多项式分别为GF(2)上的上的m和和n次本原多项式次本原多项式f1(x)和和f2(x
49、)，且且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，则在图则在
50、图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