第二章序列密碼

2．1概述

2．2線性反饋移位寄存器

2．3m序列及其性質2．4對偶移位寄存器2．5

B-M算法2．6非線性組合與算法舉例

2.1概述序列密碼將明文編碼為比特串:

同時產生與明文相同長度的密鑰流:

或者GF(p)效仿一次一密加密方式：

（1）密鑰和明文長度相同；

（2）每次加密采用不同的密鑰；

（3）密鑰是隨機的。古典密碼中的

Vernam密碼（1917年）：

但密鑰如何實現？偽隨機數發生器：產生性能接近隨機的二進制序列。種子密鑰序列密碼主要任務：設計安全的偽隨機密鑰產生器。對KG（KeyGenerator）的基本要求：（1）密鑰量大；（2）極大周期；（3）理想分布；（4）非線性度大；（5）推測K是計算不可行的。KG非線性移位寄存器（NFSR：Non-linearFeedbackShiftRegister）

－－－－M序列（周期最大）線性反饋移位寄存器（LFSR：Linear

FeedbackShiftRegister）

－－－－m序列（周期最大）線性移位寄存器的非線性組合（實用的）序列密碼與分組密碼的比較：（1）序列密碼：

處理速度快，實時性好；

適用于軍事、外交等保密系統。

但是適應性差，需要密鑰同步。（2）分組密碼：

不需密鑰同步，較強的適應性；適宜作為加密標準。

但是加密速度稍慢，錯誤易擴散和傳播。

(但比公鑰密碼快得多，軟件上約100倍。)2．2線性反饋移位寄存器1.反饋移位寄存器KG！

例題-1：初始狀態：s0＝101f10110111111011011011移位寄存器的一個狀態（開始時為初始狀態）：反饋函數

反饋寄存器的狀態序列：必然是周期的！因為狀態有限，進入一個相同狀態后則重復。當觸發脈沖到來時，寄存器狀態移位更新為一個新狀態。

例題-1的輸出序列：10111011…..完整的狀態圖：如何使狀態都在一個圈里？這樣周期最大。2.線性移位寄存器-LFSR(Fibonacci-LFSRs)反饋函數為線性函數（否則為非線性反饋移位寄存器）

稱為結構常數。

結構常數反序是為了將來有理表示方便（不必求互反多項式）。例題-2：

這是一個4階線性反饋移位寄存器：4-LFSR。

布爾函數！f110001000011000110001101111010110100001000

初始狀態記為：

最重要的關系！結構常數不動

可以劃出相應的狀態轉移圖。

圖形和公式是對應的

上例中：反饋函數為,

初始狀態:(1000)，輸出序列:(1000110)

，周期為7初始狀態:(0010)，輸出序列:(0010111)

，周期為7

初始狀態:(0110)，輸出序列:(0110100)

，周期為7

第三個初態！第一個初態！第二個初態！

反饋函數為：初始狀態:(1000)，輸出序列:(100010011010111)

，周期為

初始狀態:(0110)，輸出序列:(011010111100010)

，周期為

的序列稱為n階m序列。另一：f110001000010000100001001110011000110001101111010f111010110101001011110111001111111110111100111000110001續前：第二個初態！第一個初態！只要進入，就得循環！

結論：（1）n-LFSR的結構由其結構常數唯一確定；（2）n-LFSR的結構常數與反饋函數互相唯一確定；（3）n-LFSR序列由其結構常數和初態唯一確定；（4）一個n-LFSR可以產生個不同序列；（5）一個n-LFSR的序列的最大周期是。關鍵問題：如何產生m序列？LFSR的聯接多項式為本原多項式。f(x)稱為線性移位寄存器的聯接多項式或生成多項式。

3.LFSR的有理表示

a(x)稱為序列的形式冪級數或生成函數。--S(f(x))LFSR的有理表示：其中g(x)是次數小于n的多項式：a(x):表示輸出序列f(x)：表示結構常數g(x)：與初態、結構常數相關

序列空間定理-1：n-LFSR有理表示中g(x)的次數小于n。證明：因為迭代關系：

LFSR:g(x)的系數和結構常數與初態都有關系。DSR

：g(x)的系數就是初態。（后面講）

當初結構常數序號與寄存器序號反向，就是為了此處。

另一簡單方法求g(x)：

消最低項的長除法可求a(x)：2.3、m序列及其性質1.如何構造m序列例題-4：

設的有理表示為，求其序列表示。解：通過消最低項的多項式除法，得到：

升冪排列消最低項另一種方法：定理-2：周期為p的序列的（非最簡）有理表示為：證明：

所以：分子多項式的系數（含常數項）為一個周期；分母二項式的次數為周期。

例題-5：求產生序列（100111）∞的最短的LFSR。

多項式的輾轉相除法階數最少！最簡有理表示

任何一個（周期）序列都可以表示為：

此即研究多項式形式的原因

定理-3：當f(x)為本原多項式，產生的序列為m序列。

nFeedbackpolynomialPeriod23374155316637127不止一個！是一個本原多項式。初態為(10101)，求序列的表示。例題-6：兩種基本方法：（1）畫出結構圖，進行迭代，得到狀態圖。（2）求出有理表示，進行長除法，得到一個周期。（1010111011000111110011010010000）∞設一個序列的聯接多項式為

