應用密碼學：5-序列密碼

1、第5章 序 列 密 碼51 序列密碼的基本原理5.2 線性反饋移位寄存器5.3 m 序列5.4 BM算法5. 5 線性移位寄存器的非線性組合古典密碼：替代和換位 （置換、重合指數）分組密碼：DES、AES （字節(jié)運算、字運算）序列密碼：LFSR、m序列、B-M算法公鑰密碼：RSA加密大數分解 Elgamal加密離散對數 （模逆、模冪算法）數字簽名和hash函數： RSA簽名、Elgamal簽名 hash函數：壓縮、單向、無碰撞密碼協議：密鑰管理、身份認證對稱密碼認證本課程的主要內容5.1 序列密碼的基本原理序列密碼將明文編碼為比特串:加密為：如果每隔固定的r個字符或比特，以后密鑰重復使用，則為

2、周期序列密碼；密鑰不重復的為非周期序列密碼。同時產生與明文相同長度的密鑰流:同步方式（synchronous）；自同步方式（self-synchronous） 解密為：實際應用中不可能存儲大量的同步序列密碼的密鑰流，因此加密解密裝置均需包含密鑰生成器(KG)，其中密鑰流的初始狀態(tài)由短的種子密鑰I觸發(fā)。 序列密碼方案的發(fā)展是致力于模擬一次一密。但真正隨機的密鑰不可能產生兩次相同的序列，因此序列密碼使用偽隨機（Pseudo Random）或偽噪聲(Pseudo Noise)序列。 設計安全的密鑰生成器是一個重要的研究課題。序列密碼主要任務是設計安全的偽隨機序列產生器。對KG的基本要求：（1）密鑰量

3、大；（2）極大周期；（3）理想分布；（4）抗線性逼近；（5）推測K是計算不可行的；（6）混亂性。密文和明文的統計關系復雜化；（7）擴散性。每位明文的影響盡可能散布到較多密文中， 以便隱蔽明文的統計特性。分組密碼與序列密碼的比較：（1）序列密碼：處理速度快，實時性好，適用于軍事、 外交等保密系統。但是適應性差，需要密鑰同步。（2）分組密碼：不需密鑰同步，較強的適應性，適宜 作為加密標準。但是加密速度慢，錯誤易擴散和 傳播。(但比公鑰密碼快得多)5.2 線性反饋移位寄存器一、反饋移位寄存器序列密碼通過反饋移位寄存器產生密鑰。移位寄存器可以通過一個反饋循環(huán)，從前面n項計算下一項，成為一個偽隨機序列發(fā)

4、生器。KG！反饋函數一個 q 元域 GF(q)上的 n 階反饋移位寄存器（FSR：Feedback Shift Register），由n個寄存器和一個反饋函數構成。最右端的寄存器為第1級寄存器，最左端的寄存器為第n級寄存器，反饋函數在任意時刻，第1級至第n級寄存器的內容所形成的中的向量稱為反饋移位寄存器的一個狀態(tài)。開始為初始狀態(tài)。（注意順序是從輸出開始?。?GF(2)或F2反饋移位寄存器序列： 反饋寄存器的狀態(tài)序列 ：例6.1：初始狀態(tài)：s0101輸出序列：10111011.輸出序列為第一個字母完全狀態(tài)圖：二、線性移位寄存器 （LFSR：Linear Feedback Shift Regist

5、er） 反饋函數為線性函數。否則為非線性反饋移位寄存器。我們總要求第一級的系數不為0，稱之為非退化的。如果第一級的系數為0，則不是n階反饋了，稱為退化的。例6.2(P103)結構常數反饋函遞推式例：反饋函數為 初始狀態(tài): (1000)，輸出序列: (1000110)，周期為7初始狀態(tài):(0010)，輸出序列:(0010111)，周期為7 初始狀態(tài):(0110)，輸出序列:(0110100)，周期為7 第三個初態(tài)！第一個初態(tài)！第二個初態(tài)！反饋函數為 ：初始狀態(tài):(1000)，輸出序列:(100010011010111)， 周期為 初始狀態(tài):(0110)，輸出序列:(011010111100010

6、)， 周期為 的序列稱為n 階 m序列。第二個初態(tài)！第一個初態(tài)！只要進入，就得循環(huán)！由例子可得出以下結論：（1）n-LFSR的結構由其結構常數唯一確定；（2）n-LFSR的結構常數與反饋函數互相唯一確定；（3）n-LFSR序列由其結構常數和初態(tài)唯一確定； （4）一個n-LFSR可以產生 個不同序列。 （不考慮平移等價的話。） 平移等價：一個序列向左移若干位后，和另一 序列相同。 （5） 一個n-LFSR的序列的最大周期是關鍵問題：如何產生m序列？三、線性移位寄存器的表示LFSR的多項式表示：f(x) 稱為線性移位寄存器的聯系多項式或生成多項式。x為寄存器a是它的取值（這里的x只是形式變量 ，而

