上海交大密碼學(xué)課件-第六講現(xiàn)代密碼學(xué).ppt

1、,第六講 現(xiàn)代密碼學(xué),上海交通大學(xué) 鄭東,1.現(xiàn)代分組密碼- moden-block ciphers,目前最廣泛使用的加密算法 提供保密與認(rèn)證服務(wù),2.私鑰加密算法private-key encryption,是一種單鑰或?qū)ΨQ算法 通信實體雙方使用相同的密鑰加密和解密 現(xiàn)代密碼（由乘積密碼構(gòu)成）包括DES, Blowfish, IDEA, LOKI, RC5, Rijndael (AES) 及其它一些算法,3。分組密碼,在分組密碼中，消息被分成許多塊 每塊都要被加密 類似于許多字符被替換-（ 64-bits or more ） 許多現(xiàn)代分組密碼具有下列形式：,3.分組密碼 (cont.),4.

2、理論基礎(chǔ),理想的方法是使用盡可能大的替換模塊 但不實際，因為對每個64bit的模塊，將需要264 個實體的替換表 因此使用一些小的模塊代替 使用乘積密碼的思想 這種概念由 Shannon and Feistel 提出,5. Shannons 保密系統(tǒng)理論,Claude Shannon 對現(xiàn)代密碼的重要工作 C E Shannon, Communication Theory of Secrecy Systems, Bell System Technical Journal, Vol 28, Oct 1949, pp 656-715 C E Shannon, Prediction and Entr

3、opy of printed English, Bell System Technical Journal, Vol 30, Jan 1951, pp 50-64 在上述文章中，提出了下列概念: “熵”的概念 語言冗余度 破譯密碼需要多少信息量 定義了”計算安全”與”無條件安全”,6. Shannons 保密系統(tǒng)理論 cont,即如果通過填加一些英語字母加密英文內(nèi)容，是不安全的 因為英語有80%的冗余度 英語密文如果有60%的冗余度，就可以破解,7. 替換-置換密碼,在Shannon 1949 的文章中，介紹了替換-置換網(wǎng)絡(luò)的思想 (S-P) networks 這種思想形成了現(xiàn)代密碼的基礎(chǔ) S

4、-P network 替換-置換乘積密碼的現(xiàn)代形式 S-P networks 是基于下列兩種最基本的密碼運(yùn)算（前面介紹過）： 替換（ Substitution ） 置換（ Permutation ）,8. 替換運(yùn)算,一個二進(jìn)制字用其它二進(jìn)制字替換 這種替換函數(shù)就構(gòu)成密鑰 可以看作是一個大的查表運(yùn)算 叫做 S-boxes,替換運(yùn)算（續(xù)）,9. 置換運(yùn)算（變換）,二進(jìn)制字次序被打亂 重新排序的方法構(gòu)成密鑰 叫這種變換為 P-boxes,9. Cont.,10. Substitution-Permutation Network,Shannon 把這兩種運(yùn)算組合在一起 一些 S-boxes 由 P-b

5、ox 連接 這種變換叫做混合變換（mixing transformations ）,10. 替換-置換網(wǎng)絡(luò)(cunt.),11. 實際使用的替換-置換網(wǎng)絡(luò),實際中，我們需要加密，也需要解密 因此，有兩種方法： 1.定義每個替換、置換的逆，這樣增加了復(fù)雜度 2. 定義一種結(jié)構(gòu)，容易求逆，這樣可以使用基本的相同編碼或硬件用于加密和解密,12. Feistel 密碼,Horst Feistel, （working at IBM Thomas J Watson Research Labs ）70s初，設(shè)計了這樣的結(jié)構(gòu)，我們現(xiàn)在叫做feistel cipher 思想是把輸入塊分成左右兩部分 L(i-1)

6、 和R(i-1), 變換是在密碼的第I輪只使用R(i-1) 函數(shù) g incorporates one stage of the S-P network的每個階段有g(shù) 工作，由第i 個密鑰控制（叫子密鑰）,Feistel Ciphers,13. Feistel 密碼,變換可以用下列函數(shù)表示: L(i) = R(i-1) R(i) = L(i-1) XOR g(K(i), R(i-1) 求逆很容易 實際中，一些這樣的連續(xù)變換形成完整密碼變換（典型：16輪）,14. 基本設(shè)計原理,Shannons 混合變換形成一種特殊的乘積密碼 組成部分一起工作: S-Boxes （S-盒) 提供輸入bits混合

7、作用 (confusion) 其目的在于使作用于明文的密鑰和密文之間的關(guān)系復(fù)雜化，使明文和密文之間、密文和密鑰之間的統(tǒng)計相關(guān)特性極小化，從而使統(tǒng)計分析攻擊不能奏效。通常的方法是“替換（Substitution)”（回憶愷撒密 碼）。,P-Boxes,提供擴(kuò)散作用(diffusion) 將明文及密鑰的影響盡可能迅速地散布到較多個輸出的密文中（將明文冗余度分散到密文中）。產(chǎn)生擴(kuò)散的最簡單方法是通過“換位(Permutation)”（比如：重新排列字符） 這種效果進(jìn)一步解釋為”雪崩”與”完全性” (Avalanche and Completeness )by Webster & Tavares On

