密鑰流產(chǎn)生技術(shù)

1、1,第4章,密鑰流產(chǎn)生技術(shù),2,本章內(nèi)容概要,概述密鑰流產(chǎn)生原理、技術(shù)和實例。,3,本章目錄,4.1 流密碼體制概述4.2 流密碼設(shè)計方法4.3線性反饋移位寄存器4.4 流密碼安全性分析4.5密鑰流產(chǎn)生器的構(gòu)造,4,4.1 流密碼體制概述,4.1.1 一次一密密帶體制的工作原理4.1.2 一次一密密帶體制的安全性4.1.3 同步序列密碼原理4.1.4 真隨機序列的三大特征,5,4.1.1 一次一密密帶體制的原理,一次一密密

2、帶體制也稱為Vernam密碼。它是在1917年由Major Joseph Mauborgne和AT&T的Gilber Vernam發(fā)明的。在這種密碼體制中，密文是由明文消息與相同長度的非重復(fù)隨機序列按比特異或生成的。因為在GF(2)中，加法和減法是相同的，所以第二次施行異或，就能完成解密。圖4-1給出一次一密密帶體制的原理圖。,6,一次一密密帶體制的原理,,一次一密密帶體制的基本原理是通過使用真隨機的密鑰序列,使密文和明文在統(tǒng)計

3、上無關(guān).產(chǎn)生這種隨機序列(即序列中的每一比特都獨立于其前面的各比特,并且其等概率地取0或1的序列)的設(shè)備叫作二進制對稱源(BSS).簡而言之,BSS輸出一種相當好的硬幣拋擲序列.,7,一次一密密帶體制的原始形式,一次一密密帶體制的原始形式是用于電傳打字機。發(fā)送者使用密帶上每一個密鑰字母嚴密地加密一個明文字母。加密是明文字母和一次一密密帶上的密鑰字母的mod26加法，解密是密文字母和一次一密密帶上的密鑰字母的mod26減法。對于一次消息

4、，每一個密鑰字母嚴格地使用一次。發(fā)送者加密消息，然后毀壞使用過的密帶上的記錄或者使用過的磁帶介質(zhì)。接收者具有和發(fā)送者相同的密帶，并且依次使用密帶上的每一個密鑰字母解密密文中的每一個字母。在解密消息后，接收者毀壞使用過的密帶上的記錄或者磁帶介質(zhì)。為了能夠再次進行安全通信，接收端保存的密帶上記錄或者磁帶介質(zhì)應(yīng)與發(fā)送端完全相同。,8,電傳打字機的加密與解密,例4-1 如果消息是：ONETIMEPAD； 密鑰字母序列是：TBFRGFARF

5、M，完成電傳打字機的加密。解：假定我們按正常序列中字母的位置數(shù)給每一個字母標一個數(shù)來表示它則可以得到下面的對應(yīng)關(guān)系：A B C D E F G H I J K L M N O P Q R S T U V W X Y Z1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26因為電傳打字機的

6、加密是明文字母和密鑰字母的mod26加法所以有 (O＋T)mod 26＝(15＋20)mod 26＝9mod 26＝I；同理(N＋B)mod 26＝P；…；(D＋M)mod 26＝Q，得到密文為IPKLPSFHGQ。例4-2 如果密文消息是：IPKLPSFHGQ； 密鑰字母序列是: TBFRGFARFM,完成電傳打字機的解密。因為電傳打字機的解密是密文字母和密鑰字母的mod26減法所以有(I－

7、T)mod26＝(9－20)mod 26＝(－11＋26)mod 26＝15mod 26＝O；(P－B)mod 26＝(16－2) mod 26＝14 mod26＝N；…；(Q－M)mod26＝(17－13)mod 26＝4mod26＝D，得到明文為ONETIMEPAD。從例4-1和例4-2可知，mod26運算有一個重要性質(zhì)，如果密文和使用相同的密鑰字母流進行減法，則恢復(fù)成明文。,9,4.1.2 一次一密密帶體制的安全性,1．一次

