《應用密碼學》課件第4章

第4章序列密碼體制4.1密碼學中的隨機數(shù)4.2序列密碼的概念及模型4.3線性反饋移位寄存器4.4非線性序列簡介4.5常用的序列密碼算法 4.1密碼學中的隨機數(shù)

為什么在密碼學中要討論隨機數(shù)的產(chǎn)生？因為許多密碼系統(tǒng)的安全性都依賴于隨機數(shù)的生成，例如DES加密算法中的密鑰，RSA加密和數(shù)字簽名中的素數(shù)。所有這些方案都需要足夠長度并且要“隨機”的數(shù)，即使得任何特定值被選中的概率足夠小，防止對方根據(jù)概率來優(yōu)化搜索策略。例如DES密鑰空間大小為256，如果密鑰k是隨機產(chǎn)生的，那么對方要嘗試256個可能的密鑰值。但是如果密鑰k這樣產(chǎn)生：選取一個16位隨機秘鑰s，然后利用一個復雜但是公開的函數(shù)f將其擴展為56位密鑰k，這時對方只要嘗試216個可能的密鑰值就能找到真正密鑰。4.1.1隨機數(shù)的使用

序列密碼的保密性完全取決于密鑰的隨機性。如果密鑰是真正的隨機數(shù)，則這種體制在理論上就是不可破譯的。但這種方式所需的密鑰量大得驚人，在實際中是不可行的。因此，目前一般采用偽隨機序列來代替隨機序列作為密鑰序列，也就是序列存在著一定的循環(huán)周期。這樣序列周期的長短就成為保密性的關鍵。如果周期足夠長，就會有比較好的保密性。現(xiàn)在周期小于1010的序列很少被采用，周期長達1050的序列也并不少見。4.1.2偽隨機數(shù)產(chǎn)生器

計算機上的隨機數(shù)產(chǎn)生器并不是隨機的，因為計算機一直是具有完全確定性的機器，特別在行為隨機性方面表現(xiàn)得不盡人意。所以當程序員需要一個或一組真正的隨機數(shù)時，他們必須通過各種方式近似地生成隨機數(shù)。

什么是偽隨機數(shù)生成器（PRNG）？假定需要生成介于1和10之間的隨機數(shù)，每一個數(shù)出現(xiàn)的幾率都是一樣的。理想情況下，應生成0到1之間的一個值，不考慮以前的值，這個范圍中的每一個值出現(xiàn)的幾率都是一樣的，然后再將該值乘以10。因為在0和1之間有無窮多個值，計算機不能提供這樣的精度。為了編寫代碼來實現(xiàn)類似于前面提到的算法，常見情況下，偽隨機數(shù)生成器生成0到N之間的一個整數(shù)，返回的整數(shù)再除以N。得出的數(shù)字總是處于0和1之間。對生成器隨后的調(diào)用采用第一次運行產(chǎn)生的整數(shù)，并將它傳給一個函數(shù)，以生成0到N之間的一個新整數(shù)，然后再將新整數(shù)除以N返回。這意味著，由任何偽隨機數(shù)生成器返回的數(shù)目會受到0到N之間整數(shù)數(shù)目的限制。

在大多數(shù)的常見隨機數(shù)發(fā)生器中，N是232-1（大約等于40億），對于32位數(shù)字來說，這是最大的值。換句話說，我們經(jīng)常碰到的這類生成器能夠至多生成40億個可能值，而40億的個數(shù)根本不算大。偽隨機數(shù)生成器將作為“種子”的數(shù)當作初始整數(shù)傳給函數(shù)。由偽隨機數(shù)生成器返回的每一個值完全由它返回的前一個值所決定。因此，最初的種子決定了這個隨機數(shù)序列。如果知道用于計算任何一個值的那個整數(shù)，那么就可以算出從這個生成器返回的下一個值。

偽隨機數(shù)生成器是一個生成完全可預料的數(shù)列（稱為流）的確定性程序。一個編寫得很好的PRNG可以創(chuàng)建一個序列，而這個序列的屬性與許多真正隨機數(shù)的序列的屬性是一樣的。例如：（1）PRNG可以以相同幾率在一個范圍內(nèi)生成任何數(shù)字；

（2）PRNG可以生成帶任何統(tǒng)計分布的流；

