本科生必修課《現(xiàn)代密碼學》第二章流密碼主講教師：董慶寬副教授研究方向：密碼學與信息安全電子郵件：個人主頁：

內(nèi)容提要1.流密碼的基本概念2.線性反饋移位寄存器3.非線性序列4.流密碼算法第二章流密碼22.1流密碼的基本概念流密碼(streamcipher)，也稱為序列密碼(SequenceCipher)，是一種重要的密碼體制明文消息按字符或比特逐位加密流密碼的基本思想利用密鑰k產(chǎn)生一個密鑰流z=z0z1z2…，并使用如下規(guī)則對明文串x=x0x1x2…加密：

y=y0y1y2…＝Ez0(x0)Ez1(x1)Ez2(x2)…流密碼與分組密碼的區(qū)別：在于有無記憶性流密碼的密鑰流是由已知記憶狀態(tài)導出當前狀態(tài)與記憶元件初始狀態(tài)、密鑰k、輸入的明文和狀態(tài)轉換函數(shù)導出分組密碼對明文一組一組的加密，組間一般沒有關系第二章流密碼流密碼示意圖分組密碼示意圖32.1.1同步流密碼流密碼的滾動密鑰流由密鑰流發(fā)生器f產(chǎn)生：zi＝f(k,σi)內(nèi)部記憶元件由一組移位寄存器構成，這里假設有n個移位寄存器σi是加密器中的記憶元件在時刻i的狀態(tài)，可表示為σi=(an,an-1,…,a1)

f是由k,σi產(chǎn)生的函數(shù)流密碼的滾動密鑰由函數(shù)f、密鑰k和指定的初態(tài)σ0完全確定此后由于輸入加密器的明文可能影響加密器中的內(nèi)部記憶元件的存儲狀態(tài)，因而σi(i>0)可能依賴于k，σ0，x0，x1，…，xi－1，即前i個明文和密鑰及初態(tài)第二章流密碼：2.1流密碼的基本概念FeedbackShiftRegister,FSR52.1.1同步流密碼流密碼可按記憶元件存儲狀態(tài)分類按照加密器中記憶元件的存儲狀態(tài)σi是否依賴于輸入的明文字符流，流密碼可進一步分成同步和自同步流密碼兩種σi獨立于明文字符流的叫做同步流密碼，否則叫做自同步流密碼由于自同步流密碼的密鑰流產(chǎn)生與明文有關，所以理論上難于分析。好的密碼算法應該在理論上或基于實踐檢驗能夠證明其是安全的或至少是沒有明顯漏洞的。如果算法難于分析，則無法保證其安全性，也就無法放心使用，因此自同步流密碼研究很少，很少采用。第二章流密碼：2.1流密碼的基本概念62.1.1同步流密碼目前大多數(shù)研究成果都是關于同步流密碼的由于zi＝f(k,σi)與明文無關，此刻的密文字符yi=Ezi(xi)也不依賴于此前的明文字符，這樣可將同步流密碼的加密器分成密鑰流產(chǎn)生器和加密變換器兩個部分。設解密變換為xi=Dzi(yi)。同步流密碼體制模型如下圖第二章流密碼：2.1流密碼的基本概念72.1.1同步流密碼加密變換Ezi可有多種選擇，保證變換可逆性即可比如明文流和密鑰流對應位異或實際數(shù)字保密通信系統(tǒng)一般都是二元的{0,1},在有限域GF(2)上討論二元加法流密碼是目前最常用的流密碼體制加密變換可表示為yi＝zixi，加法流密碼體制模型同步流密碼算法的設計主要是密鑰流產(chǎn)生器的設計密鑰產(chǎn)生器目標是：使密鑰k經(jīng)其擴展成的密鑰流序列z具有：極大的周期，良好的統(tǒng)計特性，抗差分分析，抗線性分析等性質第二章流密碼：2.1流密碼的基本概念82.1.2有限狀態(tài)自動機【例2－1】S={s1,s2,s3}，A1={A1(1),A2(1),A3(1)}，A2={A1(2),A2(2),A3(2)}，轉移函數(shù)由表2－1給出。f1為輸出轉移函數(shù)，f2為狀態(tài)轉移函數(shù)第二章流密碼：2.1流密碼的基本概念f1A1(1)A2(1)A3(1)s1A1(2)A3(2)A2(2)s2A2(2)A1(2)A3(2)s3A3(2)A2(2)A1(2)f2A1(1)A2(1)A3(1)s1s2s1s3s2s3s2s1s3s1s3s2102.1.3密鑰流產(chǎn)生器同步流密碼的關鍵是密鑰流產(chǎn)生器(KeyGenerator)一般可將其看成一個參數(shù)為k的有限狀態(tài)自動機，由一個輸出符號集Z、一個狀態(tài)集∑、兩個函數(shù)φ和ψ以及一個初始狀態(tài)σ0組成狀態(tài)轉移函數(shù)φ：σi→σi+1，將當前狀態(tài)σi變?yōu)橐粋€新狀態(tài)σi+1輸出函數(shù)ψ:σi→zi，當前狀態(tài)σi變?yōu)檩敵龇柤械囊粋€元素zi。密鑰流生成器設計的關鍵在于找出適當?shù)臓顟B(tài)轉移函數(shù)φ和輸出函數(shù)ψ，使得輸出序列z滿足密鑰流序列z應滿足的幾個條件，并且要求在設備上是節(jié)省的和容易實現(xiàn)的。為了實現(xiàn)這一目標，必須采用非線性函數(shù)

