序列密碼講解及事例

1、第五講：第五講：序列密碼序列密碼2 人們試圖用序列密碼方式仿效”一次一密”密碼. 從而促成了序列密碼的研究和發(fā)展. 序列密碼是世界軍事, 外交等領(lǐng)域應(yīng)用的主流密碼體制. 在通常的序列密碼中, 加解密用的密鑰序列是偽隨機序列, 它的產(chǎn)生容易且有較成熟的理論工具, 所以序列密碼是當(dāng)前通用的密碼系統(tǒng). 序列密碼的安全性主要依賴于密鑰序列, 因而什么樣的偽隨機序列是安全可靠的密鑰序列, 以及如何實現(xiàn)這種序列就成了序列密碼中研究的一個主要方面.3 在密碼學(xué)都要涉及到隨機數(shù)？因為許多密碼系統(tǒng)的安全性都依在密碼學(xué)都要涉及到隨機數(shù)？因為許多密碼系統(tǒng)的安全性都依賴于隨機數(shù)的生成，例如賴于隨機數(shù)的生成，例如DES

2、加密算法中的密鑰，加密算法中的密鑰，RSA加密和數(shù)字加密和數(shù)字簽名中的素數(shù)。簽名中的素數(shù)。 5.1.1 隨機數(shù)的使用隨機數(shù)的使用 序列密碼的保密性完全取決于密鑰的隨機性。序列密碼的保密性完全取決于密鑰的隨機性。如果密鑰是真正如果密鑰是真正的隨機數(shù)，則這種體制在理論上就是不可破譯的。的隨機數(shù)，則這種體制在理論上就是不可破譯的。但這種方式所需但這種方式所需的密鑰量大得驚人，在實際中是不可行的。的密鑰量大得驚人，在實際中是不可行的。 目前一般采用偽隨機序列來代替隨機序列作為密鑰序列，也就目前一般采用偽隨機序列來代替隨機序列作為密鑰序列，也就是序列存在著一定的循環(huán)周期。是序列存在著一定的循環(huán)周期。這樣

3、序列周期的長短就成為保密性這樣序列周期的長短就成為保密性的關(guān)鍵。如果周期足夠長，就會有比較好的保密性。的關(guān)鍵。如果周期足夠長，就會有比較好的保密性?，F(xiàn)在周期小于現(xiàn)在周期小于1010的序列很少被采用，周期長達(dá)的序列很少被采用，周期長達(dá)1050的序列也并不少見。的序列也并不少見。 4 何謂偽隨機數(shù)生成器（何謂偽隨機數(shù)生成器（PRNG）？）？假定需要生成介于假定需要生成介于1和和 10 之之間的隨機數(shù)，每一個數(shù)出現(xiàn)的幾率都是一樣的。間的隨機數(shù)，每一個數(shù)出現(xiàn)的幾率都是一樣的。理想情況下，應(yīng)生理想情況下，應(yīng)生成成0到到1之間的一個值，不考慮以前值，這個范圍中的每一個值出現(xiàn)之間的一個值，不考慮以前值，這個

4、范圍中的每一個值出現(xiàn)的幾率都是一樣的，然后再將該值乘以的幾率都是一樣的，然后再將該值乘以 10。 由任何偽隨機數(shù)生成器返回的數(shù)目會受到由任何偽隨機數(shù)生成器返回的數(shù)目會受到 0 到到 N 之間整數(shù)數(shù)目的之間整數(shù)數(shù)目的限制。限制。因為常見情況下，偽隨機數(shù)生成器生成因為常見情況下，偽隨機數(shù)生成器生成 0 0 到到 N N 之間的一個之間的一個整數(shù)，返回的整數(shù)再除以整數(shù)，返回的整數(shù)再除以 N N。可以得出的數(shù)字總是處于可以得出的數(shù)字總是處于 0 0 和和 1 1 之之間。間。對生成器隨后的調(diào)用采用第一次運行產(chǎn)生的整數(shù)，并將它傳給對生成器隨后的調(diào)用采用第一次運行產(chǎn)生的整數(shù)，并將它傳給一個函數(shù)，以生成一個

5、函數(shù)，以生成 0 0 到到 N N 之間的一個新整數(shù)，然后再將新整數(shù)除之間的一個新整數(shù)，然后再將新整數(shù)除以以 N N 返回。返回。 5.1.2 偽隨機數(shù)產(chǎn)生器5 目前，常見隨機數(shù)發(fā)生器中目前，常見隨機數(shù)發(fā)生器中N 是是2321 （大約等于（大約等于 40 億），對億），對于于 32 位數(shù)字來說，這是最大的值。位數(shù)字來說，這是最大的值。但在密碼學(xué)領(lǐng)域，但在密碼學(xué)領(lǐng)域， 40 億個數(shù)根億個數(shù)根本不算大！本不算大！ 偽隨機數(shù)生成器將作為偽隨機數(shù)生成器將作為“種子種子”的數(shù)當(dāng)作初始整數(shù)傳給函數(shù)。的數(shù)當(dāng)作初始整數(shù)傳給函數(shù)。由由偽隨機數(shù)生成器返回的每一個值完全由它返回的前一個值所決定。偽隨機數(shù)生成器返回的

6、每一個值完全由它返回的前一個值所決定。因此，最初的種子決定了這個隨機數(shù)序列。因此，最初的種子決定了這個隨機數(shù)序列。如果知道用于計算任何如果知道用于計算任何一個值的那個整數(shù)，那么就可以算出從這個生成器返回的下一個值。一個值的那個整數(shù)，那么就可以算出從這個生成器返回的下一個值。 偽隨機數(shù)生成器是一個生成完全可預(yù)料的數(shù)列（稱為流）的確定偽隨機數(shù)生成器是一個生成完全可預(yù)料的數(shù)列（稱為流）的確定性程序。性程序。一個編寫得很好的的一個編寫得很好的的PRNGPRNG可以創(chuàng)建一個序列，而這個序列可以創(chuàng)建一個序列，而這個序列的屬性與許多真正隨機數(shù)的序列的屬性是一樣的。的屬性與許多真正隨機數(shù)的序列的屬性是一樣的。

