新編密碼學(xué) 課件 第5章 中外文網(wǎng)絡(luò)數(shù)據(jù)庫檢索

5.1序列密碼的基本原理

5.2反饋移位寄存器

5.3基于LFSR的生成器

5.4非線性反饋移位寄存器

5.5序列密碼的攻擊法

5.6RC4算法

5.7祖沖之算法5.1序列密碼的基本原理5.1.1序列密碼的設(shè)計思想計算機技術(shù)帶來的基本改變是信息的表示。在其內(nèi)部,計算機是以二進制位(0和1)來表示信息的。這樣,所有的信息都必須轉(zhuǎn)換成計算機的位進行存儲和操作。字符是通過ASCII碼(AmericanStandardCodeforInformationInterchange,美國信息交換標(biāo)準(zhǔn)碼)轉(zhuǎn)換成0,1數(shù)串的,這促使人們將加密算法的設(shè)計放在計算機的特征上而不是語言的結(jié)構(gòu)上。也就是說,將加密算法的設(shè)計焦點放在二進制(位)而不是字母上。Shannon證明了一次一密密碼體制是不可破譯的,這意味著,若能夠以一種方式產(chǎn)生一個隨機序列,這一序列由密鑰確定,則可利用這樣的序列進行加密?；?1序列的異或運算,人們提出了序列密碼,其密鑰是一個01隨機序列。序列密碼每次只對明文中的單個位(或字節(jié))進行運算(加密變換),因此,序列密碼的密鑰生成方法是其關(guān)鍵,通常密鑰流由種子密鑰通過密鑰流生成器產(chǎn)生。加密過程所需的密鑰流可以利用以移位寄存器為基礎(chǔ)的電路來產(chǎn)生,這促使線性和非線性移位寄存器理論迅速發(fā)展,加上有效的數(shù)學(xué)工具,從

而

使

得

序

列

密

碼

理

論

迅

速

發(fā)

展。序列密碼的主要原理是通過隨機數(shù)發(fā)生器產(chǎn)生性能優(yōu)良的偽隨機序列(密鑰流),使用該序列加密信息流(逐位加密),得到密文序列。由于每一個明文都對應(yīng)一個隨機的加密密鑰,所以序列密碼在理論上屬于無條件安全的密碼體制。序列密碼的基本加密過程如圖5-1所示。按照加密、解密過程中密鑰流工作方式的不同,序列密碼

一

般

分

為

同

步

序

列

密

碼和自同步序列密碼兩種。1.同步序列密碼在同步序列密碼中,密鑰流的產(chǎn)生完全獨立于消息流(明文流或密文流),如圖5-2所示。在這種工作方式下,如果傳輸過程中丟失一個密文字符,發(fā)送方和接收方就必須使它們的密鑰生成器重新同步,這樣才能正確地加密、解密后續(xù)的序列,否則加密、解密將失敗。圖5-2的操作過程可用如下函數(shù)描述:其中,密鑰流ki

是由種子密鑰k產(chǎn)生的,σi

是密鑰流生成器的內(nèi)部狀態(tài),mi

是明文流,ci是密文流,F是狀態(tài)轉(zhuǎn)移函數(shù),G是密鑰流ki的產(chǎn)生函數(shù),E是同步序列密碼的加密變換,D是同步序列密碼的解密變換。由于同步序列密碼各操作位之間相互獨立,因此應(yīng)用這種方式進行加密、解密時無錯誤傳播,操作過程中產(chǎn)生一位錯誤時只會影響一位,不會影響后續(xù)位,這是同步序列密碼的一個重要特點。同步序列密碼具有以下性質(zhì):(1)同步性:在同步序列密碼中,消息的發(fā)送者和接收者必須同步才能正確地解密,即通信雙方使用相同的密鑰,并對同一位置進行操作。一旦密文字符在傳輸過程中被插入或刪除,系統(tǒng)的同步性被破壞,那么解密過程將失敗。這時只有借助其他附加技術(shù)重建同步,解密過程才能夠繼續(xù)進行。重建同步的技術(shù)包括:重新初始化,在密文序列的規(guī)則間隔中設(shè)置特殊記號,當(dāng)明文消息序列包含足夠的冗余度時,也可以嘗試密鑰流所有可能的偏移。(2)無錯誤傳播性:密文字符在傳輸過程中被修改(未被刪除),并不影響其他密文字符的解密。(3)主動攻擊可檢測性:主動攻擊者對密文字符進行的插入、刪除或重放操作都會立即破壞系統(tǒng)的同步性,從而可能被解密器檢測出來。同時,主動攻擊者可能會有選擇地改動密文字符,并準(zhǔn)確地知道這些改動對明文的影響。所以,必須采用其他的附加技術(shù)保證被加密數(shù)據(jù)的完整性。2.自同步序列密碼與同步序列密碼相比,自同步序列密碼是一種有記憶變換的密碼,如圖5-3所示。每一個密鑰字符是由前面n個密文字符推導(dǎo)出來的(其中n為定值),即在傳輸過程中,如果丟失或更改了一個字符,則這一錯誤就要向前傳播n個字符。因此,自同步序列密碼有錯誤傳播現(xiàn)象。不過,在收到n個正確的密文字符以后,密碼自身會實現(xiàn)重新同步。圖5-3的操作過程可用如下函數(shù)描述:其中,密鑰流ki

