密码学02－流密码.ppt

《密码学02－流密码.ppt》由会员分享，可在线阅读，更多相关《密码学02－流密码.ppt（90页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、密码学02流密码 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望流密码概况流密码概况2.1 2.1 流密码的基本概念流密码的基本概念布尔函数简介布尔函数简介2.2 2.2 线性反馈移位寄存器线性反馈移位寄存器2.3 2.3 线性移位寄存器的一元多项式表示线性移位寄存器的一元多项式表示 2.4 2.4 mm序列的伪随机性序列的伪随机性2.5 2.5 mm序列密码的破译序列密码的破译2.6 2.6 非线性序列非线性序列本章提要本章提要2流密码概况流密码概况流密码流密码

2、(stream cipher)是一种重要的密码体制是一种重要的密码体制l明文消息按字符或比特逐位加密明文消息按字符或比特逐位加密l流密码也称为序列密码流密码也称为序列密码(Sequence Cipher)流密码在手工和机械密码时代是主流技术流密码在手工和机械密码时代是主流技术流密码在流密码在50年代得到飞跃式发展年代得到飞跃式发展l密钥流可以用移位寄存器电路来产生，也促进了线性和密钥流可以用移位寄存器电路来产生，也促进了线性和非线性移位寄存器发展非线性移位寄存器发展主要用于专用和机密机构：军方，银行等主要用于专用和机密机构：军方，银行等l由于互联网是分组传输的，流密码的使用较少由于互联网是分组

3、传输的，流密码的使用较少3流密码具有有效的数学分析工具流密码具有有效的数学分析工具l代数代数(如布尔代数如布尔代数)、有限域理论和谱分析理论等等、有限域理论和谱分析理论等等l流密码在现代密码学阶段的主要成果来自于密码分析流密码在现代密码学阶段的主要成果来自于密码分析很多密码学家因流密码研究而成名很多密码学家因流密码研究而成名l肖国镇，肖国镇，Massey，Berlikamp等。等。l在在IEEE Transaction on Information Theory上能够发表的密码上能够发表的密码成果多数都是来自于流密码的相关研究成果多数都是来自于流密码的相关研究流密码基于硬件实现优势更明显，目前

4、也有些算法是针对流密码基于硬件实现优势更明显，目前也有些算法是针对软件设计的软件设计的l如如Ecrypt计划中的算法，计划中的算法，RC4等等参考资料参考资料：伪随机序列及其应用，流密码学及其应：伪随机序列及其应用，流密码学及其应用，肖国镇著用，肖国镇著42.1 流密码的基本概念流密码的基本概念流密码的基本思想流密码的基本思想l利用密钥利用密钥k产生一个密钥流产生一个密钥流z=z0z1z2，并使用如下规则，并使用如下规则对明文串对明文串x=x0 x1x2加密：加密：y=y0y1y2Ez0(x0)Ez1(x1)Ez2(x2)，密钥流密钥流l由密钥流发生器由密钥流发生器 f 产生：产生：zif(k

5、,i)li是加密器中的记忆元件在时刻是加密器中的记忆元件在时刻 i 的状态的状态l f 是由是由k,i 产生的函数产生的函数5 流密码流密码 分组密码分组密码内部记忆元件由一组移位寄存器构成内部记忆元件由一组移位寄存器构成 6流密码与分组密码的区别：在于有无记忆性流密码与分组密码的区别：在于有无记忆性l流密码的滚动密钥由函数流密码的滚动密钥由函数f、密钥、密钥k和指定的初态和指定的初态0完全确定完全确定l此后由于输入加密器的明文可能影响加密器中的内部记此后由于输入加密器的明文可能影响加密器中的内部记忆元件的存储状态，因而忆元件的存储状态，因而i(i0)可能依赖于可能依赖于k，0，x0，x1，x

6、i1，前前 i 个个明文和密钥及初态明文和密钥及初态l分组密码中，一组一组的加密，一般等长分组密码中，一组一组的加密，一般等长l在分组内明文和密钥充分混淆，分组间一般互不影响，在分组内明文和密钥充分混淆，分组间一般互不影响，与分组连接模式有关与分组连接模式有关72.1.1同步流密码同步流密码流密码可按记忆元件存储状态分类流密码可按记忆元件存储状态分类l按照加密器中记忆元件的存储状态按照加密器中记忆元件的存储状态i 是否依赖于输入的是否依赖于输入的明文字符流明文字符流，流密码可进一步分成，流密码可进一步分成同步同步和和自同步流密码自同步流密码两种两种li 独立于明文字符流的叫做同步流密码，否则叫