（3）由PRNG生成的數(shù)字流不具備可辨別的模。4.1.3基于密碼算法的隨機數(shù)產(chǎn)生器

1．使用軟件方法的隨機數(shù)產(chǎn)生器

一個常用的隨機數(shù)產(chǎn)生器是屬于線性擬合生成器一類的。這類生成器相當普遍，它們采用很具體的數(shù)學公式：

Xn+1=(aXn+b)modc即第n+1個數(shù)等于第n個數(shù)乘以某個常數(shù)a，再加上常數(shù)b。如果結(jié)果大于或等于某個常數(shù)c，那么通過除以c，并取它的余數(shù)來將這個值限制在一定范圍內(nèi)。注意，a、b和c通常都是質(zhì)數(shù)。DonaldKnuth在“TheArtofComputerProgramming”一書中詳細介紹了對于這些常數(shù)，如何挑選好的值。

2．使用硬件方法的隨機數(shù)產(chǎn)生器

真正的隨機數(shù)發(fā)生器是非確定的，在計算機上執(zhí)行非確定性事情的唯一方法是從一些自然的隨機過程中收集數(shù)據(jù)。最好的一種方法涉及使用電子Geiger計數(shù)器，每次當它檢測到放射性衰變時，它就會生成一個脈沖。衰變之間的時間是一個實足的、純粹的隨機部分。尤其是，沒有人可以預測到下一次衰變的時間大于還是小于自上次衰變以來的時間。那就產(chǎn)生了一位隨機信息。目前生成隨機數(shù)的幾種硬件設備都是用于商業(yè)用途。得到廣泛使用的設備是ComScireQNG，它是使用并行端口連接到PC的外部設備，它可以在每秒鐘生成20000位，這對于大多數(shù)注重安全性的應用程序來說已經(jīng)足夠了。

另外，Intel公司宣布他們將開始在其芯片組中添加基于熱能的硬件隨機數(shù)發(fā)生器，而且基本上不會增加客戶的成本。迄今為止，已經(jīng)交付了一些帶有硬件RNG的CPU。4.1.4偽隨機數(shù)的評價標準

如果一序列產(chǎn)生器是偽隨機的，它應有下面的性質(zhì)：

（1）看起來是隨機的，表明它可以通過所有隨機性統(tǒng)計檢驗。

現(xiàn)在有許多統(tǒng)計測試。它們采用了各種形式，但共同思路是它們?nèi)家越y(tǒng)計方式檢查來自發(fā)生器的數(shù)據(jù)流，嘗試發(fā)現(xiàn)數(shù)據(jù)是否是隨機的。

確保數(shù)據(jù)流隨機性的最廣為人知的測試套件就是GeorgeMarsaglia的DIEHARD軟件包（請參閱/pub/diehard/）。另一個適合此類測試的合理軟件包是pLab（請參閱http://random.mat.sbg.ac.at/tests/）。（2）它是不可預測的。即使給出產(chǎn)生序列的算法或硬件和所有以前產(chǎn)生的比特流的全部知識，也不可能通過計算來預測下一個隨機比特應是什么。

（3）它不能可靠地重復產(chǎn)生。如果用完全同樣的輸入對序列產(chǎn)生器操作兩次將得到兩個不相關的隨機序列。

4.2序列密碼的概念及模型

序列密碼算法將明文逐位轉(zhuǎn)換成密文。該算法最簡單的應用如圖4－1所示。密鑰流發(fā)生器（也稱為滾動密鑰發(fā)生器）輸出一系列比特流：K1，K2，K3，…，Ki。密鑰流（也稱為滾動密鑰）跟明文比特流P1，P2，P3，…，Pi，進行異或運算產(chǎn)生密文比特流，即Ci=Pi⊕Ki

（4－1）圖4－1序列密碼在解密端，密文流與完全相同的密鑰流異或運算恢復出明文流。Pi

=Ci⊕Ki

