《現(xiàn)代密碼學(xué)原理與實(shí)踐》課件第2章

第2章序列密碼2.1序列密碼原理

2.2線性反饋移位寄存器

2.3非線性序列

2.4利用線性反饋移位寄存器的密碼反饋習(xí)題2

實(shí)踐練習(xí)2

把明文加密成密文，有兩種方式，一種是分組(塊)加密，一種是序列(流)加密。采用序列加密時(shí)，明文不進(jìn)行分段，明文序列被源源不斷地送入加密器，在密鑰作用下進(jìn)行加密運(yùn)算，產(chǎn)生的密文序列源源不斷地被輸出來，實(shí)時(shí)地完成加密過程。本章主要討論偽隨機(jī)序列的產(chǎn)生和特點(diǎn)，因?yàn)樗粌H是序列加密密鑰的來源，而且也是現(xiàn)代密碼體制中不可缺少的關(guān)鍵數(shù)據(jù)。2.1序列密碼原理2.1.1序列加、解密原理一個(gè)序列流加密的保密通信系統(tǒng)的流程如圖2.1所示。明文消息序列為

m=m1m2m3…

密鑰序列為

k=k1k2k3…

加、解密都是逐位順序進(jìn)行的：

ci=Ek(mi)；mi=Dk(ci)(2-1)得到的密文序列為

c=c1c2c3…圖2.1序列流加密的保密通信系統(tǒng)流程圖2.1.2安全性討論

從傳統(tǒng)密碼算法得知，不論單表加密、多表加密，或是置換還是其他方式，密文之所以“密”，原因在于密鑰使明文變“亂”了，這種亂就是隨機(jī)性。密鑰的隨機(jī)性掩蓋了明文的可理解性。

Shannon信息論已經(jīng)證明［1］，只有“一字一密”系統(tǒng)才是不可破譯的、完全安全的保密系統(tǒng)。所謂一字一密，指密鑰序列是無限長(zhǎng)的真正的隨機(jī)序列，密鑰使每位密文都變得無規(guī)律可循。對(duì)于這樣的系統(tǒng)，破譯者完全無法從已有的密文中，或明、密文對(duì)照中找到規(guī)律，不能為未知的密文破譯提供任何有價(jià)值的信息。

然而，這樣的保密系統(tǒng)是不可行的。且不說真正的隨機(jī)序列如何獲得，單就如何把無限長(zhǎng)的密鑰安全地傳給合法收信人就是個(gè)難題。如果密鑰和密文一樣長(zhǎng)，用秘密信道傳遞密鑰還不如直接傳遞明文好了！保密通信的初衷就是希望在公開信道中安全通信，因?yàn)槊孛苄诺缹?shí)在昂貴而又難得。有實(shí)際意義的密鑰應(yīng)當(dāng)是用軟、硬件可以再生的“偽”隨機(jī)序列，偽就偽在它并不真正隨機(jī)，而是有規(guī)律的，這個(gè)規(guī)律就是周期性。只不過周期很長(zhǎng)，在有限時(shí)段內(nèi)看不出規(guī)律罷了。生成這樣的偽隨機(jī)序列，只需要很短的“初始密鑰”(或曰種子)，只要通信雙方在協(xié)議中約定好偽隨機(jī)序列的產(chǎn)生方法和初始值，即具有了共同的密鑰。圖2.2為用偽隨機(jī)序列作為密鑰的序列流加密系統(tǒng)。圖2.2用偽隨機(jī)序列作為密鑰的序列流加密系統(tǒng)2.1.3序列密碼對(duì)密鑰流的要求［6］

1.極大的周期現(xiàn)代密碼機(jī)數(shù)據(jù)率高達(dá)108bit/s。如果使用10年內(nèi)不會(huì)重復(fù)的密鑰流，密鑰的周期應(yīng)不少于3×1016或255。

2.良好的統(tǒng)計(jì)特性

Golomb對(duì)隨機(jī)序列的統(tǒng)計(jì)性質(zhì)提出了三條要求：

(1)在序列的一個(gè)周期內(nèi)，0和1的個(gè)數(shù)最多相差1。

