第2章01--流密碼(LFSR)

1、1第第2 2章章 流密碼流密碼( (序列密碼序列密碼) )一、流密碼的基本概念一、流密碼的基本概念二、線性反饋移位寄存器序列二、線性反饋移位寄存器序列三三、線性移位寄存器的一元多項(xiàng)式表示、線性移位寄存器的一元多項(xiàng)式表示四四、m序列的偽隨機(jī)性序列的偽隨機(jī)性五、五、m序列密碼的破譯序列密碼的破譯2 流密碼的基本概念流密碼的基本概念n流密碼是將明文劃分成字符流密碼是將明文劃分成字符( (如單個(gè)字母如單個(gè)字母) )，或其編碼，或其編碼的基本單元的基本單元( (如如0, 10, 1數(shù)字?jǐn)?shù)字) )，字符分別與密鑰流作用進(jìn)，字符分別與密鑰流作用進(jìn)行加密，解密時(shí)以同步產(chǎn)生的同樣的密鑰流實(shí)現(xiàn)。行加密，解密時(shí)以同

2、步產(chǎn)生的同樣的密鑰流實(shí)現(xiàn)。n流密碼強(qiáng)度流密碼強(qiáng)度完全依賴于密鑰序列的隨機(jī)性完全依賴于密鑰序列的隨機(jī)性( (Randomness)Randomness)和不可預(yù)測(cè)性和不可預(yù)測(cè)性( (Unpredictability)Unpredictability)。n核心問題核心問題是密鑰流生成器的設(shè)計(jì)是密鑰流生成器的設(shè)計(jì)。n保持收發(fā)兩端密鑰流的保持收發(fā)兩端密鑰流的精確精確同步同步是實(shí)現(xiàn)可靠解密的關(guān)是實(shí)現(xiàn)可靠解密的關(guān)鍵技術(shù)鍵技術(shù)。iiikmciiikcm加密加密解密解密3流密碼的框圖流密碼的框圖kI 安 全 信 道 kI KG KG ki ki mi ci ci mi Eki(mi) Eki(mi)4 流密碼

