现代密码学第5章：序列密码

序列密码《现代密码学》第5章1本章主要内容1、序列密码的基本概念2、线性反馈移位寄存器3、线性移位寄存器的一元多项式表示4、m序列的伪随机性5、M序列的特性6、m序列密码的破译7、非线性序列8、欧洲NESSIE工程及其征集的Lili-128候选算法9、习题2序列密码的基本思想是利用密钥k产生一个密钥流z=z0z1…，并使用如下规则对明文串x=x0x1x2…加密：

y=y0y1y2…=Ez0(x0)Ez1(x1)Ez2(x2)…。密钥流由密钥流发生器f产生：zi=f(k,σi)，这里σi是加密器中的记忆元件（存储器）在时刻i的状态，f是由密钥k和σi产生的函数。1.序列密码的基本概念3分组密码与序列密码的区别就在于有无记忆性（如图）。序列密码的滚动密钥z0=f(k,σ0)由函数f、密钥k和指定的初态σ0完全确定。此后，由于输入加密器的明文可能影响加密器中内部记忆元件的存储状态，因而σi(i>0)可能依赖于k，σ0，x0，x1，…，xi-1等参数。1.序列密码的基本概念4分组密码和序列密码的比较5序列密码的例子：设对定义取K=8明文为rendezvous明文对应的整数序列为17413342521142018密钥流为：8174133425211420密文对应的整数序列为2521171673209812密文为：zvrqhdujim怎样解密？6根据加密器中记忆元件的存储状态σi是否依赖于输入的明文字符，序列密码可进一步分成同步和自同步两种。

σi独立于明文字符的叫做同步序列密码，否则叫做自同步序列密码。由于自同步序列密码的密钥流的产生与明文有关，因而较难从理论上进行分析。目前大多数研究成果都是关于同步序列密码的。1.1同步序列密码7在同步序列密码中，由于zi=f(k,σi)与明文字符无关，因而此时密文字符yi=Ezi(xi)也不依赖于此前的明文字符。因此，可将同步序列密码的加密器分成密钥流产生器和加密变换器两个部分。如果与上述加密变换对应的解密变换为xi=Dzi(yi)，则可给出同步序列密码体制的模型如下图所示。1.1同步序列密码8滚动密钥生成器滚动密钥生成器KK安全信道…………同步序列密码体制模型9同步序列密码的加密变换Ezi可以有多种选择，只要保证变换是可逆的即可。实际使用的数字保密通信系统一般都是二元系统，因而在有限域CF(2)上讨论的二元加法序列密码（如下图）是目前最为常用的序列密码体制，其加密变换可表示为yi=zixi。

1.1同步序列密码10加法序列密码体制模型滚动密钥生成器滚动密钥生成器KK安全信道…………11一次一密密码是加法序列密码的原型。事实上，如果（即密钥用作滚动密钥流），则加法序列密码就退化成一次一密密码。实际使用中，密码设计者的最大愿望是设计出一个滚动密钥生成器，使得密钥经其扩展成的密钥流序列具有如下性质：极大的周期、良好的统计特性、抗线性分析、抗统计分析。

1.1同步序列密码12有限状态自动机是具有离散输入和输出（输入集和输出集均有限）的一种数学模型，由以下3部分组成：①有限状态集②有限输入字符集和有限输出字符集。③转移函数即在状态为si，输入为Aj(1)时，输出为Ak(2)，而状态转移为sk。1.2有限状态自动机13有限状态自动机可用有向图表示，称为转移图。转移图的顶点对应于自动机的状态，若状态si在输入A(1)i时转为状态sj，且输出一字符A(2)j，则在转移图中，从状态si到状态sj有一条标有(A(1)i,A(2)j)的弧线，见下图。14S1S2S3有限状态自动机的转移图15例：转移函数由下表给出：16上例中，若输入序列为，初始状态为s1，则得到状态序列s1s2s2s3s2s1s2输出字符序列思考题：如果上面的输入序列变为：则上面的结果为什么？1.2有限状态自动机172.密钥序列生成器(KG)我们知道，序列密码的关键在于密钥序列生成器KG的设计。一般来说，KG的输入——种子密钥k是较短的，人们却希望它的输出——密钥序列k对不知情的人来说象是随机的。到底该从哪些角度把握随机性等、才使所设计出来的KG能够具有我们需要的安全程度？18密钥序列生成器(KG)基本要求人们就目前的想象和预见，对KG提出了以下基本要求：种子密钥k的变化量足够大，一般应在2128以上；KG产生的密钥序列k具极大周期，一般应不小于255；k具有均匀的n-元分布，即在一个周期环上，某特定形式的n-长bit串与其求反，两者出现的频数大抵相当(例如，均匀的游程分布)；19k不可由一个低级(比如，小于106级)的LFSR产生，也不可与一个低级LFSR产生的序列只有比率很小的相异项；利用统计方法由k提取关于KG结构或K的信息在计算上不可行；混乱性.即k的每一bit均与k的大多数bit有关；扩散性.即k任一bit的改变要引起k在全貌上的变化。密钥序列生成器(KG)基本要求20同步序列密码的关键是密钥流产生器。一般可将其看成一个参数为k的有限状态自动机，由一个输出符号集Z、一个状态集∑、两个函数φ和ψ以及一个初始状态σ0组成（如下图）。状态转移函数φ:σi→σi+1，将当前状态σi变为一个新状态σi+1，输出函数ψ:σi→zi，当前状态σi变为输出符号集中的一个元素zi。同步序列密码密钥流产生器21作为有限状态自动机的密钥流生成器kkk22这种密钥流生成器设计的关键在于找出适当的状态转移函数φ和输出函数ψ，使得输出序列z满足密钥流序列z应满足的几个条件，并且要求在设备上是节省的和容易实现的。为了实现这一目标，必须采用非线性函数。作为有限状态自动机的密钥流生成器23由于具有非线性的φ的有限状态自动机理论很不完善，相应的密钥流产生器的分析工作受到极大的限制。相反地，当采用线性的φ和非线性的ψ时，将能够进行深入的分析并可以得到好的生成器。为方便讨论，可将这类生成器分成驱动部分和非线性组合部分（如下图）。驱动部分控制生成器的状态转移，并为非线性组合部分提供统计性能好的序列；而非线性组合部分要利用这些序列组合出满足要求的密钥流序列。同步序列密码密钥流产生器24密钥流生成器的分解驱动子系统非线性组合子系统kk25目前最为流行和实用的密钥流产生器如图所示，其驱动部分是一个或多个线性反馈移位寄存器。常见的两种密钥流产生器LFSR………FLFSR1LFSR2LFSRn……FFF26KG的一般结构通常，人们总是把KG设计得具有一定的结构特点，从而可以分析和论证其强度，以增加使用者的置信度。一般有以下模式：驱动子系统f（可线性）非线性组合子系统F种子密钥k……k=k0k1k2

