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

第4章

密鑰流產(chǎn)生技術(shù)1本章內(nèi)容概要概述密鑰流產(chǎn)生原理、技術(shù)和實(shí)例。2本章目錄4.1流密碼體制概述4.2流密碼設(shè)計(jì)方法4.3線性反饋移位寄存器4.4流密碼安全性分析4.5密鑰流產(chǎn)生器的構(gòu)造34.1.1一次一密密帶體制的原理一次一密密帶體制也稱為Vernam密碼。它是在1917年由MajorJosephMauborgne和AT&T的GilberVernam發(fā)明的。在這種密碼體制中，密文是由明文消息與相同長(zhǎng)度的非重復(fù)隨機(jī)序列按比特異或生成的。因?yàn)樵贕F(2)中，加法和減法是相同的，所以第二次施行異或，就能完成解密。圖4-1給出一次一密密帶體制的原理圖。

5一次一密密帶體制的原理一次一密密帶體制的基本原理是通過(guò)使用真隨機(jī)的密鑰序列,使密文和明文在統(tǒng)計(jì)上無(wú)關(guān).產(chǎn)生這種隨機(jī)序列(即序列中的每一比特都獨(dú)立于其前面的各比特,并且其等概率地取0或1的序列)的設(shè)備叫作二進(jìn)制對(duì)稱源(BSS).簡(jiǎn)而言之,BSS輸出一種相當(dāng)好的硬幣拋擲序列.6一次一密密帶體制的原始形式

一次一密密帶體制的原始形式是用于電傳打字機(jī)。發(fā)送者使用密帶上每一個(gè)密鑰字母嚴(yán)密地加密一個(gè)明文字母。加密是明文字母和一次一密密帶上的密鑰字母的mod26加法，解密是密文字母和一次一密密帶上的密鑰字母的mod26減法。對(duì)于一次消息，每一個(gè)密鑰字母嚴(yán)格地使用一次。發(fā)送者加密消息，然后毀壞使用過(guò)的密帶上的記錄或者使用過(guò)的磁帶介質(zhì)。接收者具有和發(fā)送者相同的密帶，并且依次使用密帶上的每一個(gè)密鑰字母解密密文中的每一個(gè)字母。在解密消息后，接收者毀壞使用過(guò)的密帶上的記錄或者磁帶介質(zhì)。為了能夠再次進(jìn)行安全通信，接收端保存的密帶上記錄或者磁帶介質(zhì)應(yīng)與發(fā)送端完全相同。7電傳打字機(jī)的加密與解密例4-1如果消息是：ONETIMEPAD；密鑰字母序列是：TBFRGFARFM，完成電傳打字機(jī)的加密。解：假定我們按正常序列中字母的位置數(shù)給每一個(gè)字母標(biāo)一個(gè)數(shù)來(lái)表示它則可以得到下面的對(duì)應(yīng)關(guān)系：ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567891011121314151617181920212223242526因?yàn)殡妭鞔蜃謾C(jī)的加密是明文字母和密鑰字母的mod26加法所以有(O＋T)mod26＝(15＋20)mod26＝9mod26＝I；同理(N＋B)mod26＝P；…；(D＋M)mod26＝Q，得到密文為IPKLPSFHGQ。例4-2如果密文消息是：IPKLPSFHGQ；密鑰字母序列是:TBFRGFARFM,完成電傳打字機(jī)的解密。因?yàn)殡妭鞔蜃謾C(jī)的解密是密文字母和密鑰字母的mod26減法所以有(I－T)mod26＝(9－20)mod26＝(－11＋26)mod26＝15mod26＝O；(P－B)mod26＝(16－2)mod26＝14mod26＝N；…；(Q－M)mod26＝(17－13)mod26＝4mod26＝D，得到明文為ONETIMEPAD。從例4-1和例4-2可知，mod26運(yùn)算有一個(gè)重要性質(zhì)，如果密文和使用相同的密鑰字母流進(jìn)行減法，則恢復(fù)成明文。8偽隨機(jī)序列存在局部的非隨機(jī)特征1．使用一個(gè)偽隨機(jī)序列代替真隨機(jī)序列是有漏洞的告誡：這是一個(gè)重要的告誡，密鑰序列必須隨機(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)算也有類似特性，如例4-1和例4-2所示)。因此，從不使用相同的密鑰序列。104.1.3同步序列密碼原理圖中的密鑰流產(chǎn)生器，它在真正密鑰（K）的控制下，產(chǎn)生一隨機(jī)序列，其被用來(lái)對(duì)明文加密。這樣的同步序列密碼體制的安全性取決于密鑰序列的“隨機(jī)性”。假定采用已知明文攻擊，密碼分析者完全可以獲得部分密鑰流。關(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ì)稱源(BSS).簡(jiǎn)而言之,BSS輸出一種相當(dāng)好的硬幣拋擲序列12⑵流密碼的安全性①密鑰流產(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í)際的流密碼的安全性位于簡(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)，那么其輸出是密鑰的函數(shù)，只要密鑰改變就不會(huì)產(chǎn)生相同的比特流。這就是為什么密鑰流產(chǎn)生器必須由密鑰來(lái)驅(qū)動(dòng)的原因。現(xiàn)在，如果竊聽(tīng)者得到一個(gè)明文/密文對(duì)，那么他只能讀懂由相同密鑰加密的消息；只要密鑰改變，竊聽(tīng)者就不能讀懂其他密文。14密鑰流產(chǎn)生器起始狀態(tài)不變帶來(lái)的弊端

