現(xiàn)代密碼學(xué)第5章：序列密碼

序列密碼《現(xiàn)代密碼學(xué)》第5章1本章主要內(nèi)容1、序列密碼的基本概念2、線性反饋移位寄存器3、線性移位寄存器的一元多項(xiàng)式表示4、m序列的偽隨機(jī)性5、M序列的特性6、m序列密碼的破譯7、非線性序列8、歐洲NESSIE工程及其征集的Lili-128候選算法9、習(xí)題2序列密碼的基本思想是利用密鑰k產(chǎn)生一個(gè)密鑰流z=z0z1…，并使用如下規(guī)則對(duì)明文串x=x0x1x2…加密：

y=y0y1y2…=Ez0(x0)Ez1(x1)Ez2(x2)…。密鑰流由密鑰流發(fā)生器f產(chǎn)生：zi=f(k,σi)，這里σi是加密器中的記憶元件（存儲(chǔ)器）在時(shí)刻i的狀態(tài)，f是由密鑰k和σi產(chǎn)生的函數(shù)。1.序列密碼的基本概念3分組密碼與序列密碼的區(qū)別就在于有無(wú)記憶性（如圖）。序列密碼的滾動(dòng)密鑰z0=f(k,σ0)由函數(shù)f、密鑰k和指定的初態(tài)σ0完全確定。此后，由于輸入加密器的明文可能影響加密器中內(nèi)部記憶元件的存儲(chǔ)狀態(tài)，因而σi(i>0)可能依賴(lài)于k，σ0，x0，x1，…，xi-1等參數(shù)。1.序列密碼的基本概念4分組密碼和序列密碼的比較5序列密碼的例子：設(shè)對(duì)定義取K=8明文為rendezvous明文對(duì)應(yīng)的整數(shù)序列為17413342521142018密鑰流為：8174133425211420密文對(duì)應(yīng)的整數(shù)序列為2521171673209812密文為：zvrqhdujim怎樣解密？6根據(jù)加密器中記憶元件的存儲(chǔ)狀態(tài)σi是否依賴(lài)于輸入的明文字符，序列密碼可進(jìn)一步分成同步和自同步兩種。

σi獨(dú)立于明文字符的叫做同步序列密碼，否則叫做自同步序列密碼。由于自同步序列密碼的密鑰流的產(chǎn)生與明文有關(guān)，因而較難從理論上進(jìn)行分析。目前大多數(shù)研究成果都是關(guān)于同步序列密碼的。1.1同步序列密碼7在同步序列密碼中，由于zi=f(k,σi)與明文字符無(wú)關(guān)，因而此時(shí)密文字符yi=Ezi(xi)也不依賴(lài)于此前的明文字符。因此，可將同步序列密碼的加密器分成密鑰流產(chǎn)生器和加密變換器兩個(gè)部分。如果與上述加密變換對(duì)應(yīng)的解密變換為xi=Dzi(yi)，則可給出同步序列密碼體制的模型如下圖所示。1.1同步序列密碼8滾動(dòng)密鑰生成器滾動(dòng)密鑰生成器KK安全信道…………同步序列密碼體制模型9同步序列密碼的加密變換Ezi可以有多種選擇，只要保證變換是可逆的即可。實(shí)際使用的數(shù)字保密通信系統(tǒng)一般都是二元系統(tǒng)，因而在有限域CF(2)上討論的二元加法序列密碼（如下圖）是目前最為常用的序列密碼體制，其加密變換可表示為yi=zixi。

1.1同步序列密碼10加法序列密碼體制模型滾動(dòng)密鑰生成器滾動(dòng)密鑰生成器KK安全信道…………11一次一密密碼是加法序列密碼的原型。事實(shí)上，如果（即密鑰用作滾動(dòng)密鑰流），則加法序列密碼就退化成一次一密密碼。實(shí)際使用中，密碼設(shè)計(jì)者的最大愿望是設(shè)計(jì)出一個(gè)滾動(dòng)密鑰生成器，使得密鑰經(jīng)其擴(kuò)展成的密鑰流序列具有如下性質(zhì)：極大的周期、良好的統(tǒng)計(jì)特性、抗線性分析、抗統(tǒng)計(jì)分析。

1.1同步序列密碼12有限狀態(tài)自動(dòng)機(jī)是具有離散輸入和輸出（輸入集和輸出集均有限）的一種數(shù)學(xué)模型，由以下3部分組成：①有限狀態(tài)集②有限輸入字符集和有限輸出字符集。③轉(zhuǎn)移函數(shù)即在狀態(tài)為si，輸入為Aj(1)時(shí)，輸出為Ak(2)，而狀態(tài)轉(zhuǎn)移為sk。1.2有限狀態(tài)自動(dòng)機(jī)13有限狀態(tài)自動(dòng)機(jī)可用有向圖表示，稱(chēng)為轉(zhuǎn)移圖。轉(zhuǎn)移圖的頂點(diǎn)對(duì)應(yīng)于自動(dòng)機(jī)的狀態(tài)，若狀態(tài)si在輸入A(1)i時(shí)轉(zhuǎn)為狀態(tài)sj，且輸出一字符A(2)j，則在轉(zhuǎn)移圖中，從狀態(tài)si到狀態(tài)sj有一條標(biāo)有(A(1)i,A(2)j)的弧線，見(jiàn)下圖。14S1S2S3有限狀態(tài)自動(dòng)機(jī)的轉(zhuǎn)移圖15例：轉(zhuǎn)移函數(shù)由下表給出：16上例中，若輸入序列為，初始狀態(tài)為s1，則得到狀態(tài)序列s1s2s2s3s2s1s2輸出字符序列思考題：如果上面的輸入序列變?yōu)椋簞t上面的結(jié)果為什么？1.2有限狀態(tài)自動(dòng)機(jī)172.密鑰序列生成器(KG)我們知道，序列密碼的關(guān)鍵在于密鑰序列生成器KG的設(shè)計(jì)。一般來(lái)說(shuō)，KG的輸入——種子密鑰k是較短的，人們卻希望它的輸出——密鑰序列k對(duì)不知情的人來(lái)說(shuō)象是隨機(jī)的。到底該從哪些角度把握隨機(jī)性等、才使所設(shè)計(jì)出來(lái)的KG能夠具有我們需要的安全程度？18密鑰序列生成器(KG)基本要求人們就目前的想象和預(yù)見(jiàn)，對(duì)KG提出了以下基本要求：種子密鑰k的變化量足夠大，一般應(yīng)在2128以上；KG產(chǎn)生的密鑰序列k具極大周期，一般應(yīng)不小于255；k具有均勻的n-元分布，即在一個(gè)周期環(huán)上，某特定形式的n-長(zhǎng)bit串與其求反，兩者出現(xiàn)的頻數(shù)大抵相當(dāng)(例如，均勻的游程分布)；19k不可由一個(gè)低級(jí)(比如，小于106級(jí))的LFSR產(chǎn)生，也不可與一個(gè)低級(jí)LFSR產(chǎn)生的序列只有比率很小的相異項(xiàng)；利用統(tǒng)計(jì)方法由k提取關(guān)于KG結(jié)構(gòu)或K的信息在計(jì)算上不可行；混亂性.即k的每一bit均與k的大多數(shù)bit有關(guān)；擴(kuò)散性.即k任一bit的改變要引起k在全貌上的變化。密鑰序列生成器(KG)基本要求20同步序列密碼的關(guān)鍵是密鑰流產(chǎn)生器。一般可將其看成一個(gè)參數(shù)為k的有限狀態(tài)自動(dòng)機(jī)，由一個(gè)輸出符號(hào)集Z、一個(gè)狀態(tài)集∑、兩個(gè)函數(shù)φ和ψ以及一個(gè)初始狀態(tài)σ0組成（如下圖）。狀態(tài)轉(zhuǎn)移函數(shù)φ:σi→σi+1，將當(dāng)前狀態(tài)σi變?yōu)橐粋€(gè)新?tīng)顟B(tài)σi+1，輸出函數(shù)ψ:σi→zi，當(dāng)前狀態(tài)σi變?yōu)檩敵龇?hào)集中的一個(gè)元素zi。同步序列密碼密鑰流產(chǎn)生器21作為有限狀態(tài)自動(dòng)機(jī)的密鑰流生成器kkk22這種密鑰流生成器設(shè)計(jì)的關(guān)鍵在于找出適當(dāng)?shù)臓顟B(tài)轉(zhuǎn)移函數(shù)φ和輸出函數(shù)ψ，使得輸出序列z滿(mǎn)足密鑰流序列z應(yīng)滿(mǎn)足的幾個(gè)條件，并且要求在設(shè)備上是節(jié)省的和容易實(shí)現(xiàn)的。為了實(shí)現(xiàn)這一目標(biāo)，必須采用非線性函數(shù)。作為有限狀態(tài)自動(dòng)機(jī)的密鑰流生成器23由于具有非線性的φ的有限狀態(tài)自動(dòng)機(jī)理論很不完善，相應(yīng)的密鑰流產(chǎn)生器的分析工作受到極大的限制。相反地，當(dāng)采用線性的φ和非線性的ψ時(shí)，將能夠進(jìn)行深入的分析并可以得到好的生成器。為方便討論，可將這類(lèi)生成器分成驅(qū)動(dòng)部分和非線性組合部分（如下圖）。驅(qū)動(dòng)部分控制生成器的狀態(tài)轉(zhuǎn)移，并為非線性組合部分提供統(tǒng)計(jì)性能好的序列；而非線性組合部分要利用這些序列組合出滿(mǎn)足要求的密鑰流序列。同步序列密碼密鑰流產(chǎn)生器24密鑰流生成器的分解驅(qū)動(dòng)子系統(tǒng)非線性組合子系統(tǒng)kk25目前最為流行和實(shí)用的密鑰流產(chǎn)生器如圖所示，其驅(qū)動(dòng)部分是一個(gè)或多個(gè)線性反饋移位寄存器。常見(jiàn)的兩種密鑰流產(chǎn)生器LFSR………FLFSR1LFSR2LFSRn……FFF26KG的一般結(jié)構(gòu)通常，人們總是把KG設(shè)計(jì)得具有一定的結(jié)構(gòu)特點(diǎn)，從而可以分析和論證其強(qiáng)度，以增加使用者的置信度。一般有以下模式：驅(qū)動(dòng)子系統(tǒng)f（可線性）非線性組合子系統(tǒng)F種子密鑰k……k=k0k1k2