第二章流密碼：2.1流密碼的基本概念122.2.1布爾函數(shù)簡介n元布爾函數(shù)f(x1,…,xn)定義為f：F2nF2表示方法有三種：邏輯關系式，真值表，多元多項式多元多項式：如f(x1,x2,x3,x4)＝x1x2＋x3＋x4異或x1x2x1＋x2(在GF(2)上的“＋”(模2加)邏輯“與”x1x2

x1x2(GF(2)上的“乘法”)邏輯“或”x1x2x1x2+x1＋x2其真值表為：非1＋x

冪xt＝x·x…x=x

t>0x0=1;布爾函數(shù)的高次項只有如下形式xi1xi2…xik第二章流密碼：2.2線性反饋移位寄存器x1x2x1x2000011101111142.2.1布爾函數(shù)簡介布爾函數(shù)的重量W(f)：真值表中函數(shù)值列里”1”的個數(shù)f(x1,x2)＝x1x2=x1x2+x1＋x2的重量W(f)＝3布爾函數(shù)的次數(shù)f(x1,…,xn)＝a0＋一個乘積項的次數(shù)定義為r最大次數(shù)定義為布爾函數(shù)的次數(shù)def(f)，也稱為代數(shù)次數(shù)def(f)＝1時，稱為仿射函數(shù)：f(x1,…,xn)＝a0＋若仿射函數(shù)的常數(shù)項a0＝0，則稱為線性函數(shù)def(f)>1時，稱為非線性函數(shù)第二章流密碼：2.2線性反饋移位寄存器152.2.2線性反饋移位寄存器的結構與表示移位寄存器(FSR)是序列密碼產(chǎn)生密鑰流的主要組成部分GF(2)上一個n級反饋移位寄存器由n個二元存儲器與一個反饋函數(shù)f(a1,a2,…,an)組成，如圖所示移位寄存器的狀態(tài)每一存儲器稱為移位寄存器的一級，具有0和1兩個狀態(tài)在任一時刻，這些級的內(nèi)容構成該反饋移位寄存器的狀態(tài)，可用GF(2)上的一個n維向量(a1,a2,…,an)表示，其中ai是第i級存儲器的內(nèi)容。共有2n種可能的狀態(tài)。初始狀態(tài)σ0由用戶確定，屬于密鑰k的一部分第二章流密碼：2.2線性反饋移位寄存器162.2.2線性反饋移位寄存器的結構與表示狀態(tài)轉換規(guī)則根據(jù)FSR的工作原理，當?shù)趇個移位時鐘脈沖到來時a1被移出，作為輸出序列在第i時刻的輸出bit其它每一級存儲器ai都將其內(nèi)容向下一級ai-1傳遞同時，根據(jù)時鐘脈沖到來前寄存器的狀態(tài)a1,a2,…,an計算出的an=f(a1,a2,…,an)也移入最左邊的寄存器反饋函數(shù)f(a1,a2,…,an)是n元布爾函數(shù)函數(shù)中的運算有邏輯與、邏輯或、邏輯補、或其它運算最后的函數(shù)值為0或1?？赡苁蔷€性或非線性布爾函數(shù)第二章流密碼：2.2線性反饋移位寄存器172.2.2線性反饋移位寄存器的結構與表示例：下圖是一個3級反饋移位寄存器，其初始狀態(tài)為(a1,a2,a3)=(1,0,1)，輸出可由表2.2求出第二章流密碼：2.2線性反饋移位寄存器該3級反饋移位寄存器的狀態(tài)和輸出如下狀態(tài)（a3,a2,a1)輸出101110111011101110101110即輸出序列為1…，周期為4在一個一般n-FSR的狀態(tài)圖中，至少含有一個圈，且從任意狀態(tài)出發(fā)進動若干拍后必定進入某一個圈！這時得到的輸出序列雖不必是周期序列，但去掉其前若干項后即得到周期序列，也就是說這樣的序列為終歸周期序列182.2.2線性反饋移位寄存器的結構與表示[例2-3]下圖是一個5級線性反饋移位寄存器，其初始狀態(tài)為（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出輸出序列為1110…周期為31。線性反饋移位寄存器因其實現(xiàn)簡單、速度快、有較為成熟的理論等優(yōu)點而成為構造密鑰流生成器的最重要的部件之一第二章流密碼：2.2線性反饋移位寄存器202.2.2線性反饋移位寄存器的結構與表示LFSR的相關性質(1)反饋系數(shù)所有系統(tǒng)都為0，即c1=c2=…=cn=0，由于沒有反饋，n個時鐘脈沖后，狀態(tài)變?yōu)槿?，并一直下去若c1,c2,…,cn中只有一個系數(shù)不為0，設僅有cj不為0，實際上是一種延遲裝置。若從cj開始cj,cj+1,…,cn都等于0，則是一種退化的LFSR，cj,cj+1,…,cn對應的移位寄存器相當于延遲裝置，因此，我們討論的LFSR總是假定cn=1按照遞推式，LFSR輸出序列的性質由其反饋函數(shù)和

初始狀態(tài)決定，而其生成序列周期的性質主要由反饋函數(shù)決定第二章流密碼：2.2線性反饋移位寄存器212.2.2線性反饋移位寄存器的結構與表示LFSR的一元多項式表示設n級線性移位寄存器的輸出序列{ai}滿足遞推關系式an+k=c1an＋k－1c2an＋k－2…cnak

(*)對任何k1成立。這種遞推關系可用一個一元高次多項式表示

p(x)=1+c1x+c2x2+…+cn-1xn-1+cnxn稱這個多項式為LFSR的特征多項式。特征多項式按如下方式獲得：在(*)式中兩邊同時加上an+k有

0＝1an+kc1an＋k－1c2an＋k－2…cnak

第二章流密碼：2.2線性反饋移位寄存器232.2.2線性反饋移位寄存器的結構與表示每一個時鐘信號，寄存器中的內(nèi)容從左向右移動一次，因此一個寄存器代表一次符號遲延，因而引入遲延算子DD(an＋k)＝an＋k－1表示遲延一位(一拍)D2(an＋k)＝an＋k－2表示遲延兩位，即D2(an＋k)＝D(D(an＋k))＝D(an＋k－1)=an＋k－2同理有Dn(an＋k)＝ak表示遲延n位。并引入恒等算子I=D0，I(an＋k)=an＋k于是遞推式0＝1an+kc1an＋k－1c2an＋k－2…cnak可表示成