8、一密密帶體制的安全性來自于真隨機密鑰序列 關(guān)于一次一密密帶體制，值得注意是：如果一個竊聽者不能得到加密消息的一次一密密帶，那么這個密碼體制是完全安全的。因為一次一密密帶體制使用的密鑰序列是真隨機產(chǎn)生的；一個真隨機密鑰序列加到一個非隨機的明文消息上，會產(chǎn)生一個完全隨機的密文消息，并且沒有一種計算方法能改變這種情況，所以從一次一密密帶體制得到的密文消息具有下列特點：⑴密文和明文在統(tǒng)計上是無關(guān)的； ⑵每一個密文消息都是完全

9、隨機的，與等長的任意可能的明文消息之間不存在某種關(guān)系；⑶在進行密碼分析時，任意一個明文消息都有等概率出現(xiàn)的可能，這樣對于密碼分析者來說，沒有一種方法能夠確定哪一個明文消息是正確的。 因為每一個密鑰序列公正地相似(記住，密鑰序列是真隨機產(chǎn)生的)，密碼分析者沒有可用于分析密文的信息，所以一次一密密帶體制是完全安全的。,10,偽隨機序列存在局部的非隨機特征,1．使用一個偽隨機序列代替真隨機序列是有漏洞的告誡：這是一個重要的

10、告誡，密鑰序列必須隨機產(chǎn)生。如果密鑰序列具有局部的非隨機特征，那么容易遭到攻擊。使用一個偽隨機序列代替真隨機序列在安全上是有漏洞的，因為偽隨機序列存在局部的非隨機特征。如果使用一個真隨機源，那么攻擊是困難的。2．相同的密鑰序列不能重復(fù)使用如果一個密碼分析者已經(jīng)掌握有密鑰交疊的多重密文，則他能夠重構(gòu)明文。因為異或操作有一個特性：如果密文和使用相同的密鑰流進行異或，則恢復(fù)成明文(模運算也有類似特性，如例4-1和例4-2所示)。因此，從不

11、使用相同的密鑰序列。,11,4．一次一密密帶體制的實現(xiàn)問題,1）密鑰的分配和存儲問題因為在一次一密密帶體制中，密鑰比特必須是隨機的，并且從不再次使用，密鑰的長度要等于消息的長度，所以在這3個約束條件下，要求密鑰產(chǎn)生速度快、密鑰分配及時，因而一次一密密帶體制不適合長消息加密，只適合一些短的消息加密。當然能夠把650兆字節(jié)的隨機比特存儲在一個CD-ROM上，但是也存在一些問題。首先，需要兩個精確的隨機比特復(fù)制品，但是，CD-ROM僅僅在

12、大量使用時才是經(jīng)濟的。其次，必須毀壞已經(jīng)使用過的比特。除非在物理層面破壞整個CD-ROM，它是不容易被局部毀壞的設(shè)備。在這些存儲介質(zhì)的挑選中，數(shù)字磁帶是更好的介質(zhì)。2）密鑰的同步問題即使解決了密鑰的分配和存儲問題，也必須確信發(fā)送者和接收者使用的密鑰是完全同步的。如果接收者使用的密鑰相對于發(fā)送者偏移1比特(或者如果在傳輸期間停止傳輸一些比特)，則會引起收發(fā)雙方密鑰失步，導(dǎo)致無法解密。另一方面，如果在傳輸期間一些比特發(fā)生改變(比如由于隨

13、機噪聲影響而發(fā)生)，那么僅僅這些比特解密不正確。3）目前主要用于超安全低帶寬信道一次一密密帶體制已經(jīng)得到實用，主要用于超安全低帶寬信道。在那種場合下，完全保密是頭等重要的。但是因為對密鑰產(chǎn)生的時間和密鑰分配要求過高，目前還只能在低速情況下應(yīng)用。,12,4.1.3 同步序列密碼原理,,,圖中的密鑰流產(chǎn)生器，它在真正密鑰（K）的控制下，產(chǎn)生一隨機序列，其被用來對明文加密。這樣的同步序列密碼體制的安全性取決于密鑰序列的“隨機性”。假定采用

