第2章_流密碼__現(xiàn)代密碼學(xué)

1、第第2章章 流密碼流密碼2.1 流密碼的基本概念流密碼的基本概念2.2 線性反饋移位寄存器線性反饋移位寄存器2.3 線性移位寄存器的一元多項(xiàng)式表示線性移位寄存器的一元多項(xiàng)式表示2.4 m序列的偽隨機(jī)性序列的偽隨機(jī)性2.5 m序列密碼的破譯序列密碼的破譯2.6 非線性序列非線性序列基本思想基本思想: 利用密鑰利用密鑰k產(chǎn)生一個(gè)密鑰流產(chǎn)生一個(gè)密鑰流z=z0z1，并使用如并使用如下規(guī)則對明文串下規(guī)則對明文串x=x0 x1x2加密：加密： y=y0y1y2=Ez0(x0)Ez1(x1)Ez2(x2)。 密鑰流由密鑰流發(fā)生器密鑰流由密鑰流發(fā)生器f產(chǎn)生：產(chǎn)生： zi=f(k,i)， i:加密器中的記憶元件

2、加密器中的記憶元件(存儲器存儲器)在時(shí)刻在時(shí)刻i的狀態(tài)，的狀態(tài)， f:由密鑰由密鑰k和和i產(chǎn)生的函數(shù)。產(chǎn)生的函數(shù)。2.1 流密碼的基本概念流密碼的基本概念分組密碼與流密碼的區(qū)別分組密碼與流密碼的區(qū)別: 有無記憶性有無記憶性（如圖（如圖2.1）。）。滾動(dòng)密鑰：滾動(dòng)密鑰：z0=f(k,0)由由函數(shù)函數(shù)f、密鑰密鑰k和和指定的初態(tài)指定的初態(tài)0完全確定。完全確定。 注：由于輸入加密器的明文可能影響加密器中內(nèi)部記憶元件的存儲注：由于輸入加密器的明文可能影響加密器中內(nèi)部記憶元件的存儲狀態(tài)，因而狀態(tài)，因而i(i0)可能依賴于可能依賴于 k，0，x0，x1，xi-1等參數(shù)。等參數(shù)。圖圖2.1 分組密碼和流密碼

3、的比較分組密碼和流密碼的比較 根據(jù)加密器中記憶元件的存儲狀態(tài)根據(jù)加密器中記憶元件的存儲狀態(tài)i是否依賴于輸入是否依賴于輸入的明文字符的明文字符，流密碼可進(jìn)一步分成，流密碼可進(jìn)一步分成同步同步和和自同步自同步兩種。兩種。 同步流密碼同步流密碼: i獨(dú)立于明文字符獨(dú)立于明文字符 自同步流密碼自同步流密碼: i不獨(dú)立于明文字符。不獨(dú)立于明文字符。 自同步流密碼自同步流密碼較難從理論上進(jìn)行分析較難從理論上進(jìn)行分析主要原因在于密鑰流的產(chǎn)生與明文有關(guān)主要原因在于密鑰流的產(chǎn)生與明文有關(guān) 目前大多數(shù)研究成果都是關(guān)于同步流密碼的。目前大多數(shù)研究成果都是關(guān)于同步流密碼的。2.1.1 同步流密碼同步流密碼圖圖2.2

4、同步流密碼體制模型同步流密碼體制模型密文字符密文字符yi=Ezi(xi)也不依賴于此前的明文字符。也不依賴于此前的明文字符。加密器分成加密器分成密鑰流產(chǎn)生器密鑰流產(chǎn)生器和和加密變換器加密變換器兩個(gè)部分。兩個(gè)部分。加密變換加密變換Ezi可以有多種選擇，只要保證變換是可以有多種選擇，只要保證變換是可逆可逆的即可。的即可。圖圖2.3 加法流密碼體制模型加法流密碼體制模型實(shí)際使用的數(shù)字保密通信系統(tǒng)一般都是實(shí)際使用的數(shù)字保密通信系統(tǒng)一般都是二元系統(tǒng)二元系統(tǒng)，因而在，因而在有限域有限域CF(2)上討論的二元加法流密碼（如圖上討論的二元加法流密碼（如圖2.3）是目前最）是目前最為常用的流密碼體制，其加密變換

5、可表示為為常用的流密碼體制，其加密變換可表示為yi=zi xi。一次一密密碼是加法流密碼的原型。一次一密密碼是加法流密碼的原型。 如果（即密鑰用作滾動(dòng)密鑰流），則加法流密碼就退如果（即密鑰用作滾動(dòng)密鑰流），則加法流密碼就退化成一次一密密碼?；梢淮我幻苊艽a。密碼設(shè)計(jì)者的最大愿望是設(shè)計(jì)出一個(gè)滾動(dòng)密鑰生成器，使密碼設(shè)計(jì)者的最大愿望是設(shè)計(jì)出一個(gè)滾動(dòng)密鑰生成器，使得密鑰經(jīng)其擴(kuò)展成的密鑰流序列具有如下性質(zhì)：得密鑰經(jīng)其擴(kuò)展成的密鑰流序列具有如下性質(zhì)：極大的周期、良好的統(tǒng)計(jì)特性、極大的周期、良好的統(tǒng)計(jì)特性、抗線性分析、抗統(tǒng)計(jì)分析抗線性分析、抗統(tǒng)計(jì)分析具有離散輸入和輸出（輸入集和輸出集均有限）的一種具有離散輸

