《《線性移位寄存器》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《線性移位寄存器》PPT課件.ppt（25頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、密碼學(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 x
2、i+2 xi+1xi+2 (非線性) 移位寄存器 前3 bits是初態(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, 生成的序
3、列就是 1001101011110001001 15 bits (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,密碼
4、學(xué)補(bǔ)充：線性反饋移位寄存器,序列的生成函數(shù),給定序列s0, s1, s2, 生成函數(shù) G(x) = s0+s1x+s2x2+ s3x3+ = si xi,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)式
5、的迭代算法。運(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的LFSR a的連接多項(xiàng)式形如f(x) = c0 + c1x + c2x2 + + cLxL Berlekamp-Massey算法可以求得f(x),21,密碼學(xué)補(bǔ)充：線性反饋移位寄存器,Berlekamp-Massey算法,設(shè)：0級(jí)LFSR 是以f(x)=1的LFSR ，n
6、=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 l1l2 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==l
7、n=0時(shí)，取： fn+1(x)=1+xn+1，ln+1=n+1 當(dāng)有m(0m n)使lmlm+1=lm+2==ln，則fn+1(x)=fn(x)+xn-mfm(x), ln+1=maxln, 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à)量相同的序列，周期為多少？,
《線性移位寄存器》PPT課件.ppt