KG結(jié)構(gòu)分解示意圖

27在上圖中，f——一般由m-序列(或M-序列)生成器構(gòu)成，提供若干周期大、統(tǒng)計(jì)特性好的序列(稱(chēng)為驅(qū)動(dòng)序列)。F——就是把f產(chǎn)生的多條驅(qū)動(dòng)序列綜合在一起的一些非線性編碼手段，目的是有效地破壞和掩蓋多條驅(qū)動(dòng)序列中存在的規(guī)律或關(guān)系，提高線性復(fù)雜度。KG的一般結(jié)構(gòu)28F的設(shè)計(jì)：兩種典型的基本編碼手段非線性組合生成器一個(gè)非線性組合生成器的圖示如下：N1-LFSRN2-LFSRNt-LFSR

),,,(21txxxFLkF是一個(gè)t元非線性布爾函數(shù)，一般要求：

具有較高的非線性次數(shù)；

是平衡的。29F的設(shè)計(jì)：兩種典型的基本編碼手段一個(gè)有關(guān)的結(jié)果是：若對(duì)一切i=1,2,,t，Ni-LFSR都是m-序列生成器，且ij(Ni,Nj)=1，則

p(k)=(2N1-1)(2N2-1)

(2Nt-1)，

(k)=F*(N1,N2,

,Nt)，這里F*是把F在F2上的多項(xiàng)式表示作為整數(shù)環(huán)Z上的多項(xiàng)式來(lái)計(jì)算而得的函數(shù)。30F的設(shè)計(jì)：兩種典型的基本編碼手段非線性組合生成器的一個(gè)特殊情形是所謂的非線性濾波生成器，或也稱(chēng)為前饋網(wǎng)絡(luò)，它的圖示如下：N-LFSR

k31F的設(shè)計(jì)：兩種典型的基本編碼手段鐘控序列生成器一個(gè)鐘控序列生成器的圖示如下：LLLN1101++iiinnnxxxxx}{inx時(shí)刻iN-LFSR作速度因子控制器D=be-1·2e-1

++b1·2+

b0+cbe-1

b1b0滑動(dòng)位被鐘控序列此時(shí)刻輸出指針位置下一時(shí)刻輸出指針位置輸出指針初始位置n00隨意選定(缺省值為0）ni+1=ni+D32F的設(shè)計(jì)：兩種典型的基本編碼手段一個(gè)特殊情形就是“停停走走”(Stop-and-Go)生成器，它的圖示如下：n-LFSR1m-LFSR2時(shí)鐘脈沖k一個(gè)有關(guān)的結(jié)果是：若n-LFSR1與m-LFSR2都是m-序列生成器，且n|m或2n-1為素?cái)?shù)，則

p(k)=(2n-1)(2m-1)，

(k)至少為[m,n](2(m,n)-1)。33移位寄存器是序列密碼產(chǎn)生密鑰流的一個(gè)主要組成部分。GF(2)上一個(gè)n級(jí)反饋移位寄存器由n個(gè)二元存儲(chǔ)器與一個(gè)反饋函數(shù)f(a1,a2,…,an)組成，如圖所示。2.線性反饋移位寄存器….輸出序列34每一存儲(chǔ)器稱(chēng)為移位寄存器的一級(jí)，在任一時(shí)刻，這些級(jí)的內(nèi)容構(gòu)成該反饋移位寄存器的狀態(tài)，每一狀態(tài)對(duì)應(yīng)于GF(2)上的一個(gè)n維向量，共有2n種可能的狀態(tài)。每一時(shí)刻的狀態(tài)可用n長(zhǎng)序列a1,a2,…,an或n維向量(a1,a2,…,an)表示，其中ai是第i級(jí)存儲(chǔ)器的內(nèi)容。GF(2)上的n級(jí)反饋移位寄存器35初始狀態(tài)由用戶(hù)確定，當(dāng)?shù)趇個(gè)移位時(shí)鐘脈沖到來(lái)時(shí)，每一級(jí)存儲(chǔ)器ai都將其內(nèi)容向下一級(jí)ai-1傳遞，并根據(jù)寄存器此時(shí)的狀態(tài)a1,a2,…,an計(jì)算f(a1,a2,…,an)，作為下一時(shí)刻的an。反饋函數(shù)f(a1,a2,…,an)是n元布爾函數(shù)，即n個(gè)變?cè)猘1,a2,…,an可以獨(dú)立地取0和1這兩個(gè)可能的值，函數(shù)中的運(yùn)算有邏輯與、邏輯或、邏輯補(bǔ)等運(yùn)算，最后的函數(shù)值也為0或1。GF(2)上的n級(jí)反饋移位寄存器36例：下圖是一個(gè)3級(jí)反饋移位寄存器，其初始狀態(tài)為(a1,a2,a3)=(1,0,1)，輸出可由表2.2求出。一個(gè)3級(jí)反饋移位寄存器GF(2)上的n級(jí)反饋移位寄存器輸出序列37一個(gè)3級(jí)反饋移位寄存器的狀態(tài)和輸出狀態(tài)（a1,a2,a3)輸出101110111011101110