0＝I(an＋k)+c1D(an＋k)+c2D2(an＋k)+…+cnDn(an＋k)即0＝(I+c1D+c2D2+…+cnDn)an＋k以x表示D，則有p(x)an＋k=0于是可知p(x)可以描述LFSR的全部特征，可以由p(x)來研究LFSR第二章流密碼：2.2線性反饋移位寄存器242.2.3m序列產(chǎn)生器反饋函數(shù)，也即特征多項式?jīng)Q定了LFSR輸出序列的性質，本節(jié)將探討特征多項式滿足什么條件時LFSR能夠產(chǎn)生具有最大周期的m序列，以及這種序列的安全性(即破譯問題）為此，首先引入生成函數(shù)的概念，它是一種形式冪級數(shù)，其中的xi可以理解為延遲算子定義2-1給定序列{ai},冪級數(shù)稱為該序列的生成函數(shù)定理2-1設p(x)=1+c1x+c2x2+…+cn-1xn-1+cnxn是GF(2)上的多項式，G(p(x))中任一序列{ai}的生成函數(shù)A(x)滿足：，其中第二章流密碼：2.2線性反饋移位寄存器262.2.3m序列產(chǎn)生器證明：由遞推式不難得出an+1=c1anc2an-1…cna1an+2=c1an+1c2an…cna2…兩邊分別乘以xn,xn+1,…，再求和左邊＝an+1xn+an+2xn+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)第二章流密碼：2.2線性反饋移位寄存器移項整理得(1+c1x+c2x2+…+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)==(x)272.2.3m序列產(chǎn)生器※(x)的次數(shù)最大可能是n-1因此(x)表達式共有n個系數(shù)，從而有2n－1個不同的非0表達式，并且由初始狀態(tài)a1,a2,…,an完全確定這樣每一個初態(tài)對應一條不同的序列，而每一條序列的生成函數(shù)A(x)唯一確定一個(x)，共有2n－1個初態(tài)所以初始狀態(tài)、(x)、G(p(x))中的序列{ai}三者之間一一對應第二章流密碼：2.2線性反饋移位寄存器282.2.3m序列產(chǎn)生器反之，若G(p(x))G(q(x))，則對于次數(shù)小于n的多項式(x)，存在序列{ai}G(p(x))，以為生成函數(shù)。由于(x)和G(p(x))中的序列是一一對應的，當(x)＝1時，當然也存在序列{ai}G(p(x))以為生成函數(shù)由于G(p(x))G(q(x))，序列{ai}G(q(x))，所以存在函數(shù)r(x)，使得{ai}的生成函數(shù)也等于，從而，即q(x)＝p(x)r(x)，所以p(x)|q(x)證畢第二章流密碼：2.2線性反饋移位寄存器302.2.3m序列產(chǎn)生器定理2-2說明可用n級LFSR產(chǎn)生的序列，也可用級數(shù)更多的LFSR來產(chǎn)生反之一個LFSR序列的特征多項式可能有多個，需要的移位寄存器個數(shù)也不同定義：二元序列的線性復雜度是指生成該序列的最短LFSR的級數(shù)，最短LFSR的特征多項式稱為二元序列的極小特征多項式，顯然它的次數(shù)就是序列的線性復雜度定義2-2設p(x)是GF(2)上的多項式，使p(x)|(xp-1)的最小p稱為p(x)的周期或階第二章流密碼：2.2線性反饋移位寄存器312.2.3m序列產(chǎn)生器定理2-3若序列{ai}的特征多項式p(x)定義在GF(2)上，p是p(x)的周期，則{ai}的周期r|p。證明：(首先證明{ai}至少是以p為周期重復的，再證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)＝q(x)(x)所以(xp-1)A(x)=q(x)(x)。由于q(x)的次數(shù)為p-n，(x)的次數(shù)不超過n-1，所以(xp-1)A(x)的次數(shù)不超過(p-n)+(n-1)=p-1。對于任意的特征多項式為p(x)的A(x)，xpA(x)-A(x)的次數(shù)低于p－1，也就是A(x)移位p次后對應位相等，從而相消去)這就證明了對于任意正整數(shù)i都有ai+p=ai設p=kr+t,0t<r，則ai+p=ai+kr+t=ai+t=ai，所以t=0，即r|p。（證畢）第二章流密碼：2.2線性反饋移位寄存器322.2.3m序列產(chǎn)生器定理2-3說明n級LFSR輸出序列的周期r不依賴于初始條件，而依賴于特征多項式p(x)。如果p(x)的周期有多種不同因子，那么，其產(chǎn)生序列的周期也有多種可能，則LFSR的狀態(tài)轉移圖由多個互不相交的圈組成，每一個圈包含與周期相同的狀態(tài)數(shù)，這時所有圈包含狀態(tài)的總和為2n-1，不含全0狀態(tài)顯然，初始狀態(tài)對序列的周期有一定的影響，它屬于哪一個圈，則對應產(chǎn)生序列的周期就是哪一個圈所包含的狀態(tài)數(shù)。我們感興趣的是LFSR遍歷2n-1個非零狀態(tài)，這時序列的周期達到最大2n-1，狀態(tài)轉移圖為一個大圈，這種序列就是m序列。這時不同初始狀態(tài)生成的都是m序列，而且有狀態(tài)轉移圖特點不能看出，所有這些m序列之間是相互移位的關系，本質上是同一個序列即LFSR只要產(chǎn)生一條m序列，則產(chǎn)生的所有非0序列都是m序列下面討論特征多項式滿足什么條件時，LFSR的輸出序列為m序列。定義2-3僅能被非0常數(shù)或自身的常數(shù)倍除盡，但不能被其它的多項式除盡的多項式稱為既約多項式或不可約多項式第二章流密碼：2.2線性反饋移位寄存器332.2.3m序列產(chǎn)生器定理2-4設p(x)是n次不可約多項式，周期為m，序列{ai}G(p(x))，則{ai}的周期為m。證明：設{ai}的周期為r，由定理2.3有r|m，所以rm。設A(x)為{ai}的生成函數(shù)，A(x)=(x)/p(x)，即p(x)A(x)=(x)≠0，(x)的次數(shù)不超過n-1。而A(x)==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.2線性反饋移位寄存器342.2.3m序列產(chǎn)生器p(x)是n次不可約多項式時的狀態(tài)轉移圖：以r為周期的序列遍歷其中的r個狀態(tài)由前面的分析，對應任意的p(x)2n-1個狀態(tài)的狀態(tài)轉移圖由若干個不同的圈組成，所有圈遍歷的狀態(tài)之和正好是2n-1個如果p(x)不可約，則所有可能序列的周期都是r，那么全部狀態(tài)的狀態(tài)轉移圖將是(2n-1)/r個圈第二章流密碼：2.2線性反饋移位寄存器352.2.3m序列產(chǎn)生器定理2.5n級LFSR產(chǎn)生的序列有最大周期2n-1的必要條件是其特征多項式為不可約的。證明：設n級LFSR產(chǎn)生的序列周期達到最大2n-1，除0序列外，每一序列的周期由特征多項式惟一決定，而與初始狀態(tài)無關。注意：只要有一條序列為m序列，則所有非0序列都是m序列設特征多項式為p(x)，若p(x)可約，可設為p(x)=g(x)h(x)，其中g(x)不可約，且次數(shù)k<n。由于G(g(x))G(p(x))，而G(g(x))中序列的周期一方面不超過2k-1，另一方面又等于2n-1，這是矛盾的，所以p(x)不可約。（證畢）該定理的逆不成立，即LFSR的特征多項式為不可約多項式時，其輸出序列不一定是m序列。由定理2-4易知，n次不可約多項式的周期不一定等于2n－1，可能是其一個因子第二章流密碼：2.2線性反饋移位寄存器362.2.3m序列產(chǎn)生器判斷一個多項式是否是不可約多項式是一個困難問題，像大數(shù)分解一樣。用低于其次數(shù)的所有不可約多項式去除，如果都不能除盡則是不可約的，一些低次不可約多項式，比如x,x+1；x2+x+1；x3+x2+1，x3+x+1；x4+x3+1，x4+x+1，x4+x3+x2+x+1，…注意如果多項式p(x)是不可約的，則其互反多項式也是不可約的【例2-4】：f(x)=x4+x3+x2+x+1為GF(2)上的不可約多項式，給定初始狀態(tài)0001，則輸出序列為？解：以f(x)為特征多項式的LFSR的輸出序列可由遞推式