14、已知明文攻擊，密碼分析者完全可以獲得部分密鑰流。關(guān)鍵在于密碼設(shè)計者如何設(shè)計，使得即使密碼分析者獲得部分密鑰流（ ki ），也不能預(yù)測后繼的密鑰流或通過反演繹工作獲得產(chǎn)生密鑰流（ki）的真正密鑰（K）。,一次一密密帶體制的基本原理是通過使用真隨機的密鑰序列,使密文和明文在統(tǒng)計上無關(guān).產(chǎn)生這種隨機序列(即序列中的每一比特都獨立于其前面的各比特,并且其等概率地取0或1的序列)的設(shè)備叫作二進制對稱源(BSS).簡而言之,BSS輸出一種相當好的硬

15、幣拋擲序列,13,流密碼工作模型,,,,,,14,⑵ 流密碼的安全性,①密鑰流產(chǎn)生器輸出愈接近隨機,安全性能愈好如果密鑰流產(chǎn)生器輸出無窮個零，那么密文將等于明文，并且整個工作變得毫無價值。如果密鑰流產(chǎn)生器的輸出比特流周期太小，如周期為16比特，那么算法將是一個簡單的異或電路組成的，可以忽略其安全性。如果密鑰流產(chǎn)生器輸出無窮個隨機比特流(不是偽隨機，而是真隨機)，那么密鑰流產(chǎn)生器的安全性能達到一次一密密帶的效果，并具有完美的保密性。實

16、際的流密碼的安全性位于簡單的異或電路與一次一密密帶之間。密鑰流產(chǎn)生器產(chǎn)生的比特流看上去是隨機的，但是實際上是確定性的比特流，而且在解密時能夠無錯誤地重復(fù)產(chǎn)生。密鑰流產(chǎn)生器的輸出愈接近隨機，密碼分析者破譯它就愈困難。②密鑰流產(chǎn)生器起始狀態(tài)不變帶來的弊端如果每次打開密鑰流產(chǎn)生器都產(chǎn)生相同的比特流，那么密鑰流很容易被破譯。竊聽者可以采取以下辦法破譯密鑰流，如表10-2所示。③密鑰流產(chǎn)生器必須由密鑰來驅(qū)動如果密鑰流產(chǎn)生器由密鑰來驅(qū)動，那

17、么其輸出是密鑰的函數(shù)，只要密鑰改變就不會產(chǎn)生相同的比特流。這就是為什么密鑰流產(chǎn)生器必須由密鑰來驅(qū)動的原因?，F(xiàn)在，如果竊聽者得到一個明文/密文對，那么他只能讀懂由相同密鑰加密的消息；只要密鑰改變，竊聽者就不能讀懂其他密文。,15,密鑰流產(chǎn)生器起始狀態(tài)不變帶來的弊端,16,4.1.4 真隨機序列的三大特征,1．統(tǒng)計的隨機性如果一個序列具備統(tǒng)計的隨機性，則把它稱為偽隨機序列，這意味著它能夠通過所有的統(tǒng)計試驗。例如，它們之中1和0數(shù)目應(yīng)該是相

18、等的，大約各占長度的一半，0和1游程長度的分布也應(yīng)該是一樣的。在實際使用中，要求偽隨機序列的周期比實際使用的長度(不是周期)足夠長。因此要求偽隨機序列的局部隨機性也要與隨機序列的整體隨機性難以區(qū)分。2．不可預(yù)測性盡管給出產(chǎn)生序列的算法或者硬件完整的知識及前面產(chǎn)生的比特流，也不可能通過計算機預(yù)測出下一個隨機比特是什么。3．不可再生性不可再生性是指，即使使用精確的相同輸入，隨機序列產(chǎn)生器兩次分別產(chǎn)生的隨機序列也是不相同的。,17,

19、不可預(yù)測性：要求下一個比特值與前面無關(guān),,⑵充分條件硬幣拋擲序列呈現(xiàn)出的線性復(fù)雜性,典型地隨著所考察的序列的數(shù)目n增大而增長,如圖所示。于是,當密鑰流具有這種線性復(fù)雜性曲線時,就好像它也呈現(xiàn)出均勻的統(tǒng)計特性。相反.在一個周期序列中的均勻分布的統(tǒng)計特性,并非意味著大的線性復(fù)雜性。例如,有著良好分布特性的最大長度序列相對于周期長度而言,其線性復(fù)雜性最小。周期為 的二元最長序列僅僅需要知道2n位的值就能完全確定,⑴必要條