(2)在一個(gè)周期圈內(nèi)，長(zhǎng)度為1的游程數(shù)占1/2，長(zhǎng)度為2的游程數(shù)占1/4……長(zhǎng)度為i的游程數(shù)占1/2i，且在等長(zhǎng)的游程中，0游程和1游程各半(游程指連0或連1的段落)。

(3)自相關(guān)函數(shù)為二值函數(shù)：

偽隨機(jī)序列的自相關(guān)函數(shù)定義如下：(2-2)式中，T為周期；τ為預(yù)先指定的一個(gè)位移值。相關(guān)函數(shù)定義為序列與它的移位序列逐位相比較，相同則為1，不同則得-1，然后相加起來求平均。因此，Ra(τ)也等于兩序列逐位相比較時(shí)，取值相同的位數(shù)與取值不同的位數(shù)之差再除以T：

對(duì)于上式，當(dāng)τ≠0時(shí)Ra(τ)≡0，表明通過{ai}與{ai+τ}比較，無法得到關(guān)于{ai}的實(shí)質(zhì)性信息(比如周期)；而當(dāng)τ=0時(shí)，Ra(0)=1，表明自身歸一。

3.足夠的復(fù)雜度

用較短的“種子”就能生成周期較長(zhǎng)的偽隨機(jī)密鑰，那么破譯者也可以這么做，他只需掌握(破譯或猜出)這個(gè)種子即可。因?yàn)楫a(chǎn)生偽隨機(jī)序列的算法是公開的(至少是不難獲得的)。因此，為了系統(tǒng)的安全，僅僅周期長(zhǎng)是不夠的，還要求密鑰序列有足夠的復(fù)雜度。序列的復(fù)雜度指序列有足夠繁多的變化花樣。它的具體定義后面會(huì)討論。現(xiàn)在要說明的是，偽隨機(jī)序列生成器輸出的雖然不是真正的隨機(jī)序列，但是在計(jì)算資源受到一定限制(速度、內(nèi)存有限，機(jī)時(shí)有限)的條件下，如果要想?yún)^(qū)別這個(gè)輸出序列與相同長(zhǎng)度的真隨機(jī)序列，是不可行的；或者從理論上可以證明，二者的計(jì)算工作量隨序列長(zhǎng)度n變化的依賴關(guān)系以比多項(xiàng)式或更高(如冪指數(shù)函數(shù))的方式而增大，因而可以認(rèn)為二者是不可區(qū)分的。這樣的偽隨機(jī)序列就被認(rèn)為具有足夠的復(fù)雜性。說到底，世上沒有絕對(duì)不可破的密碼，比如通過窮搜索總能將其破譯，然而如果窮搜索不可能在有限時(shí)間內(nèi)完成，而且又不存在比窮搜索更好的破譯方法，則可以認(rèn)為這個(gè)密碼系統(tǒng)是安全的。2.2線性反饋移位寄存器［3］

20世紀(jì)50年代以后，數(shù)字電子技術(shù)大力發(fā)展，使得偽隨機(jī)序列可以方便地利用移位寄存器產(chǎn)生，加上有效的數(shù)學(xué)工具(域理論和譜分析)，使序列密碼迅速走向成熟。2.2.1反饋移位寄存器(FeedbackShiftRegister)

n位二值存儲(chǔ)器共有2n種狀態(tài)，每個(gè)狀態(tài)都代表一個(gè)長(zhǎng)度為n的序列(a0a1a2…an-1)。在主時(shí)鐘脈沖作用下，寄存器各位共同右移一位，a0輸出，而an-1來自原先狀態(tài)所決定的一個(gè)反饋值f(a0a1a2…an-1)。f(a0a1a2…an-1)是預(yù)先設(shè)定好的一個(gè)n元布爾函數(shù)，于是有關(guān)系：特別是當(dāng)f(a0a1a2…an-1)為線性函數(shù)時(shí)，有

(2-5)這里,各ci∈GF(2)，即:(2-6)這個(gè)系統(tǒng)稱為線性反饋移位寄存器(LFSR)，如圖2.3所示。圖2.3反饋移位寄存器

