《现代密码学》第5章 序列密码

本章主要内容 1、序列密码的基本概念 2、线性反馈移位寄存器 3、线性移位寄存器的一元多项式表示 4、m序列的伪随机性 5、M序列的特性 7、非线性序列 8、欧洲NESSIE工程及其征集的Lili-128 候选算法 9、习题

1. 序列密码的基本概念 序列密码的基本思想是利用密钥k产生一个密钥流z=z0z1…，并使用如下规则对明文串x=x0x1x2…加密： y=y0y1y2…=Ez0(x0)Ez1(x1)Ez2(x2)…。 密钥流由密钥流发生器f产生： zi=f(k,σi)，这里σi是加密器中的记忆元件（存储器）在时刻i的状态，f是由密钥k和σi产生的函数。

1. 序列密码的基本概念 分组密码与序列密码的区别就在于有无记忆性（如图）。序列密码的滚动密钥z0=f(k,σ0)由函数f、密钥k和指定的初态σ0完全确定。此后，由于输入加密器的明文可能影响加密器中内部记忆元件的存储状态，因而σi(i>0)可能依赖于k，σ0，x0，x1，…，xi-1等参数。

分组密码和序列密码的比较

序列密码的例子： 怎样解密？ 设 对 定义 取K=8 明文为rendezvous 明文对应的整数序列为 17 4 13 3 4 25 21 14 20 18 密钥流为： 8 17 4 13 3 4 25 21 14 20 密文对应的整数序列为 25 21 17 16 7 3 20 9 8 12 密文为：zvrqhdujim 怎样解密？

1.1 同步序列密码 根据加密器中记忆元件的存储状态σi是否依赖于输入的明文字符，序列密码可进一步分成同步和自同步两种。 1.1 同步序列密码 根据加密器中记忆元件的存储状态σi是否依赖于输入的明文字符，序列密码可进一步分成同步和自同步两种。 σi独立于明文字符的叫做同步序列密码，否则叫做自同步序列密码。由于自同步序列密码的密钥流的产生与明文有关，因而较难从理论上进行分析。目前大多数研究成果都是关于同步序列密码的。

1.1 同步序列密码 在同步序列密码中，由于zi=f(k,σi)与明文字符无关，因而此时密文字符yi=Ezi(xi)也不依赖于此前的明文字符。因此，可将同步序列密码的加密器分成密钥流产生器和加密变换器两个部分。 如果与上述加密变换对应的解密变换为xi=Dzi(yi)，则可给出同步序列密码体制的模型如下图所示。

同步序列密码体制模型 滚动密钥生成器 K 安全信道 ……

1.1 同步序列密码 同步序列密码的加密变换Ezi可以有多种选择，只要保证变换是可逆的即可。 1.1 同步序列密码 同步序列密码的加密变换Ezi可以有多种选择，只要保证变换是可逆的即可。 实际使用的数字保密通信系统一般都是二元系统，因而在有限域CF(2)上讨论的二元加法序列密码（如下图）是目前最为常用的序列密码体制，其加密变换可表示为 yi=zi xi。

加法序列密码体制模型 滚动密钥生成器 K 安全信道 ……

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

1.2 有限状态自动机 有限状态自动机是具有离散输入和输出（输入集和输出集均有限）的一种数学模型，由以下3部分组成： ① 有限状态集 1.2 有限状态自动机 有限状态自动机是具有离散输入和输出（输入集和输出集均有限）的一种数学模型，由以下3部分组成： ① 有限状态集 ② 有限输入字符集 和有限输出字符集 。 ③ 转移函数 即在状态为si，输入为Aj(1)时，输出为Ak(2)，而状态转移为sk。

有限状态自动机可用有向图表示，称为转移图。转移图的顶点对应于自动机的状态，若状态si在输入A(1)i时转为状态sj，且输出一字符A(2)j，则在转移图中，从状态si到状态sj有一条标有(A(1)i,A(2)j)的弧线，见下图。

有限状态自动机的转移图 S1 S2 S3

例： 转移函数由下表给出：

1.2 有限状态自动机 上例中，若输入序列为 ，初始状态为s1，则得到状态序列 s1s2s2s3s2s1s2 输出字符序列 1.2 有限状态自动机 上例中，若输入序列为 ，初始状态为s1，则得到状态序列 s1s2s2s3s2s1s2 输出字符序列 思考题：如果上面的输入序列变为： 则上面的结果为什么？

2. 密钥序列生成器(KG) 我们知道，序列密码的关键在于密钥 序列生成器KG的设计。一般来说，KG的输 是随机的。 到底该从哪些角度把握随机性等、才 使所设计出来的KG能够具有我们需要的安 全程度？

密钥序列生成器(KG)基本要求 人们就目前的想象和预见，对KG提出 了以下基本要求： 种子密钥k的变化量足够大，一般应 在2128以上； 般应不小于255； k具有均匀的n-元分布，即在一个周 期环上，某特定形式的n-长bit串与其求反， 两者出现的频数大抵相当(例如，均匀的游 程分布)；