20、件 ①密鑰流必須具有長的周期：因為如果知道周期的值和第一周期的密鑰流,就能完全確定密鑰流的其他部分。 ②大的線性復(fù)雜性：線性復(fù)雜性指能夠產(chǎn)生該密鑰流的最短的線性反饋移位寄存器的級數(shù).如果線性復(fù)雜性愈大,那么密鑰流的周期愈長。,,18,4.3線性反饋移位寄存器,4.3.1 反饋移位寄存器4.3.2 線性反饋移位寄存器4.3.3 線性反饋移位寄存器的特點,19,4.3.1反饋移位寄存器,,,20,4.3.2 (4比特)線性反饋移

21、位寄存器,,21,4.3.3 線性反饋移位寄存器的特點,線性反饋移位寄存器有以下特點。(1)如果LFSR的初始值全為0，則會導(dǎo)致輸出一直為0，這在實際中是不能使用的，所以全0初始值(有時稱為零態(tài))不允許存在。(2)n比特的LFSR可能(2n-1)有個狀態(tài)。這就意味著在重復(fù)前能產(chǎn)生長度為(2n-1)比特的偽隨機序列。僅僅使用某些抽頭序列的LFSR才能循環(huán)通過個內(nèi)部狀態(tài)，這是LFSR的最長周期。具有最長周期的線性反饋移位寄存器序列稱為m

22、序列。產(chǎn)生m序列的條件是抽頭序列（或稱抽頭接法）要滿足本原多項式。,,,22,(3)當談?wù)摱囗検綍r，術(shù)語“素數(shù)”由“不可約的”取代。如果一個多項式不能表示為兩個其他多項式的乘積(除了1和自身外)，那么它是不可約的多項式。多項式x2+1在整數(shù)域是不可約的﹔而多項式x3+2x2+x是可約的，因為它能夠表示為x(x+1)(x+1)。 (4)當一個多項式在給定的域中能成為一個最長周期的產(chǎn)生器時，這個多項式稱為原始的多項式或本原多項式，且它們的

23、所有系數(shù)互為素數(shù)。(5)為了使一個特殊的LFSR成為具有最大周期的LFSR，抽頭序列必須加一個常數(shù)項1(即加x0=1)，以便構(gòu)成本原多項式。多項式階次等于移位寄存器的長度。,23,(6)一般來說，在給定階次(也就是說給定移位寄存器的長度)的情況下，沒有一種容易的方法產(chǎn)生mod2 本原多項式。最容易的方法是選擇一個隨機多項式，試驗它是否是本原的。(7)表4-2列出一些不同階次的本原多項式。例如，表中列出(32，7，5，3，2，1，0)

24、，這意味著它是一個32級線性反饋移位寄存器，其mod2本原多項式為： x32+x7+x5+x3+x2+x+1,24,線性反饋移位寄存器表示,,,本原多項式對于(32，7，5，3，2，1，0)，它意味著當采用一個長度為32比特的移位寄存器時，產(chǎn)生的新比特由第32、第7、第5、第3和第2比特一起異或,,25,4.4 流密碼安全性分析,線性復(fù)雜性和相關(guān)免疫是衡量基于LFSR流密碼安全強度的一種主要標志。4.4.1 線性復(fù)雜性

25、 通常，分析流密碼比分析分組密碼更容易。例如，基于線性移位寄存器的產(chǎn)生器，其重要特性之一是線性復(fù)雜性(linear complexity)或線性跨度(linear span)，其定義為，模擬產(chǎn)生器輸出的最短線性移位寄存器的長度n。有限狀態(tài)機產(chǎn)生的任何序列具有有限的線性復(fù)雜性。線性復(fù)雜度的概念是重要的，因為一個簡單的算法，如Berlekamp-Massey算法,在僅僅經(jīng)過2n比特位檢驗后，就能掌握相關(guān)線性移位寄存器的結(jié)構(gòu)。也

26、就是說已經(jīng)破譯了流密碼。為了理解Berlekamp-Massey算法的原理，下面舉例說明。,26,本原多項式的獲得過程,已知m序列的周期為15，接收到信號為10011010，求該m序列的特征多項式(亦稱連接多項式). 聯(lián)立方程的獲得過程如下：⑴把接收到的前n比特作為初態(tài)(目前n=4),第n+1比特作為線性移位寄存器輸出(一般輸出位靠近連接系數(shù)的低次項),所以得到式(4-8).⑵把接收到的前n+1位～2位作為第二狀態(tài),第n+2比特作為線