如圖2.4所示的三級(jí)線性反饋移位電路，任意給定非零初態(tài)就能輸出一個(gè)周期為T=7的偽隨機(jī)序列。圖2.4中，左右兩電路都是三級(jí)線性反饋移位器，區(qū)別僅在于抽頭的位置不同。當(dāng)初態(tài)為001時(shí)，左右兩電路寄存器狀態(tài)的變化如表2.1所示。它們分別不斷循環(huán)地輸出1001011和1001110。當(dāng)初態(tài)為101時(shí)，可得到周期為4的偽隨機(jī)序列1011的循環(huán)，它的電路如圖2.5所示。圖2.4三級(jí)移位寄存器構(gòu)成的m序列發(fā)生器表2.1三級(jí)m序列的輸出圖2.5非線性反饋三級(jí)移位寄存器2.2.2m序列

1.特征多項(xiàng)式

為了利用多項(xiàng)式的代數(shù)理論來研究線性反饋移位寄存器(LFSR)產(chǎn)生偽隨機(jī)序列的規(guī)律，定義特征多項(xiàng)式：(2-7)用它來描述線性反饋移位寄存器的構(gòu)造：各xi只是為了區(qū)分寄存器的位序號(hào)，而各ci值表示該位有無反饋，有則為1，無則為0。

為什么會(huì)是一個(gè)n次多項(xiàng)式呢？因?yàn)長(zhǎng)FSR各位的輸入都來自它前一位的輸出，xn-1位的輸入來自xn位的輸出，而xn位的寄存器是不存在的，代替xn位的是反饋回來的數(shù)據(jù)，反饋關(guān)系可表達(dá)為(2-8)將等號(hào)左面的xn移到等號(hào)右面，便是特征多項(xiàng)式p(x)。圖2.4給出的兩個(gè)三級(jí)線性反饋移位電路的特征多項(xiàng)式分別為

p(x)=x3+x+1和p(x)=x3+x2+1

它們對(duì)應(yīng)的本原元素α滿足方程p(α)=0，在模2運(yùn)算下等價(jià)于：此即電路抽頭位置所表示的反饋關(guān)系。當(dāng)然還可以存在其他形式的三級(jí)線性反饋移位電路，如：p(x)=x3+1和p(x)=x3+x2+x+1

但它們產(chǎn)生的分別是周期為T=3和T=4的偽隨機(jī)序列，其電路如圖2.6所示。寫出一個(gè)特征多項(xiàng)式pn(x),就能構(gòu)造出一個(gè)線性移位寄存器，于是就對(duì)應(yīng)著一個(gè)偽隨機(jī)序列{ai}，因而我們常用{ai}∈S{pn(x)}表示{ai}屬于由pn(x)所描述的非零偽隨機(jī)序列。這里的n表示n級(jí)反饋移位寄存器。圖2.6三級(jí)移位寄存器構(gòu)成的m序列發(fā)生器2.m序列三級(jí)的線性反饋移位寄存電路所產(chǎn)生的偽隨機(jī)序列，其周期最長(zhǎng)只能為7。這是因?yàn)閚=3位的寄存器全部狀態(tài)共2n=8個(gè)，除全零狀態(tài)之外，最多只能在2n-1=7個(gè)狀態(tài)間循環(huán)。所以，n級(jí)的線性反饋移位寄存電路所產(chǎn)生的偽隨機(jī)序列，其周期T不會(huì)大于2n-1。

定義：周期達(dá)到2n-1的n級(jí)線性反饋移位寄存器的輸出序列，稱為m序列。

定理：{ai}為m序列的充要條件是pn(x)為本原多項(xiàng)式。事實(shí)上，pn(x)是本原多項(xiàng)式，就表明pn(x)的根是GF(2n)域的本原元素，而本原元素的循環(huán)階是T=2n-1，達(dá)到了最大的循環(huán)周期。

因此，要想知道n級(jí)線性反饋移位寄存器能產(chǎn)生多少種不同的m序列，只要看GF(2n)域中n級(jí)的本原多項(xiàng)式有多少個(gè)即可。根據(jù)有限域理論，計(jì)算公式是：(2-9)式中，Φ(T)為歐拉數(shù)，代表與T互素的同余類的個(gè)數(shù)(凡是除以T后余數(shù)相同的整數(shù)為一個(gè)同余類)。Φ(T)的計(jì)算公式是：(2-10)例如，對(duì)于n=3的LFSR，有

