第4章有關(guān)序列密碼和移位寄存器4.1引言4.2序列密碼的一般原理4.3線性移位寄存器4.4線性移位寄存器的一元多項式表示4.5m序列的偽隨機性4.6m序列密碼的破譯4.7非線性序列習(xí)題第4章有關(guān)序列密碼和移位寄存器4.1引言14.1引言人們試圖用序列密碼方式仿效”一次一密”密碼.從而促成了序列密碼的研究和發(fā)展.序列密碼是世界軍事,外交等領(lǐng)域應(yīng)用的主流密碼體制.在通常的序列密碼中,加解密用的密鑰序列是偽隨機序列,它的產(chǎn)生容易且有較成熟的理論工具,所以序列密碼是當前通用的密碼系統(tǒng).序列密碼的安全性主要依賴于密鑰序列,因而什么樣的偽隨機序列是安全可靠的密鑰序列,以及如何實現(xiàn)這種序列就成了序列密碼中研究的一個主要方面.4.1引言人們試圖用序列密碼方式仿效2序列密碼的基本思想是利用一個短密鑰k通過一個算法來產(chǎn)生一個密鑰流k=k0k1…，并使用如下規(guī)則對明文串m=m0m1m2…加密：c=c0c1c2…=Ek0(m0)Ek1(m1)Ek2(m2)…。密鑰流由密鑰流發(fā)生器A產(chǎn)生：k0k1…=A(k)，4.2序列密碼的一般原理序列密碼的基本思想是利用一個短密鑰k通過一個算法來產(chǎn)生一個密3

二進制序列密碼體制模型第4章(序列密碼)課件4由此可見,序列密碼的安全性主要依賴于密鑰序列k0k1…=A(k)，當k0k1…是離散無記憶的隨機序列時,則該系統(tǒng)就是一次一密密碼,它是不可破的.但通常A(k)是一個由k通過確定性算法產(chǎn)生的偽隨機序列,因而此時,該系統(tǒng)就不再是完全保密的.設(shè)計序列密碼的關(guān)鍵是設(shè)計密鑰序列A(k)，密鑰序列A(k)的設(shè)計應(yīng)考慮如下幾個因素:(1)系統(tǒng)的安全保密性;(2)密鑰k易于分配、保管，更換簡便；(3)產(chǎn)生密鑰序列簡單快速。目前最為流行和實用的密鑰流產(chǎn)生器，其驅(qū)動部分是一個或多個線性反饋移位寄存器。由此可見,序列密碼的安全性主要依賴于密鑰序列k0k1…=A5常見的兩種密鑰流產(chǎn)生器第4章(序列密碼)課件6因為確定性算法產(chǎn)生的序列是周期的或準周期的，為了使序列密碼達到要求的安全保密性，使得密鑰經(jīng)其擴展成的密鑰流序列具有如下性質(zhì)：極大的周期、良好的統(tǒng)計特性、抗線性分析、抗統(tǒng)計分析。

我們僅對實用中最感興趣的二元情形即GF(2)上的序列密碼原理進行介紹，但其理論是可以在任何有限域GF(q)中進行研究的。因為確定性算法產(chǎn)生的序列是周期的或準周期的，為了使序列密碼達7移位寄存器是序列密碼產(chǎn)生密鑰流的一個主要組成部分。GF(2)上一個n級反饋移位寄存器由n個二元存儲器與一個反饋函數(shù)f(a1,a2,…,an)組成，如圖4.2所示。2.2線性反饋移位寄存器移位寄存器是序列密碼產(chǎn)生密鑰流的一個主要組成部分。GF(2)8圖4.2GF(2)上的n級反饋移位寄存器第4章(序列密碼)課件9每一存儲器稱為移位寄存器的一級，在任一時刻，這些級的內(nèi)容構(gòu)成該反饋移位寄存器的狀態(tài)，每一狀態(tài)對應(yīng)于GF(2)上的一個n維向量，共有2n種可能的狀態(tài)。每一時刻的狀態(tài)可用n長序列a1,a2,…,an或n維向量(a1,a2,…,an)表示，其中ai是第i級存儲器的內(nèi)容。每一存儲器稱為移位寄存器的一級，在任一時刻，這些級的內(nèi)容構(gòu)成10初始狀態(tài)由用戶確定，當?shù)趇個移位時鐘脈沖到來時，每一級存儲器ai都將其內(nèi)容向下一級ai-1傳遞，并根據(jù)寄存器此時的狀態(tài)a1,a2,…,an計算f(a1,a2,…,an)，作為下一時刻的an。反饋函數(shù)f(a1,a2,…,an)是n元布爾函數(shù)，即n個變元a1,a2,…,an可以獨立地取0和1這兩個可能的值，函數(shù)中的運算有邏輯與、邏輯或、邏輯補等運算，最后的函數(shù)值也為0或1。初始狀態(tài)由用戶確定，當?shù)趇個移位時鐘脈沖到來時，每一級存儲器11例4.1圖4-3是一個3級反饋移位寄存器，其初始狀態(tài)為(a1,a2,a3)=(1,0,1)，求出輸出序列。例4.1圖4-3是一個3級反饋移位寄存器，其初始狀態(tài)為(12圖4-3一個3級反饋移位寄存器第4章(序列密碼)課件13一個3級反饋移位寄存器的狀態(tài)和輸出狀態(tài)（a1,a2,a3)輸出101110111011101110

101110一個3級反饋移位寄存器狀態(tài)（a1,a2,a3)輸出1014即輸出序列為101110111011…，周期為4。如果移位寄存器的反饋函數(shù)f(a1,a2,…,an)是a1，a2，…，an的線性函數(shù)，則稱之為線性反饋移位寄存器LFSR（linearfeedbackshiftregister）。此時f可寫為f(a1,a2,…,an)=cna1cn-1a2…c1an其中常數(shù)ci=0或1，是模2加法。ci=0或1可用開關(guān)的斷開和閉合來實現(xiàn)，如圖4-4所示。即輸出序列為101110111011…，周期為4。15圖4-4GF(2)上的n級線性反饋移位寄存器第4章(序列密碼)課件16輸出序列{at}滿足an+t=cnatcn-1at+1…c1an+t-1其中t為非負正整數(shù)。線性反饋移位寄存器因其實現(xiàn)簡單、速度快、有較為成熟的理論等優(yōu)點而成為構(gòu)造密鑰流生成器的最重要的部件之一。輸出序列{at}滿足17例4.2圖4-5是一個5級線性反饋移位寄存器，其初始狀態(tài)為（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出輸出序列為1001101001000010101110110001111100110…周期為31。例4.2圖4-5是一個5級線性反饋移位寄存器，其初始狀態(tài)為18圖4-5一個5級線性反饋移位寄存器第4章(序列密碼)課件19在線性反饋移位寄存器中總是假定c1,c2,…,cn中至少有一個不為0，否則f(a1,a2,…,an)≡0，這樣的話，在n個脈沖后狀態(tài)必然是00…0，且這個狀態(tài)必將一直持續(xù)下去。若只有一個系數(shù)不為0，設(shè)僅有cj不為0，實際上是一種延遲裝置。一般對于n級線性反饋移位寄存器，總是假定cn=1。在線性反饋移位寄存器中總是假定c1,c2,…,cn中至少有一20線性反饋移位寄存器輸出序列的性質(zhì)完全由其反饋函數(shù)決定。n級線性反饋移位寄存器最多有2n個不同的狀態(tài)。若其初始狀態(tài)為0，則其狀態(tài)恒為0。若其初始狀態(tài)非0，則其后繼狀態(tài)不會為0。因此n級線性反饋移位寄存器的狀態(tài)周期小于等于2n-1。其輸出序列的周期與狀態(tài)周期相等，也小于等于2n-1。只要選擇合適的反饋函數(shù)便可使序列的周期達到最大值2n-1，周期達到最大值的序列稱為m序列。線性反饋移位寄存器輸出序列的性質(zhì)完全由其反饋函數(shù)決定。n級線21設(shè)n級線性移位寄存器的輸出序列滿足遞推關(guān)系an+k=c1an+k-1c2an+k-2