27、性移位寄存器輸出,所以得式(4-9).以此類推,可得式(4-10)和(4-11),27,4.4.2 相關(guān)免疫 (1),為了獲得高強度的密碼序列，最常用的辦法之一是從一組較簡單的原始序列出發(fā)，經(jīng)過某種非線性方法組合，得到一個新的序列。這里存在的危險是，一個或更多內(nèi)部原始序列經(jīng)常由線性移位寄存器產(chǎn)生，它們可能分別與輸出的組合密鑰流相關(guān)。 相關(guān)攻擊的基本思想是，檢驗輸出的組合密鑰流與它的一個內(nèi)部原始序列之間的相關(guān)性，然后，借助于觀

28、測組合密鑰流的輸出序列，獲得一個內(nèi)部原始序列的信息。再通過使用這些信息和其他信息的相關(guān)性，收集關(guān)于其他內(nèi)部原始序列的信息，直到破譯整個產(chǎn)生器。,28,4.4.2 相關(guān)免疫 (2),可以把上述相關(guān)分析或稱為相關(guān)攻擊的思想用數(shù)學(xué)形式來表示，即在由多個子序列,可以把上述相關(guān)分析或稱為相關(guān)攻擊的思想用數(shù)學(xué)形式來表示，即在由多個子序列 驅(qū)動的密鑰流k中,對k與子序列的符合率進行分析,如果 與 中0比特的符合率為 ，且

29、 ，則 與k之間存在相關(guān)性，當 值愈大，k與 之間的互信息就愈大。相關(guān)免疫(correlation immunity)是指 ，n個隨機變量統(tǒng)計獨立或互信息為 =0 。,29,相關(guān)法破譯,,Geffe產(chǎn)生器把三個線性移位寄存器用非線性方法組合起來。兩個線性移位寄存器輸入到一個多路選擇器，第3個線性移位寄存器控制多路選擇器的輸出。,為了獲得高強度的密碼序列,最常

30、用的辦法之一是從一組較簡單的原始序列出發(fā),經(jīng)過某種非線性方法的組合,得到一個新的序列.這里存在的危險是,一個或更多內(nèi)部原始序列可能分別與輸出的組合密鑰流相關(guān).相關(guān)攻擊的基本思想是:檢驗輸出的組合密鑰流與它的一個內(nèi)部原始序列之間的相關(guān)性,借助于觀測組合密鑰流輸出序列,來獲得一個內(nèi)部原始序列的信息.通過使用這些信息和其他的相關(guān)性,收集關(guān)于其他內(nèi)部原始序列的信息,直到破譯整個產(chǎn)生器,30,相關(guān)法破譯,,,,,,,,31,相關(guān)法破譯實例,例 已

31、知Geffe產(chǎn)生器輸出序列B為10100 10111 00100 01101 10010 01010 10010 10110 11100 01110 11010 01000 11110100 10111 00111 01101 10010 00111 10011 10110 11111 00101 11010 00011 101連接多項式分別是,,,,試破譯各原始序列 的初始態(tài),也就是破譯序列產(chǎn)生器的密鑰,32,,,,,33,破譯

32、步驟1,第1步，尋找序列A2的初始態(tài)。使用序列A2的連接多項式校驗序列B的工作狀態(tài)，結(jié)果如下表所示。由表可知，由狀態(tài)值“101”產(chǎn)生的校驗值“001”與輸出序列B的“001”完全一致，所以“101”是序列A2的正確的工作狀態(tài)。由于“101”是第一個工作狀態(tài)，所以它是初始態(tài)。 使用序列A2連接多項式校驗序列B的工作狀態(tài) 狀態(tài)序號 B輸出 10100 10111 00100 01101 10010 01

33、010 10010 10110 11100 A2校驗位 00 11 用初始態(tài)“101”重構(gòu)序列 A2B輸出 10100 10111 00100 01101 10010 01010 10010 10110 11100 01110 11010 01000 111 A2輸出10100 11101 00111 01001 11010 01110 10011 10100 11101 00111 01001 1