KG结构分解示意图

27在上图中，f——一般由m-序列(或M-序列)生成器构成，提供若干周期大、统计特性好的序列(称为驱动序列)。F——就是把f产生的多条驱动序列综合在一起的一些非线性编码手段，目的是有效地破坏和掩盖多条驱动序列中存在的规律或关系，提高线性复杂度。KG的一般结构28F的设计：两种典型的基本编码手段非线性组合生成器一个非线性组合生成器的图示如下：N1-LFSRN2-LFSRNt-LFSR

),,,(21txxxFLkF是一个t元非线性布尔函数，一般要求：

具有较高的非线性次数；

是平衡的。29F的设计：两种典型的基本编码手段一个有关的结果是：若对一切i=1,2,,t，Ni-LFSR都是m-序列生成器，且ij(Ni,Nj)=1，则

p(k)=(2N1-1)(2N2-1)

(2Nt-1)，

(k)=F*(N1,N2,

,Nt)，这里F*是把F在F2上的多项式表示作为整数环Z上的多项式来计算而得的函数。30F的设计：两种典型的基本编码手段非线性组合生成器的一个特殊情形是所谓的非线性滤波生成器，或也称为前馈网络，它的图示如下：N-LFSR

k31F的设计：两种典型的基本编码手段钟控序列生成器一个钟控序列生成器的图示如下：LLLN1101++iiinnnxxxxx}{inx时刻iN-LFSR作速度因子控制器D=be-1·2e-1

++b1·2+

b0+cbe-1

b1b0滑动位被钟控序列此时刻输出指针位置下一时刻输出指针位置输出指针初始位置n00随意选定(缺省值为0）ni+1=ni+D32F的设计：两种典型的基本编码手段一个特殊情形就是“停停走走”(Stop-and-Go)生成器，它的图示如下：n-LFSR1m-LFSR2时钟脉冲k一个有关的结果是：若n-LFSR1与m-LFSR2都是m-序列生成器，且n|m或2n-1为素数，则

p(k)=(2n-1)(2m-1)，

(k)至少为[m,n](2(m,n)-1)。33移位寄存器是序列密码产生密钥流的一个主要组成部分。GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1,a2,…,an)组成，如图所示。2.线性反馈移位寄存器….输出序列34每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于GF(2)上的一个n维向量，共有2n种可能的状态。每一时刻的状态可用n长序列a1,a2,…,an或n维向量(a1,a2,…,an)表示，其中ai是第i级存储器的内容。GF(2)上的n级反馈移位寄存器35初始状态由用户确定，当第i个移位时钟脉冲到来时，每一级存储器ai都将其内容向下一级ai-1传递，并根据寄存器此时的状态a1,a2,…,an计算f(a1,a2,…,an)，作为下一时刻的an。反馈函数f(a1,a2,…,an)是n元布尔函数，即n个变元a1,a2,…,an可以独立地取0和1这两个可能的值，函数中的运算有逻辑与、逻辑或、逻辑补等运算，最后的函数值也为0或1。GF(2)上的n级反馈移位寄存器36例：下图是一个3级反馈移位寄存器，其初始状态为(a1,a2,a3)=(1,0,1)，输出可由表2.2求出。一个3级反馈移位寄存器GF(2)上的n级反馈移位寄存器输出序列37一个3级反馈移位寄存器的状态和输出状态（a1,a2,a3)输出101110111011101110

