单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,B-M,算 法,1,上节内容复习,移位存放器序列的三种表示方法：,线性递推式一元多项式：,at+n=c1at+n-1+c2at+n-2+cnat ,t=0,联结多项式：,f(x)=1+c1x+c2x2+cnxn,状态转移矩阵：,满足：st+1=stTf,称st=(at,at+1,at+2,at+n-1)为n维状态,2,几个概念,非退化的移位存放器,(不)可约多项式,极小多项式,序列和周期,本原多项式,m序列,1游程、0游程,m序列的游程分布规律,3,线性移存器,一解方程法,序列a是由n级线性移存器产生的，且知a的连续2n位，可用解线性方程组的方法得到线性递推式。,例：设,a,=01111000是4级线性移存器产生的序列的8个连续信号，求该移存器的线性递推式。,4,解：产生,a,=01111000的联结 多项式,设其联结多项式f(x)=1+c,1,x+c,2,x,2,+c,3,x,3,+x,4,线性递推式a,t,=a,t-4,+c,3,a,t-3,+c,2,a,t-2,+c,1,a,t-1,0+c3+c2+c1=1,1+c3+c2+c1=0,1+c3+c2+0=0,1+c3+0+0=0,解得：c3=1；c2=0；c1=0,故其联结多项式为1+x,3,+x,4,5,二、B-M迭代算法,根据密码学的需要，对线性反响移位存放器(LFSR)主要考虑下面两个问题：,1如何利用级数尽可能短的LFSR产生周期大、随机性能良好的序列，即固定级数时，什么样的移存器序列周期最长。这是从密钥生成角度考虑，用最小的代价产生尽可能好的、参与密码变换的序列。,2当一个长为N序列a时，如何构造一个级数尽可能小的LFSR来产生它。这是从密码分析角度来考虑，要想用线性方法重构密钥序列所必须付出的最小代价。这个问题可通过B-M算法来解决。,6,1、概念简介,设 是 上的长度为,N,的序列，而,是 上的多项式，,c,0,=1.,如果,f,(,x,)是一个能产生,a,并且级数最小的线性移位寄存器的反馈多项式，,l,是该移存器的级数，则称 为,序列,a,的线性综合解,。,如果序列中的元素满足递推关系：,则称 产生二元序列,a,。其中 表示,以,f,(,x,)为反馈多项式的,l,级线性移位寄存器。,7,线性移位存放器的综合问题可表述为：给定一个N长二元序列a，如何求出产生这一序列的最小级数的线性移位存放器，即最短的线性移存器？,几点说明：,2、规定：0级线性移位存放器是以f(x)=1为反响多项式的线性移位存放器，且n长(n=1,2,N)全零序列，仅由0级线性移位存放器产生。事实上，以f(x)=1为反响多项式的递归关系式是：ak=0，k=0,1,n-1.因此，这一规定是合理的。,1、反响多项式f(x)的次数l。因为产生a且级数最小的线性移位存放器可能是退化的，在这种情况下 f(x)的次数l；并且此时 f(x)中的cl=0，因此在反响多项式f(x)中c0=1，但不要求cl=1。,3、给定一个N长二元序列a，求能产生a并且级数最小的线性移位存放器，就是求a的线性综合解。利用B-M算法可以有效的求出。,8,2、B-M算法要点,用归纳法求出一系列线性移位寄存器：,每一个 都是产生序列a的前n项的最短线性移位存放器，在 的根底上构造相应的 ，使得 是产生给定序列前n+1项的最短移存器，那么最后得到的 就是产生给定N长二元序列a的最短的线性移位存放器。,9,3、B-M算法,1、,取初始值：,2、,设,均已求得，且,任意给定一个N长序列 ，按,n,归纳,定义,记：再计算：,称,d,n,为第n步差值。然后,分,两种情形,讨论,：,10,最后得到的 便是产生序列,a,的最短线性移位寄存器。,11,B-M算法流程,12,例2、求产生周期为7的m序列一个周期：0011101的最短线性移位存放器。,4、,实例,解：设 ，首先取初值,f,0,(,x,),=,1,l,0,=,0，则由,a,0,=0得,d,0,=1,a,0,=0,从而,f,1,(,x,),=,1,l,1,=,0；同理由,a,1,=0得,d,1,=1,a,1,=0,从而,f,2,(,x,),=,1,l,2,=,0。,由,a,2,=1得,d,2,=1,a,2,=1,，从而根据,l,0,=l,1,=l,2,=,0 知,f,2,(,x,),=,1+,x,2+1,=,1+,x,3,l,3,=,3,第1步,，计算,d,3,：,d,3,=1,a,3,+,0,a,2,+,0,a,1,+,1,a,0,=1,因为,l,2,l,3,，故,m,=2，由此,13,第2步,，计算,d,4,：,d,4,=1,a,4,+,1,a,3,+,0,a,2,+,1,a,1,=0,，从而,第3步,，计算,d,5,：,d,5,=1,a,5,+,1,a,4,+,0,a,3,+,1,a,2,=0,，从而,第4步,，计算,d,6,：,d,6,=1,a,6,+,1,a,5,+,0,a,4,+,1,a,3,=0,，从而,这表明，即为产生所给序列一个周期的最短线性移位寄存器。,14,