密码学02－流码

本科生必修课：现代密码学本科生必修课：现代密码学第二章第二章 流密码流密码主讲教师主讲教师：董庆宽：董庆宽研究方向研究方向：密码学与信息安全：密码学与信息安全Email Email ：个人主页：个人主页：http:/ 2.1 流密码的基本概念流密码的基本概念布尔函数简介布尔函数简介2.2 2.2 线性反馈移位寄存器线性反馈移位寄存器2.3 2.3 线性移位寄存器的一元多项式表示线性移位寄存器的一元多项式表示 2.4 2.4 mm序列的伪随机性序列的伪随机性2.5 2.5 mm序列密码的破译序列密码的破译2.6 2.6 非线性序列非线性序列本章提要本章提要3/90流密码概况流密码概况流密码流密码(stream cipher)是一种重要的密码体制是一种重要的密码体制l明文消息按字符或比特逐位加密明文消息按字符或比特逐位加密l流密码也称为序列密码流密码也称为序列密码(Sequence Cipher)流密码在手工和机械密码时代是主流技术流密码在手工和机械密码时代是主流技术流密码在流密码在50年代得到飞跃式发展年代得到飞跃式发展l密钥流可以用移位寄存器电路来产生，也促进了线性和密钥流可以用移位寄存器电路来产生，也促进了线性和非线性移位寄存器发展非线性移位寄存器发展主要用于专用和机密机构：军方，银行等主要用于专用和机密机构：军方，银行等l由于互联网是分组传输的，流密码的使用较少由于互联网是分组传输的，流密码的使用较少4/90流密码具有有效的数学分析工具流密码具有有效的数学分析工具l代数代数(如布尔代数如布尔代数)、有限域理论和谱分析理论等等、有限域理论和谱分析理论等等l流密码在现代密码学阶段的主要成果来自于密码分析流密码在现代密码学阶段的主要成果来自于密码分析很多密码学家因流密码研究而成名很多密码学家因流密码研究而成名l肖国镇，肖国镇，Massey，Berlikamp等。等。l在在IEEE Transaction on Information Theory上能够发表的密码上能够发表的密码成果多数都是来自于流密码的相关研究成果多数都是来自于流密码的相关研究流密码基于硬件实现优势更明显，目前也有些算法是针对流密码基于硬件实现优势更明显，目前也有些算法是针对软件设计的软件设计的l如如Ecrypt计划中的算法，计划中的算法，RC4等等参考资料参考资料：伪随机序列及其应用伪随机序列及其应用，流密码学及其应流密码学及其应用用，肖国镇著，肖国镇著5/902.1 流密码的基本概念流密码的基本概念流密码的基本思想流密码的基本思想l利用密钥利用密钥k产生一个密钥流产生一个密钥流z=z0z1z2，并使用如下规则，并使用如下规则对明文串对明文串x=x0 x1x2加密：加密： y=y0y1y2Ez0(x0)Ez1(x1) Ez2(x2)，密钥流密钥流l由密钥流发生器由密钥流发生器 f 产生：产生：zif(k,i)li是加密器中的记忆元件在时刻是加密器中的记忆元件在时刻 i 的状态的状态l f 是由是由k, i 产生的函数产生的函数6/90 流密码流密码 分组密码分组密码内部记忆元件由一组移位寄存器构成内部记忆元件由一组移位寄存器构成 7/90流密码与分组密码的区别：在于有无记忆性流密码与分组密码的区别：在于有无记忆性l流密码的滚动密钥由函数流密码的滚动密钥由函数f、密钥、密钥k和指定的初态和指定的初态0完全确定完全确定l此后由于输入加密器的明文可能影响加密器中的内部记此后由于输入加密器的明文可能影响加密器中的内部记忆元件的存储状态，因而忆元件的存储状态，因而i (i0)可能依赖于可能依赖于k，0，x0，x1，xi1，前前 i 个个明文和密钥及初态明文和密钥及初态l分组密码中，一组一组的加密，一般等长分组密码中，一组一组的加密，一般等长l在分组内明文和密钥充分混淆，分组间一般互不影响，在分组内明文和密钥充分混淆，分组间一般互不影响，与分组连接模式有关与分组连接模式有关8/902.1.1同步流密码同步流密码流密码可按记忆元件存储状态分类流密码可按记忆元件存储状态分类l按照加密器中记忆元件的存储状态按照加密器中记忆元件的存储状态i 是否依赖于输入的是否依赖于输入的明文字符流明文字符流，流密码可进一步分成，流密码可进一步分成同步同步和和自同步流密码自同步流密码两种两种li 独立于明文字符流的叫做同步流密码，否则叫做自同独立于明文字符流的叫做同步流密码，否则叫做自同步流密码步流密码l由于由于自同步流密码的密钥流的产生与明文有关自同步流密码的密钥流的产生与明文有关，所以理论上难，所以理论上难于分析。于分析。l好的密码算法应该好的密码算法应该在理论上或基于实践检验能够证明其是安全在理论上或基于实践检验能够证明其是安全的或至少是没有明显漏洞的的或至少是没有明显漏洞的。l如果算法难于分析，则无法保证其安全性，也就无法放心使用，如果算法难于分析，则无法保证其安全性，也就无法放心使用，因此自同步流密码研究很少，很少采用。因此自同步流密码研究很少，很少采用。9/90目前大多数研究成果都是关于同步流密码的目前大多数研究成果都是关于同步流密码的l由于由于zif(k,i)与明文无关，此刻的密文字符与明文无关，此刻的密文字符yi=Ezi(xi)也也不依赖于此前的明文字符，这样不依赖于此前的明文字符，这样可将同步流密码的加密可将同步流密码的加密器分成器分成密钥流产生器密钥流产生器和和加密变换器加密变换器两个部分。两个部分。l设解密变换为设解密变换为xi=Dzi(yi)。同步流密码体制模型如下图。同步流密码体制模型如下图10/90加密变换加密变换Ezi可有多种选择，保证变换可逆性即可可有多种选择，保证变换可逆性即可l比如明文流和密钥流对应位异或比如明文流和密钥流对应位异或l实际数字保密通信系统一般都是二元的实际数字保密通信系统一般都是二元的0,1,在有限域在有限域GF(2)上讨论上讨论二元加法流密码二元加法流密码是目前最常用的流密码体制是目前最常用的流密码体制l加密变换可表示为加密变换可表示为yizi xi，加法流密码体制模型加法流密码体制模型11/90一次一密密码一次一密密码(One Time Padding 一次一密乱码本一次一密乱码本)是加法是加法流密码的原型流密码的原型l其中密钥的长度至少和明文的长度一样长，是无条件安全的，但其中密钥的长度至少和明文的长度一样长，是无条件安全的，但实用性较差，因而不能广泛应用。实用性较差，因而不能广泛应用。l如果加法流密码中，如果加法流密码中，ziki，即直接将密钥，即直接将密钥k(k至少和明文一样长至少和明文一样长)用作滚动的密钥流，则加法流密码就是一次一密密码。用作滚动的密钥流，则加法流密码就是一次一密密码。流密码体制中如果密钥有限，则安全性一般低于一次一密流密码体制中如果密钥有限，则安全性一般低于一次一密l从信息论意义上讲，对从信息论意义上讲，对k比特长的串进行任何固定变换，其信息量比特长的串进行任何固定变换，其信息量至多为至多为k比特，即密钥流再长，其安全性最大也就是密钥长度，而比特，即密钥流再长，其安全性最大也就是密钥长度，而一次一密的密钥长度至少和明文一样。一次一密的密钥长度至少和明文一样。同步流密码算法的设计主要是密钥流产生器的设计同步流密码算法的设计主要是密钥流产生器的设计l密钥产生器目标是：使得密钥密钥产生器目标是：使得密钥k经其扩展成的密钥流序列经其扩展成的密钥流序列z具有如具有如下性质：下性质：l极大的周期，良好的统计特性，抗差分分析，抗线性分析等极大的周期，良好的统计特性，抗差分分析，抗线性分析等12/902.1.2 有限状态自动机有限状态自动机流密码中任意时刻流密码中任意时刻密钥流密钥流和和密文密文的输出与状态密切的输出与状态密切相关。可以用有限状态自动机这一数学模型来表述相关。可以用有限状态自动机这一数学模型来表述有限状态自动机是具有离散输入和输出有限状态自动机是具有离散输入和输出（输入集和（输入集和输出集均有限）输出集均有限）的一种数学模型的一种数学模型，由，由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。13/90【例【例21】lS=s1,s2,s3，lA1=A1(1),A2(1),A3(1)，A2=A1(2),A2(2),A3(2),转移函数由转移函数由表表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)s1s2s1s3s2s3s2s1s3s1s3s214/90有限状态自动机可用有向图表示，称为转移图有限状态自动机可用有向图表示，称为转移图转移图的顶点对应于自动机的状态转移图的顶点对应于自动机的状态l若状态若状态 si在输入在输入Ai(1)时转为状态时转为状态sj，且输出一字符且输出一字符Aj(2)，则在转移图中，则在转移图中，从状态从状态si到状态到状态sj有一条标有有一条标有(Ai(1), Aj(2)的有向弧线，的有向弧线，如图如图15/90在例在例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)16/902.1.3 密钥流产生器密钥流产生器同步流密码的关键是密钥流产生器同步流密码的关键是密钥流产生器(Key Generator)l一般可将其看成一般可将其看成一个参数为一个参数为k的有限状态自动机的有限状态自动机，由一个输出符号，由一个输出符号集集Z、一个状态集、一个状态集、两个函数、两个函数和和以及一个初始状态以及一个初始状态 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应满足的几个条件，并且要求在设备上是节省的和容易实应满足的几个条件，并且要求在设备上是节省的和容易实现的。为了实现这一目标，必须采用现的。为了实现这一目标，必须采用非线性函数非线性函数 17/90由于由于具有非线性的具有非线性的的有限状态自动机理论很不完善的有限状态自动机理论很不完善，相，相应的密钥流产生器的分析工作受到极大的限制。应的密钥流产生器的分析工作受到极大的限制。相反地，当相反地，当采用线性的采用线性的和非线性的和非线性的时，将能够进行深时，将能够进行深入的分析并可以得到好的生成器。入的分析并可以得到好的生成器。l为方便讨论，可将这类生成器分成为方便讨论，可将这类生成器分成驱动部分和非线性组合驱动部分和非线性组合部分部分l驱动部分驱动部分控制生成器的状态转移，并为非线性组合部分提供统计控制生成器的状态转移，并为非线性组合部分提供统计性能好的序列；性能好的序列；l非线性组合部分非线性组合部分要利用这些序列组合出满足要求的密钥流序列。要利用这些序列组合出满足要求的密钥流序列。18/90目前最为流行和实用的密钥流产生器如图所示，其目前最为流行和实用的密钥流产生器如图所示，其驱动部分是一个或驱动部分是一个或多个线性反馈移位寄存器多个线性反馈移位寄存器。l前者称为滤波生成器，或前馈生成器前者称为滤波生成器，或前馈生成器l后者称为非线性组合生成器后者称为非线性组合生成器l还有钟控生成器，缩减生成器，停走生成器等还有钟控生成器，缩减生成器，停走生成器等l在非线性生成器中介绍在非线性生成器中介绍19/90密钥流序列密钥流序列z应满足的几个条件：应满足的几个条件：一般来说，一般来说，KG(密钥产生器密钥产生器)的输入的输入(种子密钥种子密钥k)是是较短的，其输出为周期序列较短的，其输出为周期序列l对于二元序列，如果种子密钥对于二元序列，如果种子密钥k为为n比特，则其周期最大比特，则其周期最大为为2nl因为一旦密钥产生器的某一时刻的存储状态与前面的某一时刻因为一旦密钥产生器的某一时刻的存储状态与前面的某一时刻的状态相同，则在其它参数不变的情况下，输出开始重复的状态相同，则在其它参数不变的情况下，输出开始重复l这个重复周期太小则不安全这个重复周期太小则不安全l希望一个周期的长度很长，这样在加密有限的明文时只希望一个周期的长度很长，这样在加密有限的明文时只需要一个周期内的某个片断，就像真随机的一样需要一个周期内的某个片断，就像真随机的一样20/90基于以上考虑，密钥产生器目标是：使得密钥基于以上考虑，密钥产生器目标是：使得密钥k经其扩展经其扩展成的密钥流序列成的密钥流序列z具有如下性质：具有如下性质：种子密钥的长度种子密钥的长度（一般来说就是流密码的密钥长度）（一般来说就是流密码的密钥长度）足够长足够长l比如比如128比特，这样密钥空间将有比特，这样密钥空间将有2128规模，抗穷搜索攻击规模，抗穷搜索攻击极大的周期极大的周期：一般来说不应小于：一般来说不应小于255良好的统计特性良好的统计特性l密钥流序列密钥流序列k具有均匀的具有均匀的n-元分布，即在一个周期环上，某特定形元分布，即在一个周期环上，某特定形式的式的n-长长bit串与其求反，两者出现的频数大抵相当串与其求反，两者出现的频数大抵相当(例如，均匀的例如，均匀的游程分布游程分布) 21/90密钥流序列密钥流序列z不可由一个低级的不可由一个低级的LFSR产生，也不可与一产生，也不可与一个低级个低级LFSR产生的序列只有比率很小的相异项产生的序列只有比率很小的相异项；l如果密钥流序列周期为如果密钥流序列周期为n，而人为改变其，而人为改变其1比特后周期急剧变小，比特后周期急剧变小，例如变为例如变为n/t，则序列的安全性就大为减小。，则序列的安全性就大为减小。抗统计分析抗统计分析l利用统计方法由密钥流提取关于利用统计方法由密钥流提取关于KG结构或结构或k的信息在计算上不可的信息在计算上不可行；行；混乱性混乱性. 即即z的每一的每一bit均与均与z的大多数的大多数bit有关；有关；扩散性扩散性. 即即z任一任一bit的改变要引起的改变要引起z在全貌上的变化。在全貌上的变化。抗线性分析抗线性分析l其中的其中的LSFR就是线性反馈移位寄存器，就是线性反馈移位寄存器，linear shift feedback register，在下一节介绍，在下一节介绍22/90布尔函数简介布尔函数简介n元布尔函数元布尔函数f(x1,xn)定义为定义为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;布尔函数的高次项只有如下形式布尔函数的高次项只有如下形式lxi1xi2xikxx1x2x1 x200001110111123/90布尔函数的重量布尔函数的重量W(f)：真值表中函数值列里：真值表中函数值列里”1”的个数的个数lf(x1,x2)x1 x2 = x1x2+x1x2的重量的重量W(f)3布尔函数的次数布尔函数的次数lf(x1,xn)a0nrniiiiiiiiirrrxxxa1.1.212121.riiixxx.21一个乘积项一个乘积项 的次数定义为的次数定义为r最大次数定义为布尔函数的次数最大次数定义为布尔函数的次数 def(f)def(f)1时，称为仿射函数时，称为仿射函数 ：f(x1,xn)a0l若仿射函数的常数项若仿射函数的常数项a00，则称为线性函数，则称为线性函数def(f)1时，称为非线性函数时，称为非线性函数riiixxx.2124/902.2 线性反馈移位寄存器线性反馈移位寄存器移位寄存器是序列密码产生密钥流的一个主要组成部分移位寄存器是序列密码产生密钥流的一个主要组成部分lGF(2)上一个上一个n 级反馈移位寄存器由级反馈移位寄存器由n 个二元存储器个二元存储器与与一个反馈函一个反馈函数数f(a1,a2,an)组成，如图所示组成，如图所示l每一存储器称为移位寄存器的一级每一存储器称为移位寄存器的一级移位寄存器的状态移位寄存器的状态l在任一时刻，这些级的内容构成该反馈移位寄存器的在任一时刻，这些级的内容构成该反馈移位寄存器的状态状态l每一状态对应于每一状态对应于GF(2)上的一个上的一个n维向量，共有维向量，共有2n种可能的状态。种可能的状态。l每一时刻的状态可用每一时刻的状态可用n长序列长序列 a1,a2,an或或n维向量维向量 (a1,a2,an)表示，表示，其中其中ai是第是第i级存储器的内容。级存储器的内容。25/90初始状态初始状态 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可以独立地取可以独立地取0和和1这两个可能的值，这两个可能的值，l函数中的运算有逻辑与、逻辑或、逻辑补等运算，最后函数中的运算有逻辑与、逻辑或、逻辑补等运算，最后的函数值也为的函数值也为0或或1。26/90例：下图是一个例：下图是一个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，周期为，周期为427/90线性反馈移位寄存器线性反馈移位寄存器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，可用开关的断开和闭合来实现，可用开关的断开和闭合来实现28/90输出序列输出序列at满足满足 l an+t= cnat cn-1at1 c1ant-1l其中其中t为非负正整数。为非负正整数。二元情况下二元情况下(GF(2)，ci=0或或1刚好可以用开关的断开和刚好可以用开关的断开和闭合来表示，其中开关断开相当于没有连接线。闭合来表示，其中开关断开相当于没有连接线。lciani1等于等于0或或ani1恰好可用开关的断开和闭合来实现恰好可用开关的断开和闭合来实现线性反馈移位寄存器因其实现简单、速度快、有较为线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点成熟的理论等优点而成为构造密钥流生成器的最重要而成为构造密钥流生成器的最重要的部件之一。的部件之一。29/90【例2-3】下图是一个】下图是一个5级线性反馈移位寄存器，级线性反馈移位寄存器，其初始状态为（其初始状态为（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求，可求出输出序列为出输出序列为 1001101001000010101110110001111100110周期为周期为31。30/90在线性反馈移位寄存器中总是假定在线性反馈移位寄存器中总是假定c1,c2,cn中至中至少有一个不为少有一个不为0，否则，否则f(a1,a2,an)0，在，在n个脉冲个脉冲后状态必然是后状态必然是000，且这个状态必将一直持续下，且这个状态必将一直持续下去。去。l若只有一个系数不为若只有一个系数不为0，设仅有，设仅有cj不为不为0，实际上是一种，实际上是一种延迟装置。延迟装置。l一般对于一般对于n级线性反馈移位寄存器，总是假定级线性反馈移位寄存器，总是假定cn=1。l线性反馈移位寄存器线性反馈移位寄存器输出序列的性质完全由其反馈函数输出序列的性质完全由其反馈函数决定决定31/90LFSR的周期的周期ln级线性反馈移位寄存器最多有级线性反馈移位寄存器最多有2n个不同的状态。个不同的状态。l若其初始状态为若其初始状态为0，则其状态恒为，则其状态恒为0。l若其初始状态非若其初始状态非0，则其后继状态不会为，则其后继状态不会为0。因此。因此n级线性级线性反馈移位寄存器的状态周期小于等于反馈移位寄存器的状态周期小于等于2n-1。l其输出序列的周期与状态周期相等，也小于等于其输出序列的周期与状态周期相等，也小于等于2n-1。只要选择合适的反馈函数便可使序列的周期达到最只要选择合适的反馈函数便可使序列的周期达到最大值大值2n-1，周期达到最大值的线性序列称为，周期达到最大值的线性序列称为m序列序列l 其状态转移图是一个大圈其状态转移图是一个大圈32/902.3 线性移位寄存器序列的一元多项式表示线性移位寄存器序列的一元多项式表示设设n级线性移位寄存器的输出序列级线性移位寄存器的输出序列ai满足递推关系式满足递推关系式lan+k= c1ank1 c2ank2 cnak (*)l对任何对任何k 1成立。成立。l这种递推关系可用一个一元高次多项式表示这种递推关系可用一个一元高次多项式表示 p(x)=1+c1x+c2x2+cn-1xn-1+cnxn称这个多项式为称这个多项式为LFSR的特征多项式。的特征多项式。特征多项式按如下方式获得：特征多项式按如下方式获得：l在在(*)式中两边同时加上式中两边同时加上an+k有有l 01an+k c1ank1 c2ank2 cnak 33/90每一个时钟信号，寄存器中的内容从左向右移动一次，最左边的写入反馈每一个时钟信号，寄存器中的内容从左向右移动一次，最左边的写入反馈信号，最右边的移出。因此一个寄存器代表一次符号迟延，因而引入迟延信号，最右边的移出。因此一个寄存器代表一次符号迟延，因而引入迟延算子算子DlD(ank)ank1表示迟延一位，表示迟延一位，D2(ank)ank2表示迟延两位表示迟延两位(两拍两拍)即即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)来研究来研究LFSR34/90线性反馈移位寄存器与特征多项式是一一对应的线性反馈移位寄存器与特征多项式是一一对应的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/90定义定义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)满足：满足： 其中其中11)(iiixaxA)()()(xpxxAijjjniininxaxcx111)()(36/90证明：证明： 由递推等式不难得出由递推等式不难得出lan+1=c1an c2an-1 cna1lan+2=c1an+1 c2an cna2ll两边分别乘以两边分别乘以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)ijjjniininxaxc111)(移项整理得移项整理得 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)37/90 (x)的次数小于的次数小于nl因此共有因此共有2n1个不同的非个不同的非0表达式表达式l而每一个初态都对应不同的而每一个初态都对应不同的 (x)，共有，共有2n1个个初态初态l所以初态和所以初态和 (x)是一一对应的是一一对应的l初始状态、初始状态、 (x)、G(p(x)三者一一对应三者一一对应38/90定理定理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根据定理根据定理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)()()(xpxxA)()()()(xrxpxrx)()()(xqxrx39/90l反之，若反之，若G(p(x) G(q(x)，则对于次数小于，则对于次数小于n的多的多项式项式 (x)，存在序列，存在序列ai G(p(x)，以，以 为生成函数为生成函数 根据定理根据定理2-1的推导过程，当的推导过程，当 (x)1时，当然也存时，当然也存在序列在序列ai G(p(x)以以 为生成函数为生成函数 由于由于G(p(x) G(q(x)，序列，序列ai G(q(x)，所以存在，所以存在函数函数r(x)，使得，使得ai的生成函数也等于的生成函数也等于 ， 从而从而 ，即，即q(x)p(x)r(x)，所以，所以p(x)|q(x)。 证毕证毕)(1)(xpxA)()()(xpxxA)(1)(xpxA)()(xqxr)()(xqxr40/90l定理定理2-2 说明可用说明可用n级级LFSR产生的序列，也可产生的序列，也可用级数更多的用级数更多的LFSR来产生来产生l反之一个反之一个LFSR序列的特征多项式可能有多个，序列的特征多项式可能有多个，需要的移位寄存器个数也不同需要的移位寄存器个数也不同l2.6节将介绍线性复杂度概念，极小多项式的次数节将介绍线性复杂度概念，极小多项式的次数定义定义2-2 设设p(x)是是GF(2)上的多项式，使上的多项式，使p(x)|(xp-1)的最小的最小p称为称为p(x)的周期或阶的周期或阶41/90定理定理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所以所以(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/90n级级LFSR输出序列的周期输出序列的周期r不依赖于初始条件，而依赖于不依赖于初始条件，而依赖于特征多项式特征多项式p(x)。l我们感兴趣的是我们感兴趣的是LFSR遍历遍历2n-1个非零状态，这时序列的周期达到个非零状态，这时序列的周期达到最大最大2n-1，这种序列就是，这种序列就是m序列序列。显然对于特征多项式一样，而仅。显然对于特征多项式一样，而仅初始条件不同的两个初始条件不同的两个m输出序列，一个记为输出序列，一个记为ai(1)，另一个记为，另一个记为ai(2)，其中一个必是另一个的移位，即存在一个常数，其中一个必是另一个的移位，即存在一个常数k，使得，使得lai(1)=aik(2),i=1,2,下面讨论特征多项式满足什么条件时，下面讨论特征多项式满足什么条件时，LFSR的输出序列的输出序列为为m序列。序列。定义定义2-3 仅能被非仅能被非0常数或自身的常数倍除尽，但不能被其常数或自身的常数倍除尽，但不能被其它的多项式除尽的多项式称为既约多项式或不可约多项式它的多项式除尽的多项式称为既约多项式或不可约多项式l不可约多项式的讨论与域有关，不同的域，多项式是否既约可能不可约多项式的讨论与域有关，不同的域，多项式是否既约可能是不同的是不同的43/90定理定理2-4 设设p(x)是是n次不可约多项式，周期为次不可约多项式，周期为m，序列，序列ai G(p(x)，则，则ai的周期为的周期为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+arxr-1)= (x)(xr-1)l因因p(x)是不可约的，所以是不可约的，所以gcd(p(x), (x) =1，p(x)|(xr-1)，因此，因此m r。l综上综上r=m。（证毕）。（证毕）11iiixa44/90定理定理2.5 n级级LFSR产生的序列有最大周期产生的序列有最大周期2n-1的必的必要条件是其特征多项式为不可约的。要条件是其特征多项式为不可约的。l证明：设证明：设n级级LFSR产生的序列周期达到最大产生的序列周期达到最大2n-1，除，除0序序列外，每一序列的周期由特征多项式惟一决定，而与初始列外，每一序列的周期由特征多项式惟一决定，而与初始状态无关。状态无关。l(只要有一条序列为只要有一条序列为m序列，则所有非序列，则所有非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的游程总数为的游程总数为2n-i-1。57/90l由于寄存器中不会出现全由于寄存器中不会出现全0状态，所以状态，所以不会出现不会出现0的的n游程游程，但由状态遍历性但由状态遍历性必有一个必有一个1的的n游程游程，而且，而且1的游程不会更大，的游程不会更大，因为若出现因为若出现1的的n+1游程，就必然有两个相邻的全游程，就必然有两个相邻的全1状态，但状态，但这是不可能的，因为如果这样移位寄存器将永远是全这是不可能的，因为如果这样移位寄存器将永远是全1状态状态l这就证明了这就证明了1的的n游程必然出现在如下的串中：游程必然出现在如下的串中：”01110”其中其中1共有共有n个，首尾是个，首尾是0。l当这当这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)矛盾矛盾58/90l0的的n-1游程有一个游程有一个1001(n-1个个0)，不可能有两个，不可能有两个0的的n-1游程，否则由状态重复可知周期小于游程，否则由状态重复可知周期小于2n-1l于是在一个周期内，总游程数为于是在一个周期内，总游程数为l11 2n-1l 采用构造法采用构造法lai是周期为是周期为2n-1的的m序列，对于任一正整数序列，对于任一正整数(02n-1)，ai+ai+在一个周期内为在一个周期内为0的位的的位的数目正好是序列数目正好是序列ai和和ai+对应位相同的位的数对应位相同的位的数目目lR() 2112niinTkaakkT1) 1() 1(1TkaakkT1) 1(159/90l设序列设序列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(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()= = （证毕）（证毕）1221211nnn121n60/902.5 m序列密码的破译序列密码的破译有限域上的有限域上的二元加法序列密码二元加法序列密码是目前最为常用的是目前最为常用的序列密码体制序列密码体制设滚动密钥生成器是线性反馈移位寄存器，产生设滚动密钥生成器是线性反馈移位寄存器，产生的密钥是的密钥是m序列。又设序列。又设Sh和和Sh1是序列中两个连是序列中两个连续的续的n长向量（两个连续的状态），其中长向量（两个连续的状态），其中lSh ，Sh111nhhhaaanhhhaaa2161/90设序列设序列ai满足线性递推关系满足线性递推关系lah+n=c1ah+n1 c2ah+n2 cnah可表示为：可表示为：l l即即Sh1MSh，M是其中矩阵是其中矩阵又设敌手知道一段长为又设敌手知道一段长为2n的明密文对的明密文对lxx1x2.x2n，yy1y2.y2n于是由二元加法流密码加密变换变型算法于是由二元加法流密码加密变换变型算法zi=xi yi可得长为可得长为2n的密钥序列的密钥序列 zz1z2.z2nnhhhaaa2112101000010ccccnnn11nhhhaaa62/90由长为由长为2n的密钥序列可推出的密钥序列可推出LFSR连续的连续的n+1个状态：个状态：lS1=(z1z2.zn)T 记为记为 (a1a2.an)T （此处教材中少了转置符号）（此处教材中少了转置符号）lS2=(z2z3.zn+1)T 记为记为 (a2a3.an+1)TllSn+1=(zn+1zn+2.z2n)T 记为记为 (an+1an+2.a2n)T作矩阵作矩阵X=(S1S2Sn)l则则(an+1an+2.a2n)(cncn-1.c1) =(cncn-1.c1)X若若X可逆，则可逆，则(cncn-1.c1)(an+1an+2.a2n)X1即即2n个元素构成一个行向量和一个矩阵，从而可以推导出个元素构成一个行向量和一个矩阵，从而可以推导出密钥产生器的生成多项式。密钥产生器的生成多项式。12113221nnnnnaaaaaaaaa63/90而而X是由是由S1S2Sn作为列向量构成的，要证作为列向量构成的，要证X可逆，只需证可逆，只需证明这明这n个向量线性无关个向量线性无关证明：证明：l由序列递推式由序列递推式ah+n=c1ah+n1 c2ah+n2 cnahl可得向量之间递推关系可得向量之间递推关系 Sh+n=c1Sh+n1 c2Sh+n2 cnShl在二元域上在二元域上 Sh+n=c1Sh+n1c2Sh+n2cnSh l对于对于n级级m序列，序列，n是生成该序列的最小级数是生成该序列的最小级数设设m是使是使S1，S2，Sm 线性相关的最小整数，即存在一线性相关的最小整数，即存在一组不全为组不全为0的系数的系数l1，l2，lm，不妨设，不妨设l11使得使得m个非个非零向量满足零向量满足lSm+l2Sm1l3Sm2lmS10l即即 Sml2Sm1l3Sm2lmS1 （二元域加法）（二元域加法）64/90那么对于任意整数那么对于任意整数i有，方程两边同时左乘有，方程两边同时左乘Mi 得得lSmiMiSmMi(l2Sm1l3Sm2lmS1)l l2MiSm1l3MiSm2lmMiS1l l2Smi1l3Smi2lmSi1由于以上关系式对任意的由于以上关系式对任意的i都成立，所以它也给出都成立，所以它也给出了密钥流的一个递推关系式了密钥流的一个递推关系式l am+i=l2am+i1 l3am+i2 lmai+1l即密钥流可以由即密钥流可以由m1级级LFSR生成，而生成，而由已知由已知得得m序列序列密钥流的级数最小为密钥流的级数最小为n，所以必有，所以必有n=m1l而而m是使得是使得S1，S2，Sm线性相关的最小整数，现在线性相关的最小整数，现在nm所以所以n个向量个向量S1，S2，Sn必线性无关，即矩阵必线性无关，即矩阵X可逆。可逆。65/90【例【例26】设敌手得到密文串设敌手得到密文串101101011110010和相应密文和相应密文串串011001111111001，并且假定敌手还知道密钥流是使用，并且假定敌手还知道密钥流是使用5级移位寄存器产生的，采用二元加法流密码。试破译该密级移位寄存器产生的，采用二元加法流密码。试破译该密钥流产生器，即求解出递推关系钥流产生器，即求解出递推关系l解：由明密文串立即可得相应得密钥流为二者对应位异或，得解：由明密文串立即可得相应得密钥流为二者对应位异或，得110100100001011l由已知的移位寄存器的级数由已知的移位寄存器的级数5，提取密钥流的前，提取密钥流的前10个比特，建立如个比特，建立如下方程：下方程：lSTn1CXl(a6a7a8a9a10)=(c5c4c3c2c1) ，即，即(0 1 0 0 0)=(c5c4c3c2c1)9876587654765436543254321aaaaaaaaaaaaaaaaaaaaaaaaa001000100110010001010101166/90l而而 ，从而，从而(c5c4c3c2c1)(0 1 0 0 0)l 所以有所以有(c5c4c3c2c1)(10010)从而密钥流的递推关系为从而密钥流的递推关系为lai5=c2ai3 c5aiai3 ail矩阵的逆满足矩阵的逆满足A-1=A*/|A|等于等于A的伴随阵除以的伴随阵除以A的行列式的行列式l解上述的方程组还可用克莱姆法则，解上述的方程组还可用克莱姆法则，ci|D 6-i|/|D |由于由于矩阵满秩，矩阵满秩，|D |1100100010011001000101010110110111010100000100110010011011101010000010011001067/90线性反馈移位寄存器（线性反馈移位寄存器（LFSR）的综合）的综合m-序列是满足序列是满足Golomb三条随机性公设的三条随机性公设的PN序列，但其不可以作为一个序列，但其不可以作为一个序列密码的密钥序列。因为：对序列密码的密钥序列。因为：对m-序列，知道其少量的比特以后是可以序列，知道其少量的比特以后是可以破译的破译的l级数较少的移位寄存器如果其反馈函数为非线性的，则可能相当于一个级数级数较少的移位寄存器如果其反馈函数为非线性的，则可能相当于一个级数较大的线性反馈移位寄存器产生的序列较大的线性反馈移位寄存器产生的序列 LFSR的综合问题就在于根据序列的少量比特求出整个序列所满足的线性的综合问题就在于根据序列的少量比特求出整个序列所满足的线性递推关系。递推关系。l在前述方法中：先假定线性递推关系，然后由序列的各项应该适合之而导出在前述方法中：先假定线性递推关系，然后由序列的各项应该适合之而导出线性方程组线性方程组；但这样的方法不容易确定所适用的；但这样的方法不容易确定所适用的LFSR的级数的级数n，从而不能导，从而不能导致恰当规模的线性方程组；并且当上述致恰当规模的线性方程组；并且当上述n很大时，求解相应规模线性方程组也很大时，求解相应规模线性方程组也很困难。（如破译中的方法。）很困难。（如破译中的方法。）l有些序列并不是有些序列并不是m序列，甚至是非线性反馈移位寄存器产生的序列，但该序序列，甚至是非线性反馈移位寄存器产生的序列，但该序列总能等效为一个列总能等效为一个LFSR，我们要解决的是根据序列的少量比特求出整个序列，我们要解决的是根据序列的少量比特求出整个序列满足的递推关系，即该序列的极小多项式和相应的线性复杂度。满足的递推关系，即该序列的极小多项式和相应的线性复杂度。l著名的著名的Berlekamp-Massey迭代算法，简称迭代算法，简称B-M算法，可以解决以上问题算法，可以解决以上问题l参见参见伪随机序列及其应用，肖国镇，梁传甲，王育民，国防工业出版社伪随机序列及其应用，肖国镇，梁传甲，王育民，国防工业出版社68/90在一个一般在一个一般n-FSR的状态图中，至少含有一个圈，且从的状态图中，至少含有一个圈，且从任意状态出发进动若干拍后必定进入某一个圈！这时得任意状态出发进动若干拍后必定进入某一个圈！这时得到的输出序列虽不必是周期序列，但去掉其前若干项后到的输出序列虽不必是周期序列，但去掉其前若干项后即得到周期序列，也就是说这样的序列为即得到周期序列，也就是说这样的序列为终归周期序列终归周期序列。 M-序列序列l若一若一n-FSR的输出序列的周期达到最大值的输出序列的周期达到最大值2n，则称此序列为，则称此序列为(n级级)M-序列。序列。l显然，如果一个显然，如果一个n-FSR有一个输出序列为有一个输出序列为M-序列，则其状态图序列，则其状态图是一个包含是一个包含F2n中所有中所有2n个点的大圈，从而这个个点的大圈，从而这个n-FSR由任意初态由任意初态产生的序列都是产生的序列都是M-序列（一共有序列（一共有2n个且相互平移等价！），这个且相互平移等价！），这个个n-FSR本身也就被称为本身也就被称为M-序列生成器，而相应的反馈函数被序列生成器，而相应的反馈函数被称为称为M-序列反馈函数。序列反馈函数。l例：例：.反馈函数为反馈函数为 的的3-FSR。xi是寄存是寄存器状态，器状态，321321),(xxxxxxf69/90布尔函数布尔函数f(x1,x2,xn)是是n级级M-序列的反馈函数的序列的反馈函数的必要条件是必要条件是:l f(x1,x2,xn)是非奇异的，即是非奇异的，即f(x1,x2,xn)=x1+f0(x2,x3,xn)l 中中n-1元布尔函数元布尔函数f0(x2,x3,xn) 还必须满足：还必须满足：lf0的重量的重量W(f0)是奇数；是奇数；l在在f0的任一表达中，的任一表达中，x2,x3,xn都出现；都出现；l在在f0的多项式表示中，项数为奇数、常数项的多项式表示中，项数为奇数、常数项1必出现、线性项必出现、线性项x2,x3,xn不能全出现、且不能全出现、且n-1次项次项x2x3xn一定出现。一定出现。70/902.6非线性序列非线性序列密钥流生成器可分解为驱动子系统和非线性组合密钥流生成器可分解为驱动子系统和非线性组合子系统，如图所示子系统，如图所示 l驱动子系统常用一个或多个线性反馈移位寄存器来实现，驱动子系统常用一个或多个线性反馈移位寄存器来实现，l非线性组合子系统用非线性组合函数非线性组合子系统用非线性组合函数F来实现，如图所来实现，如图所示。示。l本节介绍第本节介绍第2部分非线性组合子系统部分非线性组合子系统71/90定义：定义：二元序列的线性复杂度二元序列的线性复杂度指生成该序列的最指生成该序列的最短短LFSR的级数，最短的级数，最短LFSR的特征多项式称为的特征多项式称为二二元序列的极小特征多项式元序列的极小特征多项式l为了使密钥流生成器输出的二元序列尽可能复杂，应保为了使密钥流生成器输出的二元序列尽可能复杂，应保证其证其周期尽可能大周期尽可能大、线性复杂度和不可预测性尽可能高线性复杂度和不可预测性尽可能高l常使用多个常使用多个LFSR来构造二元序列，称每个来构造二元序列，称每个LFSR的输的输出序列为驱动序列出序列为驱动序列l显然密钥流生成器输出序列的周期不大于各驱动序列显然密钥流生成器输出序列的