10111038即输出序列为101110111011…，周期为4。如果移位寄存器的反馈函数f(a1,a2,…,an)是a1，a2，…，an的线性函数，则称之为线性反馈移位寄存器LFSR（linearfeedbackshiftregister）。此时f可写为f(a1,a2,…,an)=cna1cn-1a2…c1an其中常数ci=0或1，是模2加法。ci=0或1可用开关的断开和闭合来实现，如下图所示。线性反馈移位寄存器39练习：输出序列下图为3级反馈移位寄存器，其初始状态为试写出其输出序列，同时考虑如果初始状态不同，输出序列是否相同，序列的周期是否相同？40GF(2)上的n级线性反馈移位寄存器……输出序列41输出序列{at}满足an+t=cnatcn-1at+1…c1an+t-1其中t为非负正整数。或者{an}：线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最重要的部件之一。线性反馈移位寄存器42例：下图是一个5级线性反馈移位寄存器，其初始状态为（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出输出序列为1001101001000010101110110001111100110…周期为31。例：一个5级线性反馈移位寄存器输出序列43练习：下图为一个5级线性反馈移位寄存器，其初始状态为则其输出序列为？输出序列44在线性反馈移位寄存器中总是假定c1,c2,…,cn中至少有一个不为0，否则f(a1,a2,…,an)≡0，这样的话，在n个脉冲后状态必然是00…0，且这个状态必将一直持续下去。若只有一个系数不为0，设仅有cj不为0，实际上是一种延迟装置。

一般对于n级线性反馈移位寄存器，总是假定cn=1。线性反馈移位寄存器45线性反馈移位寄存器输出序列的性质完全由其反馈函数决定。n级线性反馈移位寄存器最多有2n个不同的状态。若其初始状态为0，则其状态恒为0。若其初始状态非0，则其后继状态不会为0。因此n级线性反馈移位寄存器的状态周期小于等于2n-1。其输出序列的周期与状态周期相等，也小于等于2n-1。只要选择合适的反馈函数便可使序列的周期达到最大值2n-1，周期达到最大值的序列称为m序列。线性反馈移位寄存器463.线性移位寄存器的一元多项式表示线性移位寄存器的输出序列满足递推关系当k>=1时成立。写出来看一看：…(1)47这种递推关系可以用一个一元高次多项式来表示：称这个多项式为LFSR的特征多项式。（*）在(1)式中两边同时加上得到：令据其在输出序列中元素的左右位置，左移一位相当于乘以2，则有：线性移位寄存器的特征多项式48

注意：线性反馈移位寄存器与特征多项式是一一对应的，如果知道了线性反馈移位寄存器的结构，可以写出它的特征多项式，同样可以根据特征多项式画出移位寄存器的结构。49设n级线性移位寄存器对应于递推关系(*)，由于ai∈GF(2)(i=1,2,…,n)，所以共有2n组初始状态，即有2n个递推序列，其中非恒零的有2n-1个，记2n-1个非零序列的全体为G(p(x))。50定义：给定序列{ai}，幂级数称为该序列的生成函数。

多项式表示中的部分概念51

定理2.1设p(x)=1+c1x+…+cn-1xn-1+cnxn是GF(2)上的多项式，G(p(x))中任一序列{ai}的生成函数A(x)满足：

其中多项式表示中的部分概念52证明：在等式an+1=c1anc2an-1…cna1an+2=c1an+1c2an…cna2 …两边分别乘以xn,xn+1,…，再求和，可得

A(x)-(a1+a2x+…+anxn-1) =c1x[A(x)-(a1+a2x+…+an-1xn-2)] +c2x2[A(x)-(a1+a2x+…+an-2xn-3)]+…+cnxnA(x)多项式表示中的部分概念53移项整理得

(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)=∑cn-ixn-i∑ajxj-1=(x)(证毕)

注意在GF(2)上有a+a=0。多项式表示中的部分概念54定理2.2p(x)|q(x)的充要条件是G(p(x))G(q(x))。证明：若p(x)|q(x)，可设q(x)=p(x)r(x)，因此所以若{ai}∈G(p(x))，则{ai}∈G(q(x))，即G(p(x))G(q(x))。多项式表示中的部分概念55反之，若G(p(x))G(q(x))，则对于多项式(x)，存在序列{ai}∈G(p(x))以A(x)=(x)p(x)为生成函数。特别地，对于多项式(x)=1，存在序列{ai}∈G(p(x))以1/p(x)为生成函数。由于G(p(x))G(q(x))，序列{ai}∈G(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来产生。多项式表示中的部分概念56定义：设p(x)是GF(2)上的多项式，使p(x)|(xp-1)的最小p称为p(x)的周期或阶。定理2.3若序列{ai}的特征多项式p(x)定义在GF(2)上，p是p(x)的周期，则{ai}的周期r|p。多项式表示中的部分概念57证明：由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,0≤t<r，则ai+p=ai+kr+t=ai+t=ai，所以t=0，即r|p。（证毕）多项式表示中的部分概念58

n级LFSR输出序列的周期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,…多项式表示中的部分概念59下面讨论特征多项式满足什么条件时，LFSR的输出序列为m序列。定理2.4设p(x)是n次不可约多项式，周期为m，序列{ai}∈G(p(x))，则{ai}的周期为m。多项式表示中的部分概念60证明：设{ai}的周期为r，由定理2.3有r|m，所以r≤m。设A(x)为{ai}的生成函数，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)多项式表示中的部分概念61于是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)，因此m≤r。综上r=m。（证毕）多项式表示中的部分概念62定理2.5n级LFSR产生的序列有最大周期2n-1的必要条件是其特征多项式为不可约的。证明：设n级LFSR产生的序列周期达到最大2n-1，除0序列外，每一序列的周期由特征多项式惟一决定，而与初始状态无关。设特征多项式为p(x)，若p(x)可约，可设为p(x)=g(x)h(x)，其中g(x)不可约，且次数k<n。由于G(g(x))G(p(x))，而G(g(x))中序列的周期一方面不超过2k-1，另一方面又等于2n-1，这是矛盾的，所以p(x)不可约。（证毕）该定理的逆不成立，即LFSR的特征多项式为不可约多项式时，其输出序列不一定是m序列。多项式表示中的部分概念63例：