密钥序列生成器(KG)基本要求 k不可由一个低级(比如，小于106级) 的LFSR产生，也不可与一个低级LFSR产生 的序列只有比率很小的相异项； 利用统计方法由k提取关于KG结构或 K的信息在计算上不可行； 混乱性. 即k的每一bit均与k的大多 数bit有关； 扩散性. 即k任一bit的改变要引起k 在全貌上的变化。

同步序列密码密钥流产生器 同步序列密码的关键是密钥流产生器。一般可将其看成一个参数为k的有限状态自动机，由一个输出符号集Z、一个状态集∑、两个函数φ和ψ以及一个初始状态σ0组成（如下图）。 状态转移函数φ:σi→σi+1，将当前状态σi变为一个新状态σi+1， 输出函数ψ:σi→zi，当前状态σi变为输出符号集中的一个元素zi。

作为有限状态自动机的密钥流生成器 k

作为有限状态自动机的密钥流生成器 这种密钥流生成器设计的关键在于找出适当的状态转移函数φ和输出函数ψ，使得输出序列z满足密钥流序列z应满足的几个条件，并且要求在设备上是节省的和容易实现的。 为了实现这一目标，必须采用非线性函数。

同步序列密码密钥流产生器 由于具有非线性的φ的有限状态自动机理论很不完善，相应的密钥流产生器的分析工作受到极大的限制。相反地，当采用线性的φ和非线性的ψ时，将能够进行深入的分析并可以得到好的生成器。为方便讨论，可将这类生成器分成驱动部分和非线性组合部分（如下图）。 驱动部分控制生成器的状态转移，并为非线性组合部分提供统计性能好的序列；而非线性组合部分要利用这些序列组合出满足要求的密钥流序列。

密钥流生成器的分解 驱动子 系统 非线性 组合子 k

目前最为流行和实用的密钥流产生器如图所示，其驱动部分是一个或多个线性反馈移位寄存器。 常见的两种密钥流产生器 目前最为流行和实用的密钥流产生器如图所示，其驱动部分是一个或多个线性反馈移位寄存器。 LFSR ……… F LFSR1 LFSR2 LFSRn ……

KG的一般结构 通常，人们总是把KG设计得具有一定 的结构特点，从而可以分析和论证其强度，以增加使用者的置信度。一般有以下模式： … … 驱动子系统 f （可线性） 非线性组合 子系统 F 种子密钥k … … k=k0k1k2 KG结构分解示意图

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