ak=ak-1ak-2ak-3ak-4(k4)

和給定的初始狀態(tài)求出，現(xiàn)在初始狀態(tài)為0001，則有輸出序列為0011…，周期為5，不是m序列。這是因為f(x)|(x5-1)第二章流密碼：2.2線性反饋移位寄存器狀態(tài)(a4,a3,a2,a1)輸出1000011000011000011100011100001100001100001110001110000110000110000111372.2.3m序列產(chǎn)生器定義2-4：若n次不可約多項式p(x)的階為2n-1，則稱p(x)是n次本原多項式定理2.6設{ai}G(p(x))，{ai}為m序列的充要條件是p(x)為本原多項式。證明：若p(x)是本原多項式，則其階為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)的階不超過2n-1，所以p(x)的階為2n-1，即p(x)是本原多項式。（證畢）第二章流密碼：2.2線性反饋移位寄存器382.2.3m序列產(chǎn)生器在有限狀態(tài)機模型中，若某n-LFSR產(chǎn)生一個m-序列，則其狀態(tài)圖除了單點(00…0)構成的圈外，就是由F2n\{(00…0)}中所有點排列而成的一個大圈，因而其任何非全零的輸出序列均是m-序列，故稱之為m-序列生成器。已經(jīng)證明，對于任意的正整數(shù)n，至少存在一個n次本原多項式。所以對于任意的n級LFSR，至少存在一種連接方式使其輸出序列為m序列。第二章流密碼：2.2線性反饋移位寄存器392.2.3m序列產(chǎn)生器【例2-5】設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)為特征多項式，則輸出序列的遞推關系為ak=ak-1ak-4(k4)若初始狀態(tài)為1001，則輸出為：11110101…狀態(tài)序列為：1001，0100，0010，0001，1000，1100，1110，1111，0111，1011，0101，1010，1101，0110，0011，1001，0100，0010，0001……可見，它是周期為24-1=15，即輸出序列為m序列。第二章流密碼：2.2線性反饋移位寄存器402.2.4m序列的破譯及B-M算法m序列雖然具有最大的周期，然而因它是線性序列而極其不安全，只要知道連續(xù)的2n個bit的序列就可以完全破譯了。即可以求出m序列產(chǎn)生器特征多項式的n個系數(shù)。因此線性反饋移位寄存器序列不能用作密鑰流之所以需要2n個比特，是因為唯一確定一個m序列生成器的參數(shù)包括n個比特的狀態(tài)和n個系數(shù)事實上如果我們知道LFSR是m序列產(chǎn)生器及其級數(shù)的話，那么cn=1就確定了，這時只要知道連續(xù)的2n-1個比特序列就可以破譯當然如果不知道序列的級數(shù)，甚至也不知道是否m序列時，我們有更一般的序列綜合算法：B-M算法來求解第二章流密碼：2.2線性反饋移位寄存器412.2.4m序列的破譯及B-M算法一、已知m序列產(chǎn)生器的級數(shù)和連續(xù)的2n個密鑰流比特，來破譯m序列這時由這2n個密鑰流比特帶入遞推式可以得到n個關于特征多項式系數(shù)的方程，聯(lián)立方程組后即可求解下面我們將證明，一定有唯一解有限域上的二元加法序列密碼是目前最為常用的序列密碼體制設滾動密鑰生成器是線性反饋移位寄存器，產(chǎn)生的密鑰是m序列。又設Sh和Sh＋1是序列中兩個連續(xù)的n長向量（兩個連續(xù)的狀態(tài)），其中第二章流密碼：2.2線性反饋移位寄存器422.2.4m序列的破譯及B-M算法設序列{ai}滿足線性遞推關系ah+n=c1ah+n－1c2ah+n－2…cnah可表示為：即Sh＋1＝M·Sh，M是其中矩陣又設敵手知道一段長為2n的明密文對x＝x1x2..x2n，y＝y(tǒng)1y2..y2n于是由二元加法流密碼加密變換變型算法zi=xiyi可得長為2n的密鑰序列z＝z1z2..z2n第二章流密碼：2.2線性反饋移位寄存器432.2.4m序列的破譯及B-M算法由長為2n的密鑰序列可推出LFSR連續(xù)的n+1個狀態(tài)：S1=(z1z2..zn)T

記為(a1a2..an)T（此處教材中少了轉置符號）S2=(z2z3..zn+1)T

記為(a2a3..an+1)T…Sn+1=(zn+1zn+2..z2n)T

記為(an+1an+2..a2n)T作矩陣X=(S1S2…Sn)則(an+1an+2..a2n)＝(cncn-1..c1)=(cncn-1..c1)X若X可逆，則(cncn-1..c1)＝(an+1an+2..a2n)X－1即2n個元素構成一個行向量和一個矩陣，從而可以推導出密鑰產(chǎn)生器的生成多項式第二章流密碼：2.2線性反饋移位寄存器442.2.4m序列的破譯及B-M算法而X是由S1S2…Sn作為列向量構成的，要證X可逆，只需證明這n個向量線性無關證明：由序列遞推式ah+n=c1ah+n－1c2ah+n－2…cnah可得向量之間遞推關系Sh+n=c1Sh+n－1c2Sh+n－2…cnSh在二元域上Sh+n=c1Sh+n－1＋c2Sh+n－2＋…＋cnSh

