线性移位寄存器

线性移位寄存器密码学补充：线性反馈移位寄存器1第一页，共二十五页，2022年，8月28日2密码学补充：线性反馈移位寄存器主要内容移位寄存器线性移位寄存器的综合线性等价量的概念第二页，共二十五页，2022年，8月28日3密码学补充：线性反馈移位寄存器移位寄存器-1传统的，流密码基于移位寄存器，如今也有更广泛的各类设计方法移位寄存器包括级，每级有1个比特反馈函数线性反馈移位寄存器(LFSR)的反馈函数是线性的第三页，共二十五页，2022年，8月28日4密码学补充：线性反馈移位寄存器实例-1第四页，共二十五页，2022年，8月28日5密码学补充：线性反馈移位寄存器实例-2第五页，共二十五页，2022年，8月28日6密码学补充：线性反馈移位寄存器移位寄存器-2举例(非线性)反馈函数f(xi,xi+1,xi+2)=1

xi

xi+2

xi+1xi+2(非线性)移位寄存器前3bits是初态:(x0,x1,x2)第六页，共二十五页，2022年，8月28日7密码学补充：线性反馈移位寄存器第七页，共二十五页，2022年，8月28日8密码学补充：线性反馈移位寄存器移位寄存器-3举例LFSR则对于所有的i，xi+4=xi

xi+2若初态(x0,x1,x2,x3,x4)=01110

则(x0,x1,…,x15对于这种LFSR，线性反馈函数通常写成多项式形态：x4+x2+1也称为LFSR的连接多项式第八页，共二十五页，2022年，8月28日9密码学补充：线性反馈移位寄存器移位寄存器-4可以把密钥作为初态使用，例如如果初态是1001,生成的序列就是10011001…15bits(24-1)之后开始重复第九页，共二十五页，2022年，8月28日10密码学补充：线性反馈移位寄存器移位寄存器-5周期研究第十页，共二十五页，2022年，8月28日11密码学补充：线性反馈移位寄存器移位寄存器-6周期研究第十一页，共二十五页，2022年，8月28日12密码学补充：线性反馈移位寄存器举例-1第十二页，共二十五页，2022年，8月28日13密码学补充：线性反馈移位寄存器举例-2第十三页，共二十五页，2022年，8月28日14密码学补充：线性反馈移位寄存器一般移位寄存器第十四页，共二十五页，2022年，8月28日15密码学补充：线性反馈移位寄存器多项式表示f(x)的集合记为Ω(f)：|Ω(f)|=2nΩ(f)是{0,1}中的向量第十五页，共二十五页，2022年，8月28日16密码学补充：线性反馈移位寄存器作业写出下列LFSR的所有可能的输出，指出其周期第十六页，共二十五页，2022年，8月28日17密码学补充：线性反馈移位寄存器序列的生成函数给定序列s0,s1,s2,…生成函数

G(x)=s0+s1x+s2x2+s3x3+…=Σsixi第十七页，共二十五页，2022年，8月28日18密码学补充：线性反馈移位寄存器LFSR输出序列的特点LFSR的输出由特征多项式唯一确定对于给定的多项式，有2n个不同的寄存器的初态，包括全零生成最大长度序列的多项式一定是本原的本原多项式的输出是遍历的，全零除外第十八页，共二十五页，2022年，8月28日19密码学补充：线性反馈移位寄存器LFSR的综合问题提出：对于长度为N的二元序列，求出产生这一序列的技术最小的LFSR，即最短的线性移位寄存器的特征多项式思路：BCH码的译码中，从校验子求找错位多项式的迭代算法。运用归纳法求出一系列线性移位寄存器，使每一个线性移位寄存器都产生该序列的前n项，从而使最后得到的线性移位寄存器是产生所给N长的二元序列的最短线性移位寄存器第十九页，共二十五页，2022年，8月28日20密码学补充：线性反馈移位寄存器Berlekamp-Massey算法已知序列a=(a0,a1,a2,…,an-1)a的线性复杂度是最短的能够产生a的LFSRa的连接多项式形如f(x)=c0+c1x+c2x2+…+cLxLBerlekamp-Massey算法可以求得f(x)第二十页，共二十五页，2022年，8月28日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按归纳法定义序列：<fn(x),ln>,n=1,2,…N取初值f0(x)=1，l0=0设<fi(x),li>,i=0,1,2,…n(0nN)均已求得(l0l1l2…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步的差值。分两种情况第二十一页，共二十五页，2022年，8月28日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(0mn)使lmlm+1=lm+2=…=ln，则fn+1(x)=fn(x)+xn-mfm(x),ln+1=max{ln,n+1-ln}注：如果该算法不是在计算机上进行，则计算起点不必从<f0(x),l0>开始，而从序列中第一个不为零元素an0的标号n0开始第二十二页，共二十五页，2022年，8月28日23密码学补充：线性反馈移位寄存器否否是是是否读入N；a0，…，aN－10n；f0(x)＝1；l0＝0计算dndn＝0？l0=l1=…=ln=0?fn＋1(x)=1+xn+1ln+1=n+1求m:lm<lm+1=…=lnfn＋1(x)=fn(x)+xn-mfm(x)ln+1=max{ln,n+1-ln}n<N－1?输出fn＋1(x)=fn(x)ln+1=lnn＋1n算法流程第二十三页，共二十五页，2022年，8月28日24密码学补充：线性反馈移位寄存器梅森算法举例N=7