7、 例如：（例如：（1 1）PRNGPRNG可以以相同幾率在一個范圍內(nèi)生成任何數(shù)字；可以以相同幾率在一個范圍內(nèi)生成任何數(shù)字；（2 2）PRNG PRNG 可以生成帶任何統(tǒng)計分布的流；（可以生成帶任何統(tǒng)計分布的流；（3 3）由）由PRNGPRNG生成的數(shù)生成的數(shù)字流不具備可辨別的模。字流不具備可辨別的模。65.1.3 基于密碼算法的隨機數(shù)產(chǎn)生器 1使用軟件方法的隨機數(shù)產(chǎn)生器使用軟件方法的隨機數(shù)產(chǎn)生器 一個常用的隨機數(shù)產(chǎn)生器是屬于線形擬合生成器一類的。一個常用的隨機數(shù)產(chǎn)生器是屬于線形擬合生成器一類的。這這類生成器相當(dāng)普遍，它們采用很具體的數(shù)學(xué)公式：類生成器相當(dāng)普遍，它們采用很具體的數(shù)學(xué)公式： Xn+

8、1 = (aXn + b) mod c即第即第 n+1 個數(shù)等于第個數(shù)等于第 n 個數(shù)乘以某個常數(shù)個數(shù)乘以某個常數(shù) a，再加上常數(shù)，再加上常數(shù) b。如果結(jié)果大于或等于某個常數(shù)如果結(jié)果大于或等于某個常數(shù) c，那么通過除以，那么通過除以 c，并取它的余數(shù)，并取它的余數(shù)來將這個值限制在一定范圍內(nèi)。來將這個值限制在一定范圍內(nèi)。注意：注意：a、b 和和 c 通常是質(zhì)數(shù)。通常是質(zhì)數(shù)。 2使用硬件方法的隨機數(shù)產(chǎn)生器使用硬件方法的隨機數(shù)產(chǎn)生器 目前生成隨機數(shù)的幾種硬件設(shè)備都是用于商業(yè)用途。目前生成隨機數(shù)的幾種硬件設(shè)備都是用于商業(yè)用途。得到廣泛使得到廣泛使用的設(shè)備是用的設(shè)備是 ComScire QNG，它是使用

9、并行端口連接到，它是使用并行端口連接到 PC 的外部設(shè)備，的外部設(shè)備，它可以在每秒鐘生成它可以在每秒鐘生成 20,000 位，這對于大多數(shù)注重安全性的應(yīng)用程序來位，這對于大多數(shù)注重安全性的應(yīng)用程序來說已經(jīng)足夠了。說已經(jīng)足夠了。 另外另外Intel 公司宣布他們將開始在其芯片組中添加基于熱能的硬件公司宣布他們將開始在其芯片組中添加基于熱能的硬件隨機數(shù)發(fā)生器，而且基本上不會增加客戶的成本。迄今為止，已經(jīng)交付隨機數(shù)發(fā)生器，而且基本上不會增加客戶的成本。迄今為止，已經(jīng)交付了一些帶有硬件了一些帶有硬件 PRNG 的的 CPU。 75.1.4 偽隨機數(shù)的評價標(biāo)準(zhǔn) （1）看起來是隨機的，表明它可以通過所有隨

10、機性統(tǒng)計檢驗。）看起來是隨機的，表明它可以通過所有隨機性統(tǒng)計檢驗。 現(xiàn)在的許多統(tǒng)計測試現(xiàn)在的許多統(tǒng)計測試。它們采用了各種形式，但共同思路是它們。它們采用了各種形式，但共同思路是它們?nèi)家越y(tǒng)計方式檢查來自發(fā)生器的數(shù)據(jù)流，嘗試發(fā)現(xiàn)數(shù)據(jù)是否是隨全都以統(tǒng)計方式檢查來自發(fā)生器的數(shù)據(jù)流，嘗試發(fā)現(xiàn)數(shù)據(jù)是否是隨機的。機的。 確保數(shù)據(jù)流隨機性的最廣為人知的測試套件就是確保數(shù)據(jù)流隨機性的最廣為人知的測試套件就是 George Marsaglia 的的 DIEHARD 軟件包（請參閱軟件包（請參閱/ pub/diehard/）。）。另一個適合此類測試的合理軟件包是另一個適

11、合此類測試的合理軟件包是 pLab（請參（請參閱閱http:/random.mat.sbg.ac.at/tests/）。）。 （2）它是不可預(yù)測的。）它是不可預(yù)測的。即使給出產(chǎn)生序列的算法或硬件和所有以即使給出產(chǎn)生序列的算法或硬件和所有以前產(chǎn)生的比特流的全部知識，也不可能通過計算來預(yù)測下一個隨機前產(chǎn)生的比特流的全部知識，也不可能通過計算來預(yù)測下一個隨機比特應(yīng)是什么。比特應(yīng)是什么。 （3）它不能可靠地重復(fù)產(chǎn)生。）它不能可靠地重復(fù)產(chǎn)生。如果用完全同樣的輸入對序列產(chǎn)生如果用完全同樣的輸入對序列產(chǎn)生器操作兩次將得到兩個不相關(guān)的隨機序列。器操作兩次將得到兩個不相關(guān)的隨機序列。 85.2 序列密碼的概念及

12、模型 序列密碼算法將明文逐位轉(zhuǎn)換成密文，如下圖所示。序列密碼算法將明文逐位轉(zhuǎn)換成密文，如下圖所示。m m 密鑰流發(fā)生器（也稱為滾動密鑰發(fā)生器）輸出一系列比特流：密鑰流發(fā)生器（也稱為滾動密鑰發(fā)生器）輸出一系列比特流：K1，K2，K3，Ki 。密鑰流（也稱為滾動密鑰）跟明文比特流，。密鑰流（也稱為滾動密鑰）跟明文比特流，m1，m2，m3，mi ，進行異或運算產(chǎn)生密文比特流。，進行異或運算產(chǎn)生密文比特流。 加密：加密： C i =mi K i 在解密端，密文流與完全相同的密鑰流異或運算恢復(fù)出明文流。在解密端，密文流與完全相同的密鑰流異或運算恢復(fù)出明文流。 解密：解密： m i =C i K i 顯然

13、顯然，mi K i K i =m i9 事實上，事實上，序列密碼算法其安全性依賴于簡單的異或運算和一次序列密碼算法其安全性依賴于簡單的異或運算和一次一密亂碼本。一密亂碼本。密鑰流發(fā)生器生成的看似隨機的密鑰流實際上是確定密鑰流發(fā)生器生成的看似隨機的密鑰流實際上是確定的，在解密的時候能很好的將其再現(xiàn)。的，在解密的時候能很好的將其再現(xiàn)。密鑰流發(fā)生器輸出的密鑰越密鑰流發(fā)生器輸出的密鑰越接近隨機，對密碼分析者來說就越困難。接近隨機，對密碼分析者來說就越困難。 如果密鑰流發(fā)生器每次都生成同樣的密鑰流的話，對攻擊來說，如果密鑰流發(fā)生器每次都生成同樣的密鑰流的話，對攻擊來說，破譯該算法就容易了。破譯該算法就容