T=23-1=7；Φ(7)=7-1=6；表明存在兩個(gè)3次本原多項(xiàng)式，分別為

p(x)=x3+x+1和p(x)=x3+x2+1分別產(chǎn)生兩種不同抽頭位置的循環(huán)移位電路。又如，n=4時(shí)，

T=24-1=15；兩個(gè)4次本原多項(xiàng)式是：

p(x)=x4+x+1和p(x)=x4+x3+1

表2.2中列出了n≤24以內(nèi)的線性反饋移位寄存器的周期和m序列的個(gè)數(shù)。表2.2n=24以內(nèi)的線性反饋移位寄存器的周期和m序列的個(gè)數(shù)

【例1】構(gòu)造一個(gè)n=5的LFSR，并計(jì)算所產(chǎn)生m序列的周期和個(gè)數(shù)。

解：n=5級(jí)的線性反饋移位寄存器所產(chǎn)生的m序列的周期為

T=25-1=31由

Φ(31)=31-1=30；知共有6種不同的五級(jí)m序列。不妨查本原多項(xiàng)式表，找到n=5的一個(gè)本原多項(xiàng)式，其八進(jìn)制表達(dá)形式為

(45)8=(100101)2

即p(x)=x5+x2+1對(duì)應(yīng)的電路如圖2.7所示。圖2.7n=5的移位寄存器構(gòu)成的m序列發(fā)生器2.2.3線性反饋移位寄存器的軟件實(shí)現(xiàn)

m序列也可以用計(jì)算機(jī)程序產(chǎn)生。首先根據(jù)所需偽隨機(jī)序列周期來設(shè)計(jì)移位寄存器的級(jí)數(shù)n，然后從本原多項(xiàng)式表中選取pn(x)。下面是一些本原多項(xiàng)式的非零系數(shù)：

(3,1,0)，(4,1,0)，(5,2,0)，(6,1,0)，(7,3,0)，(9,4,0)，(10,3,0)，(11,2,0)，(15,1,0)，(17,3,0)，(17,6,0)，(18,7,0)，(20,3,0)，(21,2,0)，(23,5,0)，(28,3,0)，(29,2,0)，(31,3,0)，(32,7,6,2,0)，(32.7,5,3,2,1,0)，(33,16,4,1,0)，…以pn(x)=x32+x7+x5+x3+x2+x+1為例，根據(jù)特征多項(xiàng)式不難畫出一個(gè)32位的線性反饋移位寄存器電路示意圖，如圖2.8所示。圖2.8pn(x)=x32+x7+x5+x3+x2+x+1的電路C語言源程序?yàn)?/p>

IntLFSR{StaticunsignedlongShiftregister=1;/*Anythingbut0.*/Shiftregister=((((shiftregister>>7)∧(shiftregister>>5)∧(shiftregister>>3)∧(shiftregister>>2)∧(shiftregister>>1)∧shiftregister)&0x00000001)<<31)|(shiftregister>>1);returnshiftregister&0x00000001;}

2.2.4m序列的統(tǒng)計(jì)性質(zhì)

m序列的統(tǒng)計(jì)性質(zhì)如下：

(1)在一個(gè)周期內(nèi)0和1的個(gè)數(shù)至多相差1位。

