現(xiàn)代密碼學(xué)與應(yīng)用-序列密碼

1、現(xiàn)代密碼學(xué)與應(yīng)用 序列密碼主講人：余艷瑋E-mail: 2008-9-211大 綱序列密碼的基本概念密鑰序列生成器線性反饋移位寄存器(LFSR)RC42008-9-212參考書籍Handbook of Applied Cryptography: Chapter 6Applied Cryptography: Protocols, algorithms, and source code in C：Chapter 16, 172008-9-213一、序列密碼的基本概念2008-9-214起源一次一密無條件安全：在理論上是不可破譯的但：要求密鑰與明文具有相同長度、且不可重復(fù)使用，增加了密鑰分配與管理的

2、困難對策：用一個較小的密鑰來偽隨機(jī)地生成密鑰流。2008-9-215人們試圖以序列密碼方式仿效“一次一密”密碼序列密碼的理論已經(jīng)比較成熟，而且具有工程實現(xiàn)容易、效率高等特點采用一個短的種子密鑰來控制某種算法產(chǎn)生出長的密鑰序列，供加、解密使用，而短的種子密鑰的存儲、分配都較容易2008-9-216序列密碼 vs. 分組密碼2008-9-217序列密碼的基本原理利用種子密鑰k和初始狀態(tài)0產(chǎn)生一個密鑰序列z=z0z1，并使用如下規(guī)則對明文序列m=m0m1m2加密，得到密文序列c：c=c0c1c2=Ez0(m0)Ez1(m1)Ez2(m2)。狀態(tài)i：位序列或或或2008-9-218序列密碼的基本原理序

3、列密碼的關(guān)鍵就是產(chǎn)生密鑰序列的算法密鑰序列產(chǎn)生算法應(yīng)能產(chǎn)生的密鑰序列z：只能是偽隨機(jī)序列具有良好的隨機(jī)性和不可預(yù)測性密鑰序列產(chǎn)生算法都采用帶存儲的時序算法，其理論模型為有限自動機(jī)，其實現(xiàn)電路為時序電路序列密碼實際應(yīng)用中的關(guān)鍵技術(shù)：如何保持通信雙方的精確同步？ (zi 與ci一一對應(yīng))2008-9-219序列密碼的分類同步序列密碼同步序列密碼密鑰序列的生成獨立于明文和密文2008-9-21102008-9-2111同步序列密碼通信模型2008-9-2112同步序列密碼的特點在保密通信過程中，通信的雙方必須保持精確的同步對于同步序列密碼，只要通信雙方的密鑰序列產(chǎn)生器具有相同的種子密鑰和相同的初始狀

4、態(tài)，就能產(chǎn)生相同的密鑰序列。對失步的敏感性收方的解密將一直錯誤，直到重新同步為止容易檢測插入、刪除、重播等主動攻擊無錯誤傳播當(dāng)通信中某些密文字符產(chǎn)生了錯誤（如0變成1，或1變成0），只影響相應(yīng)字符的解密，不影響其它字符2008-9-2113序列密碼的分類自同步序列密碼自同步序列密碼密鑰序列由種子密鑰和固定個數(shù)的以前的密文字符的函數(shù)所生成2008-9-21142008-9-2115自同步序列密碼通信模型2008-9-2116自同步序列密碼的特點自同步有限的錯誤傳播主動攻擊明文統(tǒng)計擴(kuò)散2008-9-2117二、密鑰序列產(chǎn)生器2008-9-2118密鑰序列產(chǎn)生器的構(gòu)成2008-9-2119驅(qū)動部分：