F的设计：两种典型的基本编码手段 F ( L , x ) 非线性组合生成器 一个非线性组合生成器的图示如下： N1-LFSR N2-LFSR Nt-LFSR  ) , ( 2 1 t x F L k F是一个t元非线性布尔函数，一般要求： 具有较高的非线性次数；是平衡的。

F的设计：两种典型的基本编码手段 一个有关的结果是： 若对一切i=1,2,,t，Ni-LFSR都是m- 序列生成器，且ij(Ni,Nj)=1，则 p(k)=(2N1-1)(2N2-1)(2Nt-1)， (k)=F*(N1,N2,,Nt)，这里F*是 把F在F2上的多项式表示作为整数环Z上的 多项式来计算而得的函数。

F的设计：两种典型的基本编码手段 非线性组合生成器的一个特殊情形是 所谓的非线性滤波生成器，或也称为前馈 网络，它的图示如下： N-LFSR  k

F的设计：两种典型的基本编码手段 钟控序列生成器 一个钟控序列生成器的图示如下： 时刻i be-1  b1 b0 L N x } { + i n x } { 时刻i N-LFSR作速度因子控制器 D=be-1 ·2e-1 ++ b1·2+ b0+c be-1  b1 b0 滑动 位 被钟控序列 此时刻输出指针位置 下一时刻输出指针位置 输出指针初始位 置n00随意选定 (缺省值为0） ni+1=ni+D

F的设计：两种典型的基本编码手段 一个特殊情形就是“停停走走”(Stop- and-Go)生成器，它的图示如下： 一个有关的结果是： n-LFSR1 m-LFSR2 时钟脉冲 k 一个有关的结果是： 若n-LFSR1与m-LFSR2都是m-序列生成器， 且n|m或2n-1为素数，则 p(k)=(2n-1)(2m-1)， (k)至少为[m,n](2(m,n)-1)。

2. 线性反馈移位寄存器 移位寄存器是序列密码产生密钥流的一个主要组成部分。GF(2)上一个n级反馈移位寄存器由n个二元存储器与一个反馈函数f(a1,a2,…,an)组成，如图所示。 …. 输出序列

GF(2)上的n级反馈移位寄存器 每一存储器称为移位寄存器的一级，在任一时刻，这些级的内容构成该反馈移位寄存器的状态，每一状态对应于GF(2)上的一个n维向量，共有2n种可能的状态。每一时刻的状态可用n长序列 a1,a2,…,an 或n维向量 (a1,a2,…,an) 表示，其中ai是第i级存储器的内容。

GF(2)上的n级反馈移位寄存器 初始状态由用户确定，当第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。

例：下图是一个3级反馈移位寄存器，其初始状态为(a1,a2,a3)=(1,0,1)，输出可由表2.2求出。 GF(2)上的n级反馈移位寄存器 例：下图是一个3级反馈移位寄存器，其初始状态为(a1,a2,a3)=(1,0,1)，输出可由表2.2求出。 输出序列 一个3级反馈移位寄存器

一个3级反馈移位寄存器的状态和输出 状态（a1,a2,a3) 输出 1 0 1 1 1 0 1 1 1 0 1 1 1

线性反馈移位寄存器 即输出序列为101110111011…，周期为4。 如果移位寄存器的反馈函数f(a1,a2,…,an)是a1，a2，…，an的线性函数，则称之为线性反馈移位寄存器LFSR（linear feedback shift register）。 此时f可写为 f(a1,a2,…,an)=cna1cn-1a2…c1an 其中常数ci=0或1，是模2加法。ci=0或1可用开关的断开和闭合来实现，如下图所示。

练习： 下图为3级反馈移位寄存器，其初始状态为 输出序列 试写出其输出序列，同时考虑如果初始状态不同，输出序 列是否相同，序列的周期是否相同？

GF(2)上的n级线性反馈移位寄存器 … 输出序列

线性反馈移位寄存器 输出序列{at}满足 an+t=cnatcn-1at+1…c1an+t-1 其中t为非负正整数。或者{an}： 线性反馈移位寄存器因其实现简单、速度快、有较为成熟的理论等优点而成为构造密钥流生成器的最重要的部件之一。

例： 一个5级线性反馈移位寄存器 例：下图是一个5级线性反馈移位寄存器，其初始状态为（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出输出序列为 1001101001000010101110110001111100110… 周期为31。 输出序列

练习： 下图为一个5级线性反馈移位寄存器，其初始状态为 输出序列 则其输出序列为？

线性反馈移位寄存器 在线性反馈移位寄存器中总是假定c1,c2,…,cn中至少有一个不为0，否则f(a1,a2,…,an)≡0，这样的话，在n个脉冲后状态必然是00…0，且这个状态必将一直持续下去。 若只有一个系数不为0，设仅有cj不为0，实际上是一种延迟装置。 一般对于n级线性反馈移位寄存器，总是假定cn=1。

线性反馈移位寄存器 线性反馈移位寄存器输出序列的性质完全由其反馈函数决定。n级线性反馈移位寄存器最多有2n个不同的状态。若其初始状态为0，则其状态恒为0。若其初始状态非0，则其后继状态不会为0。因此n级线性反馈移位寄存器的状态周期小于等于2n-1。其输出序列的周期与状态周期相等，也小于等于2n-1。 只要选择合适的反馈函数便可使序列的周期达到最大值2n-1，周期达到最大值的序列称为m序列。

3.线性移位寄存器的一元多项式表示 线性移位寄存器的输出序列 满足递推关系 (1) 当k>=1时成立。写出来看一看： …

线性移位寄存器的特征多项式 这种递推关系可以用一个一元高次多项式来表示： （*） 称这个多项式为LFSR的特征多项式。 在(1) 式中两边同时加上 得到： 令 据其在输出序列 中元素的左右位置， 左移一位相当于乘以2，则有：

注意： 线性反馈移位寄存器与特征多项式是一一对应的，如果知道了线性反馈移位寄存器的结构，可以写出它的特征多项式，同样可以根据特征多项式画出移位寄存器的结构。

设n级线性移位寄存器对应于递推关系(*)，由于ai∈GF(2) (i=1,2,…,n)，所以共有2n组初始状态，即有2n个递推序列，其中非恒零的有2n-1个，记2n-1个非零序列的全体为G(p(x))。

定义： 给定序列{ai}，幂级数 称为该序列的生成函数。 多项式表示中的部分概念 定义： 给定序列{ai}，幂级数 称为该序列的生成函数。

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

多项式表示中的部分概念 证明： 在等式 an+1=c1anc2an-1…cna1 an+2=c1an+1c2an …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)

多项式表示中的部分概念 移项整理得 (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。

多项式表示中的部分概念 定理2.2 p(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))。

多项式表示中的部分概念 反之，若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来产生。

