1、第2章 序列密码第第2 2章章 序列密码序列密码2.1 序列密码原理序列密码原理2.2 线性反馈移位寄存器线性反馈移位寄存器2.3 非线性序列非线性序列2.4 利用线性反馈移位寄存器的密码反馈利用线性反馈移位寄存器的密码反馈习题习题2实践练习实践练习2第2章 序列密码 把明文加密成密文，有两种方式，一种是分组(块)加密，一种是序列(流)加密。采用序列加密时，明文不进行分段，明文序列被源源不断地送入加密器，在密钥作用下进行加密运算，产生的密文序列源源不断地被输出来，实时地完成加密过程。本章主要讨论伪随机序列的产生和特点，因为它不仅是序列加密密钥的来源，而且也是现代密码体制中不可缺少的关键数据。第
2、2章 序列密码2.1序列密码原理序列密码原理2.1.1序列加、解密原理序列加、解密原理 一个序列流加密的保密通信系统的流程如图2.1所示。明文消息序列为m=m1m2m3密钥序列为k=k1k2k3加、解密都是逐位顺序进行的：ci=Ek(mi)；mi=Dk(ci)(2-1)得到的密文序列为c=c1c2c3 第2章 序列密码图2.1序列流加密的保密通信系统流程图第2章 序列密码2.1.2安全性讨论安全性讨论 从传统密码算法得知，不论单表加密、多表加密，或是置换还是其他方式，密文之所以“密”，原因在于密钥使明文变“乱”了，这种乱就是随机性。密钥的随机性掩盖了明文的可理解性。Shannon信息论已经证明
3、1，只有“一字一密”系统才是不可破译的、完全安全的保密系统。所谓一字一密，指密钥序列是无限长的真正的随机序列，密钥使每位密文都变得无规律可循。对于这样的系统，破译者完全无法从已有的密文中，或明、密文对照中找到规律，不能为未知的密文破译提供任何有价值的信息。第2章 序列密码 然而，这样的保密系统是不可行的。且不说真正的随机序列如何获得，单就如何把无限长的密钥安全地传给合法收信人就是个难题。如果密钥和密文一样长，用秘密信道传递密钥还不如直接传递明文好了！保密通信的初衷就是希望在公开信道中安全通信，因为秘密信道实在昂贵而又难得。有实际意义的密钥应当是用软、硬件可以再生的“伪”随机序列，伪就伪在它并不
4、真正随机，而是有规律的，这个规律就是周期性。只不过周期很长，在有限时段内看不出规律罢了。生成这样的伪随机序列，只需要很短的“初始密钥”(或曰种子)，只要通信双方在协议中约定好伪随机序列的产生方法和初始值，即具有了共同的密钥。图2.2为用伪随机序列作为密钥的序列流加密系统。第2章 序列密码图2.2 用伪随机序列作为密钥的序列流加密系统 第2章 序列密码2.1.3序列密码对密钥流的要求序列密码对密钥流的要求6 1.极大的周期极大的周期 现代密码机数据率高达108bit/s。如果使用10年内不会重复的密钥流，密钥的周期应不少于31016或255。2.良好的统计特性良好的统计特性 Golomb对随机序
5、列的统计性质提出了三条要求：(1)在序列的一个周期内，0和1的个数最多相差1。(2)在一个周期圈内，长度为1的游程数占1/2，长度为2的游程数占1/4长度为i的游程数占1/2i，且在等长的游程中，0游程和1游程各半(游程指连0或连1的段落)。(3)自相关函数为二值函数：第2章 序列密码时当时当0100)(xR 伪随机序列的自相关函数定义如下：10)1()1(1)(10T.TRkkaTkaa(2-2)式中，T为周期；为预先指定的一个位移值。相关函数定义为序列与它的移位序列逐位相比较，相同则为1，不同则得-1，然后相加起来求平均。因此，Ra()也等于两序列逐位相比较时，取值相同的位数与取值不同的位
6、数之差再除以T：TdnR)(第2章 序列密码 对于上式，当0时Ra()0，表明通过ai与ai+比较，无法得到关于ai的实质性信息(比如周期)；而当=0时，Ra(0)=1，表明自身归一。3.足够的复杂度足够的复杂度 用较短的“种子”就能生成周期较长的伪随机密钥，那么破译者也可以这么做，他只需掌握(破译或猜出)这个种子即可。因为产生伪随机序列的算法是公开的(至少是不难获得的)。因此，为了系统的安全，仅仅周期长是不够的，还要求密钥序列有足够的复杂度。序列的复杂度指序列有足够繁多的变化花样。它的具体定义后面会讨论。现在要说明的是，伪随机序列生成器输出的虽第2章 序列密码然不是真正的随机序列，但是在计算
7、资源受到一定限制(速度、内存有限，机时有限)的条件下，如果要想区别这个输出序列与相同长度的真随机序列，是不可行的；或者从理论上可以证明，二者的计算工作量随序列长度n变化的依赖关系以比多项式或更高(如幂指数函数)的方式而增大，因而可以认为二者是不可区分的。这样的伪随机序列就被认为具有足够的复杂性。说到底，世上没有绝对不可破的密码，比如通过穷搜索总能将其破译，然而如果穷搜索不可能在有限时间内完成，而且又不存在比穷搜索更好的破译方法，则可以认为这个密码系统是安全的。第2章 序列密码2.2线性反馈移位寄存器线性反馈移位寄存器3 20世纪50年代以后，数字电子技术大力发展，使得伪随机序列可以方便地利用移
8、位寄存器产生，加上有效的数学工具(域理论和谱分析)，使序列密码迅速走向成熟。2.2.1反馈移位寄存器反馈移位寄存器(FeedbackShiftRegister)n位二值存储器共有2n种状态，每个状态都代表一个长度为n的序列(a0a1a2an-1)。在主时钟脉冲作用下，寄存器各位共同右移一位，a0输出，而an-1来自原先状态所决定的一个反馈值f(a0a1a2an-1)。f(a0a1a2an-1)是预先设定好的一个n元布尔函数，于是有关系：第2章 序列密码)()()()1()2210()()1(11011ta,ta,taftan,.,itatannii特别是当 f(a0a1a2an-1)为线性函数
9、时，有(2-5)这里,各ciGF(2)，即:表示该示该位有 1 表示该示该位无 0 ic(2-6)这个系统称为线性反馈移位寄存器(LFSR)，如图2.3所示。第2章 序列密码图2.3反馈移位寄存器 第2章 序列密码 如图2.4所示的三级线性反馈移位电路，任意给定非零初态就能输出一个周期为T=7的伪随机序列。图2.4中，左右两电路都是三级线性反馈移位器，区别仅在于抽头的位置不同。当初态为001时，左右两电路寄存器状态的变化如表2.1所示。它们分别不断循环地输出1001011和1001110。当初态为101时，可得到周期为4的伪随机序列1011的循环，它的电路如图2.5所示。第2章 序列密码图2.
10、4 三级移位寄存器构成的m序列发生器 第2章 序列密码表表2.1 三级三级m序列的输出序列的输出 第2章 序列密码图2.5非线性反馈三级移位寄存器第2章 序列密码2.2.2m序列序列1.特征多项式特征多项式 为了利用多项式的代数理论来研究线性反馈移位寄存器(LFSR)产生伪随机序列的规律，定义特征多项式：iniinnnnxcxcxcxcxcxp0112211)(2-7)用它来描述线性反馈移位寄存器的构造：各xi只是为了区分寄存器的位序号，而各ci值表示该位有无反馈，有则为1，无则为0。第2章 序列密码 为什么会是一个n次多项式呢？因为LFSR各位的输入都来自它前一位的输出，xn-1位的输入来自
11、xn位的输出，而xn位的寄存器是不存在的，代替xn位的是反馈回来的数据，反馈关系可表达为(2-8)将等号左面的xn移到等号右面，便是特征多项式p(x)。图2.4给出的两个三级线性反馈移位电路的特征多项式分别为 p(x)=x3+x+1 和 p(x)=x3+x2+1它们对应的本原元素满足方程p()=0，在模2运算下等价于：112211nnnxcxcxcx第2章 序列密码此即电路抽头位置所表示的反馈关系。当然还可以存在其他形式的三级线性反馈移位电路，如：p(x)=x3+1 和 p(x)=x3+x2+x+1 但它们产生的分别是周期为T=3和T=4的伪随机序列，其电路如图2.6所示。写出一个特征多项式p
12、n(x),就能构造出一个线性移位寄存器，于是就对应着一个伪随机序列ai，因而我们常用aiSpn(x)表示ai属于由pn(x)所描述的非零伪随机序列。这里的n表示n级反馈移位寄存器。1 和 1233第2章 序列密码图2.6三级移位寄存器构成的m序列发生器第2章 序列密码 2.m序列序列 三级的线性反馈移位寄存电路所产生的伪随机序列，其周期最长只能为7。这是因为n=3位的寄存器全部状态共2n=8个，除全零状态之外，最多只能在2n-1=7个状态间循环。所以，n级的线性反馈移位寄存电路所产生的伪随机序列，其周期T不会大于2n-1。定义定义：周期达到2n-1的n级线性反馈移位寄存器的输出序列，称为m序列
13、。定理定理：ai为m序列的充要条件是pn(x)为本原多项式。事实上，pn(x)是本原多项式，就表明pn(x)的根是GF(2n)域的本原元素，而本原元素的循环阶是T=2n-1，达到了最大的循环周期。第2章 序列密码 因此，要想知道n级线性反馈移位寄存器能产生多少种不同的m序列，只要看GF(2n)域中n级的本原多项式有多少个即可。根据有限域理论，计算公式是：nnn)12()(2-9)式中，(T)为欧拉数，代表与T互素的同余类的个数(凡是除以T后余数相同的整数为一个同余类)。(T)的计算公式是：kkkpppTTpppTTTT212121为合数：当 )11()11)(11(为素数当 1)(2-10)第
14、2章 序列密码例如，对于n=3的LFSR，有 T=23-1=7；(7)=7-1=6；表明存在两个3次本原多项式，分别为 p(x)=x3+x+1 和 p(x)=x3+x2+1分别产生两种不同抽头位置的循环移位电路。又如，n=4时，T=24-1=15；236n；842)511()311(15(15)248n第2章 序列密码两个4次本原多项式是：p(x)=x4+x+1和p(x)=x4+x3+1表2.2中列出了n24以内的线性反馈移位寄存器的周期和m序列的个数。第2章 序列密码表表2.2n=24以内的线性反馈移位寄存器的以内的线性反馈移位寄存器的周期和周期和m序列的个数序列的个数 第2章 序列密码 【
15、例例1】构造一个n=5的LFSR，并计算所产生m序列的周期和个数。解解：n=5级的线性反馈移位寄存器所产生的m序列的周期为 T=25-1=31由 (31)=31-1=30；知共有6种不同的五级m序列。不妨查本原多项式表，找到n=5的一个本原多项式，其八进制表达形式为 (45)8=(100101)2即 p(x)=x5+x2+1对应的电路如图2.7所示。6530n第2章 序列密码图2.7 n=5的移位寄存器构成的m序列发生器 第2章 序列密码2.2.3线性反馈移位寄存器的软件实现线性反馈移位寄存器的软件实现 m序列也可以用计算机程序产生。首先根据所需伪随机序列周期来设计移位寄存器的级数n，然后从本
16、原多项式表中选取pn(x)。下面是一些本原多项式的非零系数：(3,1,0)，(4,1,0)，(5,2,0)，(6,1,0)，(7,3,0)，(9,4,0)，(10,3,0)，(11,2,0)，(15,1,0)，(17,3,0)，(17,6,0)，(18,7,0)，(20,3,0)，(21,2,0)，(23,5,0)，(28,3,0)，(29,2,0)，(31,3,0)，(32,7,6,2,0)，(32.7,5,3,2,1,0)，(33,16,4,1,0)，以 pn(x)=x32+x7+x5+x3+x2+x+1为例，根据特征多项式不难画出一个32位的线性反馈移位寄存器电路示意图，如图2.8所示。
17、第2章 序列密码图2.8 pn(x)=x32+x7+x5+x3+x2+x+1的电路第2章 序列密码C语言源程序为 Int LFSR Staticunsignedlong Shiftregister=1;/*Anythingbut0.*/Shiftregister=(shiftregister7)(shiftregister5)(shiftregister3)(shiftregister2)(shiftregister1)shiftregister)&0 x00000001)1);returnshiftregister&0 x00000001;第2章 序列密码2.2.4m序列的统计性质序列的统计
18、性质 m序列的统计性质如下：(1)在一个周期内0和1的个数至多相差1位。(2)游程特征基本符合Golomb要求：任一循环周期中含2n-1个1和2n-1-1个0。这是因为序列的排布完全取决于寄存器中状态的变化，每当a0移出一位成为序列中新加入的一个码元后，寄存器上一位又移入a0，可见a0有过些什么值，输出序列就出现些什么值。n位寄存器共2n种不同的状态，a0位为1与为0各占2n种的一半，即2n-1次，所以m序列的任一循环周期中1出现2n-1次；由于全0状态不出现，因而0出现2n-1-1次。第2章 序列密码 游程最长为n，有一个长为n的1游程，却没有长为n的0游程。这是因为只有一个全1状态，而没有
19、全0状态。没有长为n-1的1游程，却有一个长为n-1的0游程。这是因为已经有了一个全1状态，它的前一个状态是11110，后一个状态是01111，二者虽都是n-1个1的状态，却不能产生n-1的1游程，因为这三个状态进入系列后产生的是同一个长为n的1游程。而这两个n-1个1的状态既然已经出现，同一周期中就不会再出现第三个n-1个1的状态了。长为n-1的0游程却是可以存在的，这是由于不存在全0状态，所以n-1个0的状态10000和00001都可以存在，它们产生的是同一个长为n-1的0游程。第2章 序列密码 长为rn-2的1游程和0游程各为2n-r-2个。这是因为这种游程意味着状态中存在形如01111
20、0(r个1)的串，这种游程的数目就等于状态中其余n-r-2位的状态数目，此即2n-r-2。每一循环中共有2n-2个1游程和2n-2个0游程(长度大于1的)。这是因为：2212221nnrrn (3)周期为2n-1的m序列，其异相自相关函数等于 。121n第2章 序列密码 证明：由前知R()等于ai和ai+两序列对应位置上有相同值的个数减去不同值的个数，再除以周期T。当ai与ai+逐位相加后，得到的必然仍为SPn(x)中的一个序列bj。bj中的0代表ai和ai+对应位相同的情况，bj中的1代表ai和ai+中对应位不同的情况，而由性质知道，0的个数比1的个数少一个，故分子是-1，分母是周期2n-1
21、。(4)n级线性移位寄存器可以产生(n)种不同结构的m序列；每给定一种结构，还可以选择2n-1个不同的初始状态，因而所能产生密钥的总数是(n)(2n-1)个。第2章 序列密码2.2.5线性反馈移位寄存器输出序列的复杂度线性反馈移位寄存器输出序列的复杂度 能用线性反馈移位寄存器来产生有限长度的任意序列ai吗？设ai=a0a1a2aN-1，序列长度为N。显然，长度为N的自然码中肯定包含它，因此N级LFSR肯定可以产生它，只要取反馈函数 f(x)=1+xN，初始状态是什么自然码就产生什么序列。然而这并不是最小的LFSR。任意给定一个长度为N的伪随机序列ai，如何构造一个尽可能短的LFSR来产生它？可
22、以分三种情况来讨论：(1)存在一个n，恰能使N=2n-1，并且序列ai的排列情况在(n)种周期为N的m序列中可以找到，则相应的n级(LFSR)就是能产生ai的最短的发生器。第2章 序列密码 (2)虽然N=2n-1，但因所给定ai的排布花样更多，变化更复杂，以致于在N=2n-1的(n)个m序列中不能找到它，需要在更大的n值(比如n1n)的m序列中才能包括它，那么就可以用级数为n1的LFSR来产生它。显然，这时N1=2n1-1，使N1N，ai只是周期为N1的m序列中的一个段落。(3)不存在恰能使N=2n-1的n值，但可以找到一个尽可能小的L值，使N2L-1，并且序列ai在(L)种周期为2L-1的m
23、序列中可以找到，或者被包含，那么就可以用级数为L的LFSR产生它。以上分析表明，序列越复杂，恰能产生它的m序列的级数就越高，因此要定义任意一个伪随机序列ai的复杂度C(ai)，可以先来寻找恰能包含它的最短的m序列，然后用产生这个m序列的LFSR的级数n来作为它的复杂度的定义。第2章 序列密码 定义定义：二元序列ai=a0a1aN-1的线性复杂度C(ai)的定义是恰能产生完整包含该序列ai的级数最少的线性反馈移位寄存器的级数n。C(ai)=nLFSR (2-11)【例2】讨论下述3个N=6的序列的复杂度。(1)ai=100101；(2)bi=100110;(3)ci=101010。解解：(1)a
24、i=100101：它被包含在三级LFSR产生的序列/1001011/中，所以它的复杂度为3；第2章 序列密码 (2)bi=100110：它也是N=6的序列，但在两个三级LFSR序列/1001011/和/1001110/中都找不到，在四级LFSR的m序列/1000 10011010111/中方可包含，因此它的复杂度为4。(3)ci=101010：它还是N=6的序列，但却只能在五级LFSR的m序列/10 0001001011001111100011011 1010/中才能找到相应段落，因此它的复杂度C(ai)=5。对全零序列ai约定C(ai)=0；长度为N的任意序列，复杂度最大为N；如果是n级m序
25、列，则复杂度为C(ai)=n=lb(N+1)显然，用线性反馈移位寄存器产生的伪随机序列，其复杂度都不高。由表2.2中所列数据看到，周期为T=16777215的序列，复杂度才是C(ai)=n=24。第2章 序列密码 结论结论：线性反馈移位寄存器产生的m序列，是构造密钥序列的好素材，其周期长度可以做到很大，随机性也十分接近Golomb要求。但缺点是复杂度太低，必须设法解决。2.2.6m序列的破译序列的破译5 作为密钥用的伪随机序列，复杂度过低有何问题呢？答案是安全性太低！理论上可以证明，只要知道n级m序列中的相继2n位，就能推测出它的特征多项式，进而得到整个序列。由式(2-5)知，n级线性反馈移位
26、寄存器的反馈关系可表示为 c0a0 c1 a1 cn-2 an-2 cn-1an-1=an (2-12)第2章 序列密码 因为m序列实际上是线性反馈移位寄存器历史状态的记录，所以线性反馈移位寄存器状态的反馈关系也就是m序列相邻n+1位之间的约束关系。设m序列的连续2n位为 x1，x2，x3，xn，xn+1，x2n则相邻n+1位之间有以下的递推关系：c0 x1 c1 x2 cn-2 xn-1 cn-1xn=xn+1 c0 x2 c1 x3 cn-2 xn cn-1xn+1=xn+2 c0 x3 c1 x4 cn-2 xn+1 cn-1xn+2=xn+3 c0 xn c1 xn+1 cn-2 x2
27、n-2 cn-1x2n-1=x2n第2章 序列密码写成矩阵形式为nnnnnnnnnxxxcccxxxxxxxxx22111012113221(2-13)第2章 序列密码 如果上式左面的nn方阵(不妨叫做错位方阵)是非奇异的，逆矩阵存在，就能够得到：nnnnnnnnnxxxxxxxxxxxxccc221112113221110(2-14)这样，就由相继2n位m序列求出了各个反馈系数。第2章 序列密码 然而，一般情况下总是只知道一段连续的m序列，并不知道产生它的LFSR的级数n，破译者首先必须设法确定n值是多少，才能用式(2-14)来计算各反馈系数。设已知的m序列为x1，x2，x3，；因为我们不知
28、道n等于多少，不妨从k=1，2，3，测试起，这时式(2-13)的左边的方阵分别为 1211322154343232132211 kkkkkxxxxxxxxxxxxxxxxxxxxxxx；(2-15)第2章 序列密码 对每一种kk方阵，首先计算模2行列式是否为零，若为零，则逆矩阵不存在，表明所测试的k值不对。若行列式非零，则由式(2-14)解出相应的系数c0,c1,，ck，把这些系数代回式(2-13)，检验后面的所有数据是否满足。一旦发现有不满足的数据，则说明所测试的k值还是不对。只有后面的所有数据统统满足式(2-13)，才表明所测试的k值是m序列的级数n。当测试通不过时，应再测试更大的方阵。一
29、种简化的测试方法是，计算式(2-15)的各个行列式模2值，凡是等于0的都可以剔除，在模2值等于1的行列式中，k值最大的那个矩阵就应当是所寻找的矩阵。将其代回式(2-14)即可求得各个反馈系数。第2章 序列密码2.3非线性序列非线性序列62.3.1M序列序列 如果反馈函数 f(a1a2an)为非线性函数，便构成非线性移位寄存器，其输出序列为非线性序列，其周期最大可以达到2n。能达到这个最大周期2n的序列叫做M序列。M序列具有以下统计特性：(1)在一个周期(2n位)之内，0和1的个数各为一半(2n-1)。(2)在一个周期内，总游程为2n-1，其中0、1游程各半：长为n的0游程和1游程各一个，长为n
30、-1的0、1游程均不存在，长为i(1in-2)的0、1游程各2n-i-1个。(3)周期为2n的序列共有 个，但它们并非都是M序列，其中n级线性反馈寄存器产生的有2n种，由它们生成(不同初态)n22第2章 序列密码的线性序列就有2n2n=22n种。理论指出在GF(2)域上，n级M序列的总数为 个，当n较大时，非线性反馈系列的数量是巨大的，有很大的利用空间。(4)n级M序列的复杂度为 由上述性质可见，M序列有很好的统计性质，较高的复杂度和大量可供选择的序列，然而，并不是所有的M序列都能当作良好的密钥序列使用。鉴于非线性函数的复杂性，目前对非线性移位寄存器的研究仍处于非常艰难的地步，取得成果较多的是
31、通过线性移位寄存器来开发的非线性序列。nn12212)(,12)(2121naCaCnnnn第2章 序列密码2.3.2非线性前馈序列非线性前馈序列 线性反馈移位寄存器产生的m序列，因其复杂度太低而不便于直接作为密钥流使用，但可以用它作为一个驱动源来推动另一个非线性电路。图2.9所示的 f(x)是非线性网络，也叫前馈电路，当LFSR处于不同状态时，f(x)便通过各位之间的非线性运算，输出不同的ki值。显然,ki序列的周期与原来LFSR的周期相同，然而复杂度却大大提高了。ki称为前馈序列。理论证明，如果 f(x)的次数为l，那么由n级m序列为驱动源的前馈序列ki的复杂度满足：ljjniCkC1)(
32、2-16)第2章 序列密码图2.9非线性前馈序列电路原理图第2章 序列密码式中，是n中取j的组合数。由于前馈序列的周期等于LFSR的周期T=2n-1，因此由前馈电路输出的非线性伪随机序列周期也是T，可知它的复杂度最大是T。一般来说，通过前馈网络适当的非线性滤波，可以得到复杂度接近2n-1的前馈序列。前馈序列的随机性与前馈网络的设计有关，比如增加项数可以改善前馈序列的统计特性。2.3.3非线性组合序列非线性组合序列 用多个线性反馈移位序列共同驱动一个非线性网络，产生的非线性序列(见图2.10)具有更好的特性：(1)若各个LFSR的级数ni两两互素，则组合序列的周期jnC)12(1niniT(2-
33、17)第2章 序列密码图2.10多个线性反馈移位序列驱动的非线性网络 第2章 序列密码 (2)组合序列的复杂度为 C(ki)=f(n1n2)(2-18)例如，3个LFSR的级数分别为3、5、7,非线性函数为 f(x1,x2,x3)=x3+x1x2+x1x2x3则组合序列的周期为 (23-1)(25-1)(27-1)=731127=27559复杂度为 f(n1,n2,n3)=7+35+357=127 1973年，P.R.Geffe提出一种组合序列设计方案，见图2.11左图所示。它采用3个级数分别为r、s、t的线性移位寄存器组合而成，r、s、t互素。请注意，寄存器t的输出须求反后再与第2章 序列密
34、码寄存器s的输出相乘。该组合网路产生的非线性复合序列的周期为 T=(2r-1)(2s-1)(2t-1)(2-19)复杂度为 C(M)=(r+s)t+s (2-20)由多个这样的组合网路进一步组合，可产生复杂度很高的非线性组合序列，图2.11的右图是一个实例。第2章 序列密码图2.11一种多路m序列非线性组合的实例第2章 序列密码2.3.4非线性复合序列非线性复合序列 复合器实际上是一个地址选择器。由A寄存器的状态来选择B寄存器的某一位输出ki。例如图2.12所示的LFSRA是三位，LFSRB是四位，复合器所设计的选择方式是由A2A1的码值决定LFSRB的地址，正好选通LFSRB四位中的任何一位
35、。如果t1时刻A2A1A0=011，B3B2B1B0=1100，则选择器A2A1=01，选通了B1的地址，于是B1=0输出。如果t2时刻A2A1A0101，B3B2B1B0=0110，则A2A110,选通了B21。若、两个LFSR的级数n与m互素，则组合后输出序列的周期可达到 T=(2n-1)(2m-1)(2-21)而复杂度最大可达到 C(a)=nm (2-22)第2章 序列密码图2.12非线性复合序列发生器 第2章 序列密码2.4利用线性反馈移位寄存器的密码反馈利用线性反馈移位寄存器的密码反馈 反馈移位寄存器除了被用来产生密钥流之外，还可以直接把移位反馈原理用于密码的加密算法中。一般流程可示
36、意为如图2.13所示。解码流程只需把明文m与密文c的两处箭头方向相反即可。将此原理推而广之，变通得到更多灵活的加密方法。如已知明文m=“cryptographyisthescienceofdatasecurity”，采用维吉利亚密码算法加密，密钥是redstar，则生成的密文是：“TVBHMOXIESZRIJKLHKUIVEGHGYDRKEVWVUIZXB”第2章 序列密码图2.13利用移位反馈原理的加密算法第2章 序列密码 然而若采用密文反馈的方法，前七个字符用redstar为密钥，加密得到“TVBHMOX”后，相继的七个字符不用redstar为密钥，而用TVBHMOX为密钥来加密，又得到七
37、字密文。再用此七字密文为密钥，来加密后继的七个明文字符，如此下去，得到的密文为“TVBHMOXKVQOKWPDCUGMGTQEYURJTJEQYTDKRZO”或者采用redstar与前七个字密文的模26加的结果作为密钥，来加密后继的七个明文字符，就可以克服只要知道了密钥长度，就能递推解密的漏洞。这样得到的密文是：“TVBHMOXBZTGDWGLKAQYEBPQHWWHSZUCSRBAYRD”第2章 序列密码习题习题2 1.明文加密成密文有哪几种方式？2.什么是“一字一密”系统？3.什么是序列的复杂度？什么是算法的复杂度？4.将LFSR各级全部赋为0，其输出流是什么？5.对于一个48位的LFSR
38、，有多少种可能的初始状态？6.在一个最大长度为4位的LFSR中，以4位和3位为反馈。对于从00001111的每一个可能的初值，其输出序列的周期为多少？7.已知序列密码的密文串1010110110和相应的明文串0100010001，而且还已知密钥流是使用三级线性反馈移位寄存器产生的，试求出LFSR的反馈系数和初值。第2章 序列密码实践练习实践练习2 实验题目：实验题目：m序列为密钥的序列加密的密文破译。实验平台：实验平台：Mathematica4.0。实验内容：实验内容：给出m序列为密钥的序列加密的密文和起始的一部分明文，进行破译训练。实验步骤：实验步骤：(1)用已知的部分明文与密文模2加得到部分密钥。(2)由部分密钥构造不同维数的错位方阵，计算并寻找能使其行列式在模2运算下等于1的最大的维数，这就是产生该序列的LFSR的级数n。第2章 序列密码 (3)由已确定的n级错位方阵的逆矩阵乘以下一个状态，得到特征多项式。(4)由特征多项式构造m序列生成器。(5)由完整的m序列解密全部密文。