7、不是上面寄存器的標記?。┓答伜瘮德撓刀囗検铰撓刀囗検胶头答伜瘮导盃顟B(tài)的對應關系：例：一個5-LFSR的聯系多項式為 LFSR！例：（習題6.2）一個4-LFSR的聯接多項式為 初始狀態(tài)為1101。求輸出序列及其周期。解：反饋值放在后面！聯系多項式為本原多項式時，產生m序列.LFSR的矩陣表示： 設在t時刻的狀態(tài)為 ：生成矩陣：狀態(tài)轉換可以用生成矩陣實現，新狀態(tài)等于前一狀態(tài)乘以生成矩陣。t1時刻的狀態(tài) ：所以：結構常數不變！序列的2種表示方式：（1）序列： （2）形式冪級數：a(x)稱為序列的生成函數。 當序列 的周期為 p 時四、線性移位寄存器的周期性 五. 線性移位寄存器的序列空間 六.線性

8、移位寄存器序列的極小多項式 五、對偶移位寄存器（DSR）DSR是另一類線性反饋寄存器，它的模2加出現在移位寄存器之間，寄存器第一級的內容（輸出）直接反饋到第n級并同時反饋到中間某些級。 LFSRDSR如果一般nDSR的狀態(tài)轉換為 例：4DSRDSR的聯系多項式為 （與 LFSR 有相同的聯系多項式。C01表示反饋 ） DSR輸出序列也有三種表示方法，即序列表示法、形式冪級數表示法和有理表示法。序列 由f(x)對偶生成 ： 由以f(x)為聯系多項式的 n-DSR產生。 定理：序列 由f(x)對偶生成、且初態(tài)為 的充要條件是證明：設初態(tài)為省略了變量x例：（1）初態(tài)為（1,0,1,1,0,0,1,0

9、,1），求a(x). （2）已知某序列的有理表示為：求初態(tài)。初態(tài)為（0,0,0,0,1,1） 設序列 的有理表示為 求（1）給出 的LFSR，并指明初態(tài)； （2）給出 的DSR并指明初態(tài)。例：解：（1）LFSR的結構常數為（0,1,0,1） 初態(tài)為（0,1,0,0）,（或消最低項法）（2）DSR的結構常數為(0,1,0,1)，結構圖即 所以DSR和LFSR是等效的，但DSR更利于編程實現。 初態(tài)就是分子多項式的系數，所以初態(tài)為（0,1,0,1） 狀態(tài)序列為0101，101000001010， 010001010001，001000000010。 010000000100，10000000100

10、0， 000001010101。 一、m序列的構造如果n階線性移位寄存器的輸出序列周期為 則該序列稱為GF(q)上的 n 級 m 序列。 定理：若 n 次多項式f(x)是序列 的聯系多項式， 且 ，則 的周期 p|m。 證明：設：由已知可得：a(x)=g(x)/ f(x) 5.3 m 序列就是m級LFSR純左循環(huán)移位寄存器，也即結構常數只有最右邊的第一級為1，也就是將輸出直接反饋到第m級， 所以序列的周期為m， 設：所以得出 r ( p ) 也是周期，與p是周期矛盾，所以r =0所以 p|m定理：設是 周期為p的任意0，1序列，則 的有理表示 為 證明： 因為現在f(x)中只有 所以定理：設f

