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

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

2、能大的替換模塊但不實(shí)際，因?yàn)閷?duì)每個(gè)64bit的模塊，將需要264 個(gè)實(shí)體的替換表因此使用一些小的模塊代替使用乘積密碼的思想 這種概念由 Shannon and Feistel 提出75. Shannons 保密系統(tǒng)理論保密系統(tǒng)理論 Claude Shannon 對(duì)現(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 在上述文章中，提出了下列概念: “熵”的概念語(yǔ)言冗余度破譯密碼需要多少信息量定義了”計(jì)算安全”與”無(wú)條件安全” 86. Shannons 保密系統(tǒng)理論保密系統(tǒng)理論 cont 即如果通過填加一些英語(yǔ)字母加密英文內(nèi)容，是不安全的因?yàn)橛⒄Z(yǔ)有80%的冗余度英語(yǔ)密文如果有60%的冗余度，就可以破解 97. 替換替換-置換密碼置換密碼 在Shannon 1949 的文章中，介紹了替換-置換網(wǎng)絡(luò)的思想 (S-P) networks 這種思想形成了現(xiàn)代密碼的基礎(chǔ)S-P ne

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

5、些 S-boxes 由 P-box 連接這種變換叫做混合變換（mixing transformations ）1510. 替換替換-置換網(wǎng)絡(luò)置換網(wǎng)絡(luò)(cunt.)1611. 實(shí)際使用的替換實(shí)際使用的替換-置換網(wǎng)絡(luò)置換網(wǎng)絡(luò)實(shí)際中，我們需要加密，也需要解密因此，有兩種方法：1.定義每個(gè)替換、置換的逆，這樣增加了復(fù)雜度2. 定義一種結(jié)構(gòu)，容易求逆，這樣可以使用基本的相同編碼或硬件用于加密和解密1712. Feistel 密碼密碼 Horst Feistel, （working at IBM Thomas J Watson Research Labs ）70s初，設(shè)計(jì)了這樣的結(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è)階段有g(shù) 工作，由第i 個(gè)密鑰控制（叫子密鑰） 18Feistel Ciphers 1913. Feistel 密碼密碼變換可以用下列函數(shù)表示: L(i) = R(i-1) R(i) = L(i-1) XOR g(K(i), R(i-1) 求逆很容易 實(shí)際中，一些這樣的連續(xù)變換形成完整密碼變換（典型：16輪）2014. 基本設(shè)計(jì)原理基本設(shè)計(jì)原理Shannons 混合變換形成一

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

8、密文中將明文及密鑰的影響盡可能迅速地散布到較多個(gè)輸出的密文中（將明文冗余度分散到密文中）。產(chǎn)生擴(kuò)散的最簡(jiǎn)單方法是通（將明文冗余度分散到密文中）。產(chǎn)生擴(kuò)散的最簡(jiǎn)單方法是通過過“換位換位(Permutation)”（比如：重新排列字符）（比如：重新排列字符）這種效果進(jìn)一步解釋為”雪崩”與”完全性” (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ā)生變化一個(gè)函數(shù)F具有好的雪崩特性是指: 對(duì)2m個(gè)明文 向量, 分為2m-1個(gè)向量對(duì)xi和xi,每對(duì)向量只有一個(gè)bit不同, 定義Vi = f(X) XOR f(Xi) ,則近一半的Vi為1.2316. 完備性效應(yīng)完備性效應(yīng)(Completeness effect )每個(gè)輸出比特是所有輸入比特的復(fù)雜函數(shù)的輸出 F具有好的完備性是指: 對(duì)密文輸出向量的每一比特j, 0jm, 至少存在一個(gè)明文對(duì)(xi,xi),

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

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

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

13、15-23. 提供了這項(xiàng)工作的框架,但沒有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ì)描述實(shí)現(xiàn)2921. Lucifer 瀏覽瀏覽 原始描述沒有給出細(xì)節(jié)以下列形式描述: 30Lu cifer3122. Lucifer 密鑰編排密鑰編排 Lucifer IS Feistel cipher, 分組長(zhǎng)度是 128-bit ,密鑰長(zhǎng)度是12

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

15、y )subkey 替換輸出相加(modulo 2)在通過幾個(gè)8bit 置換組成128的簡(jiǎn)單置換33Lucifer Function f3424. Lucifer Security Lucifer 沒有經(jīng)過很強(qiáng)的分析 現(xiàn)在認(rè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