10111038即輸出序列為101110111011…，周期為4。如果移位寄存器的反饋函數(shù)f(a1,a2,…,an)是a1，a2，…，an的線性函數(shù)，則稱(chēng)之為線性反饋移位寄存器LFSR（linearfeedbackshiftregister）。此時(shí)f可寫(xiě)為f(a1,a2,…,an)=cna1cn-1a2…c1an其中常數(shù)ci=0或1，是模2加法。ci=0或1可用開(kāi)關(guān)的斷開(kāi)和閉合來(lái)實(shí)現(xiàn)，如下圖所示。線性反饋移位寄存器39練習(xí)：輸出序列下圖為3級(jí)反饋移位寄存器，其初始狀態(tài)為試寫(xiě)出其輸出序列，同時(shí)考慮如果初始狀態(tài)不同，輸出序列是否相同，序列的周期是否相同？40GF(2)上的n級(jí)線性反饋移位寄存器……輸出序列41輸出序列{at}滿(mǎn)足an+t=cnatcn-1at+1…c1an+t-1其中t為非負(fù)正整數(shù)。或者{an}：線性反饋移位寄存器因其實(shí)現(xiàn)簡(jiǎn)單、速度快、有較為成熟的理論等優(yōu)點(diǎn)而成為構(gòu)造密鑰流生成器的最重要的部件之一。線性反饋移位寄存器42例：下圖是一個(gè)5級(jí)線性反饋移位寄存器，其初始狀態(tài)為（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出輸出序列為1001101001000010101110110001111100110…周期為31。例：一個(gè)5級(jí)線性反饋移位寄存器輸出序列43練習(xí)：下圖為一個(gè)5級(jí)線性反饋移位寄存器，其初始狀態(tài)為則其輸出序列為？輸出序列44在線性反饋移位寄存器中總是假定c1,c2,…,cn中至少有一個(gè)不為0，否則f(a1,a2,…,an)≡0，這樣的話，在n個(gè)脈沖后狀態(tài)必然是00…0，且這個(gè)狀態(tài)必將一直持續(xù)下去。若只有一個(gè)系數(shù)不為0，設(shè)僅有cj不為0，實(shí)際上是一種延遲裝置。

一般對(duì)于n級(jí)線性反饋移位寄存器，總是假定cn=1。線性反饋移位寄存器45線性反饋移位寄存器輸出序列的性質(zhì)完全由其反饋函數(shù)決定。n級(jí)線性反饋移位寄存器最多有2n個(gè)不同的狀態(tài)。若其初始狀態(tài)為0，則其狀態(tài)恒為0。若其初始狀態(tài)非0，則其后繼狀態(tài)不會(huì)為0。因此n級(jí)線性反饋移位寄存器的狀態(tài)周期小于等于2n-1。其輸出序列的周期與狀態(tài)周期相等，也小于等于2n-1。只要選擇合適的反饋函數(shù)便可使序列的周期達(dá)到最大值2n-1，周期達(dá)到最大值的序列稱(chēng)為m序列。線性反饋移位寄存器463.線性移位寄存器的一元多項(xiàng)式表示線性移位寄存器的輸出序列滿(mǎn)足遞推關(guān)系當(dāng)k>=1時(shí)成立。寫(xiě)出來(lái)看一看：…(1)47這種遞推關(guān)系可以用一個(gè)一元高次多項(xiàng)式來(lái)表示：稱(chēng)這個(gè)多項(xiàng)式為L(zhǎng)FSR的特征多項(xiàng)式。（*）在(1)式中兩邊同時(shí)加上得到：令據(jù)其在輸出序列中元素的左右位置，左移一位相當(dāng)于乘以2，則有：線性移位寄存器的特征多項(xiàng)式48

注意：線性反饋移位寄存器與特征多項(xiàng)式是一一對(duì)應(yīng)的，如果知道了線性反饋移位寄存器的結(jié)構(gòu)，可以寫(xiě)出它的特征多項(xiàng)式，同樣可以根據(jù)特征多項(xiàng)式畫(huà)出移位寄存器的結(jié)構(gòu)。49設(shè)n級(jí)線性移位寄存器對(duì)應(yīng)于遞推關(guān)系(*)，由于ai∈GF(2)(i=1,2,…,n)，所以共有2n組初始狀態(tài)，即有2n個(gè)遞推序列，其中非恒零的有2n-1個(gè)，記2n-1個(gè)非零序列的全體為G(p(x))。50定義：給定序列{ai}，冪級(jí)數(shù)稱(chēng)為該序列的生成函數(shù)。

多項(xiàng)式表示中的部分概念51

定理2.1設(shè)p(x)=1+c1x+…+cn-1xn-1+cnxn是GF(2)上的多項(xiàng)式，G(p(x))中任一序列{ai}的生成函數(shù)A(x)滿(mǎn)足：

其中多項(xiàng)式表示中的部分概念52證明：在等式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)多項(xiàng)式表示中的部分概念53移項(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-i∑ajxj-1=(x)(證畢)

注意在GF(2)上有a+a=0。多項(xiàng)式表示中的部分概念54定理2.2p(x)|q(x)的充要條件是G(p(x))G(q(x))。證明：若p(x)|q(x)，可設(shè)q(x)=p(x)r(x)，因此所以若{ai}∈G(p(x))，則{ai}∈G(q(x))，即G(p(x))G(q(x))。多項(xiàng)式表示中的部分概念55反之，若G(p(x))G(q(x))，則對(duì)于多項(xiàng)式(x)，存在序列{ai}∈G(p(x))以A(x)=(x)p(x)為生成函數(shù)。特別地，對(duì)于多項(xiàng)式(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)。(證畢)

上述定理說(shuō)明可用n級(jí)LFSR產(chǎn)生的序列，也可用級(jí)數(shù)更多的LFSR來(lái)產(chǎn)生。多項(xiàng)式表示中的部分概念56定義：設(shè)p(x)是GF(2)上的多項(xiàng)式，使p(x)|(xp-1)的最小p稱(chēng)為p(x)的周期或階。定理2.3若序列{ai}的特征多項(xiàng)式p(x)定義在GF(2)上，p是p(x)的周期，則{ai}的周期r|p。多項(xiàng)式表示中的部分概念57證明：由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ù)不超過(guò)n-1，所以(xp-1)A(x)的次數(shù)不超過(guò)(p-n)+(n-1)=p-1。這就證明了對(duì)于任意正整數(shù)i都有ai+p=ai。設(shè)p=kr+t,0≤t<r，則ai+p=ai+kr+t=ai+t=ai，所以t=0，即r|p。（證畢）多項(xiàng)式表示中的部分概念58

n級(jí)LFSR輸出序列的周期r不依賴(lài)于初始條件，而依賴(lài)于特征多項(xiàng)式p(x)。我們感興趣的是LFSR遍歷2n-1個(gè)非零狀態(tài)，這時(shí)序列的周期達(dá)到最大2n-1，這種序列就是m序列。顯然對(duì)于特征多項(xiàng)式一樣，而僅初始條件不同的兩個(gè)輸出序列，一個(gè)記為{a(1)i}，另一個(gè)記為{a(2)i}，其中一個(gè)必是另一個(gè)的移位，即存在一個(gè)常數(shù)k，使得a(1)i=a(2)k+i,i=1,2,…多項(xiàng)式表示中的部分概念59下面討論特征多項(xiàng)式滿(mǎn)足什么條件時(shí)，LFSR的輸出序列為m序列。定理2.4設(shè)p(x)是n次不可約多項(xiàng)式，周期為m，序列{ai}∈G(p(x))，則{ai}的周期為m。多項(xiàng)式表示中的部分概念60證明：設(shè){ai}的周期為r，由定理2.3有r|m，所以r≤m。設(shè)A(x)為{ai}的生成函數(shù)，A(x)=(x)p(x)，即p(x)A(x)=(x)≠0，(x)的次數(shù)不超過(guò)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)多項(xiàng)式表示中的部分概念61于是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。（證畢）多項(xiàng)式表示中的部分概念62定理2.5n級(jí)LFSR產(chǎn)生的序列有最大周期2n-1的必要條件是其特征多項(xiàng)式為不可約的。證明：設(shè)n級(jí)LFSR產(chǎn)生的序列周期達(dá)到最大2n-1，除0序列外，每一序列的周期由特征多項(xiàng)式惟一決定，而與初始狀態(tài)無(wú)關(guān)。設(shè)特征多項(xiàng)式為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))中序列的周期一方面不超過(guò)2k-1，另一方面又等于2n-1，這是矛盾的，所以p(x)不可約。（證畢）該定理的逆不成立，即LFSR的特征多項(xiàng)式為不可約多項(xiàng)式時(shí)，其輸出序列不一定是m序列。多項(xiàng)式表示中的部分概念63例：