f(x)=x4+x3+x2+x+1为GF(2)上的不可约多项式，这可由x,x+1,x2+x+1都不能整除f(x)得到。以f(x)为特征多项式的LFSR的输出序列可由

ak=ak-1ak-2ak-3ak-4(k≥4)

和给定的初始状态求出，设初始状态为0001，则输出序列为000110001100011…，周期为5，不是m序列。多项式表示中的部分概念641110000110000110000111000111000011000011000011100011100001100001100001输出状态（）周期为5，不是m序列多项式表示中的部分概念65定义：若n次不可约多项式p(x)的阶为2n-1，则称p(x)是n次本原多项式。定理2.6设{ai}∈G(p(x))，{ai}为m序列的充要条件是p(x)为本原多项式。多项式表示中的部分概念66本原多项式：67证明：若p(x)是本原多项式，则其阶为2n-1，由定理2.4得{ai}的周期等于2n-1，即{ai}为m序列。反之，若{ai}为m序列，即其周期等于2n-1，由定理2.5知p(x)是不可约的。由定理2.3知{ai}的周期2n-1整除p(x)的阶，而p(x)的阶不超过2n-1，所以p(x)的阶为2n-1，即p(x)是本原多项式。（证毕）多项式表示中的部分概念68

{ai}为m序列的关键在于p(x)为本原多项式，n次本原多项式的个数为其中为欧拉函数。已经证明，对于任意的正整数n，至少存在一个n次本原多项式。所以对于任意的n级LFSR，至少存在一种连接方式使其输出序列为m序列。多项式表示中的部分概念69例：设p(x)=x4+x+1，由于p(x)|(x15-1)，但不存在小于15的常数，使得p(x)|(xl-1)，所以p(x)的阶为15。p(x)的不可约性可由x,x+1,x2+x+1都不能整除p(x)得到，所以p(x)是本原多项式。若LFSR以p(x)为特征多项式，则输出序列的递推关系为ak=ak-1ak-4(k≥4)多项式表示中的部分概念70若初始状态为1001，则输出为：100100011110101100100011110101…状态序列为：

1001，0100，0010，0001，1000，1100，1110，1111，0111，1011，0101，1010，1101，0110，0011，1001，0100，0010，0001……可见，它是周期为24-1=15，即输出序列为m序列。多项式表示中的部分概念71例：(100110101111000)

按前面的性质有：游程的总数为8，分别为1，00，11，0，1，0，1111，0000。其中有一半的游程长度为2，长度为2的游程为四分之一，最后有一个长度为4的游程和一个长度为3的游程。输出序列72序列密码的安全性取决于密钥流的安全性，要求密钥流序列有好的随机性，以使密码分析者对它无法预测。也就是说，即使截获其中一段，也无法推测后面是什么。如果密钥流是周期的，要完全做到随机性是困难的。严格地说，这样的序列不可能做到随机，只能要求截获比周期短的一段时不会泄露更多信息，这样的序列称为伪随机序列。

4.m序列的伪随机性73为讨论序列的随机性，我们先讨论随机序列的一般特性。设{ai}=(a1a2a3…)为0、1序列，例如00110111，其前两个数字是00，称为0的2游程；接着是11，是1的2游程；再下来是0的1游程和1的3游程。随机序列的特性74定义：GF(2)上周期为T的序列{ai}的自相关函数定义为R(τ)=(1/T)∑(-1)ak(-1)ak+τ,0≤τ≤T-1

定义中的和式表示序列{ai}与{ai+τ}（序列{ai}向后平移τ位得到）在一个周期内对应位相同的位数与对应位不同的位数之差。当τ=0时，R(τ)=1；当τ≠0时，称R(τ)为异相自相关函数。随机序列的特性75

Golomb对伪随机周期序列提出了应满足的如下3个随机性公设：①在序列的一个周期内，0与1的个数相差至多为1。随机序列的特性76②在序列的一个周期内，长为i的游程占游程总数的1/2i(i=1,2,…)，且在等长的游程中0的游程个数和1的游程个数相等。③异相自相关函数是一个常数。公设①说明{ai}中0与1出现的概率基本上相同;②说明0与1在序列中每一位置上出现的概率相同;③意味着通过对序列与其平移后的序列做比较，不能给出其他任何信息。随机序列的特性77从密码系统的角度看，一个伪随机序列还应满足下面的条件：①{ai}的周期相当大。②{ai}的确定在计算上是容易的。③由密文及相应的明文的部分信息，不能确定整个{ai}。伪随机序列应满足的条件78m-序列概念称周期达到最大值2n-1的n-LFSR（输出）序列为（n级）m-序列。显然，若某n-LFSR产生一个m-序列，则其状态图除了单点(00

0)构成的圈外，就是由F2n\{(00

0)}中所有点排列而成的一个大圈，因而其任何非全零的输出序列均是m-序列，故称之为m-序列生成器。例.4-LFSR[1,0,0,1]。79下一定理说明，m序列满足Golomb的3个随机性公设。定理2.7GF(2)上的n长m序列{ai}具有如下性质：①0,1平衡性：在一个周期内，0、1出现的次数分别为2n-1-1和2n-1。②游程特性：在一个周期内，总游程数为2n-1；对1≤i≤n-2，长为i的游程有2n-i-1个，且0、1游程各半；长为n-1的0游程一个，长为n的1游程一个。m序列的特性80③{ai}的自相关函数为m序列的特性81周期p序列a=a0a1a2