（4-2）系統(tǒng)的安全性完全依靠密鑰流發(fā)生器的內(nèi)部機制。如果它的輸出是無窮無盡的“0”序列，那么密文就是明文，系統(tǒng)沒有加密功能。如果它產(chǎn)生的是一個重復性的16比特模式，那么該算法僅是一個可忽略安全性的異或運算。如果是一系列無盡的隨機流，那就是一次一密亂碼本和非常完美的安全。實際的序列密碼算法其安全性依賴于簡單的異或運算和一次一密亂碼本。密鑰流發(fā)生器生成的看似隨機的密鑰流實際上是確定的，在解密的時候能很好地將其再現(xiàn)。密鑰流發(fā)生器輸出的密鑰越接近隨機，對密碼分析者來說就越困難。

如果密鑰流發(fā)生器每次都生成同樣的密鑰流的話，對攻擊來說，破譯該算法就容易了。

假的Alice得到一份密文和相應的明文，他就可以將兩者異或恢復出密鑰流?；蛘撸绻袃蓚€用同一個密鑰流加密的密文，他就可以讓兩者異或得到兩個明文互相異或而成的消息。這是很容易破譯的，接著他就可以用明文跟密文異或得出密鑰流?，F(xiàn)在，無論他再攔截到什么密文消息，他都可以用她所擁有的密鑰流進行解密。另外，他還可以解密，并閱讀以前截獲到的消息。一旦Alice得到一明文—密文對，他就可以讀懂任何東西了。

這就是為什么所有序列密碼也有密鑰的原因。密鑰流發(fā)生器的輸出是密鑰的函數(shù)。這樣，Alice有一個明文—密文對，但他只能讀到用特定密鑰加密的消息。更換密鑰，攻擊者就不得不重新分析。序列密碼算法對加密那些永不結(jié)束的通信數(shù)據(jù)流是特別有用的：如兩臺計算機之間的T1連接。

1．自同步序列密碼

自同步序列密碼就是密鑰流的每一位是前面固定數(shù)量密文位的函數(shù)，圖4－2描述了其工作原理。其中，內(nèi)部狀態(tài)是前面n比特密文的函數(shù)。該算法的密碼復雜性在于輸出函數(shù)，它收到內(nèi)部狀態(tài)后生成密鑰序列位。

因為內(nèi)部狀態(tài)完全依賴前面n個密文位，所以解密密鑰流發(fā)生器在收到n個密文位后自動跟加密密鑰流發(fā)生器同步。

在該模式的智能化應用中，每個消息都以隨機的n位報頭開始。這個報頭被加密、傳輸、解密，在n位密文之前整個解密是不正確的，直到之后兩個密鑰流發(fā)生器同步。自同步密碼的缺點是錯誤擴散。傳輸中每一個密文位被竄改，解密密鑰流發(fā)生器就有n位密鑰流位不能正確生成。因此，一位密文錯誤就會導致n位相應的明文錯誤，直到內(nèi)部狀態(tài)里面不再有該錯誤位。圖4－2自同步密鑰流發(fā)生器

2．同步序列密碼

在同步序列密碼中密鑰流是獨立于消息流而產(chǎn)生的。加密端密鑰流發(fā)生器一位接一位地產(chǎn)生密鑰，在解密端另一個發(fā)生器產(chǎn)生出完全相同的密鑰。兩個密鑰發(fā)生器同步以后，這種一致就開始了。如果其中一個發(fā)生器跳過一個周期或者一個密文位在傳輸過程中丟失了，那么錯誤后面的每一個密文字符都不能正確解密。

如果錯誤不幸發(fā)生了，發(fā)方和收方就必須在繼續(xù)進行之前使兩個密鑰發(fā)生器重新同步。他們必須這樣做以保證密鑰流的任意部分不會重復，重新設置發(fā)生器回到前一個狀態(tài)，然而這個簡單的法子是不行的。這也有好的一面，同步密碼并不擴散傳輸錯誤。如果有一位在傳輸中改變了，比丟失一位可能性大的多，那么只有該位不能正確解密。所有進程和結(jié)果都不會受影響。

由于在加解密兩端密鑰流發(fā)生器必須產(chǎn)生同樣的輸出，所以它必須是確定的。因為它是用有限狀態(tài)機器實現(xiàn)的（如計算機），密鑰序列終會重復。這些密鑰流發(fā)生器被稱為是周期性的。除一次一密亂碼本外，所有密鑰流發(fā)生器都是周期性的。發(fā)生器的周期必須非常長，要比密鑰更換之前發(fā)生器所能輸出的位的長度還要長得多。如果其周期比明文還要短，那么明文的不同部分將用同樣的加密——這是一個嚴重的弱點。如果密碼分析者熟悉這樣的一批明文，他就可以恢復出密鑰流，然后恢復出更多的明文。即使分析者僅有密文，他也可以用同一密鑰流加密的不同部分密文相異或得到明文跟明文的異或。這只是一個有非常長密鑰的單一異或運算罷了。

