《《線性移位寄存器》PPT課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《《線性移位寄存器》PPT課件.ppt（25頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、密碼學(xué)補充：線性反饋移位寄存器,1,密碼學(xué)補充：LFSR,范明鈺,2,密碼學(xué)補充：線性反饋移位寄存器,主要內(nèi)容,移位寄存器 線性移位寄存器的綜合 線性等價量的概念,3,密碼學(xué)補充：線性反饋移位寄存器,移位寄存器-1,傳統(tǒng)的，流密碼基于移位寄存器，如今也有更廣泛的各類設(shè)計方法 移位寄存器包括 級，每級有1個比特 反饋函數(shù) 線性反饋移位寄存器(LFSR)的反饋函數(shù)是線性的,4,密碼學(xué)補充：線性反饋移位寄存器,實例-1,,5,密碼學(xué)補充：線性反饋移位寄存器,實例-2,,6,密碼學(xué)補充：線性反饋移位寄存器,移位寄存器-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é)補充：線性反饋移位寄存器,,,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的連接多項式,9,密碼學(xué)補充：線性反饋移位寄存器,移位寄存器-4,可以把密鑰作為初態(tài)使用，例如 如果初態(tài)是1001, 生成的序
3、列就是 1001101011110001001 15 bits (24-1)之后開始重復(fù),10,密碼學(xué)補充：線性反饋移位寄存器,移位寄存器-5 周期研究,,11,密碼學(xué)補充：線性反饋移位寄存器,移位寄存器-6 周期研究,,12,密碼學(xué)補充：線性反饋移位寄存器,舉例-1,,13,密碼學(xué)補充：線性反饋移位寄存器,舉例-2,,14,密碼學(xué)補充：線性反饋移位寄存器,一般移位寄存器,,15,密碼學(xué)補充：線性反饋移位寄存器,多項式表示,f(x)的集合記為(f) ： |(f)|=2n (f)是0,1中的向量,16,密碼學(xué)補充：線性反饋移位寄存器,作業(yè),寫出下列LFSR的所有可能的輸出，指出其周期,17,密碼
4、學(xué)補充：線性反饋移位寄存器,序列的生成函數(shù),給定序列s0, s1, s2, 生成函數(shù) G(x) = s0+s1x+s2x2+ s3x3+ = si xi,18,密碼學(xué)補充：線性反饋移位寄存器,LFSR 輸出序列的特點,LFSR 的輸出由特征多項式唯一確定 對于給定的多項式，有2n個不同的寄存器的初態(tài)，包括全零 生成最大長度序列的多項式一定是本原的 本原多項式的輸出是遍歷的，全零除外,19,密碼學(xué)補充：線性反饋移位寄存器,LFSR 的綜合,問題提出：對于長度為N的二元序列，求出產(chǎn)生這一序列的技術(shù)最小的LFSR ，即最短的線性移位寄存器的特征多項式 思路：BCH碼的譯碼中，從校驗子求找錯位多項式
5、的迭代算法。運用歸納法求出一系列線性移位寄存器，使每一個線性移位寄存器都產(chǎn)生該序列的前n項，從而使最后得到的線性移位寄存器是產(chǎn)生所給N長的二元序列的最短線性移位寄存器,20,密碼學(xué)補充：線性反饋移位寄存器,Berlekamp-Massey算法,已知序列a = (a0,a1,a2,,an-1) a的線性復(fù)雜度是最短的能夠產(chǎn)生a的LFSR a的連接多項式形如f(x) = c0 + c1x + c2x2 + + cLxL Berlekamp-Massey算法可以求得f(x),21,密碼學(xué)補充：線性反饋移位寄存器,Berlekamp-Massey算法,設(shè)：0級LFSR 是以f(x)=1的LFSR ，n
6、=1,2,N的零級LFSR由且僅由f(x)=1產(chǎn)生，ak=0, k=0,1,2,n-1 對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。再計算：dn=c0(n)an+c1(n)an-1+cln(n)an-ln，稱為第n步的差值。分兩種情況,22,密碼學(xué)補充：線性反饋移位寄存器,Berlekamp-Massey算法(cntd),若dn=0，則令：fn+1(x)=fn(x)，ln+1=ln 若dn=1，則區(qū)分 L0=l1==l
7、n=0時，?。?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ìn)行，則計算起點不必從開始，而從序列中第一個不為零元素an0的標(biāo)號n0開始,23,密碼學(xué)補充：線性反饋移位寄存器,算法流程,,24,密碼學(xué)補充：線性反饋移位寄存器,梅森算法舉例,N=7，,25,密碼學(xué)補充：線性反饋移位寄存器,序列的線性等價量,定義：能產(chǎn)生該序列的線性移位寄存器的最小長度 多項式及其解空間的關(guān)系 極小特征多項式的唯一性 極小特征多項式的次數(shù)稱為其線性等價量或遞歸長度 線性等價量相同的序列，周期為多少？,
《線性移位寄存器》PPT課件.ppt