11、(x)是n-LFSR的聯接多形式，序列 f(x)的階（周期）： 對于任意次數大于等于1（ ）、常數項 為1的多項式f(x)，滿足 的最小正整數 r， 記為p(f(x)。 設f(x)的次數為n，p為所產生序列的周期，n次本原多項式：階為 的n次不可約多項式。 是 n 級 m 序列的必要條件是f(x)為不可約多項式。 由前面定理，若則 p | r，現在 r 最小，因此有 p = r。也就是 f(x)的階就是所產生序列的周期。如果要求序列周期最大，也就是f(x)的階為定理：設f(x)為常數項為1的n次多項式，非全零序列 ，則 是 n 級 m序列的充要條件 是 f(x) 是 n 次本原多項式。Prim

12、itive polynomial 定理：n次本原多項式的個數為 結論：求m序列就是求本原多項式，而求本原多項式 就是求 的 n次既約多項式的因式分解。1、不論什么表示，關鍵點是狀態(tài)遞歸關系，也就是 2、 是產生周期為p序列的p階寄存 器的聯系多項式。 注意：結構決定序列！二、m 序列的偽隨機性1、隨機性的三個公設形如 的子序列段稱為一個長為k的1游程；形如 的子序列段稱為一個長為k的0游程。 (1) 分布特性：在一個周期內，0與1的數目至多相差為1； (2) 游程特性：在一個周期內，相同長度的0游程與1游程 的數目基本平衡，且合起來大約占游程總數的1/2i； (3) 相關特性：周期性的自相關函

13、數為一個常數。 （自相關函數 ）2、m 序列的偽隨機性是GF(2)上的一個n級m序列，則 定理：1、在 的一個周期中，0和1的出現次數分別為 2、在 的一個周期中，游程總數為 對任意的 ，長為 i 的0游程和1游程都有 個，長為 n-1的0游程，長為n的1游程各有一個； 3、 的自相關函數為 對應著狀態(tài)圈證明過程見書!（將游程數目和長度， 轉化為狀態(tài)的數目） 將一個周期首尾相接，構成序列圈序列圈中，長為i 的1 游程總會體現為：存在以下形式的狀態(tài)共有有什么樣的游程對應著有什么樣的狀態(tài)！狀態(tài)圈上，下一個n位對應著下一個狀態(tài)。例：任意 5 級m序列的周期環(huán)上，有 個0，有16個1。 1111100

14、110100100001010111011000，是由本原多項式 產生，所以是5 級m序列。其周期中，15個0，16個1 。游程總數：長為1的游程：長為2的游程：長為3的游程：長為4的0游程一個，長為5的1游程一個。例：設序列的有理表示為 周期為（100100011110101），求序列。結構常數為1001 初態(tài)為1001（x4,x3,x2,x1），反饋值為x4+x1， 輸出序列依次為 100100011110101 100100011110101. 判斷m序列的偽隨機性： 一個周期中：8個1，7個0；41游程有一個， 30游程有一個， 20游程和21游程各一個； 11和10游程各為2；總游程

15、個數為 8。5.4 BM算法一、BM 算法對于 n 階線性移位寄存器，已知2n序列段 ，通過解方程組，可以求得對應的結構常數結構常數、初態(tài)nLFSR序列綜合分析（1）置初值：（2）設都已求出BM 算法：不需任何前提，求出序列段的線性綜合解：規(guī)定：(a) f(x)=1表示0階線性移位寄存器的聯系多項式， 長度為n的全零序列由0階線性移位寄存器產生。 (b) 可能是退化的。且記計算對于 ，重復第二步和第三步N次，即可求出若（a）如果（b）否則，存在（3）若 ，取例：輸入：S8=10101111輸出：上題的解釋：例：（書中例6. 4）輸入：S10=0001101111二、序列的線性復雜度 設是 一個

16、長度為n的序列，能產生該序列并且階數最小的線性反饋移位寄存器的級數，稱為 的線性復雜度，記為 。約定全零序列的線性復雜度為0。 顯然，利用BM算法，可以求出序列的線性復雜度。較高的線性復雜度是密鑰序列的一個必要的安全條件。根據 m 序列的定義，n階m序列的線性復雜度就是n。如果知道一個n階m序列的2n位，就可以利用BM算法求出這個m序列的本原多項式（書中為極小多項式）。M序列：序列周期達到最大值 -1的n-NLFSR 。5.5 線性移位寄存器的非線性組合解決線性反饋的不安全性的兩種方式： 非線性反饋：大M序列 線性反饋的非線性組合布爾函數一、非線性反饋移位寄存器M序列是最大長度的nNLFSR序列；其對應的反饋函數稱為M序列反饋函數.線性的： 種； 非線性的：例：由 4 次本原多項式構造 4 級M序列反饋函數。 0變?yōu)? 1變?yōu)?（1x）二、線性反饋的非線性組合對一個或多個線性移位寄存器進行非線性組合可獲得安全性能良好的非線性序列。有兩類： 非線性濾波生成器 非線性組合生成器 1.(1)若 是一個29級m序列，則 = ， = ；作業(yè): 6. 1、 6