第4章-序列密碼變換理論課件

4.1序列密碼的基礎理論

4.2密鑰序列的產生方法

4.3序列密碼的安全性

4.4序列密碼的應用第4章序列密碼變換理論4.1序列密碼的基礎理論

4.2密鑰序列的產生方4.1序列密碼的基礎理論序列密碼又稱流密碼(StreamCipher)，其加密方式是用密鑰序列z=z1z2…的第i個符號加密明文序列m=m1m2…的第i個符號，即在序列密碼中，第i個密鑰zi由第i時刻密鑰生成器的內部狀態(tài)和初始密鑰K決定。密碼的安全性主要取決于所用密鑰的隨機性，所以設計序列密碼的核心問題在于設計隨機性較好的密鑰序列生成器。密鑰序列生成器可看做是一個有限狀態(tài)自動機，由輸出符號集Γ、狀態(tài)集Δ、狀態(tài)轉移函數f、輸出函數g和初始狀態(tài)σ0所組成，如圖4-1所示。4.1序列密碼的基礎理論圖4-1密鑰序列生成器圖4-1密鑰序列生成器序列密碼可分為兩類：同步流密碼(SynchronousStreamCipher)和自同步流密碼(Self-SynchronousStreamCipher)，前者的密鑰序列獨立于明文和密文，后者的密鑰序列與已產生的一定數量的密文有關。同步流密碼的加密過程可描述為這里，σ0是初始狀態(tài)，可以由密鑰K確定；f是狀態(tài)轉移函數;g是產生密鑰序列的函數;E是由密鑰序列和明文序列產生密文的函數。序列密碼可分為兩類：同步流密碼(Synchronous在同步序列密碼中，只要發(fā)送端和接收端有相同的初始密鑰和初始狀態(tài)，就能產生出相同的密鑰序列，因此說收、發(fā)雙方的密鑰生成器是同步的。其優(yōu)點是無錯誤傳播，一個傳輸錯誤只能影響一個符號，不會影響后繼的解密結果。自同步序列密碼的加密過程可描述為其中，σ0=(c－t，c－t+1，…，c－1)是非秘密的初始狀態(tài)，是初始密鑰;其余符號與同步序列密碼中的含義相同。在同步序列密碼中，只要發(fā)送端和接收端有相同的初始密鑰和初4.1.1周期序列的極小多項式及m序列通常，密鑰流生成器中的驅動部分是一個反饋移位寄存器。線性反饋移位寄存器LFSR(LinearFeedbackShiftRegister)的理論非常成熟，它的實現簡單、速度快、便于分析，因而成為構造密鑰流生成器最重要的部件之一。移位寄存器是一種有限狀態(tài)自動機，它由一系列的存儲單元、若干個乘法器和加法器通過電路連接而成。假設共有n個存儲單元(此時稱該移位寄存器為n級)，每個存儲單元可存儲一比特信息，在第i時刻各個存儲單元中的比特序列(aiai+1…ai+n－1)稱為移位寄存器的狀態(tài)，(a0a1…an－1)為初始狀態(tài)。在第j個時鐘脈沖到來時，存儲單元中的數據向前移動一位，狀態(tài)由(ajaj+1…aj+n－1)變?yōu)?aj+1aj+2…aj+n)，同時，按照固定規(guī)則產生輸入比特和輸出比特。圖4-2描述了GF(2)上的n級LFSR。4.1.1周期序列的極小多項式及m序列圖4-2GF(2)上的n級LFSR圖4-2GF(2)上的n級LFSR產生輸入數據的變換規(guī)則稱為反饋函數。給定了當前狀態(tài)和反饋函數，可以唯一確定輸出和下一時刻的狀態(tài)。通常，反饋函數是一個n元布爾函數。

定義4-1設LFSR的輸出序列為a=a0a1a2…，則稱滿足對任意i∈Z+，ai=ai+p的最小正整數p為序列的周期。具有有限周期的序列稱為周期序列。更一般地，如果存在一個下標i0，滿足ai+p=ai(對所有i≥i0成立)則稱序列a是周期為p的終歸周期序列。非終歸周期序列的周期定義為無窮大。產生輸入數據的變換規(guī)則稱為反饋函數。給定了當前狀態(tài)和反饋通常我們將形如a0a1…的序列稱為半無限序列，記作a∞，而將形如a0a1…an－1a0a1…an－1…的序列稱為周期為n的周期半無限序列，記作(an)∞。一個n級LFSR的輸出序列的最長周期由以下定理確定。定理4-1

n級LFSR的周期≤2n－1。周期是衡量序列偽隨機性的一個重要標準，要產生性能較好的密鑰序列，要求作為密鑰發(fā)生器的驅動部分的移位寄存器有較長的周期。除此之外，序列的隨機性還用游程分布和周期自相關函數來度量。通常我們將形如a0a1…的序列稱為半無限序列，記作a∞，

定義4-2在序列a∞中,若有at－1≠at=at+1=…=at+l－1≠at+l，則稱(xt，xt+1，…，xt+l－1)為一個長為l的游程。

定義4-3設序列(an)∞的周期為p，定義周期自相關函數為其中，A=|{0≤i＜p;ai=ai+j}|;D=|{0≤i＜p;ai≠ai+j}|。若p|j，則R(j)為同相自相關函數，此時A=p，D=0，故R(j)=1;若p