6、入和輸出（輸入集和輸出集均有限）的一種數(shù)學(xué)模型，由以下數(shù)學(xué)模型，由以下3部分組成：部分組成： 有限狀態(tài)集有限狀態(tài)集S=si|i=1,2,l。 有限輸入字符集有限輸入字符集A1=A(1)j|j=1,2,m 有限輸出字符集有限輸出字符集A2=A(2)k|k=1,2,n。 轉(zhuǎn)移函數(shù)轉(zhuǎn)移函數(shù)A(2)k=f1(si, A(1)j)，sh=f2(si, A(1)j)即在狀態(tài)為即在狀態(tài)為si，輸入為輸入為A(1)j時(shí)，輸出為時(shí)，輸出為A(2)k，而狀態(tài)轉(zhuǎn)移為而狀態(tài)轉(zhuǎn)移為sh。2.1.2 有限狀態(tài)自動(dòng)機(jī)有限狀態(tài)自動(dòng)機(jī)例例2.1 S=s1,s2,s3，A1=A(1)1,A(1)2,A(1)3，A2=A(2)1,

7、A(2)2,A(2)3，轉(zhuǎn)移函數(shù)由下表給出。轉(zhuǎn)移函數(shù)由下表給出。A(2)k=f1(si, A(1)j)，sh=f2(si, A(1)j)A(1)1A(1)2A(1)3A(1)1A(1)2A(1)3S1A(2)1A(2)3A(2)2S1S2S1S3S2A(2)2A(2)1A(2)3S2S3S2S1S3A(2)3A(2)2A(2)1S3S1S3S2有限狀態(tài)自動(dòng)機(jī)可用有向圖表示，稱為有限狀態(tài)自動(dòng)機(jī)可用有向圖表示，稱為轉(zhuǎn)移圖轉(zhuǎn)移圖。圖圖2.4 有限狀態(tài)自動(dòng)機(jī)的轉(zhuǎn)移圖有限狀態(tài)自動(dòng)機(jī)的轉(zhuǎn)移圖例例2.1中，若輸入序列為中，若輸入序列為A(1)1A(1)2A(1)1A(1)3A(1)3A(1)1，初始狀態(tài)為初

8、始狀態(tài)為s1，則得到則得到狀態(tài)序列狀態(tài)序列 s1s2s2s3s2s1s2 輸出字符序列輸出字符序列 A(2)1A(2)1A(2)2A(2)1A(2)3A(2)1同步流密碼的關(guān)鍵是密鑰流產(chǎn)生器。同步流密碼的關(guān)鍵是密鑰流產(chǎn)生器。 可看成一個(gè)參數(shù)為可看成一個(gè)參數(shù)為k的有限狀態(tài)自動(dòng)機(jī)，由一個(gè)的有限狀態(tài)自動(dòng)機(jī)，由一個(gè)輸出符號集輸出符號集Z、一一個(gè)狀態(tài)集個(gè)狀態(tài)集、兩個(gè)函數(shù)兩個(gè)函數(shù)和和以及一個(gè)以及一個(gè)初始狀態(tài)初始狀態(tài)0組成。組成。 狀態(tài)轉(zhuǎn)移函數(shù)狀態(tài)轉(zhuǎn)移函數(shù):ii+1：將當(dāng)前狀態(tài)將當(dāng)前狀態(tài)i變?yōu)橐粋€(gè)新狀態(tài)變?yōu)橐粋€(gè)新狀態(tài)i+1輸出函數(shù)輸出函數(shù):izi： 當(dāng)前狀態(tài)當(dāng)前狀態(tài)i變?yōu)檩敵龇柤械囊粋€(gè)元素變?yōu)檩敵龇柤?/p>

9、中的一個(gè)元素zi。2.1.3 密鑰流產(chǎn)生器密鑰流產(chǎn)生器密鑰流生成器設(shè)計(jì)的關(guān)鍵在于找出適當(dāng)?shù)拿荑€流生成器設(shè)計(jì)的關(guān)鍵在于找出適當(dāng)?shù)臓顟B(tài)轉(zhuǎn)移函數(shù)狀態(tài)轉(zhuǎn)移函數(shù)和和輸出函數(shù)輸出函數(shù)，使得輸出序列使得輸出序列z滿足密鑰流序列滿足密鑰流序列z應(yīng)滿足的幾個(gè)應(yīng)滿足的幾個(gè)條件，并且要求在條件，并且要求在設(shè)備上是節(jié)省的設(shè)備上是節(jié)省的和和容易實(shí)現(xiàn)的容易實(shí)現(xiàn)的。 為了實(shí)現(xiàn)這一目標(biāo)，必須采用為了實(shí)現(xiàn)這一目標(biāo)，必須采用非線性函數(shù)。非線性函數(shù)。 由于具有非線性的由于具有非線性的的有限狀態(tài)自動(dòng)機(jī)理論很不完善的有限狀態(tài)自動(dòng)機(jī)理論很不完善，相應(yīng)的密鑰流產(chǎn)生器的分析工作受到極大的限制。相應(yīng)的密鑰流產(chǎn)生器的分析工作受到極大的限制。 相

10、反地，當(dāng)采用相反地，當(dāng)采用線性的線性的和和非線性的非線性的時(shí)，將能夠進(jìn)行時(shí)，將能夠進(jìn)行深入的分析并可以得到好的生成器。深入的分析并可以得到好的生成器。 為方便討論，可將這類生成器分成為方便討論，可將這類生成器分成驅(qū)動(dòng)部分驅(qū)動(dòng)部分和和非線性非線性組合部分組合部分 驅(qū)動(dòng)部分驅(qū)動(dòng)部分控制生成器的狀態(tài)轉(zhuǎn)移，并為非線性組合部控制生成器的狀態(tài)轉(zhuǎn)移，并為非線性組合部分提供統(tǒng)計(jì)性能好的序列；分提供統(tǒng)計(jì)性能好的序列； 非線性組合部分非線性組合部分要利用這些序列組合出滿足要求的密要利用這些序列組合出滿足要求的密鑰流序列。鑰流序列。目前最為流行和實(shí)用的密鑰流產(chǎn)生器如圖目前最為流行和實(shí)用的密鑰流產(chǎn)生器如圖2.7所示，