(2)游程特征基本符合Golomb要求：①任一循環(huán)周期中含2n-1個(gè)1和2n-1-1個(gè)0。這是因?yàn)樾蛄械呐挪纪耆Q于寄存器中狀態(tài)的變化，每當(dāng)a0移出一位成為序列中新加入的一個(gè)碼元后，寄存器上一位又移入a0，可見a0有過些什么值，輸出序列就出現(xiàn)些什么值。n位寄存器共2n種不同的狀態(tài)，a0位為1與為0各占2n種的一半，即2n-1次，所以m序列的任一循環(huán)周期中1出現(xiàn)2n-1次；由于全0狀態(tài)不出現(xiàn)，因而0出現(xiàn)2n-1-1次。②游程最長(zhǎng)為n，有一個(gè)長(zhǎng)為n的1游程，卻沒有長(zhǎng)為n的0游程。這是因?yàn)橹挥幸粋€(gè)全1狀態(tài)，而沒有全0狀態(tài)。③沒有長(zhǎng)為n-1的1游程，卻有一個(gè)長(zhǎng)為n-1的0游程。這是因?yàn)橐呀?jīng)有了一個(gè)全1狀態(tài)，它的前一個(gè)狀態(tài)是11…110，后一個(gè)狀態(tài)是011…11，二者雖都是n-1個(gè)1的狀態(tài)，卻不能產(chǎn)生n-1的1游程，因?yàn)檫@三個(gè)狀態(tài)進(jìn)入系列后產(chǎn)生的是同一個(gè)長(zhǎng)為n的1游程。而這兩個(gè)n-1個(gè)1的狀態(tài)既然已經(jīng)出現(xiàn)，同一周期中就不會(huì)再出現(xiàn)第三個(gè)n-1個(gè)1的狀態(tài)了。長(zhǎng)為n-1的0游程卻是可以存在的，這是由于不存在全0狀態(tài)，所以n-1個(gè)0的狀態(tài)100…00和00…001都可以存在，它們產(chǎn)生的是同一個(gè)長(zhǎng)為n-1的0游程。④長(zhǎng)為r≤n-2的1游程和0游程各為2n-r-2個(gè)。這是因?yàn)檫@種游程意味著狀態(tài)中存在形如011…110(r個(gè)1)的串，這種游程的數(shù)目就等于狀態(tài)中其余n-r-2位的狀態(tài)數(shù)目，此即2n-r-2。⑤每一循環(huán)中共有2n-2個(gè)1游程和2n-2個(gè)0游程(長(zhǎng)度大于1的)。這是因?yàn)椋?3)周期為2n-1的m序列，其異相自相關(guān)函數(shù)等于。

證明：由前知R(τ)等于{ai}和{ai+τ}兩序列對(duì)應(yīng)位置上有相同值的個(gè)數(shù)減去不同值的個(gè)數(shù)，再除以周期T。當(dāng){ai}與{ai+τ}逐位相加后，得到的必然仍為S{Pn(x)}中的一個(gè)序列{bj}。{bj}中的0代表{ai}和{ai+τ}對(duì)應(yīng)位相同的情況，{bj}中的1代表{ai}和{ai+τ}中對(duì)應(yīng)位不同的情況，而由性質(zhì)①知道，0的個(gè)數(shù)比1的個(gè)數(shù)少一個(gè)，故分子是-1，分母是周期2n-1。

(4)n級(jí)線性移位寄存器可以產(chǎn)生λ(n)種不同結(jié)構(gòu)的m序列；每給定一種結(jié)構(gòu)，還可以選擇2n-1個(gè)不同的初始狀態(tài)，因而所能產(chǎn)生密鑰的總數(shù)是λ(n)·(2n-1)個(gè)。2.2.5線性反饋移位寄存器輸出序列的復(fù)雜度

能用線性反饋移位寄存器來產(chǎn)生有限長(zhǎng)度的任意序列{ai}嗎？設(shè){ai}=a0a1a2…aN-1，序列長(zhǎng)度為N。顯然，長(zhǎng)度為N的自然碼中肯定包含它，因此N級(jí)LFSR肯定可以產(chǎn)生它，只要取反饋函數(shù)f(x)=1+xN，初始狀態(tài)是什么自然碼就產(chǎn)生什么序列。然而這并不是最小的LFSR。任意給定一個(gè)長(zhǎng)度為N的偽隨機(jī)序列{ai}，如何構(gòu)造一個(gè)盡可能短的LFSR來產(chǎn)生它？可以分三種情況來討論：