7、做自同独立于明文字符流的叫做同步流密码，否则叫做自同步流密码步流密码l由于由于自同步流密码的密钥流的产生与明文有关自同步流密码的密钥流的产生与明文有关，所以理论上难，所以理论上难于分析。于分析。l好的密码算法应该好的密码算法应该在理论上或基于实践检验能够证明其是安全在理论上或基于实践检验能够证明其是安全的或至少是没有明显漏洞的的或至少是没有明显漏洞的。l如果算法难于分析，则无法保证其安全性，也就无法放心使用，如果算法难于分析，则无法保证其安全性，也就无法放心使用，因此自同步流密码研究很少，很少采用。因此自同步流密码研究很少，很少采用。8目前大多数研究成果都是关于同步流密码的目前大多数研究成果都

8、是关于同步流密码的l由由于于zif(k,i)与与明明文文无无关关，此此刻刻的的密密文文字字符符yi=Ezi(xi)也也不不依依赖赖于于此此前前的的明明文文字字符符，这这样样可可将将同同步步流流密密码码的的加加密密器分成器分成密钥流产生器密钥流产生器和和加密变换器加密变换器两个部分。两个部分。l设解密变换为设解密变换为xi=Dzi(yi)。同步流密码体制模型如下图。同步流密码体制模型如下图9加密变换加密变换Ezi可有多种选择，保证变换可逆性即可可有多种选择，保证变换可逆性即可l比如明文流和密钥流对应位异或比如明文流和密钥流对应位异或l实际数字保密通信系统一般都是二元的实际数字保密通信系统一般都是

9、二元的0,1,在有限域在有限域GF(2)上讨论上讨论二元加法流密码二元加法流密码是目前最常用的流密码体制是目前最常用的流密码体制l加密变换可表示为加密变换可表示为yizi xi，加法流密码体制模型加法流密码体制模型10一次一密密码一次一密密码(One Time Padding 一次一密乱码本一次一密乱码本)是加法是加法流密码的原型流密码的原型l其中密钥的长度至少和明文的长度一样长，是无条件安全的，但其中密钥的长度至少和明文的长度一样长，是无条件安全的，但实用性较差，因而不能广泛应用。实用性较差，因而不能广泛应用。l如果加法流密码中，如果加法流密码中，ziki，即直接将密钥，即直接将密钥k(k至

10、少和明文一样长至少和明文一样长)用用作滚动的密钥流，则加法流密码就是一次一密密码。作滚动的密钥流，则加法流密码就是一次一密密码。流密码体制中如果密钥有限，则安全性一般低于一次一密流密码体制中如果密钥有限，则安全性一般低于一次一密l从信息论意义上讲，对从信息论意义上讲，对k比特长的串进行任何固定变换，其信息量比特长的串进行任何固定变换，其信息量至多为至多为k比特，即密钥流再长，其安全性最大也就是密钥长度，而比特，即密钥流再长，其安全性最大也就是密钥长度，而一次一密的密钥长度至少和明文一样。一次一密的密钥长度至少和明文一样。同步流密码算法的设计主要是密钥流产生器的设计同步流密码算法的设计主要是密钥

11、流产生器的设计l密钥产生器目标是：使得密钥密钥产生器目标是：使得密钥k经其扩展成的密钥流序列经其扩展成的密钥流序列z具有如下具有如下性质：性质：l极大的周期，良好的统计特性，抗差分分析，抗线性分析等极大的周期，良好的统计特性，抗差分分析，抗线性分析等112.1.2 有限状态自动机有限状态自动机流密码中任意时刻流密码中任意时刻密钥流密钥流和和密文密文的输出与状态密切的输出与状态密切相关。可以用有限状态自动机这一数学模型来表述相关。可以用有限状态自动机这一数学模型来表述有限状态自动机是具有离散输入和输出有限状态自动机是具有离散输入和输出（输入集和（输入集和输出集均有限）输出集均有限）的一种数学模型

