《線性移位寄存器》PPT課件.ppt

《《線性移位寄存器》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《線性移位寄存器》PPT課件.ppt（25頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

密碼學(xué)補(bǔ)充：線性反饋移位寄存器,1,密碼學(xué)補(bǔ)充：LFSR,范明鈺,2,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,主要內(nèi)容,移位寄存器線性移位寄存器的綜合線性等價(jià)量的概念,3,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,移位寄存器-1,傳統(tǒng)的，流密碼基于移位寄存器，如今也有更廣泛的各類設(shè)計(jì)方法移位寄存器包括級(jí)，每級(jí)有1個(gè)比特反饋函數(shù)線性反饋移位寄存器(LFSR)的反饋函數(shù)是線性的,4,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,實(shí)例-1,,5,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,實(shí)例-2,,6,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,移位寄存器-2,舉例(非線性)反饋函數(shù)f(xi,xi+1,xi+2)=1?xi?xi+2?xi+1xi+2(非線性)移位寄存器前3bits是初態(tài):(x0,x1,x2),7,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,,,8,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,移位寄存器-3,舉例LFSR則對(duì)于所有的i，xi+4=xi?xi+2若初態(tài)(x0,x1,x2,x3,x4)=01110則(x0,x1,…,x15,…)=0111010100001001…對(duì)于這種LFSR，線性反饋函數(shù)通常寫成多項(xiàng)式形態(tài)：x4+x2+1也稱為L(zhǎng)FSR的連接多項(xiàng)式,9,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,移位寄存器-4,可以把密鑰作為初態(tài)使用，例如如果初態(tài)是1001,生成的序列就是1001101011110001001…15bits(24-1)之后開始重復(fù),10,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,移位寄存器-5周期研究,,11,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,移位寄存器-6周期研究,,12,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,舉例-1,,13,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,舉例-2,,14,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,一般移位寄存器,,15,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,多項(xiàng)式表示,f(x)的集合記為Ω(f)：|Ω(f)|=2nΩ(f)是{0,1}中的向量,16,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,作業(yè),寫出下列LFSR的所有可能的輸出，指出其周期,17,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,序列的生成函數(shù),給定序列s0,s1,s2,…生成函數(shù)G(x)=s0+s1x+s2x2+s3x3+…=Σsixi,18,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,LFSR輸出序列的特點(diǎn),LFSR的輸出由特征多項(xiàng)式唯一確定對(duì)于給定的多項(xiàng)式，有2n個(gè)不同的寄存器的初態(tài)，包括全零生成最大長(zhǎng)度序列的多項(xiàng)式一定是本原的本原多項(xiàng)式的輸出是遍歷的，全零除外,19,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,LFSR的綜合,問題提出：對(duì)于長(zhǎng)度為N的二元序列，求出產(chǎn)生這一序列的技術(shù)最小的LFSR，即最短的線性移位寄存器的特征多項(xiàng)式思路：BCH碼的譯碼中，從校驗(yàn)子求找錯(cuò)位多項(xiàng)式的迭代算法。運(yùn)用歸納法求出一系列線性移位寄存器，使每一個(gè)線性移位寄存器都產(chǎn)生該序列的前n項(xiàng)，從而使最后得到的線性移位寄存器是產(chǎn)生所給N長(zhǎng)的二元序列的最短線性移位寄存器,20,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,Berlekamp-Massey算法,已知序列a=(a0,a1,a2,…,an-1)a的線性復(fù)雜度是最短的能夠產(chǎn)生a的LFSRa的連接多項(xiàng)式形如f(x)=c0+c1x+c2x2+…+cLxLBerlekamp-Massey算法可以求得f(x),21,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,Berlekamp-Massey算法,設(shè)：0級(jí)LFSR是以f(x)=1的LFSR，n=1,2,…N的零級(jí)LFSR由且僅由f(x)=1產(chǎn)生，ak=0,k=0,1,2,…n-1對(duì)n按歸納法定義序列：,n=1,2,…N取初值f0(x)=1，l0=0設(shè),i=0,1,2,…n(0?n?N)均已求得(l0?l1?l2?…?ln)。記fn(x)=c0(n)+c1(n)x+…+clnxln,c0(n)=1。再計(jì)算：dn=c0(n)an+c1(n)an-1+cln(n)an-ln，稱為第n步的差值。分兩種情況,22,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,Berlekamp-Massey算法(cntd),若dn=0，則令：fn+1(x)=fn(x)，ln+1=ln若dn=1，則區(qū)分L0=l1=…=ln=0時(shí)，?。篺n+1(x)=1+xn+1，ln+1=n+1當(dāng)有m(0?m?n)使lm?lm+1=lm+2=…=ln，則fn+1(x)=fn(x)+xn-mfm(x),ln+1=max{ln,n+1-ln}注：如果該算法不是在計(jì)算機(jī)上進(jìn)行，則計(jì)算起點(diǎn)不必從開始，而從序列中第一個(gè)不為零元素an0的標(biāo)號(hào)n0開始,23,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,算法流程,,24,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,梅森算法舉例,N=7，,25,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,序列的線性等價(jià)量,定義：能產(chǎn)生該序列的線性移位寄存器的最小長(zhǎng)度多項(xiàng)式及其解空間的關(guān)系極小特征多項(xiàng)式的唯一性極小特征多項(xiàng)式的次數(shù)稱為其線性等價(jià)量或遞歸長(zhǎng)度線性等價(jià)量相同的序列，周期為多少？,