11、其驅(qū)動(dòng)所示，其驅(qū)動(dòng)部分是一個(gè)或多個(gè)部分是一個(gè)或多個(gè)線性反饋移位寄存器線性反饋移位寄存器。圖圖2.7 常見的兩種密鑰流產(chǎn)生器常見的兩種密鑰流產(chǎn)生器移位寄存器移位寄存器是流密碼產(chǎn)生密鑰流的一個(gè)主要組成部分。是流密碼產(chǎn)生密鑰流的一個(gè)主要組成部分。GF(2)上一個(gè)上一個(gè)n級反饋移位寄存器級反饋移位寄存器由由n個(gè)二元存儲器個(gè)二元存儲器與一個(gè)與一個(gè)反反饋函數(shù)饋函數(shù)f(a1,a2,an)組成，如圖組成，如圖2.8所示。所示。圖圖2.8 GF(2)上的上的n級反饋移位寄存器級反饋移位寄存器2.2 線性反饋移位寄存器線性反饋移位寄存器 每一存儲器稱為移位寄存器的一級，在任一時(shí)刻，這每一存儲器稱為移位寄存器的一級

12、，在任一時(shí)刻，這些級的內(nèi)容構(gòu)成該反饋移位寄存器的狀態(tài)，每一狀態(tài)對應(yīng)些級的內(nèi)容構(gòu)成該反饋移位寄存器的狀態(tài)，每一狀態(tài)對應(yīng)于于GF(2)上的一個(gè)上的一個(gè)n維向量，共有維向量，共有2n種可能的狀態(tài)。種可能的狀態(tài)。每一時(shí)刻的狀態(tài)可用每一時(shí)刻的狀態(tài)可用n長序列長序列a1, a2, , an或或n維向量維向量(a1, a2, , an)表示，其中表示，其中ai是第是第i級存儲器的內(nèi)容。級存儲器的內(nèi)容。 初始狀態(tài)由用戶確定初始狀態(tài)由用戶確定，當(dāng)?shù)?，?dāng)?shù)趇個(gè)移位時(shí)鐘脈沖到來時(shí)，個(gè)移位時(shí)鐘脈沖到來時(shí)，每一級存儲器每一級存儲器ai都將其內(nèi)容向下一級都將其內(nèi)容向下一級ai-1傳遞，并根據(jù)寄存?zhèn)鬟f，并根據(jù)寄存器此時(shí)的狀

13、態(tài)器此時(shí)的狀態(tài)a1,a2,an計(jì)算計(jì)算f(a1,a2,an)，作為下一時(shí)刻的作為下一時(shí)刻的an。 反饋函數(shù)反饋函數(shù)f(a1,a2,an)是是n元布爾函數(shù)元布爾函數(shù)，即，即n個(gè)變元個(gè)變元a1,a2,an可以獨(dú)立地取可以獨(dú)立地取0和和1這兩個(gè)可能的值，函數(shù)中的運(yùn)算有邏輯這兩個(gè)可能的值，函數(shù)中的運(yùn)算有邏輯與、邏輯或、邏輯補(bǔ)等運(yùn)算，最后的函數(shù)值也為與、邏輯或、邏輯補(bǔ)等運(yùn)算，最后的函數(shù)值也為0或或1。例例2.2 圖圖2.9是一個(gè)是一個(gè)3級反饋移位寄存器，其初始狀態(tài)為級反饋移位寄存器，其初始狀態(tài)為(a1,a2,a3)=(1,0,1)，輸出可由表輸出可由表2.2求出。求出。圖圖2.9 一個(gè)一個(gè)3級反饋移位寄

14、存器級反饋移位寄存器狀態(tài)狀態(tài)（a3,a2,a1)輸出輸出1 0 11 1 01 1 10 1 11 0 11 1 0 101110表2.2 一個(gè)3級反饋移位反饋移位寄存器寄存器的狀態(tài)和輸出即輸出序列為即輸出序列為101110111011，周期為周期為4。 如果移位寄存器的反饋函數(shù)如果移位寄存器的反饋函數(shù)f(a1,a2,an)是是a1，a2，an的線性函的線性函數(shù)，則稱之為數(shù)，則稱之為線性反饋移位寄存器線性反饋移位寄存器LFSR（linear feedback shift register）。此時(shí)此時(shí)f可寫為可寫為f(a1,a2,an)=cna1 cn-1a2 c1an其中常數(shù)其中常數(shù)ci=0或

15、或1， 是模是模2加法加法, ci=0或或1。輸出序列輸出序列at滿足滿足an+t=cna t cn-1at+1 c1an+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)造密鑰流生成器的最重要的部件之一。件之一。例例2.3 圖圖2.11是一個(gè)是一個(gè)5級線性反饋移位寄存器，其初始狀態(tài)為級線性反饋移位寄存器，其初始狀態(tài)為（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出輸出序列為可求出輸出序列為100110100100001

16、0101110110001111100110周期為周期為31。圖圖2.11 一個(gè)一個(gè)5級線性反饋移位寄存器級線性反饋移位寄存器注：注： 總假定總假定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)必將一直持續(xù)下去。將一直持續(xù)下去。若只有一個(gè)系數(shù)不為若只有一個(gè)系數(shù)不為0，設(shè)僅有，設(shè)僅有cj不為不為0，實(shí)際上是一種延，實(shí)際上是一種延遲裝置。遲裝置。3) 一般對于一般對于n級線性反饋移位寄存器，總是假定級線性反饋移位寄存器，總是假定cn=1。輸出序列的性質(zhì)輸出序列的性

