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

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

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

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

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

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

6、所需輸出長度為len，則RC4算法可表示為ks = RC4(key, Lk)，其過程可分為三步： 第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）偽隨機數(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算法過程可知，RC4算法是通過將密鑰key周期擴展為256字節(jié)來產(chǎn)生偽隨機數(shù)的，沒有體現(xiàn)出密鑰長度的區(qū)別，例如RC4(key, Lk) = RC4(key|key, 2*Lk)（|表示串聯(lián)）。另外，統(tǒng)計測試表明，RC4算法具有相關密鑰產(chǎn)生相似輸出的缺陷。為此，有人提出了RC4的一種變形算法RC4*，其算法過程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）偽隨機數(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*算法也是通過將密鑰key周期擴展為256字節(jié)來產(chǎn)生偽隨機數(shù)的，沒有體現(xiàn)出密鑰長度的區(qū)別，即RC4*(key, Lk) = RC4*(key|key, 2*Lk)。統(tǒng)計測試表明，RC4*算法的偽隨機性比RC4有所改善，不過也存在相關密鑰產(chǎn)生相似輸出的缺陷。另外，RC4*算法與RC4相比，速度明顯下降。SNOW2 (ISO/IEC

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

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