周期需要多長取決于應用。用于加密連續(xù)T1連接通信的密鑰發(fā)生器每天加密237比特。那么它的周期應該比這個數(shù)大幾個數(shù)量級，盡管密鑰每天都要更換。如果周期足夠長，你僅僅需要每周甚至每月才更換密鑰一次。同步序列密碼同樣可防止密文中的插入和刪除，因為它們會使系統(tǒng)失去同步而立即被發(fā)現(xiàn)。然而，卻不能避免單個位被竄改。就像CFB模式下的分組密碼算法，Mallory更換數(shù)據(jù)流中的某個比特，如果他熟悉明文，他就可以使那些比特被解密成他想要的。后面的比特仍被正確地解密，所以在很多應用中Mallory仍可進行某些毀壞。 4.3線性反饋移位寄存器

移位寄存器是流密碼產(chǎn)生密鑰流的一個主要組成部分。GF(2)上一個n級反饋移位寄存器由n個二元存儲器與一個反饋函數(shù)f(a1，a2，…，an)組成，如圖4－3所示。圖4－3

GF(2)上的n級反饋移位寄存器每一存儲器稱為移位寄存器的一級，在任一時刻，這些級的內(nèi)容構(gòu)成該反饋移位寄存器的狀態(tài)，每一狀態(tài)對應于GF(2)上的一個n維向量，共有2n種可能的狀態(tài)。

每一時刻的狀態(tài)可用n長序列“a1，a2，…，an”的n維向量“(a1，a2，…，an)”來表示，其中ai是第i級存儲器的內(nèi)容。

初始狀態(tài)由用戶確定，當?shù)趇個移位時鐘脈沖到來時，每一級存儲器ai都將其內(nèi)容向下一級ai-1傳遞，并計算f(a1，a2，…，an)作為下一時刻的an。

反饋函數(shù)f(a1，a2，…，an)是n元布爾函數(shù)，即n個變元a1，a2，…，an可以獨立地取0和1這兩個可能的值，函數(shù)中的運算有邏輯與、邏輯或、邏輯補等運算，最后的函數(shù)值也為0或1。例4-1：圖4-4是一個3級反饋移位寄存器，其初始狀態(tài)為(a1,a2,a3)=(1,0,1)，輸出可由表4-1求出。

即輸出序列為101110111011…，周期為4。

如果f(a1,a2,…,an)是(a1,a2,…,an)的線性函數(shù)，則稱之為線性反饋移位寄存器LFSR（linearfeedbackshiftregister），否則稱為非線性移位寄存器。此時f可寫為：f(a1,a2,…,an)=cna1

cn-1a2

…

c1an圖4-4是一個3級反饋移位寄存器圖4－5

GF(2)上的n級線性反饋移位寄存器輸出序列{at}滿足an+k=cnat

cn-1at+1

…

c1an+t-1其中t為非負整數(shù)。線性反饋移位寄存器因其實現(xiàn)簡單、速度快、有較為成熟的理論等優(yōu)點而成為構(gòu)造密鑰流生成器的最重要的部件之一。

例4－2圖4－6是一個5級線性反饋移位寄存器，其初始狀態(tài)為（a1，a2，a3，a4，a5）=(1，0，0，1，1)，可求出輸出序列為1001101001000010101110110001111100110…，周期為31。圖4－6一個5級線性反饋移位寄存器在線性反饋移位寄存器中，總是假定c1，c2，…，cn中至少有一個不為0，否則f(a1，a2，…，an)≡0，這樣的話，在n個脈沖后狀態(tài)必然是00…0，且這個狀態(tài)必將一直持續(xù)下去。若只有一個系數(shù)不為0，設僅有cj不為0，實際上是一種延遲裝置。一般對于n級線性反饋移位寄存器，總是假定cn=1。