隨機性如何？m序列的取樣:設

是Fq上的一個周期序列s

是一個正整數，令：稱為序列的s采樣。定理-4：若是周期為p的m序列，則

2.m序列的偽隨機性形如的子序列段稱為一個長為k的1游程；形如的子序列段稱為一個長為k的0游程。

（1）分布特性：（2）相關特性：隨機性的三個特性：s是序列的長度

（3）游程特性：0游程

證明：將游程數目轉化為狀態的數目。

狀態最終都會出現在序列中！一個周期序列圈m序列特點：每個非零狀態都出現，且只

出現一次！狀態都在序列中！

序列圈中，長為i的1游程總會體現為：存在以下形式的狀態(一一對應！)在序列圈上數游程個數，都是從011…10開始。即使在******中也有，以后也會被數到，沒有遺漏。輸出序列的圈

看序列圖上的狀態，游程最終要顯示在序列圈上。輸出序列的圈所以當游程個數為現在只剩下的游程個數：n長的1游程有1個，

因為在狀態圈中，有一個全1狀態：111….1；沒有n長的0游程，因為沒有全0狀態；n-1長的0游程有1個；所以共有游程：不可能有n+1的1游程：不會有n-1長的1游程：因為不可能有兩個全1狀態，且相連；因為以下三個狀態是相連的：（否則全1狀態不會出現。）且每個狀態在狀態圈中，只出現一次；所以011..11與11..110不會連著出現（連著才會出現n-1長的1游程）。m序列特點：一個周期內,每個非零狀態都出現，且只

出現一次！（3）相關系數的證明:

任意5級m序列的周期環上，有個0，有16個1。

＝1111100110’1001000010’1011101100’0……，是由本原多項式產生，所以是5級m序列。其周期中，15個0，16個1。游程總數：長為1的1/0游程：長為2的1/0游程：長為3的1/0游程：長為4的0游程一個，長為5的1游程一個。算游程時首尾相接例題-7：

LFSR（DSR:DualShiftRegisters）DSR2．4對偶移位寄存器LFSR：也稱FibonacciLFSRsDSR：也稱GaloisLFSRs

DSR的特點：DSR也是LFSR，這樣稱呼只是為了區別開1.DSR的狀態轉換（或稱迭代過程）

例題-8：4－DSR

序列為：（1101000）

開始循環11000111010011111110000010001000100狀態不是每位都輸出初態為（1110）時，序列為（1000110）

相同的聯接多項式4-LFSR

但是：如果上例的LFSR的初態是1101，

輸出序列為：（1101000）

，

與初態為1000的DSR輸出序列相同。因此相同的結構常數，DSR和LFSR可產生相同序列。2.DSR的有理表示a(x):表示輸出序列f(x)：表示結構常數g(x)：表示初態！DSR也具有有理表示：一方面：利用DSR的遞推公式所以輸出序列為

定理-6：DSR序列的有理表示中：證明：其系數就是DSR的初態：另一方面：利用消最低項方法有理表示等式的兩邊相同，得證。

由此可得到DSR的設計思路

例題-9：解：（1）LFSR的結構常數為（0,1,0,1）

初態為（0,1,0,0）。（2）DSR的結構常數為(0,1,0,1)，結構圖即

或者：所以DSR和LFSR是等效的。

總結：4.當鏈接多項式f(x)為本原多項式時，產生m序列。

2.對于LFSR，g(x)的系數由初態和結構常數確定；

對于DSR，g(x)的系數即為初態；產生同一序列（具有相同有理表示），LFSR和DSR

的初態不同；另外：有理表示還可以擴展為假分式的情況，例如：

對應的LFSR的圖示為：(退化的7-LFSR)

非周期部分的位數有3位，對應的退化寄存器個數為3。線性復雜度：生成序列所需最小的LFSR寄存器個數。本例中，序列的線性復雜度=4+3。2.5B-M算法線性反饋移位寄存器雖然易于實現，但是不安全的，如果知道兩個周期，就能通過B-M算法解出生成多項式。已知階數B-M算法不需任何前提，求出序列段的線性綜合解：是一種迭代算法：階數對于n階線性移位寄存器，已知2n序列段，通過解方程組，可以求得對應的結構常數還可用于循環碼譯碼等。還有Berlekamp算法：用于分解多項式。B-M（Berlekamp–Massey）算法：

迭代型求解序列生成多項式的算法。（且不必事先知道寄存器階數）未知階數規定：f(x)=1表示0階線性移位寄存器的聯接多項式，（長度為n的全零序列由0階線性移位寄存器產生。）

且記計算對于，重復第二步和第三步N次，即可求出若（a）如果（b）否則，存在（3）若，取逐次試驗聯接多項式的方法！輸出：<1+x3+x4,4>同一行中最后才算dn！d=1才算m！寫在fn+1的上一行例10：輸入S8=10101111

當前結構常數：當前狀態

逐一試驗上題的解釋：（上述過程熟練以后，僅用表格形式做即可！）

例題-11：輸入：S10=0001101111

注意：