f(x)=x4+x3+x2+x+1為GF(2)上的不可約多項(xiàng)式，這可由x,x+1,x2+x+1都不能整除f(x)得到。以f(x)為特征多項(xiàng)式的LFSR的輸出序列可由

ak=ak-1ak-2ak-3ak-4(k≥4)

和給定的初始狀態(tài)求出，設(shè)初始狀態(tài)為0001，則輸出序列為000110001100011…，周期為5，不是m序列。多項(xiàng)式表示中的部分概念641110000110000110000111000111000011000011000011100011100001100001100001輸出狀態(tài)（）周期為5，不是m序列多項(xiàng)式表示中的部分概念65定義：若n次不可約多項(xiàng)式p(x)的階為2n-1，則稱(chēng)p(x)是n次本原多項(xiàng)式。定理2.6設(shè){ai}∈G(p(x))，{ai}為m序列的充要條件是p(x)為本原多項(xiàng)式。多項(xiàng)式表示中的部分概念66本原多項(xiàng)式：67證明：若p(x)是本原多項(xiàng)式，則其階為2n-1，由定理2.4得{ai}的周期等于2n-1，即{ai}為m序列。反之，若{ai}為m序列，即其周期等于2n-1，由定理2.5知p(x)是不可約的。由定理2.3知{ai}的周期2n-1整除p(x)的階，而p(x)的階不超過(guò)2n-1，所以p(x)的階為2n-1，即p(x)是本原多項(xiàng)式。（證畢）多項(xiàng)式表示中的部分概念68

{ai}為m序列的關(guān)鍵在于p(x)為本原多項(xiàng)式，n次本原多項(xiàng)式的個(gè)數(shù)為其中為歐拉函數(shù)。已經(jīng)證明，對(duì)于任意的正整數(shù)n，至少存在一個(gè)n次本原多項(xiàng)式。所以對(duì)于任意的n級(jí)LFSR，至少存在一種連接方式使其輸出序列為m序列。多項(xiàng)式表示中的部分概念69例：設(shè)p(x)=x4+x+1，由于p(x)|(x15-1)，但不存在小于15的常數(shù)，使得p(x)|(xl-1)，所以p(x)的階為15。p(x)的不可約性可由x,x+1,x2+x+1都不能整除p(x)得到，所以p(x)是本原多項(xiàng)式。若LFSR以p(x)為特征多項(xiàng)式，則輸出序列的遞推關(guān)系為ak=ak-1ak-4(k≥4)多項(xiàng)式表示中的部分概念70若初始狀態(tài)為1001，則輸出為：100100011110101100100011110101…狀態(tài)序列為：

1001，0100，0010，0001，1000，1100，1110，1111，0111，1011，0101，1010，1101，0110，0011，1001，0100，0010，0001……可見(jiàn)，它是周期為24-1=15，即輸出序列為m序列。多項(xiàng)式表示中的部分概念71例：(100110101111000)

按前面的性質(zhì)有：游程的總數(shù)為8，分別為1，00，11，0，1，0，1111，0000。其中有一半的游程長(zhǎng)度為2，長(zhǎng)度為2的游程為四分之一，最后有一個(gè)長(zhǎng)度為4的游程和一個(gè)長(zhǎng)度為3的游程。輸出序列72序列密碼的安全性取決于密鑰流的安全性，要求密鑰流序列有好的隨機(jī)性，以使密碼分析者對(duì)它無(wú)法預(yù)測(cè)。也就是說(shuō)，即使截獲其中一段，也無(wú)法推測(cè)后面是什么。如果密鑰流是周期的，要完全做到隨機(jī)性是困難的。嚴(yán)格地說(shuō)，這樣的序列不可能做到隨機(jī)，只能要求截獲比周期短的一段時(shí)不會(huì)泄露更多信息，這樣的序列稱(chēng)為偽隨機(jī)序列。

4.m序列的偽隨機(jī)性73為討論序列的隨機(jī)性，我們先討論隨機(jī)序列的一般特性。設(shè){ai}=(a1a2a3…)為0、1序列，例如00110111，其前兩個(gè)數(shù)字是00，稱(chēng)為0的2游程；接著是11，是1的2游程；再下來(lái)是0的1游程和1的3游程。隨機(jī)序列的特性74定義：GF(2)上周期為T(mén)的序列{ai}的自相關(guān)函數(shù)定義為R(τ)=(1/T)∑(-1)ak(-1)ak+τ,0≤τ≤T-1

定義中的和式表示序列{ai}與{ai+τ}（序列{ai}向后平移τ位得到）在一個(gè)周期內(nèi)對(duì)應(yīng)位相同的位數(shù)與對(duì)應(yīng)位不同的位數(shù)之差。當(dāng)τ=0時(shí)，R(τ)=1；當(dāng)τ≠0時(shí)，稱(chēng)R(τ)為異相自相關(guān)函數(shù)。隨機(jī)序列的特性75

Golomb對(duì)偽隨機(jī)周期序列提出了應(yīng)滿(mǎn)足的如下3個(gè)隨機(jī)性公設(shè)：①在序列的一個(gè)周期內(nèi)，0與1的個(gè)數(shù)相差至多為1。隨機(jī)序列的特性76②在序列的一個(gè)周期內(nèi)，長(zhǎng)為i的游程占游程總數(shù)的1/2i(i=1,2,…)，且在等長(zhǎng)的游程中0的游程個(gè)數(shù)和1的游程個(gè)數(shù)相等。③異相自相關(guān)函數(shù)是一個(gè)常數(shù)。公設(shè)①說(shuō)明{ai}中0與1出現(xiàn)的概率基本上相同;②說(shuō)明0與1在序列中每一位置上出現(xiàn)的概率相同;③意味著通過(guò)對(duì)序列與其平移后的序列做比較，不能給出其他任何信息。隨機(jī)序列的特性77從密碼系統(tǒng)的角度看，一個(gè)偽隨機(jī)序列還應(yīng)滿(mǎn)足下面的條件：①{ai}的周期相當(dāng)大。②{ai}的確定在計(jì)算上是容易的。③由密文及相應(yīng)的明文的部分信息，不能確定整個(gè){ai}。偽隨機(jī)序列應(yīng)滿(mǎn)足的條件78m-序列概念稱(chēng)周期達(dá)到最大值2n-1的n-LFSR（輸出）序列為（n級(jí)）m-序列。顯然，若某n-LFSR產(chǎn)生一個(gè)m-序列，則其狀態(tài)圖除了單點(diǎn)(00

0)構(gòu)成的圈外，就是由F2n\{(00

0)}中所有點(diǎn)排列而成的一個(gè)大圈，因而其任何非全零的輸出序列均是m-序列，故稱(chēng)之為m-序列生成器。例.4-LFSR[1,0,0,1]。79下一定理說(shuō)明，m序列滿(mǎn)足Golomb的3個(gè)隨機(jī)性公設(shè)。定理2.7GF(2)上的n長(zhǎng)m序列{ai}具有如下性質(zhì)：①0,1平衡性：在一個(gè)周期內(nèi)，0、1出現(xiàn)的次數(shù)分別為2n-1-1和2n-1。②游程特性：在一個(gè)周期內(nèi)，總游程數(shù)為2n-1；對(duì)1≤i≤n-2，長(zhǎng)為i的游程有2n-i-1個(gè)，且0、1游程各半；長(zhǎng)為n-1的0游程一個(gè)，長(zhǎng)為n的1游程一個(gè)。m序列的特性80③{ai}的自相關(guān)函數(shù)為m序列的特性81周期p序列a=a0a1a2