n級線性反饋移位寄存器的狀態(tài)周期小于等于2n-1。輸出序列的周期與狀態(tài)周期相等，也小于等于2n-1。只要選擇合適的反饋函數(shù)便可使序列的周期達到最大值2n-1。定義4－1

n級線性反饋移位寄存器產(chǎn)生的序列{ai}的周期達到最大值2n-1時，稱{ai}為n級m序列。

根據(jù)密碼學的需要，對于線性移位寄存器，主要考慮下面兩個問題：

（1）如何利用級數(shù)盡可能小的線性移位寄存器產(chǎn)生周期長、統(tǒng)計性能好的序列；

（2）已知一個序列{ai}，如何構(gòu)造一個盡可能短的線性移位寄存器來產(chǎn)生它。我們首先需要介紹一些相關的代數(shù)學知識，因篇幅有限，部分定理不做證明。因為n級線性移位寄存器的輸出序列{ai}滿足遞推關系：an+k=c1an+k-1

c2a

n+k-2

…

cnak對任何k≥1均成立。這種遞推關系可用一個一元高次多項式p(x)=1+c1x+…＋cn-1xn-1＋cnxn

表示，稱這個多項式為LFSR的特征多項式。由于ai∈GF(2)(i=1,2,…,n)，所以共有2n組初始狀態(tài)，即有2n個遞推序列，其中非恒零的有2n-1個，記2n-1個非零序列的全體為G(p(x))。

定義4－4僅能被非零常數(shù)或者本身的常數(shù)倍除盡，不能被其他多項式整除的多項式稱為不可約多項式。

定理4－3

n級LFSR產(chǎn)生的序列有最大周期2n-1的必要條件是其特征多項式為不可約多項式。

該定理的逆不成立，即LFSR產(chǎn)生的特征多項式為不可約多項式，但其輸出序列不一定是m序列。例如下面的例4－3證明存在特征多項式為不可約多項式，但其輸出序列不一定是m序列。解得c3＝1，c2＝0，c1＝1從而得到特征多項式p(x)=x3+x+1 4.4非線性序列簡介

1．Geffe序列生成器

Geffe序列生成器由3個LFSR組成（如圖4－7），其中LFSR2作為控制生成器使用。當LFSR2輸出1時，LFSR2與LFSR1相連接；當LFSR2輸出0時，LFSR2與LFSR3相連接。若設LFSRi的輸出序列為{a(i)k}(i=1，2，3)，則輸出序列{bk}可以表示為：圖4－7Geffe序列生成器圖

2．J－K觸發(fā)器

J－K觸發(fā)器如圖4－8所示，它的兩個輸入端分別用J和K表示，其輸出ck不僅依賴于輸入，還依賴于前一個輸出位ck-1，即其中x1和x2分別是J和K端的輸入。圖4－8

J－K觸發(fā)器在圖4－9中，令驅(qū)動序列{ak}和{bk}分別為m級和n級m序列，則有圖4－9利用J－K觸發(fā)器的非線性序列生成器如果令c-1=0，則輸出序列的最初3項為當m與n互素且a0+b0=1時，序列{ck}的周期為(2m-1)(2n-1)。

3．Pless生成器

Pless生成器由8個LFSR、4個J－K觸發(fā)器和1個循環(huán)計數(shù)器構(gòu)成，由循環(huán)計數(shù)器進行選通控制，如圖4－10所示。假定在時刻t輸出第t(mod4)個單元，則輸出序列為：a0b1c2d3a4b5d6圖4－10Pless生成器4．鐘控發(fā)生器

鐘控發(fā)生器是由控制序列（由一個或多個移位寄存器來控制生成）的當前值決定被采樣的序列寄存器的移動次數(shù)（即由控制序列的當前值確定采樣序列寄存器的時鐘脈沖數(shù)目）?？刂菩蛄泻捅徊蓸有蛄锌梢允窃从谕粋€LFSR（稱為自控），也可以源于不同的LFSR（稱為他控），還可以相互控制（稱為互控）。鐘控發(fā)生器示意圖如圖4－11所示。圖4－11鐘控發(fā)生器模型鐘控發(fā)生器模型中典型的是(k，d)－鐘控發(fā)生器。設控制序列為x，被采樣的序列為y，則輸出序列z表示為：當控制序列當前值為1時，被采樣序列生成器被時鐘驅(qū)動k次后輸出；當控制序列當前值為0時，被采樣序列生成器被時鐘驅(qū)動d次后輸出。另外，停走式發(fā)生器也是一種鐘控模型，它由兩個LFSR組成。其中，LFSR1控制LFSR2的時鐘輸入。當且僅當LFSR1在時刻t-1的輸出為1時，LFSR2在時刻t改變狀態(tài)（也即LFSR1輸出時鐘脈沖，使LFSR2進行輸出并反饋以改變移位寄存器的狀態(tài)）。