多项式表示中的部分概念 定义： 设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)= (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。（证毕）

多项式表示中的部分概念 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,…

多项式表示中的部分概念 下面讨论特征多项式满足什么条件时，LFSR的输出序列为m序列。 定理2.4 设p(x)是n次不可约多项式，周期为m，序列{ai}∈G(p(x))，则{ai}的周期为m。

多项式表示中的部分概念 证明：设{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)

多项式表示中的部分概念 于是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。（证毕）

多项式表示中的部分概念 定理2.5 n级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序列。

多项式表示中的部分概念 例： f(x)=x4+x3+x2+x+1为GF(2)上的不可约多项式，这可由x,x+1,x2+x+1都不能整除f(x)得到。以f(x)为特征多项式的LFSR的输出序列可由 ak=ak-1ak-2ak-3ak-4(k≥4) 和给定的初始状态求出，设初始状态为0001，则输出序列为000110001100011…，周期为5，不是m序列。

多项式表示中的部分概念 1 输出 状态（ ） 周期为5，不是 m 序列

多项式表示中的部分概念 定义： 若n次不可约多项式p(x)的阶为2n-1，则称p(x)是n次本原多项式。 定理2.6 设{ai}∈G(p(x))，{ai}为m序列的充要条件是p(x)为本原多项式。

本原多项式：

多项式表示中的部分概念 证明： 若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)是本原多项式。（证毕）

多项式表示中的部分概念 {ai}为m序列的关键在于p(x)为本原多项式，n次本原多项式的个数为 其中 为欧拉函数。 其中 为欧拉函数。 已经证明，对于任意的正整数n，至少存在一个n次本原多项式。所以对于任意的n级LFSR，至少存在一种连接方式使其输出序列为m序列。

多项式表示中的部分概念 例： 设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-1ak-4(k≥4)

多项式表示中的部分概念 若初始状态为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序列。

例： 输出序列 (100110101111000) 按前面的性质有： 游程的总数为8，分别为 1，00，11，0，1，0，1111，0000。其中有一半的游程长度为2，长度为2的游程为四分之一，最后有一个长度为4的游程和一个长度为3的游程。

4. m序列的伪随机性 序列密码的安全性取决于密钥流的安全性，要求密钥流序列有好的随机性，以使密码分析者对它无法预测。也就是说，即使截获其中一段，也无法推测后面是什么。如果密钥流是周期的，要完全做到随机性是困难的。严格地说，这样的序列不可能做到随机，只能要求截获比周期短的一段时不会泄露更多信息，这样的序列称为伪随机序列。

随机序列的特性 为讨论序列的随机性，我们先讨论随机序列的一般特性。 设{ai}=(a1a2a3…)为0、1序列，例如00110111，其前两个数字是00，称为0的2游程；接着是11，是1的2游程；再下来是0的1游程和1的3游程。

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

Golomb对伪随机周期序列提出了应满足的如下3个随机性公设： ① 在序列的一个周期内，0与1的个数相差至多为1。 随机序列的特性 Golomb对伪随机周期序列提出了应满足的如下3个随机性公设： ① 在序列的一个周期内，0与1的个数相差至多为1。

随机序列的特性 ② 在序列的一个周期内，长为i的游程占游程总数的1/2i (i=1,2,…)，且在等长的游程中0的游程个数和1的游程个数相等。 ③ 异相自相关函数是一个常数。 公设①说明{ai}中0与1出现的概率基本上相同; ②说明0与1在序列中每一位置上出现的概率相同; ③意味着通过对序列与其平移后的序列做比较，不能给出其他任何信息。

伪随机序列应满足的条件 从密码系统的角度看，一个伪随机序列还应满足下面的条件： ① {ai}的周期相当大。

m-序列概念 称周期达到最大值2n-1的n-LFSR（输 出）序列为（n级）m-序列。 显然，若某n-LFSR产生一个m-序列， 则其状态图除了单点(000)构成的圈外， 就是由F2n\{(000)}中所有点排列而成的 一个大圈，因而其任何非全零的输出序列 均是m-序列，故称之为m-序列生成器。 例.4-LFSR[1,0,0,1]。