的自相關(guān)函數(shù)定義如下：自相關(guān)函數(shù)計(jì)算.對(duì)給定的周期序列a，①找出a的周期段：a0a1a2

ap-1②計(jì)算：周期序列的自相關(guān)函數(shù)計(jì)算82

(-1)a0

(-1)a1

(-1)a2

(-1)ap-1

（左環(huán)移t位）(-1)at

(-1)at+1

(-1)at+2

(-1)at-1

對(duì)位相乘后再相加，即得pCa(t)。例.對(duì)a=(10011101101)

，計(jì)算Ca(4)。自相關(guān)特性是說(shuō)，n-級(jí)m-序列a的自相關(guān)函數(shù)值如下：(a(a<<t)非全零且滿(mǎn)足a的線性遞歸關(guān)系)周期序列的自相關(guān)函數(shù)計(jì)算83證明：①在n長(zhǎng)m序列的一個(gè)周期內(nèi)，除了全0狀態(tài)外，每個(gè)n長(zhǎng)狀態(tài)（共有2n-1個(gè)）都恰好出現(xiàn)一次，這些狀態(tài)中有2n-1個(gè)在a1位是1，其余2n-1-2n-1=2n-1-1個(gè)狀態(tài)在a1位是0。②對(duì)n=1,2，易證結(jié)論成立。對(duì)n>2，當(dāng)1≤i≤n-2時(shí)，n長(zhǎng)m序列的一個(gè)周期內(nèi)，長(zhǎng)為i的0游程數(shù)目等于序列中如下形式的狀態(tài)數(shù)目：100…01*…*，其中n-i-2個(gè)*可任取0或1。這種狀態(tài)共有2n-i-2個(gè)。同理可得長(zhǎng)為i的1游程數(shù)目也等于2n-i-2，所以長(zhǎng)為i的游程總數(shù)為2n-i-1。m序列的特性84由于寄存器中不會(huì)出現(xiàn)全0狀態(tài)，所以不會(huì)出現(xiàn)0的n游程，但必有一個(gè)1的n游程，而且1的游程不會(huì)更大，因?yàn)槿舫霈F(xiàn)1的n+1游程，就必然有兩個(gè)相鄰的全1狀態(tài)，但這是不可能的。這就證明了1的n游程必然出現(xiàn)在如下的串中：當(dāng)這n+2位通過(guò)移位寄存器時(shí)，便依次產(chǎn)生以下?tīng)顟B(tài)：

m序列的特性85由于，這兩個(gè)狀態(tài)只能各出現(xiàn)一次，所以不會(huì)有1的n-1游程。于是在一個(gè)周期內(nèi)，總游程數(shù)為m序列的特性86③{ai}是周期為2n-1的m序列，對(duì)于任一正整數(shù)τ(0<τ<2n-1)，{ai}+{ai+τ}在一個(gè)周期內(nèi)為0的位的數(shù)目正好是序列{ai}和{ai+τ}對(duì)應(yīng)位相同的位的數(shù)目。設(shè)序列{ai}滿(mǎn)足遞推關(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+τ)m序列的特性87令bj=aj

aj+τ，由遞推序列{ai}可推得遞推序列{bi}，{bi}滿(mǎn)足bh+n=c1bh+n-1c2bh+n-2…cnbh{bi}也是m序列。為了計(jì)算R(τ)，只要用{bi}在一個(gè)周期中0的個(gè)數(shù)減去1的個(gè)數(shù)，再除以2n-1，即（證畢）m序列的特性88一個(gè)n-LFSR（給定結(jié)構(gòu)常數(shù)）具有“由一個(gè)短的種子產(chǎn)生一個(gè)長(zhǎng)的序列”的功能：以短的種子作為初態(tài)，產(chǎn)生的輸出序列可以任意長(zhǎng)！上述表明，任一n-LFSR都初步具有作為一個(gè)KG的資格；但從作為KG的效用來(lái)講，自然更希望所使用的n-LFSR進(jìn)一步是m-序列生成器。m序列的特性89線性反饋移位寄存器（LFSR）的綜合n-FSR的結(jié)構(gòu)常數(shù)+初態(tài)n-FSR序列分析綜合前面我們講過(guò)，m-序列是滿(mǎn)足Golomb三條隨機(jī)性公設(shè)的PN序列，但其不可以作為一個(gè)序列密碼的密鑰序列。因?yàn)椋簩?duì)m-序列，知道其少量的比特以后是可以預(yù)測(cè)的！現(xiàn)在就講怎么樣僅憑已知的少量比特來(lái)找出整個(gè)序列所滿(mǎn)足的線性遞推關(guān)系。一般地，把有關(guān)反饋移位寄存器的求解問(wèn)題，從正反兩個(gè)方面分為分析與綜合：90線性反饋移位寄存器（LFSR）的綜合線性反饋移位寄存器的綜合問(wèn)題就在于根據(jù)序列的少量比特求出整個(gè)序列所滿(mǎn)足的線性遞推關(guān)系。一個(gè)自然的想法就是：先假定線性遞推關(guān)系，然后由序列的各項(xiàng)應(yīng)該適合之而導(dǎo)出線性方程組；但這樣的方法有其不易行之處在于：不容易確定所適用的LFSR的級(jí)數(shù)n，從而就不能導(dǎo)致恰當(dāng)規(guī)模的線性方程組；當(dāng)上述的n很大時(shí)，求解相應(yīng)規(guī)模的線性方程組也很困難。91事實(shí)上，對(duì)于線性反饋移位寄存器的綜合問(wèn)題已經(jīng)出現(xiàn)了著名的解法：Berlekamp-Massey迭代算法，簡(jiǎn)稱(chēng)B-M算法。線性反饋移位寄存器（LFSR）的綜合92B-M算法描述Input：SN=a0a1a2aN-1Step1：置f0(x)=1，L0=0（初值）Step2：設(shè)<fi(x),Li>，i=0,1,2,…,n（0n<N）均已求出，且L0

L1

L2

Ln。設(shè),由此計(jì)算。Step3：當(dāng)dn=0時(shí)，取fn+1(x)=fn(x),Ln+1=Ln。

當(dāng)dn=1時(shí)，若Ln=0,則取fn+1(x)=xn+1+1,Ln+1=n+1；

否則,找出m(0

m<n)使Lm<Lm+1=Lm+2=

=Ln,取fn+1(x)=fn(x)+xn-mfm(x),Ln+1=max{Ln,n+1-Ln}。對(duì)于n=0,1,2,

，重復(fù)Step2與Step3，直至n=N-1Output：<fN(x),LN>93B-M算法舉例

輸入：S8=10101111輸出：<1+x3+x4,4>94有關(guān)B-M算法的結(jié)果定理1.

應(yīng)用B-M算法，若以N長(zhǎng)序列SN為輸入，得到輸出<fN(x),LN>，則⑴以fN(x)為聯(lián)接多項(xiàng)式的LN-LFSR是產(chǎn)生SN的最短LFSR，且當(dāng)時(shí)，迭代至第2LN步就得到最終輸出，即：。⑵當(dāng)時(shí)，產(chǎn)生SN的最短LFSR只是上述一個(gè)；當(dāng)時(shí)，產(chǎn)生SN的最短LFSR一共有個(gè)。由上述定理知，在前面的例子中，以f8(x)=1+x3+x4為聯(lián)接多項(xiàng)式的4-LFSR是唯一的產(chǎn)生S8=10101111的最短LFSR。95有關(guān)B-M算法的結(jié)果考慮問(wèn)題：