14、易了。 假的假的AliceAlice得到一份密文和相應(yīng)的明文，她就可以將兩者異或得到一份密文和相應(yīng)的明文，她就可以將兩者異或恢復(fù)出密鑰流。恢復(fù)出密鑰流?；蛘撸绻袃蓚€用同一個密鑰流加密的密文，或者，如果她有兩個用同一個密鑰流加密的密文，她就可以讓兩者異或得到兩個明文互相異或而成的消息。她就可以讓兩者異或得到兩個明文互相異或而成的消息。這是很容這是很容易破譯的，接著她就可以用明文跟密文異或得出密鑰流。易破譯的，接著她就可以用明文跟密文異或得出密鑰流。 現(xiàn)在，無論她再攔截到什么密文消息，她都可以用她所擁有的現(xiàn)在，無論她再攔截到什么密文消息，她都可以用她所擁有的密鑰流進行解密。密鑰流進行解密。另

15、外，她還可以解密，并閱讀以前截獲到的消息另外，她還可以解密，并閱讀以前截獲到的消息。一旦一旦AliceAlice得到一明文得到一明文/ /密文對，她就可以讀懂任何東西了。密文對，她就可以讀懂任何東西了。10 這就是為什么所有序列密碼也有密鑰的原因。這就是為什么所有序列密碼也有密鑰的原因。密鑰流發(fā)生器的密鑰流發(fā)生器的輸出是密鑰的函數(shù)。輸出是密鑰的函數(shù)。 這樣，這樣，AliceAlice有一個明文有一個明文/ /密文對，但她只能讀到用特定密鑰加密文對，但她只能讀到用特定密鑰加密的消息。密的消息。 更換密鑰，攻擊者就不得不重新分析。更換密鑰，攻擊者就不得不重新分析。 流密碼強度完全依賴于密鑰序列的隨

16、機性隨機性(Randomness)和不可不可預(yù)測性預(yù)測性(Unpredictability)。 核心問題是密鑰流生成器的設(shè)計核心問題是密鑰流生成器的設(shè)計。 保持收發(fā)兩端密鑰流的精確同步是實現(xiàn)可靠解密的關(guān)鍵技術(shù)保持收發(fā)兩端密鑰流的精確同步是實現(xiàn)可靠解密的關(guān)鍵技術(shù)。11流密碼的分類流密碼的分類: 1. 1.自同步序列密碼自同步序列密碼 自同步序列密碼就是密鑰流的每一位是前面固定數(shù)量密文位的自同步序列密碼就是密鑰流的每一位是前面固定數(shù)量密文位的函數(shù)，下圖和下頁圖描述了其工作原理。函數(shù)，下圖和下頁圖描述了其工作原理。其中，內(nèi)部狀態(tài)是前面其中，內(nèi)部狀態(tài)是前面n比特密文的函數(shù)。該算法的密碼復(fù)雜性在于輸出函

17、數(shù)，它收到內(nèi)部比特密文的函數(shù)。該算法的密碼復(fù)雜性在于輸出函數(shù)，它收到內(nèi)部狀態(tài)后生成密鑰序列位。狀態(tài)后生成密鑰序列位。12自同步流密碼自同步流密碼SSSC(Self-Synchronous Stream Cipher) 內(nèi)部狀態(tài)i依賴于(k kI,i-1,mi)，使密文ci不僅與當(dāng)前輸入mi有關(guān)，而且由于ki對i的關(guān)系而與以前的輸入m1, m2 ,mi-1有關(guān)。一般在有限的n級存儲下將與mi-1,mi-n有關(guān)。13特點特點: 密鑰流不僅依賴于種子密鑰和密鑰流產(chǎn)生器的結(jié)構(gòu)，還密鑰流不僅依賴于種子密鑰和密鑰流產(chǎn)生器的結(jié)構(gòu)，還與密文流（或明文流）有關(guān)。初始向量與密文流（或明文流）有關(guān)。初始向量IV在這

18、里相當(dāng)在這里相當(dāng)于初始密文的作用，要求收、發(fā)雙方必須相同。于初始密文的作用，要求收、發(fā)雙方必須相同。 自同步。解密只取決于先前特定數(shù)量的密文字符，因此，自同步。解密只取決于先前特定數(shù)量的密文字符，因此，即使出現(xiàn)刪除、插入等非法攻擊，收方最終都能夠自動即使出現(xiàn)刪除、插入等非法攻擊，收方最終都能夠自動重建同步解密，因而收、發(fā)雙方不再需要外部同步。重建同步解密，因而收、發(fā)雙方不再需要外部同步。 有差錯傳播。因為密鑰流與密文流有關(guān)，所以一個密文有差錯傳播。因為密鑰流與密文流有關(guān)，所以一個密文的傳輸錯誤會影響下面有限個密文的解密。的傳輸錯誤會影響下面有限個密文的解密。 14自同步序列密碼舉例自同步序列密

19、碼舉例例例 假設(shè)種子密鑰為假設(shè)種子密鑰為k=hk=h，之后的密鑰是上一個密文。采用移位密，之后的密鑰是上一個密文。采用移位密碼，明文為碼，明文為cryptographycryptography，列表給出它的加密和解密過程。，列表給出它的加密和解密過程。一個字符的差錯傳播一個字符的差錯傳播 不需要同步不需要同步15 2同步序列密碼同步序列密碼在同步序列密碼中，密鑰流的產(chǎn)生獨立于明文和密文。分組加密的在同步序列密碼中，密鑰流的產(chǎn)生獨立于明文和密文。分組加密的OFBOFB模模式就是一個同步序列加密的例子。式就是一個同步序列加密的例子。1 1）同步要求。在一個同步序列密碼中，發(fā)送方和接收方必須是同步的

20、，）同步要求。在一個同步序列密碼中，發(fā)送方和接收方必須是同步的，用同樣的密鑰且該秘鑰操作在同樣的位置，才能保證解密。如果在傳輸過用同樣的密鑰且該秘鑰操作在同樣的位置，才能保證解密。如果在傳輸過程中密文字符有插入或刪除導(dǎo)致同步丟失，則解密失敗，且只能通過重新程中密文字符有插入或刪除導(dǎo)致同步丟失，則解密失敗，且只能通過重新同步來實現(xiàn)恢復(fù)。同步來實現(xiàn)恢復(fù)。2 2）無錯誤傳輸。在傳輸期間，一個密文字符被改變只影響該字符的恢復(fù)，）無錯誤傳輸。在傳輸期間，一個密文字符被改變只影響該字符的恢復(fù)，不會對后繼字符產(chǎn)生影響。不會對后繼字符產(chǎn)生影響。16 2同步序列密碼同步序列密碼 同步流密碼同步流密碼SSC(Sy

21、nchronous Stream Cipher)： 內(nèi)部狀態(tài)i與明文消息無關(guān)，密鑰流將獨立于明文。特點：特點：對于明文而言，這類加密變換是無記憶的無記憶的。但它是時變的時變的。只有保持兩端精確同步才能正常工作。對主動攻擊時異常敏感而有利于檢測無差錯傳播差錯傳播( (Error Propagation) )17 同步序列密碼同樣可防止密文中的插入和刪除，同步序列密碼同樣可防止密文中的插入和刪除，因為它們會使系統(tǒng)因為它們會使系統(tǒng)失去同步而立即被發(fā)現(xiàn)。失去同步而立即被發(fā)現(xiàn)。然而，卻不能避免單個位被竄改。然而，卻不能避免單個位被竄改。優(yōu)點優(yōu)點：具有自同步能力，強化了其抗統(tǒng)計分析的能力缺點缺點：有n位長