34、1010 011 A2與B的符合率為(63－18)/63＝1－0.286＝0.714，符合理論分析，說明初始態(tài)的選擇是正確的。,,,34,破譯步驟2(a),第2步，尋找序列A3的初始態(tài)。一開始可以認為，既然“101”是序列的初始態(tài)，那么“1010”會不會是序列A3的初始態(tài)，所以把“1010”設(shè)置到A3連接多項式中，重構(gòu)序列A3。 用初始態(tài)“1010”重構(gòu)序列 A3B輸出 10100 10111 00100 01101 100

35、10 01010 10010 10110 11100 01110 11010 01000 111 A3輸出10101 10010 00111 10101 10010 00111 10101 10010 00111 10101 10010 00111 101 A3與B的符合率為(63－28)/63＝1－0.45＝0.55，不符合理論分析，說明初始態(tài)的選擇是不正確的。,,,35,破譯步驟2(b),狀態(tài) 序號 01234567890

36、123456789012345678901234567890123456789012B輸出 10100101110010001101100100101010010101101110001110110100A3校驗位 10001011100010100001 00000111100011100001111111100101 狀態(tài) 序號 3456789012345B輸出 100011110100

37、1 A3校驗位 0000111101010 使用序列A3連接多項式校驗序列B的工作狀態(tài)。由狀態(tài)序號0～55，沒有一個狀態(tài)值與其校驗值一致，只有狀態(tài)序號56表示的狀態(tài)值“0001”產(chǎn)生的校驗值“1111”與輸出序列B的“1111”完全一致，所以“0001”是序列A3正確的工作狀態(tài)。由“0001”的狀態(tài)序號(56號)可以推算出序列B的初始態(tài)為“1111”。使用初始態(tài)“1111”重構(gòu)序列 A3B輸出 10100 10111 0

38、0100 01101 10010 01010 10010 10110 11100 01110 11010 01000 111 A3輸出11110 10110 01000 11110 10110 01000 11110 10110 01000 11110 10110 01000 111A3與B的符合率為(63－17)/63＝1－0.27＝0.73，符合理論分析，說明初始態(tài)選擇是正確的。,36,破譯步驟3,第3步,尋找控制序列A1的初始

39、態(tài).把輸出序列B分別與序列A2和A3比較,如果與A2符合,則A1記為“1”;如果與A3符合,則記A1為“0”;如果A2與A3和都符合記為“X”.這樣可以得到部分比特,如果其長度超過寄存器的長度,那么就找到的一個正確的態(tài),然后推算出初始態(tài).這里介紹一種取巧的捷徑:在A2和A3都符合記的情況下,如果在“1”上符合,記A1為“1”;如果在“0”上符合,則記A1為“0”,或者按照相反條件假設(shè),主要看能否通過輸出校驗.從下表發(fā)現(xiàn),經(jīng)過這種處理,A

40、1校驗位與其輸出的一致性迅速提高,并發(fā)現(xiàn)狀態(tài)值“111111”產(chǎn)生的校驗值“010101”與A1輸出一致,所以““111111”是序列正確的工作狀態(tài)。由于“111111”是第1個工作狀態(tài)，所以它是初始態(tài)。,37,尋找A1初態(tài),A2輸出10100 11101 00111010011101 001110 1001A3輸出11110 10110 01000111101011 001000 1111B輸出 10100 10111 0010

41、0011011001 001010 1001A1輸出X1X11X0X01X110011011X01XXXX01XX11XA1輸出 1111110101 01100110111011 00101 0111 1A1校驗位 0101 01100110111 011011110 0101 0A2輸出 110 1001 1101001 11010A3輸出 010 1100 1000111 10101B輸出

42、 010 1101 1100011 10110A1輸出 0XXX0X1X1X010XX0011A1輸出 01 010 011 10010110011A1校驗位 000110010 00010101101,38,由重構(gòu)序列控制和產(chǎn)生的B序列,A2輸出 10100 11101 00111 010011101 001110 1001A3輸出 11110 10110 01000 111101011 001000 111

43、1A1輸出 11111 10101 01100 110111011 010010 0111重構(gòu)B輸出 10100 10111 00100 011011001 001010 1001B輸出 10100 10111 00100 011011001 001010 1001A2輸出 110 1001 1101001 11010A3輸出 010 1100 1000111 10101A1輸出 0 0 0101