154.1.4真隨機(jī)序列的三大特征1．統(tǒng)計(jì)的隨機(jī)性如果一個(gè)序列具備統(tǒng)計(jì)的隨機(jī)性，則把它稱為偽隨機(jī)序列，這意味著它能夠通過(guò)所有的統(tǒng)計(jì)試驗(yàn)。例如，它們之中1和0數(shù)目應(yīng)該是相等的，大約各占長(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ī)序列也是不相同的。16不可預(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位的值就能完全確定⑴必要條件①密鑰流必須具有長(zhǎng)的周期：因?yàn)槿绻乐芷诘闹岛偷谝恢芷诘拿荑€流,就能完全確定密鑰流的其他部分。②大的線性復(fù)雜性：線性復(fù)雜性指能夠產(chǎn)生該密鑰流的最短的線性反饋移位寄存器的級(jí)數(shù).如果線性復(fù)雜性愈大,那么密鑰流的周期愈長(zhǎng)。174.3線性反饋移位寄存器4.3.1反饋移位寄存器4.3.2線性反饋移位寄存器4.3.3線性反饋移位寄存器的特點(diǎn)184.3.2(4比特)線性反饋移位寄存器204.3.3線性反饋移位寄存器的特點(diǎn)線性反饋移位寄存器有以下特點(diǎn)。(1)如果LFSR的初始值全為0，則會(huì)導(dǎo)致輸出一直為0，這在實(shí)際中是不能使用的，所以全0初始值(有時(shí)稱為零態(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)周期的線性反饋移位寄存器序列稱為m序列。產(chǎn)生m序列的條件是抽頭序列（或稱抽頭接法）要滿足本原多項(xiàng)式。21(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)，這意味著它是一個(gè)32級(jí)線性反饋移位寄存器，其mod2本原多項(xiàng)式為：

x32+x7+x5+x3+x2+x+123線性反饋移位寄存器表示本原多項(xiàng)式對(duì)于(32，7，5，3，2，1，0)，它意味著當(dāng)采用一個(gè)長(zhǎng)度為32比特的移位寄存器時(shí)，產(chǎn)生的新比特由第32、第7、第5、第3和第2比特一起異或24本原多項(xiàng)式的獲得過(guò)程

已知m序列的周期為15，接收到信號(hào)為10011010，求該m序列的特征多項(xià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比特作為線性移位寄存器輸出,所以得式(4-9).以此類推,可得式(4-10)和(4-11)264.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)性，然后，借助于觀測(cè)組合密鑰流的輸出序列，獲得一個(gè)內(nèi)部原始序列的信息。再通過(guò)使用這些信息和其他信息的相關(guān)性，收集關(guān)于其他內(nèi)部原始序列的信息，直到破譯整個(gè)產(chǎn)生器。

274.4.2相關(guān)免疫(2)可以把上述相關(guān)分析或稱為相關(guān)攻擊的思想用數(shù)學(xué)形式來(lái)表示，即在由多個(gè)子序列

可以把上述相關(guān)分析或稱為相關(guān)攻擊的思想用數(shù)學(xué)形式來(lái)表示，即在由多個(gè)子序列驅(qū)動(dòng)的密鑰流k中,對(duì)k與子序列的符合率進(jìn)行分析,如果與中0比特的符合率為，且，則與k之間存在相關(guān)性，當(dāng)值愈大，k與之間的互信息就愈大。相關(guān)免疫(correlationimmunity)是指，n個(gè)隨機(jī)變量統(tǒng)計(jì)獨(dú)立或互信息為=0。

28相關(guān)法破譯

30相關(guān)法破譯實(shí)例例已知Geffe產(chǎn)生器輸出序列B為101001011100100011011001001010100101011011100011101101001000111101001011100111011011001000111100111011011111001011101000011101連接多項(xiàng)式分別是試破譯各原始序列的初始態(tài),也就是破譯序列產(chǎn)生器的密鑰3132破譯步驟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輸出101001011100100011011001001010100101011011100A2校驗(yàn)位0011

用初始態(tài)“101”重構(gòu)序列A2B輸出101001011100100011011001001010100101011011100011101101001000111A2輸出101001110100111010011101001110100111010011101001110100111010011A2與B的符合率為(63－18)/63＝1－0.286＝0.714，符合理論分析，說(shuō)明初始態(tài)的選擇是正確的。

33破譯步驟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輸出101001011100100011011001001010100101011011100011101101001000111A3輸出101011001000111101011001000111101011001000111101011001000111101A3與B的符合率為(63－28)/63＝1－0.45＝0.55，不符合理論分析，說(shuō)明初始態(tài)的選擇是不正確的。34破譯步驟2(b)狀態(tài)序號(hào)01234567890123456789012345678901234567890123456789012B輸出10100101110010001101100100101010010101101110001110110100A3校驗(yàn)位1000101110001010000100000111100011100001111111100101狀態(tài)序號(hào)3456789012345B輸出

1000111101001A3校驗(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輸出101001011100100011011001001010100101011011100011101101001000111A3輸出111101011001000111101011001000111101011001000111101011001000111A3與B的符合率為(63－17)/63＝1－0.27＝0.73，符合理論分析，說(shuō)明初始態(tài)選擇是正確的。35破譯步驟3第3步,尋找控制序列A1的初始態(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ò)這種處理,A1校驗(yàn)位與其輸出的一致性迅速提高,并發(fā)現(xiàn)狀態(tài)值“111111”產(chǎn)生的校驗(yàn)值“010101”與A1輸出一致,所以““111111”是序列正確的工作狀態(tài)。由于“111111”是第1個(gè)工作狀態(tài)，所以它是初始態(tài)。36尋找A1初態(tài)A2輸出1010011101001110100111010011101001A3輸出1111010110010001111010110010001111B輸出1010010111001000110110010010101001A1輸出X1X11X0X01X110011011X01XXXX01XX11XA1輸出1111110101011001101110110010101111A1校驗(yàn)位01010110011011101101111001010A2輸出1101001110100111010A3輸出0101100100011110101B輸出0101101110001110110A1輸出0XXX0X1X1X010XX0011A1輸出0101001110010110011A1校驗(yàn)位0001100100001010110137由重構(gòu)序列控制和產(chǎn)生的B序列A2輸出1010011101001110100111010011101001A3輸出1111010110010001111010110010001111A1輸出1111110101011001101110110100100111重構(gòu)B輸出

1010010111001000110110010010101001B輸出1010010111001000110110010010101001A2輸出1101001110100111010A3輸出0101100100011110101A1輸出000101111001010001重構(gòu)B輸出0101101110001110110B輸出010110111000111011038一般的Geffe產(chǎn)生器

一般的Geffe產(chǎn)生器是選擇n個(gè)線性移位寄存器代替兩個(gè)線性移位寄存器，這里n等于2的冪。共有n+1個(gè)線性移位寄存器，其中第一個(gè)線性移位寄存器的時(shí)鐘速度比其他n個(gè)線性移位寄存器快倍盡管這個(gè)線路比Geffe產(chǎn)生器更加復(fù)雜，但是同樣會(huì)遭受同類的相關(guān)攻擊，所以不推薦采用這種產(chǎn)生器。394.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)生器

404.5.1基于線性移位寄存器設(shè)計(jì)密鑰流產(chǎn)生器

1.設(shè)計(jì)方法概述

⑴首先要獲得一個(gè)或多個(gè)線性反饋移位寄存器(LFSR)，使用不同的反饋多項(xiàng)式產(chǎn)生不同的長(zhǎng)度。密鑰是各個(gè)線性移位寄存器的初態(tài)。輸出比特是各個(gè)線性移位寄存器一些比特的函數(shù)，更適宜的是非線性函數(shù)，這個(gè)函數(shù)稱為組合函數(shù)，整個(gè)產(chǎn)生器稱作組合產(chǎn)生器。⑵為了增加