的自相关函数定义如下：自相关函数计算.对给定的周期序列a，①找出a的周期段：a0a1a2

ap-1②计算：周期序列的自相关函数计算82

(-1)a0

(-1)a1

(-1)a2

(-1)ap-1

（左环移t位）(-1)at

(-1)at+1

(-1)at+2

(-1)at-1

对位相乘后再相加，即得pCa(t)。例.对a=(10011101101)

，计算Ca(4)。自相关特性是说，n-级m-序列a的自相关函数值如下：(a(a<<t)非全零且满足a的线性递归关系)周期序列的自相关函数计算83证明：①在n长m序列的一个周期内，除了全0状态外，每个n长状态（共有2n-1个）都恰好出现一次，这些状态中有2n-1个在a1位是1，其余2n-1-2n-1=2n-1-1个状态在a1位是0。②对n=1,2，易证结论成立。对n>2，当1≤i≤n-2时，n长m序列的一个周期内，长为i的0游程数目等于序列中如下形式的状态数目：100…01*…*，其中n-i-2个*可任取0或1。这种状态共有2n-i-2个。同理可得长为i的1游程数目也等于2n-i-2，所以长为i的游程总数为2n-i-1。m序列的特性84由于寄存器中不会出现全0状态，所以不会出现0的n游程，但必有一个1的n游程，而且1的游程不会更大，因为若出现1的n+1游程，就必然有两个相邻的全1状态，但这是不可能的。这就证明了1的n游程必然出现在如下的串中：当这n+2位通过移位寄存器时，便依次产生以下状态：

m序列的特性85由于，这两个状态只能各出现一次，所以不会有1的n-1游程。于是在一个周期内，总游程数为m序列的特性86③{ai}是周期为2n-1的m序列，对于任一正整数τ(0<τ<2n-1)，{ai}+{ai+τ}在一个周期内为0的位的数目正好是序列{ai}和{ai+τ}对应位相同的位的数目。设序列{ai}满足递推关系：

ah+n=c1ah+n-1c2ah+n-2…cnah故ah+n+τ=c1ah+n+τ-1c2ah+n+τ-2…cnah+τ ah+nah+n+τ=c1(ah+n-1ah+n+τ-1)c2(ah+n-2ah+n+τ-2)…cn(ahah+τ)m序列的特性87令bj=aj

aj+τ，由递推序列{ai}可推得递推序列{bi}，{bi}满足bh+n=c1bh+n-1c2bh+n-2…cnbh{bi}也是m序列。为了计算R(τ)，只要用{bi}在一个周期中0的个数减去1的个数，再除以2n-1，即（证毕）m序列的特性88一个n-LFSR（给定结构常数）具有“由一个短的种子产生一个长的序列”的功能：以短的种子作为初态，产生的输出序列可以任意长！上述表明，任一n-LFSR都初步具有作为一个KG的资格；但从作为KG的效用来讲，自然更希望所使用的n-LFSR进一步是m-序列生成器。m序列的特性89线性反馈移位寄存器（LFSR）的综合n-FSR的结构常数+初态n-FSR序列分析综合前面我们讲过，m-序列是满足Golomb三条随机性公设的PN序列，但其不可以作为一个序列密码的密钥序列。因为：对m-序列，知道其少量的比特以后是可以预测的！现在就讲怎么样仅凭已知的少量比特来找出整个序列所满足的线性递推关系。一般地，把有关反馈移位寄存器的求解问题，从正反两个方面分为分析与综合：90线性反馈移位寄存器（LFSR）的综合线性反馈移位寄存器的综合问题就在于根据序列的少量比特求出整个序列所满足的线性递推关系。一个自然的想法就是：先假定线性递推关系，然后由序列的各项应该适合之而导出线性方程组；但这样的方法有其不易行之处在于：不容易确定所适用的LFSR的级数n，从而就不能导致恰当规模的线性方程组；当上述的n很大时，求解相应规模的线性方程组也很困难。91事实上，对于线性反馈移位寄存器的综合问题已经出现了著名的解法：Berlekamp-Massey迭代算法，简称B-M算法。线性反馈移位寄存器（LFSR）的综合92B-M算法描述Input：SN=a0a1a2aN-1Step1：置f0(x)=1，L0=0（初值）Step2：设<fi(x),Li>，i=0,1,2,…,n（0n<N）均已求出，且L0

L1

L2

Ln。设,由此计算。Step3：当dn=0时，取fn+1(x)=fn(x),Ln+1=Ln。

当dn=1时，若Ln=0,则取fn+1(x)=xn+1+1,Ln+1=n+1；

否则,找出m(0

m<n)使Lm<Lm+1=Lm+2=

=Ln,取fn+1(x)=fn(x)+xn-mfm(x),Ln+1=max{Ln,n+1-Ln}。对于n=0,1,2,

，重复Step2与Step3，直至n=N-1Output：<fN(x),LN>93B-M算法举例

输入：S8=10101111输出：<1+x3+x4,4>94有关B-M算法的结果定理1.