j，則R(j)為異相自相關函數。Golomb對于二進制序列的隨機性提出了三條假設［4］，滿足這些假設的序列就被視為具有較強的隨機性，或稱其為偽隨機序列(Pseudo-RandomSequence)。定義4-2在序列a∞中,若有at－1≠at=at+1這三條假設是：(1)若序列的周期為偶數，則在一個周期內，0、1的個數相等；若序列的周期為奇數，則在一個周期內，0、1的個數相差1。(2)在一個周期內，長度為l的游程數占游程總數的，且對于任意長度，0游程與1游程個數相等。(3)所有的異相自相關函數值相等。這三條假設也可以推廣到GF(q)上的序列。這三條假設是：LFSR可以用線性函數遞歸地定義，末端存儲器的輸入引入多項式f(x)=c0+c1x+c2x2+…+cn－1xn－1其中，未定元x(xak=ak－1)稱為延遲算子。f(x)稱為LFSR的聯結多項式。f(x)的互反多項式稱為LFSR的特征多項式。LFSR可以用線性函數遞歸地定義，末端存儲器的輸入已知二元周期序列a=a0a1a2…，其周期p(a)=L，顯然，由聯結多項式為1+xL－1的L級LFSR(稱為純輪換移位寄存器)可以產生序列a，聯結多項式為1+x2L－1，1+x3L－1，…的LFSR也可以產生a。我們將能產生a的LFSR的聯結多項式組成的集合記作J(a)：J(a)={g(x)|g(x)∈F2［x］，g(x)a=0}設ma(x)是J(a)中次數最低的首一多項式，則J(a)={h(x)ma(x)|h(x)∈F2［x］}即J(a)中的多項式都是ma(x)的倍式。事實上，可以證明J(a)是多項式環(huán)GF(2)［x］的一個理想，其生成元為ma(x)。通常稱ma(x)為周期序列a的極小多項式，也稱極小聯結式。顯然，用ma(x)作為聯結多項式產生序列a是效率最高的一種方案。已知二元周期序列a=a0a1a2…，其周期p(a)=L，由于序列的周期與其聯結多項式密切相關，下面我們介紹多項式的周期，并用多項式的周期來研究序列的周期。

定義4-4設g(x)為GF(2)上的多項式，deg(g(x))≥1，g(0)≠0，使g(x)|(1－xL)成立的最小正整數L稱為g(x)的周期(又稱階或指數)，記作p(g)。注：如果g(0)=0，則可將g表示為如下形式：g(x)=xlh(x)h(0)≠0此時，g(x)的周期定義為h(x)的周期。如果LFSR的聯結多項式中的cn－1≠0，則稱該LFSR是非退化的。由于序列的周期與其聯結多項式密切相關，下面我們介紹多項式

定理4-2設ma(x)是非退化LFSR產生的序列a的極小多項式，則p(a)=p(ma)，即a的周期等于多項式ma(x)的周期。由定理4-2知，n級LFSR的極小多項式周期的上界與其輸出序列的周期上界相同，均為2n－1。設f(x)∈F2［x］，deg(f(x))≥1，如果f(x)不能分解為GF(2)中兩個非平凡多項式的乘積，則稱f(x)是GF(2)上的不可約多項式(或既約多項式)。如果f(x)是GF(2)上的n次不可約多項式，并且其周期達到上界2n－1，則稱f(x)是GF(2)上的一個n次本原多項式。

定理4-3設LFSR的聯結多項式f(x)是GF(2)上常數項為1的既約多項式，則對于LFSR的任一非0輸出序列a，有ma(x)=f(x)，并且p(a)=p(f)。定理4-2設ma(x)是非退化LFSR產生的序列a的定義4-5周期為2n－1的n級LFSR的輸出序列稱為m序列。m序列是由n級線性移位寄存器所能產生的最長周期序列，同時，它也是研究最為成熟的序列。除了具有最長周期之外，它還有許多良好的偽隨機性質，因而在密碼學和擴頻通信等領域中得到了廣泛應用。m序列的基本特性由以下定理給出[2]。定義4-5周期為2n－1的n級LFSR的輸出序列稱定理4-4GF(q)上的n級m序列a∞具有以下性質：(1)a∞的周期為qn－1，線性復雜度為n。(2)對任意x∈GF(q)，x≠0，x在a∞的一個周期內出現qn－1次，0出現qn－1－1次，特別地，GF(2)上的m序列在一個周期內0的個數為2n－1，1的個數為2n－1－1。(3)a∞的極小多項式生成的所有非0序列均為m序列，它們是a∞的平移序列。(4)設(a(j))∞(j=1，2，…，k)為a∞的k個平移序列，任取k個常數xj∈GF(q)，則序列

或為全0序列，或為a∞的一個平移序列。定理4-4GF(q)上的n級m序列a∞具有以下性質：(5)對任意k(1≤k≤n)，稱為序列a∞的一個k維狀態(tài)向量。在連續(xù)qn－1個k維狀態(tài)向量中，GF(q)k中的每個非0向量出現qn－k次，0向量出現qn－k－1次。(6)如果aj=aj+1=…=aj+k－1=x∈GF(q)，且aj－1≠x，aj+k≠x，則稱(ajaj+1…aj+k－1)是一個長為k的x游程。(5)對任意k(1≤k≤n)，將序列a∞的一個周期首尾相連，則游程分布如下：①游程的總數為qn－1；②1≤k≤n－2時，對x∈GF(q)，長為k的x游程有(q－1)2qn－k－2個；③長為n－1的0游程有q－1個；④對x≠0，長為n－1的x游程有q－2個，長為n的x游程有1個。

將序列a∞的一個周期首尾相連，則游程分布如下：(7)設序列a∞的h間隔采樣序列為a(h，d)∞，即a(h，d)∞=adad+had+2h…，則a(h，d)∞是m序列當且僅當h與qn－1互素。當gcd(h，qn－1)=1時，m序列a(h，d)∞的極小多項式與起始采樣位置d無關，僅僅與采樣間隔h有關；不同的采樣間隔對應著不同的極小多項式。(8)對任意h=1，2，…，qn－2，d=0，1，…，qn－2且gcd(h，qn－1)=1，h間隔采樣序列a(h，d)∞遍歷了所有的n級m序列。下述定理給出了產生m序列的充要條件。(7)設序列a∞的h間隔采樣序列為a(h，d)∞，即

定理4-5設GF(2)上n級LFSR的聯結多項式為f(x)，用G(f)表示可以由此LFSR產生的全部序列集合，則G(f)中的非零序列均為n級m序列的充要條件是f(x)為GF(2)上的n次本原多項式。根據定理4-5，可將產生n級m序列的問題歸結為求GF(2)上n次本原多項式這個純代數問題，這屬于近世代數的內容，在此不加詳述。LFSR的綜合問題是指根據序列中的少量比特求出整個序列所滿足的線性遞推關系，這個問題可以用Berlelcamp-Massey算法(簡稱B-M算法)解決[6-7]。根據B-M算法，對于任意n級LFSR,連續(xù)抽取序列的2n項之后，都可以求出產生該序列的聯結多項式。該算法以長為N的二元序列a0，a2，…，aN－1為輸入，輸出產生該序列的最短LFSR的特征多項式fN(x)及其階數lN。定理4-5設GF(2)上n級LFSR的聯結多項式為f