S6=101011f6(x)=1+x2+x3

如何解釋?zhuān)俊鋵?shí)，對(duì)

，由于L6=4，故4-LFSR[0,1,1,0]生成S6；對(duì)

，由于L1+N=1，故1-LFSR[0]生成S2（規(guī)定：f(x)=1產(chǎn)生全零序列）。96有關(guān)B-M算法的結(jié)果對(duì)于周期序列，也可應(yīng)用B-M算法求出產(chǎn)生它的最短LFSR的聯(lián)接多項(xiàng)式，不過(guò)須注意：一定得是針對(duì)兩個(gè)周期段去求才正確！定理2.

對(duì)周期為p的序列a=a0a1a2

，⑴應(yīng)用B-M算法于S2p=a0a1

ap-1a0a1

ap-1求出<f2p(x),L2p>時(shí)，必f2p(x)的次數(shù)必為L(zhǎng)2p，且以f2p(x)為聯(lián)接多項(xiàng)式的L2p-LFSR是唯一的產(chǎn)生a的最短LFSR。⑵。97應(yīng)用B-M算法舉例

求產(chǎn)生序列a的最低次多項(xiàng)式，這里⑴a=111001，⑵a=(111001)

解：可見(jiàn)答案為：⑴

1+x2+x3；⑵1+x2+x4。98應(yīng)用B-M算法舉例

注.

對(duì)于⑵中周期序列a，其實(shí)以前介紹過(guò)一種求生成它的最低次聯(lián)接多項(xiàng)式的方法：應(yīng)用展轉(zhuǎn)相除法可以求出最大公因式于是，從而可知生成序列a的最短LFSR的聯(lián)接多項(xiàng)式為1+x2+x4。995.M-序列的特性在一個(gè)一般n-FSR的狀態(tài)圖中，至少含有一個(gè)圈，且從任意狀態(tài)出發(fā)進(jìn)動(dòng)若干拍后必定進(jìn)入某一個(gè)圈！這時(shí)得到的輸出序列雖不必是周期序列，但去掉其前若干項(xiàng)后即得到周期序列，也就是說(shuō)這樣的序列為終歸周期序列。若一n-FSR的輸出序列的周期達(dá)到最大值2n，則稱(chēng)此序列為(n級(jí))M-序列。100顯然，如果一個(gè)n-FSR有一個(gè)輸出序列為M-序列，則其狀態(tài)圖是一個(gè)包含F(xiàn)2n中所有2n個(gè)點(diǎn)的大圈，從而這個(gè)n-FSR由任意初態(tài)產(chǎn)生的序列都是M-序列（一共有2n個(gè)且相互平移等價(jià)！），這個(gè)n-FSR本身也就被稱(chēng)為M-序列生成器，而相應(yīng)的反饋函數(shù)被稱(chēng)為M-序列反饋函數(shù)。例.反饋函數(shù)為的3-FSR。M-序列的概念101一個(gè)關(guān)于與M-序列反饋函數(shù)的結(jié)果有關(guān)布爾函數(shù)的一些知識(shí)：一個(gè)n元布爾函數(shù)是指下述形式的映射它既可以用邏輯關(guān)系式表達(dá)，也可以用真值表來(lái)表示，還可以表為多元多項(xiàng)式。上述三者之間的互化方法：邏輯關(guān)系式多元多項(xiàng)式真值表（容易）102另外，xt=x(t>1)。因此，在布爾函數(shù)f(x1,x2,…,xn)的多項(xiàng)式表示中，高次項(xiàng)的形式只有是。重量：w(f)是指在布爾函數(shù)f的真值表中，函數(shù)值列里1的個(gè)數(shù)。邏輯關(guān)系式多元多項(xiàng)式：真值表多元多項(xiàng)式（舉例）一個(gè)關(guān)于與M-序列反饋函數(shù)的結(jié)果103布爾函數(shù)f(x1,x2,…,xn)是n級(jí)M-序列反饋函數(shù)的必要條件是:⑴f(x1,x2,…,xn)是非奇異的，即

f(x1,x2,…,xn)=x1+f0(x2,x3,…,xn)⑵⑴中n-1元布爾函數(shù)f0(x2,x3,…,xn)一個(gè)關(guān)于與M-序列反饋函數(shù)的結(jié)果104還必須滿(mǎn)足：

f0的重量w(f0)是奇數(shù)；

在f0的任一表達(dá)中，x2,x3,…,xn都出現(xiàn)；

在f0的多項(xiàng)式表示中，項(xiàng)數(shù)為奇數(shù)、常數(shù)項(xiàng)1必出現(xiàn)、線性項(xiàng)x2,x3,…,xn不能全出現(xiàn)、且n-1次項(xiàng)x2x3

xn一定出現(xiàn)。一個(gè)關(guān)于與M-序列反饋函數(shù)的結(jié)果105n級(jí)M-序列反饋函數(shù)的個(gè)為。M-序列的統(tǒng)計(jì)特性.在n級(jí)M-序列的一個(gè)周期圈中，⑴0與1的數(shù)目均為2n-1；

⑵長(zhǎng)為k的0-游程與1-游程的數(shù)目均為M-序列的特性106線性復(fù)雜度概念定義.能夠產(chǎn)生（有限長(zhǎng)或周期）序列a的最短LFSR的級(jí)數(shù)稱(chēng)為a的線性復(fù)雜度，記為

(a)；約定：

(0)=0。若對(duì)序列a應(yīng)用B-M算法產(chǎn)生的輸出為<f(x),L>，則

(a)=L。研討：若a為n-級(jí)m-序列，則

(a)=

。107M-序列的自相關(guān)特性.設(shè)n級(jí)M-序列a的反饋函數(shù)f(x1,x2,…,xn)=x1+f0(x2,x3,…,xn)那么，⑴Ca(0)=1⑵Ca(

t)=0，0<tn-1⑶Ca(

n)=1-w(f0)/2n-2≠0對(duì)于n(n≥3)級(jí)M-序列a，M-序列的特性108上面說(shuō)過(guò)，有限域上的二元加法序列密碼是目前最為常用的序列密碼體制，設(shè)滾動(dòng)密鑰生成器是線性反饋移位寄存器，產(chǎn)生的密鑰是序列。又設(shè)和是序列中兩個(gè)連續(xù)的長(zhǎng)向量，其中6.m序列密碼的破譯109設(shè)序列{ai}滿(mǎn)足線性遞推關(guān)系：可表示為m序列密碼的破譯110或Sh+1=M·Sh，其中又設(shè)敵手知道一段長(zhǎng)為2n的明密文對(duì)，即已知m序列密碼的破譯111于是可求出一段長(zhǎng)為2n的密鑰序列其中,由此可推出線性反饋移位寄存器連續(xù)的n+1個(gè)狀態(tài)：m序列密碼的破譯112做矩陣而若X可逆，則m序列密碼的破譯113下面證明X的確是可逆的。因?yàn)閄是由S1,S2,…,Sn作為列向量，要證X可逆，只要證明這n個(gè)向量線性無(wú)關(guān)。由序列遞推關(guān)系：可推出向量的遞推關(guān)系：m序列密碼的破譯114設(shè)m(m≤n+1)是使S1,S2,…,Sm線性相關(guān)的最小整數(shù)，即存在不全為0的系數(shù)l1,l2,…,lm，其中不妨設(shè)l1=1，使得即對(duì)于任一整數(shù)i有m序列密碼的破譯115由此又推出密鑰流的遞推關(guān)系：即密鑰流的級(jí)數(shù)小于m。若m≤n，則得出密鑰流的級(jí)數(shù)小于n，矛盾。所以m=n+1，從而矩陣X必是可逆的。m序列密碼的破譯116例：設(shè)敵手得到密文串101101011110010和相應(yīng)的明文串011001111111001，因此可計(jì)算出相應(yīng)的密鑰流為110100100001011。進(jìn)一步假定敵手還知道密鑰流是使用5級(jí)線性反饋移位寄存器產(chǎn)生的，那么敵手可分別用密文串中的前10個(gè)比特和明文串中的前10個(gè)比特建立如下方程m序列密碼的破譯117即而m序列密碼的破譯118從而得到所以密鑰流的遞推關(guān)系為m序列密碼的破譯119已介紹密鑰流生成器可分解為驅(qū)動(dòng)子系統(tǒng)和非線性組合子系統(tǒng)，如圖所示。7.非線性序列驅(qū)動(dòng)子系統(tǒng)非線性組合子系統(tǒng)120驅(qū)動(dòng)子系統(tǒng)常用一個(gè)或多個(gè)線性反饋移位寄存器來(lái)實(shí)現(xiàn)，非線性組合子系統(tǒng)用非線性組合函數(shù)F來(lái)實(shí)現(xiàn)，如圖所示。本節(jié)介紹第2部分非線性組合子系統(tǒng)。7.非線性序列LFSRFLFSR1LFSRnF常見(jiàn)的兩種密鑰流產(chǎn)生器121為了使密鑰流生成器輸出的二元序列盡可能復(fù)雜，應(yīng)保證其周期盡可能大、線性復(fù)雜度和不可預(yù)測(cè)性盡可能高，因此常使用多個(gè)LFSR來(lái)構(gòu)造二元序列，稱(chēng)每個(gè)LFSR的輸出序列為驅(qū)動(dòng)序列，顯然密鑰流生成器輸出序列的周期不大于各驅(qū)動(dòng)序列周期的乘積，因此，提高輸出序列的線性復(fù)雜度應(yīng)從極大化其周期開(kāi)始。非線性序列122二元序列的線性復(fù)雜度指生成該序列的最短LFSR的級(jí)數(shù)，最短LFSR的特征多項(xiàng)式稱(chēng)為二元序列的極小特征多項(xiàng)式。下面介紹4種由多個(gè)LFSR驅(qū)動(dòng)的非線性序列生成器。非線性序列123

