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

5.1序列密碼的基本原理

5.2反饋移位寄存器

5.3基于LFSR的生成器

5.4非線性反饋移位寄存器

5.5序列密碼的攻擊法

5.6RC4算法

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

而

使

得

序

列

密

碼

理

論

迅

速

發(fā)

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

一

般

分

為

同

步

序

列

密

碼和自同步序列密碼兩種。1.同步序列密碼在同步序列密碼中,密鑰流的產(chǎn)生完全獨(dú)立于消息流(明文流或密文流),如圖5-2所示。在這種工作方式下,如果傳輸過程中丟失一個(gè)密文字符,發(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是同步序列密碼的解密變換。由于同步序列密碼各操作位之間相互獨(dú)立,因此應(yīng)用這種方式進(jìn)行加密、解密時(shí)無(wú)錯(cuò)誤傳播,操作過程中產(chǎn)生一位錯(cuò)誤時(shí)只會(huì)影響一位,不會(huì)影響后續(xù)位,這是同步序列密碼的一個(gè)重要特點(diǎn)。同步序列密碼具有以下性質(zhì):(1)同步性:在同步序列密碼中,消息的發(fā)送者和接收者必須同步才能正確地解密,即通信雙方使用相同的密鑰,并對(duì)同一位置進(jìn)行操作。一旦密文字符在傳輸過程中被插入或刪除,系統(tǒng)的同步性被破壞,那么解密過程將失敗。這時(shí)只有借助其他附加技術(shù)重建同步,解密過程才能夠繼續(xù)進(jìn)行。重建同步的技術(shù)包括:重新初始化,在密文序列的規(guī)則間隔中設(shè)置特殊記號(hào),當(dāng)明文消息序列包含足夠的冗余度時(shí),也可以嘗試密鑰流所有可能的偏移。(2)無(wú)錯(cuò)誤傳播性:密文字符在傳輸過程中被修改(未被刪除),并不影響其他密文字符的解密。(3)主動(dòng)攻擊可檢測(cè)性:主動(dòng)攻擊者對(duì)密文字符進(jìn)行的插入、刪除或重放操作都會(huì)立即破壞系統(tǒng)的同步性,從而可能被解密器檢測(cè)出來(lái)。同時(shí),主動(dòng)攻擊者可能會(huì)有選擇地改動(dòng)密文字符,并準(zhǔn)確地知道這些改動(dòng)對(duì)明文的影響。所以,必須采用其他的附加技術(shù)保證被加密數(shù)據(jù)的完整性。2.自同步序列密碼與同步序列密碼相比,自同步序列密碼是一種有記憶變換的密碼,如圖5-3所示。每一個(gè)密鑰字符是由前面n個(gè)密文字符推導(dǎo)出來(lái)的(其中n為定值),即在傳輸過程中,如果丟失或更改了一個(gè)字符,則這一錯(cuò)誤就要向前傳播n個(gè)字符。因此,自同步序列密碼有錯(cuò)誤傳播現(xiàn)象。不過,在收到n個(gè)正確的密文字符以后,密碼自身會(huì)實(shí)現(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)自同步性:自同步序列密碼在解密過程中依賴固定個(gè)數(shù)以前的密文字符,因此,當(dāng)密文字符被插入或刪除時(shí),密碼的自同步性就會(huì)體現(xiàn)出來(lái)。自同步序列密碼在同步性遭到破壞時(shí),可以自動(dòng)重建正確的解密過程,而且只有固定數(shù)量的明文字符不可恢復(fù)。(2)錯(cuò)誤傳播的有限性:假設(shè)一個(gè)自同步序列密碼的狀態(tài)依賴于n個(gè)以前的密文字符,在密文序列傳輸?shù)倪^程中,當(dāng)一位的密文字符被改動(dòng)(插入或刪除)時(shí),那么至多會(huì)有n位隨后的密文字符解密出錯(cuò),然后恢復(fù)正確的解密過程。(3)主動(dòng)攻擊可檢測(cè)性:主動(dòng)攻擊者對(duì)密文字符的任何改動(dòng)都會(huì)引發(fā)一些密文字符的解密出錯(cuò),因此增加了被解密器檢測(cè)出的可能性。同時(shí),自同步序列密碼在檢測(cè)主動(dòng)攻擊者發(fā)起的對(duì)密文字符的插入、刪除、重放等攻擊時(shí)更加困難,所以必須采取附加的技術(shù)來(lái)保證被加密數(shù)據(jù)的完整性。(4)明文統(tǒng)計(jì)擴(kuò)散性:每個(gè)明文字符都會(huì)影響其后的整個(gè)密文,即明文的統(tǒng)計(jì)學(xué)特征被擴(kuò)散到了密文中。因此,自同步序列密碼對(duì)利用明文的冗余度發(fā)起的攻擊有較強(qiáng)的抗攻擊能力。在自同步序列密碼系統(tǒng)中,密文流參與了密鑰流的生成,這使得對(duì)密鑰流的分析非常復(fù)雜,從而導(dǎo)致了對(duì)自同步序列密碼進(jìn)行系統(tǒng)的理論分析非常困難。因此,目前應(yīng)用較多的流密碼是自同步序列密碼。使用序列密碼系統(tǒng)的一個(gè)關(guān)鍵是要有對(duì)應(yīng)的隨機(jī)序列,而現(xiàn)實(shí)中通過隨機(jī)數(shù)發(fā)生器產(chǎn)生的序列只能是一個(gè)偽隨機(jī)序列,要從數(shù)學(xué)上證明密鑰流生成器是否產(chǎn)生了隨機(jī)序列是不現(xiàn)實(shí)的,因此需要對(duì)生成序列的隨機(jī)性進(jìn)行評(píng)價(jià),下節(jié)將給出判斷生成的偽隨機(jī)序列具有隨機(jī)性的評(píng)價(jià)指標(biāo)。5.1.2序列隨機(jī)性能評(píng)價(jià)令s=s0,s1,s2,…是一個(gè)無(wú)窮序列,前n項(xiàng)組成的子序列記為sn=s0,s1,…,sn-1。序列s=s0,s1,s2,…稱為N周期的,對(duì)于i≥0,均有si=si+N

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

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

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

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

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

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