应用B-M算法，若以N长序列SN为输入，得到输出<fN(x),LN>，则⑴以fN(x)为联接多项式的LN-LFSR是产生SN的最短LFSR，且当时，迭代至第2LN步就得到最终输出，即：。⑵当时，产生SN的最短LFSR只是上述一个；当时，产生SN的最短LFSR一共有个。由上述定理知，在前面的例子中，以f8(x)=1+x3+x4为联接多项式的4-LFSR是唯一的产生S8=10101111的最短LFSR。95有关B-M算法的结果考虑问题：

S6=101011f6(x)=1+x2+x3

如何解释？——其实，对

，由于L6=4，故4-LFSR[0,1,1,0]生成S6；对

，由于L1+N=1，故1-LFSR[0]生成S2（规定：f(x)=1产生全零序列）。96有关B-M算法的结果对于周期序列，也可应用B-M算法求出产生它的最短LFSR的联接多项式，不过须注意：一定得是针对两个周期段去求才正确！定理2.

对周期为p的序列a=a0a1a2

，⑴应用B-M算法于S2p=a0a1

ap-1a0a1

ap-1求出<f2p(x),L2p>时，必f2p(x)的次数必为L2p，且以f2p(x)为联接多项式的L2p-LFSR是唯一的产生a的最短LFSR。⑵。97应用B-M算法举例

求产生序列a的最低次多项式，这里⑴a=111001，⑵a=(111001)

解：可见答案为：⑴

1+x2+x3；⑵1+x2+x4。98应用B-M算法举例

注.

对于⑵中周期序列a，其实以前介绍过一种求生成它的最低次联接多项式的方法：应用展转相除法可以求出最大公因式于是，从而可知生成序列a的最短LFSR的联接多项式为1+x2+x4。995.M-序列的特性在一个一般n-FSR的状态图中，至少含有一个圈，且从任意状态出发进动若干拍后必定进入某一个圈！这时得到的输出序列虽不必是周期序列，但去掉其前若干项后即得到周期序列，也就是说这样的序列为终归周期序列。若一n-FSR的输出序列的周期达到最大值2n，则称此序列为(n级)M-序列。100显然，如果一个n-FSR有一个输出序列为M-序列，则其状态图是一个包含F2n中所有2n个点的大圈，从而这个n-FSR由任意初态产生的序列都是M-序列（一共有2n个且相互平移等价！），这个n-FSR本身也就被称为M-序列生成器，而相应的反馈函数被称为M-序列反馈函数。例.反馈函数为的3-FSR。M-序列的概念101一个关于与M-序列反馈函数的结果有关布尔函数的一些知识：一个n元布尔函数是指下述形式的映射它既可以用逻辑关系式表达，也可以用真值表来表示，还可以表为多元多项式。上述三者之间的互化方法：逻辑关系式多元多项式真值表（容易）102另外，xt=x(t>1)。因此，在布尔函数f(x1,x2,…,xn)的多项式表示中，高次项的形式只有是。重量：w(f)是指在布尔函数f的真值表中，函数值列里1的个数。逻辑关系式多元多项式：真值表多元多项式（举例）一个关于与M-序列反馈函数的结果103布尔函数f(x1,x2,…,xn)是n级M-序列反馈函数的必要条件是:⑴f(x1,x2,…,xn)是非奇异的，即

f(x1,x2,…,xn)=x1+f0(x2,x3,…,xn)⑵⑴中n-1元布尔函数f0(x2,x3,…,xn)一个关于与M-序列反馈函数的结果104还必须满足：

f0的重量w(f0)是奇数；

在f0的任一表达中，x2,x3,…,xn都出现；

在f0的多项式表示中，项数为奇数、常数项1必出现、线性项x2,x3,…,xn不能全出现、且n-1次项x2x3

xn一定出现。一个关于与M-序列反馈函数的结果105n级M-序列反馈函数的个为。M-序列的统计特性.在n级M-序列的一个周期圈中，⑴0与1的数目均为2n-1；

⑵长为k的0-游程与1-游程的数目均为M-序列的特性106线性复杂度概念定义.能够产生（有限长或周期）序列a的最短LFSR的级数称为a的线性复杂度，记为

(a)；约定：

(0)=0。若对序列a应用B-M算法产生的输出为<f(x),L>，则

(a)=L。研讨：若a为n-级m-序列，则

(a)=