(1)存在一個(gè)n，恰能使N=2n-1，并且序列{ai}的排列情況在λ(n)種周期為N的m序列中可以找到，則相應(yīng)的n級(jí)(LFSR)就是能產(chǎn)生{ai}的最短的發(fā)生器。(2)雖然N=2n-1，但因所給定{ai}的排布花樣更多，變化更復(fù)雜，以致于在N=2n-1的λ(n)個(gè)m序列中不能找到它，需要在更大的n值(比如n1>n)的m序列中才能包括它，那么就可以用級(jí)數(shù)為n1的LFSR來產(chǎn)生它。顯然，這時(shí)N1=2n1-1，使N1>N，{ai}只是周期為N1的m序列中的一個(gè)段落。

(3)不存在恰能使N=2n-1的n值，但可以找到一個(gè)盡可能小的L值，使N<2L-1，并且序列{ai}在λ(L)種周期為2L-1的m序列中可以找到，或者被包含，那么就可以用級(jí)數(shù)為L(zhǎng)的LFSR產(chǎn)生它。以上分析表明，序列越復(fù)雜，恰能產(chǎn)生它的m序列的級(jí)數(shù)就越高，因此要定義任意一個(gè)偽隨機(jī)序列{ai}的復(fù)雜度C({ai})，可以先來尋找恰能包含它的最短的m序列，然后用產(chǎn)生這個(gè)m序列的LFSR的級(jí)數(shù)n來作為它的復(fù)雜度的定義。

定義：二元序列{ai}=a0a1…aN-1的線性復(fù)雜度C({ai})的定義是恰能產(chǎn)生完整包含該序列{ai}的級(jí)數(shù)最少的線性反饋移位寄存器的級(jí)數(shù)n。

C({ai})=nLFSR(2-11)【例2】討論下述3個(gè)N=6的序列的復(fù)雜度。

(1){ai}=100101；

(2){bi}=100110;(3){ci}=101010。解：(1){ai}=100101：它被包含在三級(jí)LFSR產(chǎn)生的序列//1001011//中，所以它的復(fù)雜度為3；(2){bi}=100110：它也是N=6的序列，但在兩個(gè)三級(jí)LFSR序列//1001011//和//1001110//中都找不到，在四級(jí)LFSR的m序列//100010011010111//中方可包含，因此它的復(fù)雜度為4。

(3){ci}=101010：它還是N=6的序列，但卻只能在五級(jí)LFSR的m序列//1000010010110011111000110111010//中才能找到相應(yīng)段落，因此它的復(fù)雜度C({ai})=5。對(duì)全零序列{ai}約定C({ai})=0；長(zhǎng)度為N的任意序列，復(fù)雜度最大為N；如果是n級(jí)m序列，則復(fù)雜度為C({ai})=n=lb(N+1)

顯然，用線性反饋移位寄存器產(chǎn)生的偽隨機(jī)序列，其復(fù)雜度都不高。由表2.2中所列數(shù)據(jù)看到，周期為T=16777215的序列，復(fù)雜度才是C({ai})=n=24。

結(jié)論：線性反饋移位寄存器產(chǎn)生的m序列，是構(gòu)造密鑰序列的好素材，其周期長(zhǎng)度可以做到很大，隨機(jī)性也十分接近Golomb要求。但缺點(diǎn)是復(fù)雜度太低，必須設(shè)法解決。2.2.6m序列的破譯［5］

作為密鑰用的偽隨機(jī)序列，復(fù)雜度過低有何問題呢？答案是安全性太低！理論上可以證明，只要知道n級(jí)m序列中的相繼2n位，就能推測(cè)出它的特征多項(xiàng)式，進(jìn)而得到整個(gè)序列。由式(2-5)知，n級(jí)線性反饋移位寄存器的反饋關(guān)系可表示為

c0a0⊕c1a1⊕…⊕cn-2

an-2⊕cn

-1an-1=an(2-12)

因?yàn)閙序列實(shí)際上是線性反饋移位寄存器歷史狀態(tài)的記錄，所以線性反饋移位寄存器狀態(tài)的反饋關(guān)系也就是m序列相鄰n+1位之間的約束關(guān)系。設(shè)m序列的連續(xù)2n位為

x1，x2，x3，…，xn，xn+1，…，x2n

則相鄰n+1位之間有以下的遞推關(guān)系：

c0

x1⊕c1x2⊕…⊕cn-2

xn-1⊕cn

-1xn

=xn+1

c0

