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

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

2、能大的替換模塊但不實際，因為對每個64bit的模塊，將需要264 個實體的替換表因此使用一些小的模塊代替使用乘積密碼的思想 這種概念由 Shannon and Feistel 提出75. Shannons 保密系統(tǒng)理論保密系統(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 Entropy of printe

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

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

5、些 S-boxes 由 P-box 連接這種變換叫做混合變換（mixing transformations ）1510. 替換替換-置換網(wǎng)絡(luò)置換網(wǎng)絡(luò)(cunt.)1611. 實際使用的替換實際使用的替換-置換網(wǎng)絡(luò)置換網(wǎng)絡(luò)實際中，我們需要加密，也需要解密因此，有兩種方法：1.定義每個替換、置換的逆，這樣增加了復(fù)雜度2. 定義一種結(jié)構(gòu)，容易求逆，這樣可以使用基本的相同編碼或硬件用于加密和解密1712. Feistel 密碼密碼 Horst Feistel, （working at IBM Thomas J Watson Research Labs ）70s初，設(shè)計了這樣的結(jié)構(gòu)，我們現(xiàn)在叫做feis

6、tel cipher 思想是把輸入塊分成左右兩部分 L(i-1) 和R(i-1), 變換是在密碼的第I輪只使用R(i-1) 函數(shù) g incorporates one stage of the S-P network的每個階段有g(shù) 工作，由第i 個密鑰控制（叫子密鑰） 18Feistel Ciphers 1913. Feistel 密碼密碼變換可以用下列函數(shù)表示: L(i) = R(i-1) R(i) = L(i-1) XOR g(K(i), R(i-1) 求逆很容易 實際中，一些這樣的連續(xù)變換形成完整密碼變換（典型：16輪）2014. 基本設(shè)計原理基本設(shè)計原理Shannons 混合變換形成一

7、種特殊的乘積密碼 組成部分一起工作: S-Boxes （S-盒)提供輸入bits混合作用 (confusion) 其目的在于使作用于明文的密鑰和密文之間的關(guān)系復(fù)雜化，其目的在于使作用于明文的密鑰和密文之間的關(guān)系復(fù)雜化，使明文和密文之間、密文和密鑰之間的統(tǒng)計相關(guān)特性極小化，使明文和密文之間、密文和密鑰之間的統(tǒng)計相關(guān)特性極小化，從而使統(tǒng)計分析攻擊不能奏效。通常的方法是從而使統(tǒng)計分析攻擊不能奏效。通常的方法是“替換替換（Substitution)”（回憶愷撒密（回憶愷撒密 碼）。碼）。 21P-Boxes提供擴散作用提供擴散作用(diffusion) 將明文及密鑰的影響盡可能迅速地散布到較多個輸出的

8、密文中將明文及密鑰的影響盡可能迅速地散布到較多個輸出的密文中（將明文冗余度分散到密文中）。產(chǎn)生擴散的最簡單方法是通（將明文冗余度分散到密文中）。產(chǎn)生擴散的最簡單方法是通過過“換位換位(Permutation)”（比如：重新排列字符）（比如：重新排列字符）這種效果進一步解釋為”雪崩”與”完全性” (Avalanche and Completeness )by Webster & Tavares On the Design of S-boxes, in Advances in Cryptology - Crypto 85, Lecture Notes in Computer Science

9、, No 218, Springer-Verlag, 1985, pp 523-5342215. 雪崩效應(yīng)雪崩效應(yīng)(Avalanche effect )輸入改變1bit, 導(dǎo)致近一般的比特發(fā)生變化一個函數(shù)F具有好的雪崩特性是指: 對2m個明文 向量, 分為2m-1個向量對xi和xi,每對向量只有一個bit不同, 定義Vi = f(X) XOR f(Xi) ,則近一半的Vi為1.2316. 完備性效應(yīng)完備性效應(yīng)(Completeness effect )每個輸出比特是所有輸入比特的復(fù)雜函數(shù)的輸出 F具有好的完備性是指: 對密文輸出向量的每一比特j, 0jm, 至少存在一個明文對(xi,xi),

10、此明文對只在第i比特不同,且F(xi)與F(xi)的第j比特不同.2417. 分組密碼設(shè)計分組密碼設(shè)計(Block Cipher Design ) 這些設(shè)計原理是設(shè)計好的分組密碼的準則 “雪崩雪崩”保證小的輸入變化導(dǎo)致大的輸出變保證小的輸入變化導(dǎo)致大的輸出變化化完全性保證每個輸出比特依賴于所有的輸入完全性保證每個輸出比特依賴于所有的輸入比特比特我們可以看到,古典密碼沒有這些性質(zhì) 2518. Feistel Cipher 設(shè)計設(shè)計設(shè)計密碼時,下列參數(shù)需要考慮: 分組大小分組大小(block size) 增加分組長度會提高安全性, 但降低了密碼運算速度密鑰大小密鑰大小(key size) 增加密鑰

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

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

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

14、8-bit 每輪使用的子密鑰是密鑰的左半部分密鑰每次要向左旋轉(zhuǎn)56-bits, 所以,密鑰的每部分都參加運算3223. Lucifer 數(shù)據(jù)計算數(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 ke

15、y )subkey 替換輸出相加(modulo 2)在通過幾個8bit 置換組成128的簡單置換33Lucifer Function f3424. Lucifer Security Lucifer 沒有經(jīng)過很強的分析 現(xiàn)在認為是理論可破的(通過差分分析) 現(xiàn)在不被使用 是 DES的前生 3525. 小結(jié)小結(jié) 討論了:分組密碼的概念及理論基礎(chǔ)feistel ciphers 的概念, 雪崩與完備性概念Lucifer 的主要結(jié)構(gòu) 36END37Exercises 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 fo