對于n級m序列，n是生成該序列的最小級數(shù)設m是使S1，S2，…，Sm

線性相關的最小整數(shù)，即存在一組不全為0的系數(shù)l1，l2，…，lm，不妨設l1＝1使得m個非零向量滿足Sm+l2Sm－1＋l3Sm－2＋…＋lmS1＝0即Sm＝l2Sm－1＋l3Sm－2＋…＋lmS1

（二元域加法）第二章流密碼：2.2線性反饋移位寄存器452.2.4m序列的破譯及B-M算法那么對于任意整數(shù)i有，方程兩邊同時左乘Mi

得Sm＋i＝MiSm＝Mi(l2Sm－1＋l3Sm－2＋…＋lmS1)

＝l2MiSm－1＋l3MiSm－2＋…＋lmMiS1

＝l2Sm＋i－1＋l3Sm＋i－2＋…＋lmSi＋1由于以上關系式對任意的i都成立，所以它也給出了密鑰流的一個遞推關系式

am+i=l2am+i－1l3am+i－2…lmai+1即密鑰流可以由m－1級LFSR生成，而由已知得m序列密鑰流的級數(shù)最小為n，所以必有n<=m－1而m是使得S1，S2，…，Sm線性相關的最小整數(shù)，現(xiàn)在n<m所以n個向量S1，S2，…，Sn必線性無關，即矩陣X可逆。第二章流密碼：2.2線性反饋移位寄存器462.2.4m序列的破譯及B-M算法【例2－6】設敵手得到密文串1010和相應密文串1001，并且假定敵手還知道密鑰流是使用5級移位寄存器產(chǎn)生的，采用二元加法流密碼。試破譯該密鑰流產(chǎn)生器，即求解出遞推關系解：由明密文串立即可得相應得密鑰流為二者對應位異或，得1111由已知的移位寄存器的級數(shù)5，提取密鑰流的前10個比特，建立如下方程：STn＋1＝CX(a6a7a8a9a10)=(c5c4c3c2c1)，即(01000)=(c5c4c3c2c1)第二章流密碼：2.2線性反饋移位寄存器472.2.4m序列的破譯及B-M算法而＝，從而(c5c4c3c2c1)＝(01000)

所以有(c5c4c3c2c1)＝(10010)從而密鑰流的遞推關系為ai＋5=c2ai＋3c5ai＝ai＋3ai矩陣的逆滿足A-1=A*/|A|等于A的伴隨陣除以A的行列式解方程組還可用克萊姆法則，ci＝|D6-i|/|D|由于矩陣滿秩，|D|＝1這種方法不容易確定所適用的LFSR的級數(shù)n，從而不能導致恰當規(guī)模的線性方程組；并且當上述n很大時，求解相應規(guī)模線性方程組也很困難。第二章流密碼：2.2線性反饋移位寄存器482.2.4m序列的破譯及B-M算法(二)B-M算法當不知道LFSR的特性和級數(shù)時，對于給定的N長的密鑰流比特(a1,a2,…,aN)，基于B-M算法可求解出產(chǎn)生該序列的最短的LFSR及其極小多項式B-M算法即著名的Berlekamp-Massey迭代算法，用于解決LFSR的綜合問題LFSR的綜合問題就在于根據(jù)序列的少量比特求出整個序列的線性復雜度n和極小多項式f(x)。所以由m序列的2nbit肯定能求出生成多項式和級數(shù)即如下問題：設a(N)=(a1,a2,…,aN)是一個長度為N的序列，fN(x)是一個能生成a(N)且級數(shù)最小的LFSR的特征多項式，lN是LFSR的級數(shù)，則把<fN(x),lN>稱為a(N)的線性綜合解1969年Berlekamp和Massey給出了求解<fN(x),lN>的迭代算法第二章流密碼：2.2線性反饋移位寄存器492.2.4m序列的破譯及B-M算法第二章流密碼：2.2線性反饋移位寄存器注：在二元域上dndm-1=1502.2.4m序列的破譯及B-M算法例：輸入：a10=0100100001fn(x)表示前n個元素的極小多項式，ln表示此時的線性復雜度f0(x)=1，為初始值f4(x)=1,而線性復雜度為2，退化形式，表示沒有反饋，兩個移位寄存器直連f8(x)，f9(x)＝1同理，無反饋時相當于反饋為0例如當aN＝100000000時，可計算出fN(x)=1,lN=1,無反饋的初值為1的一級LFSR第二章流密碼：2.2線性反饋移位寄存器na10dnfn(x)lnmfm(x)0001011110112001－1x1+1=1+x223011+x22114111+x21－x3－1*1=12115001－1x4－11＝1＋x336001＋x337011＋x33418001＋x3－1x7－41=159111571＋x3101－1x9-7(1＋x3)=1+x2+x55例1：輸入：a10=0100100001初始化階段且由f2(x)計算出了d2=0由d3=1及fm(x)=1計算出了f4(x)并計算出了d4=1512.2.4m序列的破譯及B-M算法有關B-M算法的結果定理

應用B-M算法，若以N長序列aN為輸入，得到輸出<fN(x),lN>，則⑴以fN(x)為特征多項式的lN-LFSR是產(chǎn)生aN的最短LFSR，且當lNN/2時，迭代至第2lN步就得到最終輸出，即：=<fN(x),lN>。⑵當lNN/2時，產(chǎn)生aN的最短LFSR只是上述一個；否則共有

個。即將序列補齊到2lN可任意添加2lN－N個元素

作業(yè)：使用B-M算法，求產(chǎn)生a6＝100101的極小多項式和線性復雜度？第二章流密碼：2.2線性反饋移位寄存器522.2.5m序列的偽隨機性同步流密碼的安全性取決于密鑰流的安全性，要求密鑰流序列有好的隨機性，以使密碼分析者對它無法預測。即使截獲其中一段，也無法推測密鑰流產(chǎn)生器的任何其它信息。如果密鑰流是周期的，要完全做到隨機性是困難的。嚴格地說，這樣的序列不可能做到隨機，只能要求截獲比周期短的一段時不會泄露更多信息，這樣的序列稱為偽隨機序列,PseudoRandomSequence游程：序列中連0或連1串稱為1個游程連0或連1串中包含的0或1的個數(shù)稱為游程長度設{ai}=(a1a2a3…)為0、1序列，例如，其前兩個數(shù)字是00，稱為0的2游程；11，是1的2游程；再下來是0的1游程和1的3游程第二章流密碼：2.2線性反饋移位寄存器532.2.5m序列的偽隨機性首先討論隨機序列的一般特性。定義：GF(2)上周期為T的序列{ai}的自相關函數(shù)定義為