17、質(zhì)完全由其反饋函數(shù)決定完全由其反饋函數(shù)決定。最多有最多有2n個(gè)不同的狀態(tài)。個(gè)不同的狀態(tài)。狀態(tài)周期小于等于狀態(tài)周期小于等于2n-1。若其初始狀態(tài)為若其初始狀態(tài)為0，則其狀態(tài)恒為，則其狀態(tài)恒為0。若其初始狀態(tài)非。若其初始狀態(tài)非0，則，則其后繼狀態(tài)不會為其后繼狀態(tài)不會為0。因此其。因此其輸出序列的周期與狀態(tài)周期相輸出序列的周期與狀態(tài)周期相等，也小于等于等，也小于等于2n-1。只要選擇合適的反饋函數(shù)便可使序列的周期達(dá)到最大值只要選擇合適的反饋函數(shù)便可使序列的周期達(dá)到最大值2n-1，周期達(dá)到最大值的序列稱為周期達(dá)到最大值的序列稱為m序列序列。設(shè)設(shè)n級線性移位寄存器的輸出序列滿足遞推關(guān)系級線性移位寄存器的

18、輸出序列滿足遞推關(guān)系an+k=c1an+k-1 c2an+k-2 cnak (*)對任何成立。這種遞推關(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)式或或特征多項(xiàng)式特征多項(xiàng)式。2.3 線性移位寄存器的一元多項(xiàng)式表示線性移位寄存器的一元多項(xiàng)式表示由于由于a ai iGF(2) (i=1,2,n)GF(2) (i=1,2,n)，所以共有所以共有2 2n n組初始狀態(tài)，組初始狀態(tài)，即有即有2 2n n個(gè)遞推序列個(gè)遞推序列，其中非恒零的有，其中非恒零的有2 2n