22、的差錯傳播。 密碼設(shè)計者的最大愿望是設(shè)計出一個滾動密鑰生成器，使得密鑰經(jīng)其擴展成的密鑰流序列具有如下性質(zhì)：極大的周期良好的統(tǒng)計特性抗線性分析抗統(tǒng)計分析。18195.3 5.3 線性反饋移位寄存器線性反饋移位寄存器( (linear feedback shift registerlinear feedback shift register，LFSRLFSR) ) nnnnnacacacaca1122111)2(,GFcaii異或表達(dá)式異或表達(dá)式-線性反饋線性反饋如果如果n n級線性反級線性反饋移位寄存器產(chǎn)饋移位寄存器產(chǎn)生的輸出序列的生的輸出序列的周期為周期為2 2n n-1-1，則，則稱為稱為m

23、 m序列產(chǎn)生器。序列產(chǎn)生器。m m序列不僅周期序列不僅周期長，而且偽隨機長，而且偽隨機特性好，這正是特性好，這正是序列密碼的密鑰序列密碼的密鑰流所需要的特性。流所需要的特性。 205.3 線性反饋移位寄存器 產(chǎn)生密鑰序列的最重要部件是線性反饋移位寄存器(LFSR),是因為: (1) LFSR非常適合于硬件實現(xiàn); (2) 能產(chǎn)生大的周期序列; (3) 能產(chǎn)生較好統(tǒng)計特性的序列; (4) 其結(jié)構(gòu)能應(yīng)用代數(shù)方法進行很好的分析. 移位寄存器是流密碼產(chǎn)生密鑰流的一個主要組成部分。移位寄存器是流密碼產(chǎn)生密鑰流的一個主要組成部分。GF(2)上一個上一個n級反饋移位寄存器由級反饋移位寄存器由n個二元存儲器與一

24、個反饋函數(shù)個二元存儲器與一個反饋函數(shù)f(a1,a2,an)組成，如下頁圖所示。組成，如下頁圖所示。 21 每一存儲器稱為移位寄存器的一級，在任一時刻，這些級的內(nèi)容每一存儲器稱為移位寄存器的一級，在任一時刻，這些級的內(nèi)容構(gòu)成該反饋移位寄存器的狀態(tài)，構(gòu)成該反饋移位寄存器的狀態(tài)，每一狀態(tài)對應(yīng)于每一狀態(tài)對應(yīng)于GF(2)上的一個上的一個n維維向量，共有向量，共有2n種可能的狀態(tài)。種可能的狀態(tài)。 每一時刻的狀態(tài)可用每一時刻的狀態(tài)可用n長序列長序列“a1,a2,an ”n維向量維向量“(a1,a2,an)”來表示，來表示，其中其中ai是第是第i級存儲器的內(nèi)容級存儲器的內(nèi)容。 初始狀態(tài)由用戶確定，當(dāng)?shù)诔跏紶顟B(tài)

25、由用戶確定，當(dāng)?shù)趇個移位時鐘脈沖到來時，個移位時鐘脈沖到來時，每一級存每一級存儲器儲器ai都將其內(nèi)容向下一級都將其內(nèi)容向下一級ai-1傳遞，并計算傳遞，并計算f(a1,a2,an)作為下一時作為下一時刻的刻的an。22 反饋函數(shù)反饋函數(shù)f(a1,a2,an)是是n元布爾函數(shù)，元布爾函數(shù)，即即n個變元個變元a1,a2,an 可以可以獨立地取獨立地取0和和1兩個可能的值兩個可能的值，函數(shù)中的運算有邏輯與、邏輯或、邏，函數(shù)中的運算有邏輯與、邏輯或、邏輯補等運算，最后的函數(shù)值也為輯補等運算，最后的函數(shù)值也為0或或1。 例：下例：下圖是一個3級反饋移位寄存器，其初始狀態(tài)為(a1,a2,a3)= (1,0

26、,1)，輸出可由下表求出。 即輸出序列為即輸出序列為101110111011，周期為，周期為4。23 如果如果f(a1,a2,an)是是(a1,a2,an)的線性函數(shù)，則稱之為線性反饋的線性函數(shù)，則稱之為線性反饋移位寄存器移位寄存器LFSR（linear feedback shift register），），否則稱為非線否則稱為非線性移位寄存器。性移位寄存器。此時此時f可寫為：可寫為： f(a1,a2,an)=cna1 cn-1a2 c1an 其中常數(shù)其中常數(shù)ci=0或或1， 是模是模2加法。加法。ci=0或或1可用開關(guān)的斷開和閉可用開關(guān)的斷開和閉合來實現(xiàn)，合來實現(xiàn)，如下圖所示如下圖所示，這樣

27、的線性函數(shù)共有，這樣的線性函數(shù)共有2n個。個。24 輸出序列輸出序列at滿足：滿足：an+t=cnat cn-1at+1 c1an+t-1 其中，其中，t為非負(fù)正整數(shù)。為非負(fù)正整數(shù)。 線性反饋移位寄存器因其實現(xiàn)簡單、速度快、有較為成熟的理線性反饋移位寄存器因其實現(xiàn)簡單、速度快、有較為成熟的理論等優(yōu)點而成為構(gòu)造密鑰流生成器的最重要的部件之一。論等優(yōu)點而成為構(gòu)造密鑰流生成器的最重要的部件之一。例：例：下圖是一個5級線性反饋移位寄存器，其初始狀態(tài)為（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出輸出序列為1001101001000010 101110110001111100110，周