R(τ)=，0τT－1和式表示序列{ai}與{ai＋τ}（序列{ai}向后平移τ位得到）在一個周期內(nèi)對應位相同的位數(shù)與對應位不同的位數(shù)之差。當τ=0時，R(τ)=1；當τ≠0時，稱R(τ)為異相自相關函數(shù)。在計算時，R(τ)等于{ai}在一個周期內(nèi)，與其自身循環(huán)左移位后代入公式第二章流密碼：2.2線性反饋移位寄存器542.2.5m序列的偽隨機性Golomb對偽隨機周期序列提出了應滿足的如下3個隨機性公設：①在序列的一個周期內(nèi)，0與1的個數(shù)相差至多為1{ai}中0與1出現(xiàn)的概率基本上相同②在序列的一個周期內(nèi)，長為i的游程占游程總數(shù)的1/2i(i=1,2,…)，且在等長的游程中0的游程個數(shù)和1的游程個數(shù)相等。0與1在序列中每一位置上出現(xiàn)的概率相同③異相自相關函數(shù)是一個常數(shù)。通過對序列與其平移后的序列做比較，不能給出其他任何信息滿足三條假設的序列也稱為偽噪聲序列，pseudonoisesequence，簡稱PN碼，常用于CDMA，通信同步，導航，雷達測距等當然滿足這些條件的偽隨機序列，如果是LFSR產(chǎn)生的，線性復雜度很小，則不能作為安全的密鑰流，也不能作為隨機數(shù)產(chǎn)生器第二章流密碼：2.2線性反饋移位寄存器552.2.5m序列的偽隨機性從密碼系統(tǒng)的角度看，一個偽隨機序列還應滿足下面的條件：①{ai}的周期相當大，比如大于1050。②{ai}的確定在計算上是容易的。容易找到滿足條件的序列③由密文及相應的明文的部分信息，不能確定整個{ai}m序列滿足Golomb的3個隨機性公設定理2.7GF(2)上的n長m序列{ai}具有如下性質：①0,1平衡性：在一個周期內(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}的自相關函數(shù)為R(τ)=第二章流密碼：2.2線性反饋移位寄存器562.2.5m序列的偽隨機性證明：注意m序列包含的2n-1個狀態(tài)的遍歷性，可進一步證明題設①考察：移出的每個bit都會依次經(jīng)過某個寄存器ai在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。由于全0狀態(tài)不出現(xiàn)，所以0少了一個。②采用狀態(tài)考察法對n=1,2，易證結論成立。n＝1時，初態(tài)只能為1，如果為0，則為全0狀態(tài)n＝2時，1+x+x2，序列周期為3，比如011011011…對n>2，當1in-2時，n長m序列的一個周期內(nèi)，長為i的0游程數(shù)目等于序列中如下形式的狀態(tài)數(shù)目：100…01*…*，且每個100…01串必經(jīng)過連續(xù)的i+2個寄存器，其中n-i-2個*可任取0或1。由遍歷性，這種狀態(tài)共有2n-i-2個。同理可得長為i的1游程數(shù)目也等于2n-i-2，所以長為i的游程總數(shù)為2n-i-1。第二章流密碼：2.2線性反饋移位寄存器572.2.5m序列的偽隨機性0的n游程不會出現(xiàn)，因為寄存器不會出現(xiàn)全0狀態(tài)0的n-1游程有一個10…01(n-1個0)，不可能有兩個0的n-1游程，否則必在一個周期內(nèi)發(fā)生狀態(tài)重復，從而序列周期小于2n-11的n游程必有一個，因為m序列會遍歷所有非0狀態(tài)1的游程不會更大，假設會出現(xiàn)1的n+1游程，那么這連續(xù)的n+1個1中前n個1構成一個狀態(tài)，而下一個狀態(tài)還是n個1，也就是說全1狀態(tài)的下一個狀態(tài)還是全1，從而輸出的序列就是全1序列，這和m序列矛盾于是在一個周期內(nèi)，總游程數(shù)為1＋1＋＝2n-1③采用構造法證明{ai}是周期為2n-1的m序列，對于任一正整數(shù)τ(0<τ<2n-1)，{ai}+{ai+τ}在一個周期內(nèi)為0的位的數(shù)目正好是序列{ai}和{ai+τ}對應位相同的位的數(shù)目R(τ)＝＝第二章流密碼：2.2線性反饋移位寄存器582.2.5m序列的偽隨機性設序列{ai}滿足遞推關系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+τ)令bj=ajaj+τ，則由遞推序列{ai}可推得遞推序列{bi}＝{ai}+{ai+τ}{bi}滿足bh+n=c1bh+n－1c2bh+n－2…cnbh{bi}也是m序列。為了計算R(τ)，只要用{bi}在一個周期中0的個數(shù)減去1的個數(shù)，再除以2n-1，即

R(τ)==（證畢）第二章流密碼：2.2線性反饋移位寄存器592.3.1非線性序列的設計要求從二元加法同步流密碼的結構可以看出，如果產(chǎn)生的密鑰流具有完全隨機的特性，即真隨機性，那么密鑰比特之間是完全相互獨立的，每一個比特滿足P(zl=0)=P(zl=1)=1/2，那么這種加密體制就是一次一密密碼(OneTimePadding一次一密亂碼本)，這時密鑰的長度至少和明文的長度一樣長，即真隨機數(shù)直接用作密鑰流，可以達到無條件安全然而過長的密鑰缺乏實用性，只是一種理想體制實際的流密碼體制，希望用有限的密鑰產(chǎn)生一個安全的不可預測密鑰流。比如具有k比特密鑰的密鑰流產(chǎn)生器(KG)但從信息論意義上講，kbit的密鑰不論進行何總固定變換，其安全性最大也就達到密鑰長度，一般低于一次一密。設計一個性能良好的序列密碼是一項十分困難的任務。最基本的設計原則是“密鑰流生成器的不可預測性”，還要避免內(nèi)部狀態(tài)演變的線性性以及輸出序列統(tǒng)計性質的偏向性第二章流密碼：2.3非線性序列602.3.1非線性序列的設計要求一般來講，密鑰流產(chǎn)生器