B-M算法輸入：N，序列a0，a1，…，aN－1。第一步：n←0，〈f0(x)，l0〉←〈1，0〉。第二步：計算dn=fn(D)an，其中，D為延遲算子(Dak=ak－1)。(1)當dn=0時，〈fn+1(x)，ln+1〉←〈fn(x)，ln〉轉第三步；(2)當dn=1，且l0=l1=…=ln=0時，〈fn+1(x)，ln+1〉←〈1+xn+1，n+1〉轉第三步；B-M算法(3)當dn=1，且lm<lm+1=lm+2=…=ln(m<n)時，第三步：若n<N－1，n←n+1，轉第二步。輸出：〈fN(x)，lN〉。B-M算法的時間復雜性為O(N2)，空間復雜性為O(N)。B-M算法廣泛應用于BCH碼的譯碼中。一個二元隨機序列a0a1a2…可視作一個二元對稱信源的輸出，當前輸出位an與以前輸出段a0a1…an－1之間是完全獨立的，因此，即使已知a0，a1，…，an－1，an仍是不可預測的。而對于n級m序列，由B-M算法，只要得知其前2n位，就能以較快的速度求出序列的任一位。(3)當dn=1，且lm<lm+1=lm+2=…=ln4.1.2序列的線性復雜度

度量有限長或周期序列的隨機性的方法有很多，但最常用的方法是由Lempel和Ziv建議的“線性復雜度”方法［8］，用產生該序列的最短LFSR的長度來度量，這種方法本質上衡量了序列的線性不可預測性。

定義4-6一個有限序列a=a0a1…at的線性復雜度，是指對于選定的初始狀態(tài)，生成序列a所需要的線性反饋移位寄存器的最小階數，記作C(a)。對于全0序列，約定其復雜度為0。

定理4-6設a=a0a1a2…是二元周期序列，且序列a的線性復雜度C(a)=L≥1，則只要知道a中任意相繼的2L位就可確定整個序列及產生a的極小多項式。4.1.2序列的線性復雜度事實上，B-M算法給出了確定序列線性復雜度的有效方法，由于B-M算法可以求得任一給定序列的線性復雜度，從而使序列的線性復雜度成為同步序列密碼的一個重要強度指標。在序列密碼中，線性復雜度小的序列不能用作密鑰序列，但也不是說，線性復雜度大的序列就一定能作為密鑰序列。比如周期為p的序列：000…0100…10如果p很大，則產生該序列的LFSR長度也很大，然而該序列顯然不能作為密鑰序列。任何周期序列的線性復雜度顯然不超過它的周期。此外還可以利用矩陣的秩來研究序列的線性復雜度。事實上，B-M算法給出了確定序列線性復雜度的有效方法，由

定理4-7設域GF(q)上的序列a=a0a1…an－1，則a的線性復雜度等于矩陣Ga當Δ1，Δ2，…，Δn－1取遍GF(q)中所有值時的最小秩。證明:設Ga的最小秩為r(Ga)，將矩陣Ga的第一行至第n行分別標記為0至n－1。若a的線性復雜度C(a)=l，則存在線性遞推關系:(4-1)定理4-7設域GF(q)上的序列a=a0a1…an－從而對于l≤i≤n－1，只要適當地選擇Δ1，Δ2，…，Δn－1，便可將Ga的第i行表示為前面l行的線性組合，因此r(Ga)≤1。但由線性復雜度的定義，l是使式(4-1)成立的最小整數，因而也是第l行的前n－l個分量能夠表示成前面各行的對應分量線性組合的最小整數。故前l(fā)行線性獨立，從而r(Ga)≥l，故r(Ga)=l。定理4-7描述了有限長序列的線性復雜度的秩表示，下面討論無限序列的線性復雜度的秩表示。從而對于l≤i≤n－1，只要適當地選擇Δ1，Δ2，…，

定理4-8一個周期半無限序列(an)∞的線性復雜度等于矩陣的秩，即C((an)∞)=rank［M(an)］這里，Si(a)表示序列a循環(huán)左移i位得到的序列，稱矩陣M(an)為循環(huán)矩陣。定理4-8一個周期半無限序列(an)∞的線性復雜度等