28、期為31。25 在線性反饋移位寄存器中總是假定在線性反饋移位寄存器中總是假定c1,c2,cn中至少有一個不為中至少有一個不為0，否則，否則f(a1,a2,an)0，這樣的話，在，這樣的話，在n個脈沖后狀態(tài)必然是個脈沖后狀態(tài)必然是000，且這個狀態(tài)必將一直持續(xù)下去。，且這個狀態(tài)必將一直持續(xù)下去。 若只有一個系數(shù)不為若只有一個系數(shù)不為0，設(shè)僅有，設(shè)僅有cj不為不為0，實際上是一種延遲裝置，實際上是一種延遲裝置。一般對于。一般對于n級線性反饋移位寄存器，總是假定級線性反饋移位寄存器，總是假定cn=1。 n級線性反饋移位寄存器的狀態(tài)周期小于等于級線性反饋移位寄存器的狀態(tài)周期小于等于2n-1。輸出序列的

29、周。輸出序列的周期與狀態(tài)周期相等，也小于等于期與狀態(tài)周期相等，也小于等于2n-1。只要選擇合適的反饋函數(shù)便。只要選擇合適的反饋函數(shù)便可使序列的周期達(dá)到最大值可使序列的周期達(dá)到最大值2n-1。 定義定義1：n級線性反饋移位寄存器產(chǎn)生的序列級線性反饋移位寄存器產(chǎn)生的序列ai的周期達(dá)到最大的周期達(dá)到最大值值2n-1時，稱時，稱ai為為n級級m序列。序列。26 根據(jù)密碼學(xué)需要，對于線性移位寄存器需考慮以下問題：根據(jù)密碼學(xué)需要，對于線性移位寄存器需考慮以下問題： （1）如何利用級數(shù)盡可能小的線性移位寄存器產(chǎn)生周期長、）如何利用級數(shù)盡可能小的線性移位寄存器產(chǎn)生周期長、統(tǒng)計性能好的序列；統(tǒng)計性能好的序列；

30、（2）已知一個序列）已知一個序列ai，如何構(gòu)造一個盡可能短的線性移位，如何構(gòu)造一個盡可能短的線性移位寄存器來產(chǎn)生它。寄存器來產(chǎn)生它。 因為因為n級線性移位寄存器的輸出序列級線性移位寄存器的輸出序列ai滿足遞推關(guān)系：滿足遞推關(guān)系： an+k=c1an+k-1 c2a n+k-2 cnak，對任何，對任何k1成立。成立。 這種遞推關(guān)系可用一個一元高次多項式這種遞推關(guān)系可用一個一元高次多項式 p(x)=1+c1x+cn-1xn-1cnxn 表示，稱這個多項式為表示，稱這個多項式為LFSR的特征多項式。的特征多項式。 由于由于aiGF(2) (i =1, 2, n)，所以共有，所以共有2n組初始狀態(tài)，