…cnak(*)對任何成立。這種遞推關(guān)系可用一個一元高次多項式P(x)=1+c1x+…＋cn-1xn-1＋cnxn表示，稱這個多項式為LFSR的聯(lián)系多項式或特征多項式。4.4線性移位寄存器的一元多項式表示設(shè)n級線性移位寄存器的輸出序列滿足遞推關(guān)系4.4線性移位22設(shè)n級線性移位寄存器對應(yīng)于遞推關(guān)系(*)，由于ai∈GF(2)(i=1,2,…,n)，所以共有2n組初始狀態(tài)，即有2n個遞推序列，其中非恒為零的序列有2n-1個，記2n-1個非零序列的全體為G(p(x))。設(shè)n級線性移位寄存器對應(yīng)于遞推關(guān)系(*)，由于ai∈GF(223定義給定序列{ai}，冪級數(shù)A(x)=∑aixi-1稱為該序列的生成函數(shù)或母函數(shù)。

定義給定序列{ai}，冪級數(shù)24定理4.1設(shè)p(x)=1+c1x+…+cn-1xn-1+cnxn是GF(2)上的多項式，G(p(x))中任一序列{ai}的生成函數(shù)A(x)滿足：A(x)=(x)/p(x)其中定理4.1設(shè)p(x)=1+c1x+…+cn-1xn-125證明：在等式an+1=c1anc2an-1…cna1an+2=c1an+1c2an…cna2

…兩邊分別乘以xn,xn+1,…，再求和，可得 A(x)-(a1+a2x+…+anxn-1) =c1x[A(x)-(a1+a2x+…+an-1xn-2)] +c2x2[A(x)-(a1+a2x+…+an-2xn-3)]+…+cnxnA(x)證明：在等式26移項整理得(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)=(證畢)注意在GF(2)上有a+a=0。移項整理得27引理:

引理:28定理4.2p(x)|q(x)的充要條件是G(p(x))G(q(x))。證明：若p(x)|q(x)，可設(shè)q(x)=p(x)r(x)，因此A(x)=(x)/p(x)=[(x)r(x)]/[p(x)r(x)]=(x)r(x)/q(x)所以若{ai}∈G(p(x))，則{ai}∈G(q(x))，即G(p(x))G(q(x))。定理4.2p(x)|q(x)的充要條件是G(p(x))G29反之，若G(p(x))G(q(x))，則對于多項式(x)，存在序列{ai}∈G(p(x))以A(x)=(x)/p(x)為生成函數(shù)。特別地，對于多項式(x)=1，存在序列{ai}∈G(p(x))以1/p(x)為生成函數(shù)。由于G(p(x))G(q(x))，序列{ai}∈G(q(x))，所以存在函數(shù)r(x)，使得{ai}的生成函數(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ù)更多的LFSR來產(chǎn)生。反之，若G(p(x))G(q(x))，則對于多項式(x)30定義4.2設(shè)p(x)是GF(2)上的多項式，使p(x)|(xp-1)的最小p稱為p(x)的周期或階。定義4.2設(shè)p(x)是GF(2)上的多項式，使p(x)|(31定理4.3若序列{ai}的特征多項式p(x)定義在GF(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ù)為p-n，(x)的次數(shù)不超過n-1，所以(xp-1)A(x)的次數(shù)不超過(p-n)+(n-1)=p-1。這就證明了對于任意正整數(shù)i都有ai+p=ai。設(shè)p=kr+t,0≤t<r，則ai+p=ai+kr+t=ai+t=ai，所以t=0，即r|p。（證畢）定理4.3若序列{ai}的特征多項式p(x)定義在GF(232n級LFSR輸出序列的周期r不依賴于初始條件，而依賴于特征多項式p(x)。我們感興趣的是LFSR遍歷2n-1個非零狀態(tài)，這時序列的周期達到最大2n-1，這種序列就是m序列。顯然對于特征多項式一樣，而僅初始條件不同的兩個輸出序列，一個記為{a(1)i}，另一個記為{a(2)i}，其中一個必是另一個的移位，即存在一個常數(shù)k，使得a(1)i=a(2)k+i,i=1,2,…n級LFSR輸出序列的周期r不依賴于初始條件，而依賴于特征多33下面討論特征多項式滿足什么條件時，LFSR的輸出序列為m序列。下面討論特征多項式滿足什么條件時，LFSR的輸出序列為m序列34定理4.4設(shè)p(x)是n次不可約多項式，周期為m，序列{ai}∈G(p(x))，則{ai}的周期為m。證明：設(shè){ai}的周期為r，由定理4.3有r|m，所以r≤m.設(shè)A(x)為{ai}的生成函數(shù),A(x)=(x)/p(x)，即p(x)A(x)=(x)≠0，(x)的次數(shù)不超過n-1。而 A(x)=∑aixi-1=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)定理4.4設(shè)p(x)是n次不可約多項式，周期為m，序列{a35于是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)，因此m≤r。綜上r=m。（證畢）于是A(x)=a1+a2x+…+arxr-1/(xr-1)=36定理4.5n級LFSR產(chǎn)生的序列有最大周期2n-1的必要條件是其特征多項式為不可約的。證明：設(shè)n級LFSR產(chǎn)生的序列周期達到最大2n-1，除0序列外，每一序列的周期由特征多項式惟一決定，而與初始狀態(tài)無關(guān)。設(shè)特征多項式為p(x)，若p(x)可約，可設(shè)為p(x)=g(x)h(x)，其中g(shù)(x)不可約，且次數(shù)k<n。由于G(g(x))G(p(x))，而G(g(x))中序列的周期一方面不超過2k-1，另一方面又等于2n-1，這是矛盾的，所以p(x)不可約。(證畢)該定理的逆不成立，即LFSR的特征多項式為不可約多項式時，其輸出序列不一定是m序列。定理4.5n級LFSR產(chǎn)生的序列有最大周期2n-1的必要條37例4.3f(x)=x4+x3+x2+x+1為GF(2)上的不可約多項式，這可由x,x+1,x2+x+1都不能整除f(x)得到。以f(x)為特征多項式的LFSR的輸出序列可由ak=ak-1ak-2ak-3ak-4(k≥4)和給定的初始狀態(tài)求出，設(shè)初始狀態(tài)為0001，則輸出序列為000110001100011…，周期為5，不是m序列。例4.3f(x)=x4+x3+x2+x+1為GF(2)上的38定義4.3若n次不可約多項式p(x)的階為2n-1，則稱p(x)是n次本原多項式。定義4.3若n次不可約多項式p(x)的階為2n-1，則稱p39定理4.6設(shè){ai}∈G(p(x))，{ai}為m序列的充要條件是p(x)為本原多項式。證明：若p(x)是本原多項式，則其階為2n-1，由定理4.4得{ai}的周期等于2n-1，即{ai}為m序列。反之，若{ai}為m序列，即其周期等于2n-1，由定理4.5知p(x)是不可約的。由定理4.3知{ai}的周期2n-1整除p(x)的階，而p(x)的階不超過2n-1，所以p(x)的階為2n-1，即p(x)是本原多項式。（證畢）定理4.6設(shè){ai}∈G(p(x))，{ai}為m序列的充40{ai}為m序列的關(guān)鍵在于p(x)為本原多項式，n次本原多項式的個數(shù)為(2n-1)/n其中為歐拉函數(shù)。已經(jīng)證明，對于任意的正整數(shù)n，至少存在一個n次本原多項式。所以對于任意的n級LFSR，至少存在一種連接方式使其輸出序列為m序列。{ai}為m序列的關(guān)鍵在于p(x)為本原多項式，n次本原多項41例4.4設(shè)p(x)=x4+x+1，由于p(x)|(x15-1)，但不存在小于15的常數(shù)l，使得p(x)|(xl-1)，所以p(x)的階為15。p(x)的不可約性可由x,x+1,x2+x+1都不能整除p(x)得到，所以p(x)是本原多項式。若LFSR以p(x)為特征多項式，則輸出序列的遞推關(guān)系為ak=ak-1ak-4(k≥4)若初始狀態(tài)為1001，則輸出為100100011110101100100011110101…周期為24-1=15，即輸出序列為m序列。例4.4設(shè)p(x)=x4+x+1，由于p(x)|(x142序列密碼的安全性取決于密鑰流的安全性，要求密鑰流序列有良好的隨機性，以使密碼分析者對它無法預(yù)測。也就是說，即使截獲其中一段，也無法推測后面是什么。如果密鑰流是周期的，要完全做到隨機性是困難的。嚴格地說，這樣的序列不可能做到隨機，只能要求截獲比周期短的一段時不會泄露更多信息，這樣的序列稱為偽隨機序列。

4.5m序列的偽隨機性序列密碼的安全性取決于密鑰流的安全性，要求密鑰流序列有良好的43為討論序列的隨機性，我們先討論隨機序列的一般特性。設(shè){ai}=(a1a2a3…)為0、1序列，例如00110111，其前兩個數(shù)字是00，稱為0的2游程；接著是11，是1的2游程；再下來是0的1游程和1的3游程。為討論序列的隨機性，我們先討論隨機序列的一般特性。44定義4.4：GF(2)上周期為T的序列{ai}的自相關(guān)函數(shù)定義為定義中的和式表示序列{ai}與{ai+τ}（序列{ai}向后平移τ位得到）在一個周期內(nèi)對應(yīng)位相同的位數(shù)與對應(yīng)位不同的位數(shù)之差。當τ=0時，R(τ)=1；當τ≠0時，稱R(τ)為異相自相關(guān)函數(shù)。定義4.4：GF(2)上周期為T的序列{ai}的自相關(guān)函數(shù)定45Golomb對偽隨機周期序列提出了應(yīng)滿足的如下3個隨機性公設(shè)：①在序列的一個周期內(nèi)，0與1的個數(shù)相差至多為1。②在序列的一個周期內(nèi)，長為i的游程占游程總數(shù)的1/2i(i=1,2,…)，且在等長的游程中0的游程個數(shù)和1的游程個數(shù)相等。③異相自相關(guān)函數(shù)是一個常數(shù)。公設(shè)①說明{ai}中0與1出現(xiàn)的概率基本上相同;②說明0與1在序列中每一位置上出現(xiàn)的概率相同;③意味著通過對序列與其平移后的序列做比較，不能給出其他任何信息。Golomb對偽隨機周期序列提出了應(yīng)滿足的如下3個隨機性公設(shè)46從密碼系統(tǒng)的角度看，一個偽隨機序列還應(yīng)滿足下面的條件：①{ai}的周期相當大。②{ai}的確定在計算上是容易的。③由密文及相應(yīng)的明文的部分信息，不能確定整個{ai}。從密碼系統(tǒng)的角度看，一個偽隨機序列還應(yīng)滿足下面的條件：47下一定理說明，m序列滿足Golomb的3個隨機性公設(shè)。定理4.7GF(2)上的n級m序列{ai}具有如下性質(zhì)：①在一個周期內(nèi)，0、1出現(xiàn)的次數(shù)分別為2n-1-1和2n-1。②在一個周期內(nèi)，總游程數(shù)為2n-1；對1≤i≤n-2，長為i的游程有2n-i-1個，且0、1游程各半；長為n-1的0游程一個，長為n的1游程一個。③{ai}的自相關(guān)函數(shù)為下一定理說明，m序列滿足Golomb的3個隨機性公設(shè)。48證明：①在n長m序列的一個周期內(nèi)，除了全0狀態(tài)外，每個n長狀態(tài)（共有2n-1個）都恰好出現(xiàn)一次，這些狀態(tài)中有2n-1個在a1位是1，其余2n-1-2n-1=2n-1-1個狀態(tài)在a1位是0。②對n=1,2，易證結(jié)論成立。對n>2，當1≤i≤n-2時，n長m序列的一個周期內(nèi)，長為i的0游程數(shù)目等于序列中如下形式的狀態(tài)數(shù)目：100…01*…*，其中n-i-2個*可任取0或1。這種狀態(tài)共有2n-i-2個。同理可得長為i的1游程數(shù)目也等于2n-i-2，所以長為i的游程總數(shù)為2n-i-1。證明：①在n長m序列的一個周期內(nèi)，除了全0狀態(tài)外，每個n49由于寄存器中不會出現(xiàn)全0狀態(tài)，所以不會出現(xiàn)0的n游程，但必有一個1的n游程，而且1的游程不會更大，因為若出現(xiàn)1的n+1游程，就必然有兩個相鄰的全1狀態(tài)，但這是不可能的。這就證明了1的n游程必然出現(xiàn)在如下的串中：當這n+2位通過移位寄存器時，便依次產(chǎn)生以下狀態(tài)：

由于寄存器中不會出現(xiàn)全0狀態(tài)，所以不會出現(xiàn)0的n游程，但必有50由于，這兩個狀態(tài)只能各出現(xiàn)一次，所以不會有1的n-1游程。于是在一個周期內(nèi)，總游程數(shù)為由于，51③{ai}是周期為2n-1的m序列，對于任一正整數(shù)τ(0<τ<2n-1)，{ai}+{ai+τ}在一個周期內(nèi)為0的位的數(shù)目正好是序列{ai}和{ai+τ}對應(yīng)位相同的位的數(shù)目。設(shè)序列{ai}滿足遞推關(guān)系：ah+n=c1ah+n-1c2ah+n-2…cnah故 ah+n+τ=c1ah+n+τ-1c2ah+n+τ-2…cnah+τ ah+nah+n+τ=c1(ah+n-1ah+n+τ-1)c2(ah+n-2ah+n+τ-2)…cn(ahah+τ)③{ai}是周期為2n-1的m序列，對于任一正整數(shù)τ(0<52令bj=ajaj+τ，由遞推序列{ai}可推得遞推序列{bi}，{bi}滿足bh+n=c1bh+n-1c2bh+n-2…cnbh{bi}也是m序列。為了計算R(τ)，只要用{bi}在一個周期中0的個數(shù)減去1的個數(shù)，再除以2n-1，即（證畢）令bj=ajaj+τ，由遞推序列{ai}可推得遞推序列{b53上面說過，有限域上的二元加法序列密碼是目前最為常用的序列密碼體制(圖4-6)，設(shè)滾動密鑰生成器是線性反饋移位寄存器，產(chǎn)生的密鑰是m序列。又設(shè)Sh和Sh+1是序列中任意兩個連續(xù)的向量，其中4.6m序列密碼的破譯上面說過，有限域上的二元加法序列密碼是目前最為常用的序列密碼54設(shè)序列{ai}滿足線性遞推關(guān)系：可表示為設(shè)序列{ai}滿足線性遞推關(guān)系：55或Sh+1=M·Sh，其中又設(shè)敵手知道一段長為2n的明密文對，即已知或Sh+1=M·Sh，其中56于是可求出一段長為2n的密鑰序列其中,由此可推出線性反饋移位寄存器連續(xù)的n+1個狀態(tài)：于是可求出一段長為2n的密鑰序列57做矩陣而若X可逆，則做矩陣58下面證明X的確是可逆的。因為X是由S1,S2,…,Sn作為列向量，要證X可逆，只要證明這n個向量線性無關(guān)。由序列遞推關(guān)系：可推出向量的遞推關(guān)系：下面證明X的確是可逆的。59設(shè)m(m≤n+1)是使S1,S2,…,Sm線性相關(guān)的最小整數(shù)，即存在不全為0的系數(shù)l1,l2,…,lm，其中不妨設(shè)l1=1，使得即對于任一整數(shù)i有設(shè)m(m≤n+1)是使S1,S2,…,Sm線性相關(guān)的最小整數(shù)60由此又推出密鑰流的遞推關(guān)系：即密鑰流的級數(shù)小于m。若m≤n，則得出密鑰流的級數(shù)小于n，矛盾。所以m=n+1，從而矩陣X必是可逆的。由此又推出密鑰流的遞推關(guān)系：61例4.5設(shè)敵手得到密文串101101011110010和相應(yīng)的明文串011001111111001，因此可計算出相應(yīng)的密鑰流為110100100001011。進一步假定敵手還知道密鑰流是使用5級線性反饋移位寄存器產(chǎn)生的，那么敵手可分別用密文串中的前10個比特和明文串中的前10個比特建立如下方程例4.5設(shè)敵手得到密文串101101011110010和相62即而即63從而得到所以密鑰流的遞推關(guān)系為從而得到64目前研究得比較充分的方法有非線性移位寄存器序列,對多個線性反饋移位寄存器進行非線性組合,利用非線性分組密碼產(chǎn)生非線性序列,存儲變換等.4.7非線性序列目前研究得比較充分的方法有非線性移位寄存器序列,對多個線性反65一.非線性移位寄存器序列根據(jù)圖4-2可知,令反饋函數(shù)f(a1,a2,…,an)為非線性函數(shù)便構(gòu)成非線性移位寄存器,其輸出序列為非線性序列.輸出序列的周期最大可達,并稱周期達到最大值的非線性移位寄存器序列為M序列,M序列具有下面定理所述的隨機統(tǒng)計特性:一.非線性移位寄存器序列根據(jù)圖4-2可知,令反饋函數(shù)f(a166定理4.8GF(2)上的n級M序列具有如下性質(zhì)：①在一個周期內(nèi)，0、1出現(xiàn)的次數(shù)各為

。②在一個周期內(nèi)，總游程數(shù)為；對1≤i≤n-2，長為i的游程有個，且0、1游程各半；長為n-1的游程不存在，長為n的0游程和1游程各一個。稱兩個周期序列為不同的,若其中一個不能由另一個經(jīng)適當移位而得到.定理4.9GF(2)上的n級M序列的數(shù)目為個.定理4.8GF(2)上的n級M序列具有如下性質(zhì)：67例4.6

令n=3,設(shè)初態(tài)為(101),則輸出序列為1011100010…它是周期為8的序列,為M序列.一般的非線性移位寄存器尚處于艱難的研究之中,所以目前研究更多的還是在LFSR基礎(chǔ)上的非線性化問題.例4.6令n=3,設(shè)初態(tài)為(101),則輸出序列為10168為了使密鑰流生成器輸出的二元序列盡可能復(fù)雜，應(yīng)保證其周期盡可能大、線性復(fù)雜度和不可預(yù)測性盡可能高，因此常使用多個LFSR來構(gòu)造二元序列，稱每個LFSR的輸出序列為驅(qū)動序列，顯然密鑰流生成器輸出序列的周期不大于各驅(qū)動序列周期的乘積，因此，提高輸出序列的線性復(fù)雜度應(yīng)從極大化其周期開始。二.對線性移位寄存器進行非線性組合為了使密鑰流生成器輸出的二元序列盡可能復(fù)雜，應(yīng)保證其周期盡可69二元序列的線性復(fù)雜度指生成該序列的最短LFSR的級數(shù)，最短LFSR的特征多項式稱為二元序列的極小特征多項式。下面介紹幾種由多個LFSR驅(qū)動的非線性序列生成器。二元序列的線性復(fù)雜度指生成該序列的最短LFSR的級數(shù)，最短L70圖利用J-K觸發(fā)器的非線性序列生成器

J-K觸發(fā)器J-K觸發(fā)器71令驅(qū)動序列{ak}和{bk}分別為m級和n級m序列，則有如果令c-1=0，則輸出序列的最初3項為當m與n互素且a0+b0=1時，序列{ck}的周期為(2m-1)(2n-1)。令驅(qū)動序列{ak}和{bk}分別為m級和n級m序列，則有72例4.7令m=2,n=3，兩個驅(qū)動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。例4.7令m=2,n=3，兩個驅(qū)動m序列分別為73由表達式ck=(ak+1+bk)ck-1+ak可得因此，如果知道{ck}中相鄰位的值ck-1和ck，就可以推斷出ak和bk中的一個。而一旦知道足夠多的這類信息，就可通過密碼分析的方法得到序列{ak}和{bk}。為了克服上述缺點，Pless提出了由多個J-K觸發(fā)器序列驅(qū)動的多路復(fù)合序列方案，稱為Pless生成器。由表達式ck=(ak+1+bk)ck-1+ak可得74Pless生成器由8個LFSR、4個J-K觸發(fā)器和1個循環(huán)計數(shù)器構(gòu)成，由循環(huán)計數(shù)器進行選擇控制，如圖4-8所示。假定在時刻t輸出第t(mod4)個單元，則輸出序列為a0b1c2d3a4b5d6Pless生成器Pless生成器由8個LFSR、4個J-K觸發(fā)器和1個循環(huán)計75圖4-8Pless生成器第4章(序列密碼)課件76當8個線性移位寄存器的級數(shù)都互素時,且滿足定理4.10的條件,輸出序列周期可達它們各自周期的乘積.Pless體制的一個直觀上的弱點是最后的選擇器依次輪換輸出,如果改為隨機方式,似乎要好些.當8個線性移位寄存器的級數(shù)都互素時,且滿足定理4.10的條件77鐘控序列最基本的模型是用一個LFSR控制另外一個LFSR的移位時鐘脈沖。鐘控序列鐘控序列最基本的模型是用一個LFSR控制另外一個LFSR的移78基本鐘控序列它由兩個不同的線性移位寄存器LFSR1和LFSR2以及一個采樣函數(shù)S組成,通常,i=0,1,2,…,而輸出的鐘控序列其中,用于產(chǎn)生密鑰序列的鐘控序列產(chǎn)生器一般由多個基本鐘控序列產(chǎn)生器的級聯(lián)組成.基本鐘控序列它由兩個不同的線性移位寄存器LFSR1和LFSR79移位-刪除鐘控序列兩個不同的線性移位寄存器LFSR1和LFSR2各自單獨運行,且有相同的時鐘脈沖控制移位.LFSR1的最后兩級輸出相乘后控制LFSR2的輸出,如果,LFSR2移位一步,但不輸出;如果,則LFSR2移位一步,且輸出得到的序列稱為移位-刪除鐘控序列.移位-刪除鐘控序列兩個不同的線性移位寄存器LFSR1和LFS80例4.8給定和的特征多項式分別為和初態(tài)分別為和

,則有例4.8給定和的特征多項式81j12345678910111213141516{aj}1011001000111101{cj}001000000011100{bj}1001101011110001{zj}101101011001j12345682實際應(yīng)用中，可以用上述最基本的鐘控序列生成器構(gòu)造復(fù)雜的模型，具體構(gòu)造方式可參閱有關(guān)文獻。實際應(yīng)用中，可以用上述最基本的鐘控序列生成器構(gòu)造復(fù)雜的模型，83設(shè)計一個性能良好的序列密碼是一項十分困難的任務(wù)。最基本的設(shè)計原則是“密鑰流生成器的不可預(yù)測性”，它可分解為下述基本原則：①長周期。②高線性復(fù)雜度。③統(tǒng)計性能良好。④足夠的“混亂”。⑤足夠的“擴散”。⑥抵抗不同形式的攻擊。設(shè)計一個性能良好的序列密碼是一項十分困難的任務(wù)。最基本的設(shè)計84第4章有關(guān)序列密碼和移位寄存器4.1引言4.2序列密碼的一般原理4.3線性移位寄存器4.4線性移位寄存器的一元多項式表示4.5m序列的偽隨機性4.6m序列密碼的破譯4.7非線性序列習(xí)題第4章有關(guān)序列密碼和移位寄存器4.1引言854.1引言人們試圖用序列密碼方式仿效”一次一密”密碼.從而促成了序列密碼的研究和發(fā)展.序列密碼是世界軍事,外交等領(lǐng)域應(yīng)用的主流密碼體制.在通常的序列密碼中,加解密用的密鑰序列是偽隨機序列,它的產(chǎn)生容易且有較成熟的理論工具,所以序列密碼是當前通用的密碼系統(tǒng).序列密碼的安全性主要依賴于密鑰序列,因而什么樣的偽隨機序列是安全可靠的密鑰序列,以及如何實現(xiàn)這種序列就成了序列密碼中研究的一個主要方面.4.1引言人們試圖用序列密碼方式仿效86序列密碼的基本思想是利用一個短密鑰k通過一個算法來產(chǎn)生一個密鑰流k=k0k1…，并使用如下規(guī)則對明文串m=m0m1m2…加密：c=c0c1c2…=Ek0(m0)Ek1(m1)Ek2(m2)…。密鑰流由密鑰流發(fā)生器A產(chǎn)生：k0k1…=A(k)，4.2序列密碼的一般原理序列密碼的基本思想是利用一個短密鑰k通過一個算法來產(chǎn)生一個密87

二進制序列密碼體制模型第4章(序列密碼)課件88由此可見,序列密碼的安全性主要依賴于密鑰序列k0k1…=A(k)，當k0k1…是離散無記憶的隨機序列時,則該系統(tǒng)就是一次一密密碼,它是不可破的.但通常A(k)是一個由k通過確定性算法產(chǎn)生的偽隨機序列,因而此時,該系統(tǒng)就不再是完全保密的.設(shè)計序列密碼的關(guān)鍵是設(shè)計密鑰序列A(k)，密鑰序列A(k)的設(shè)計應(yīng)考慮如下幾個因素:(1)系統(tǒng)的安全保密性;(2)密鑰k易于分配、保管，更換簡便；(3)產(chǎn)生密鑰序列簡單快速。目前最為流行和實用的密鑰流產(chǎn)生器，其驅(qū)動部分是一個或多個線性反饋移位寄存器。由此可見,序列密碼的安全性主要依賴于密鑰序列k0k1…=A89常見的兩種密鑰流產(chǎn)生器第4章(序列密碼)課件90因為確定性算法產(chǎn)生的序列是周期的或準周期的，為了使序列密碼達到要求的安全保密性，使得密鑰經(jīng)其擴展成的密鑰流序列具有如下性質(zhì)：極大的周期、良好的統(tǒng)計特性、抗線性分析、抗統(tǒng)計分析。

我們僅對實用中最感興趣的二元情形即GF(2)上的序列密碼原理進行介紹，但其理論是可以在任何有限域GF(q)中進行研究的。因為確定性算法產(chǎn)生的序列是周期的或準周期的，為了使序列密碼達91移位寄存器是序列密碼產(chǎn)生密鑰流的一個主要組成部分。GF(2)上一個n級反饋移位寄存器由n個二元存儲器與一個反饋函數(shù)f(a1,a2,…,an)組成，如圖4.2所示。2.2線性反饋移位寄存器移位寄存器是序列密碼產(chǎn)生密鑰流的一個主要組成部分。GF(2)92圖4.2GF(2)上的n級反饋移位寄存器第4章(序列密碼)課件93每一存儲器稱為移位寄存器的一級，在任一時刻，這些級的內(nèi)容構(gòu)成該反饋移位寄存器的狀態(tài)，每一狀態(tài)對應(yīng)于GF(2)上的一個n維向量，共有2n種可能的狀態(tài)。每一時刻的狀態(tài)可用n長序列a1,a2,…,an或n維向量(a1,a2,…,an)表示，其中ai是第i級存儲器的內(nèi)容。每一存儲器稱為移位寄存器的一級，在任一時刻，這些級的內(nèi)容構(gòu)成94初始狀態(tài)由用戶確定，當?shù)趇個移位時鐘脈沖到來時，每一級存儲器ai都將其內(nèi)容向下一級ai-1傳遞，并根據(jù)寄存器此時的狀態(tài)a1,a2,…,an計算f(a1,a2,…,an)，作為下一時刻的an。反饋函數(shù)f(a1,a2,…,an)是n元布爾函數(shù)，即n個變元a1,a2,…,an可以獨立地取0和1這兩個可能的值，函數(shù)中的運算有邏輯與、邏輯或、邏輯補等運算，最后的函數(shù)值也為0或1。初始狀態(tài)由用戶確定，當?shù)趇個移位時鐘脈沖到來時，每一級存儲器95例4.1圖4-3是一個3級反饋移位寄存器，其初始狀態(tài)為(a1,a2,a3)=(1,0,1)，求出輸出序列。例4.1圖4-3是一個3級反饋移位寄存器，其初始狀態(tài)為(96圖4-3一個3級反饋移位寄存器第4章(序列密碼)課件97一個3級反饋移位寄存器的狀態(tài)和輸出狀態(tài)（a1,a2,a3)輸出101110111011101110

101110一個3級反饋移位寄存器狀態(tài)（a1,a2,a3)輸出1098即輸出序列為101110111011…，周期為4。如果移位寄存器的反饋函數(shù)f(a1,a2,…,an)是a1，a2，…，an的線性函數(shù)，則稱之為線性反饋移位寄存器LFSR（linearfeedbackshiftregister）。此時f可寫為f(a1,a2,…,an)=cna1cn-1a2…c1an其中常數(shù)ci=0或1，是模2加法。ci=0或1可用開關(guān)的斷開和閉合來實現(xiàn)，如圖4-4所示。即輸出序列為101110111011…，周期為4。99圖4-4GF(2)上的n級線性反饋移位寄存器第4章(序列密碼)課件100輸出序列{at}滿足an+t=cnatcn-1at+1…c1an+t-1其中t為非負正整數(shù)。線性反饋移位寄存器因其實現(xiàn)簡單、速度快、有較為成熟的理論等優(yōu)點而成為構(gòu)造密鑰流生成器的最重要的部件之一。輸出序列{at}滿足101例4.2圖4-5是一個5級線性反饋移位寄存器，其初始狀態(tài)為（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出輸出序列為1001101001000010101110110001111100110…周期為31。例4.2圖4-5是一個5級線性反饋移位寄存器，其初始狀態(tài)為102圖4-5一個5級線性反饋移位寄存器第4章(序列密碼)課件103在線性反饋移位寄存器中總是假定c1,c2,…,cn中至少有一個不為0，否則f(a1,a2,…,an)≡0，這樣的話，在n個脈沖后狀態(tài)必然是00…0，且這個狀態(tài)必將一直持續(xù)下去。若只有一個系數(shù)不為0，設(shè)僅有cj不為0，實際上是一種延遲裝置。一般對于n級線性反饋移位寄存器，總是假定cn=1。在線性反饋移位寄存器中總是假定c1,c2,…,cn中至少有一104線性反饋移位寄存器輸出序列的性質(zhì)完全由其反饋函數(shù)決定。n級線性反饋移位寄存器最多有2n個不同的狀態(tài)。若其初始狀態(tài)為0，則其狀態(tài)恒為0。若其初始狀態(tài)非0，則其后繼狀態(tài)不會為0。因此n級線性反饋移位寄存器的狀態(tài)周期小于等于2n-1。其輸出序列的周期與狀態(tài)周期相等，也小于等于2n-1。只要選擇合適的反饋函數(shù)便可使序列的周期達到最大值2n-1，周期達到最大值的序列稱為m序列。線性反饋移位寄存器輸出序列的性質(zhì)完全由其反饋函數(shù)決定。n級線105設(shè)n級線性移位寄存器的輸出序列滿足遞推關(guān)系an+k=c1an+k-1c2an+k-2

…cnak(*)對任何成立。這種遞推關(guān)系可用一個一元高次多項式P(x)=1+c1x+…＋cn-1xn-1＋cnxn表示，稱這個多項式為LFSR的聯(lián)系多項式或特征多項式。4.4線性移位寄存器的一元多項式表示設(shè)n級線性移位寄存器的輸出序列滿足遞推關(guān)系4.4線性移位106設(shè)n級線性移位寄存器對應(yīng)于遞推關(guān)系(*)，由于ai∈GF(2)(i=1,2,…,n)，所以共有2n組初始狀態(tài)，即有2n個遞推序列，其中非恒為零的序列有2n-1個，記2n-1個非零序列的全體為G(p(x))。設(shè)n級線性移位寄存器對應(yīng)于遞推關(guān)系(*)，由于ai∈GF(2107定義給定序列{ai}，冪級數(shù)A(x)=∑aixi-1稱為該序列的生成函數(shù)或母函數(shù)。

定義給定序列{ai}，冪級數(shù)108定理4.1設(shè)p(x)=1+c1x+…+cn-1xn-1+cnxn是GF(2)上的多項式，G(p(x))中任一序列{ai}的生成函數(shù)A(x)滿足：A(x)=(x)/p(x)其中定理4.1設(shè)p(x)=1+c1x+…+cn-1xn-1109證明：在等式an+1=c1anc2an-1…cna1an+2=c1an+1c2an…cna2

…兩邊分別乘以xn,xn+1,…，再求和，可得 A(x)-(a1+a2x+…+anxn-1) =c1x[A(x)-(a1+a2x+…+an-1xn-2)] +c2x2[A(x)-(a1+a2x+…+an-2xn-3)]+…+cnxnA(x)證明：在等式110移項整理得(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)=(證畢)注意在GF(2)上有a+a=0。移項整理得111引理:

引理:112定理4.2p(x)|q(x)的充要條件是G(p(x))G(q(x))。證明：若p(x)|q(x)，可設(shè)q(x)=p(x)r(x)，因此A(x)=(x)/p(x)=[(x)r(x)]/[p(x)r(x)]=(x)r(x)/q(x)所以若{ai}∈G(p(x))，則{ai}∈G(q(x))，即G(p(x))G(q(x))。定理4.2p(x)|q(x)的充要條件是G(p(x))G113反之，若G(p(x))G(q(x))，則對于多項式(x)，存在序列{ai}∈G(p(x))以A(x)=(x)/p(x)為生成函數(shù)。特別地，對于多項式(x)=1，存在序列{ai}∈G(p(x))以1/p(x)為生成函數(shù)。由于G(p(x))G(q(x))，序列{ai}∈G(q(x))，所以存在函數(shù)r(x)，使得{ai}的生成函數(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ù)更多的LFSR來產(chǎn)生。反之，若G(p(x))G(q(x))，則對于多項式(x)114定義4.2設(shè)p(x)是GF(2)上的多項式，使p(x)|(xp-1)的最小p稱為p(x)的周期或階。定義4.2設(shè)p(x)是GF(2)上的多項式，使p(x)|(115定理4.3若序列{ai}的特征多項式p(x)定義在GF(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ù)為p-n，(x)的次數(shù)不超過n-1，所以(xp-1)A(x)的次數(shù)不超過(p-n)+(n-1)=p-1。這就證明了對于任意正整數(shù)i都有ai+p=ai。設(shè)p=kr+t,0≤t<r，則ai+p=ai+kr+t=ai+t=ai，所以t=0，即r|p。（證畢）定理4.3若序列{ai}的特征多項式p(x)定義在GF(2116n級LFSR輸出序列的周期r不依賴于初始條件，而依賴于特征多項式p(x)。我們感興趣的是LFSR遍歷2n-1個非零狀態(tài)，這時序列的周期達到最大2n-1，這種序列就是m序列。顯然對于特征多項式一樣，而僅初始條件不同的兩個輸出序列，一個記為{a(1)i}，另一個記為{a(2)i}，其中一個必是另一個的移位，即存在一個常數(shù)k，使得a(1)i=a(2)k+i,i=1,2,…n級LFSR輸出序列的周期r不依賴于初始條件，而依賴于特征多117下面討論特征多項式滿足什么條件時，LFSR的輸出序列為m序列。下面討論特征多項式滿足什么條件時，LFSR的輸出序列為m序列118定理4.4設(shè)p(x)是n次不可約多項式，周期為m，序列{ai}∈G(p(x))，則{ai}的周期為m。證明：設(shè){ai}的周期為r，由定理4.3有r|m，所以r≤m.設(shè)A(x)為{ai}的生成函數(shù),A(x)=(x)/p(x)，即p(x)A(x)=(x)≠0，(x)的次數(shù)不超過n-1。而 A(x)=∑aixi-1=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)定理4.4設(shè)p(x)是n次不可約多項式，周期為m，序列{a119于是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)，因此m≤r。綜上r=m。（證畢）于是A(x)=a1+a2x+…+arxr-1/(xr-1)=120定理4.5n級LFSR產(chǎn)生的序列有最大周期2n-1的必要條件是其特征多項式為不可約的。證明：設(shè)n級LFSR產(chǎn)生的序列周期達到最大2n-1，除0序列外，每一序列的周期由特征多項式惟一決定，而與初始狀態(tài)無關(guān)。設(shè)特征多項式為p(x)，若p(x)可約，可設(shè)為p(x)=g(x)h(x)，其中g(shù)(x)不可約，且次數(shù)k<n。由于G(g(x))G(p(x))，而G(g(x))中序列的周期一方面不超過2k-1，另一方面又等于2n-1，這是矛盾的，所以p(x)不可約。(證畢)該定理的逆不成立，即LFSR的特征多項式為不可約多項式時，其輸出序列不一定是m序列。定理4.5n級LFSR產(chǎn)生的序列有最大周期2n-1的必要條121例4.3f(x)=x4+x3+x2+x+1為GF(2)上的不可約多項式，這可由x,x+1,x2+x+1都不能整除f(x)得到。以f(x)為特征多項式的LFSR的輸出序列可由ak=ak-1ak-2ak-3ak-4(k≥4)和給定的初始狀態(tài)求出，設(shè)初始狀態(tài)為0001，則輸出序列為000110001100011…，周期為5，不是m序列。例4.3f(x)=x4+x3+x2+x+1為GF(2)上的122定義4.3若n次不可約多項式p(x)的階為2n-1，則稱p(x)是n次本原多項式。定義4.3若n次不可約多項式p(x)的階為2n-1，則稱p123定理4.6設(shè){ai}∈G(p(x))，{ai}為m序列的充要條件是p(x)為本原多項式。證明：若p(x)是本原多項式，則其階為2n-1，由定理4.4得{ai}的周期等于2n-1，即{ai}為m序列。反之，若{ai}為m序列，即其周期等于2n-1，由定理4.5知p(x)是不可約的。由定理4.3知{ai}的周期2n-1整除p(x)的階，而p(x)的階不超過2n-1，所以p(x)的階為2n-1，即p(x)是本原多項式。（證畢）定理4.6設(shè){ai}∈G(p(x))，{ai}為m序列的充124{ai}為m序列的關(guān)鍵在于p(x)為本原多項式，n次本原多項式的個數(shù)為(2n-1)/n其中為歐拉函數(shù)。已經(jīng)證明，對于任意的正整數(shù)n，至少存在一個n次本原多項式。所以對于任意的n級LFSR，至少存在一種連接方式使其輸出序列為m序列。{ai}為m序列的關(guān)鍵在于p(x)為本原多項式，n次本原多項125例4.4設(shè)p(x)=x4+x+1，由于p(x)|(x15-1)，但不存在小于15的常數(shù)l，使得p(x)|(xl-1)，所以p(x)的階為15。p(x)的不可約性可由x,x+1,x2+x+1都不能整除p(x)得到，所以p(x)是本原多項式。若LFSR以p(x)為特征多項式，則輸出序列的遞推關(guān)系為ak=ak-1ak-4(k≥4)若初始狀態(tài)為1001，則輸出為100100011110101100100011110101…周期為24-1=15，即輸出序列為m序列。例4.4設(shè)p(x)=x4+x+1，由于p(x)|(x1126序列密碼的安全性取決于密鑰流的安全性，要求密鑰流序列有良好的隨機性，以使密碼分析者對它無法預(yù)測。也就是說，即使截獲其中一段，也無法推測后面是什么。如果密鑰流是周期的，要完全做到隨機性是困難的。嚴格地說，這樣的序列不可能做到隨機，只能要求截獲比周期短的一段時不會泄露更多信息，這樣的序列稱為偽隨機序列。

4.5m序列的偽隨機性序列密碼的安全性取決于密鑰流的安全性，要求密鑰流序列有良好的127為討論序列的隨機性，我們先討論隨機序列的一般特性。設(shè){ai}=(a1a2a3…)為0、1序列，例如00110111，其前兩個數(shù)字是00，稱為0的2游程；接著是11，是1的2游程；再下來是0的1游程和1的3游程。為討論序列的隨機性，我們先討論隨機序列的一般特性。128定義4.4：GF(2)上周期為T的序列{ai}的自相關(guān)函數(shù)定義為定義中的和式表示序列{ai}與{ai+τ}（序列{ai}向后平移τ位得到）在一個周期內(nèi)對應(yīng)位相同的位數(shù)與對應(yīng)位不同的位數(shù)之差。當τ=0時，R(τ)=1；當τ≠0時，稱R(τ)為異相自相關(guān)函數(shù)。定義4.4：GF(2)上周期為T的序列{ai}的自相關(guān)函數(shù)定129Golomb對偽隨機周期序列提出了應(yīng)滿足的如下3個隨機性公設(shè)：①在序列的一個周期內(nèi)，0與1的個數(shù)相差至多為1。②在序列的一個周期內(nèi)，長為i的游程占游程總數(shù)的1/2i(i=1,2,…)，且在等長的游程中0的游程個數(shù)和1的游程個數(shù)相等。③異相自相關(guān)函數(shù)是一個常數(shù)。公設(shè)①說明{ai}中0與1出現(xiàn)的概率基本上相同;②說明0與1在序列中每一位置上出現(xiàn)的概率相同;③意味著通過對序列與其平移后的序列做比較，不能給出其他任何信息。Golomb對偽隨機周期序列提出了應(yīng)滿足的如下3個隨機性公設(shè)130從密碼系統(tǒng)的角度看，一個偽隨機序列還應(yīng)滿足下面的條件：①{ai}的周期相當大。②{ai}的確定在計算上是容易的。③由密文及相應(yīng)的明文的部分信息，不能確定整個{ai}。從密碼系統(tǒng)的角度看，一個偽隨機序列還應(yīng)滿足下面的條件：131下一定理說明，m序列滿足Golomb的3個隨機性公設(shè)。定理4.7GF(2)上的n級m序列{ai}具有如下性質(zhì)：①在一個周期內(nèi)，0、1出現(xiàn)的次數(shù)分別為2n-1-1和2n-1。②在一個周期內(nèi)，總游程數(shù)為2n-1；對1≤i≤n-2，長為i的游程有2n-i-1個，且0、1游程各半；長為n-1的0游程一個，長為n的1游程一個。③{ai}的自相關(guān)函數(shù)為下一定理說明，m序列滿足Golomb的3個隨機性公設(shè)。132證明：①在n長m序列的一個周期內(nèi)，除了全0狀態(tài)外，每個n長狀態(tài)（共有2n-1個）都恰好出現(xiàn)一次，這些狀態(tài)中有2n-1個在a1位是1，其余2n-1-2n-1=2n-1-1個狀態(tài)在a1位是0。②對n=1,2，易證結(jié)論成立。對n>2，當1≤i≤n-2時，n長m序列的一個周期內(nèi)，長為i的0游程數(shù)目等于序列中如下形式的狀態(tài)數(shù)目：100…01*…*，其中n-i-2個*可任取0或1。這種狀態(tài)共有2n-i-2個。同理可得長為i的1游程數(shù)目也等于2n-i-2，所以長為i的游程總數(shù)為2n-i-1。證明：①在n長m序列的一個周期內(nèi)，除了全0狀態(tài)外，每個n133由于寄存器中不會出現(xiàn)全0狀態(tài)，所以不會出現(xiàn)0的n游程，但必有一個1的n游程，而且1的游程不會更大，因為若出現(xiàn)1的n+1游程，就必然有兩個相鄰的全1狀態(tài)，但這是不可能的。這就證明了1的n游程必然出現(xiàn)在如下的串中：當這n+2位通過移位寄存器時，便依次產(chǎn)生以下狀態(tài)：

由于寄存器中不會出現(xiàn)全0狀態(tài)，所以不會出現(xiàn)0的n游程，但必有134由于，這兩個狀態(tài)只能各出現(xiàn)一次，所以不會有1的n-1游程。于是在一個周期內(nèi)，總游程數(shù)為由于，135③{ai}是周期為2n-1的m序列，對于任一正整數(shù)τ(0<τ<2n-1)，{ai}+{ai+τ}在一個周期內(nèi)為0的位的數(shù)目正好是序列{ai}和{ai+τ}對應(yīng)位相同的位的數(shù)目。設(shè)序列{ai}滿足遞推關(guān)系：ah+n=c1ah+n-1c2ah+n-2…cnah故 ah+n+τ=c1ah+n+τ-1c2ah+n+τ-2…cnah+τ ah+nah+n+τ=c1(ah+n-1ah+n+τ-1)c2(ah+n-2ah+n+τ-2)…cn(ahah+τ)③{ai}是周期為2n-1的m序列，對于任一正整數(shù)τ(0<136令bj=ajaj+τ，由遞推序列{ai}可推得遞推序列{bi}，{bi}滿足bh+n=c1bh+n-1c2bh+n-2…cnbh{bi}也是m序列。為了計算R(τ)，只要用{bi}在一個周期中0的個數(shù)減去1的個數(shù)，再除以2n-1，即（證畢）令bj=ajaj+τ，由遞推序列{ai}可推得遞推序列{b137上面說過，有限域上的二元加法序列密碼是目前最為常用的序列密碼體制(圖4-6)，設(shè)滾動密鑰生成器是線性反饋移位寄存器，產(chǎn)生的密鑰是m序列。又設(shè)Sh和Sh+1是序列中任意兩個連續(xù)的向量，其中4.6m序列密碼的破譯上面說過，有限域上的二元加法序列密碼是目前最為常用的序列密碼138設(shè)序列{ai}滿足線性遞推關(guān)系：可表示為設(shè)序列{ai}滿足線性遞推關(guān)系：139或Sh+1=M·Sh，其中又設(shè)敵手知道一段長為2n的明密文對，即已知或Sh+1=M·Sh，其中140于是可求出一段長為2n的密鑰序列其中,由此可推出線性反饋移位寄存器連續(xù)的n+1個狀態(tài)：于是可求出一段長為2n的密鑰序列141做矩陣而若X可逆，則做矩陣142下面證明X的確是可逆的。因為X是由S1,S2,…,Sn作為列向量，要證X可逆，只要證明這n個向量線性無關(guān)。由序列遞推關(guān)系：可推出向量的遞推關(guān)系：下面證明X的確是可逆的。143設(shè)m(m≤n+1)是使S1,S2,…,Sm線性相關(guān)的最小整數(shù)，即存在不全為0的系數(shù)l1,l2,…,lm，其中不妨設(shè)l1=1，使得即對于任一整數(shù)i有設(shè)m(m≤n+1)是使S1,S2,…,Sm線性相關(guān)的最小整數(shù)144由此又推出密鑰流的遞推關(guān)系：即密鑰流的級數(shù)小于m。若m≤n，則得出密鑰流的級數(shù)小于n，矛盾。所以m=n+1，從而矩陣X必是可逆的。由此又推出密鑰流的遞推關(guān)系：145例4.5設(shè)敵手得到密文串101101011110010和相應(yīng)的明文串011001111111001，因此可計算出相應(yīng)的密鑰流為110100100001011。進一步假定敵手還知道密鑰流是使用5級線性反饋移位寄存器產(chǎn)生的，那么敵手可分別用密文串中的前10個比特和明文串中的前10個比特建立如下方程例4.5設(shè)敵手得到密文串101101011110010和相146即而即147從而得到所以密鑰流的遞推關(guān)系為從而得到148目前研究得比較充分的方法有非線性移位寄存器序列,對多個線性反饋移位寄存器進行非線性組合,利用非線性分組密碼產(chǎn)生非線性序列,存儲變換等.4.7非線性序列目前研究得比較充分的方法有非線性移位寄存器序列,對多個線性反149一.非線性移位寄存器序列根據(jù)圖4-2可知,令反饋函數(shù)f(a1,a2,…,an)為非線性函數(shù)便構(gòu)成非線性移位寄存器,其輸出序列為非線性序列.輸出序列的周期最大可達,并稱周期達到最大值的非線性移位寄存器序列為M序列,M序列具有下面定理所述的隨機統(tǒng)計特性:一.非線性移位寄存器序列根據(jù)圖4-2可知,令反饋函數(shù)f(a1150定理4.8GF(2)上的n級M序列具有如下性質(zhì)：①在一個周期內(nèi)，0、1出現(xiàn)的次數(shù)各為

。②在一個周期內(nèi)，總游程數(shù)為；對1≤i≤n-2，長為i的游程有個，且0、1游程各半；長為n-1的游程不存在，長為n的