19、 n-1-1個(gè)，記個(gè)，記2 2n n-1-1個(gè)非個(gè)非零序列的全體為零序列的全體為G(p(x)G(p(x)。定義定義2.1 給定序列給定序列ai，冪級數(shù)冪級數(shù)A(x)=aixi-1稱為該序列的生成函數(shù)。稱為該序列的生成函數(shù)。定理定理2.1設(shè)設(shè)p(x)=1+c1x+cn-1xn-1+cnxn是是GF(2)上的多項(xiàng)式，上的多項(xiàng)式，G(p(x)中任一序列中任一序列ai的生成函數(shù)的生成函數(shù)A(x)滿足：滿足： A(x)= (x)/p(x)其中其中 (x)=cn-ixn-iajxj-1證明：證明： 在等式在等式an+1=c1an c2an-1 cna1an+2=c1an+1 c2an cna2 兩邊分別乘

20、以兩邊分別乘以xn,xn+1,，再求和，可得再求和，可得A(x)-(a1+a2x+anxn-1)=c1xA(x)-(a1+a2x+an-1xn-2)+c2x2A(x)-(a1+a2x+an-2xn-3)+cnxnA(x)移項(xiàng)整理得移項(xiàng)整理得(1+c1x+cn-1xn-1+cnxn)A(x)=(a1+a2x+anxn-1)+c1x(a1+a2x+an-1xn-2)+c2x2(a1+a2x+an-2xn-3)+cn-1xn-1a1即即p(x)A(x)=cn-ixn-iajxj-1= (x) (證畢證畢)注意在注意在GF(2)上有上有a+a=0。定理定理2.2 p(x)|q(x)的充要條件是的充要條

21、件是G(p(x) G(q(x)。證明：若證明：若p(x)|q(x)，可設(shè)可設(shè)q(x)=p(x)r(x)，因此因此A(x)= (x)/p(x)= (x)r(x)/p(x)r(x)= (x)r(x)/q(x)所以若所以若aiG(p(x)，則則aiG(q(x)，即即G(p(x) G(q(x)。反之，若反之，若G(p(x) G(q(x)，則對于多項(xiàng)式則對于多項(xiàng)式 (x)，存在序存在序列列aiG(p(x)以以A(x)= (x)/p(x)為生成函數(shù)。為生成函數(shù)。特別地，對于多項(xiàng)式特別地，對于多項(xiàng)式 (x)=1，存在序列存在序列aiG(p(x)以以1/p(x)為生成函數(shù)。由于為生成函數(shù)。由于G(p(x) G

22、(q(x)，序列序列aiG(q(x)，所以存在函數(shù)所以存在函數(shù)r(x)，使得使得ai的生成函數(shù)也等的生成函數(shù)也等于于r(x)/q(x)，從而從而1/p(x)=r(x)/q(x)，即即q(x)=p(x)r(x)，所以所以p(x)|q(x)。(證畢證畢)上述定理說明可用上述定理說明可用n級級LFSR產(chǎn)生的序列，也可用級數(shù)更多產(chǎn)生的序列，也可用級數(shù)更多的的LFSR來產(chǎn)生。來產(chǎn)生。定義定義2.2 設(shè)設(shè)p(x)是是GF(2)上的多項(xiàng)式，使上的多項(xiàng)式，使p(x)|(xp-1)的的最小最小p稱為稱為p(x)的周期或階。的周期或階。定理定理2.3 若序列若序列ai的特征多項(xiàng)式的特征多項(xiàng)式p(x)定義在定義在G

23、F(2)上，上，p是是p(x)的周期，則的周期，則ai的周期的周期r|p。證明：由證明：由p(x)周期的定義得周期的定義得p(x)|(xp-1)，因此存在因此存在q(x)，使得使得xp-1=p(x)q(x)，又由又由p(x)A(x)= (x)可得可得p(x)q(x)A(x)= (x)q(x)，所以所以(xp-1)A(x)= (x)q(x)。 由于由于q(x)的次數(shù)為的次數(shù)為p-n， (x)的次數(shù)不超過的次數(shù)不超過n-1，所以所以(xp-1)A(x)的次數(shù)不超過的次數(shù)不超過(p-n)+(n-1)=p-1。則有：對于任意正整數(shù)則有：對于任意正整數(shù) i, 都有都有ai+p=ai。設(shè)設(shè)p=kr+t,0

24、tr，則則ai+p=ai+kr+t=ai+t=ai，所以所以t=0，即即r|p。（證畢）證畢）n級級LFSR輸出序列的周期輸出序列的周期r不依賴于初始條件，而依賴不依賴于初始條件，而依賴于特征多項(xiàng)式于特征多項(xiàng)式p(x)。我們感興趣的是我們感興趣的是LFSR遍歷遍歷2n-1個(gè)非零狀態(tài)，這時(shí)序列的個(gè)非零狀態(tài)，這時(shí)序列的周期達(dá)到最大周期達(dá)到最大2n-1，這種序列就是這種序列就是m序列序列。顯然顯然, 對于特征多項(xiàng)式一樣，而僅初始條件不同的兩個(gè)對于特征多項(xiàng)式一樣，而僅初始條件不同的兩個(gè)輸出序列，一個(gè)記為輸出序列，一個(gè)記為a(1)i，另一個(gè)記為另一個(gè)記為a(2)i，其中一個(gè)必其中一個(gè)必是另一個(gè)的移位，即

25、存在一個(gè)常數(shù)是另一個(gè)的移位，即存在一個(gè)常數(shù)k，使得使得a(1)i=a(2)k+i, i=1,2,下面討論特征多項(xiàng)式滿足什么條件時(shí)，下面討論特征多項(xiàng)式滿足什么條件時(shí)，LFSR的的輸出序列為輸出序列為m序列。序列。定理定理2.4 設(shè)設(shè)p(x)是是n次不可約多項(xiàng)式，周期為次不可約多項(xiàng)式，周期為m，序列序列aiG(p(x)，則則ai的周期為的周期為m。證明：設(shè)證明：設(shè)ai的周期為的周期為r，由定理由定理2.3有有r|m，所以所以rm。設(shè)設(shè)A(x)為為ai的生成函數(shù)，的生成函數(shù)，A(x)= (x)/p(x)，即即p(x)A(x)= (x)0， (x)的數(shù)不超過的數(shù)不超過n-1。而而A(x)=aixi-1

26、=a1+a2x+arxr-1+xr(a1+a2x+arxr-1) +(xr)2(a1+a2x+arxr-1)+=a1+a2x+arxr-1/(1-xr)=a1+a2x+arxr-1/(xr-1)于是于是A(x)=a1+a2x+arxr-1/(xr-1)= (x)p(x)，即即p(x)(a1+a2x+arxr-1)= (x)(xr-1) 因因p(x)是不可約的，所以是不可約的，所以gcd(p(x), (x)=1，p(x)|(xr-1)，因此因此 mr。綜上綜上r=m。（。（證畢）證畢）定理定理2.5 n級級LFSR產(chǎn)生的序列有最大周期產(chǎn)生的序列有最大周期2n-1的必要條件的必要條件是其特征多項(xiàng)式

27、為不可約的。是其特征多項(xiàng)式為不可約的。證明：設(shè)證明：設(shè)n級級LFSR產(chǎn)生的序列周期達(dá)到最大產(chǎn)生的序列周期達(dá)到最大2n-1，除除0序序列外，每一序列的周期由特征多項(xiàng)式惟一決定，而與初始列外，每一序列的周期由特征多項(xiàng)式惟一決定，而與初始狀態(tài)無關(guān)。狀態(tài)無關(guān)。設(shè)特征多項(xiàng)式為設(shè)特征多項(xiàng)式為p(x)，若若p(x)可約，可設(shè)為可約，可設(shè)為p(x)=g(x)h(x)，其中其中g(shù)(x)不可約，且次數(shù)不可約，且次數(shù)k2，當(dāng)當(dāng)1in-2時(shí)，時(shí)，n長長m序列的一個(gè)周期內(nèi)，長為序列的一個(gè)周期內(nèi)，長為i的的0游程數(shù)目等于序列中如下形式的狀態(tài)數(shù)目：游程數(shù)目等于序列中如下形式的狀態(tài)數(shù)目： 10001*，其中，其中n-i-2個(gè)

28、個(gè)*可任取可任取0或或1。這種狀態(tài)共有這種狀態(tài)共有2n-i-2個(gè)。個(gè)。同理可得長為同理可得長為i的的1游程數(shù)目也等于游程數(shù)目也等于 2n-i-2，所以長為所以長為i的的游程總數(shù)為游程總數(shù)為2n-i-1。由于寄存器中不會出現(xiàn)全由于寄存器中不會出現(xiàn)全0狀態(tài)，所以不會出現(xiàn)狀態(tài)，所以不會出現(xiàn)0的的n游程，游程，但必有一個(gè)但必有一個(gè)1的的n游程，而且游程，而且1的游程不會更大，因?yàn)槿舫霈F(xiàn)的游程不會更大，因?yàn)槿舫霈F(xiàn)1的的n+1游程，就必然有兩個(gè)相鄰的全游程，就必然有兩個(gè)相鄰的全1狀態(tài)，但這是不可能狀態(tài)，但這是不可能的。這就證明了的。這就證明了1的的n游程必然出現(xiàn)在如下的串中：游程必然出現(xiàn)在如下的串中：當(dāng)這

29、當(dāng)這n+2位通過移位寄存器時(shí)，便依次產(chǎn)生以下狀態(tài)：位通過移位寄存器時(shí)，便依次產(chǎn)生以下狀態(tài)： 10 111 0n個(gè)110 111n個(gè)1111n個(gè)11111 0n個(gè)由于由于 ， 這兩個(gè)狀態(tài)只能各出現(xiàn)這兩個(gè)狀態(tài)只能各出現(xiàn)一次，所以不會有一次，所以不會有1的的n-1游程。游程。于是在一個(gè)周期內(nèi)，總游程數(shù)為于是在一個(gè)周期內(nèi)，總游程數(shù)為110 111n個(gè)11111 0n個(gè)21111 122nn ini ai是周期為是周期為2n-1的的m序列，對于任一正整數(shù)序列，對于任一正整數(shù)(02n-1)，ai+ai+在一個(gè)周期內(nèi)為在一個(gè)周期內(nèi)為0的位的數(shù)目正好是序列的位的數(shù)目正好是序列ai和和ai+對應(yīng)位相同的位的數(shù)目

30、。對應(yīng)位相同的位的數(shù)目。設(shè)序列設(shè)序列ai滿足遞推關(guān)系：滿足遞推關(guān)系： ah+n=c1ah+n-1 c2ah+n-2 cnah故故ah+n+=c1ah+n+-1 c2ah+n+-2 cnah+ ah+n ah+n+=c1(ah+n-1 ah+n+-1) c2(ah+n-2 ah+n+-2) cn(ah ah+) 令令bj=aj aj+，由遞推序列由遞推序列ai可推得遞推序列可推得遞推序列bi，bi滿滿足足bh+n=c1bh+n-1 c2bh+n-2 cnbhbi也是也是m序列。為了計(jì)算序列。為了計(jì)算R()，只要用只要用bi在一個(gè)周期中在一個(gè)周期中0的個(gè)數(shù)減去的個(gè)數(shù)減去1的個(gè)數(shù)，再除以的個(gè)數(shù)，再除

31、以2n-1，即即（證畢）（證畢） 1121212121nnnnR 上面說過，有限域上的二元加法流密碼（如圖上面說過，有限域上的二元加法流密碼（如圖2.3）是目前）是目前最為常用的流密碼體制，設(shè)滾動(dòng)密鑰生成器是線性反饋移最為常用的流密碼體制，設(shè)滾動(dòng)密鑰生成器是線性反饋移位寄存器，產(chǎn)生的密鑰是序列。又設(shè)和是序列中兩個(gè)連續(xù)位寄存器，產(chǎn)生的密鑰是序列。又設(shè)和是序列中兩個(gè)連續(xù)的長向量，其中的長向量，其中2.5 m序列密碼的破譯序列密碼的破譯11211,hhhhhhh nh naaaaSSaa 設(shè)序列設(shè)序列ai滿足線性遞推關(guān)系：滿足線性遞推關(guān)系：可表示為可表示為1122h nh nh nnhac ac a

32、c a 12112110 1 000 0 10hhhhnnnh nh naaaaccccaa 或或Sh+1=MSh，其中其中又設(shè)敵手知道一段長為又設(shè)敵手知道一段長為2n的明密文對，即已知的明密文對，即已知12101000010ccccMnnn122nxx xx122nyy yy于是可求出一段長為于是可求出一段長為2n的密鑰序列的密鑰序列其中其中 ,由此可推出線性反由此可推出線性反饋移位寄存器連續(xù)的饋移位寄存器連續(xù)的n+1個(gè)狀態(tài)：個(gè)狀態(tài)：1 22nzz zziiiiiizxyxxz11 21222312311122122nnnnnnnnnnnSz zza aaSz zza aaSzzzaaa記為

33、記為記為做矩陣做矩陣而而若若X可逆，則可逆，則12nXSSS122311221112111nnnnnnnnnnnnaaaaaaaaacccaaacccX111122nnnnncccaaaX下面證明下面證明X的確是可逆的。的確是可逆的。因?yàn)橐驗(yàn)閄是由是由S1,S2,Sn作為列向量，要證作為列向量，要證X可逆，只要證明這可逆，只要證明這n個(gè)向量線性無關(guān)。個(gè)向量線性無關(guān)。由序列遞推關(guān)系：由序列遞推關(guān)系：可推出向量的遞推關(guān)系：可推出向量的遞推關(guān)系：1122h nh nh nnhac ac ac a 11221mod2nh nh nh nnhih n iiSc Sc Sc Sc S 設(shè)設(shè)m(mn+1)是

34、使是使S1,S2,Sm線性相關(guān)的最小整數(shù)，即存在線性相關(guān)的最小整數(shù)，即存在不全為不全為0的系數(shù)的系數(shù)l1,l2,lm，其中不妨設(shè)其中不妨設(shè)l1=1，使得使得即即對于任一整數(shù)對于任一整數(shù)i有有213210mmmmSl Sl Sl S11122111mmmmmjmjjSl SlSl SlS122111221112211imimimmiimimmmmimiimSlSlSlSMlSMlSMlSlSlSlMSMS由此又推出密鑰流的遞推關(guān)系：由此又推出密鑰流的遞推關(guān)系：即密鑰流的級數(shù)小于即密鑰流的級數(shù)小于m。若若mn，則得出密鑰流的級數(shù)小于則得出密鑰流的級數(shù)小于n，矛盾。所以矛盾。所以m=n+1，從而矩陣

35、從而矩陣X必是可逆的。必是可逆的。21321m im im imial al al a 例例2.6 設(shè)敵手得到密文串設(shè)敵手得到密文串101101011110010和相應(yīng)的明文串和相應(yīng)的明文串011001111111001，因此可計(jì)算出相應(yīng)的密鑰流為，因此可計(jì)算出相應(yīng)的密鑰流為110100100001011。進(jìn)一步假定敵手還知道密鑰流是使用。進(jìn)一步假定敵手還知道密鑰流是使用5級線性反饋移位寄存器產(chǎn)生的，那么敵手可分別用密文串級線性反饋移位寄存器產(chǎn)生的，那么敵手可分別用密文串中的前中的前10個(gè)比特和明文串中的前個(gè)比特和明文串中的前10個(gè)比特建立如下方程個(gè)比特建立如下方程12345234566789

36、1054321345674567856789aaaaaaaaaaaaaaacccccaaaaaaaaaaaaaaa即即而而543211 1 0 1 01 0 1 0 00 1 0 0 00 1 0 0 11 0 0 1 00 0 1 0 0ccccc11 1 0 1 00 1 0 0 11 0 1 0 01 0 0 1 00 1 0 0 10 0 0 0 11 0 0 1 00 1 0 1 10 0 1 0 01 0 1 1 0從而得到從而得到所以所以密鑰流的遞推關(guān)系為密鑰流的遞推關(guān)系為543210 1 0 0 11 0 0 1 00 1 0 0 00 0 0 0 10 1 0 1 11 0

37、1 1 0ccccc543211 0 0 1 0ccccc55233iiiiiac ac aaa在在2.1.3節(jié)已介紹密鑰流生成器可分解為節(jié)已介紹密鑰流生成器可分解為驅(qū)動(dòng)子系統(tǒng)驅(qū)動(dòng)子系統(tǒng)和和非線非線性組合子系統(tǒng)性組合子系統(tǒng)，如圖，如圖2.6所示。所示。驅(qū)動(dòng)子系統(tǒng)常用一個(gè)或多個(gè)驅(qū)動(dòng)子系統(tǒng)常用一個(gè)或多個(gè)線性反饋移位寄存器線性反饋移位寄存器來實(shí)現(xiàn)，來實(shí)現(xiàn)，非線性組合子系統(tǒng)用非線性組合函數(shù)非線性組合子系統(tǒng)用非線性組合函數(shù)F來實(shí)現(xiàn)，如圖來實(shí)現(xiàn)，如圖2.7所所示。示。本節(jié)介紹第本節(jié)介紹第2部分非線性組合子系統(tǒng)。部分非線性組合子系統(tǒng)。2.6 非線性序列非線性序列 為了使密鑰流生成器輸出的二元序列盡可能復(fù)雜，

38、應(yīng)為了使密鑰流生成器輸出的二元序列盡可能復(fù)雜，應(yīng)保證其保證其周期盡可能大周期盡可能大、線性復(fù)雜度和不可預(yù)測性盡可能高線性復(fù)雜度和不可預(yù)測性盡可能高，因此常使用多個(gè)因此常使用多個(gè)LFSR來構(gòu)造二元序列，稱每個(gè)來構(gòu)造二元序列，稱每個(gè)LFSR的輸?shù)妮敵鲂蛄袨轵?qū)動(dòng)序列。出序列為驅(qū)動(dòng)序列。 顯然，密鑰流生成器輸出序列的周期不大于各驅(qū)動(dòng)序顯然，密鑰流生成器輸出序列的周期不大于各驅(qū)動(dòng)序列周期的乘積，因此，列周期的乘積，因此，提高輸出序列的線性復(fù)雜度應(yīng)從極提高輸出序列的線性復(fù)雜度應(yīng)從極大化其周期開始大化其周期開始。 二元序列的線性復(fù)雜度指二元序列的線性復(fù)雜度指生成該序列的最短生成該序列的最短LFSR的級的級數(shù)

39、數(shù)，最短最短LFSR的特征多項(xiàng)式稱為二元序列的極小特征多項(xiàng)的特征多項(xiàng)式稱為二元序列的極小特征多項(xiàng)式式。下面介紹下面介紹4種由多個(gè)種由多個(gè)LFSR驅(qū)動(dòng)的非線性序列生成器。驅(qū)動(dòng)的非線性序列生成器。Geffe序列生成器由序列生成器由3個(gè)個(gè)LFSR組成，其中組成，其中LFSR2作為控制生作為控制生成器使用，如圖成器使用，如圖2.12所示。所示。圖圖2.12 Geffe序列生成器圖序列生成器圖2.6.1 Geffe序列生成器序列生成器當(dāng)當(dāng)LFSR2輸出輸出1時(shí)，時(shí)，LFSR2與與LFSR1相連接；相連接；當(dāng)當(dāng)LFSR2輸出輸出0時(shí)，時(shí)，LFSR2與與LFSR3相連接。相連接。若設(shè)若設(shè)LFSRi的輸出序列

40、為的輸出序列為a(i)k (i=1,2,3)，則輸出序列則輸出序列bk可可以表示為以表示為 123212323kkkkkkkkkkba aaaa aaaaGeffe序列生成器也可以表示為圖序列生成器也可以表示為圖2.13的形式，其中的形式，其中LFSR1和和LFSR3作為多路復(fù)合器的輸入作為多路復(fù)合器的輸入LFSR2控制多路復(fù)合器的輸出控制多路復(fù)合器的輸出圖圖2.13 多路復(fù)合器表示的多路復(fù)合器表示的Geffe序列生成器序列生成器設(shè)設(shè)LFSRi的特征多項(xiàng)式分別為的特征多項(xiàng)式分別為ni次本原多項(xiàng)式，且次本原多項(xiàng)式，且ni兩兩互兩兩互素，則素，則Geffe序列的周期為序列的周期為線性復(fù)雜度為線性復(fù)

41、雜度為Geffe序列的周期實(shí)現(xiàn)了極大化，且序列的周期實(shí)現(xiàn)了極大化，且0與與1之間的分布大體上之間的分布大體上是平衡的。是平衡的。3121ini1323nnnnJ-K觸發(fā)器如圖觸發(fā)器如圖2.14所示，它的兩個(gè)輸入端分別用所示，它的兩個(gè)輸入端分別用J和和K表示，表示，其輸出其輸出ck不僅依賴于輸入，還依賴于前一個(gè)輸出位不僅依賴于輸入，還依賴于前一個(gè)輸出位ck-1，即即其中其中x1和和x2分別是分別是J和和K端的輸入。端的輸入。圖圖2.14 J-K觸發(fā)器觸發(fā)器2.6.2 J-K觸發(fā)器觸發(fā)器1211kkcxxcx由此可得由此可得J-K觸發(fā)器的真值表，如表觸發(fā)器的真值表，如表2.3。JKck00ck-1

42、010101111kc利用利用J-K觸發(fā)器的非線性序列生成器見圖觸發(fā)器的非線性序列生成器見圖2.15。圖圖2.15 利用利用J-K觸發(fā)器的非線性序列生成器觸發(fā)器的非線性序列生成器在圖在圖2.15中，令驅(qū)動(dòng)序列中，令驅(qū)動(dòng)序列ak和和bk分別為分別為m級和級和n級級m序列，序列，則有則有如果令如果令c-1=0，則輸出序列的最初則輸出序列的最初3項(xiàng)為項(xiàng)為m與與n互素且互素且a0+b0=1時(shí)，序列時(shí)，序列ck的周期為的周期為(2m-1)(2n-1)。111kkkkkkkkkcabcaabca001110122211012111cacabaacababaaa例例2.7 令令m=2,n=3，兩個(gè)驅(qū)動(dòng)兩個(gè)驅(qū)

43、動(dòng)m序列分別為序列分別為ak=0,1,1,和和bk=1,0,0,1,0,1,1,于是，輸出序列于是，輸出序列ck是是0,1,1,0,1,0,0,1,1,1,0,1,0,1,0,0,1,0,0,1,0,其周期為其周期為(22-1)(23-1)=21。由表達(dá)式由表達(dá)式ck=(ak+bk+1)ck-1+ak可得可得因此，如果知道因此，如果知道ck中相鄰位的值中相鄰位的值ck-1和和ck，就可以推斷出就可以推斷出ak和和bk中的一個(gè)。而一旦知道足夠多的這類信息，就可通過中的一個(gè)。而一旦知道足夠多的這類信息，就可通過密碼分析的方法得到序列密碼分析的方法得到序列ak和和bk。 為了克服上述缺點(diǎn)，為了克服上

44、述缺點(diǎn)，Pless提出了由多個(gè)提出了由多個(gè)J-K觸發(fā)器序觸發(fā)器序列驅(qū)動(dòng)的多路復(fù)合序列方案，稱為列驅(qū)動(dòng)的多路復(fù)合序列方案，稱為Pless生成器生成器。11,0,1kkkkkaccbcPless生成器由生成器由8個(gè)個(gè)LFSR、4個(gè)個(gè)J-K觸發(fā)器和觸發(fā)器和1個(gè)循環(huán)計(jì)數(shù)器構(gòu)個(gè)循環(huán)計(jì)數(shù)器構(gòu)成，由循環(huán)計(jì)數(shù)器進(jìn)行選通控制，如圖成，由循環(huán)計(jì)數(shù)器進(jìn)行選通控制，如圖2.16所示。假定在時(shí)所示。假定在時(shí)刻刻t輸出第輸出第t(mod 4)個(gè)單元，則輸出序列為個(gè)單元，則輸出序列為a0b1c2d3a4b5d62.6.3 Pless生成器生成器圖圖2.16 Pless生成器生成器鐘控序列最基本的模型是用一個(gè)鐘控序列最基本的

45、模型是用一個(gè)LFSR控制另外一個(gè)控制另外一個(gè)LFSR的移位時(shí)鐘脈沖，如圖的移位時(shí)鐘脈沖，如圖2.17所示。所示。圖圖2.17 最簡單的鐘控序列生成器最簡單的鐘控序列生成器2.6.4 鐘控序列生成器鐘控序列生成器假設(shè)假設(shè)LFSR1和和LFSR2分別輸出序列分別輸出序列ak和和bk，其周期分別其周期分別為為p1和和p2。當(dāng)當(dāng)LFSR1輸出輸出1時(shí)，移位時(shí)鐘脈沖通過與門使時(shí)，移位時(shí)鐘脈沖通過與門使LFSR2進(jìn)行一進(jìn)行一次移位，從而生成下一位。次移位，從而生成下一位。當(dāng)當(dāng)LFSR1輸出輸出0時(shí)，移位時(shí)鐘脈沖無法通過與門影響時(shí)，移位時(shí)鐘脈沖無法通過與門影響LFSR2。因此因此LFSR2重復(fù)輸出前一位。重

46、復(fù)輸出前一位。假設(shè)鐘控序列假設(shè)鐘控序列ck的周期為的周期為p，可得如下關(guān)系：可得如下關(guān)系：其中其中 。1212gcd,p ppwp1110piiwa又設(shè)又設(shè)ak和和bk的極小特征多項(xiàng)式分別為的極小特征多項(xiàng)式分別為GF(2)上的上的m和和n次次本原多項(xiàng)式本原多項(xiàng)式f1(x)和和f2(x)，且且m|n。因此，因此，p1=2m-1, p2=2n-1。又知又知w1=2m-1， 因此因此gcd(w1,p2)=1，所以所以p=p1p2=(2m-1)(2n-1)。此外，也可推導(dǎo)出此外，也可推導(dǎo)出ck的線性復(fù)雜度為的線性復(fù)雜度為n(2m-1)，極小特征多極小特征多項(xiàng)式為項(xiàng)式為 。212mfx例例2.8 設(shè)設(shè)LFSR1為為3級級m序列生成器，其特征多項(xiàng)式為序列生成器，其特征多項(xiàng)式為f1(