m序列的特性 下一定理说明，m序列满足Golomb的3个随机性公设。 定理2.7 GF(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序列的特性 ③ {ai}的自相关函数为

周期序列的自相关函数计算 周期p序列a=a0a1a2的自相关函数定 义如下： 自相关函数计算. 对给定的周期序列a， ①找出a的周期段：a0a1a2 ap-1 ②计算：

周期序列的自相关函数计算 对位相乘后再相加，即得pCa(t)。 例.对a=(10011101101)，计算Ca(4)。 (-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的线性递归关系)

m序列的特性 证明： ① 在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序列的特性 由于寄存器中不会出现全0状态，所以不会出现0的n游程，但必有一个1的n游程，而且1的游程不会更大，因为若出现1的n+1游程，就必然有两个相邻的全1状态，但这是不可能的。这就证明了1的n游程必然出现在如下的串中： 当这n+2位通过移位寄存器时，便依次产生以下状态：

由于 ， 这两个状态只能各出现一次，所以不会有1的n-1游程。 于是在一个周期内，总游程数为 m序列的特性 由于 ， 这两个状态只能各出现一次，所以不会有1的n-1游程。 于是在一个周期内，总游程数为

m序列的特性 ③ {ai}是周期为2n-1的m序列，对于任一正整数τ(0<τ<2n-1)，{ai}+{ai+τ}在一个周期内为0的位的数目正好是序列{ai}和{ai+τ}对应位相同的位的数目。 设序列{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+τ)

m序列的特性 令bj=ajaj+τ，由递推序列{ai}可推得递推序列{bi}，{bi}满足 bh+n=c1bh+n-1c2bh+n-2…cnbh {bi}也是m序列。为了计算R(τ)，只要用{bi}在一个周期中0的个数减去1的个数，再除以2n-1，即 （证毕）

m序列的特性 一个n-LFSR（给定结构常数）具有“由 一个短的种子产生一个长的序列”的功能： 以短的种子作为初态，产生的输出序列 可以任意长！ 上述表明，任一n-LFSR都初步具有作为 一个KG的资格；但从作为KG的效用来讲，自 然更希望所使用的n-LFSR进一步是m-序列生 成器。

n-FSR的结构常数+初态 n-FSR序列 线性反馈移位寄存器（LFSR）的综合 前面我们讲过，m-序列是满足Golomb 三条随机性公设的PN序列，但其不可以作 为一个序列密码的密钥序列。因为：对m- 序列，知道其少量的比特以后是可以预测 的！现在就讲怎么样仅凭已知的少量比特 来找出整个序列所满足的线性递推关系。 一般地，把有关反馈移位寄存器的求 解问题，从正反两个方面分为分析与综合： n-FSR的结构常数+初态 n-FSR序列 分析 综合

线性反馈移位寄存器（LFSR）的综合 线性反馈移位寄存器的综合问题就在 于根据序列的少量比特求出整个序列所满 足的线性递推关系。一个自然的想法就是：先假定线性递推关系，然后由序列的各项应该适合之而导出线性方程组；但这样的方法有其不易行之处在于： 不容易确定所适用的LFSR的级数n， 从而就不能导致恰当规模的线性方程组； 当上述的n很大时，求解相应规模的 线性方程组也很困难。

Berlekamp-Massey迭代算法，简称B- 线性反馈移位寄存器（LFSR）的综合 事实上，对于线性反馈移位寄存器的 综合问题已经出现了著名的解法： Berlekamp-Massey迭代算法，简称B- M算法。

B-M算法描述 当dn=1时，若Ln=0,则取fn+1(x)=xn+1+1,Ln+1=n+1； Input：SN=a0a1a2aN-1 Step1：置f0(x)=1，L0=0（初值） Step2：设<fi(x),Li>，i=0,1,2,…,n（0n<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-1 Output：<fN(x),LN>

B-M算法举例 输入：S8=10101111 输出：<1+x3+x4,4>

有关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。

有关B-M算法的结果 考虑问题：  S6=101011f6(x)=1+x2+x3  如何解释？ ——其实，对，由于L6=4，故4-LFSR [0,1,1,0]生成S6；对，由于L1+N=1，故1- LFSR[0]生成S2（规定：f(x)=1产生全零序 列）。

有关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。 ⑵ 。

应用B-M算法举例 求产生序列a的最低次多项式，这里 ⑴ a=111001，⑵ a=(111001) 解： 可见答案为：⑴ 1+x2+x3；⑵ 1+x2+x4。

应用B-M算法举例 注. 对于⑵中周期序列a，其实以前 介绍过一种求生成它的最低次联接多项式 的方法： 应用展转相除法可以求出最大公因式 于是， 从而可知生成序列a的最短LFSR的联接多项式为1+x2+x4。

5.M-序列的特性 在一个一般n-FSR的状态图中，至少含 有一个圈，且从任意状态出发进动若干拍 后必定进入某一个圈！这时得到的输出序 列虽不必是周期序列，但去掉其前若干项 后即得到周期序列，也就是说这样的序列 为终归周期序列。 若一n-FSR的输出序列的周期达到最大 值2n，则称此序列为(n级)M-序列。

M-序列的概念 显然，如果一个n-FSR有一个输出序列 为M-序列，则其状态图是一个包含F2n中所 有2n个点的大圈，从而这个n-FSR由任意初 态产生的序列都是M-序列（一共有2n个且相 互平移等价！），这个n-FSR本身也就被称 为M-序列生成器，而相应的反馈函数被称 为M-序列反馈函数。 例.反馈函数为 的3-FSR。

一个关于与M-序列反馈函数的结果 有关布尔函数的一些知识： 一个n元布尔函数是指下述形式的映射 它既可以用逻辑关系式表达，也可以用真值 表来表示，还可以表为多元多项式。 上述三者之间的互化方法： 逻辑关系式 多元多项式 真值表（容易）

一个关于与M-序列反馈函数的结果 逻辑关系式 多元多项式： 另外，xt=x (t>1)。因此，在布尔函数f(x1, x2,…,xn)的多项式表示中，高次项的形式只 有是 。 重量：w(f)是指在布尔函数f的真值表 中，函数值列里1的个数。 真值表 多元多项式（举例）

一个关于与M-序列反馈函数的结果 布尔函数f(x1,x2,…,xn)是n级M-序列 反馈函数的必要条件是: f(x1,x2,…,xn)=x1+f0(x2,x3,…,xn) ⑵ ⑴中n-1元布尔函数f0(x2,x3,…,xn)

一个关于与M-序列反馈函数的结果 还必须满足： f0的重量w(f0)是奇数； 在f0的任一表达中，x2,x3,…,xn都出现； 在f0的多项式表示中，项数为奇数、常数项1必出现、线性项x2,x3,…,xn不能全出现、且n-1次项x2x3xn一定出现。

M-序列的特性 n级M-序列反馈函数的个为 。 M-序列的统计特性. 在n级M-序列的 一个周期圈中， ⑴ 0与1的数目均为2n-1； ⑵ 长为k的0-游程与1-游程的数目均 为

线性复杂度概念 定义. 能够产生（有限长或周期）序 列a的最短LFSR的级数称为a的线性复杂度， 记为(a)；约定：(0)=0。 若对序列a应用B-M算法产生的输出为 <f(x),L>，则(a)=L。 研讨： 若a为n-级m-序列，则(a)= 。

M-序列的特性 M-序列的自相关特性. 设n级M-序列 a的反馈函数 f(x1,x2,…,xn)=x1+f0(x2,x3,…,xn) 那么， ⑴ Ca(0)=1 ⑵ Ca(t)=0，0<tn-1 ⑶ Ca(n)=1-w(f0)/2n-2 ≠0 对于n(n≥3)级M-序列a，

6. m序列密码的破译 上面说过，有限域上的二元加法序列密码是目前最为常用的序列密码体制，设滚动密钥生成器是线性反馈移位寄存器，产生的密钥是序列。又设和是序列中两个连续的长向量，其中

设序列{ai}满足线性递推关系： 可表示为 m序列密码的破译 设序列{ai}满足线性递推关系： 可表示为

或Sh+1=M·Sh，其中 又设敌手知道一段长为2n的明密文对，即已知

于是可求出一段长为2n的密钥序列 其中 ,由此可推出线性反馈移位寄存器连续的n+1个状态： m序列密码的破译 于是可求出一段长为2n的密钥序列 其中 ,由此可推出线性反馈移位寄存器连续的n+1个状态：

m序列密码的破译 做矩阵 而 若X可逆，则

m序列密码的破译 下面证明X的确是可逆的。 因为X是由S1,S2,…,Sn作为列向量，要证X可逆，只要证明这n个向量线性无关。 由序列递推关系： 可推出向量的递推关系：

m序列密码的破译 设m(m≤n+1)是使S1,S2,…,Sm线性相关的最小整数，即存在不全为0的系数l1,l2,…,lm，其中不妨设l1=1，使得 即 对于任一整数i有

由此又推出密钥流的递推关系： 即密钥流的级数小于m。若m≤n，则得出密钥流的级数小于n，矛盾。所以m=n+1，从而矩阵X必是可逆的。

m序列密码的破译 例： 设敌手得到密文串101101011110010和相应的明文串011001111111001，因此可计算出相应的密钥流为110100100001011。进一步假定敌手还知道密钥流是使用5级线性反馈移位寄存器产生的，那么敌手可分别用密文串中的前10个比特和明文串中的前10个比特建立如下方程

m序列密码的破译 即 而

m序列密码的破译 从而得到 所以 密钥流的递推关系为

已介绍密钥流生成器可分解为驱动子系统和非线性组合子系统，如图所示。 7. 非线性序列 已介绍密钥流生成器可分解为驱动子系统和非线性组合子系统，如图所示。 驱动子 系统 非线性 组合子

驱动子系统常用一个或多个线性反馈移位寄 存器来实现，非线性组合子系统用非线性组合函数F来实现，如图所示。本节介绍第2部分非线性组合子系统。 7. 非线性序列 驱动子系统常用一个或多个线性反馈移位寄 存器来实现，非线性组合子系统用非线性组合函数F来实现，如图所示。本节介绍第2部分非线性组合子系统。 LFSR F LFSR1 LFSRn 常见的两种密钥流产生器

非线性序列 为了使密钥流生成器输出的二元序列尽可能复杂，应保证其周期尽可能大、线性复杂度和不可预测性尽可能高，因此常使用多个LFSR来构造二元序列，称每个LFSR的输出序列为驱动序列，显然密钥流生成器输出序列的周期不大于各驱动序列周期的乘积，因此，提高输出序列的线性复杂度应从极大化其周期开始。

非线性序列 二元序列的线性复杂度指生成该序列的最短LFSR的级数，最短LFSR的特征多项式称为二元序列的极小特征多项式。

Geffe序列生成器由3个LFSR组成，其中LFSR2作为控制生成器使用，如图所示。 输出 Geffe序列生成器图

Geffe序列生成器 当LFSR2输出1时，LFSR2与LFSR1相连接；当LFSR2输出0时，LFSR2与LFSR3相连接。 若设LFSRi的输出序列为{a(i)k} (i=1,2,3)，则输出序列{bk}可以表示为

多路复合器表示的Geffe序列生成器 LFSR1 多路复合器 选择控制

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

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

7.2 J-K触发器 J-K触发器如下图所示，它的两个输入端分别用J和K表示，其输出ck不仅依赖于输入，还依赖于前一个输出位ck-1，即 其中x1和x2分别是J和K端的输入。由此可得J-K触发器的真值表，如表。

J-K触发器 R J K J-K触发器真值表 J K 1

利用J-K触发器的非线性序列生成器见图。 LFSR1 LFSR2 J K

利用J-K触发器组成非线性序列生产器 令驱动序列{ak}和{bk}分别为m级和n级m序列，则有 如果令c-1=0，则输出序列的最初3项为 当m与n互素且a0+b0=1时，序列{ck}的周期为(2m-1)(2n-1)。

例： 令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+bk+1)ck-1+ak可得 因此，如果知道{ck}中相邻位的值ck-1和ck，就可以推断出ak和bk中的一个。而一旦知道足够多的这类信息，就可通过密码分析的方法得到序列{ak}和{bk}。为了克服上述缺点，Pless提出了由多个J-K触发器序列驱动的多路复合序列方案，称为Pless生成器。

