线性移位寄存器.ppt
密码学补充：线性反馈移位寄存器,1,密码学补充：LFSR,范明钰,2,密码学补充：线性反馈移位寄存器,主要内容,移位寄存器线性移位寄存器的综合线性等价量的概念,3,密码学补充：线性反馈移位寄存器,移位寄存器-1,传统的，流密码基于移位寄存器，如今也有更广泛的各类设计方法移位寄存器包括级，每级有1个比特反馈函数线性反馈移位寄存器(LFSR)的反馈函数是线性的,4,密码学补充：线性反馈移位寄存器,实例-1,5,密码学补充：线性反馈移位寄存器,实例-2,6,密码学补充：线性反馈移位寄存器,移位寄存器-2,举例(非线性)反馈函数f(xi,xi+1,xi+2)=1 xi xi+2 xi+1xi+2(非线性)移位寄存器前3 bits是初态:(x0,x1,x2),7,密码学补充：线性反馈移位寄存器,8,密码学补充：线性反馈移位寄存器,移位寄存器-3,举例LFSR则对于所有的i，xi+4=xi xi+2若初态(x0,x1,x2,x3,x4)=01110则(x0,x1,x15对于这种LFSR，线性反馈函数通常写成多项式形态：x4+x2+1也称为LFSR的连接多项式,9,密码学补充：线性反馈移位寄存器,移位寄存器-4,可以把密钥作为初态使用，例如如果初态是1001,生成的序列就是 1001100115 bits(24-1)之后开始重复,10,密码学补充：线性反馈移位寄存器,移位寄存器-5 周期研究,11,密码学补充：线性反馈移位寄存器,移位寄存器-6 周期研究,12,密码学补充：线性反馈移位寄存器,举例-1,13,密码学补充：线性反馈移位寄存器,举例-2,14,密码学补充：线性反馈移位寄存器,一般移位寄存器,15,密码学补充：线性反馈移位寄存器,多项式表示,f(x)的集合记为(f)：|(f)|=2n(f)是0,1中的向量,16,密码学补充：线性反馈移位寄存器,作业,写出下列LFSR的所有可能的输出，指出其周期,17,密码学补充：线性反馈移位寄存器,序列的生成函数,给定序列s0,s1,s2,生成函数 G(x)=s0+s1x+s2x2+s3x3+=si xi,18,密码学补充：线性反馈移位寄存器,LFSR 输出序列的特点,LFSR 的输出由特征多项式唯一确定对于给定的多项式，有2n个不同的寄存器的初态，包括全零生成最大长度序列的多项式一定是本原的本原多项式的输出是遍历的，全零除外,19,密码学补充：线性反馈移位寄存器,LFSR 的综合,问题提出：对于长度为N的二元序列，求出产生这一序列的技术最小的LFSR，即最短的线性移位寄存器的特征多项式思路：BCH码的译码中，从校验子求找错位多项式的迭代算法。运用归纳法求出一系列线性移位寄存器，使每一个线性移位寄存器都产生该序列的前n项，从而使最后得到的线性移位寄存器是产生所给N长的二元序列的最短线性移位寄存器,20,密码学补充：线性反馈移位寄存器,Berlekamp-Massey算法,已知序列a=(a0,a1,a2,an-1)a的线性复杂度是最短的能够产生a的LFSRa的连接多项式形如f(x)=c0+c1x+c2x2+cLxLBerlekamp-Massey算法可以求得f(x),21,密码学补充：线性反馈移位寄存器,Berlekamp-Massey算法,设：0级LFSR 是以f(x)=1的LFSR，n=1,2,N的零级LFSR由且仅由f(x)=1产生，ak=0,k=0,1,2,n-1对n按归纳法定义序列：,n=1,2,N取初值f0(x)=1，l0=0设,i=0,1,2,n(0 n N)均已求得(l0 l1l2 ln)。记fn(x)=c0(n)+c1(n)x+clnxln,c0(n)=1。再计算：dn=c0(n)an+c1(n)an-1+cln(n)an-ln，称为第n步的差值。分两种情况,22,密码学补充：线性反馈移位寄存器,Berlekamp-Massey算法(cntd),若dn=0，则令：fn+1(x)=fn(x)，ln+1=ln若dn=1，则区分L0=l1=ln=0时，取：fn+1(x)=1+xn+1，ln+1=n+1当有m(0m n)使lmlm+1=lm+2=ln，则fn+1(x)=fn(x)+xn-mfm(x),ln+1=maxln,n+1-ln注：如果该算法不是在计算机上进行，则计算起点不必从开始，而从序列中第一个不为零元素an0的标号n0开始,23,密码学补充：线性反馈移位寄存器,算法流程,24,密码学补充：线性反馈移位寄存器,梅森算法举例,N=7，,25,密码学补充：线性反馈移位寄存器,序列的线性等价量,定义：能产生该序列的线性移位寄存器的最小长度多项式及其解空间的关系极小特征多项式的唯一性极小特征多项式的次数称为其线性等价量或递归长度线性等价量相同的序列，周期为多少？,