31、即有組初始狀態(tài)，即有2n個遞推序列，個遞推序列，其中非恒零的有其中非恒零的有2n-1個，記個，記2n-1個非零序列的全體為個非零序列的全體為G(p(x)。27 定義定義2：給定序列ai，冪級數(shù) ，稱為該序列的生成函數(shù)。 定義定義3：設(shè)p(x)是GF(2)上的多項式，使p(x)|(xp-1)的最小p稱為p(x)的周期或階。 定理定理1：設(shè)p(x)=1+c1x+cn-1xn-1cnxn是GF(2)上的多項式，G(p(x)中任一序列ai的生成函數(shù)A(x)滿足： A(x)=(x)/p(x)，其中 =(a1+a2x+anxn-1)+c1x(a1+a2x+an1xn-2) + c2x(a1+a2x+an2

32、xn-3)+cn-1xn-1a1。 定理1說明了n級線性移位寄存器的特征多項式和它的生成函數(shù)之間的關(guān)系。 定理定理2：若序列ai的特征多項式p(x)定義在GF(2)上，p是p(x)的周期，則ai的周期r | p。 n級LFSR輸出序列的周期r不依賴于初始條件，而依賴于特征多項式p(x)。我們感興趣的是LFSR遍歷2n-1個非零狀態(tài)，這時序列的周期達(dá)到最大2n-1，這種序列就是m序列。28 例例3：設(shè)設(shè)f(x)=x4+x3+x2+x+1是是GF(2)上的不可約多項式，但是它上的不可約多項式，但是它的輸出序列是的輸出序列是000110001100011，周期是，周期是5，不是，不是m序列。序列。

33、解：f(x)的不可約性由多項式x，x+1， x2+x+1不能整除f(x)而得。對于k5，輸出序列用ak=ak-1a k-2a k-3ak4 檢驗即可。 定義定義4：僅能被非零常數(shù)或者本身的常數(shù)倍除盡，不能被其他多項式整除的多項式稱為不可約多項式。 特征多項式滿足什么條件時，特征多項式滿足什么條件時，LFSR的輸出序列為的輸出序列為m序列。序列。 定理定理3：n級LFSR產(chǎn)生的序列有最大周期2n-1的必要條件是其特征多項式為不可約多項式。 該定理的逆不成立，即LFSR產(chǎn)生的特征多項式為不可約多項式，但其輸出序列不一定是m序列。 29 定義定義5：若n次不可約多項式p(x)的階為2n-1，稱其為n

34、次本原多項式。 定理定理4：ai為n級m序列的充要條件是其特征多項式p(x)為n次本原多項式。 例例4：設(shè)p(x)=x4+x+1,是4次本原多項式，以其為特征多項式的線性移位寄存器的輸出是10010001111010110010001111010,周期是24-1=15的m序列。 解：p(x)|(x15-1),但是不存在l15，使得p(x)|(xl-1)，所以p(x)階是15。 p(x)的不可約性由x，x+1， x2+x+1不能整除p(x)而得，因此p(x)是本原多項式。 對于k5，輸出序列用ak=ak-1ak4 檢驗即可。 雖然雖然n級線性移位寄存器產(chǎn)生的級線性移位寄存器產(chǎn)生的m序列具有良好的

35、偽隨機性，序列具有良好的偽隨機性，但是直接用其構(gòu)造密鑰流序列是極不安全的。因為利用但是直接用其構(gòu)造密鑰流序列是極不安全的。因為利用2n個輸出位個輸出位可以找到它的起始狀態(tài)和特征多項式?？梢哉业剿钠鹗紶顟B(tài)和特征多項式。30 若特征多項式p(x)=x3+x+1，初始狀態(tài)為（101）的移位寄存器產(chǎn)生序列為(101001)。 設(shè)明文為（011010），那么密文為（110011）。破譯者計算mc得到密鑰系列(101001)，那么可以得到下列矩陣方程式： 得到c31，c20，c11， 從而得到特征多項式：p(x)=x3+x+11 23342 34253 451 6k k kckk k kckk k kc

36、k321 101001001001ccc 31線性反饋移位寄存器舉例線性反饋移位寄存器舉例一個周期的輸出序列一個周期的輸出序列100010011010111 100010011010111 m m序列產(chǎn)生器序列產(chǎn)生器序列周期長，偽隨序列周期長，偽隨機特性好。機特性好。LFSRLFSR的結(jié)構(gòu)過于簡的結(jié)構(gòu)過于簡單，只要攻擊者得單，只要攻擊者得到到2n2n位密文和對應(yīng)位密文和對應(yīng)的明文，就可以導(dǎo)的明文，就可以導(dǎo)出出n n級級LFSRLFSR序列產(chǎn)生序列產(chǎn)生器的代數(shù)結(jié)構(gòu)。器的代數(shù)結(jié)構(gòu)。不適宜直接作為不適宜直接作為密密鑰流產(chǎn)生器使用。鑰流產(chǎn)生器使用。325.4 非線性序列簡介 線性移位寄存器序列密碼在已

37、知明文攻擊下是可破譯的這一事實促使線性移位寄存器序列密碼在已知明文攻擊下是可破譯的這一事實促使人們向非線性領(lǐng)域探索。人們向非線性領(lǐng)域探索。目前研究的比較充分的由非線性移位寄存器，目前研究的比較充分的由非線性移位寄存器，對線性移位寄存器進行非線性組合等對線性移位寄存器進行非線性組合等。 為了使密鑰流生成器輸出的二元序列盡可能復(fù)雜，應(yīng)保證其周期盡可為了使密鑰流生成器輸出的二元序列盡可能復(fù)雜，應(yīng)保證其周期盡可能大、線性復(fù)雜度和不可預(yù)測性盡可能高，能大、線性復(fù)雜度和不可預(yù)測性盡可能高，因此常使用多個因此常使用多個LFSR來構(gòu)造來構(gòu)造二元序列，稱每個二元序列，稱每個LFSR的輸出序列為驅(qū)動序列，的輸出序

38、列為驅(qū)動序列，顯然密鑰流生成器輸出顯然密鑰流生成器輸出序列的周期不大于各驅(qū)動序列周期的乘積，序列的周期不大于各驅(qū)動序列周期的乘積，因此，提高輸出序列的線性因此，提高輸出序列的線性復(fù)雜度應(yīng)從極大化其周期開始。復(fù)雜度應(yīng)從極大化其周期開始。 1Geffe序列生成器序列生成器 Geffe序列生成器由序列生成器由3個個LFSR組成（如下圖），其中組成（如下圖），其中LFSR2作為控制生作為控制生成器使用。成器使用。33 當(dāng)當(dāng)LFSR2輸出輸出1時，時，LFSR2與與LFSR1相連接；當(dāng)相連接；當(dāng)LFSR2輸出輸出0時，時，LFSR2與與LFSR3相連接。相連接。 若設(shè)若設(shè)LFSRi的輸出序列為的輸出序列

39、為a(i)k (i=1,2,3)，則輸出序列，則輸出序列bk可以表可以表示為：示為： 123212323kkkkkkkkkkba aaaa aaaa3121ini1323nnnn設(shè)LFSRi的特征多項式分別為ni次本原多項式，且ni兩兩互素，則Geffe序列的周期為 ，線性復(fù)雜度為 。342J-K觸發(fā)器觸發(fā)器 其中，x1和x2分別是J和K端的輸入。1211kkcxxcx J-K觸發(fā)器如下圖所示，它的兩個輸入端分別用J和K表示，其輸出ck不僅依賴于輸入，還依賴于前一個輸出位ck-1，即001110122211012111cacabaacababaaa 在下圖中，令驅(qū)動序列在下圖中，令驅(qū)動序列ak

40、和和bk分分別為別為m級和級和n級級m序列，則有序列，則有 111kkkkkkkkkcabcaabca利用利用J-K觸發(fā)器的非線性序列生成器觸發(fā)器的非線性序列生成器 如果令如果令c-1=0，則輸出序列的最，則輸出序列的最初初3項為：項為： 當(dāng)當(dāng)m與與n互素且互素且a0+b0=1時，序列時，序列ck的周期為的周期為 (2m-1)(2n-1)。353Pless生成器生成器 Pless生成器由生成器由8個個LFSR、4個個J-K觸發(fā)器和觸發(fā)器和1個循環(huán)計數(shù)器構(gòu)成，個循環(huán)計數(shù)器構(gòu)成，由循環(huán)計數(shù)器進行選通控制，如下圖所示。由循環(huán)計數(shù)器進行選通控制，如下圖所示。 假定在時刻假定在時刻t輸出第輸出第t(mo

41、d 4)個單元，則輸出序列為：個單元，則輸出序列為： a a0 0 b b1 1 c c2 2 d d3 3 a a4 4 b b5 5 d d6 6365.鐘控發(fā)生器鐘控發(fā)生器 鐘控發(fā)生器是由控制序列鐘控發(fā)生器是由控制序列（由一個或多個移位寄存器來控制生成）（由一個或多個移位寄存器來控制生成）的當(dāng)前值決定被采樣的序列寄存器移動次數(shù)（即由控制序列的當(dāng)前值的當(dāng)前值決定被采樣的序列寄存器移動次數(shù)（即由控制序列的當(dāng)前值確定采樣序列寄存器的時鐘脈沖數(shù)目）。確定采樣序列寄存器的時鐘脈沖數(shù)目）。 控制序列和被采樣序列可以是源于同一個控制序列和被采樣序列可以是源于同一個LFSR（稱為自控），也（稱為自控），

42、也可以源于不同的可以源于不同的LFSR（稱為他控），（稱為他控），還可以相互控制還可以相互控制（稱為互控）。（稱為互控）。鐘控發(fā)生器示意圖如下圖所示。鐘控發(fā)生器示意圖如下圖所示。37 當(dāng)控制序列當(dāng)前值為當(dāng)控制序列當(dāng)前值為1時，被采樣序列生成器被時鐘驅(qū)動時，被采樣序列生成器被時鐘驅(qū)動k次后次后輸出；輸出；當(dāng)控制序列當(dāng)前值為當(dāng)控制序列當(dāng)前值為0時，被采樣序列生成器被時鐘驅(qū)動時，被采樣序列生成器被時鐘驅(qū)動d次次后輸出。后輸出。 另外，停走式發(fā)生器也是一種鐘控模型，它由另外，停走式發(fā)生器也是一種鐘控模型，它由2個個LFSR組成。組成。其中，其中，LFSR-1控制控制LFSR-2的時鐘輸入。的時鐘輸入。

43、 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)LFSR-1的時間的時間t-1的輸出為的輸出為1時，時，LFSR-2在時間在時間t改變改變狀態(tài)（狀態(tài)（也即也即LFSR-1輸出時鐘脈沖，使輸出時鐘脈沖，使LFSR-2進行輸出并反饋以改進行輸出并反饋以改變移位寄存器的狀態(tài)變移位寄存器的狀態(tài)）。）。 385收縮和自收縮發(fā)生器收縮和自收縮發(fā)生器 收縮發(fā)生器是又控制序列的當(dāng)前值決定被采樣序列移位寄存器收縮發(fā)生器是又控制序列的當(dāng)前值決定被采樣序列移位寄存器是否輸出。是否輸出。 該發(fā)生器由該發(fā)生器由2個個LFSR組成。組成。LFSR-1、LFSR-2分別按各自時鐘分別按各自時鐘運行，運行，LFSR-1在時間在時間t-1時刻的輸出為時刻的

44、輸出為1時，時，LFSR-2在時間在時間t時刻輸時刻輸出為密鑰流，否則舍去。出為密鑰流，否則舍去。 自收縮發(fā)生器從一個自收縮發(fā)生器從一個LFSR抽出抽出2條序列，其中一條為控制序列條序列，其中一條為控制序列，另一條為百采樣序列。，另一條為百采樣序列。當(dāng)控制序列輸出為當(dāng)控制序列輸出為1時，采樣序列輸出為時，采樣序列輸出為密鑰流，否則舍去。密鑰流，否則舍去。 此外，還有多路復(fù)合序列，這類序列也歸結(jié)為非線性組合序此外，還有多路復(fù)合序列，這類序列也歸結(jié)為非線性組合序列。列。39 基于基于LFSR的序列密碼非常適合于硬件實現(xiàn)，但是不特別適合軟的序列密碼非常適合于硬件實現(xiàn)，但是不特別適合軟件實現(xiàn)。件實現(xiàn)。

45、這導(dǎo)致出現(xiàn)了一些關(guān)于序列密碼被計劃用于快速軟件實這導(dǎo)致出現(xiàn)了一些關(guān)于序列密碼被計劃用于快速軟件實現(xiàn)的新建議，因為這些建議大部分具有專利，因此這里不討論它現(xiàn)的新建議，因為這些建議大部分具有專利，因此這里不討論它們的技術(shù)細(xì)節(jié)。們的技術(shù)細(xì)節(jié)。 比較常用的序列密碼是比較常用的序列密碼是A5、SEAL和和RC4序列密碼算法，序列密碼算法，A5是典是典型的基于型的基于LFSR的序列密碼算法，的序列密碼算法，SEAL和和RC4不是基于不是基于LFSR的的序列密碼算法，而是基于分組密碼的輸出反饋模式（序列密碼算法，而是基于分組密碼的輸出反饋模式（OFB）和密）和密碼反饋模式（碼反饋模式（CFB）來實現(xiàn)的。）來

46、實現(xiàn)的。其他不基于其他不基于LFSR的序列密碼生的序列密碼生成器的安全性基于數(shù)論問題的難解性，這些生成器比基于成器的安全性基于數(shù)論問題的難解性，這些生成器比基于LFSR的生成器要慢很多。的生成器要慢很多。40 A5序列密碼算法是利用歐洲數(shù)字蜂窩移動電話（序列密碼算法是利用歐洲數(shù)字蜂窩移動電話（GSM）加密的）加密的序列密碼算法，它用于從用戶手機至基站的連接加密，序列密碼算法，它用于從用戶手機至基站的連接加密，GSM會會話每幀數(shù)據(jù)包含話每幀數(shù)據(jù)包含228比特，比特，A5算法每次會話將產(chǎn)生算法每次會話將產(chǎn)生228比特的密比特的密鑰，算法的密鑰長度為鑰，算法的密鑰長度為64比特，還包含有一個比特，還

47、包含有一個22比特的幀數(shù)。比特的幀數(shù)。A5算法有兩個版本：強算法有兩個版本：強A5/1和弱和弱A5/2。 A5算法是一種典型的基于算法是一種典型的基于LFSR的序列密碼算法，它由三個的序列密碼算法，它由三個LFSR組成，是一種集控制與停走于一體的鐘控模型，但是組成，是一種集控制與停走于一體的鐘控模型，但是A5算算法沒有完全公開，因而各種資料的描述也不盡相同，重要是第二法沒有完全公開，因而各種資料的描述也不盡相同，重要是第二個和第三個個和第三個LFSR的聯(lián)接多項式以及鐘控的位置。的聯(lián)接多項式以及鐘控的位置。 A5算法的算法的3個個LFSR中中LFSR-1、LFSR-2、LFSR-3的級數(shù)分別為的

48、級數(shù)分別為19、22和和23。LFSR-1的反饋抽頭是的反饋抽頭是18、17、16、13，LFSR-2的的反饋抽頭是反饋抽頭是21、20、16、12，LFSR-3的反饋抽頭是的反饋抽頭是22、21、18、17（如下頁圖的數(shù)字表示抽頭的位置）。（如下頁圖的數(shù)字表示抽頭的位置）。 414243SEAL序列密碼算法444546474849 5.5.3 RC4序列密碼體制o RC4是是Ron Rivest 1987年為年為RSA設(shè)計，是一設(shè)計，是一個可變密鑰長度、面向字節(jié)操作的序列密碼個可變密鑰長度、面向字節(jié)操作的序列密碼o 基本思想：基本思想： 對于對于n n位長的字，它總共位長的字，它總共N=2N

49、=2n n個可能的個可能的內(nèi)部置換狀內(nèi)部置換狀 態(tài)矢量態(tài)矢量S S，這些狀態(tài)是保密的，密鑰，這些狀態(tài)是保密的，密鑰流流K K由由S S中中N N個元素按照一定方式選出一個元素而生個元素按照一定方式選出一個元素而生成。每生成一個成。每生成一個K K值，值，S S中的元素就被重新置換一次中的元素就被重新置換一次o 密鑰調(diào)度算法（密鑰調(diào)度算法（KSA）o 偽隨機數(shù)生成算法（偽隨機數(shù)生成算法（PRGA）50密鑰調(diào)度算法KSAo KSA算法描述如下：o For i=0 to N-1 doo Si=i;o j=0;o For i=0 to N-1 doo J=(j+Si+KI mod L) mod N;o

50、 Swap(Si,Sj)51偽隨機數(shù)生成算法PRGAo i=0；o J=0；o While(true）o i=（i+1）mod N；o J=（j+Si) mod N;o Swap(Si,Sj);o T=(Si+Sj) mod N;o Output k=St;52實例535455oRC4目前使用在：o （1）SSL（安全套接字）中廣泛使用o （2）WEP(Wired Equivalent Privacy:有線對等保密) IEEE 802.11o(http:/ 真隨機序列的特性真隨機序列的特性 統(tǒng)計的隨機性。即序列能夠通過數(shù)學(xué)上已知的所有統(tǒng)計的隨機性。即序列能夠通過數(shù)學(xué)上已知的所有的隨機性檢驗，滿

51、足這個要求的序列稱為偽隨機序列。的隨機性檢驗，滿足這個要求的序列稱為偽隨機序列。 不可預(yù)測性。即無論采用何種方法，也無法根據(jù)以不可預(yù)測性。即無論采用何種方法，也無法根據(jù)以前的任意多元素預(yù)測序列的下一個元素。前的任意多元素預(yù)測序列的下一個元素。 不可再生性。即使使用完全相同的輸入?yún)?shù)，也無不可再生性。即使使用完全相同的輸入?yún)?shù)，也無法產(chǎn)生完全相同的輸出序列。法產(chǎn)生完全相同的輸出序列。真隨機序列特性雖好，但難以在實際密碼系統(tǒng)中應(yīng)用。真隨機序列特性雖好，但難以在實際密碼系統(tǒng)中應(yīng)用。實際密碼系統(tǒng)中使用的密鑰流都是偽隨機序列。實際密碼系統(tǒng)中使用的密鑰流都是偽隨機序列。57三、密鑰流的局部隨機性檢驗三、密