的正整數(shù),且令

將序列s分成k個(gè)互不相交的部分,每個(gè)部分的長(zhǎng)度為m位,令ni為

第i種

長(zhǎng)

度

為m位

的

序

列

出

現(xiàn)

的

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

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

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

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

其中

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

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

移

位

寄

存

器,特

別

是

線

性

反

饋

移

位

寄

存

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

的。對(duì)

于

每

一

個(gè)

若

第i級(jí)

的

初

始

存儲(chǔ)值為si∈{0,1},則稱

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

位

寄

存

器LFSR的

結(jié)

構(gòu)

如

圖5-4所

示,相

應(yīng)

的

初

始

狀

態(tài)

為

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

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

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

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

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

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

的長(zhǎng)度為2L+k-2的任意子序列,那么

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

次,而且

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

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

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

為

這

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

么

相

應(yīng)

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

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

上述例子說明,通過cn

和cn+1的值可以計(jì)算出an+1和bn+1

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

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

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

對(duì)每一個(gè)i(1≤i≤L-1),將第i級(jí)的存儲(chǔ)內(nèi)容移入第i-1級(jí)。③

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

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

知道了k2,Oscar就可以利用

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

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

序

列{x1,x2,…,xn}和

與

其

對(duì)

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

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

法)實(shí)

現(xiàn)。KSA用

來(lái)

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

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

算

法128-EIA3在3GPP立

項(xiàng),并

申

請(qǐng)

成

為3GPP的

算

法

標(biāo)

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

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

布

祖

沖

之

算

法

為

國(guó)

家

標(biāo)

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

準(zhǔn)

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