3、的框圖流密碼的框圖n消息流：消息流：m=m1m2mi，其中，其中mi M。n密文流：密文流： c=c1c2ci=Ek1(m1)Ek2(m2) Eki(mi)，ci C。n密鑰流：密鑰流：ki，i 0。 一個(gè)完全隨機(jī)的非周期序列，可以實(shí)現(xiàn)一次一密體制。但一個(gè)完全隨機(jī)的非周期序列，可以實(shí)現(xiàn)一次一密體制。但需要需要無限存儲(chǔ)單元無限存儲(chǔ)單元和和復(fù)雜的輸出邏輯函數(shù)復(fù)雜的輸出邏輯函數(shù)f f。 i i是第是第i i時(shí)刻時(shí)刻密鑰流生成器的內(nèi)部狀態(tài)，以存儲(chǔ)單元的存數(shù)矢量描述。密鑰流生成器的內(nèi)部狀態(tài)，以存儲(chǔ)單元的存數(shù)矢量描述。),(iikfk5 流密碼的分類流密碼的分類(1)n同步流密碼同步流密碼SSC(Sync

4、hronous Stream Cipher)： i與明文消息無關(guān)，密鑰流將獨(dú)立于明文。與明文消息無關(guān)，密鑰流將獨(dú)立于明文。n特點(diǎn)：特點(diǎn)：n對(duì)于明文而言，這類加密變換是無記憶的。但它是時(shí)變對(duì)于明文而言，這類加密變換是無記憶的。但它是時(shí)變的。的。n只有保持兩端精確同步才能正常工作。只有保持兩端精確同步才能正常工作。n對(duì)主動(dòng)攻擊時(shí)異常敏感而有利于檢測(cè)對(duì)主動(dòng)攻擊時(shí)異常敏感而有利于檢測(cè)n無差錯(cuò)傳播無差錯(cuò)傳播( (Error Propagation)Error Propagation) 6流密碼的分類流密碼的分類(2)n自同步流密碼自同步流密碼SSSC(Self-Synchronous Stream Ci

5、pher) i i依賴于依賴于( (k kI I, , i-1i-1, ,m mi i) )，使密文使密文c ci i不僅與當(dāng)前輸不僅與當(dāng)前輸入入m mi i有關(guān)，而且由于有關(guān)，而且由于k ki i對(duì)對(duì) i i的關(guān)系而與以前的輸入的關(guān)系而與以前的輸入m m1 1, , m m2 2 , , ,m mi-1i-1有關(guān)。一般在有限的有關(guān)。一般在有限的n n級(jí)存儲(chǔ)下將級(jí)存儲(chǔ)下將與與m mi-1i-1, , ,m mi-ni-n有關(guān)。有關(guān)。n優(yōu)點(diǎn)：優(yōu)點(diǎn)：具有自同步能力，強(qiáng)化了其抗統(tǒng)計(jì)分析的具有自同步能力，強(qiáng)化了其抗統(tǒng)計(jì)分析的能力能力n缺點(diǎn)：缺點(diǎn)：有有n n位位長的差錯(cuò)傳播長的差錯(cuò)傳播。密鑰流與明文流不

6、相互獨(dú)立！密鑰流與明文流不相互獨(dú)立！7同步流密碼n密鑰流產(chǎn)生器密鑰流產(chǎn)生器n加密變換器加密變換器n主要問題：設(shè)計(jì)一個(gè)滾動(dòng)的密鑰產(chǎn)生器，主要問題：設(shè)計(jì)一個(gè)滾動(dòng)的密鑰產(chǎn)生器，使使k經(jīng)其擴(kuò)展成一個(gè)密鑰流具有以下性質(zhì)：經(jīng)其擴(kuò)展成一個(gè)密鑰流具有以下性質(zhì)：極大的周期、良好的統(tǒng)計(jì)特性、抗線性極大的周期、良好的統(tǒng)計(jì)特性、抗線性分析、抗統(tǒng)計(jì)分析分析、抗統(tǒng)計(jì)分析。有限狀態(tài)自動(dòng)機(jī)有限狀態(tài)自動(dòng)機(jī)FA8有限狀態(tài)自動(dòng)機(jī)有限狀態(tài)自動(dòng)機(jī)FA(Finite state Automation)n具有離散輸入和輸出（輸入集和輸出集均有具有離散輸入和輸出（輸入集和輸出集均有限）的一種數(shù)學(xué)模型限）的一種數(shù)學(xué)模型n有限狀態(tài)集有限狀態(tài)集S

7、=si|i=1,2,ln有限輸入字符集有限輸入字符集X= Xi|i=1,2,mn有限輸出字符集有限輸出字符集Y= Yk|k=1,2,nn轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù)nYjf 1(sj ,Xj)nSj+1 f 2(sj ,Xj)第第j時(shí)刻輸入時(shí)刻輸入Xj X ，輸出輸出YjY第第j時(shí)刻輸入時(shí)刻輸入Xj X ，狀態(tài)變?yōu)闋顟B(tài)變?yōu)镾j+1S9例nS=s1,s2,s3,X=x1, x2,x3,Y=(y1,y2,y3)n轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù)f1x1x2X3s1s2s3y1y2y3y3y1y2y2y3y1f2x1x2X3s1s2s3s2s3s1s1s2s3s3s1s210FA的狀態(tài)圖表示 若輸入為若輸入為x1x2x1x3x