52、鑰流的局部隨機性檢驗 1 1、偽隨機序列的統(tǒng)計特性、偽隨機序列的統(tǒng)計特性 戈龍（戈龍（GolombGolomb）提出的三條隨機性公設(shè)：）提出的三條隨機性公設(shè)： 平衡特性。任何隨機的二元周期序列，在一個周平衡特性。任何隨機的二元周期序列，在一個周期期P P內(nèi)，不同元素出現(xiàn)的概率應(yīng)該是相同的。如果內(nèi)，不同元素出現(xiàn)的概率應(yīng)該是相同的。如果P P為為偶數(shù)，一個周期內(nèi)所含有的偶數(shù)，一個周期內(nèi)所含有的“0 0”和和“1 1”的個數(shù)應(yīng)該相的個數(shù)應(yīng)該相等；如果等；如果P P為奇數(shù)，一個周期內(nèi)所含有的為奇數(shù)，一個周期內(nèi)所含有的“0 0”和和“1 1”的個數(shù)應(yīng)該只相差的個數(shù)應(yīng)該只相差1 1個。個。58戈龍（戈龍（

53、GolombGolomb）提出的三條隨機性公設(shè)）提出的三條隨機性公設(shè) 游程特性。游程特性。游程是指一串相同的元素序列，其前導(dǎo)和后繼都不同，游程是指一串相同的元素序列，其前導(dǎo)和后繼都不同，而相同元素的個數(shù)叫做游程的長度。而相同元素的個數(shù)叫做游程的長度。由一串由一串“1 1”構(gòu)成的游程叫做構(gòu)成的游程叫做“1 1”游程（也叫塊組），游程（也叫塊組），由一串由一串“0 0”構(gòu)成的游程叫做構(gòu)成的游程叫做“0 0”游程（也叫間隔）。游程（也叫間隔）。例如，序列例如，序列“11100101110010”有有1 1個長度為個長度為3 3的的“1 1”游程游程（111111）、）、1 1個長度為個長度為2 2的

