密碼學(xué)c3流密碼算法與偽隨機(jī)數(shù)產(chǎn)生器

1、密碼學(xué)Cryptology計(jì)算機(jī)學(xué)院 黃玉劃辦公室：北門(mén)A12號(hào)樓11613675155711教學(xué)內(nèi)容第1章 引論第2章 古典密碼學(xué)第3章 流密碼算法與偽隨機(jī)數(shù)產(chǎn)生器第4章 分組密碼算法第5章 分組密碼算法的工作模式第6章 單向散列(Hash)函數(shù)第7章 公鑰密碼算法與數(shù)字簽名算法第8章 認(rèn)證與密鑰交換協(xié)議第3章 流密碼算法與偽隨機(jī)數(shù)產(chǎn)生器密碼算法可分為兩類(lèi)：對(duì)稱(chēng)算法和非對(duì)稱(chēng)算法。對(duì)稱(chēng)算法又稱(chēng)單密鑰算法，可分為兩類(lèi)：序列密碼算法和分組密碼算法。序列密碼算法通過(guò)將明（密）文同密碼流逐位相異或進(jìn)行加（解）密,其特點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，速度一般比較快，錯(cuò)誤傳播少或沒(méi)有。分組密碼算法則將明（密）文分組通過(guò)一對(duì)

2、互逆密碼算法來(lái)進(jìn)行分組加（解）密。 第3章 流密碼算法(續(xù))序列密碼也稱(chēng)為流密碼流密碼，密鑰序列也稱(chēng)為密鑰流密鑰流。 序列密碼加密的基本原理是：用一個(gè)隨機(jī)隨機(jī)序列與明文明文序列進(jìn)行異或來(lái)產(chǎn)生密文。流密碼是將明文劃分成字符（單個(gè)字母），或其編碼的基本單元（0, 1數(shù)字），字符分別與密鑰流作用進(jìn)行加密，解密時(shí)以同步產(chǎn)生的同樣的密鑰流實(shí)現(xiàn)。 設(shè)計(jì)序列密碼體制的關(guān)鍵就是要設(shè)計(jì)一種產(chǎn)生密鑰序密鑰序列列的方法?！耙淮我幻堋钡碾S機(jī)密鑰序列密碼體制在理論上是不可以破譯的。產(chǎn)生序列密碼中的密鑰序列的一種主要工具是移位寄移位寄存器存器。第3章 流密碼算法移位寄存器移位寄存器是流密碼產(chǎn)生密鑰流的一個(gè)主要組成部分。G

3、F(2)上一個(gè)n級(jí)反饋移位寄存器由n個(gè)二元存儲(chǔ)器與一個(gè)反饋函數(shù)f(a1,a2,an)組成，如圖所示。第3章 流密碼算法線(xiàn)性反饋移位寄存器(LFSR)如果移位寄存器的反饋函數(shù)f (a1,a2,an)是a1,a2,an的線(xiàn)性函數(shù),則稱(chēng)之為線(xiàn)性反饋移位寄存器(LFSR)。此時(shí)輸出序列an+t=f(at,at+1,an+t-1)=cnatcn-1at+1c1an+t-1其中常數(shù)ci=0或1(總是假定cn=1),是模2加法。ci=0或1可用開(kāi)關(guān)的斷開(kāi)和閉合來(lái)實(shí)現(xiàn),如圖所示。第3章 流密碼算法線(xiàn)性反饋移位寄存器(續(xù))n級(jí)線(xiàn)性反饋移位寄存器最多有2n個(gè)不同的狀態(tài)。若其初始狀態(tài)為0，則其狀態(tài)恒為0。若其初始狀

4、態(tài)非0，則其后繼狀態(tài)不會(huì)為0。因此n級(jí)線(xiàn)性反饋移位寄存器的狀態(tài)周期2n-1。其輸出序列的周期T與狀態(tài)周期相等，也2n-1。只要選擇合適的反饋函數(shù)便可使序列的周期達(dá)到最大值2n-1，周期達(dá)到最大值的序列稱(chēng)為m序列。第3章 流密碼算法LFSR的特征多項(xiàng)式設(shè)n級(jí)線(xiàn)性移位寄存器的輸出序列滿(mǎn)足遞推關(guān)系an+t=cnatcn-1at+1c1an+t-1這 種 遞 推 關(guān) 系 可 用 一 個(gè) 一 元 高 次 多 項(xiàng) 式P(x)=1+c1x+cn-1xn-1cnxn表示，稱(chēng)這個(gè)多項(xiàng)式為L(zhǎng)FSR的特征多項(xiàng)式。定理定理 n級(jí)LFSR產(chǎn)生的序列有最大周期2n-1的必必要條件要條件是其特征多項(xiàng)式為不可約的。若n次不可

