現(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起源一次一密無條件安全：在理論上是不可破譯的但：要求密鑰與明文具有相同長(zhǎng)度、且不可重復(fù)使用，增加了密鑰分配與管理的

2、困難對(duì)策：用一個(gè)較小的密鑰來偽隨機(jī)地生成密鑰流。2008-9-215人們?cè)噲D以序列密碼方式仿效“一次一密”密碼序列密碼的理論已經(jīng)比較成熟，而且具有工程實(shí)現(xiàn)容易、效率高等特點(diǎn)采用一個(gè)短的種子密鑰來控制某種算法產(chǎn)生出長(zhǎng)的密鑰序列，供加、解密使用，而短的種子密鑰的存儲(chǔ)、分配都較容易2008-9-216序列密碼 vs. 分組密碼2008-9-217序列密碼的基本原理利用種子密鑰k和初始狀態(tài)0產(chǎn)生一個(gè)密鑰序列z=z0z1，并使用如下規(guī)則對(duì)明文序列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ù)測(cè)性密鑰序列產(chǎn)生算法都采用帶存儲(chǔ)的時(shí)序算法，其理論模型為有限自動(dòng)機(jī)，其實(shí)現(xiàn)電路為時(shí)序電路序列密碼實(shí)際應(yīng)用中的關(guān)鍵技術(shù)：如何保持通信雙方的精確同步？ (zi 與ci一一對(duì)應(yīng))2008-9-219序列密碼的分類同步序列密碼同步序列密碼密鑰序列的生成獨(dú)立于明文和密文2008-9-21102008-9-2111同步序列密碼通信模型2008-9-2112同步序列密碼的特點(diǎn)在保密通信過程中，通信的雙方必須保持精確的同步對(duì)于同步序列密碼，只要通信雙方的密鑰序列產(chǎn)生器具有相同的種子密鑰和相同的初始狀

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

5、控制生成器的狀態(tài)序列，并為非線性組合部分提供統(tǒng)計(jì)性能良好的序列。如，驅(qū)動(dòng)部分可由一組最大長(zhǎng)度線性反饋移位寄存器組成。（將實(shí)際密鑰k擴(kuò)散成周期很大的驅(qū)動(dòng)序列）擴(kuò)散非線性部分：將驅(qū)動(dòng)部分所提供的序列組合成密碼特性好的序列。如，可提高密鑰序列的線性復(fù)雜度（可隱蔽驅(qū)動(dòng)序列與密鑰k之間過分明顯的依賴關(guān)系）混淆這兩部分構(gòu)成剛好與Shannon早期提出的兩條密碼原則擴(kuò)散和混淆是一致的。2008-9-2120 目前最為流行和實(shí)用的密鑰流產(chǎn)生器大多基于線性反饋移位寄存器。如圖所示，其驅(qū)動(dòng)部分是一個(gè)或多個(gè)線性反饋移位寄存器。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)點(diǎn)非常適合用硬件實(shí)現(xiàn)可以產(chǎn)生大周期序列可以產(chǎn)生具有良好統(tǒng)計(jì)性質(zhì)的序列易于利用代數(shù)方法對(duì)其進(jìn)行分析2008-9-2127線性反

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

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

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

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

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

12、序列，定義0 1上的映射為： ，定義 序列 的自相關(guān)函數(shù)為性質(zhì)：若 是一個(gè)r級(jí)m序列，那么自相關(guān)函數(shù)反映一個(gè)周期內(nèi)平均每位的相同程度 若 是一個(gè)周期為p的0、1序列，定義0 1上的映射為： ，定義 序列 的自相關(guān)函數(shù)為2008-9-2147LFSR非常適合用硬件實(shí)現(xiàn)可以產(chǎn)生大周期序列可以產(chǎn)生具有良好統(tǒng)計(jì)性質(zhì)的序列易于利用代數(shù)方法對(duì)其進(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è)敵手知道一段長(zhǎng)為2n的明-密文對(duì)，即已知于是，可求出一段長(zhǎng)為2n的密鑰序列z 其中m序列密碼的破譯2008-9-2153m序列密碼的破譯由此，可推出線性反饋移位寄存器連續(xù)的n+1個(gè)狀態(tài)：2008-9-2154構(gòu)造矩陣根據(jù) 可推出：若X可逆，則m序列密碼的破譯2008-9-2155m序列密碼的破譯對(duì)于n級(jí)LFSR，只需要知道長(zhǎng)為2n的明-密文對(duì)(mi

14、,yi)，就可求出矩陣M，便確定出聯(lián)結(jié)多項(xiàng)式p(x)，從而可完全確定LFSR的結(jié)構(gòu)求出n位的密鑰序列ai 2008-9-2156下面證明X的確是可逆的。 因?yàn)閄是由S1,S2,Sn作為列向量，要證X可逆，只要證明這n個(gè)向量線性無關(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，使得即對(duì)于任一整數(shù)i有m序列密碼的破譯2008-9-2158 由此又推出密鑰序列的遞推關(guān)系： 即密鑰流的級(jí)數(shù)為小于m。若mn，則得出密鑰流的級(jí)數(shù)小于n，矛盾。所以m=n+1，從而矩陣X必是

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

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

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