是由種子密鑰k產(chǎn)生的,σi是密鑰流生成器的內(nèi)部狀態(tài),mi是明文流,ci是密文流,F是狀態(tài)轉(zhuǎn)移函數(shù),G是密鑰流ki的產(chǎn)生函數(shù),E是同步序列密碼的加密變換,D是同步序列密碼的解密變換。自同步序列密碼具有以下性質(zhì):(1)自同步性:自同步序列密碼在解密過程中依賴固定個數(shù)以前的密文字符,因此,當(dāng)密文字符被插入或刪除時,密碼的自同步性就會體現(xiàn)出來。自同步序列密碼在同步性遭到破壞時,可以自動重建正確的解密過程,而且只有固定數(shù)量的明文字符不可恢復(fù)。(2)錯誤傳播的有限性:假設(shè)一個自同步序列密碼的狀態(tài)依賴于n個以前的密文字符,在密文序列傳輸?shù)倪^程中,當(dāng)一位的密文字符被改動(插入或刪除)時,那么至多會有n位隨后的密文字符解密出錯,然后恢復(fù)正確的解密過程。(3)主動攻擊可檢測性:主動攻擊者對密文字符的任何改動都會引發(fā)一些密文字符的解密出錯,因此增加了被解密器檢測出的可能性。同時,自同步序列密碼在檢測主動攻擊者發(fā)起的對密文字符的插入、刪除、重放等攻擊時更加困難,所以必須采取附加的技術(shù)來保證被加密數(shù)據(jù)的完整性。(4)明文統(tǒng)計擴散性:每個明文字符都會影響其后的整個密文,即明文的統(tǒng)計學(xué)特征被擴散到了密文中。因此,自同步序列密碼對利用明文的冗余度發(fā)起的攻擊有較強的抗攻擊能力。在自同步序列密碼系統(tǒng)中,密文流參與了密鑰流的生成,這使得對密鑰流的分析非常復(fù)雜,從而導(dǎo)致了對自同步序列密碼進行系統(tǒng)的理論分析非常困難。因此,目前應(yīng)用較多的流密碼是自同步序列密碼。使用序列密碼系統(tǒng)的一個關(guān)鍵是要有對應(yīng)的隨機序列,而現(xiàn)實中通過隨機數(shù)發(fā)生器產(chǎn)生的序列只能是一個偽隨機序列,要從數(shù)學(xué)上證明密鑰流生成器是否產(chǎn)生了隨機序列是不現(xiàn)實的,因此需要對生成序列的隨機性進行評價,下節(jié)將給出判斷生成的偽隨機序列具有隨機性的評價指標(biāo)。5.1.2序列隨機性能評價令s=s0,s1,s2,…是一個無窮序列,前n項組成的子序列記為sn=s0,s1,…,sn-1。序列s=s0,s1,s2,…稱為N周期的,對于i≥0,均有si=si+N

。如果存在正整數(shù)N,使得序列s是N周期的,那么序列s稱為周期序列。周期序列的周期定義為使其為N周期序列的最小正整數(shù)N。如果s是周期為N的周期序列,那么子序列sN

為s的一個周期。令s是一個序列,s的一個游程是指s的包含連續(xù)個0或連續(xù)個1的子序列,且其前后均為與其不同的符號。0游程稱為溝,1游程稱為塊。令s=s0,s1,s2,…是一個周期為N的周期序列,s的自相關(guān)系數(shù)C(t)為一個自變量取整數(shù)的函數(shù),定義如下:自相關(guān)系數(shù)是用來衡量序列s和s的t個位置的移位之間的相似性的量,自相關(guān)系數(shù)越小,說明序列s的隨機性能越好。Golomb隨機性假設(shè)包括以下3個條件:(1)在序列的一個周期內(nèi),0和1的個數(shù)至多相差1。(2)在序列的一個周期內(nèi),長為1的游程個數(shù)占總游程數(shù)的

長為2的游程個數(shù)占總游程數(shù)的依此類推,長為i的游程個數(shù)占總游程數(shù)的

且在等長的游程中,0游程和1游程各占一半。(3)自相關(guān)系數(shù)是二值的,即對某個整數(shù)K,有滿足上述3個條件的序列稱為偽隨機序列。其中,條件(1)說明序列s中0和1出現(xiàn)的概率基本相等;條件(2)說明在已知位置n前若干位置上的值的前提下,在第n個位置上出現(xiàn)0和1的概率是相等的;條件(3)說明如果將si

與si+t進行比較,無法得到關(guān)于序列s的實質(zhì)性信息(如周期等)。接下來我們將介紹對長度是n位的二進制序列s=s0,s1,…,sn-1進行隨機性檢驗常用的5個統(tǒng)計測試,它們是判斷二進制序列s是否具有隨機性的一些統(tǒng)計量。(1)頻率測試。頻率該測試的目的是確定s中0和1的個數(shù)是否相等。令n0,n1

分別表示s中0和1的個數(shù)。頻率測試使用的統(tǒng)計量為當(dāng)n≥10時,該統(tǒng)計量近似服從自由度為1的χ2分布。(2)序列測試。序列測試的目的是確定s的子序列00,01,10,11的個數(shù)是否相等。令n0,n1分別表示s中0和1的個數(shù),n00,n01,n10,n11分別表示s中子序列00,01,10,11的個數(shù)。序列測試使用的統(tǒng)計量為當(dāng)n≥21時,該統(tǒng)計量近似服從自由度為2的χ2分布。(3)撲克測試。撲克測試的目的是確定每個部分的長度是m位的序列在s中出現(xiàn)的次數(shù)是否相等。令m是一個滿足

的正整數(shù),且令

將序列s分成k個互不相交的部分,每個部分的長度為m位,令ni為

第i種

長

度

為m位

的

序

列

出

現(xiàn)

的

次數(shù),1≤i≤2m