8、3x1初始狀態(tài)初始狀態(tài)s1狀態(tài)序列：狀態(tài)序列：s1s2s2s3s2s1s2輸出序列：輸出序列： y1 y1 y2 y1 y3 y111作為作為FAFA的密鑰流產(chǎn)生器的密鑰流產(chǎn)生器n同步流密碼的密鑰流產(chǎn)生器可看為一同步流密碼的密鑰流產(chǎn)生器可看為一個(gè)參數(shù)為個(gè)參數(shù)為k的的FAFAn輸出集輸出集Z Z，狀態(tài)集，狀態(tài)集，狀態(tài)轉(zhuǎn)移函數(shù)，狀態(tài)轉(zhuǎn)移函數(shù)和輸出函數(shù)和輸出函數(shù)，初態(tài)，初態(tài) 0 0n設(shè)計(jì)的關(guān)鍵是設(shè)計(jì)的關(guān)鍵是和和ikkkzi),(0Z采用非線性函數(shù)采用非線性函數(shù)12作為作為FAFA的密鑰流產(chǎn)生器的密鑰流產(chǎn)生器n具有非線性的具有非線性的的的FA理論很不完善，通理論很不完善，通常采用線性狀態(tài)轉(zhuǎn)移函數(shù)常采用

9、線性狀態(tài)轉(zhuǎn)移函數(shù)以及非線性的以及非線性的輸出函數(shù)輸出函數(shù)n可將此類產(chǎn)生器分為驅(qū)動(dòng)部分和非線性可將此類產(chǎn)生器分為驅(qū)動(dòng)部分和非線性組合部分。組合部分。n驅(qū)動(dòng)部分控制狀態(tài)轉(zhuǎn)移驅(qū)動(dòng)部分控制狀態(tài)轉(zhuǎn)移n非線性組合部分提供統(tǒng)計(jì)特性良好的序列非線性組合部分提供統(tǒng)計(jì)特性良好的序列),(0ZLFSR13兩種常見的密鑰流產(chǎn)生器LFSR非線性組合函數(shù)ziLFSRLFSRLFSR非線性組合函數(shù)zi14第四章第四章 流密碼流密碼一、流密碼的基本概念一、流密碼的基本概念二、二、線性反饋移位寄存器序列線性反饋移位寄存器序列三三、線性移位寄存器的一元多項(xiàng)式表示、線性移位寄存器的一元多項(xiàng)式表示四四、m序列的偽隨機(jī)性序列的偽隨機(jī)性

10、五、五、m序列密碼的破譯序列密碼的破譯15線性反饋移位寄存器序列概念線性反饋移位寄存器序列概念移位寄存器是流密碼產(chǎn)生密鑰流的一個(gè)主要組成部分。移位寄存器是流密碼產(chǎn)生密鑰流的一個(gè)主要組成部分。GF(2)上一個(gè)上一個(gè)n級(jí)反饋移位寄存器由級(jí)反饋移位寄存器由n個(gè)二元存儲(chǔ)器與個(gè)二元存儲(chǔ)器與一個(gè)反饋函數(shù)一個(gè)反饋函數(shù)f(a1,a2,an)組成，如圖所示。組成，如圖所示。每一存儲(chǔ)器稱為移位寄存器的一級(jí)，在任一時(shí)刻，這些級(jí)的內(nèi)容構(gòu)成該反饋每一存儲(chǔ)器稱為移位寄存器的一級(jí)，在任一時(shí)刻，這些級(jí)的內(nèi)容構(gòu)成該反饋移位寄存器的狀態(tài)，每一狀態(tài)對(duì)應(yīng)于移位寄存器的狀態(tài)，每一狀態(tài)對(duì)應(yīng)于GF(2)上的一個(gè)上的一個(gè)n維向量，共有維向量

11、，共有2n種可種可能的狀態(tài)。每一時(shí)刻的狀態(tài)可用能的狀態(tài)。每一時(shí)刻的狀態(tài)可用n長序列表示長序列表示: a1,a2,an16例：例： 3級(jí)反饋移位寄存器，其初始狀態(tài)為級(jí)反饋移位寄存器，其初始狀態(tài)為(a1,a2,a3)=(1,0,1)，輸出可由表求出輸出可由表求出狀態(tài)狀態(tài)（a1,a2,a3)輸出輸出1 0 11 1 01 1 10 1 11 0 11 1 0 101110非線性反饋移位寄存器非線性反饋移位寄存器17 如果移位寄存器的反饋函數(shù)如果移位寄存器的反饋函數(shù)f(a1,a2,an)是是a1，a2，an的線性函數(shù)，則稱之為線性反饋移位寄存器的線性函數(shù)，則稱之為線性反饋移位寄存器LFSR（linea