54、的“0 0”游程（游程（0000）、）、1 1個長度為個長度為1 1的的“1 1”游程（游程（1 1）和）和1 1個長度為個長度為1 1的的“0 0”游程（游程（0 0）。）。任意隨機的二元周期序列，在一個周期任意隨機的二元周期序列，在一個周期P P內(nèi)，長度為內(nèi)，長度為n n的游程數(shù)應(yīng)占游程總數(shù)的的游程數(shù)應(yīng)占游程總數(shù)的1/21/2n n，并且對于每一種長度，并且對于每一種長度，“0 0”游程的個數(shù)應(yīng)和游程的個數(shù)應(yīng)和“1 1”游程的個數(shù)同樣多。游程的個數(shù)同樣多。 59戈龍（戈龍（GolombGolomb）提出的三條隨機性公設(shè)）提出的三條隨機性公設(shè) 自相關(guān)特性。假定自相關(guān)特性。假定S S是一個周期

55、為是一個周期為P P的二元序列，對于任意的二元序列，對于任意固定的固定的，把，把S S的開始的開始P P項（即一個周期）和其平移項（即一個周期）和其平移（一個周（一個周期循環(huán)左移期循環(huán)左移位）后的序列進行比較，并用位）后的序列進行比較，并用A A表示它們對應(yīng)位表示它們對應(yīng)位相同的個數(shù)，用相同的個數(shù)，用D=P-AD=P-A表示它們對應(yīng)位不同的個數(shù)，定義自相表示它們對應(yīng)位不同的個數(shù)，定義自相關(guān)函數(shù)為：關(guān)函數(shù)為：PDAC)(任意隨機的二元周期序列，其自相關(guān)函數(shù)應(yīng)為任意隨機的二元周期序列，其自相關(guān)函數(shù)應(yīng)為 1;0( );0C常數(shù)自相關(guān)特性也可以表述為：異相自相關(guān)函數(shù)是一個常數(shù)。自相關(guān)特性也可以表述為：

56、異相自相關(guān)函數(shù)是一個常數(shù)。 602 2、密鑰流的局部隨機性檢驗、密鑰流的局部隨機性檢驗 頻數(shù)檢驗頻數(shù)檢驗序列檢驗序列檢驗撲克檢驗撲克檢驗自相關(guān)檢驗自相關(guān)檢驗游程檢驗游程檢驗 612 2、密鑰流的局部隨機性檢驗、密鑰流的局部隨機性檢驗 （1 1）頻數(shù)檢驗）頻數(shù)檢驗用來確保密鑰流有大致相等數(shù)量的用來確保密鑰流有大致相等數(shù)量的“0 0”和和“1 1”。假設(shè)被檢驗序列的長度為假設(shè)被檢驗序列的長度為n n比特，其中有比特，其中有n n0 0個個“0 0”和和n n1 1個個“1 1”，計算，計算 nnnx2012)(的數(shù)值并和的數(shù)值并和1 1自由度的自由度的 分布表中分布表中5%5%顯著性水顯著性水平值平值3.8413.841進行比較。若進行比較。若 ，則認(rèn)為通，則認(rèn)為通過了頻數(shù)檢驗，否則，必須舍棄該序列。過了頻數(shù)檢驗，否則，必須舍棄該序列。2x23.841x 622 2、密鑰流的局部隨機性檢驗、密鑰流的局部隨