7.3 Pless生成器 Pless生成器由8个LFSR、4个J-K触发器和1个循环计数器构成，由循环计数器进行选通控制，如下图所示。假定在时刻t输出第t(mod 4)个单元，则输出序列为 a0b1c2d3a4b5d6

Pless生成器 LFSR1 LFSR2 J K LFSR7 LFSR8 LFSR3 LFSR4 LFSR5 LFSR6 3 2 1

钟控序列最基本的模型是用一个LFSR控制另外一个LFSR的移位时钟脉冲，如图所示。 7.4 钟控序列生成器 钟控序列最基本的模型是用一个LFSR控制另外一个LFSR的移位时钟脉冲，如图所示。 LFSR1 LFSR2 时钟脉冲 最简单的钟控序列生成器

钟控序列生成器 假设LFSR1和LFSR2分别输出序列{ak}和{bk}，其周期分别为p1和p2。当LFSR1输出1时，移位时钟脉冲通过与门使LFSR2进行一次移位，从而生成下一位。当LFSR1输出0时，移位时钟脉冲无法通过与门影响LFSR2。因此LFSR2重复输出前一位。假设钟控序列{ck}的周期为p，可得如下关系： 其中 。

钟控序列生成器 又设{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)，极小特征多项式为 。

钟控序列生成器 例： 设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的变化情况如下：