。撲克測試使用的統(tǒng)計量為該統(tǒng)計量近似服從自由度為2m-1的χ2分布。(4)游程測試。根據(jù)對序列隨機性的要求,在長度為n位的隨機序列中,所期待的長度為i位的0游程(或1游程)的個數(shù)為

。令k為滿足ei≥5的i的最大整數(shù),令Bi,Gi

分別為s中長度為i位的0游程和1游程的個數(shù),1≤i≤k。游程測試使用的統(tǒng)計量為該統(tǒng)計量近似服從自由度為2k-2的χ2分布。(5)自相關(guān)測試。自相關(guān)測試的目的是檢驗序列s與其發(fā)生移位后所形成的序列之間的相關(guān)性。令d為一個固定的整數(shù),序列s與s發(fā)生d個移位后所形成的序列中的不同位數(shù)為

其中

表示異或操作。自相關(guān)測試的統(tǒng)計量為當(dāng)n-d≥10時,該統(tǒng)計量近似服從N(0,1)分布。

5.2反饋移位寄存器由序列隨機性能評價指標(biāo)的介紹可知,對序列密碼的安全性要求越高,相應(yīng)地,對密鑰流的隨機性要求就越高。因此,在設(shè)計密鑰流生成方法時,不僅要考慮安全性,還要考慮以下兩個因素:(1)生成密鑰流的密鑰k應(yīng)該易于分配和管理。(2)密鑰流生成方法應(yīng)該易于快速實現(xiàn)。基于以上分析,下面介紹常用來生成密鑰流的密鑰流生成器的基本部件———反饋移位寄存器。一個反饋移位寄存器由移位寄存器和反饋函數(shù)兩部分組成。移位寄存器是一個位序列,它的長度用位表示,如果移位寄存器的長度是n位,則稱為n位移位寄存器。每次運算的結(jié)果實際只改變序列中的一個值,其中移位寄存器中除最右端的位以外,其余所有位向右移一位,新的最左端位的值根據(jù)寄存器中其他位的值計算得到。移位寄存器的輸出值常常是序列中的最低有效位。移位寄存器的周期是指輸出序列從開始到重復(fù)時的長度。反饋函數(shù)是n元布爾函數(shù),函數(shù)中的運算有邏輯與、邏輯或、邏輯補等運算,最后的函數(shù)值為0或1。5.2.1線性反饋移位寄存器反饋

移

位

寄

存

器,特

別

是

線

性

反

饋

移

位

寄

存

器,是許多密鑰流生成器的基本器件。目前出現(xiàn)的許多密鑰流生成器都使用線性反饋移位寄存器,LFSR的優(yōu)點如下:(1)LFSR非常適合于硬件實現(xiàn)。(2)LFSR可以產(chǎn)生大周期的序列。(3)LFSR產(chǎn)生的序列具有良好的統(tǒng)計特性。(4)LFSR在結(jié)構(gòu)上具有一定的特點,便于利用代數(shù)方法對其進行分析。LFSR的結(jié)構(gòu)如圖54所示。其中每個Ci為0或1,圖中閉合的半圓表示“與”運算。一個長度為L位的線性反饋移位寄存器(LFSR)由0,1,…,L-1共L個級(或延遲單元)和一個時鐘構(gòu)成,每個級都有1位的輸入和1位的輸出,并且可以存儲1位字符;時鐘用于控制數(shù)據(jù)的移動。每個時間單位內(nèi)執(zhí)行下述操作:(1)輸出0級所存儲的字符,作為輸出序列的一部分。(2)對每個i(1≤i≤L-1),將第i級的存儲內(nèi)容移入第i-1級。(3)第L-1級中存儲的新元素稱為反饋比特sj,它由0,1,…,L-1級中的一個固定的子集合的內(nèi)容進行模2相加而得到。圖54所示的線性反饋移位寄存器可以記為<L,C(D)>,其中為特征多項式。若C(D)的次數(shù)為L(即cL=1),則稱相應(yīng)的線性移位寄存器LFSR為非奇異

的。對

于

每

一

個

若

第i級

的

初

始

存儲值為si∈{0,1},則稱

為線性移位寄存器LFSR的初始狀態(tài)。如果已知線性反饋移

位

寄

存

器LFSR的

結(jié)

構(gòu)

如

圖5-4所

示,相

應(yīng)

的

初

始

狀

態(tài)

為

那么輸出序列s=s0,s1,s2,…可以通過以下遞推公式唯一確定:5.2.2LFSR輸出序列的周期與隨機性線性反饋移位寄存器輸出序列的性質(zhì)完全由其反饋函數(shù)決定。L級線性反饋移位寄存器最多有2L

個不同的狀態(tài)。若其初始狀態(tài)為0,則其后續(xù)狀態(tài)恒為0;若其初始狀態(tài)不為0,則其后續(xù)狀態(tài)不會為0。因此,L級線性反饋移位寄存器的輸出序列的周期不大于2L-1(不考慮0狀態(tài)),只要選擇合適的反饋函數(shù),便可使輸出序列的周期達到最大值2L-1。由線性反饋移位寄存器LFSR產(chǎn)生序列的周期性有以下結(jié)論:(1)線性反饋移位寄存器LFSR<L,C(D)>的每一個輸出序列是周期的,當(dāng)且僅當(dāng)特征多項式C(D)的次數(shù)為L。在線性反饋移位寄存器LFSR<L,C(D)>是奇異的(即C(D)的次數(shù)小于L)情況下,并不是所有的LFSR<L,C(D)>輸出序列都有周期。在忽略掉輸出序列中開始的固定有限項后,得到的新序列是周期的,但此時的序列周期不會達到2L-1。(2)對于線性反饋移位寄存器LFSR<L,C(D)>,設(shè)C(D)∈?2[D]是一個L次的特征多項式。①