5．收縮和自收縮發(fā)生器

收縮發(fā)生器是由控制序列的當前值決定被采樣序列移位寄存器是否輸出。該發(fā)生器由2個LFSR組成。LFSR1、LFSR2分別按各自的時鐘運行，LFSR1在t-1時刻的輸出為1時，LFSR2在t時刻輸出為密鑰流，否則舍去。

自收縮發(fā)生器從一個LFSR中抽出2條序列，其中一條為控制序列，另一條為采樣序列。當控制序列輸出為1時，采樣序列輸出為密鑰流，否則舍去。

此外，還有多路復合序列，這類序列也歸結(jié)為非線性組合序列。

4.5常用的序列密碼算法

4.5.1

A5序列密碼算法

A5序列密碼算法是利用歐洲數(shù)字蜂窩移動電話（GSM）加密的序列密碼算法，它用于從用戶手機至基站的聯(lián)接加密，GSM會話的每幀數(shù)據(jù)包含228比特，A5算法每次會話將產(chǎn)生228比特的密鑰，算法的密鑰長度為64比特，還包含有一個22比特的幀數(shù)。A5算法有兩個版本：強A5/1和弱A5/2。

A5算法是一種典型的基于LFSR的序列密碼算法，它由三個LFSR組成，是一種集控制與停走于一體的鐘控模型，但是A5算法沒有完全公開，因而各種資料的描述也不盡相同，重要的是第二個和第三個LFSR的聯(lián)接多項式以及鐘控的位置。

A5算法的3個LFSR中LFSR1、LFSR2、LFSR3的級數(shù)分別為19、22和23。LFSR1的反饋抽頭是18、17、16、13，LFSR2的反饋抽頭是21、20、16、12，LFSR3的反饋抽頭是22、21、18、17（如圖4－12中的數(shù)字表示抽頭的位置）。因此，LFSR1、LFSR2、LFSR3的生成多項式分別為：三個線性反饋移位寄存器的生成多項式均為本原多項式。圖4－12

A5算法

A5算法的密鑰產(chǎn)生過程如下：

（1）先將64比特密鑰注入LFSR；

（2）再將22比特的幀數(shù)與LFSR的反饋值模2加注入LFSR（以上LFSR正常驅(qū)動）；

（3）LFSR開始停走鐘控；

（4）舍去產(chǎn)生的100比特輸出；

（5）產(chǎn)生114比特作為密鑰輸出；

（6）舍去產(chǎn)生的100比特輸出；

（7）產(chǎn)生114比特作為密鑰輸出。4.5.2

SEAL序列密碼算法

SEAL（Software－OptimizedEncryptionAlgorithm）序列密碼算法是IBM公司的P.Rogaway和D.Coppersmith設計的易于軟件實現(xiàn)的序列密碼算法，它是面向32位處理器的，需要8個32位的寄存器和約8MB的內(nèi)存，它不是傳統(tǒng)意義上基于LFSR的序列密碼算法，而是一個偽隨機函數(shù)簇（PRF），它將明文的位置變成一個隨機串。給定160比特長的密鑰a和32比特的n，SEAL將擴展成L比特的函數(shù)與a(n)。設計第n個明文為xn，xn的長度為L比特，SEAL用密鑰a將n加密成長度為L比特的SEAL(a,n,L)，則位置n的明文xn的密文為〈n,xnSEAL(a,n,L)〉。下面描述SEAL算法的第3版（SEAL3.0）。運用SHA-1對整數(shù)進行雜湊就得到160比特的散列值：圖4－13SEAL算法的內(nèi)循環(huán)初始化部分是基于n、l的使用表T、R對A、B、C、D和n1、n2、n3、n4進行初始化。算法描述如下：對給定的密鑰a，密文xn的位置n及x