線性移位寄存器

線性移位寄存器密碼學(xué)補充：線性反饋移位寄存器1第1頁，課件共25頁，創(chuàng)作于2023年2月2密碼學(xué)補充：線性反饋移位寄存器主要內(nèi)容移位寄存器線性移位寄存器的綜合線性等價量的概念第2頁，課件共25頁，創(chuàng)作于2023年2月3密碼學(xué)補充：線性反饋移位寄存器移位寄存器-1傳統(tǒng)的，流密碼基于移位寄存器，如今也有更廣泛的各類設(shè)計方法移位寄存器包括級，每級有1個比特反饋函數(shù)線性反饋移位寄存器(LFSR)的反饋函數(shù)是線性的第3頁，課件共25頁，創(chuàng)作于2023年2月4密碼學(xué)補充：線性反饋移位寄存器實例-1第4頁，課件共25頁，創(chuàng)作于2023年2月5密碼學(xué)補充：線性反饋移位寄存器實例-2第5頁，課件共25頁，創(chuàng)作于2023年2月6密碼學(xué)補充：線性反饋移位寄存器移位寄存器-2舉例(非線性)反饋函數(shù)f(xi,xi+1,xi+2)=1

xi

xi+2

xi+1xi+2(非線性)移位寄存器前3bits是初態(tài):(x0,x1,x2)第6頁，課件共25頁，創(chuàng)作于2023年2月7密碼學(xué)補充：線性反饋移位寄存器第7頁，課件共25頁，創(chuàng)作于2023年2月8密碼學(xué)補充：線性反饋移位寄存器移位寄存器-3舉例LFSR則對于所有的i，xi+4=xi

xi+2若初態(tài)(x0,x1,x2,x3,x4)=01110

則(x0,x1,…,x15,…)=0111010100001001…對于這種LFSR，線性反饋函數(shù)通常寫成多項式形態(tài)：x4+x2+1也稱為LFSR的連接多項式第8頁，課件共25頁，創(chuàng)作于2023年2月9密碼學(xué)補充：線性反饋移位寄存器移位寄存器-4可以把密鑰作為初態(tài)使用，例如如果初態(tài)是1001,生成的序列就是1001101011110001001…15bits(24-1)之后開始重復(fù)第9頁，課件共25頁，創(chuàng)作于2023年2月10密碼學(xué)補充：線性反饋移位寄存器移位寄存器-5周期研究第10頁，課件共25頁，創(chuàng)作于2023年2月11密碼學(xué)補充：線性反饋移位寄存器移位寄存器-6周期研究第11頁，課件共25頁，創(chuàng)作于2023年2月12密碼學(xué)補充：線性反饋移位寄存器舉例-1第12頁，課件共25頁，創(chuàng)作于2023年2月13密碼學(xué)補充：線性反饋移位寄存器舉例-2第13頁，課件共25頁，創(chuàng)作于2023年2月14密碼學(xué)補充：線性反饋移位寄存器一般移位寄存器第14頁，課件共25頁，創(chuàng)作于2023年2月15密碼學(xué)補充：線性反饋移位寄存器多項式表示f(x)的集合記為Ω(f)：|Ω(f)|=2nΩ(f)是{0,1}中的向量第15頁，課件共25頁，創(chuàng)作于2023年2月16密碼學(xué)補充：線性反饋移位寄存器作業(yè)寫出下列LFSR的所有可能的輸出，指出其周期第16頁，課件共25頁，創(chuàng)作于2023年2月17密碼學(xué)補充：線性反饋移位寄存器序列的生成函數(shù)給定序列s0,s1,s2,…生成函數(shù)

G(x)=s0+s1x+s2x2+s3x3+…=Σsixi第17頁，課件共25頁，創(chuàng)作于2023年2月18密碼學(xué)補充：線性反饋移位寄存器LFSR輸出序列的特點LFSR的輸出由特征多項式唯一確定對于給定的多項式，有2n個不同的寄存器的初態(tài)，包括全零生成最大長度序列的多項式一定是本原的本原多項式的輸出是遍歷的，全零除外第18頁，課件共25頁，創(chuàng)作于2023年2月19密碼學(xué)補充：線性反饋移位寄存器LFSR的綜合問題提出：對于長度為N的二元序列，求出產(chǎn)生這一序列的技術(shù)最小的LFSR，即最短的線性移位寄存器的特征多項式思路：BCH碼的譯碼中，從校驗子求找錯位多項式的迭代算法。運用歸納法求出一系列線性移位寄存器，使每一個線性移位寄存器都產(chǎn)生該序列的前n項，從而使最后得到的線性移位寄存器是產(chǎn)生所給N長的二元序列的最短線性移位寄存器第19頁，課件共25頁，創(chuàng)作于2023年2月20密碼學(xué)補充：線性反饋移位寄存器Berlekamp-Massey算法已知序列a=(a0,a1,a2,…,an-1)a的線性復(fù)雜度是最短的能夠產(chǎn)生a的LFSRa的連接多項式形如f(x)=c0+c1x+c2x2+…+cLxLBerlekamp-Massey算法可以求得f(x)第20頁，課件共25頁，創(chuàng)作于2023年2月21密碼學(xué)補充：線性反饋移位寄存器Berlekamp-Massey算法設(shè)：0級LFSR是以f(x)=1的LFSR，n=1,2,…N的零級LFSR由且僅由f(x)=1產(chǎn)生，ak=0,k=0,1,2,…n-1對n按歸納法定義序列：<fn(x),ln>,n=1,2,…N取初值f0(x)=1，l0=0設(shè)<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步的差值。分兩種情況第21頁，課件共25頁，創(chuàng)作于2023年2月22密碼學(xué)補充：線性反饋移位寄存器Berlekamp-Massey算法(cntd)若dn=0，則令：fn+1(x)=fn(x)，ln+1=ln若dn=1，則區(qū)分L0=l1=…=ln=0時，?。篺n+1(x)=1+xn+1，ln+1=n+1當(dāng)有m(0mn)使lmlm+1=lm+2=…=ln，則fn+1(x)=fn(x)+xn-mfm(x),ln+1=max{ln,n+1-ln}注：如果該算法不是在計算機上進(jìn)行，則計算起點不必從<f0(x),l0>開始，而從序列中第一個不為零元素an0的標(biāo)號n0開始第22頁，課件共25頁，創(chuàng)作于2023年2月23密碼學(xué)補充：線性反饋移位寄存器否否是是是否讀入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算法流程第23頁，課件共25頁，創(chuàng)作于2023年2月24密碼學(xué)補充：線性反饋移位寄存器梅森算法舉例