的輸入(種子密鑰k)是較短的，其輸出為周期序列首先，產(chǎn)生的周期要足夠大，否則不安全對于二元序列，如果種子密鑰k為n比特，則其周期最大為2n希望一個周期的長度很長，這樣在加密有限的明文時只需要一個周期內(nèi)的某個片斷，就像真隨機的一樣其次，序列的線性復雜度也要足夠大，否則很容易被破譯從LFSR產(chǎn)生的線性序列的破譯不難看出，因其線性復雜度遠遠小于周期，僅需要知道少量的比特就可通過B-M算法破譯，所以無法用作密鑰流而且線性序列的線性復雜度一般等于移位寄存器的個數(shù)，選擇大的線性復雜度意味著需要使用大量移位寄存器，這不實際所以需要采用非線性的密鑰流產(chǎn)生器第二章流密碼：2.3非線性序列612.3.1非線性序列的設計要求首先了解一個結論：定理如果一個比特流是一個周期序列，則它一定是線性反饋移位寄存器序列。(也就是說，不管它實際是由非線性還是線性產(chǎn)生器生成，其產(chǎn)生序列一定可以等效為由一個LFSR生成)證明設比特流k的最小周期是N。則l>N后，kl=kl-N。因此比特流k為N階線性反饋移位寄存器序列，抽頭系數(shù)為

{c1、c2、…、cN}={0、0

、…0、1}（即特征多項式f(x)=1+xN），初始狀態(tài)為k1k2k3…kN由以上定理，如果以序列的周期p作為生成它的LFSR的階數(shù)，則對應的特征多項式為f(x)=1+xp，它可以生成該序列。而周期序列的線性復雜度是生成該序列的最短LFSR的級數(shù)，所以周期序列的線性復雜度一定不超過它的最小周期第二章流密碼：2.3非線性序列622.3.1非線性序列的設計要求對于非線性序列而言，一個重要的任務是基于很少的移位寄存器，構造一個其線性復雜度盡可能大的序列，最好接近周期注意密鑰流序列和偽隨機序列兩個概念的區(qū)別前者是用于加解密的，要求在密碼學上是安全的后者是用于產(chǎn)生性能良好的滿足某種應用需求的隨機數(shù)的，比如PN碼當偽隨機序列產(chǎn)生的隨機數(shù)用在密碼應用時，和密鑰流序列是一致的針對以上考慮，在多年的流密碼研究發(fā)展過程中，人們總結了經(jīng)密鑰k擴展而成的密鑰流序列z應滿足的性質：1.種子密鑰的長度足夠長（一般來說就是流密碼的密鑰長度）比如128比特，這樣密鑰空間將有2128規(guī)模，抗窮搜索攻擊，決定了密碼強度2.極大的周期：一般來說不應小于1050，約21663.良好的統(tǒng)計特性密鑰流序列k具有均勻的n-元分布，例如均勻的游程分布)第二章流密碼：2.3非線性序列632.3.1非線性序列的設計要求4.極大的線性復雜度密鑰流序列z不可由一個低級的LFSR產(chǎn)生5.極大的k錯線性復雜度密鑰流序列不可與一個低級LFSR產(chǎn)生序列只有比率很小的相異項如果密鑰流序列周期為n，而人為改變其1比特后周期急劇變小，例如變?yōu)閚/t，則序列的安全性就大為減小。把改變?nèi)我鈑個比特后序列的最小的線性復雜度稱為K錯線性復雜度6.抗統(tǒng)計分析利用統(tǒng)計方法由密鑰流提取關于KG結構或k的信息在計算上不可行7.混亂性：即z的每一bit均與z的大多數(shù)bit有關；8.擴散性：即z任一bit的改變要引起z在全貌上的變化9.抗線性分析第二章流密碼：2.3非線性序列642.3.1非線性序列的設計要求一些典型的流密碼分析方法流密碼安全性的關鍵指標：線性復雜度和k-錯復雜度，非線性性典型方法折中攻擊：將時間、記憶和信息復雜度進行策略性的平衡猜測和決定攻擊：猜測密鑰流生成器的部分內(nèi)部狀態(tài)相關攻擊：觀察輸出和某些內(nèi)部狀態(tài)的相關性最佳仿射攻擊：用線性LFSR來逼近非線性算法代數(shù)攻擊：建立密鑰和輸出bit之間的代數(shù)方程邊信道攻擊：觀察能量消耗和時間延遲第二章流密碼：2.3非線性序列652.3.2密鑰流產(chǎn)生器的結構非線性的密鑰流序列的產(chǎn)生主要是基于移位寄存器序列1.采用非線性的狀態(tài)轉移函數(shù)φ(反饋函數(shù))這種FSR采用非線性反饋函數(shù)產(chǎn)生大周期的非線性序列如M-序列，周期2n，具有較好的密碼學性質，但反饋函數(shù)選擇有難度再有就是1993年A.Klapper和M.Goresky提出的進位移位寄存器。2.采用線性的φ和非線性的輸出函數(shù)ψ這類密鑰流生成器是當前流密碼設計的主流可分解為驅動子系統(tǒng)和非線性組合子系統(tǒng)，如圖驅動子系統(tǒng)常用一個或多個LFSR來實現(xiàn)非線性組合子系統(tǒng)用非線性組合函數(shù)(非線性布爾函數(shù))來實現(xiàn)，主要用來提高生成序列的線性復雜度最基本的形式有三類前饋生成器(濾波生成器)、非線性組合生成器、鐘控生成器以上基本類型的組合、采樣等，如縮減生成器、停走生成器第二章流密碼：2.3非線性序列662.3.2密鑰流產(chǎn)生器的結構3.也有非移位寄存器序列，比如RC4需要說明的是，這些密鑰流產(chǎn)生器都可以作為偽隨機序列產(chǎn)生器而偽隨機序列產(chǎn)生器在密碼學中主要用于產(chǎn)生隨機數(shù)，比如對稱加密時的會話密鑰，因而僅需要產(chǎn)生少量的比特，所以偽隨機序列產(chǎn)生器還有很多構造方法，比如基于數(shù)學困難問題，基于分組密碼等，將在密鑰管理一章中的隨機數(shù)產(chǎn)生一節(jié)詳細介紹第二章流密碼：2.3非線性序列672.3.2密鑰流產(chǎn)生器的結構流密碼中非線性的布爾函數(shù)承擔著提高序列線性復雜度、保持輸出序列良好統(tǒng)計特性的關鍵作用，需要滿足很多的特性比如非線性度、代數(shù)次數(shù)、非退化性、相關免疫性、雪崩準則、擴散準則等。比如Bent函數(shù)就是一類具有很好指標特性的布爾函數(shù)這里主要給出非線性度的概念，主要為了抵抗線性攻擊，應盡可能大定義設L是Z2上所有線性函數(shù)的集合，即L={ux+v|uZ2n,vZ2}。則布爾函數(shù)f(x)的非線性度定義為Nf=minl(x)L