5、約多項(xiàng)式p(x)的階為2n-1，則稱(chēng)p(x)是n次本原多項(xiàng)式。定理定理 設(shè)aiG(p(x)，ai為m序列的充要條件充要條件是p(x)為本原多項(xiàng)式。第3章 流密碼算法（續(xù)）從密碼系統(tǒng)的角度看，一個(gè)偽隨機(jī)序列還應(yīng)滿(mǎn)足下面的條件： ai的周期相當(dāng)大。 ai的確定在計(jì)算上是容易的。 由密文及相應(yīng)的明文的部分信息，不能確定整個(gè)ai。注：LFSR不能直接作為流密碼算法。第3章 流密碼算法 RC4算法RC4算法是由RSA公司的Ron Rivest設(shè)計(jì)的序列密碼算法。在WLAN(無(wú)線(xiàn)局域網(wǎng))保密機(jī)制中，IEEE802.11的初期標(biāo)準(zhǔn)就是采用了RC4算法。假設(shè)密鑰為key，密鑰長(zhǎng)度為L(zhǎng)k字節(jié)；輸出密鑰流為ks，

6、所需輸出長(zhǎng)度為len，則RC4算法可表示為ks = RC4(key, Lk)，其過(guò)程可分為三步： 第3章 流密碼算法 RC4算法步驟1）初始化(Initialization)：j = 0;Fori = 0 to 255 si = i ; ki = keyi mod Lk; 2）密鑰編排算法(KSA)Fori = 0 to 255 j = ( j + si + ki) mod 256; tmp2 = si; si = sj; sj = tmp2; 第3章 流密碼算法 RC4算法步驟（續(xù)）3）偽隨機(jī)數(shù)產(chǎn)生(PRNG)算法：i = j = 0;fortmp = 0tolen-1 i = (i + 1

7、) mod 256; j = (j + si) mod 256; tmp2 = si; si = sj; sj = tmp2; t = (si + sj) mod 256; kstmp = st; 第3章 流密碼算法 RC4算法性能由RC4算法過(guò)程可知，RC4算法是通過(guò)將密鑰key周期擴(kuò)展為256字節(jié)來(lái)產(chǎn)生偽隨機(jī)數(shù)的，沒(méi)有體現(xiàn)出密鑰長(zhǎng)度的區(qū)別，例如RC4(key, Lk) = RC4(key|key, 2*Lk)（|表示串聯(lián)）。另外，統(tǒng)計(jì)測(cè)試表明，RC4算法具有相關(guān)密鑰產(chǎn)生相似輸出的缺陷。為此，有人提出了RC4的一種變形算法RC4*，其算法過(guò)程ks=RC4*(key, Lk)為： 第3章 流密

8、碼算法 RC4*算法步驟1）初始化(Initialization)：j = 0; i0 = 0; j0 = 0;Fori = 0 to 255 si = i ; ki = keyi mod Lk; 2）密鑰編排算法(KSA)Fori = 0 to 255 j = ( j + si + ki) mod 256; i0 = (i0+si) mod 256; j0 = ( j0+sj) mod 256; tmp2 = si; si = sj; sj = tmp2; 第3章 流密碼算法 RC4*算法步驟（續(xù)）3）偽隨機(jī)數(shù)產(chǎn)生(PRNG*)算法： i = i0; j = j0;fortmp = 0tol

9、en-1 i = (i + C) mod 256; j = (j + si) mod 256; tmp2 = si; si = sj; sj = tmp2; t = (si + sj) mod 256; kstmp = st; 第3章 流密碼算法 RC4*算法性能RC4*算法也是通過(guò)將密鑰key周期擴(kuò)展為256字節(jié)來(lái)產(chǎn)生偽隨機(jī)數(shù)的，沒(méi)有體現(xiàn)出密鑰長(zhǎng)度的區(qū)別，即RC4*(key, Lk) = RC4*(key|key, 2*Lk)。統(tǒng)計(jì)測(cè)試表明，RC4*算法的偽隨機(jī)性比RC4有所改善，不過(guò)也存在相關(guān)密鑰產(chǎn)生相似輸出的缺陷。另外，RC4*算法與RC4相比，速度明顯下降。SNOW2 (ISO/IEC

10、 18033-4: 2006) St+15 St+11St+5St+2 St-1R1SR2有限狀態(tài)機(jī)kSNOW2SNOW2算法邏輯結(jié)構(gòu)簡(jiǎn)潔，運(yùn)算速度較快，已被采納為3GPP加密標(biāo)準(zhǔn)。 SNOW2由1個(gè)線(xiàn)性反饋移位寄存器(LFSR)和1個(gè)有限狀態(tài)機(jī)組成，狀態(tài)機(jī)采用AES的思想。SNOW2的密鑰編排比RC4、SEAL和HC256快，但比AES慢。SNOW2的缺點(diǎn)是：(1) SNOW2不能直接擴(kuò)展成64位字算法，要更換不可約多項(xiàng)式。(2)內(nèi)存需求較大。SNOW2有6個(gè)表，其中2個(gè)用于LFSR，4個(gè)S盒用于狀態(tài)機(jī)，每個(gè)表由256個(gè)32位字組成。如果擴(kuò)展成64位字算法，需要8個(gè)以上S盒，每個(gè)S盒由256

11、個(gè)64位字組成。 分組密鑰編排/Hash消息擴(kuò)展AES：wi=S(wi-1) wi-4 SHA1：wt = (wt-3 wt-8 wt-14 wt-16 )1SHA2： Wt = F6(Wt 2) + Wt 7 + F5 (Wt 15) + Wt 16 非線(xiàn)性循環(huán)移位寄存器非線(xiàn)性循環(huán)移位寄存器(NRSR) 輸 出 a i ( m 比 特 ) 計(jì) 數(shù) 加 1 a i + n - 1 ( m 比 特 )a i + 1 ( i mod m ) 2 i + 1 ai+n = ( a i + n -1 j ) ai + 1 mod 2m ai+n = ( bai+n-1) (ai j ) + 1 mod

12、 2m 非線(xiàn)性循環(huán)移位寄存器特點(diǎn)非線(xiàn)性循環(huán)移位寄存器特點(diǎn)(1) 周期更大、安全性更高。n級(jí)LFSR的最大周期為2n-1；n級(jí)NLFSR的最大周期為2n。由于運(yùn)算不固定，NRSR周期大于(2m)n（m為字長(zhǎng)）。對(duì)于周期達(dá)到最大的LFSR，其輸出狀態(tài)1 2n-1是絕對(duì)均勻的；對(duì)于周期達(dá)到最大的NLFSR，其輸出狀態(tài)0 2n-1是絕對(duì)均勻的，遍歷了所有狀態(tài)才會(huì)重復(fù)。測(cè)試表明，NRSR產(chǎn)生的輸出是偽隨機(jī)均勻的。因此，NRSR的不可預(yù)測(cè)性和安全性?xún)?yōu)于(N)LFSR。NRSR的初值不受限，可以全為0。對(duì)于SHA1和SHA2的消息擴(kuò)展算法，如果分組消息全為0，則擴(kuò)展消息也全為0。 非線(xiàn)性循環(huán)移位寄存器特點(diǎn)非線(xiàn)性循環(huán)移位寄存器特點(diǎn)(2) 多平臺(tái)適應(yīng)性更靈活。(N)LFSR軟件實(shí)現(xiàn)慢，解決的辦法是并行m個(gè)(N)LFSR（m一般取平臺(tái)的位數(shù)），相當(dāng)于字長(zhǎng)為m比特，但最大周期還是小于等于2n，除非象SNOW2一樣采用模2m的本原多項(xiàng)式，最大周期才小于等于(2m)n。此時(shí)一般需要空間存儲(chǔ)反饋系數(shù)表。對(duì)于不同的字長(zhǎng)m和不同的級(jí)數(shù)n，(N)LFSR要尋找不同的反饋模式。不管字長(zhǎng)m和級(jí)數(shù)n為多大，NRSR存在固定的反饋模式，無(wú)須尋找達(dá)到最大周期的反饋模式，可以直接適應(yīng)各種平臺(tái)，包括將來(lái)128位以上的平臺(tái)。 非線(xiàn)性循環(huán)移位寄存器特點(diǎn)非線(xiàn)性循環(huán)移位寄存器特點(diǎn)(3) 效率更高。在32位平臺(tái)下（2.4GHz雙