證明:在周期半無限序列(an)∞=a0a1…an－1a0a1…an－1…中，ai=ai+n(i≥0)。顯然，(an)∞的線性復雜度至多為n，如果C((an)∞)=l，則對1≤i<∞，式(4-1)必成立。而該周期序列的線性復雜度是l當且僅當對序列中n個連續(xù)位，式(4-1)成立。為了使i≥l時，式(4-1)也成立，則(an)∞必須滿足以下的矢量方程:(4-2)因此，C((an)∞)是使式(4-2)成立的最小l。證明:在周期半無限序列(an)∞=a0a1…an－1如果C((an)∞)=l，則l是使M(an)的第Sl(a)行為前l(fā)行的線性組合的最小整數，也是式(4-2)成立的最小整數，因此rank［M(an)］≥l。另一方面，對式(4-2)兩邊同時乘以Sj，得上式表明，M(an)的每一行與以前各行線性相關，因此rank［M(an)］≤l。由此得到rank［M(an)］=l，從而C((an)∞)=rank［M(an)］。如果C((an)∞)=l，則l是使M(an)的第Sl(a線性復雜度是衡量序列密碼安全性的重要指標，但是要衡量一個密鑰序列的安全性，僅用線性復雜度是遠遠不夠的，原因在于線性復雜度嚴格局限于線性方式。20世紀80年代末至今，隨著頻譜理論在密碼學中的應用，人們又提出了線性復雜度輪廓、躍復雜度、重量復雜度、球體復雜度、k錯復雜度、變復雜度距離、定復雜度距離、球周期、非線性復雜度等多種度量序列隨機性和穩(wěn)定性的指標，使序列密碼的研究日趨完善。線性復雜度是衡量序列密碼安全性的重要指標，但是要衡量一個4.1.3和序列與乘積序列序列密碼中的密鑰流序列通常由多個序列經過一些簡單運算得到，因而研究序列間的運算規(guī)律有著重要的密碼學價值。本節(jié)簡要介紹序列的加法、Hadamard乘法及卷積運算的概念及這些運算對于序列的隨機性，特別是周期和線性復雜度的影響。為了進一步分析序列的性質，此處引入生成函數的概念。4.1.3和序列與乘積序列

定義4-7設(an)∞=a0a1…an－1a0a1…an－1…為GF(q)上的周期序列，(an)∞的生成函數定義為如下的形式冪級數:這里x為未定元。生成函數與序列是一一對應的。設B(x)、C(x)為GF(q)上的多項式，如果B(x)C(x)=1，則稱B(x)和C(x)互為乘法逆元素。定義4-7設(an)∞=a0a1…an－1a0a1…

定理4-9形式冪級數:有乘法逆元素當且僅當b0≠0。證明:如果存在使得B(x)C(x)=1，則下述方程成立：

定理4-9形式冪級數:由第一個方程知b0≠0，且c0由第一個方程唯一確定；再由第二個方程和c0唯一確定出c1。一般而言，利用第一個方程和遞歸關系式：可以確定出所有的cn，所得到的形式冪級數C(x)即為B(x)的乘法逆元。若B(x)的乘法逆元存在，則其必是唯一的，在這里用符號表示B(x)的乘法逆元。對A(x)∈GF(q)［x］，我們用表示A(x)與的乘積。由第一個方程知b0≠0，且c0由第一個方程唯一確定；再

定理4-10設GF(q)上的周期序列(an)∞滿足齊次線性遞歸關系式:(4-3)則ga(x)可以表示為有理分式的形式，即(4-4)其中，(4-5)反之，若r(x)是GF(q)上的一個次數小于n的多項式，且f(x)由式(4-5)給出，則由式(4-4)所定義的形式冪級數是一個滿足遞歸關系式(4-3)的齊次遞歸序列的生成函數。定理4-10設GF(q)上的周期序列(an)∞滿足齊證明:由于(4-6)如果(an)∞滿足式(4-3)，則當j≥n時，式(4-6)右端xi項的系數為零，因而f(x)ga(x)=r(x)。由定理4-9知，f(x)在GF(q)［x］中有乘法逆元，故式(4-4)成立。反之，由式(4-6)知，只有當對所有j≥L都成立時，f(x)ga(x)的次數才小于L，從而ga(x)的系數序列滿足遞歸關系式(4-3)。證明:由于上述定理表明，以f(x)為特征多項式的L階齊次線性遞歸序列和以f(x)為分母的有理分式之間存在著一一對應關系。當f(x)與r(x)互素時，稱分式為既約有理分式。序列的相加是指序列中的對應分量分別相加，它是最簡單的一種序列運算。上述定理表明，以f(x)為特征多項式的L階齊次線性遞歸序

定理4-11設為GF(q)上的k個周期序列，其周期分別為n1,n2,…,nk，生成函數分別為f1(x)，f2(x)，…，fk(x)，再設分別為其生成函數的既約有理分式表示，定義k個序列的和序列為，即令定理4-11設為GF(q)上的k則有:(1)序列s的極小多項式

；(2)序列s的周期p(s)≤lcm{n1，n2，…，nk}，當f1(x)，…，fk(x)兩兩互素時等號成立；(3)序列s的線性復雜度，當且僅當f1(x)，…，fk(x)兩兩互素時等號成立。上述定理表明，在序列密碼體制中，如果利用多個序列的和作為密鑰序列，則一般情況下其周期和線性復雜度會比單個序列有所增加，所以相加是一種有效的序列運算方法。更有意義的序列運算是序列的Hadamard乘積和序列的運算。則有:

定義4-8GF(q)上的兩個周期序列(an)∞和(bm)∞的Hadamard乘積定義為t=(an)∞×(bm)∞

ti=aibi;i=0，1，…兩個序列集合A和B的Hadamard乘積定義為T=A×B={(an)∞×(bm)∞：(an)∞∈A，(bm)∞∈B}

定理4-12設(an)∞與(bm)∞為GF(q)上的兩個周期序列，則其乘積序列t的線性復雜度滿足C(t)≤C((an)∞)·C((bm)∞)

定義4-9GF(q)上的兩個周期序列(an)∞和(bm)∞的卷積序列定義為

關于卷積序列的周期和線性復雜度有以下結論。定義4-8GF(q)上的兩個周期序列(an)∞和(b

定理4-13設(an)∞與(bm)∞為GF(q)上的兩個周期序列，其生成函數的既約有理分式分別為，令g(x)=gcd(fa(x)fb(x)，ra(x)rb(x))，再設ω為(an)∞與(bm)∞的卷積序列，則有:(1)ω的周期p(ω)≤nm，當gcd(fa(x)，rb(x))=1，gcd(fb(x)，ra(x))=1且gcd(n，m)=1時等號成立；定理4-13設(an)∞與(bm)∞為GF(q)上的(2)ω的線性復雜度C(ω)≤C((an)∞)+C((bm)∞)，當且僅當gcd(fa(x)，rb(x))=1且gcd(fb(x)，ra(x))=1時等號成立。從上述定理可以看出，序列間進行相加、相乘和卷積運算都能使周期和線性復雜度提高。這些運算各有優(yōu)缺點。在實際應用中，常常利用各種運算的復合使最終得到的密鑰序列具有良好的隨機性。本節(jié)并未給出定理4-11、4-12及4-13的證明，有興趣的讀者可以參閱參考文獻［1-2］。(2)ω的線性復雜度C(ω)≤C((an)∞)+C(4.1.4密鑰序列的穩(wěn)定性周期序列的穩(wěn)定性主要考慮當改變每個周期段相應的一些元素后，序列的各個隨機性指標(如周期、線性復雜度等)的變化情況。為了衡量序列線性復雜度的穩(wěn)定性，丁存生等提出了重量復雜度和球體復雜度兩個穩(wěn)定性度量指標［9］，隨后為了進一步分析序列密碼的穩(wěn)定性，又提出了定復雜度距離和變復雜度距離等指標。本節(jié)對此作簡要介紹。4.1.4密鑰序列的穩(wěn)定性

定義4-10設(an)∞為GF(q)上的周期序列，對于非負整數u，(an)∞的重量復雜度和球體復雜度分別定義為其中，WH((tn)∞)表示周期序列(tn)∞的Hamming重量。

引理4-1設(an)∞為GF(2)上的周期序列，(tn)∞為(an)∞的補序列，則C((an)∞)－1≤C((tn)∞)≤C((an)∞)+1定義4-10設(an)∞為GF(q)上的周期序列，對

證明:設序列(an)∞的極小多項式為f(x)，則易知(1+x)f(x)必為(tn)∞的一個特征多項式，因此C((tn)∞)≤C((an)∞)+1，由對稱性知C((an)∞)≤C((tn)∞)+1。

定理4-14設(an)∞、(tn)∞為GF(2)上的周期序列，an=a0a1…an－1，u為非負整數，則有:(1)WC0((an)∞)≤C((an)∞)；(2)；(3)C((an)∞)－1≤WCn((an)∞)≤C((an)∞)+1；(4)WCu((an)∞+(tn)∞)≤WCu((an)∞)+WCu((tn)∞)證明:設序列(an)∞的極小多項式為f(x)，則易知

證明:(1)是顯然的。若取(tn)∞為(an)∞的補序列，則(an)∞+(tn)∞為全1序列，由重量復雜度的定義，(2)顯然成立。取(tn)∞為全1序列,則(an)∞+(tn)∞是(an)∞的補序列,(3)得證。取(ωn)∞為GF(2)上的周期序列，ωn=ω0ω1…ωn－1，且WH(ωn)=u，則由于C((an)∞+(tn)∞)≤C((an)∞)+C((tn)∞)因此從而(4)成立。證明:(1)是顯然的。

定理4-15設(an)∞和(bn)∞是GF(q)上的周期序列，分別為其生成函數的既約有理分式表示，則對任意非負整數u，有定理4-15設(an)∞和(bn)∞是GF(q)上的特別地，當u=1時，有其中，。定理4-15給出了重量復雜度和球體復雜度的確切表達。其詳細證明見參考文獻［1］。特別地，當u=1時，有4.2密鑰序列的產生方法序列密碼主要有四種設計方法：系統(tǒng)論方法、復雜性理論方法、信息論方法和隨機化方法。在序列密碼設計中，最關鍵的問題是設計良好的偽隨機序列作為密鑰。4.1.1節(jié)中指出，n級m序列是以n次不可約多項式作為聯結多項式所能生成的最長周期序列。m序列具有許多優(yōu)良的密碼學性質，但在所有相同周期的序列中線性復雜度最低,因此一般不直接用作密鑰序列。為了構造線性復雜度較高的序列，傳統(tǒng)的方法主要有兩類。第一類是將m序列作為驅動序列，進行適當的變換或組合，在提高線性復雜度的同時，保留m序列的其它較好的偽隨機性。第二類是以計算上困難問題(如分解大整數、離散對數問題等)為基礎構造的偽隨機序列，如Shamir利用大數分解問題構造了一種偽隨機數生成器［10］。4.2密鑰序列的產生方法通常第二類方法的計算量較大，不適合直接用作密碼體制中的密鑰序列，但可用于消息認證等領域。第一類偽隨機數生成方法主要包括以下三種：(1)非線性組合。設為GF(q)上的k個m序列，f(x)為GF(q)上的k元非線性函數，令，則稱(tn)∞為非線性組合序列，稱為驅動序列。特別地，當k個m序列互為平移序列時，f(x)的輸出序列(tn)∞稱為非線性前饋序列。通常第二類方法的計算量較大，不適合直接用作密碼體制中的密(2)多路復合序列。用一個LFSR的輸出控制其它LFSR的輸出，產生的序列稱為多路復合序列。(3)鐘控序列。用某些m序列的輸出控制另一些m序列生成器的行為，所產生的與時鐘脈沖有關的輸出序列稱為鐘控序列。(2)多路復合序列。用一個LFSR的輸出控制其它LFS4.2.1前饋序列本節(jié)介紹由LFSR的輸出序列經過非線性變換而得到的前饋序列，后兩節(jié)介紹多路復合序列和鐘控序列。基于m序列的前饋序列可以分為兩大類：第一類由一個m序列經過非線性組合電路生成；第二類由若干個不同的m序列經過非線性化生成。設序列a∞為n級m序列，g(x)為非線性組合函數，其輸出序列為t∞，則第一類前饋序列生成器如圖4-3所示。4.2.1前饋序列圖4-3第一類前饋序列生成器圖4-3第一類前饋序列生成器圖4-3中，輸出序列t∞即為前饋序列。關于第一類前饋序列的密碼學特性有以下結論：

定理4-16基于GF(2)上的n級m序列的二元前饋序列(tn)∞的線性復雜度滿足:其中，k是非線性組合函數g(x)的次數。圖4-3中，輸出序列t∞即為前饋序列。

定理4-17若前饋序列生成器中的非線性函數次數為k，且具有如下形式：其中，ci∈GF(2)，i=0，1，…，n－k，且ci不全為零;g1(x0，…，xn－1)是次數小于k的布爾函數。則由g(x0，…，xn－1)產生的前饋序列t∞的線性復雜度滿足:

定理4-18設布爾函數g(x0,…,xn－1)=xr+g1(x0,x1,…,xr－1,xr+1,…,xn－1)，r=0，1，…，n－1，則以g為前饋函數所產生的輸出序列在一個周期內，0、1個數相差不會超過1。第二類前饋序列生成器的構成如圖4-4所示。定理4-17若前饋序列生成器中的非線性函數次數為k，圖4-4第二類前饋序列生成器圖4-4第二類前饋序列生成器關于第二類前饋序列有以下相關結論：

定理4-19若g(x)的輸入序列均為m序列，各個m序列的周期分別為n1，n2，…，nk，且對i≠j，i，j∈{1，2，…，k}，有(ni，nj)=1，則輸出序列t∞的周期為

一種典型的前饋序列是由Olsen和Scholtz等于1982年為減少通信系統(tǒng)中的干擾而構造的Bent序列［12］，Kumar等人分析了這類序列的線性復雜度［13］，由于Bent序列在生成過程中利用Bent函數濾波并具有可控的線性復雜度，因而在實際中得到了較廣泛的應用。

關于第二類前饋序列有以下相關結論：設n>8，n=4k，m=2k，2<d≤k，再設c∈GF(2)m，定義d次函數f(x)：GF(2)m→GF(2)，(4-7)其中，x=(x(1)，x(2))∈GF(2)m，x(1)，x(2)∈GF(2)k，x(1)=(x1，x2，…，xk)，xT為x的轉置，則顯然f(x)是GF(2)m上的Bent函數。設n>8，n=4k，m=2k，2<d≤k，再設c∈GF(

定義4-11設a∞={a(t)|t=0，1，2，…}為GF(2)上的n級m序列，為a∞的平移序列，令其中，函數f(x)如式(4-7)中所定義，則序列s∞={s(t)|t=0，1，2，…}稱為一個Bent序列。參考文獻［13］及［1］中給出了Bent序列線性復雜度的下界值。

定理4-20Bent序列的線性復雜度

。此外，典型的前饋序列還有幾何序列、No序列等，詳細構造可見參考文獻［2］。定義4-11設a∞={a(t)|t=0，1，2，…}4.2.2多路復合序列多路復合序列生成器涉及到多個LFSR，其中一個LFSR用于控制其它LFSR的輸出。常見的多路復合序列有Geffe序列、J-K觸發(fā)器及Pless序列等。

1.Geffe序列Geffe序列生成器由三個LFSR組成，其中LFSR2作為控制生成器使用，如圖4-5所示。4.2.2多路復合序列圖4-5Geffe序列生成器(一)圖4-5Geffe序列生成器(一)當LFSR2輸出1時，LFSR2與LFSR1相連接；當LFSR2輸出0時，LFSR2與LFSR3相連接。若設LFSRi(i=1，2，3)的輸入序列為a(i)，輸出序列為b，則有

Geffe序列生成器也可以表示為如圖4-6所示的形式。當LFSR2輸出1時，LFSR2與LFSR1相連接；當L圖4-6Geffe序列生成器(二)圖4-6Geffe序列生成器(二)圖中，LFSR1和LFSR3作為多路復合器的輸入；LFSR2控制多路復合器的輸出。

定理4-21在如圖4-6所示的Geffe序列生成器中，設LFSRi(i=1，2，3)的特征多項式分別為di次本原多項式，且di兩兩互素，則所生成的Geffe序列的周期為，線性復雜度為(d1+d3)d2+d3。Geffe序列的周期實現了極大化，且0與1之間的分布大體上是平衡的，因而不失為一種理想的偽隨機序列。圖中，LFSR1和LFSR3作為多路復合器的輸入；LFS

2.J-K觸發(fā)器J-K觸發(fā)器如圖4-7所示，它的兩個輸入端分別用J和K表示，其輸出ck不僅依賴于輸入，還依賴于前一個輸出位ck－1。2.J-K觸發(fā)器圖4-7J-K觸發(fā)器圖4-7J-K觸發(fā)器設J、K端的輸入分別為x1和x2，則由此可得J-K觸發(fā)器的真值表如表4-1所示。設J、K端的輸入分別為x1和x2，則利用J-K觸發(fā)器可以構造非線性序列生成器，如圖4-8所示。圖4-8利用J-K觸發(fā)器構造的非線性序列生成器利用J-K觸發(fā)器可以構造非線性序列生成器，如圖4-8所示圖中，a∞、b∞為驅動序列，且(4-8)設驅動序列a∞和b∞分別為n1級和n2級m序列，如果n1、n2互素且a0+b0=1，則序列c∞的周期為

。圖中，a∞、b∞為驅動序列，且由式(4-8)易知:因此，如果知道序列c∞中兩個相鄰位的值ck－1和ck，就可以推斷出ak或bk。進而可以由足夠多的這類信息分析得到序列a∞和b∞。為了克服這個缺點，Pless提出了由多個J-K觸發(fā)器序列驅動的多路復合序列方案，稱為Pless生成器［14］。由式(4-8)易知:

3.Pless生成器Pless生成器由八個LFSR、四個J-K觸發(fā)器和一個循環(huán)計數器構成，由循環(huán)計數器進行選通控制，如圖4-9所示。3.Pless生成器圖4-9Pless生成器圖4-9Pless生成器4.2.3鐘控序列鐘控序列最基本的模型是用一個LFSR控制另外一個LFSR的移位時鐘脈沖，如圖4-10所示。

圖4-10鐘控序列4.2.3鐘控序列圖4-10鐘控序列當LFSR1輸出1時，移位時鐘脈沖通過與門使LFSR2進行一次移位，從而生成下一位。當LFSR1輸出0時，移位時鐘脈沖無法通過與門影響LFSR2，因此LFSR2重復輸出前一位。輸出序列c∞稱為鐘控序列。設LFSR1和LFSR2的輸出序列分別為，周期分別為p1和p2，鐘控序列c∞的周期為p3，則有如下關系：其中，。當LFSR1輸出1時，移位時鐘脈沖通過與門使LFSR2進再設的極小多項式分別為GF(2)上的本原多項式f1(x)和f2(x)，deg(f1)=d1，deg(f2)=d2，且d1|d2，則

，由m序列的性質知，從而gcd(w，p2)=1，所以

此外，也可推導出c∞的線性復雜度為

，極小多項式為

。再設的極小多項式分別為GF(2)上的本原多在實際應用中，可以用上述最基本的鐘控序列生成器構造復雜的模型。典型的鐘控序列有Jennings復合序列［15］、?！呱善?stop-and-gogenerator)［16］、Gunther生成器［17］及縮減序列［18］。以下僅對?！呱善髯鲆缓喴榻B，其它序列的具體構造請參考有關文獻。

定義4-12設GF(2)上的兩個n級m序列為a∞和b∞，它們的極小多項式分別為f(x)和g(x)，定義整數函數G(t)為(4-9)在實際應用中，可以用上述最基本的鐘控序列生成器構造復雜的令

，則序列u∞=u0u1u2…稱為?！咝蛄?。所謂?！咝蛄惺侵赣尚蛄衋∞控制b∞的?；蜃叨傻男蛄?，實際上是由a∞控制的對b∞的不等距采樣序列。其周期和線性復雜度由下述定理給出。令，則序列u∞=u0u1u2…稱為?！?/p>

定理4-22?！咝蛄衭∞的極小多項式為，周期為(2n－1)2，線性復雜度為n(2n－1)。停—走序列的概念可以進一步推廣到兩個級數不同m序列或者多個同級m序列的情形。定理4-23設a∞為GF(2)上的n級m序列，b∞為GF(2)上的r級m序列，函數G(t)如式(4-9)中定義，序列u∞=u0u1u2…定義為ut=bG(t)

t=0，1，2，…則u∞的線性復雜度為n(2r－1)。定理4-22?！咝蛄衭∞的極小多項式為，

定理4-24設

為GF(2)上的k個n級m序列，如果將這k個序列用?！呱善鬟M行級聯，即用

控制得到序列控制

得到序列控制

得到序列，則的線性復雜度不小于n(2n－1)k－1。?！咝蛄械木€性復雜度有著良好的穩(wěn)定性，這由以下定理給出。定理4-24設為GF(2)上的k個

定理4-25［1］設?！咝蛄衭∞如定義4-12所述，則其重量復雜度滿足以下關系：

(1)WC1(u∞)≥(2n－1)(2n－n－1)；

(2)WC2(u∞)≥(2n－1)(2n－N－n－1)，其中N是2n－1的最大真因子。定理4-25［1］設停—走序列u∞如定義4-12所述鐘控序列是對線性序列進行改造，提高序列線性復雜度的一種有效方法。與多路復合序列及前饋序列相比，通常認為鐘控序列有以下兩個優(yōu)越性［2］：(1)鐘控序列的線性復雜度“指數地依賴于”驅動LFSR的級數，而不像前饋序列和多路復合序列那樣，“線性地依賴于”驅動LFSR的級數，從而穩(wěn)定性較強；(2)鐘控序列生成器易于控制其線性復雜度。但鐘控序列也有不足之處，除線性復雜度之外，有些鐘控序列其它方面的偽隨機性能常常不理想，比如有過多的長游程。鐘控序列是對線性序列進行改造，提高序列線性復雜度的一種有4.3序列密碼的安全性為了使密鑰序列有較強的隨機性，從而使密碼體制足夠安全，人們對序列密碼中的密鑰生成器提出了如下一些基本要求：(1)初始密鑰K的變化量足夠大，一般應在2128種以上；(2)密鑰序列k∞的周期一般不小于255；(3)k∞具有均勻的游程分布；(4)k∞不能由一個低級(比如，小于106級)的LFSR產生，也不能與由低級LFSR產生的序列具有較高相似度；(5)利用統(tǒng)計方法由k∞提取關于密鑰生成器的結構或初始密鑰K的信息在計算上是不可行的；(6)具有混亂性，即k∞的每一位與K的大多數比特有關；4.3序列密碼的安全性(7)具有擴散性，即改變K中任何一位，均會引起k∞的較大改變。目前對序列密碼的攻擊方法主要有分別征服攻擊、線性攻擊、最佳仿射攻擊、線性伴隨式攻擊、線性一致性攻擊、快速相關攻擊、線性時序邏輯逼近、熵漏分析等多種有效的分析方法。

(7)具有擴散性，即改變K中任何一位，均會引起k∞的較線性攻擊是一種已知明文攻擊，主要針對線性復雜度較低的序列，用B-M算法破解密鑰序列。分別征服攻擊(DivideandConquer，DC攻擊)［19］利用非線性組合序列對驅動序列的依賴性進行攻擊。最佳仿射攻擊(BestAffineAttack，BAA攻擊)［1］利用序列線性復雜度的不穩(wěn)定性，當一個高線性復雜度的序列與一個低線性復雜度的序列“距離很近”時，BAA攻擊有效。以下主要討論BAA攻擊和DC攻擊。在進行BAA攻擊或DC攻擊時，序列密碼體制的模型如圖4-11所示。線性攻擊是一種已知明文攻擊，主要針對線性復雜度較低的序列圖4-11序列密碼體制模型圖4-11序列密碼體制模型有限域GF(q)上的s元非線性布爾函數f(x)具有如下的一般形式：

(4-10)其中，a0，ai，aij，…∈GF(q)。當函數f(x)的輸入序列均為m序列時，關于輸出密鑰序列的復雜度有如下結論。有限域GF(q)上的s元非線性布爾函數f(x)具有如下的

定理4-26設GF(q)上s個最大長度序列由式(4-10)中的函數f(x)進行組合，如果產生這s個最大長度序列的LFSR的極小多項式次數Li(i=1，…，s)互不相同且均大于2，則由f(x)產生的序列有最大線性復雜度f*(L1，L2，…，Ls)。其中，這里的計算在實數域中進行。定理4-26設GF(q)上s個最大長度序列由式(4-4.3.1布爾函數的最佳仿射逼近與BAA攻擊

定義4-13設f(x)：GF(2)n→GF(2)，如果存在仿射函數wx+l(w∈GF(2)n，l∈GF(2))，使得取最大值，則稱wx+l是f(x)的一個最佳仿射逼近。布爾函數的最佳仿射逼近可以用Walsh譜值來研究，以下的結論與實例來自參考文獻［1］。用第二種Walsh譜值描述的最佳逼近定理如下。4.3.1布爾函數的最佳仿射逼近與BAA攻擊

引理4-2令Pf(wx+l)為函數f(x)與仿射函數wx+l相等的概率，則有(4-11)(4-12)引理4-2令Pf(wx+l)為函數f(x)與仿射函數證明:由第二種Walsh譜的定義，有由此即得式(4-11)，再由定理3-2可得式(4-12)。由引理4-2易證得如下的最佳逼近定理。證明:由第二種Walsh譜的定義，有

定理4-27設f(x)：GF(2)n→GF(2)，a=max{|S〈f〉(w)|：w∈GF(2)n}=|S〈f〉(w0)|則有：(1)如果S〈f〉(w0)≥0，則w0x為f(x)的最佳仿射逼近，且與f(x)相等的概率為；(2)如果S〈f〉(w0)<0，則1+w0x為f(x)的最佳仿射逼近，且與f(x)相等的概率為。Rueppel首先給出了DES中S盒的最佳仿射逼近分析，但未對該方法在密碼學中的應用給予進一步的分析。丁存生與單煒娟于1987年將線性逼近與代數方法結合起來設計了針對兩類流密碼的BAA攻擊方法，并由此提出了序列密碼的穩(wěn)定性問題。定理4-27設f(x)：GF(2)n→GF(2)，BAA攻擊是一種已知明文攻擊方法，其目的不是恢復密鑰生成器的初始密鑰，而是利用已知信息構造一個新的密鑰生成器來近似替代原密鑰序列生成器，從而完成對任意密文的解密。假定攻擊者所掌握的信息為：(1)非線性組合函數f(x)；(2)所有LFSR的級數ri(i=1，…，s)；(3)明文編碼及語言的統(tǒng)計特性；(4)M比特密鑰序列k1k2…kM，其中M>2(r1+…+rs)。BAA攻擊是一種已知明文攻擊方法，其目的不是恢復密鑰生成BAA攻擊的主要思想是利用已知信息構造一個新的級數不超過的LFSR，以它來近似地替代原密鑰序列生成器；構造方法則是用一個低復雜度的線性序列去逼近高復雜度的非線性序列。由定理4-27知，如果求出w=(w1，w2，…，wn)∈GF(2)n,使譜值的絕對值|S〈f〉(w)|達到最大，且(1≤t≤n)，而其它wj=0，則f(x)的最佳仿射逼近為這里當S〈f〉(w)≥0時，l=0，否則l=1。從而得到序列:BAA攻擊的主要思想是利用已知信息構造一個新的級在LFSR的輸出序列的所有線性組合序列中，(k′)∞與密鑰序列k∞的相關性最好，且兩者相等的概率為，這里a為最大譜值|S〈f〉(w)|。

例4-1設圖4-11中的s=5，r1=3，r2=4，r3=5，r4=6，r5=7，非線性組合函數f(x)的真值表為f=(00110011110011000011001111001100)，再設已知如下51bit的密鑰序列段：k51=100110000110100010000100010011010101011011001011001在LFSR的輸出序列的所有線性組合序列中，(k′)∞與密如果每個LFSR的聯結多項式均為本原多項式，則由定理4-26，有L(k∞)=6677，計算出最大譜值a=15/16，最大譜值點為(01010)，最佳仿射逼近函數為x2+x4，這樣，就有r=4+6=10。從而用B-M算法可以求出第10個2r截段后的每個截段的(g(x)，L)為(1+x2+x4+x5+x6+x7+x10，10)因而基本上可以認為這個LFSR即為產生密鑰序列的LFSR。如果進一步的檢驗正確的話，就構造出了一個級數為10的LFSR，使得它與原密鑰生成器的符合率為31/32。這時雖然原密鑰流序列的線性復雜度為6677，但可以用一個復雜度為10的序列去逼近它，并且這種逼近與原序列的符合率是相當高(31/32)的。如果每個LFSR的聯結多項式均為本原多項式，則由定理4-264.3.2DC攻擊“DivideandConquer”是一種圖論算法，意為將一個待求解問題分解成許多子問題，然后對每個子問題求解，最后再綜合。Siegenthler于1985年將這種方法用于分析二元加法非線性組合序列密碼［20］，針對圖4-11中所示的密碼體制設計了一種分別征服攻擊方法，該方法大大地降低了尋找密鑰所需的試驗次數。4.3.2DC攻擊DC攻擊是一種惟密文攻擊，其基本思路是：根據非線性組合器的輸出序列k∞與組合函數f(x)的每個輸入序列(a(i))∞之間的相關性，用統(tǒng)計方法恢復各個LFSR的初始狀態(tài)和反饋函數。在圖4-11的密碼體制中，如果令GF(2)上所有次數為ri的本原多項式數量為Ri，則第i個LFSR的未知參數有個，因此，總的密鑰量為。而Siegenthler提出的DC攻擊方法將實施窮盡攻擊時所需的次減少到了次。

DC攻擊是一種惟密文攻擊，其基本思路是：根據非線性組合器假設攻擊者掌握了以下信息：(1)足夠長的密文序列；(2)非線性組合函數f(x)；(3)所有LFSR的級數ri(i=1，…，s)；(4)語言編碼及語言統(tǒng)計特性。假設攻擊者掌握了以下信息：在進行DC攻擊時，首先為密碼體制建立如下的統(tǒng)計模型。假設函數f(x)的輸入是由一些相互獨立同分布的隨機變量所產生的，這些隨機變量的分布函數為pA，且對所有i和n，有，即為均勻分布。函數f(x)生成一些獨立同分布的隨機變量

,其概率分布為pK，這里P(Kn=0)=P(Kn=1)且P(Kn=)=qj。再假定明文序列x∞由二元無記憶信源產生，且P(Xn=0)=P0。在進行DC攻擊時，首先為密碼體制建立如下的統(tǒng)計模型。由于密文Yn與Kn和Xn有關，而Kn又與有關，因而Yn間接地與有關，所以Yn中必定含有LFSRi的信息。DC攻擊通過計算LFSRi的輸出序列與密文序列之間的相關度α或符合率pe來提取子密鑰的信息。由于密文Yn與Kn和Xn有關，而Kn又與有關，因而Y

定義4-14兩個長度為N的序列Y1Y2…YN與之間的相關度定義為這里，與各個統(tǒng)計獨立且同分布，其概率分布為pA，其中。序列Y1Y2…YN與之間的符合率pe定義為于是。定義4-14兩個長度為N的序列Y1Y2…YN與由定義知，pe越大說明序列Y1Y2…YN與之間的符合率越大，從而密文序列中含有關于LFSRi的子密鑰的信息量就越大。DC攻擊中還包括假設檢驗、錯誤決策分析等過程，這里不一一詳述，具體可參考參考文獻［1］及［20］。Siegenthler指出，當LFSR的級數足夠大時，DC攻擊由于計算量太大而無法實現［20］。同時由于目前沒有有效的方法來確定所有n次本原多項式，因而DC攻擊只能應用于驅動LFSR的級數較小的序列密碼。由定義知，pe越大說明序列Y1Y2…YN與4.4序列密碼的應用序列密碼是一種方便快捷的加密方法，許多序列密碼在現實中得到了廣泛應用，如RC4、A5和SNOW。本節(jié)將對這些密碼體制進行介紹。4.4.1RC4密碼RC4加密算法是RonRivest于1987年設計的密鑰長度可變的序列密碼算法。該算法在最初的7年中為專利，算法的細節(jié)必須在簽署保密協議后才能得到。后來RC4通過互聯網流傳到全世界并得到了關注和研究，隨后被廣泛地應用于商業(yè)加密中。4.4序列密碼的應用與前面介紹的基于LFSR的隨機數產生器不同，RC4的密鑰序列使用了稱為Table-shuffling的方法產生，即利用一張很大的表生成隨機密鑰，而這張表可以在自身的控制下變化。RC4主要有以下特征：(1)可變