x2⊕c1x3⊕…⊕cn-2

xn⊕cn-1xn+1=xn+2c0

x3⊕c1x4⊕…⊕cn-2

xn+1⊕cn-1xn+2=xn+3c0

xn⊕c1xn+1⊕…⊕cn-2

x2n-2⊕cn

-1x2n-1=x2n…寫成矩陣形式為(2-13)

如果上式左面的n×n方陣(不妨叫做錯(cuò)位方陣)是非奇異的，逆矩陣存在，就能夠得到：(2-14)

這樣，就由相繼2n位m序列求出了各個(gè)反饋系數(shù)。

然而，一般情況下總是只知道一段連續(xù)的m序列，并不知道產(chǎn)生它的LFSR的級(jí)數(shù)n，破譯者首先必須設(shè)法確定n值是多少，才能用式(2-14)來計(jì)算各反饋系數(shù)。設(shè)已知的m序列為x1，x2，x3，…；因?yàn)槲覀儾恢纍等于多少，不妨從k=1，2，3，…測(cè)試起，這時(shí)式(2-13)的左邊的方陣分別為(2-15)

對(duì)每一種k×k方陣，首先計(jì)算模2行列式是否為零，若為零，則逆矩陣不存在，表明所測(cè)試的k值不對(duì)。若行列式非零，則由式(2-14)解出相應(yīng)的系數(shù)c0,c1,…，ck，把這些系數(shù)代回式(2-13)，檢驗(yàn)后面的所有數(shù)據(jù)是否滿足。一旦發(fā)現(xiàn)有不滿足的數(shù)據(jù)，則說明所測(cè)試的k值還是不對(duì)。只有后面的所有數(shù)據(jù)統(tǒng)統(tǒng)滿足式(2-13)，才表明所測(cè)試的k值是m序列的級(jí)數(shù)n。當(dāng)測(cè)試通不過時(shí)，應(yīng)再測(cè)試更大的方陣。一種簡(jiǎn)化的測(cè)試方法是，計(jì)算式(2-15)的各個(gè)行列式模2值，凡是等于0的都可以剔除，在模2值等于1的行列式中，k值最大的那個(gè)矩陣就應(yīng)當(dāng)是所尋找的矩陣。將其代回式(2-14)即可求得各個(gè)反饋系數(shù)。2.3非線性序列［6］

2.3.1M序列

如果反饋函數(shù)f(a1a2…an)為非線性函數(shù)，便構(gòu)成非線性移位寄存器，其輸出序列為非線性序列，其周期最大可以達(dá)到2n。能達(dá)到這個(gè)最大周期2n的序列叫做M序列。

M序列具有以下統(tǒng)計(jì)特性：

(1)在一個(gè)周期(2n位)之內(nèi)，0和1的個(gè)數(shù)各為一半(2n-1)。

(2)在一個(gè)周期內(nèi)，總游程為2n-1，其中0、1游程各半：長(zhǎng)為n的0游程和1游程各一個(gè)，長(zhǎng)為n-1的0、1游程均不存在，長(zhǎng)為i(1≤i≤n-2)的0、1游程各2n-i-1個(gè)。

(3)周期為2n的序列共有個(gè)，但它們并非都是M序列，其中n級(jí)線性反饋寄存器產(chǎn)生的有2n種，由它們生成(不同初態(tài))的線性序列就有2n×2n=22n種。理論指出在GF(2)域上，n級(jí)M序列的總數(shù)為個(gè)，當(dāng)n較大時(shí)，非線性反饋系列的數(shù)量是巨大的，有很大的利用空間。

(4)n級(jí)M序列的復(fù)雜度為

由上述性質(zhì)可見，M序列有很好的統(tǒng)計(jì)性質(zhì)，較高的復(fù)雜度和大量可供選擇的序列，然而，并不是所有的M序列都能當(dāng)作良好的密鑰序列使用。鑒于非線性函數(shù)的復(fù)雜性，目前對(duì)非線性移位寄存器的研究仍處于非常艱難的地步，取得成果較多的是通過線性移位寄存器來開發(fā)的非線性序列。2.3.2非線性前饋序列