5、控制生成器的狀態(tài)序列，并為非線性組合部分提供統(tǒng)計性能良好的序列。如，驅(qū)動部分可由一組最大長度線性反饋移位寄存器組成。（將實際密鑰k擴(kuò)散成周期很大的驅(qū)動序列）擴(kuò)散非線性部分：將驅(qū)動部分所提供的序列組合成密碼特性好的序列。如，可提高密鑰序列的線性復(fù)雜度（可隱蔽驅(qū)動序列與密鑰k之間過分明顯的依賴關(guān)系）混淆這兩部分構(gòu)成剛好與Shannon早期提出的兩條密碼原則擴(kuò)散和混淆是一致的。2008-9-2120 目前最為流行和實用的密鑰流產(chǎn)生器大多基于線性反饋移位寄存器。如圖所示，其驅(qū)動部分是一個或多個線性反饋移位寄存器。LFSRFLFSR1LFSR2LFSRnFFF常見的密鑰序列產(chǎn)生器2008-9-2121N

6、1-LFSRN2-LFSRNt-LFSR),(21txxxFLzi(1) 非線性組合生成器2008-9-2122N-LFSRzi(2) 非線性濾波生成器2008-9-2123(3) 鐘控生成器2008-9-2124三、線性反饋移位寄存器(LFSR) (Linear Feedback Shift Register)2008-9-2125線性反饋移位寄存器(LFSR)是許多密鑰序列生成器的基本部件LFSRFLFSR1LFSR2LFSRnFFF2008-9-2126LFSR的優(yōu)點非常適合用硬件實現(xiàn)可以產(chǎn)生大周期序列可以產(chǎn)生具有良好統(tǒng)計性質(zhì)的序列易于利用代數(shù)方法對其進(jìn)行分析2008-9-2127線性反

7、饋移位寄存器(LFSR)n-位LFSR:2008-9-2128密鑰序列產(chǎn)生器的構(gòu)成2008-9-2129同步序列密碼密鑰序列的生成獨立于明文和密文2008-9-2130LFSR的組成移位寄存器：是位的序列輸入位bn+1：最高有效位輸出位b1：最低有效位級數(shù)(長度)n：包含的位的數(shù)目周期T：輸出序列從開始到重復(fù)時的長度輸出序列：最低有效位串狀態(tài)序列i ：某個時刻移位寄存器存儲的位所組成的序列i =(bn,bn-1, , b1)共有2n-1個可能的狀態(tài)線性反饋函數(shù)：f (f是線性函數(shù)）其中常數(shù)ci=0或1， 是模2加法2008-9-2131輸出序列2008-9-2132例題若其初始狀態(tài)序列為 ，求

8、：輸入位是？輸出位是？級數(shù)(長度)n=？后續(xù)的狀態(tài)序列分別為？共有多少個不同的狀態(tài)？輸出序列是？周期T=？線性反饋函數(shù)f 如何表述？2008-9-2133下圖為一個5級線性反饋移位寄存器，其初始狀態(tài)為則其輸出序列為？輸出序列習(xí)題2008-9-2134LFSR線性反饋移位寄存器輸出序列的性質(zhì)完全由其反饋函數(shù)決定。n級線性反饋移位寄存器最多有2n個不同的狀態(tài)。若其初始狀態(tài)為0，則其狀態(tài)恒為0。若其初始狀態(tài)非0，則其后繼狀態(tài)不會為0。n級LFSR的狀態(tài)周期 2n-1。其輸出序列的周期與狀態(tài)周期相等，也 2n-1。只要選擇合適的反饋函數(shù)便可使輸出序列的周期達(dá)到最大值2n-1周期達(dá)到最大值的輸出序列稱為

9、m序列。2008-9-2135例題若其初始狀態(tài)序列為 ，求：輸入位是？輸出位是？級數(shù)(長度)n=？后續(xù)的狀態(tài)序列分別為？共有多少個不同的狀態(tài)？輸出序列是？周期T=？線性反饋函數(shù)f 如何表述？其輸出序列為m序列？2008-9-2136下圖為一個5級線性反饋移位寄存器，其初始狀態(tài)為輸出序列習(xí)題其輸出序列為m序列？2008-9-2137 LFSR可以用一個一元高次多項表示：稱這個多項式為LFSR的聯(lián)結(jié)多項式。則，LFSR可記為： (L n)（*）輸出序列LFSR的形式化表示2008-9-2138例題上圖所示的LFSR的聯(lián)結(jié)多項式為：2008-9-2139則其聯(lián)結(jié)多項式為？輸出序列習(xí)題2008-9-2

10、140注意： LFSR與聯(lián)結(jié)多項式是一一對應(yīng)的，如果知道了線性反饋移位寄存器的結(jié)構(gòu)，可以寫出它的聯(lián)結(jié)多項式，同樣可以根據(jù)聯(lián)結(jié)多項式畫出移位寄存器的結(jié)構(gòu)。2008-9-2141本原多項式設(shè)f(x)為GF(2)上的多項式，使f(x)|xp-1的最小整數(shù)p稱為f(x)的周期。如果f(x)的次數(shù)為n，且其周期為2n-1，則稱f(x)為本原多項式LFSR的輸出序列為m序列，當(dāng)且僅當(dāng)其聯(lián)結(jié)多項式p(x)為本原多項式2008-9-2142已經(jīng)證明，對于任意的正整數(shù)n，至少存在一個n次本原多項式。且有有效的產(chǎn)生算法。2008-9-2143m序列的統(tǒng)計特性n級m序列的一個周期中，0和1出現(xiàn)的次數(shù)接近相等。即，1

11、出現(xiàn) 個，0出現(xiàn) 個。游程分布規(guī)律自相關(guān)特性2008-9-2144m序列的游程分布規(guī)律若干個信號連續(xù)出現(xiàn)的現(xiàn)象稱游程。對于序列a，稱a中形如0110或1001的段為一個1游程或0游程游程中所含1或0的個數(shù)稱為該游程的長度如0110為一個長為2的1游程，101為一個長為1的0游程。2008-9-2145m序列的游程分布規(guī)律性質(zhì)：將n級m序列的一個周期段首尾相接，其游程總數(shù)為N=2n-1。1游程的數(shù)目和0游程的數(shù)目各占一半；游程分布如下：長度為n的1游程有1個長度為n-1的0游程有1個；長度為 的1游程有 個長度為 的0游程有 個2008-9-2146m序列的自相關(guān)特性 若 是一個周期為p的0、1

12、序列，定義0 1上的映射為： ，定義 序列 的自相關(guān)函數(shù)為性質(zhì)：若 是一個r級m序列，那么自相關(guān)函數(shù)反映一個周期內(nèi)平均每位的相同程度 若 是一個周期為p的0、1序列，定義0 1上的映射為： ，定義 序列 的自相關(guān)函數(shù)為2008-9-2147LFSR非常適合用硬件實現(xiàn)可以產(chǎn)生大周期序列可以產(chǎn)生具有良好統(tǒng)計性質(zhì)的序列易于利用代數(shù)方法對其進(jìn)行分析2008-9-2148將LFSR的輸出序列直接作為密鑰序列，即將LFSR作為密鑰序列產(chǎn)生器，可行嗎？50年代開始用作密鑰序列，并用于軍用;60年代發(fā)現(xiàn)其是不安全的2008-9-2149設(shè)將m序列的LFSR作為密鑰序列生成器輸出序列 (i=1,2,)m序列密碼

13、的破譯2008-9-2150m序列密碼的破譯設(shè)m序列的LFSR的狀態(tài)為則，其下一狀態(tài)為其中，寫成矩陣形式：其中，依據(jù)LFSR的結(jié)構(gòu)，可定義 (i=1,2,)2008-9-2151 若 則， (i=1,2,) (i=1,2,)2008-9-2152假設(shè)敵手知道一段長為2n的明-密文對，即已知于是，可求出一段長為2n的密鑰序列z 其中m序列密碼的破譯2008-9-2153m序列密碼的破譯由此，可推出線性反饋移位寄存器連續(xù)的n+1個狀態(tài)：2008-9-2154構(gòu)造矩陣根據(jù) 可推出：若X可逆，則m序列密碼的破譯2008-9-2155m序列密碼的破譯對于n級LFSR，只需要知道長為2n的明-密文對(mi

14、,yi)，就可求出矩陣M，便確定出聯(lián)結(jié)多項式p(x)，從而可完全確定LFSR的結(jié)構(gòu)求出n位的密鑰序列ai 2008-9-2156下面證明X的確是可逆的。 因為X是由S1,S2,Sn作為列向量，要證X可逆，只要證明這n個向量線性無關(guān)。由LFSR的結(jié)構(gòu)，可推出：m序列密碼的破譯2008-9-2157 設(shè)m(mn+1)是使S1,S2,Sm線性相關(guān)的最小整數(shù)，即存在不全為0的系數(shù)l1,l2,lm，其中不妨設(shè)l1=1，使得即對于任一整數(shù)i有m序列密碼的破譯2008-9-2158 由此又推出密鑰序列的遞推關(guān)系： 即密鑰流的級數(shù)為小于m。若mn，則得出密鑰流的級數(shù)小于n，矛盾。所以m=n+1，從而矩陣X必是

15、可逆的。m序列密碼的破譯2008-9-2159例： 設(shè)敵手得到密文串101101011110010和相應(yīng)的明文串011001111111001，因此可計算出相應(yīng)的密鑰流為110100100001011。進(jìn)一步假定敵手還知道密鑰序列是使用5級線性反饋移位寄存器產(chǎn)生的，那么敵手可分別用密文串中的前10個比特和明文串中的前10個比特建立如下方程例題2008-9-21602008-9-21612008-9-2162密鑰序列產(chǎn)生器的構(gòu)成2008-9-2163四、RC42008-9-2164RC4RC4是美國RSA數(shù)據(jù)安全公司設(shè)計的一種序列密碼。RSA數(shù)據(jù)安全公司將其收集在加密工具軟件BSAFE中。最初并

16、沒有公布RC4的算法。人們通過軟件進(jìn)行逆向分析得到了算法在這種情況下，RSA數(shù)據(jù)安全公司于1997年公布了RC4密碼算法2008-9-2165RC4RC4與基于LFSR的序列密碼不同RC4以隨機(jī)置換為基礎(chǔ)它是一種基于非線性數(shù)據(jù)表變換的序列密碼，面向字節(jié)操作。它以一個足夠大的數(shù)據(jù)表為基礎(chǔ)，對表進(jìn)行非線性變換，產(chǎn)生非線性的密鑰序列RC4目前被用于SSL/TLS標(biāo)準(zhǔn)中2008-9-2166RC4RC4使用256個字節(jié)的S表和兩個指針（I和J)S表的值S0, S1, , S255是0, 1, , 255的一個排列I和J的初值為0算法步驟：Step1：初始化S表Step2：生成密鑰序列2008-9-21

17、67RC4Step1 在用RC4加解密之前，應(yīng)當(dāng)首先對S表初始化。初始化過程如下： 對S表進(jìn)行填充，即令 S0=0, S1 =1, S2=2, , S255=255(2) 用密鑰k(k0, k1, , klen( k )-1)填充另一個256字節(jié)的R表。若密鑰的長度小于R表的長度，則依次重復(fù)填充，直至將R表填滿Ri=ki mod len( k ) 2008-9-2168RC4 Step1 (3) J=0;(4) 對于I=0: 255，重復(fù)以下操作：J=(J+SI+RI) mod 256;交換SI和SJ注意，對S表初始化的過程實質(zhì)上是對S表進(jìn)行隨機(jī)化處理的過程，只有當(dāng)這一個過程完成后，才能計算產(chǎn)生密鑰序列，否則將是不安全的2008-9-2169RC4Step2 RC4的下一狀態(tài)函數(shù)定義如下： I=0, J=0; I=(I+1) mod 256 J=(J+SI) mo