。107M-序列的自相关特性.设n级M-序列a的反馈函数f(x1,x2,…,xn)=x1+f0(x2,x3,…,xn)那么，⑴Ca(0)=1⑵Ca(

t)=0，0<tn-1⑶Ca(

n)=1-w(f0)/2n-2≠0对于n(n≥3)级M-序列a，M-序列的特性108上面说过，有限域上的二元加法序列密码是目前最为常用的序列密码体制，设滚动密钥生成器是线性反馈移位寄存器，产生的密钥是序列。又设和是序列中两个连续的长向量，其中6.m序列密码的破译109设序列{ai}满足线性递推关系：可表示为m序列密码的破译110或Sh+1=M·Sh，其中又设敌手知道一段长为2n的明密文对，即已知m序列密码的破译111于是可求出一段长为2n的密钥序列其中,由此可推出线性反馈移位寄存器连续的n+1个状态：m序列密码的破译112做矩阵而若X可逆，则m序列密码的破译113下面证明X的确是可逆的。因为X是由S1,S2,…,Sn作为列向量，要证X可逆，只要证明这n个向量线性无关。由序列递推关系：可推出向量的递推关系：m序列密码的破译114设m(m≤n+1)是使S1,S2,…,Sm线性相关的最小整数，即存在不全为0的系数l1,l2,…,lm，其中不妨设l1=1，使得即对于任一整数i有m序列密码的破译115由此又推出密钥流的递推关系：即密钥流的级数小于m。若m≤n，则得出密钥流的级数小于n，矛盾。所以m=n+1，从而矩阵X必是可逆的。m序列密码的破译116例：设敌手得到密文串101101011110010和相应的明文串011001111111001，因此可计算出相应的密钥流为110100100001011。进一步假定敌手还知道密钥流是使用5级线性反馈移位寄存器产生的，那么敌手可分别用密文串中的前10个比特和明文串中的前10个比特建立如下方程m序列密码的破译117即而m序列密码的破译118从而得到所以密钥流的递推关系为m序列密码的破译119已介绍密钥流生成器可分解为驱动子系统和非线性组合子系统，如图所示。7.非线性序列驱动子系统非线性组合子系统120驱动子系统常用一个或多个线性反馈移位寄存器来实现，非线性组合子系统用非线性组合函数F来实现，如图所示。本节介绍第2部分非线性组合子系统。7.非线性序列LFSRFLFSR1LFSRnF常见的两种密钥流产生器121为了使密钥流生成器输出的二元序列尽可能复杂，应保证其周期尽可能大、线性复杂度和不可预测性尽可能高，因此常使用多个LFSR来构造二元序列，称每个LFSR的输出序列为驱动序列，显然密钥流生成器输出序列的周期不大于各驱动序列周期的乘积，因此，提高输出序列的线性复杂度应从极大化其周期开始。非线性序列122二元序列的线性复杂度指生成该序列的最短LFSR的级数，最短LFSR的特征多项式称为二元序列的极小特征多项式。下面介绍4种由多个LFSR驱动的非线性序列生成器。非线性序列123

Geffe序列生成器由3个LFSR组成，其中LFSR2作为控制生成器使用，如图所示。7.1Geffe序列生成器Geffe序列生成器图LFSR1LFSR2LFSR3输出124当LFSR2输出1时，LFSR2与LFSR1相连接；当LFSR2输出0时，LFSR2与LFSR3相连接。若设LFSRi的输出序列为{a(i)k}(i=1,2,3)，则输出序列{bk}可以表示为Geffe序列生成器125多路复合器表示的Geffe序列生成器LFSR1LFSR1LFSR1多路复合器选择控制126

Geffe序列生成器也可以表示为上图的形式，其中LFSR1和LFSR3作为多路复合器的输入，LFSR2控制多路复合器的输出。设LFSRi的特征多项式分别为ni次本原多项式，且ni两两互素，则Geffe序列的周期为线性复杂度为Geffe序列生成器127

Geffe序列的周期实现了极大化，且0与1之间的分布大体上是平衡的。Geffe序列生成器128

J-K触发器如下图所示，它的两个输入端分别用J和K表示，其输出ck不仅依赖于输入，还依赖于前一个输出位ck-1，即其中x1和x2分别是J和K端的输入。由此可得J-K触发器的真值表，如表。7.2J-K触发器129J-K触发器RJKJ-K触发器真值表JK0001010111130利用J-K触发器的非线性序列生成器见图。利用J-K触发器组成非线性序列生产器LFSR1LFSR2JK131令驱动序列{ak}和{bk}分别为m级和n级m序列，则有如果令c-1=0，则输出序列的最初3项为当m与n互素且a0+b0=1时，序列{ck}的周期为(2m-1)(2n-1)。利用J-K触发器组成非线性序列生产器132例：令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。133由表达式ck=(ak+bk+1)ck-1+ak可得因此，如果知道{ck}中相邻位的值ck-1和ck，就可以推断出ak和bk中的一个。而一旦知道足够多的这类信息，就可通过密码分析的方法得到序列{ak}和{bk}。为了克服上述缺点，Pless提出了由多个J-K触发器序列驱动的多路复合序列方案，称为Pless生成器。134

Pless生成器由8个LFSR、4个J-K触发器和1个循环计数器构成，由循环计数器进行选通控制，如下图所示。假定在时刻t输出第t(mod4)个单元，则输出序列为a0b1c2d3a4b5d67.3Pless生成器135Pless生成器LFSR1LFSR2JKLFSR7LFSR8JKLFSR3LFSR4JKLFSR5LFSR6JK3210136钟控序列最基本的模型是用一个LFSR控制另外一个LFSR的移位时钟脉冲，如图所示。7.4钟控序列生成器最简单的钟控序列生成器LFSR1LFSR2时钟脉冲137假设LFSR1和LFSR2分别输出序列{ak}和{bk}，其周期分别为p1和p2。当LFSR1输出1时，移位时钟脉冲通过与门使LFSR2进行一次移位，从而生成下一位。当LFSR1输出0时，移位时钟脉冲无法通过与门影响LFSR2。因此LFSR2重复输出前一位。假设钟控序列{ck}的周期为p，可得如下关系：其中。钟控序列生成器138又设{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)，极小特征多项式为。钟控序列生成器139例：设LFSR1为3级m序列生成器，其特征多项式为f1(x)=1+x+x3。设初态为a0=a1=a2=1，于是输出序列为{ak}=1,1,1,0,1,0,0,…。又设LFSR2为3级m序列生成器，且记其状态向量为σk，则在上图的构造下σk的变化情况如下：钟控序列生成器140

