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

1、1,第4章,密鑰流產(chǎn)生技術(shù),2,本章內(nèi)容概要,概述密鑰流產(chǎn)生原理、技術(shù)和實(shí)例。,3,本章目錄,4.1 流密碼體制概述4.2 流密碼設(shè)計(jì)方法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 真隨機(jī)序列的三大特征,5,4.1.1 一次一密密帶體制的原理,一次一密密

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

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

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

5、M，完成電傳打字機(jī)的加密。解：假定我們按正常序列中字母的位置數(shù)給每一個(gè)字母標(biāo)一個(gè)數(shù)來(lái)表示它則可以得到下面的對(duì)應(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因?yàn)殡妭鞔蜃謾C(jī)的

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,完成電傳打字機(jī)的解密。因?yàn)殡妭鞔蜃謾C(jī)的解密是密文字母和密鑰字母的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運(yùn)算有一個(gè)重要性質(zhì)，如果密文和使用相同的密鑰字母流進(jìn)行減法，則恢復(fù)成明文。,9,4.1.2 一次一密密帶體制的安全性,1．一次

8、一密密帶體制的安全性來(lái)自于真隨機(jī)密鑰序列 關(guān)于一次一密密帶體制，值得注意是：如果一個(gè)竊聽(tīng)者不能得到加密消息的一次一密密帶，那么這個(gè)密碼體制是完全安全的。因?yàn)橐淮我幻苊軒w制使用的密鑰序列是真隨機(jī)產(chǎn)生的；一個(gè)真隨機(jī)密鑰序列加到一個(gè)非隨機(jī)的明文消息上，會(huì)產(chǎn)生一個(gè)完全隨機(jī)的密文消息，并且沒(méi)有一種計(jì)算方法能改變這種情況，所以從一次一密密帶體制得到的密文消息具有下列特點(diǎn)：⑴密文和明文在統(tǒng)計(jì)上是無(wú)關(guān)的； ⑵每一個(gè)密文消息都是完全

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

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

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

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

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

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

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

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

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

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

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

20、件 ①密鑰流必須具有長(zhǎng)的周期：因?yàn)槿绻乐芷诘闹岛偷谝恢芷诘拿荑€流,就能完全確定密鑰流的其他部分。 ②大的線性復(fù)雜性：線性復(fù)雜性指能夠產(chǎn)生該密鑰流的最短的線性反饋移位寄存器的級(jí)數(shù).如果線性復(fù)雜性愈大,那么密鑰流的周期愈長(zhǎng)。,,18,4.3線性反饋移位寄存器,4.3.1 反饋移位寄存器4.3.2 線性反饋移位寄存器4.3.3 線性反饋移位寄存器的特點(diǎn),19,4.3.1反饋移位寄存器,,,20,4.3.2 (4比特)線性反饋移

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

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

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

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

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

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

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

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

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

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

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連接多項(xiàng)式分別是,,,,試破譯各原始序列 的初始態(tài),也就是破譯序列產(chǎn)生器的密鑰,32,,,,,33,破譯

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

33、010 10010 10110 11100 A2校驗(yàn)位 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，符合理論分析，說(shuō)明初始態(tài)的選擇是正確的。,,,34,破譯步驟2(a),第2步，尋找序列A3的初始態(tài)。一開(kāi)始可以認(rèn)為，既然“101”是序列的初始態(tài)，那么“1010”會(huì)不會(huì)是序列A3的初始態(tài)，所以把“1010”設(shè)置到A3連接多項(xiàng)式中，重構(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，不符合理論分析，說(shuō)明初始態(tài)的選擇是不正確的。,,,35,破譯步驟2(b),狀態(tài) 序號(hào) 01234567890

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

37、1 A3校驗(yàn)位 0000111101010 使用序列A3連接多項(xiàng)式校驗(yàn)序列B的工作狀態(tài)。由狀態(tài)序號(hào)0～55，沒(méi)有一個(gè)狀態(tài)值與其校驗(yàn)值一致，只有狀態(tài)序號(hào)56表示的狀態(tài)值“0001”產(chǎn)生的校驗(yàn)值“1111”與輸出序列B的“1111”完全一致，所以“0001”是序列A3正確的工作狀態(tài)。由“0001”的狀態(tài)序號(hào)(56號(hào))可以推算出序列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，符合理論分析，說(shuō)明初始態(tài)選擇是正確的。,36,破譯步驟3,第3步,尋找控制序列A1的初始

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

40、1校驗(yàn)位與其輸出的一致性迅速提高,并發(fā)現(xiàn)狀態(tài)值“111111”產(chǎn)生的校驗(yàn)值“010101”與A1輸出一致,所以““111111”是序列正確的工作狀態(tài)。由于“111111”是第1個(gè)工作狀態(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校驗(yàn)位 0101 01100110111 011011110 0101 0A2輸出 110 1001 1101001 11010A3輸出 010 1100 1000111 10101B輸出

42、 010 1101 1100011 10110A1輸出 0XXX0X1X1X010XX0011A1輸出 01 010 011 10010110011A1校驗(yàn)位 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個(gè)線性移位寄存器代替兩個(gè)線性移位寄存器，這里n等于2的冪。共有n+1個(gè)線性移位寄存器，其中第一個(gè)線性移位寄存器的時(shí)鐘速度比其他n個(gè)線性移位寄存器快 倍,盡管這個(gè)線路比Geffe產(chǎn)生器更

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

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

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

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

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