钟控序列生成器 {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+x14x21，其线性复杂度为3·（23-1）=21，图是其线性等价生成器。 钟控序列生成器 {ck}的极小特征多项式为1+x14x21，其线性复杂度为3·（23-1）=21，图是其线性等价生成器。 一个钟控序列的线性等价生成器

实际应用中，可以用上述最基本的钟控序列生成器构造复杂的模型，具体构造方式可参阅有关文献。

序列密码的设计原则 设计一个性能良好的序列密码是一项十分困难的任务。最基本的设计原则是“密钥流生成器的不可预测性”，它可分解为下述基本原则： ① 长周期。 ② 高线性复杂度。 ③ 统计性能良好。 ④ 足够的“混乱”。 ⑤ 足够的“扩散”。 ⑥ 抵抗不同形式的攻击。

8. 欧洲NESSIE工程及其征集的Lili-128 候选算法 自2000年1月至2002年12月，欧洲委 员会投资33亿欧元支持其信息社会技术 （IST）规划中一项名为NESSIE(New Eu- ropean Schemes for Signatures,Inte- grity,and Encryption)的工程。该工程 也象DES、RIPE规划和AES的选择过程一样， 采用先征集后评估的办法，但其征集范围 要比NIST的AES广泛得多。

欧洲NESSIE工程介绍 信息社会不仅需要分组密码标准来提 供机密性服务，而且也需要其它密码标准 来提供认证和完整性等服务。因此，NESS 如： 分组（块）密码； 序列（流）密码； 消息认证码； 伪随机函数族； 数字签名和Hash函数； 非对称加密方案； 非对称识别方案。

欧洲NESSIE工程介绍 此外，NESSIE工程将考虑候选密码标准所能应用的具体环境，甚至也征集评测这些侯选密码标准的测试方法(如统计测试)。 NESSIE工程的主要目标就是通过公 开征集进行公开的、透明的测试评价，提 出一套强的密码标准，这些标准包括分组 密码，序列密码，杂凑函数，消息认证码， 数字签名方案和公钥加密方案。该工程将 发展一种密码体制的评估方法（包括安全 性和性能评价）和支持评估的一个软件工 具箱。

欧洲NESSIE工程介绍 21世纪欧洲密码标准产生： 1993年2月27日，以征集对世纪欧洲新的密码算 选结果。除了从参评的42个算法方案中评出了12个 方案外，还选取了已有标准中的5个方案（见打“＊” 的）。NESSIE工程委员会公布的终选结果如下页。 在整个评测过程中，上述方案均未发现任何缺 陷。上述算法中的10个对称算法允许免费使用。非 对称方案RSA—KEM、RSA—PSS和SFLASH也可以在公开 领域内使用。需要特别加以说明的是由于安全性审 查有些过于严密，所有6个参选的同步序列密码算 法方案无一进入终选。

欧洲NESSIE工程介绍 

欧洲NESSIE工程介绍 有关NESSIE工程的其它事项可通过 NESSIE的主页http://cryptonessie.org 去追索。

欧洲NESSIE工程介绍 以下介绍一下的是关于序列密码的情况。NESSIE收到的5个候选同步序列密码如下表： 算法名称 整体结构 设计特点 国家（组织） 整体结构 设计特点 Leviathan 美国 是一种二进制树结构 密钥流由一组二进制的数结构定义 Lili-128 澳大利亚 钟控结构 由钟控子系统与数据生成子系统组成，使用了两个LFSR与两个函数 BMGL 瑞典 密钥反馈模式(类似于OFB) 基于复杂性理论，具有可证明安全性，核心是Rijdael分组密码 SOBER-t32/t16 非线性滤波结构 使用带有密钥的非线性滤波函数，输出32/16比特分组 SNOW 由一个LFSR和一个有限状态机(FSM)组成 是一个面向32-比特字的序列密码，基于经典的求和发生器的观点

候选序列密码—Lili-128算法 限于同学们的知识和数学能力，在此 仅简要介绍一下Lili-128算法。 生成器，它使用两个LFSR和两个非线性函 数来产生伪随机的二元密钥流序列。基于 所完成的功能， Lili-128密钥流生成器 的部件可分成两个子系统：钟控子系统和 数据生成子系统。如下页图所示：

候选序列密码—Lili-128算法 LFSRd LFSRc fd fc ··· k=2 n=10 c(t) z(t) 钟控子系统 数据生成子系统 钟控

候选序列密码—Lili-128算法 钟控子系统 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算法 数据生成子系统 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算法 0,0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,0,0,0,0,1,1,0,0,1,1,1,1,0,0, 1,1,0,0,0,0,1,1,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,1,1,0,0,0,0,1,1, 0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,1,1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0, 1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,1, 0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0, 0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0, 0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0, 0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1, 1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0, 0,0,1,1,0,0,1,1,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,0,0,1,1,0,0,1,1, 1,1,0,0,1,1,0,0,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,1,1,0,0,1,1,0,0, 0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,0,0,0,0,1,1, 1,1,0,0,0,0,1,1,1,1,0,0,0,0,1,1,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0, 0,0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,0,0,1,1,1,1,0,0,1,1,0,0,0,0,1,1, 1,1,0,0,0,0,1,1,0,0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,0,0,1,1,1,1,0,0, 0,1,0,1,0,1,0,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1, 1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,0,1,0,1,0,1,0, 0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,1,1,0,1,0,0,1,0,1, 1,0,1,0,0,1,0,1,1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,0, 0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,1, 1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,1,0,1,0, 0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1, 1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0, 0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1, 1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,0,1,1,0, 0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1, 1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0

9.习题 1. 3级线性反馈移位寄存器在c3=1时可有4种线性反馈函数，设其初始状态为(a1,a2,a3)=(1,0,1)，求各线性反馈函数的输出序列及周期。 2. 设n级线性反馈移位寄存器的特征多项式为p(x)，初始状态为(a1,a2,…,an-1,an)= (00…01)，证明输出序列的周期等于p(x)的阶。

习题 3. 设n=4, ，初始状态为(a1,a2,a3,a4)=(1,1,0,1)，求此非线性反馈移位寄存器的输出序列及周期。

习题 4. 已知序列密码的密文串1010110110和相应的明文串0100010001，而且还已知密钥流是使用3级线性反馈移位寄存器产生的，试破译该密码系统。 5. 设J-K触发器中{ak}和{bk}分别为3级和4级m序列，且 {ak}=11101001110100… {bk}=001011011011000001011011011000… 求输出序列{ck}及周期。

习题 6. 设基本钟控序列产生器中{ak}和{bk}分别为2级和3级m序列，且 {ak}=101101… {bk}=10011011001101…求输出序列{ck}及周期。

习题 7.给定两个逻辑函数： 判断Y1和Y2是否为平衡逻辑函数，它们是5级M- 序列反馈函数吗？

习题

THE END！