{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,…钟控序列生成器141

{ck}的极小特征多项式为1+x14x21，其线性复杂度为3·（23-1）=21，图是其线性等价生成器。一个钟控序列的线性等价生成器钟控序列生成器142实际应用中，可以用上述最基本的钟控序列生成器构造复杂的模型，具体构造方式可参阅有关文献。钟控序列生成器143设计一个性能良好的序列密码是一项十分困难的任务。最基本的设计原则是“密钥流生成器的不可预测性”，它可分解为下述基本原则：①长周期。②高线性复杂度。③统计性能良好。④足够的“混乱”。⑤足够的“扩散”。⑥抵抗不同形式的攻击。序列密码的设计原则144欧洲NESSIE工程介绍自2000年1月至2002年12月，欧洲委员会投资33亿欧元支持其信息社会技术（IST）规划中一项名为NESSIE(NewEu-ropeanSchemesforSignatures,Inte-grity,andEncryption)的工程。该工程也象DES、RIPE规划和AES的选择过程一样，采用先征集后评估的办法，但其征集范围要比NIST的AES广泛得多。8.欧洲NESSIE工程及其征集的Lili-128候选算法145信息社会不仅需要分组密码标准来提供机密性服务，而且也需要其它密码标准来提供认证和完整性等服务。因此，NESSIE的征集范围涉及到多个密码学领域，诸如：分组（块）密码；序列（流）密码；消息认证码；伪随机函数族；数字签名和Hash函数；非对称加密方案；非对称识别方案。欧洲NESSIE工程介绍146

此外，NESSIE工程将考虑候选密码标准所能应用的具体环境，甚至也征集评测这些侯选密码标准的测试方法(如统计测试)。NESSIE工程的主要目标就是通过公开征集进行公开的、透明的测试评价，提出一套强的密码标准，这些标准包括分组密码，序列密码，杂凑函数，消息认证码，数字签名方案和公钥加密方案。该工程将发展一种密码体制的评估方法（包括安全性和性能评价）和支持评估的一个软件工具箱。欧洲NESSIE工程介绍14721世纪欧洲密码标准产生：1993年2月27日，以征集对世纪欧洲新的密码算法标准为内容的NESSIE工程，终于宣布了最后的终选结果。除了从参评的42个算法方案中评出了12个方案外，还选取了已有标准中的5个方案（见打“＊”的）。NESSIE工程委员会公布的终选结果如下页。在整个评测过程中，上述方案均未发现任何缺陷。上述算法中的10个对称算法允许免费使用。非对称方案RSA—KEM、RSA—PSS和SFLASH也可以在公开领域内使用。需要特别加以说明的是由于安全性审查有些过于严密，所有6个参选的同步序列密码算法方案无一进入终选。欧洲NESSIE工程介绍148

欧洲NESSIE工程介绍149有关NESSIE工程的其它事项可通过NESSIE的主页http://去追索。欧洲NESSIE工程介绍150以下介绍一下的是关于序列密码的情况。NESSIE收到的5个候选同步序列密码如下表：欧洲NESSIE工程介绍算法名称国家（组织）整体结构设计特点Leviathan美国是一种二进制树结构密钥流由一组二进制的数结构定义Lili-128澳大利亚钟控结构由钟控子系统与数据生成子系统组成，使用了两个LFSR与两个函数BMGL瑞典密钥反馈模式(类似于OFB)基于复杂性理论，具有可证明安全性，核心是Rijdael分组密码SOBER-t32/t16澳大利亚非线性滤波结构使用带有密钥的非线性滤波函数，输出32/16比特分组SNOW瑞典由一个LFSR和一个有限状态机(FSM)组成是一个面向32-比特字的序列密码，基于经典的求和发生器的观点151限于同学们的知识和数学能力，在此仅简要介绍一下Lili-128算法。Lili-128是一种简单而快速的密钥流生成器，它使用两个LFSR和两个非线性函数来产生伪随机的二元密钥流序列。基于所完成的功能，Lili-128密钥流生成器的部件可分成两个子系统：钟控子系统和数据生成子系统。如下页图所示：候选序列密码—Lili-128算法152LFSRcfck=2···LFSRdfdn=10···c(t)z(t)钟控子系统数据生成子系统钟控候选序列密码—Lili-128算法153钟控子系统LFSRc的联接多项式为本原多项式1+x2+x14+x15+x17+x31+x33+x35+x39。在时刻t，LFSRc当前状态的第12、20两个位置（起始位置是0）的分量x12与x20作为函数fc的输入，得到的输出为c(t)=fc(x12,x20)=2x12+x20+1。显然，c(t)的范围在{1,2,3,4}。候选序列密码—Lili-128算法154数据生成子系统LFSRd的联接多项式为本原多项式1+x+x39+x42+x53+x55+x80+x83+x89。在时刻t，LFSRd当前状态的下列位置分量被抽头：{0,1,3,7,12,20,30,44,65,80}且输入给函数fd以得到z(t)，然后连续进动c(t)拍。fd选为高度非线性的、且是作为上述10个位置输入的3阶相关免疫的平衡布尔函数（真值表如下页）。候选序列密码—Lili-128算法1550,0,1,1,1