12、r feedback shift register）。）。此時(shí)此時(shí)f可寫為可寫為其中常數(shù)其中常數(shù)ci=0或或1，是模是模2加法。加法。ci=0或或1可用開關(guān)的斷開和閉合來實(shí)現(xiàn)，如上圖所示?？捎瞄_關(guān)的斷開和閉合來實(shí)現(xiàn)，如上圖所示。nnnnacacacaaaf121121),(18 輸出序列輸出序列at滿足滿足an+t=cnatcn-1at+1c1an+t-1其中其中t為非負(fù)正整數(shù)。為非負(fù)正整數(shù)。 線性反饋移位寄存器因其實(shí)現(xiàn)簡單、速度快、有較為成線性反饋移位寄存器因其實(shí)現(xiàn)簡單、速度快、有較為成熟的理論等優(yōu)點(diǎn)而成為構(gòu)造密鑰流生成器的最重要的部件熟的理論等優(yōu)點(diǎn)而成為構(gòu)造密鑰流生成器的最重要的部件之一。

13、之一。19例，下圖是一個(gè)例，下圖是一個(gè)5級(jí)線性反饋移位寄存器，其初始狀態(tài)為級(jí)線性反饋移位寄存器，其初始狀態(tài)為（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出輸出序列為：可求出輸出序列為：14aaf1001101001000010101110110001111100110輸出序列為輸出序列為反饋函數(shù)：反饋函數(shù)：周期：周期：3120 在線性反饋移位寄存器中總是假定在線性反饋移位寄存器中總是假定c1,c2,cn中至中至少有一個(gè)不為少有一個(gè)不為0，否則，否則f(a1,a2,an)0，這樣的話，這樣的話，在在n個(gè)脈沖后狀態(tài)必然是個(gè)脈沖后狀態(tài)必然是000，且這個(gè)狀態(tài)必將一直，且這個(gè)狀態(tài)必將

14、一直持續(xù)下去。持續(xù)下去。 若只有一個(gè)系數(shù)不為若只有一個(gè)系數(shù)不為0，設(shè)僅有，設(shè)僅有cj不為不為0，實(shí)際上是，實(shí)際上是一種延遲裝置。一般對(duì)于一種延遲裝置。一般對(duì)于n級(jí)線性反饋移位寄存器，總級(jí)線性反饋移位寄存器，總是假定是假定c0=1。21n線性反饋移位寄存器輸出序列的性質(zhì)完全由其反饋函數(shù)線性反饋移位寄存器輸出序列的性質(zhì)完全由其反饋函數(shù)決定。決定。nn級(jí)線性反饋移位寄存器最多有級(jí)線性反饋移位寄存器最多有2n個(gè)不同的狀態(tài)。個(gè)不同的狀態(tài)。n若其初始狀態(tài)為若其初始狀態(tài)為0，則其狀態(tài)恒為，則其狀態(tài)恒為0。若其初始狀態(tài)非。若其初始狀態(tài)非0，則其后繼狀態(tài)不會(huì)為則其后繼狀態(tài)不會(huì)為0。n因此因此n級(jí)線性反饋移位寄存

15、器的狀態(tài)周期小于等于級(jí)線性反饋移位寄存器的狀態(tài)周期小于等于2n-1。n其輸出序列的周期與狀態(tài)周期相等，也小于等于其輸出序列的周期與狀態(tài)周期相等，也小于等于2n-1。n只要選擇合適的反饋函數(shù)便可使序列的周期達(dá)到最大值只要選擇合適的反饋函數(shù)便可使序列的周期達(dá)到最大值2n-1，周期達(dá)到最大值的序列稱為周期達(dá)到最大值的序列稱為m序列序列。nnnnacacacaaaf121121),(22第四章第四章 流密碼流密碼一、流密碼的基本概念一、流密碼的基本概念二、二、線性反饋移位寄存器序列線性反饋移位寄存器序列三三、線性移位寄存器的一元多項(xiàng)式表示、線性移位寄存器的一元多項(xiàng)式表示四四、m序列的偽隨機(jī)性序列的偽隨

16、機(jī)性五、五、m序列密碼的破譯序列密碼的破譯23設(shè)設(shè)n級(jí)級(jí)LFSR的輸出序列滿足遞推關(guān)系的輸出序列滿足遞推關(guān)系an+k=c1an+k-1 c2an+k-2 cnak (*)對(duì)任何對(duì)任何k1成立。這種遞推關(guān)系可用一個(gè)一元高次多項(xiàng)式成立。這種遞推關(guān)系可用一個(gè)一元高次多項(xiàng)式 P(x)=1+c1x+cn-1xn-1cnxn表示，稱這個(gè)多項(xiàng)式為表示，稱這個(gè)多項(xiàng)式為LFSR的的特征多項(xiàng)式特征多項(xiàng)式。4.3 線性移位寄存器的一元多項(xiàng)式表示線性移位寄存器的一元多項(xiàng)式表示24實(shí)例：（畫出下列個(gè)移存器的邏輯框圖，寫出相應(yīng)的線實(shí)例：（畫出下列個(gè)移存器的邏輯框圖，寫出相應(yīng)的線性遞推式，并討論由它們所產(chǎn)生的序列）性遞推式

17、，并討論由它們所產(chǎn)生的序列）1、不可約多項(xiàng)式2、可約多項(xiàng)式3、本原多項(xiàng)式4、環(huán)式移存器1)(234xxxxxf) 1)(1(1)(334xxxxxxf1)(4xxxf1)(4 xxf25答案：答案：1 1、該移存器產(chǎn)生三類周期相同（全為、該移存器產(chǎn)生三類周期相同（全為5 5）的序列及一個(gè)全）的序列及一個(gè)全零序列。零序列。2 2、該移存器產(chǎn)生五類周期分別為、該移存器產(chǎn)生五類周期分別為6 6、3 3、3 3、2 2、1 1的序列及的序列及一個(gè)全零序列。一個(gè)全零序列。3 3、該移存器產(chǎn)生周期為、該移存器產(chǎn)生周期為1515的的m序列及一個(gè)全零序列。序列及一個(gè)全零序列。1、不可約多項(xiàng)式2、可約多項(xiàng)式3、

18、本原多項(xiàng)式4、環(huán)式移存器1)(234xxxxxf) 1)(1(1)(334xxxxxxf1)(4xxxf1)(4 xxf26本原多項(xiàng)式本原多項(xiàng)式n設(shè)設(shè)p(x)是是GF(2)上的多項(xiàng)式，使上的多項(xiàng)式，使p(x)|(xp-1)的最小的最小p稱為稱為p(x)的周期或者階的周期或者階。n僅能被非僅能被非0常數(shù)或自身的常數(shù)倍除盡，但不能被其他常數(shù)或自身的常數(shù)倍除盡，但不能被其他多項(xiàng)式除盡的多項(xiàng)式稱為多項(xiàng)式除盡的多項(xiàng)式稱為不可約多項(xiàng)式不可約多項(xiàng)式。n若若n次不可約多項(xiàng)式次不可約多項(xiàng)式p(x)的階為的階為2n-1，則稱，則稱p(x)是是n次本原多項(xiàng)式次本原多項(xiàng)式。以本原多項(xiàng)式為連接多項(xiàng)式產(chǎn)生的非零序列均是以本原多項(xiàng)式為連接多項(xiàng)式產(chǎn)生的非零序列均是m序列。序列。271)(4xxxf例：本原多項(xiàng)式例：本原多項(xiàng)式因?yàn)?，因?yàn)?，f(x)|(x15-1)，但不存在比，但不存在比15小的常數(shù)小的常數(shù)m，使，