8、 the Design of S-boxes, in Advances in Cryptology - Crypto 85, Lecture Notes in Computer Science, No 218, Springer-Verlag, 1985, pp 523-534,15. 雪崩效應(yīng)(Avalanche effect ),輸入改變1bit, 導(dǎo)致近一般的比特發(fā)生變化 一個函數(shù)F具有好的雪崩特性是指: 對2m個明文 向量, 分為2m-1個向量對xi和xi,每對向量只有一個bit不同, 定義Vi = f(X) XOR f(Xi) , 則近一半的Vi為1.,16. 完備性效應(yīng)(Compl

9、eteness effect ),每個輸出比特是所有輸入比特的復(fù)雜函數(shù)的輸出 F具有好的完備性是指: 對密文輸出向量的每一比特j, 0jm, 至少存在一個明文對(xi,xi), 此明文對只在第i比特不同,且F(xi)與F(xi)的第j比特不同.,17. 分組密碼設(shè)計(Block Cipher Design ),這些設(shè)計原理是設(shè)計好的分組密碼的準(zhǔn)則 “雪崩”保證小的輸入變化導(dǎo)致大的輸出變化 完全性保證每個輸出比特依賴于所有的輸入比特 我們可以看到,古典密碼沒有這些性質(zhì),18. Feistel Cipher 設(shè)計,設(shè)計密碼時,下列參數(shù)需要考慮: 分組大小(block size) 增加分組長度會提高

10、安全性, 但降低了密碼運(yùn)算速度 密鑰大小(key size) 增加密鑰長度,可以提高安全性(使得窮搜索困難),同樣,降低了密碼速度.,Feistel Cipher 設(shè)計(續(xù)),輪數(shù) 增加輪數(shù)可以提高安全性,但降低速度 子密鑰生成 子密鑰生成越復(fù)雜,就越安全,但降低速度 輪函數(shù) 復(fù)雜的輪函數(shù)能夠使的密碼分析困難,但降低速度 (所有問題就是平衡問題) 設(shè)計”安全”的密碼算法并不難,只要使用足夠多的輪數(shù)就可以,但降低速度 得到一個快速安全的算法是困難的,19. 密碼設(shè)計 評價,“好的”密碼設(shè)計具有: 雪崩特性,完備性,不可預(yù)料性(avalanche, completeness, unpredicta

11、bility ) 差的密碼設(shè)計缺乏隨機(jī)性,具有太大的可預(yù)料性 許多密碼都被攻破 (incl. commercial products like Wordperfect, pkzip, all current mobile phone ciphers) 即使密碼學(xué)專家也會犯這樣的錯誤 最好的辦法是測試, 通過實際檢驗證明它的安全性,20. Lucifer,第一個可用的替換-置換密碼(by Horst Feistel at IBM labs ) Horst Feistel, Cryptography and Computer Privacy, Scientific American, Vol 22

12、8(5), May 1973, pp 15-23. 提供了這項工作的框架,但沒有Lucifer 的細(xì)節(jié) 詳細(xì)的介紹: Arthur Sorkin, Lucifer, A Cryptographic Algorithm, Cryptologia, Vol 8(1), Jan 1984, pp 22-41, with addenda in Vol 8(3) pp260-261 包括算法的詳細(xì)描述實現(xiàn),21. Lucifer 瀏覽,原始描述沒有給出細(xì)節(jié) 以下列形式描述:,Lu cifer,22. Lucifer 密鑰編排,Lucifer IS Feistel cipher, 分組長度是 128-bi

13、t ,密鑰長度是128-bit 每輪使用的子密鑰是密鑰的左半部分 密鑰每次要向左旋轉(zhuǎn)56-bits, 所以,密鑰的每部分都參加運(yùn)算,23. Lucifer 數(shù)據(jù)計算,16輪數(shù)據(jù)計算(使用子密鑰) 輸出的右半部分作為下輪的輸入 RH side as inputs to the round function 交換位置前,與左半異或 S-P function for Lucifer 有下列結(jié)構(gòu): substitution 使用8個 4-bit S-boxes (S0 & S1) (對) 每個對的交替使用方法依賴與密鑰(order (S0|S1) or (S1|S0) depending on the

14、 key ) subkey 替換輸出相加(modulo 2) 在通過幾個8bit 置換組成128的簡單置換,Lucifer Function f,24. Lucifer Security,Lucifer 沒有經(jīng)過很強(qiáng)的分析 現(xiàn)在認(rèn)為是理論可破的(通過差分分析) 現(xiàn)在不被使用 是 DES的前生,25. 小結(jié),討論了: 分組密碼的概念及理論基礎(chǔ) feistel ciphers 的概念, 雪崩與完備性概念 Lucifer 的主要結(jié)構(gòu),END,Exercises,A Shannon style Substitution Box (S-box) grows in size as the number of input bits increases. For inputs of 4, 6, 8, 10, and 12 bits, list how many entries would be required. How large would each of these entries be, and why? What are the implications for the growth of this n