線性反饋移位寄存器產(chǎn)生的m序列，因其復(fù)雜度太低而不便于直接作為密鑰流使用，但可以用它作為一個(gè)驅(qū)動(dòng)源來推動(dòng)另一個(gè)非線性電路。圖2.9所示的f(x)是非線性網(wǎng)絡(luò)，也叫前饋電路，當(dāng)LFSR處于不同狀態(tài)時(shí)，f(x)便通過各位之間的非線性運(yùn)算，輸出不同的ki值。顯然,{ki}序列的周期與原來LFSR的周期相同，然而復(fù)雜度卻大大提高了。{ki}稱為前饋序列。理論證明，如果f(x)的次數(shù)為l，那么由n級(jí)m序列為驅(qū)動(dòng)源的前饋序列{ki}的復(fù)雜度滿足：(2-16)圖2.9非線性前饋序列電路原理圖式中，是n中取j的組合數(shù)。由于前饋序列的周期等于LFSR的周期T=2n-1，因此由前饋電路輸出的非線性偽隨機(jī)序列周期也是T，可知它的復(fù)雜度最大是T。一般來說，通過前饋網(wǎng)絡(luò)適當(dāng)?shù)姆蔷€性濾波，可以得到復(fù)雜度接近2n-1的前饋序列。前饋序列的隨機(jī)性與前饋網(wǎng)絡(luò)的設(shè)計(jì)有關(guān)，比如增加項(xiàng)數(shù)可以改善前饋序列的統(tǒng)計(jì)特性。2.3.3非線性組合序列

用多個(gè)線性反饋移位序列共同驅(qū)動(dòng)一個(gè)非線性網(wǎng)絡(luò)，產(chǎn)生的非線性序列(見圖2.10)具有更好的特性：

(1)若各個(gè)LFSR的級(jí)數(shù)ni兩兩互素，則組合序列的周期(2-17)圖2.10多個(gè)線性反饋移位序列驅(qū)動(dòng)的非線性網(wǎng)絡(luò)(2)組合序列的復(fù)雜度為

C({ki})=f(n1n2…)(2-18)例如，3個(gè)LFSR的級(jí)數(shù)分別為3、5、7,非線性函數(shù)為

f(x1,x2,x3)=x3+x1x2+x1x2x3則組合序列的周期為

(23-1)(25-1)(27-1)=7×31×127=27559復(fù)雜度為

f(n1,n2,n3)=7+3×5+3×5×7=1271973年，P.R.Geffe提出一種組合序列設(shè)計(jì)方案，見圖2.11左圖所示。它采用3個(gè)級(jí)數(shù)分別為r、s、t的線性移位寄存器組合而成，r、s、t互素。請(qǐng)注意，寄存器t的輸出須求反后再與寄存器s的輸出相乘。該組合網(wǎng)路產(chǎn)生的非線性復(fù)合序列的周期為

T=(2r-1)(2s-1)(2t-1)(2-19)復(fù)雜度為

C(M)=(r+s)t+s(2-20)

由多個(gè)這樣的組合網(wǎng)路進(jìn)一步組合，可產(chǎn)生復(fù)雜度很高的非線性組合序列，圖2.11的右圖是一個(gè)實(shí)例。圖2.11一種多路m序列非線性組合的實(shí)例2.3.4非線性復(fù)合序列

復(fù)合器實(shí)際上是一個(gè)地址選擇器。由A寄存器的狀態(tài)來選擇B寄存器的某一位輸出{ki}。例如圖2.12所示的LFSRA是三位，LFSRB是四位，復(fù)合器所設(shè)計(jì)的選擇方式是由A2A1的碼值決定LFSRB的地址，正好選通LFSRB四位中的任何一位。如果t1時(shí)刻A2A1A0=011，B3B2B1B0=1100，則選擇器A2A1=01，選通了B1的地址，于是B1=0輸出。如果t2時(shí)刻A2A1A0＝101，B3B2B1B0=0110，則A2A1＝10,選通了B2＝1。若Ａ、Ｂ兩個(gè)LFSR的級(jí)數(shù)n與m互素，則組合后輸出序列的周期可達(dá)到

T=(2n-1)(2m-1)