Geffe序列生成器由3個(gè)LFSR組成，其中LFSR2作為控制生成器使用，如圖所示。7.1Geffe序列生成器Geffe序列生成器圖LFSR1LFSR2LFSR3輸出124當(dāng)LFSR2輸出1時(shí)，LFSR2與LFSR1相連接；當(dāng)LFSR2輸出0時(shí)，LFSR2與LFSR3相連接。若設(shè)LFSRi的輸出序列為{a(i)k}(i=1,2,3)，則輸出序列{bk}可以表示為Geffe序列生成器125多路復(fù)合器表示的Geffe序列生成器LFSR1LFSR1LFSR1多路復(fù)合器選擇控制126

Geffe序列生成器也可以表示為上圖的形式，其中LFSR1和LFSR3作為多路復(fù)合器的輸入，LFSR2控制多路復(fù)合器的輸出。設(shè)LFSRi的特征多項(xiàng)式分別為ni次本原多項(xiàng)式，且ni兩兩互素，則Geffe序列的周期為線性復(fù)雜度為Geffe序列生成器127

Geffe序列的周期實(shí)現(xiàn)了極大化，且0與1之間的分布大體上是平衡的。Geffe序列生成器128

J-K觸發(fā)器如下圖所示，它的兩個(gè)輸入端分別用J和K表示，其輸出ck不僅依賴(lài)于輸入，還依賴(lài)于前一個(gè)輸出位ck-1，即其中x1和x2分別是J和K端的輸入。由此可得J-K觸發(fā)器的真值表，如表。7.2J-K觸發(fā)器129J-K觸發(fā)器RJKJ-K觸發(fā)器真值表JK0001010111130利用J-K觸發(fā)器的非線性序列生成器見(jiàn)圖。利用J-K觸發(fā)器組成非線性序列生產(chǎn)器LFSR1LFSR2JK131令驅(qū)動(dòng)序列{ak}和{bk}分別為m級(jí)和n級(jí)m序列，則有如果令c-1=0，則輸出序列的最初3項(xiàng)為當(dāng)m與n互素且a0+b0=1時(shí)，序列{ck}的周期為(2m-1)(2n-1)。利用J-K觸發(fā)器組成非線性序列生產(chǎn)器132例：令m=2,n=3，兩個(gè)驅(qū)動(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。133由表達(dá)式ck=(ak+bk+1)ck-1+ak可得因此，如果知道{ck}中相鄰位的值ck-1和ck，就可以推斷出ak和bk中的一個(gè)。而一旦知道足夠多的這類(lèi)信息，就可通過(guò)密碼分析的方法得到序列{ak}和{bk}。為了克服上述缺點(diǎn)，Pless提出了由多個(gè)J-K觸發(fā)器序列驅(qū)動(dòng)的多路復(fù)合序列方案，稱(chēng)為Pless生成器。134

Pless生成器由8個(gè)LFSR、4個(gè)J-K觸發(fā)器和1個(gè)循環(huán)計(jì)數(shù)器構(gòu)成，由循環(huán)計(jì)數(shù)器進(jìn)行選通控制，如下圖所示。假定在時(shí)刻t輸出第t(mod4)個(gè)單元，則輸出序列為a0b1c2d3a4b5d67.3Pless生成器135Pless生成器LFSR1LFSR2JKLFSR7LFSR8JKLFSR3LFSR4JKLFSR5LFSR6JK3210136鐘控序列最基本的模型是用一個(gè)LFSR控制另外一個(gè)LFSR的移位時(shí)鐘脈沖，如圖所示。7.4鐘控序列生成器最簡(jiǎn)單的鐘控序列生成器LFSR1LFSR2時(shí)鐘脈沖137假設(shè)LFSR1和LFSR2分別輸出序列{ak}和{bk}，其周期分別為p1和p2。當(dāng)LFSR1輸出1時(shí)，移位時(shí)鐘脈沖通過(guò)與門(mén)使LFSR2進(jìn)行一次移位，從而生成下一位。當(dāng)LFSR1輸出0時(shí)，移位時(shí)鐘脈沖無(wú)法通過(guò)與門(mén)影響LFSR2。因此LFSR2重復(fù)輸出前一位。假設(shè)鐘控序列{ck}的周期為p，可得如下關(guān)系：其中。鐘控序列生成器138又設(shè){ak}和{bk}的極小特征多項(xiàng)式分別為GF(2)上的m和n次本原多項(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)出{ck}的線性復(fù)雜度為n(2m-1)，極小特征多項(xiàng)式為。鐘控序列生成器139例：設(shè)LFSR1為3級(jí)m序列生成器，其特征多項(xiàng)式為f1(x)=1+x+x3。設(shè)初態(tài)為a0=a1=a2=1，于是輸出序列為{ak}=1,1,1,0,1,0,0,…。又設(shè)LFSR2為3級(jí)m序列生成器，且記其狀態(tài)向量為σk，則在上圖的構(gòu)造下σk的變化情況如下：鐘控序列生成器140

{ck}的周期為(23-1)2=49，在它的一個(gè)周期內(nèi)，每個(gè)σk恰好出現(xiàn)7次。設(shè)f2(x)=1+x2+x3為L(zhǎng)FSR2的特征多項(xiàng)式，且初態(tài)為b0=b1=b2=1，則{bk}=1,1,1,0,0,1,0，…。由σk的變化情況得

{ck}=1,1,1,0,0,0,0,0,1,0,1,1,1,1,1,1,0,0,0,1,1,1,0,1,1,1,1,1,1,0,0,1,1,0,0,0,1,1,1,1,0,0,0,0,1,0,0,1,1,…鐘控序列生成器141

{ck}的極小特征多項(xiàng)式為1+x14x21，其線性復(fù)雜度為3·（23-1）=21，圖是其線性等價(jià)生成器。一個(gè)鐘控序列的線性等價(jià)生成器鐘控序列生成器142實(shí)際應(yīng)用中，可以用上述最基本的鐘控序列生成器構(gòu)造復(fù)雜的模型，具體構(gòu)造方式可參閱有關(guān)文獻(xiàn)。鐘控序列生成器143設(shè)計(jì)一個(gè)性能良好的序列密碼是一項(xiàng)十分困難的任務(wù)。最基本的設(shè)計(jì)原則是“密鑰流生成器的不可預(yù)測(cè)性”，它可分解為下述基本原則：①長(zhǎng)周期。②高線性復(fù)雜度。③統(tǒng)計(jì)性能良好。④足夠的“混亂”。⑤足夠的“擴(kuò)散”。⑥抵抗不同形式的攻擊。序列密碼的設(shè)計(jì)原則144歐洲NESSIE工程介紹自2000年1月至2002年12月，歐洲委員會(huì)投資33億歐元支持其信息社會(huì)技術(shù)（IST）規(guī)劃中一項(xiàng)名為NESSIE(NewEu-ropeanSchemesforSignatures,Inte-grity,andEncryption)的工程。該工程也象DES、RIPE規(guī)劃和AES的選擇過(guò)程一樣，采用先征集后評(píng)估的辦法，但其征集范圍要比NIST的AES廣泛得多。8.歐洲NESSIE工程及其征集的Lili-128候選算法145信息社會(huì)不僅需要分組密碼標(biāo)準(zhǔn)來(lái)提供機(jī)密性服務(wù)，而且也需要其它密碼標(biāo)準(zhǔn)來(lái)提供認(rèn)證和完整性等服務(wù)。因此，NESSIE的征集范圍涉及到多個(gè)密碼學(xué)領(lǐng)域，諸如：分組（塊）密碼；序列（流）密碼；消息認(rèn)證碼；偽隨機(jī)函數(shù)族；數(shù)字簽名和Hash函數(shù)；非對(duì)稱(chēng)加密方案；非對(duì)稱(chēng)識(shí)別方案。歐洲NESSIE工程介紹146

此外，NESSIE工程將考慮候選密碼標(biāo)準(zhǔn)所能應(yīng)用的具體環(huán)境，甚至也征集評(píng)測(cè)這些侯選密碼標(biāo)準(zhǔn)的測(cè)試方法(如統(tǒng)計(jì)測(cè)試)。NESSIE工程的主要目標(biāo)就是通過(guò)公開(kāi)征集進(jìn)行公開(kāi)的、透明的測(cè)試評(píng)價(jià)，提出一套強(qiáng)的密碼標(biāo)準(zhǔn)，這些標(biāo)準(zhǔn)包括分組密碼，序列密碼，雜湊函數(shù)，消息認(rèn)證碼，數(shù)字簽名方案和公鑰加密方案。該工程將發(fā)展一種密碼體制的評(píng)估方法（包括安全性和性能評(píng)價(jià)）和支持評(píng)估的一個(gè)軟件工具箱。歐洲NESSIE工程介紹14721世紀(jì)歐洲密碼標(biāo)準(zhǔn)產(chǎn)生：1993年2月27日，以征集對(duì)世紀(jì)歐洲新的密碼算法標(biāo)準(zhǔn)為內(nèi)容的NESSIE工程，終于宣布了最后的終選結(jié)果。除了從參評(píng)的42個(gè)算法方案中評(píng)出了12個(gè)方案外，還選取了已有標(biāo)準(zhǔn)中的5個(gè)方案（見(jiàn)打“＊”的）。NESSIE工程委員會(huì)公布的終選結(jié)果如下頁(yè)。在整個(gè)評(píng)測(cè)過(guò)程中，上述方案均未發(fā)現(xiàn)任何缺陷。上述算法中的10個(gè)對(duì)稱(chēng)算法允許免費(fèi)使用。非對(duì)稱(chēng)方案RSA—KEM、RSA—PSS和SFLASH也可以在公開(kāi)領(lǐng)域內(nèi)使用。需要特別加以說(shuō)明的是由于安全性審查有些過(guò)于嚴(yán)密，所有6個(gè)參選的同步序列密碼算法方案無(wú)一進(jìn)入終選。歐洲NESSIE工程介紹148

歐洲NESSIE工程介紹149有關(guān)NESSIE工程的其它事項(xiàng)可通過(guò)NESSIE的主頁(yè)http://去追索。歐洲NESSIE工程介紹150以下介紹一下的是關(guān)于序列密碼的情況。NESSIE收到的5個(gè)候選同步序列密碼如下表：歐洲NESSIE工程介紹算法名稱(chēng)國(guó)家（組織）整體結(jié)構(gòu)設(shè)計(jì)特點(diǎn)Leviathan美國(guó)是一種二進(jìn)制樹(shù)結(jié)構(gòu)密鑰流由一組二進(jìn)制的數(shù)結(jié)構(gòu)定義Lili-128澳大利亞鐘控結(jié)構(gòu)由鐘控子系統(tǒng)與數(shù)據(jù)生成子系統(tǒng)組成，使用了兩個(gè)LFSR與兩個(gè)函數(shù)BMGL瑞典密鑰反饋模式(類(lèi)似于OFB)基于復(fù)雜性理論，具有可證明安全性，核心是Rijdael分組密碼SOBER-t32/t16澳大利亞非線性濾波結(jié)構(gòu)使用帶有密鑰的非線性濾波函數(shù)，輸出32/16比特分組SNOW瑞典由一個(gè)LFSR和一個(gè)有限狀態(tài)機(jī)(FSM)組成是一個(gè)面向32-比特字的序列密碼，基于經(jīng)典的求和發(fā)生器的觀點(diǎn)151限于同學(xué)們的知識(shí)和數(shù)學(xué)能力，在此僅簡(jiǎn)要介紹一下Lili-128算法。Lili-128是一種簡(jiǎn)單而快速的密鑰流生成器，它使用兩個(gè)LFSR和兩個(gè)非線性函數(shù)來(lái)產(chǎn)生偽隨機(jī)的二元密鑰流序列?；谒瓿傻墓δ?，Lili-128密鑰流生成器的部件可分成兩個(gè)子系統(tǒng)：鐘控子系統(tǒng)和數(shù)據(jù)生成子系統(tǒng)。如下頁(yè)圖所示：候選序列密碼—Lili-128算法152LFSRcfck=2···LFSRdfdn=10···c(t)z(t)鐘控子系統(tǒng)數(shù)據(jù)生成子系統(tǒng)鐘控候選序列密碼—Lili-128算法153鐘控子系統(tǒng)LFSRc的聯(lián)接多項(xiàng)式為本原多項(xiàng)式1+x2+x14+x15+x17+x31+x33+x35+x39。在時(shí)刻t，LFSRc當(dāng)前狀態(tài)的第12、20兩個(gè)位置（起始位置是0）的分量x12與x20作為函數(shù)fc的輸入，得到的輸出為c(t)=fc(x12,x20)=2x12+x20+1。顯然，c(t)的范圍在{1,2,3,4}。候選序列密碼—Lili-128算法154數(shù)據(jù)生成子系統(tǒng)LFSRd的聯(lián)接多項(xiàng)式為本原多項(xiàng)式1+x+x39+x42+x53+x55+x80+x83+x89。在時(shí)刻t，LFSRd當(dāng)前狀態(tài)的下列位置分量被抽頭：{0,1,3,7,12,20,30,44,65,80}且輸入給函數(shù)fd以得到z(t)，然后連續(xù)進(jìn)動(dòng)c(t)拍。fd選為高度非線性的、且是作為上述10個(gè)位置輸入的3階相關(guān)免疫的平衡布爾函數(shù)（真值表如下頁(yè)）。候選序列密碼—Lili-128算法1550,0,1,1,1