dH(f(x),l(x))其中dH()是漢明距離，x和u是n元向量第二章流密碼：2.3非線性序列682.3.2密鑰流產(chǎn)生器的結構關于密鑰有幾種不同用法，而且不同類型的產(chǎn)生器也不同以下是前饋序列用作密鑰流時的情況有以下三種不同的用法：（1）原始密鑰是初始狀態(tài)，而將極小多項式和非線性布爾函數(shù)公開。此時原始密鑰最短，但需要精心設計非線性布爾函數(shù)。（2）原始密鑰是初始狀態(tài)和極小多項式，而將非線性布爾函數(shù)公開。此時原始密鑰長一些，但對非線性布爾函數(shù)的要求低一些。（3）原始密鑰是初始狀態(tài)、極小多項式、非線性布爾函數(shù)。此時原始密鑰最長，但對非線性布爾函數(shù)的要求最低。一般結構性很強的序列主要以初始狀態(tài)和極小多項式為密鑰，而作為國際標準的算法，一般只有初始狀態(tài)作為密鑰第二章流密碼：2.3非線性序列692.3.3典型非線性序列產(chǎn)生器介紹一、M-序列（非線性反饋移位寄存器）若一n-FSR的輸出序列的周期達到最大值2n，則稱此序列為(n級)M-序列。則其狀態(tài)圖是一個包含F(xiàn)2n中所有2n個點的大圈，從而這個n-FSR由任意初態(tài)產(chǎn)生的序列都是M-序列，這個n-FSR本身也就被稱為M-序列生成器，而相應的反饋函數(shù)被稱為M-序列反饋函數(shù)。例：反饋函數(shù)為的3-FSR。xi是寄存器狀態(tài)布爾函數(shù)f(x1,x2,…,xn)是n級M-序列的反饋函數(shù)的必要條件是:⑴f(x1,x2,…,xn)是非奇異的，即f(x1,x2,…,xn)=x1+f0(x2,x3,…,xn)⑵⑴中n-1元布爾函數(shù)f0(x2,x3,…,xn)還必須滿足：f0的重量W(f0)是奇數(shù)；在f0的任一表達中，x2,x3,…,xn都出現(xiàn)；在f0的多項式表示中，項數(shù)為奇數(shù)、常數(shù)項1必出現(xiàn)、線性項x2,x3,…,xn不能全出現(xiàn)、且n-1次項x2x3…xn一定出現(xiàn)第二章流密碼：2.3非線性序列702.3.3典型非線性序列產(chǎn)生器介紹二、Geffe序列生成器(非線性組合生成器)Geffe序列生成器由3個LFSR組成，其中LFSR2作為控制生成器使用，如圖所示當LFSR2輸出1時，LFSR2與LFSR1相連接當LFSR2輸出0時，LFSR2與LFSR3相連接若設LFSRi的輸出序列為{ak(i)}(i=1,2,3)，則輸出序列{bk}可以表示為＝ak(1)ak(2)+ak(3)ak(2)+ak(3)第二章流密碼：2.3非線性序列712.3.3典型非線性序列產(chǎn)生器介紹二、Geffe序列生成器(非線性組合生成器)Geffe序列生成器也可以表示為多路復合的形式，其中LFSR1和LFSR3作為多路復合器的輸入，LFSR2控制多路復合器的輸出。設LFSRi的特征多項式分別為ni次本原多項式，且ni兩兩互素，則Geffe序列的周期為，線性復雜度為(n1+n3)n2+n3注意，這里如果n和m互素，由歐幾里得算法可知，2n－1，2m－1也互素，即周期也兩兩互素，再由和序列與乘積序列(對應元素相乘后所得序列)的性質，可得出以上結論互素時，乘積序列的周期等于各周期的乘積，和序列的周期等于最小公倍數(shù)，可知周期為三者乘積。此時的線性復雜度也滿足乘積和和的條件，固有以上結果。Geffe序列的周期實現(xiàn)了極大化，且0與1之間的分布大體上是平衡的。顯然密鑰流生成器輸出序列的周期不大于各驅動序列周期的乘積，因此，提高輸出序列的線性復雜度應從極大化其周期開始第二章流密碼：2.3非線性序列722.3.3典型非線性序列產(chǎn)生器介紹三、J-K觸發(fā)器(非線性組合生成器)J-K觸發(fā)器如下圖所示，它的兩個輸入端分別用J和K表示，其輸出ck不僅依賴于輸入，還依賴于前一個輸出位ck-1，即ck=()ck-1+x1其中x1和x2分別是J和K端的輸入。由此可得J-K觸發(fā)器的真值表第二章流密碼：2.3非線性序列732.3.3典型非線性序列產(chǎn)生器介紹三、J-K觸發(fā)器(非線性組合生成器)利用J-K觸發(fā)器的非線性序列生成器見圖令驅動序列{ak}和{bk}分別為m級和n級的m-序列，則有ck=()ck-1+ak=(ak+bk+1)ck-1+ak如果令c-1=0，則輸出序列的最初3項為c0=a0；

c1=(a1+b1+1)a0+a1c2=(a2+b2+1)((a1+b1+1)a0+a1)+a2當m與n互素且a0+b0=1時，序列{ck}的周期為(2m-1)(2n-1)兩個序列同時回到a0和b0時由于a0+b0=1，剛好恢復初態(tài)第二章流密碼：2.3非線性序列顯然當輸入的兩個序列再次回到a0和b0時J-K觸發(fā)器的輸出又恢復到以上狀態(tài)，由于m與n互素，(2m-1)和(2n-1)也互素，當運行p＝(2m-1)(2n-1)拍以后才能達到此狀態(tài)。742.3.3典型非線性序列產(chǎn)生器介紹例2－7：令m=2,n=3，兩個驅動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。由表達式ck=(ak+bk+1)ck-1+ak可得ck=因此，如果知道{ck}中相鄰位的值ck-1和ck，就可以推斷出ak和bk