12、的一种数学模型，由，由3部分组成：部分组成：l有限状态集有限状态集S=si|i=1,2,l 共有共有l个可能状态个可能状态l有限输入字符集有限输入字符集A1=Aj(1)|j=1,2,m和有限输出字符集和有限输出字符集A2=Ak(2)|k=1,2,n。l转移函数转移函数:lAk(2)=f1(si,Aj(1)，sh=f2(si,Aj(1)l即在状态为即在状态为si，输入为，输入为Aj(1)时，输出为时，输出为Ak(2)，而状态转移为，而状态转移为sh。12【例【例21】lS=s1,s2,s3，lA1=A1(1),A2(1),A3(1)，A2=A1(2),A2(2),A3(2),转转移移函函数数由表

13、由表21给出给出f1A1(1)A2(1)A3(1)s1A1(2)A3(2)A2(2)s2A2(2)A1(2)A3(2)s3A3(2)A2(2)A1(2)f2A1(1)A2(1)A3(1)s1s2s1s3s2s3s2s1s3s1s3s213有限状态自动机可用有向图表示，称为转移图有限状态自动机可用有向图表示，称为转移图转移图的顶点对应于自动机的状态转移图的顶点对应于自动机的状态l若若状状态态 si在在输输入入Ai(1)时时转转为为状状态态sj，且且输输出出一一字字符符Aj(2)，则则在在转转移移图图中中，从从状状态态si到到状状态态 sj有有 一一 条条 标标 有有(Ai(1),Aj(2)的的有

14、有向向弧线，如图弧线，如图14在例在例21中，若中，若l输入序列为输入序列为A1(1)A2(1)A1(1)A3(1)A3(1)A1(1)l初始状态为初始状态为s1，l则得到状态序列为：则得到状态序列为：l输出字符序列为：输出字符序列为：s1s2s2s3s2s1s2A1(2)A1(2)A2(2)A1(2)A3(2)A1(2)152.1.3 密钥流产生器密钥流产生器同步流密码的关键是密钥流产生器同步流密码的关键是密钥流产生器(Key Generator)l一般可将其看成一般可将其看成一个参数为一个参数为k的有限状态自动机的有限状态自动机，由一个输出符号，由一个输出符号集集Z、一个状态集、一个状态集

15、、两个函数、两个函数和和以及一个初始状态以及一个初始状态 0 0组成组成l状态转移函数状态转移函数：i i i i+1+1，将当前状态，将当前状态 i i变为一个新状态变为一个新状态 i i+1+1l输出函数输出函数:i iz zi i，当前状态，当前状态 i i变为输出符号集中的一个元素变为输出符号集中的一个元素z zi i。密钥流生成器设计的关键在于密钥流生成器设计的关键在于l找出适当的状态转移函数找出适当的状态转移函数和输出函数和输出函数，使得输出序列，使得输出序列z满足密钥满足密钥流序列流序列z应满足的几个条件，并且要求在设备上是节省的和容易实应满足的几个条件，并且要求在设备上是节省的

16、和容易实现的。为了实现这一目标，必须采用现的。为了实现这一目标，必须采用非线性函数非线性函数 16由于由于具有非线性的具有非线性的的有限状态自动机理论很不完善的有限状态自动机理论很不完善，相，相应的密钥流产生器的分析工作受到极大的限制。应的密钥流产生器的分析工作受到极大的限制。相反地，当相反地，当采用线性的采用线性的和非线性的和非线性的时，将能够进行深时，将能够进行深入的分析并可以得到好的生成器。入的分析并可以得到好的生成器。l为方便讨论，可将这类生成器分成为方便讨论，可将这类生成器分成驱动部分和非线性组合驱动部分和非线性组合部分部分l驱动部分驱动部分控制生成器的状态转移，并为非线性组合部分提

17、供统计控制生成器的状态转移，并为非线性组合部分提供统计性能好的序列；性能好的序列；l非线性组合部分非线性组合部分要利用这些序列组合出满足要求的密钥流序列。要利用这些序列组合出满足要求的密钥流序列。17目前最为流行和实用的密钥流产生器如图所示，其目前最为流行和实用的密钥流产生器如图所示，其驱动部分是一个或驱动部分是一个或多个线性反馈移位寄存器多个线性反馈移位寄存器。l前者称为滤波生成器，或前馈生成器前者称为滤波生成器，或前馈生成器l后者称为非线性组合生成器后者称为非线性组合生成器l还有钟控生成器，缩减生成器，停走生成器等还有钟控生成器，缩减生成器，停走生成器等l在非线性生成器中介绍在非线性生成器

18、中介绍18密钥流序列密钥流序列z应满足的几个条件：应满足的几个条件：一般来说，一般来说，KG(密钥产生器密钥产生器)的输入的输入(种子密钥种子密钥k)是是较短的，其输出为周期序列较短的，其输出为周期序列l对于二元序列，如果种子密钥对于二元序列，如果种子密钥k为为n比特，则其周期最大比特，则其周期最大为为2nl因为一旦密钥产生器的某一时刻的存储状态与前面的某一时刻因为一旦密钥产生器的某一时刻的存储状态与前面的某一时刻的状态相同，则在其它参数不变的情况下，输出开始重复的状态相同，则在其它参数不变的情况下，输出开始重复l这个重复周期太小则不安全这个重复周期太小则不安全l希望一个周期的长度很长，这样在

19、加密有限的明文时只希望一个周期的长度很长，这样在加密有限的明文时只需要一个周期内的某个片断，就像真随机的一样需要一个周期内的某个片断，就像真随机的一样19基于以上考虑，密钥产生器目标是：使得密钥基于以上考虑，密钥产生器目标是：使得密钥k经其扩展经其扩展成的密钥流序列成的密钥流序列z具有如下性质：具有如下性质：种子密钥的长度种子密钥的长度（一般来说就是流密码的密钥长度）（一般来说就是流密码的密钥长度）足够长足够长l比如比如128比特，这样密钥空间将有比特，这样密钥空间将有2128规模，抗穷搜索攻击规模，抗穷搜索攻击极大的周期极大的周期：一般来说不应小于：一般来说不应小于255良好的统计特性良好的

20、统计特性l密钥流序列密钥流序列k具有均匀的具有均匀的n-元分布，即在一个周期环上，某特定形元分布，即在一个周期环上，某特定形式的式的n-长长bit串与其求反，两者出现的频数大抵相当串与其求反，两者出现的频数大抵相当(例如，均匀的例如，均匀的游程分布游程分布)20密钥流序列密钥流序列z不可由一个低级的不可由一个低级的LFSR产生，也不可与一产生，也不可与一个低级个低级LFSR产生的序列只有比率很小的相异项产生的序列只有比率很小的相异项；l如果密钥流序列周期为如果密钥流序列周期为n，而人为改变其，而人为改变其1比特后周期急剧变小，比特后周期急剧变小，例如变为例如变为n/t，则序列的安全性就大为减小

21、。，则序列的安全性就大为减小。抗统计分析抗统计分析l利用统计方法由密钥流提取关于利用统计方法由密钥流提取关于KG结构或结构或k的信息在计算上不可的信息在计算上不可行；行；混乱性混乱性.即即z的每一的每一bit均与均与z的大多数的大多数bit有关；有关；扩散性扩散性.即即z任一任一bit的改变要引起的改变要引起z在全貌上的变化。在全貌上的变化。抗线性分析抗线性分析l其中的其中的LSFR就是线性反馈移位寄存器，就是线性反馈移位寄存器，linear shift feedback register，在下一节介绍，在下一节介绍21布尔函数简介布尔函数简介n元布尔函数元布尔函数f(x1,xn)定义为定义为

22、f：F2nF2l表示方法有三种：逻辑关系式，真值表，多元多项式表示方法有三种：逻辑关系式，真值表，多元多项式多元多项式：如多元多项式：如 f(x1,x2,x3,x4)x1x2x3x4l异或异或 x1 x2 x1x2(在在GF(2)上的上的“”(模模2加加)l逻辑逻辑“与与”x1 x2 x1x2(GF(2)上的上的“乘法乘法”)l逻辑逻辑“或或”x1 x2 x1x2+x1x2 其真值表为：其真值表为：l非非 1x l幂幂 xtxxx=x t0lx0=1;布尔函数的高次项只有如下形式布尔函数的高次项只有如下形式lxi1xi2xikx1x2x1 x200001110111122布尔函数的重量布尔函数

23、的重量W(f)：真值表中函数值列里：真值表中函数值列里”1”的个数的个数lf(x1,x2)x1 x2=x1x2+x1x2的重量的重量W(f)3布尔函数的次数布尔函数的次数lf(x1,xn)a0一个乘积项一个乘积项 的次数定义为的次数定义为r最大次数定义为布尔函数的次数最大次数定义为布尔函数的次数 def(f)def(f)1时，称为仿射函数时，称为仿射函数：f(x1,xn)a0l若仿射函数的常数项若仿射函数的常数项a00，则称为线性函数，则称为线性函数def(f)1时，称为非线性函数时，称为非线性函数232.2 线性反馈移位寄存器线性反馈移位寄存器移位寄存器是序列密码产生密钥流的一个主要组成部分

24、移位寄存器是序列密码产生密钥流的一个主要组成部分lGF(2)上一个上一个n 级反馈移位寄存器由级反馈移位寄存器由n 个二元存储器个二元存储器与与一个反馈函一个反馈函数数f(a1,a2,an)组成，如图所示组成，如图所示l每一存储器称为移位寄存器的一级每一存储器称为移位寄存器的一级移位寄存器的状态移位寄存器的状态l在任一时刻，这些级的内容构成该反馈移位寄存器的在任一时刻，这些级的内容构成该反馈移位寄存器的状态状态l每一状态对应于每一状态对应于GF(2)上的一个上的一个n维向量，共有维向量，共有2n种可能的状态。种可能的状态。l每一时刻的状态可用每一时刻的状态可用n长序列长序列 a1,a2,an或

25、或n维向量维向量(a1,a2,an)表表示，其中示，其中ai是第是第i级存储器的内容。级存储器的内容。24初始状态初始状态 0 0由用户确定由用户确定l属于密钥属于密钥k的一部分的一部分状态转换规则状态转换规则（线性）：（线性）：l当第当第i个移位时钟脉冲到来时，每一级存储器个移位时钟脉冲到来时，每一级存储器ai都将其内都将其内容向下一级容向下一级ai-1传递，并根据寄存器此时的状态传递，并根据寄存器此时的状态a1,a2,an计算计算f(a1,a2,an)，作为下一时刻的，作为下一时刻的an反馈函数反馈函数f(a1,a2,an)是是n元布尔函数，即元布尔函数，即n个变个变元元a1,a2,an可

26、以独立地取可以独立地取0和和1这两个可能的值，这两个可能的值，l函数中的运算有逻辑与、逻辑或、逻辑补等运算，最后函数中的运算有逻辑与、逻辑或、逻辑补等运算，最后的函数值也为的函数值也为0或或1。25例例：下下图图是是一一个个3级级反反馈馈移移位位寄寄存存器器，其其初初始始状状态态为为(a1,a2,a3)=(1,0,1)，输出可由表输出可由表2.2求出求出该该3 3级反馈移位寄存器级反馈移位寄存器的状态和输出如下的状态和输出如下状态（a3,a2,a1)输出1 0 11 1 01 1 10 1 11 0 11 1 0101110即输出序列为即输出序列为101110111011，周期为，周期为426

27、线性反馈移位寄存器线性反馈移位寄存器LFSR l如果移位寄存器的反馈函数如果移位寄存器的反馈函数f(a1,a2,an)是是a1,a2,an的线性函数，则称之为线性反馈移位寄存器的线性函数，则称之为线性反馈移位寄存器LFSR（linear feedback shift register），此时），此时f可写为可写为lf(a1,a2,an)=cna1 cn-1a2 c1anl其中常数其中常数ci=0或或1，可用开关的断开和闭合来实现，可用开关的断开和闭合来实现27输出序列输出序列at满足满足 l an+t=cnat cn-1at1 c1ant-1l其中其中t为非负正整数。为非负正整数。二元情况下二

28、元情况下(GF(2)，ci=0或或1刚好可以用开关的断开和刚好可以用开关的断开和闭合来表示，其中开关断开相当于没有连接线。闭合来表示，其中开关断开相当于没有连接线。lciani1等于等于0或或ani1恰好可用开关的断开和闭合来实现恰好可用开关的断开和闭合来实现线性反馈移位寄存器因其实现简单、速度快、有较为线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点成熟的理论等优点而成为构造密钥流生成器的最重要而成为构造密钥流生成器的最重要的部件之一。的部件之一。28【例2-3】下图是一个】下图是一个5级线性反馈移位寄存器，级线性反馈移位寄存器，其初始状态为（其初始状态为（a1,a2,a3,a

29、4,a5）=(1,0,0,1,1)，可求，可求出输出序列为出输出序列为 1001101001000010101110110001111100110周期为周期为31。29在线性反馈移位寄存器中总是假定在线性反馈移位寄存器中总是假定c1,c2,cn中至中至少有一个不为少有一个不为0，否则，否则f(a1,a2,an)0，在，在n个脉个脉冲后状态必然是冲后状态必然是000，且这个状态必将一直持续，且这个状态必将一直持续下去。下去。l若只有一个系数不为若只有一个系数不为0，设仅有，设仅有cj不为不为0，实际上是一种，实际上是一种延迟装置。延迟装置。l一般对于一般对于n级线性反馈移位寄存器，总是假定级线性

30、反馈移位寄存器，总是假定cn=1。l线性反馈移位寄存器线性反馈移位寄存器输出序列的性质完全由其反馈函数输出序列的性质完全由其反馈函数决定决定30LFSR的周期的周期ln级线性反馈移位寄存器最多有级线性反馈移位寄存器最多有2n个不同的状态。个不同的状态。l若其初始状态为若其初始状态为0，则其状态恒为，则其状态恒为0。l若其初始状态非若其初始状态非0，则其后继状态不会为，则其后继状态不会为0。因此。因此n级线性级线性反馈移位寄存器的状态周期小于等于反馈移位寄存器的状态周期小于等于2n-1。l其输出序列的周期与状态周期相等，也小于等于其输出序列的周期与状态周期相等，也小于等于2n-1。只要选择合适的

31、反馈函数便可使序列的周期达到最只要选择合适的反馈函数便可使序列的周期达到最大值大值2n-1，周期达到最大值的线性序列称为，周期达到最大值的线性序列称为m序列序列l 其状态转移图是一个大圈其状态转移图是一个大圈312.3 线性移位寄存器序列的一元多项式表示线性移位寄存器序列的一元多项式表示设设n级线性移位寄存器的输出序列级线性移位寄存器的输出序列ai满足递推关系式满足递推关系式lan+k=c1ank1 c2ank2 cnak (*)l对任何对任何k 1成立。成立。l这种递推关系可用一个一元高次多项式表示这种递推关系可用一个一元高次多项式表示 p(x)=1+c1x+c2x2+cn-1xn-1+cn

32、xn称这个多项式为称这个多项式为LFSR的特征多项式。的特征多项式。特征多项式按如下方式获得：特征多项式按如下方式获得：l在在(*)式中两边同时加上式中两边同时加上an+k有有l 01an+k c1ank1 c2ank2 cnak 32每一个时钟信号，寄存器中的内容从左向右移动一次，最左边的写入反馈每一个时钟信号，寄存器中的内容从左向右移动一次，最左边的写入反馈信号，最右边的移出。因此一个寄存器代表一次符号迟延，因而引入迟延信号，最右边的移出。因此一个寄存器代表一次符号迟延，因而引入迟延算子算子DlD(ank)ank1表示迟延一位，表示迟延一位，D2(ank)ank2表示迟延两位表示迟延两位(

33、两拍两拍)即即lD2(ank)D(D(ank)D(ank1)=ank2l同理有同理有Dn(ank)ak表示迟延表示迟延n位。位。l引入恒等算子引入恒等算子I=D0，I(ank)=ank于是递推式于是递推式01an+k c1ank1 c2ank2 cnak可表示成可表示成l 0I(ank)+c1D(ank)+c2D2(ank)+cnDn(ank)l即即0(I+c1D+c2D2+cnDn)ankl以以x表示表示D，则有则有p(x)ank=0于是可知于是可知p(x)可以描述可以描述LFSR的全部特征，可以由的全部特征，可以由p(x)来研究来研究LFSR33线性反馈移位寄存器与特征多项式是一一对应的线

34、性反馈移位寄存器与特征多项式是一一对应的l如果知道了线性反馈移位寄存器的结构，可以写出它如果知道了线性反馈移位寄存器的结构，可以写出它的特征多项式的特征多项式l同样可以根据特征多项式画出移位寄存器的结构。同样可以根据特征多项式画出移位寄存器的结构。设设n级线性移位寄存器对应于递推关系级线性移位寄存器对应于递推关系(*)，l由于由于ai GF(2)(i=1,2,n)，所以共有，所以共有2n组初始状态，组初始状态，即有即有2n个递推序列，其中非恒零的有个递推序列，其中非恒零的有2n-1个个l记记2n-1个非零序列的全体为个非零序列的全体为G(p(x)。l一般的一般的cn=1，如果，如果cn0则发生

35、次数退化则发生次数退化34定义定义2-1 给定序列给定序列ai,幂级数幂级数称为该序列的称为该序列的生成函数生成函数。l把把输输出出序序列列的的每每一一项项按按顺顺序序依依次次看看作作级级数数的的系数（系数（xt 表示迟延表示迟延t个节拍）个节拍）定定 理理 2-1设设 p(x)=1+c1x+c2x2+cn-1xn-1+cnxn是是GF(2)上上的的多多项项式式，G(p(x)中中任任一一序序列列ai的的生生成函数成函数A(x)满足：满足：其中其中35证明：证明：由递推等式不难得出由递推等式不难得出lan+1=c1an c2an-1 cna1lan+2=c1an+1 c2an cna2ll两边分

36、别乘以两边分别乘以xn,xn+1,，再求和，再求和l左边左边an+1xn+an+2xn+1+A(x)(a1+a2x+anxn-1)l右边逐列相加整理得右边逐列相加整理得l右边右边=c1xA(x)(a1+a2x+an-1xn-2)l +c2x2A(x)(a1+a2x+an-2xn-3)l +l +cnxnA(x)移项整理得移项整理得 l(1+c1x+c2x2+cn-1xn-1+cnxn)A(x)=(a1+a2x+anxn-1)+c1x(a1+a2x+an-1xn-2)+c2x2(a1+a2x+an-2xn-3)+cn-1xn-1a1l即即p(x)A(x)=(x)36 (x)的次数小于的次数小于n

37、l因此共有因此共有2n1个不同的非个不同的非0表达式表达式l而每一个初态都对应不同的而每一个初态都对应不同的(x)，共有，共有2n1个个初态初态l所以初态和所以初态和(x)是一一对应的是一一对应的l初始状态、初始状态、(x)、G(p(x)三者一一对应三者一一对应37定理定理2-2 p(x)|q(x)的充要条件是的充要条件是G(p(x)G(q(x)l证明：若证明：若p(x)|q(x)，可设，可设q(x)p(x)r(x)，因此，因此 l l而而(x)次数小于等于次数小于等于n1，r(x)次数为次数为nqn，所以，所以(x)r(x)次数小于等于次数小于等于nqn+(n1)=nq1。l根据定理根据定理

38、2-1的推导过程，可知的推导过程，可知(x)r(x)唯一对应一个唯一对应一个q(x)生成的序列，而显然有生成的序列，而显然有lq(x)A(x)p(x)r(x)A(x)(x)r(x)，即该序列为，即该序列为A(x)。l所以若所以若ai G(p(x)，则也有，则也有ai G(q(x)，即，即G(p(x)G(q(x)38l反之，若反之，若G(p(x)G(q(x)，则对于次数小于，则对于次数小于n的多的多项式项式(x)，存在序列，存在序列ai G(p(x)，以，以 为生成函数为生成函数 根据定理根据定理2-1的推导过程，当的推导过程，当(x)1时，当然也存在时，当然也存在序列序列ai G(p(x)以以

39、 为生成函数为生成函数 由于由于G(p(x)G(q(x)，序列，序列ai G(q(x)，所以存在，所以存在函数函数r(x)，使得，使得ai的生成函数也等于的生成函数也等于 ，从而从而 ，即，即q(x)p(x)r(x)，所以，所以p(x)|q(x)。证毕证毕39l定理定理2-2 说明可用说明可用n级级LFSR产生的序列，也可产生的序列，也可用级数更多的用级数更多的LFSR来产生来产生l反之一个反之一个LFSR序列的特征多项式可能有多个，序列的特征多项式可能有多个，需要的移位寄存器个数也不同需要的移位寄存器个数也不同l2.6节将介绍线性复杂度概念，极小多项式的次数节将介绍线性复杂度概念，极小多项式

40、的次数定义定义2-2 设设p(x)是是GF(2)上的多项式，使上的多项式，使p(x)|(xp-1)的最小的最小p称为称为p(x)的周期或阶的周期或阶40定理定理2-3 若序列若序列ai的特征多项式的特征多项式p(x)定义在定义在GF(2)上，上，p是是p(x)的周期，则的周期，则ai的周期的周期r|p。l证明：证明：(首先证明首先证明ai至少是以至少是以p为周期重复的为周期重复的)l由由p(x)周期的定义得周期的定义得p(x)|(xp-1)，因此存在，因此存在q(x)，使得，使得 xp-1=p(x)q(x)，l又由又由p(x)A(x)(x)可得可得p(x)q(x)A(x)q(x)(x)l所以所

41、以(xp-1)A(x)=q(x)(x)。由于。由于q(x)的次数为的次数为p-n，(x)的次数不超过的次数不超过n-1，所以，所以(xp-1)A(x)的次数不超过的次数不超过(p-n)+(n-1)=p-1。l对于任意的特征多项式为对于任意的特征多项式为p(x)的的A(x)，xpA(x)-A(x)的次数低于的次数低于p1，也就是也就是A(x)移位移位p次后对应位相等，从而相消去次后对应位相等，从而相消去)l 这就证明了对于任意正整数这就证明了对于任意正整数i都有都有ai+p=ail设设p=kr+t,0 tr，则，则ai+p=ai+kr+t=ai+t=ai，所以，所以t=0，即，即r|p。（证毕）

42、。（证毕）41n级级LFSR输出序列的周期输出序列的周期r不依赖于初始条件，而依赖于不依赖于初始条件，而依赖于特征多项式特征多项式p(x)。l我们感兴趣的是我们感兴趣的是LFSR遍历遍历2n-1个非零状态，这时序列的周期达到个非零状态，这时序列的周期达到最大最大2n-1，这种序列就是，这种序列就是m序列序列。显然对于特征多项式一样，而仅。显然对于特征多项式一样，而仅初始条件不同的两个初始条件不同的两个m输出序列，一个记为输出序列，一个记为ai(1)，另一个记为，另一个记为ai(2)，其中一个必是另一个的移位，即存在一个常数，其中一个必是另一个的移位，即存在一个常数k，使得，使得lai(1)=a

43、ik(2),i=1,2,下面讨论特征多项式满足什么条件时，下面讨论特征多项式满足什么条件时，LFSR的输出序列的输出序列为为m序列。序列。定义定义2-3 仅能被非仅能被非0常数或自身的常数倍除尽，但不能被其常数或自身的常数倍除尽，但不能被其它的多项式除尽的多项式称为既约多项式或不可约多项式它的多项式除尽的多项式称为既约多项式或不可约多项式l不可约多项式的讨论与域有关，不同的域，多项式是否既约可能不可约多项式的讨论与域有关，不同的域，多项式是否既约可能是不同的是不同的42定理定理2-4 设设p(x)是是n次不可约多项式，周期为次不可约多项式，周期为m，序列，序列ai G(p(x)，则，则ai的周

44、期为的周期为m。l证明：设证明：设ai的周期为的周期为r，由定理，由定理2.3 有有r|m，所以，所以r m。l设设A(x)为为ai的生成函数，的生成函数，A(x)=(x)/p(x)，即，即p(x)A(x)=(x)0，(x)的次数不超过的次数不超过n-1。而。而lA(x)=a1+a2x+arxr-1+xr(a1+a2x+arxr-1)l +(xr)2(a1+a2x+arxr-1)+l =(a1+a2x+arxr-1)/(1-xr)l =(a1+a2x+arxr-1)/(xr-1)l于是于是A(x)=(a1+a2x+arxr-1)/(xr-1)(x)/p(x)，l即即 p(x)(a1+a2x+a

45、rxr-1)=(x)(xr-1)l因因p(x)是不可约的，所以是不可约的，所以gcd(p(x),(x)=1，p(x)|(xr-1)，因此，因此m r。l综上综上r=m。（证毕）。（证毕）43定理定理2.5 n级级LFSR产生的序列有最大周期产生的序列有最大周期2n-1的必的必要条件是其特征多项式为不可约的。要条件是其特征多项式为不可约的。l证明：设证明：设n级级LFSR产生的序列周期达到最大产生的序列周期达到最大2n-1，除，除0序序列外，每一序列的周期由特征多项式惟一决定，而与初始列外，每一序列的周期由特征多项式惟一决定，而与初始状态无关。状态无关。l(只要有一条序列为只要有一条序列为m序列

46、，则所有非序列，则所有非0序列都是序列都是m序列序列)l设特征多项式为设特征多项式为p(x)，若，若p(x)可约，可设为可约，可设为p(x)=g(x)h(x)，其中其中g(x)不可约，且次数不可约，且次数k2，当，当1 i n-2时，时，n长长m序列的一个周期内，长为序列的一个周期内，长为i的的0游程数游程数目等于序列中如下形式的状态数目：目等于序列中如下形式的状态数目：10001*，其中，其中n-i-2个个*可可任取任取0或或1。由遍历性，这种状态共有。由遍历性，这种状态共有2n-i-2个。同理可得长为个。同理可得长为i的的1游游程数目也等于程数目也等于2n-i-2，所以长为，所以长为i的游

47、程总数为的游程总数为2n-i-1。56l由于寄存器中不会出现全由于寄存器中不会出现全0状态，所以状态，所以不会出现不会出现0的的n游程游程，但由状态遍历性但由状态遍历性必有一个必有一个1的的n游程游程，而且，而且1的游程不会更大，的游程不会更大，因为若出现因为若出现1的的n+1游程，就必然有两个相邻的全游程，就必然有两个相邻的全1状态，但状态，但这是不可能的，因为如果这样移位寄存器将永远是全这是不可能的，因为如果这样移位寄存器将永远是全1状态状态l这就证明了这就证明了1的的n游程必然出现在如下的串中：游程必然出现在如下的串中：”01110”其中其中1共共有有n个，首尾是个，首尾是0。l当这当这

48、n+2位通过移位寄存器时，便依次产生以下状态：位通过移位寄存器时，便依次产生以下状态：l 0111(n-1个个1)111(n个个1)1110(n-1个个1)l而而0111(n-1个个1)和和1110(n-1个个1)这两个状态只可能出现这两个状态只可能出现一次，而它们包含在了全一次，而它们包含在了全1状态中，所以不会有状态中，所以不会有1的的n-1游程游程l如果存在如果存在1的的n-1游程，则必有形式游程，则必有形式0110，它与，它与0111(n个个1)矛盾矛盾57l0的的n-1游程有一个游程有一个1001(n-1个个0)，不可能有两个，不可能有两个0的的n-1游程，否则由状态重复可知周期小于

49、游程，否则由状态重复可知周期小于2n-1l于是在一个周期内，总游程数为于是在一个周期内，总游程数为l11 2n-1l 采用构造法采用构造法lai是周期为是周期为2n-1的的m序列，对于任一正整数序列，对于任一正整数(02n-1)，ai+ai+在一个周期内为在一个周期内为0的位的数的位的数目正好是序列目正好是序列ai和和ai+对应位相同的位的数目对应位相同的位的数目lR()58l设序列设序列ai满足递推关系满足递推关系lah+n=c1ah+n1 c2ah+n2 cnahl故故ah+n+=c1ah+n+1 c2ah+n+2 cnah+l即即ah+n ah+n+=c1(ah+n1 ah+n+1)c2

50、(ah+n2 ah+n+2)cn(ah ah+)l令令bj=aj aj+，则由递推序列，则由递推序列ai可推得递推序列可推得递推序列biai+ai+lbi满足满足bh+n=c1bh+n1 c2bh+n2cnbhlbi也是也是m序列。为了计算序列。为了计算R()，只要用只要用bi在一个周期在一个周期中中0的个数减去的个数减去1的个数，再除以的个数，再除以2n-1，即，即l R()=（证毕）（证毕）592.5 m序列密码的破译序列密码的破译有限域上的有限域上的二元加法序列密码二元加法序列密码是目前最为常用的是目前最为常用的序列密码体制序列密码体制设滚动密钥生成器是线性反馈移位寄存器，产生设滚动密钥