若C(D)在?2[D]上是不可約的,那么非奇異的LFSR<L,C(D)>的2L-1個非零狀態(tài)中的每一個都可以產(chǎn)生一個周期為N的輸出序列,其中N為C(D)在?2[D]中能夠整除1+DN

的最小正整數(shù)。②

若C(D)為本原多項式,那么非奇異的LFSR<L,C(D)>的2L-1個非零狀態(tài)中的每一個均能產(chǎn)生具有最大可能周期為2L-1的輸出序列。根據(jù)以上結(jié)論,我們給出m序列的定義:若C(D)∈?2[D]是一個L次的本原多項式,則<L,C(D)>稱為最大長度LFSR。最大長度LFSR在非零狀態(tài)下的輸出稱為m序列。根據(jù)m序列的定義,例5.2中,C(D)=1+D+D4

為?2[D]中的一個本原多項式,所以相應(yīng)的LFSR<4,1+D+D4>的輸出序列是一個m序列,其最大可能周期為N=24-1=15。m序列有以下性質(zhì):(1)設(shè)k為整數(shù)(1≤k≤L),且

的長度為2L+k-2的任意子序列,那么

的每一個長度為k的非零子序列恰好出現(xiàn)2L-k

次,而且

的長度為k的零子序列恰好出現(xiàn)2L-k-1次。也就是說,具有固定長度且長度至多為L的模型分布幾乎是均勻的。(2)m序列滿足Golomb隨機性假設(shè)。下面對性質(zhì)(2)進行分析。當(dāng)線性反饋移位寄存器的初始狀態(tài)相同時,輸出序列也是相同的,所以LFSR在產(chǎn)生m序列的過程中必須遍歷2L-1個非0狀態(tài)中的每一個,然后才會出現(xiàn)重復(fù)。這2L-1個狀態(tài),在s1位有2L-1