44、1110010 10001重構(gòu)B輸出 010 1101 1100011 10110B輸出 010 1101 1100011 10110,39,一般的Geffe產(chǎn)生器,,一般的Geffe產(chǎn)生器是選擇n個線性移位寄存器代替兩個線性移位寄存器，這里n等于2的冪。共有n+1個線性移位寄存器，其中第一個線性移位寄存器的時鐘速度比其他n個線性移位寄存器快 倍,盡管這個線路比Geffe產(chǎn)生器更

45、加復(fù)雜，但是同樣會遭受同類的相關(guān)攻擊，所以不推薦采用這種產(chǎn)生器。,40,4.5密鑰流產(chǎn)生器的構(gòu)造,本節(jié)主要講述三種安全可靠的密鑰流產(chǎn)生器。4.5.1 基于線性移位寄存器設(shè)計密鑰流產(chǎn)生器 1.設(shè)計方法概述 2. 多路選擇密鑰流產(chǎn)生器 3. 鐘控密鑰流產(chǎn)生器 4.5.2 基于置換盒設(shè)計密鑰流產(chǎn)生器,41,4.5.1 基于線性移位寄存器設(shè)計密鑰流產(chǎn)生器1.設(shè)計方法概述,⑴首先要獲得一個或多個線性反饋移位寄存器(LFSR)，使用不同

46、的反饋多項式產(chǎn)生不同的長度。密鑰是各個線性移位寄存器的初態(tài)。輸出比特是各個線性移位寄存器一些比特的函數(shù)，更適宜的是非線性函數(shù)，這個函數(shù)稱為組合函數(shù)，整個產(chǎn)生器稱作組合產(chǎn)生器。⑵為了增加產(chǎn)生器輸出比特的安全性，必須對線性移位寄存器(LFSR)添加復(fù)雜性。有一些LFSR的時鐘工作在不同的速率上，有一些LFSR的時鐘依賴于另一個LFSR的輸出，這種產(chǎn)生器稱為時鐘控制產(chǎn)生器。時鐘能夠控制前饋(feedforward)或反饋(feedback)

47、，前者指LFSR的輸出控制另一個時鐘，而后者指LFSR的輸出控制自己的時鐘。⑶基于線性移位寄存器的密鑰流產(chǎn)生器一般是用硬件實現(xiàn)的。,42,2. 多路選擇密鑰流產(chǎn)生器,Geffe產(chǎn)生器把三個線性移位寄存器用非線性方法組合起來，兩個線性移位寄存器輸入到一個多路選擇器，第三個線性移位寄存器控制多路選擇器的輸出。一般的Geffe產(chǎn)生器是選擇n個線性移位寄存器代替兩個線性移位寄存器，這里n等于2的冪。,,⑴一般的Geffe產(chǎn)生器,43,⑵Jen

48、nings 產(chǎn)生器,這種線路使用一個多路選擇器組合兩個線性反饋移位寄存器。多路選擇器根據(jù)第一個線性反饋移位寄存器的控制信號值來選擇第二個線性反饋移位寄存器每次輸出比特中的一個比特，在第二個反饋線性移位寄存器輸出到多路選擇器輸入端之間也加入一個映射函數(shù),,44,3. 鐘控密鑰流產(chǎn)生器,⑴Beth-Piper停走型產(chǎn)生器 這種產(chǎn)生器使用一個線性移位寄存器的輸出控制另一個線性移位寄存器的時鐘，如圖4-14所示。第二個線性移位寄

49、存器的輸入時鐘受到第一個線性移位寄存器輸出的控制，所以當?shù)谝粋€線性移位寄存器輸出改變t-1次時，第二個線性移位寄存器只改變t次狀態(tài)。,,一般情況下，沒有人能夠證明其線性復(fù)雜度，但它卻容易遭受相關(guān)攻擊。,45,⑵交替停走型產(chǎn)生器,這種產(chǎn)生器使用三個不同長度的線性移位寄存器。如圖4-15所示，當?shù)谝粋€線性移位寄存器輸出為1時，第二個線性移位寄存器得到時鐘；當?shù)谝粋€線性移位寄存器輸出為0時，第三個線性移位寄存器得到時鐘。最后產(chǎn)生器的輸出是第二