個1,其余2L-1-1個是0,所以滿足Golomb隨機性假設(shè)的第一個條件。由于線性反饋移位寄存器LFSR中不可能出現(xiàn)全0狀態(tài),所以輸出序列不會出現(xiàn)0的L游程,而且必然有一個1的L游程,但不可能有長度大于L的1游程。因為如果出現(xiàn)一個1的L+1游程,必然會有兩個全是1的狀態(tài)相鄰,根據(jù)LFSR的設(shè)計原理,這是不可能的。所以可以知道值為1、長度為L的游程必然出現(xiàn)在以下的情況中,即當(dāng)以上的L+2位通過移位寄存器時,會依次產(chǎn)生以下狀態(tài):由于0,1,1,…,1,1和1,1,…,1,1,0這兩個狀態(tài)只能各出現(xiàn)一次,所以不會有其他的1的L-1游程。同理,輸出序列中會出現(xiàn)0的L-1游程,即它產(chǎn)生1,0,0,…,0,0和0,0,…,0,0,1兩個狀態(tài)。當(dāng)L=2時,以上分析過程已經(jīng)驗證了所有的情況。當(dāng)L>2時,設(shè)r為不大于L-2的任意一個正整數(shù),則任何1的r游程就意味著輸出序列中存在序列為了計算1的r游程的數(shù)目,只要計算左邊的r+2個比特的狀態(tài)數(shù)目就可以了。因為任一個1的r游程總會在通過移位寄存器時處在當(dāng)前的位置,其余的L-r-2位可以是由0和1構(gòu)成的任何狀態(tài),所以1的r游程的數(shù)目是2L-r-2。于是在每一個周期中出現(xiàn)1的游程的數(shù)目為同樣,0游程的數(shù)目也是2L-2。因此m序列滿足Golomb隨機性假設(shè)的第二個條件。根據(jù)換行定理,即周期為2L-1的m序列,其異相關(guān)自相關(guān)函數(shù)等于m序列滿足Golomb隨機性假設(shè)的第三個條件。以上結(jié)論表明,應(yīng)用線性反饋移位寄存器LFSR產(chǎn)生的m序列具有良好的隨機性能。5.3基于LFSR的生成器線性反饋移位寄存器被廣泛應(yīng)用于序列密碼的密鑰流生成器中。線性反饋移位寄存器產(chǎn)生的序列具有較好的統(tǒng)計特性,非常適合用硬件來實現(xiàn)。此外線性反饋移位寄存器已經(jīng)用代數(shù)技術(shù)分析過,因此可靠性較高?；贚FSR的序列密碼的基本結(jié)構(gòu)如圖5-6所示。如果線性反饋移位寄存器產(chǎn)生的是m序列,則算法的密鑰取決于LFSR的初始狀態(tài)和LFSR的參數(shù)c1,c2,…,cL的取值情況。鑒于線性反饋移位寄存器LFSR對應(yīng)的特征多項式是本原多項式,而L次的本原多項式共有λ(L)個(λ(L)=?(2L-1)/L,(?

為歐拉函數(shù)),LFSR的非零初始狀態(tài)共有2L-1個,所以應(yīng)用線性反饋移位寄存器LFSR產(chǎn)生m序列的算法密鑰共有λ(L)×(2L-1)個。對于以上所有可能的密鑰,基于LFSR的密鑰流生成器應(yīng)該具備以下性質(zhì):(1)大周期。(2)大線性復(fù)雜度。(3)較好的統(tǒng)計特性。以上性質(zhì)被認(rèn)為是密鑰流生成器在密碼學(xué)上計算安全的必要條件。要達到以上要求,在設(shè)計線性反饋移位寄存器LFSR時應(yīng)該考慮以下因素:(1)為保證密鑰流生成器產(chǎn)生的輸出序列具有大周期,設(shè)計相應(yīng)的線性反饋移位寄存器LFSR時,應(yīng)該始終選擇最大長度的LFSR,也就是說,設(shè)計的LFSR應(yīng)該具有形式<L,C(D)>,其中C(D)∈?2[D]是一個L次的本原多項式。(2)基于線性反饋移位寄存器的密鑰流生成器中的LFSR可能存在已知的或者秘密的特征多項式。對于LFSR已知的特征多項式,秘密密鑰通常由LFSR的初始內(nèi)容構(gòu)成;對于秘密的特征多項式,密鑰流生成器的秘密密鑰通常由初始內(nèi)容和特征多項式兩者共同構(gòu)成。所以對于長度為L而且具有秘密特征多項式的線性反饋移位寄存器LFSR,應(yīng)該從域?2[D]上所有次數(shù)為L的本原多項式所組成的集合中隨機均勻地選擇特征多項式。(3)在實際設(shè)計線性反饋移位寄存器時,通常使用秘密特征多項式的形式。因

為

這

種設(shè)計能夠更好地抵御使用預(yù)計算來分析特殊特征多項式的攻擊,而且采用秘密特征多項式設(shè)計LFSR產(chǎn)生的輸出序列也更能經(jīng)得起統(tǒng)計分析。雖然基于秘密特征多項式設(shè)計的LFSR需要額外的電路來完成硬件實現(xiàn),但是由于這種形式的LFSR具有更好的安全性,所以以上缺點可以通過選擇更短的線性反饋移位寄存器進行彌補。(4)在設(shè)計線性反饋移位寄存器時,為了便于實現(xiàn),可以選擇稀疏的LFSR,也就是說,采用的特征多項式中只有很少一部分系數(shù)是非零的。這樣就只需要在LFSR的各種狀態(tài)之間構(gòu)造很少的特征多項式來計算反饋位。當(dāng)然,某些使用稀疏的特征多項式設(shè)計的LFSR可能會受到一些特殊的攻擊。以上討論了基于線性反饋移位寄存器的密鑰流發(fā)生器設(shè)計LFSR應(yīng)該考慮的因素。接下來我們給出基于線性反饋移位寄存器設(shè)計密鑰流生成器的方法。使用一個或多個線性反饋移位寄存器時,通常要求LFSR具有不同的長度和不同的特征多項式。對于采用兩個LFSR的密鑰流生成器,當(dāng)兩個LFSR的長度互素,并且它們的特征多項式是本原多項式時,密鑰流生成器得到的輸出序列將具有最大的長度。密鑰流生成器的密鑰是LFSR的初始狀態(tài),每一次取LFSR中的一位,然后將LFSR移位一次(也稱為一個時鐘)。密鑰流生成器的輸出位是LFSR中一些位的函數(shù),該函數(shù)一般要求是非線性的,稱為組合函數(shù),相應(yīng)的整個密鑰流生成器也稱為一個組合生成器(如果密鑰流生成器的輸出位是單個LFSR的函數(shù),則相應(yīng)密鑰流生成器稱為過濾生成器)。下面通過介紹幾種基本的組合生成器,來進一步說明基于線性反饋移位寄存器的密鑰流生成器的工作原理。1.Geffe生成器Geffe生成器使用了3個線性反饋移位寄存器,它們以非線性的方式組合,其中2個LFSR作為復(fù)合器的輸入,第3個LFSR用來控制復(fù)合器的輸出。Geffe生成器的基本結(jié)構(gòu)如圖5-7所示。設(shè)s1,s2,s3分別是Geffe生成器中3個LFSR的輸出位,則相應(yīng)的Geffe生成器的輸出表示為上式意味著,當(dāng)LFSR-1輸出1時,LFSR-1與LFSR-2相連;當(dāng)LFSR-1輸出0時,LFSR-1與LFSR-3相連。如果已知3個LFSR的長度分別為n1,n2,n3,那

么

相

應(yīng)

的Geffe生成器的線性復(fù)雜性為該Geffe生成器的周期是3個LFSR周期的最小公倍數(shù),所以當(dāng)3個LFSR的本原的特征多項式的次數(shù)互素時,相應(yīng)的Geffe生成器的周期就是3個LFSR周期的乘積,即Geffe生成器在密碼學(xué)意義上是不安全的,因為第1個和第3個LFSR的狀態(tài)信息會在Geffe生成器的輸出序列中表現(xiàn)出來。2.Jennings生成器生成器使用了2個線性反饋移位寄存器，通過1個復(fù)合器將2個LFSR組合起來，其基本結(jié)構(gòu)如圖5-8所示。在Jennings生成器中,LFSR-1控制的復(fù)合器為每一個輸出位選擇LFSR-2的一位,用一個函數(shù)將LFSR-2的輸出映射到復(fù)合器的輸入。密鑰流生成器的密鑰是2個線性反饋移位寄存器和映射函數(shù)的初始狀態(tài)。3.J-K觸發(fā)器J-K觸發(fā)器也使用了2個線性反饋移位寄存器,其中LFSR-1是一個m級的線性反饋移位寄存器,LFSR-2是一個n級的線性反饋移位寄存器。J-K觸發(fā)器的基本結(jié)構(gòu)如圖5-9所示。J-K觸發(fā)器的工作表如表5-2所示。設(shè)J-K觸發(fā)器中線性反饋移位寄存器LFSR-1的輸出序列為a1,a2,…,周期為m,線性反饋移位寄存器LFSR-2的輸出序列為b1,b2,…,周期為n,其中m與n互素,J-K觸發(fā)器的輸出序列為c1,c2,…。由于J-K觸發(fā)器的輸出序列中的位一般都與其前一位有關(guān),通常令c0=0,所以J-K觸發(fā)器的輸出序列可以通過以下遞推公式計算:J-K觸發(fā)器產(chǎn)生的輸出序列雖然具有較好的隨機性,但當(dāng)輸出序列的部分值已知時,通過一定的方法可以給出以上遞推方程的部分解。例如,知道J-K觸發(fā)器輸出序列中cn

和cn+1的值時,通過遞推關(guān)系,有

上述例子說明,通過cn

和cn+1的值可以計算出an+1和bn+1

的值,所以J-K觸發(fā)器密鑰流生成機制也存在安全問題。4.普勒斯體制普勒斯(Pless)生成器是由8個線性反饋移位寄存器組成4個J-K觸發(fā)器,外加1個循環(huán)計數(shù)器連接而成的。普勒斯生成器的基本結(jié)構(gòu)如圖5-10所示。在普勒斯生成器中,循環(huán)計數(shù)器的作用是決定在每一個時間脈沖作用下的輸出單元。這個密鑰流生成器的密鑰是由8個線性反饋移位寄存器和它們相應(yīng)的初始狀態(tài)、J-K觸發(fā)器的初始狀態(tài)與輸出單元的順序組成的。普勒斯提出的8個線性反饋移位寄存器的級數(shù)不僅使得各個線性反饋移位寄存器對之間達到級數(shù)互素,而且達到各個J-K觸發(fā)器的輸出周期,從而使得最終的輸出序列的周期為以上各周期的乘積。5.4非線性反饋移位寄存器本節(jié)介紹一些有關(guān)非線性反饋移位寄存器的基本結(jié)論。(1)如果一個函數(shù)有n個二元輸入和1個二元輸出,則稱該函數(shù)為包含n個變元的布爾函數(shù)。在包含n個變元的函數(shù)中共有22n

個不同的布爾函數(shù),所以相應(yīng)的n級移位寄存器中共有22n個不同的反饋函數(shù),而n級線性反饋移位寄存器對應(yīng)的線性反饋函數(shù)只有2n種,因此在反饋移位寄存器中,非線性反饋函數(shù)比線性反饋函數(shù)的數(shù)量更多。應(yīng)強調(diào)的是,并非所有這些非線性反饋函數(shù)都能產(chǎn)生具有良好特性的輸出序列。關(guān)于一般的非線性反饋移位寄存器的研究目前仍然處于初級階段,應(yīng)用較多的仍然是在線性反饋移位寄存器的基礎(chǔ)上進行非線性化的設(shè)計。(2)長度為L的反饋移位寄存器(FSR)由標(biāo)號為0,1,…,L-1的L級(或延遲單元)構(gòu)成,其中每一級均可存儲1位,并且有1位的輸入和輸出,而且還有一個時鐘來控制數(shù)據(jù)的運動。FSR在每一個時間單位內(nèi)執(zhí)行以下操作:①

將第0級中的存儲內(nèi)容輸出構(gòu)成輸出序列的一部分。②

對每一個i(1≤i≤L-1),將第i級的存儲內(nèi)容移入第i-1級。③

第L-1級中存儲的新元素為反饋比特sj=f(sj-1,sj-2,…,sj-L),其中反饋函數(shù)f是一個布爾函數(shù),且1≤i≤L,sj-1為第L-i級中先前存儲的位。如果對每一個j(1≤i≤L-1),第i級中所存儲的初始內(nèi)容為si∈{0,1},則相應(yīng)的[sL-1,sL-2,…,s1,s0]稱為該反饋移位寄存器的初始狀態(tài)。圖5-11給出了一個反饋移位寄存器的基本結(jié)構(gòu)。當(dāng)反饋函數(shù)f是一個線性函數(shù)時,FSR就是一個線性反饋移位寄存器;否則,FSR是一個非線性反饋移位寄存器。已知反饋移位寄存器的結(jié)構(gòu)如圖5-11所示,相應(yīng)的初始狀態(tài)為[sL-1,sL-2,…,s1,s0],那么FSR的輸出序列s=s0,s1,s2,…可以通過以下遞推公式唯一確定:(3)如果反饋移位寄存器的每一個輸出序列都是周期序列,則該反饋移位寄存器稱為非奇異的。當(dāng)反饋移位寄存器的反饋函數(shù)為f(sj-1,sj-2,…,sj-L)時,當(dāng)且僅當(dāng)反饋函數(shù)f具有以下形式:則稱該反饋移位寄存器是非奇異的。一個長度為L的非奇異反饋移位寄存器的輸出序列的周期最大為2L

。(4)如果一個長度為L的非奇異反饋移位寄存器的輸出序列的周期均為2L,那么該反饋移位寄存器稱為deBruijnFSR,相應(yīng)的輸出序列稱為deBruijn序列。5.5序列密碼的攻擊法5.5.1插入攻擊法插入攻擊法很簡單,它要求能在明文流中插入一個位,并能截獲密文流。假設(shè)原始明文流、密鑰流和密文流分別為如果Oscar能在明文流中插入一個已知位m,例如在第一位后面插入m,然后用同樣的密鑰加密后發(fā)送,結(jié)果將為由于Oscar知道插入的已知位和兩個密鑰流,通過構(gòu)建一個等組,可以求解出密鑰和實際的明文。第一個求解出的密鑰位是k2,這是由于

知道了k2,Oscar就可以利用

得到原來的第二位m;知道了m2,Oscar就可以利用

得到k3。依次類推,就可以得到以下方程組:5.5.2位串匹配攻擊法位串匹配攻擊法是可能詞攻擊方法中的一種。對于基于LFSR的序列密碼密鑰流生成器,由于線性反饋移位寄存器是從初始狀態(tài)通過線性遞推關(guān)系產(chǎn)生密鑰流的,所以該密鑰流生成方法容易受到已知明文攻擊。假設(shè)Oscar已經(jīng)有了明文消息

序

列{x1,x2,…,xn}和

與

其

對

應(yīng)

的

密

文

消

息

序

列{y1,y2,…,yn},其中yi≡(xi+si)mod2(1≤i≤n),{s1,s2,…,sn}是由LFSR產(chǎn)生的密鑰流,則密鑰流si≡(xi+yi)mod2(1≤i≤n)。如果Oscar再知道LFSR的級數(shù)m,那么Oscar只需要計算{c0,c1,…,cm-1}的值就能夠重構(gòu)整個密鑰流。對于任意的i≥1,有以上方程是一個含有m個未知數(shù){c0,c1,…,cm-1}的線性方程。如果n≥2m,則根據(jù)明文和密文消息之間的對應(yīng)關(guān)系,我們可以得到包含以上m個未知數(shù){c0,c1,…,cm-1}的m個線性方程,利用這些方程就可以解出這m個未知數(shù)。m個線性方程可以用矩陣形式表示,即如果以上方程組的系數(shù)矩陣在模2運算的逆矩陣存在,則可得到方程組的解為當(dāng)然,如果m是LFSR的級數(shù),那么方程組(5-12)的系數(shù)矩陣在模2運算下就一定是可逆的。5.6RC4算法RC4是由麻省理工學(xué)院的RonRivest開發(fā)的,它是世界上使用最為廣泛的序列加密算法之一,已被應(yīng)用于MicrosoftWindows,LotusNotes和其他軟件應(yīng)用程序中。RC4使用安全套接字層(SecureSocketsLayer,SSL)來保護互聯(lián)網(wǎng)的信息流,也被應(yīng)用于無線系統(tǒng)來保護無線連接的安全。RC4的一個優(yōu)點是在軟件中很容易實現(xiàn)。RC4的大小隨參數(shù)n的值而變化。RC4可以實現(xiàn)一個秘密的內(nèi)部狀態(tài),對n位數(shù),有2n

種可能。通常取n=8,于是RC4可以生成28=256個元素的數(shù)組S。RC4的每個輸出都是數(shù)組S中的一個隨機元素,通過KSA(Key-SchedulingAlgorithm,密鑰調(diào)度法)與PRGA(PseudoRandom-GenerationAlgorithm,偽隨機生成算

法)實

現(xiàn)。KSA用

來

設(shè)置S的初始排列,PRGA用于選取隨機元素并修改S的原始排列順序。KSA首先對S進行初始化,取S(i)=i(i=0,…,255),然后選取一系列隨機數(shù)字,并將其加載到密鑰數(shù)組K(0)~K(255)上,根據(jù)密鑰數(shù)組K實現(xiàn)對S的初始隨機化。根據(jù)初始化S(i)=i(i=0,…,255)得到初始序列S,那么根據(jù)選取的密鑰數(shù)組K(0),K(1),…,K(255)對S進行初始隨機化的過程描述如下:首先初始化i=0,j=0,然后計算j≡(j+S(i)+K(i))mod256,將S(i)與S(j)互換位置,同時更新i=1,計算j≡(j+S(i)+K(i))mod256,將S(i)與s(j)互換位置。重復(fù)以上過程,直到i=255,就可以得到一組隨機的整數(shù)序列S。當(dāng)完成了對序列S的初始隨機化后,就可以開始進行偽隨機生成算法,PRGA為密鑰流選取字節(jié),即從序列S中選取元素,同時修改序列S的值以便下一次選取。密鑰流的選取過程描述如下:首先初始化i=0,j=0;然后計算i≡(i+1)mod256,j≡(j+S(i))mod256;將S(i)與S(j)互換位置,同時計算t≡(S(i)+S(j))mod256,并在此基礎(chǔ)上,選取密鑰值為k=S(t)。重復(fù)以上過程,就可以得到一組密鑰流序列。應(yīng)用得到的密鑰流序列即可以實現(xiàn)相應(yīng)的序列密碼。以下以n=3為例,介紹RC4算法的整個過程。當(dāng)n=3時,數(shù)組S只有23=8個元素,此時對S進行初始化,得到S={0,1,2,3,4,5,6,7}Alice和Bob選取一個密鑰,該密鑰是由整數(shù)0~7構(gòu)成的一個隨機序列。假設(shè)本例中選取的密鑰為{3,6,5,2},則可以得到相應(yīng)的密鑰數(shù)組K為K={3,6,5,2,3,6,5,2}在此基礎(chǔ)上,對序列S進行隨機化處理,過程如下:初始化i=0,j=0,計算j≡(0+S(0)+K(0))mod8≡3,將數(shù)組S中的S(0)與S(3)互換,得到S={3,1,2,0,4,5,6,7}更新i=1,計算j≡(3+S(1)+K(1))mod8≡2,將數(shù)組S中的S(1)與S(2)互換,得到S={3,2,1,0,4,5,6,7}更新i=2,計算j≡(2+S(2)+K(2))mod8≡0,將數(shù)組S中的S(2)與S(0)互換,得到S={1,2,3,0,4,5,6,7}更新i=3,計算j≡(0+S(3)+K(3))mod8≡2,將數(shù)組S中的S(3)與S(2)互換,得到S={1,2,0,3,4,5,6,7}更新i=4,計算j≡(2+S(4)+K(4))mod8≡1,將數(shù)組S中的S(4)與S(1)互換,得到S={1,4,0,3,2,5,6,7}更新i=5,計算j≡(1+S(5)+K(5))mod8≡4,將數(shù)組S中的S(5)與S(4)互換,得到S={1,4,0,3,5,2,6,7}更新i=6,計算j≡(4+S(6)+K(6))mod8≡7,將數(shù)組S中的S(6)與S(7)互換,得到S={1,4,0,3,5,2,7,6}更新i=7,計算j≡(7+S(7)+K(7))mod8≡7,將數(shù)組S中的S(7)與S(7)互換,得到S={1,4,0,3,5,2,7,6}經(jīng)過以上運算,最終得到經(jīng)過隨機化處理后的結(jié)果序列S={1,4,0,3,5,2,7,6}。根據(jù)得到的序列S,就可以產(chǎn)生相應(yīng)的隨機數(shù)序列。具體過程如下:首先初始化i=0,j=0,計算i≡(i+1)mod8≡1,j≡(j+S(i))mod8≡4,將數(shù)組S中的S(1)與S(4)互換,得到S={1,5,0,3,4,2,7,6}然后計算t≡(S(i)+S(j))mod8≡5,k=S(t)=2,于是產(chǎn)生的第一個隨機數(shù)字為2,其二進制表示為10。重復(fù)以上過程,就可以得到相應(yīng)的密鑰流序列。常見的RC4算法對應(yīng)n=8,這種情況下,系統(tǒng)的初始密鑰是長為256的整數(shù)序列,該序列對應(yīng)0~255的一個排列,因此RC4算法的密鑰空間大小為256!,相當(dāng)于21600,使得采用窮盡搜索的攻擊方式變得不可能。但是,攻擊者可以利用RC4算法中的一些弱點進行密碼分析,例如,RC4算法的計算生成過程會導(dǎo)致一些密鑰永遠不可能產(chǎn)生,如j=i+1和S(j)=1,現(xiàn)在已經(jīng)證明,這類密鑰的數(shù)量約為22n

。因此當(dāng)n=8時,RC4算法密鑰空間的實際大小約為5.7祖沖之算法5.7.1祖沖之算法的描述祖沖之算法(即ZUC算法)是一個面向字設(shè)計的序列密碼算法,該算法由中國科學(xué)院數(shù)據(jù)保護和通信安全研究中心研制,是目前第四代移動通信加密的國際標(biāo)準(zhǔn)之一。3GPP(The3rdGenerationPartnershipProject,第三代合作伙伴計劃)于2004年啟動LTE(LongTermEvolution,長期演進計劃)的研究,該計劃于2010年被指定為第四代無線通信標(biāo)準(zhǔn),即4G通信標(biāo)準(zhǔn)。LTE是第四代無線通信的主要技術(shù)之一,其中安全技術(shù)是LTE的關(guān)鍵技術(shù),預(yù)留了16個密碼算法接口。2009年5月,以祖沖之算法為核心的加密算法128-EEA3和完整性

算

法128-EIA3在3GPP立

項,并

申

請

成

為3GPP的

算

法

標(biāo)

準(zhǔn)。2011年9月128-EEA3和128-EIA3正式成為3GPP加密和完整性算法標(biāo)準(zhǔn),與以AES和SNOW3G為核心的加密算法和完整性算法共同占用LTE中的3個算法接口,這是我國第一個自主研制的成為國際標(biāo)準(zhǔn)的密碼算法。2012年3月,祖沖之算法成為我國國家秘密行業(yè)標(biāo)準(zhǔn)(標(biāo)準(zhǔn)

號GM/T0001—2012),2016年10月,發(fā)

布

祖

沖

之

算

法

為

國

家

標(biāo)

準(zhǔn)(標(biāo)

準(zhǔn)

號GB/T33133—2016)。祖沖之算法是一個基于字設(shè)計的同步序列密碼算法,種子密鑰SK和初始向量IV的長度為128位,在SK和IV的控制下,算法每次輸出一個32位的密鑰字。祖沖之算法采用過濾生成器結(jié)構(gòu)設(shè)計,在線性驅(qū)動部分采用素域GF(232-1)上的m序列作為源序列,具有周期大、隨機統(tǒng)計特性好等特點,且在二元域上是非線性的,可以很好地抵抗二元域上的密碼分析。算法的過濾部分采用有限狀態(tài)機設(shè)計,內(nèi)部包含記憶單元,使用分組密碼算法中擴散和混淆特性良好的線性變換與S-盒,可提供較高的非線性?，F(xiàn)有分析結(jié)果表明,祖沖之算法具有非常高的安全性。祖沖之算法的結(jié)構(gòu)包含3層,如圖5-12所示。其中,上層為線性反饋移位寄存器LFSR,中間層為比特重組BR層,下層為非線性函數(shù)F。1.LFSR層LFSR由16個31位的字單元變量si(i=0,1,…,15)構(gòu)成,定義在素域GF(232-1)上,其特征多項式為這是素域GF(232-1)上的一個本原多項式。設(shè){at}(t≥0)為LFSR生成的序列,則對任意t≥0,有:2.比特重組BR層比特重組BR層為中間過渡層,該層從LFSR的8個寄存器單元s0,s2,s5,s7,s9,s11,s14,s15中抽取128位組成4個32位的字X0,X1,X2,X3,供下層的非線性函數(shù)F和密鑰導(dǎo)出函數(shù)使用。BR的具體計算過程如下: