1、四川大學電子信息學院1/129上周講到l第第1章章 密碼學概述密碼學概述l第第2章章 古典密碼技術古典密碼技術l第第3章章 分組密碼分組密碼l第第4章章 公鑰密碼體制公鑰密碼體制 l第第5章章 散列函數與消息鑒別散列函數與消息鑒別 l第第6章章 數字簽名技術數字簽名技術 l第第7章章 密鑰管理技術密鑰管理技術l第第8章章 身份鑒別技術身份鑒別技術 l第第9章章 序列密碼序列密碼 基礎基礎l第第10章章 密碼技術應用密碼技術應用課程主要內容課程主要內容四川大學電子信息學院2/129 3.1 分組密碼體制概述分組密碼體制概述 3.2 分組密碼的設計原則與評估分組密碼的設計原則與評估 3.3 數據加

2、密標準數據加密標準DES 3.4 分組密碼的操作方式分組密碼的操作方式 3.5 其它分組密碼算法其它分組密碼算法 (三重三重DES, IDEA, RC5 , AES )本章主要內容：本章主要內容：四川大學電子信息學院3/1293.1 分組密碼體制概述分組密碼體制概述 分組密碼體制是在密鑰控制下一次變換一個明文數據塊分組密碼體制是在密鑰控制下一次變換一個明文數據塊（又稱為分組）的密碼體制。（又稱為分組）的密碼體制。 分組密碼具有速度快、易于標準化和便于軟硬件實現等分組密碼具有速度快、易于標準化和便于軟硬件實現等待點。待點。 通常是信息與網絡安全中實現數據加密和認證的核心體通常是信息與網絡安全中實

3、現數據加密和認證的核心體制，它在計算機通信和信息系統安全領域有著最廣泛的應用。制，它在計算機通信和信息系統安全領域有著最廣泛的應用。四川大學電子信息學院4/1293.2 分組密碼的設計原則與評估分組密碼的設計原則與評估3.2.1 分組密碼的設計原則分組密碼的設計原則1. 針對安全性的一般設計原則針對安全性的一般設計原則l 明文分組長度和密鑰長度望盡可能大明文分組長度和密鑰長度望盡可能大 l 擴散原則擴散原則：密鑰或明文的每一位影響密文的：密鑰或明文的每一位影響密文的許多位以便隱蔽明文的統計特性許多位以便隱蔽明文的統計特性 l 混亂原則混亂原則：又稱混淆原則，是指密鑰和明文：又稱混淆原則，是指密

4、鑰和明文以及密文之間的依賴關系盡可能的復雜以及密文之間的依賴關系盡可能的復雜 2. 針對實現的設計原則針對實現的設計原則 l 軟件實現的設計原則軟件實現的設計原則: :使用子塊和簡單的運算。l 硬件實現的設計原則硬件實現的設計原則 : :盡量使用規則結構。四川大學電子信息學院5/129乘積密碼體制：乘積密碼體制： 為簡單起見，這里只討論明文空間和密文空問相同的密碼體為簡單起見，這里只討論明文空間和密文空問相同的密碼體制（稱為自同態密碼體制）制（稱為自同態密碼體制）,即即 M = C。 設設密碼體制密碼體制S1 =（M，C，K1，E1，D1)和和S2 =（M，C，K2，E2，D2) ，那么，那么

5、S1和和S2的乘積記為的乘積記為 S1 S2 ，它定義的乘積密碼體，它定義的乘積密碼體制制 S 為：為：S =（M, C, K1K2 , E, D) ；K1K2稱為稱為K1與與K2的笛卡爾積的笛卡爾積在在S中，對于每一個中，對于每一個k = (k1, k2 )，定義加密規則為：，定義加密規則為：和相應的解密規則：和相應的解密規則：mcDDcDkkk)()(21顯然有：顯然有：mmEDmEEDDmEEDmEDkkkkkkkkkkk)()()()(11122112cmEEmEkkk)()(12；mM， cC， k1 K1 ， k1 K1四川大學電子信息學院6/129 稱為是稱為是 n次迭代密碼體制

6、。次迭代密碼體制。 如果如果 S2 S，則稱為密碼體制是，則稱為密碼體制是冪等的冪等的，否則稱為，否則稱為非冪等密碼體制非冪等密碼體制。 對于冪等密碼，有，對于冪等密碼，有，)()(,312321mEmEEkKkkMmkkk滿足：，對迭代密碼體制：迭代密碼體制：Sn = S S S設設S是一個明文空間和密文空間相同的密碼體制，則：是一個明文空間和密文空間相同的密碼體制，則： n四川大學電子信息學院7/129 許多古典密碼體制都是冪等的密碼體制。譬如許多古典密碼體制都是冪等的密碼體制。譬如仿射密碼、仿射密碼、置換密碼以及置換密碼以及Vigenere密碼密碼等都是冪等密碼體制。顯然，若使等都是冪等

7、密碼體制。顯然，若使用具有冪等特性的密碼體制構造用具有冪等特性的密碼體制構造n次迭代密碼體制沒有意義次迭代密碼體制沒有意義 ，因為迭代需要更多的密鑰但卻不能提供更高的安全性。因為迭代需要更多的密鑰但卻不能提供更高的安全性。迭代密迭代密碼體制必須使用非冪等密碼體制。碼體制必須使用非冪等密碼體制。 如果如果S不是一個冪等的密碼體制，則對不是一個冪等的密碼體制，則對n1，迭代密碼體，迭代密碼體制制Sn的安全性能可能會比的安全性能可能會比S強。這種通過對一個密碼體制進行強。這種通過對一個密碼體制進行迭代來提高其安全性能的思想被廣泛應用于分組密碼體制的設迭代來提高其安全性能的思想被廣泛應用于分組密碼體制

8、的設計之中。計之中。 乘積密碼的思想在現代密碼體制的設計中具有重要意義。乘積密碼的思想在現代密碼體制的設計中具有重要意義。許多簡單的密碼體制都適合于通過乘積或迭代來構造分組密碼許多簡單的密碼體制都適合于通過乘積或迭代來構造分組密碼體制。體制。思考：思考：Hill密碼體制是否是冪等的密碼體制，為什么？密碼體制是否是冪等的密碼體制，為什么？迭代密碼體制（續）迭代密碼體制（續）四川大學電子信息學院8/129擴散原理與擾亂原理擴散原理與擾亂原理 為挫敗統計分析，香農提出了兩種實用的原則：擴散與擾亂擴散與擾亂l 擴散原理擴散原理(diffusion)： 盡量將每一位明文和密鑰的的影響盡可能迅速地分布到較

9、多的輸出密文位中，以便隱藏明文的統計特性。 擴散的目的是希望密文的任一位Ci都盡可能與明文和密鑰相關聯，或者說明文和密鑰任一位上值的改變都會影響到Ci的值。輸出輸出c可看成是可看成是m的的64個布爾函數：個布爾函數： ci = f i(m0, m1, m63)c0 = f 0(m0, m1, m63)c1 = f 1(m0, m1, m63)c63 = f 63(m0, m1, m63)使每個布爾函數在化簡后仍然包括使每個布爾函數在化簡后仍然包括64個輸入量個輸入量(m0, m1, m63)DESm64bitc64bitk四川大學電子信息學院9/129 使密文與明文、加密密鑰之間的統計關系盡量

10、復雜化，使破譯者難以從密文的統計特性導出與密鑰相關的信息。 為此，可以使用與密鑰和明文輸入有關的很復雜的各種非線性算法。（實現時主要利用復雜的替換算法）擾亂和擴散的結果：擾亂和擴散的結果： 使密碼分析者需要截獲大量的密文數據才能用統計分析方法進行破譯工作。已成為設計現代分組密碼的基礎。l 擾亂原理擾亂原理(confusion)：擴散原理與擾亂原理（續）擴散原理與擾亂原理（續） 四川大學電子信息學院10/129(1)安全性安全性 評估中的最重要因素，包括下述要點：評估中的最重要因素，包括下述要點：l 算法抗密碼分析的強度；算法抗密碼分析的強度；l 可靠的數學基礎；可靠的數學基礎；l 算法輸出的隨

11、機性；算法輸出的隨機性；l 與其他候選算法比較的相對安全性與其他候選算法比較的相對安全性 (2)性能性能 在各種平臺上的計算效率和對存儲空間的需求在各種平臺上的計算效率和對存儲空間的需求 (3)算法和實現特性算法和實現特性 靈活性、硬件和軟件適應性、算法的簡單性等。靈活性、硬件和軟件適應性、算法的簡單性等。 3.2.2 分組密碼的評估分組密碼的評估 四川大學電子信息學院11/1293.3 分組密碼常見的設計方法分組密碼常見的設計方法1. 思路思路 利用乘積密碼獲得簡單的替換密碼，并使最后結果的密碼利用乘積密碼獲得簡單的替換密碼，并使最后結果的密碼強度高于每個基本密碼系統產生的結果。強度高于每個

12、基本密碼系統產生的結果。 實際上是實際上是Shannon提出的利用乘積密碼實現擾亂和擴散思提出的利用乘積密碼實現擾亂和擴散思想的具體應用。想的具體應用。（1） SPN結構結構 在Shannon 1949 的文章中，介紹了替換-置換網絡（SPN）的思想 。這種思想形成了現代分組密碼的基礎。 SPN 是基于下列兩種最基本的密碼運算，這也是分組加密算法的兩個基本結構。兩個基本結構。2. 分組加密算法的兩個基本結構分組加密算法的兩個基本結構 四川大學電子信息學院12/129替換替換 (Substitution) - S盒盒置換或變位置換或變位 (Permutation) - P盒盒基本運算過程：基本運

13、算過程： 對各數據塊基于密鑰進行變位(置換)一次運算，然后再進行替換等運算，構成一輪，并重復運算多次構成循環。正向的循環構成加密過程，而反向的循環則構成解密過程。替換和變位可用簡單電路來實現，替換和變位可用簡單電路來實現，P盒實現變位，盒實現變位，S盒實現替換。盒實現替換。0123456734057612P盒 輸入序號為： 0 1 2 3 4 5 6 7P盒輸出序號為： 3 4 0 5 7 6 1 2通過適當的調整內部布線，可讓P盒作任意變位。P盒的作用是起到擴散作用（本質屬線性變換）。盒的作用是起到擴散作用（本質屬線性變換）。分組加密算法的兩個基本結構分組加密算法的兩個基本結構(續續) 四川

14、大學電子信息學院13/12901 2 34567b23-8解碼器8-3編碼器01 2 34567b1b0c2c1c0S盒盒S盒實現替換。圖例中輸入盒實現替換。圖例中輸入3bit的明文，輸出的明文，輸出3bit的密文。的密文。S盒分為盒分為3部分：解碼、部分：解碼、P盒及編碼。盒及編碼。圖中，如輸入序列為圖中，如輸入序列為01234567，則輸出序列為則輸出序列為34057612，即對應完成了替換。，即對應完成了替換。 顯然，通過適當的調整顯然，通過適當的調整P盒內部布線，可讓盒內部布線，可讓S盒作任意替換。盒作任意替換。 S盒的作用是起到擾亂作用（非線性變換）。盒的作用是起到擾亂作用（非線性變

15、換）。 如果一種密碼體制可用一組線性方程組來定義，稱為線性密如果一種密碼體制可用一組線性方程組來定義，稱為線性密碼，而線性密碼系統是極易被密碼分析攻破的碼，而線性密碼系統是極易被密碼分析攻破的 。14/129 當將若干當將若干P盒、盒、S盒串聯起來，組成乘積密碼，即可使輸盒串聯起來，組成乘積密碼，即可使輸出成為輸入非常復雜的函數。出成為輸入非常復雜的函數。P1S1S2S3S4P2S5S6S7S8P3S9S10S11S12P4輸入輸出011011 圖中第一站圖中第一站P1盒對盒對12根輸入線作變序處理，從理論上根輸入線作變序處理，從理論上講第講第2站可以為一個站可以為一個S盒，由它把盒，由它把1

16、2bit數據替換為另外一個數據替換為另外一個12bit數據，但這樣的數據，但這樣的S盒中需要盒中需要212=4096根跨接線，為此可根跨接線，為此可將將12bit分為分為4個個3bit分組，各組獨立地進行替換處理，從而分組，各組獨立地進行替換處理，從而可減少可減少S盒的復雜性。盒的復雜性。 當乘積密碼中配置足夠多的站，就可使輸出成為輸入的當乘積密碼中配置足夠多的站，就可使輸出成為輸入的非常復雜的函數。非常復雜的函數。(也稱為也稱為SP網絡網絡)15/129 SPN結構也是一種特殊的迭代密碼結構也是一種特殊的迭代密碼 。SPN結構和結構和Feistel結構相比，可以得到更快速的擴散，結構相比，可

17、以得到更快速的擴散，但是但是SPN密密碼的加解密通常不相似。碼的加解密通常不相似。 典型典型SPN結構結構 (P44)16/129 （2）Feistel 密碼結構密碼結構（20世紀70年代） 理想的密碼：理想的密碼： 密文的任何一位均與明文的每一位相關；而明文的任何密文的任何一位均與明文的每一位相關；而明文的任何一位的變化將影響到盡量多的密文。一位的變化將影響到盡量多的密文。Li RiFLi+1Ri+1Kiw比特比特w比特比特ww基本結構單元),(11iiiiiiKRFLRRL網絡結構特點：網絡結構特點： 輸入為輸入為2w比特的分組（稱為左半分組和比特的分組（稱為左半分組和右半分組）；右半分組

18、）； 函數用于產生擴散和擾亂作用，函數用于產生擴散和擾亂作用，但并但并不要求為可逆函數；不要求為可逆函數； Ki為由密碼密鑰為由密碼密鑰K生成的子密鑰；生成的子密鑰； Feistel網絡由網絡由n個基本結構單元構成個基本結構單元構成（但子密鑰（但子密鑰Ki互不相同）互不相同）四川大學電子信息學院17/129（2）Feistel 密碼結構（續）密碼結構（續）Feistel結構的實現依賴的主要參數與特征：結構的實現依賴的主要參數與特征： 分組大小：分組大小：越大安全性越高，但運算速度越慢，一般為越大安全性越高，但運算速度越慢，一般為64bit； 密鑰長度：密鑰長度：越大安全性越高，但運算速度越慢，

19、常為越大安全性越高，但運算速度越慢，常為128bit； 循環次數：循環次數：越多安全性越高，但運算開銷越大，通常采越多安全性越高，但運算開銷越大，通常采用用16次；次； 子密鑰產生算法：子密鑰產生算法：算法越復雜，密碼分析越困難；算法越復雜，密碼分析越困難； 輪函數輪函數F：復雜性越高，密碼分析越困難；復雜性越高，密碼分析越困難；“加解密相似加解密相似”是是Feistel型密碼的實現特點點。但同時，型密碼的實現特點點。但同時，Feistel型密碼的擴散要慢一些。如算法至少需要兩輪才能改變型密碼的擴散要慢一些。如算法至少需要兩輪才能改變輸入的每一位。輸入的每一位。18/129L0 R0FL1R1

20、K1w比特w比特wwFLiRiKiFLnRnKn第1輪第 i 輪明文Ln+1Rn+1密文(2w bit)第 n 輪Feistel網絡結構如圖四川大學電子信息學院19/129本章主要內容：本章主要內容： 3.1 分組密碼體制概述分組密碼體制概述 3.2 分組密碼的設計原則與評估分組密碼的設計原則與評估 3.3 數據加密標準數據加密標準DES 3.4 分組密碼的操作方式分組密碼的操作方式 3.5 其它分組密碼算法其它分組密碼算法 (三重三重DES, IDEA, RC5 , AES )四川大學電子信息學院20/1293.3 數據加密標準數據加密標準DES1 . DES概述概述 數據加密標準數據加密標

21、準DES( Data Encryption Standard )是美是美國國家標準局（國國家標準局（National Bureau of Standards，現在的，現在的美國標準與技術協會，美國標準與技術協會，NIST）在）在1977年發布的，用于保年發布的，用于保護護“非絕密的計算機數據非絕密的計算機數據”。 DES由美國由美國IBM公司研制，是在早期的稱作公司研制，是在早期的稱作Lucifer密碼（密鑰長度密碼（密鑰長度128bit）的一種發展和修改。）的一種發展和修改。 1975年被首次公布，年被首次公布，1977年正式被批準為美國聯邦年正式被批準為美國聯邦信息處理標準信息處理標準(F

22、IPS-46)，并規定每隔五年由美國國家安，并規定每隔五年由美國國家安全局全局( National Security Agency，NSA)做出評估。做出評估。 1979年美國銀行協會批準使用年美國銀行協會批準使用DES； 1981年成為美國標準化協會（年成為美國標準化協會（ANSI）標準；）標準； 四川大學電子信息學院21/129DES概述（續）概述（續） 對對DES的首次評估是的首次評估是在在1983年，年，未作任何修改；未作任何修改； 1987年，年，NSA認為認為DES不安全，宣布不再為其安全負責，不安全，宣布不再為其安全負責，但仍將其作為國家標準作為過渡；但仍將其作為國家標準作為過渡

23、； 1994年年NIST把聯邦政府使用的把聯邦政府使用的DES的有效期又延長了的有效期又延長了5年，年，建議算法用于保護非絕密的應用；建議算法用于保護非絕密的應用； 1997年年NIST開始征集開始征集AES， 并于并于2000年年10月月2日日 確定比利確定比利時的時的 “Rijndael數據加密算法數據加密算法”最終獲勝，成為新的加密標準。最終獲勝，成為新的加密標準。 DES是一種分組加密算法，數據分組長度為是一種分組加密算法，數據分組長度為64位，密文分組位，密文分組長度也是長度也是64位，使用的密鑰為位，使用的密鑰為64位，有效密鑰長度為位，有效密鑰長度為56位位(有有8位位用于奇偶校

24、驗用于奇偶校驗)。由固定換位、密鑰依賴、多次非線性變換而產生。由固定換位、密鑰依賴、多次非線性變換而產生全面的混亂。全面的混亂。解密算法和加密相同解密算法和加密相同，但密鑰的使用順序正好相反。，但密鑰的使用順序正好相反。 DES的整個體制是公開的，系統的安全性完全靠密鑰的保密。的整個體制是公開的，系統的安全性完全靠密鑰的保密。四川大學電子信息學院22/1292. DES算法原理算法原理 DES屬于分組密碼體制，其設計思想有利于硬件實現屬于分組密碼體制，其設計思想有利于硬件實現（相對于軟件實現）。（相對于軟件實現）。硬件實現方面：硬件實現方面： DEC公司開發的DES芯片處理速度達 1Gb/s

25、(每秒處理約1680萬個分組)； VLSI推出的商用芯片處理速度達 512Mb/s 軟件實現方面：軟件實現方面： 基于486/66的處理速度達 2.7Mb/s； 基于9000/887（125MHz）的處理速度達 12.5Mb/s ； 基于SUN Sparc10/52的處理速度達 3.4Mb/s ； 一般硬件實現速度在一般硬件實現速度在500Mb/s以上，而軟件實現速度在以上，而軟件實現速度在幾幾十幾十幾Mb/s四川大學電子信息學院23/129 DES算法描述算法描述 DES是一種是一種明文分組為明文分組為64比特比特，有效密鑰有效密鑰56比特比特，輸出密文輸出密文64比特比特的，具有的，具有1

26、6輪迭代輪迭代的的Feistel密碼算密碼算法。法。 DES由初始置換，由初始置換，16輪迭代，初始逆置換組成。輪迭代，初始逆置換組成。 2. DES算法原理（續）算法原理（續） DES基本運算操作：基本運算操作： 置換、替換、異或與循環移位置換、替換、異或與循環移位 。四川大學電子信息學院24/129K2 6464位明文位明文M 初始置換IP 64 64位密文位密文C C第1輪 逆初始置換IP-1第2輪第16輪循環左移 置換選擇2密鑰密鑰(56bit) 置換選擇2 置換選擇2循環左移循環左移置換選擇1K1K16DES加密算法的一般描述加密算法的一般描述32位對換(半交換)L0 R0L15 R

27、15L16 R16返回返回DESDES密鑰產生密鑰產生四川大學電子信息學院25/129DES算法的輪循環算法的輪循環: Feistel 密碼結構密碼結構 四川大學電子信息學院26/129Ri-1(32 bit)Ki (48 bit)EE(Ri-1)為48 bit+S1S2S3S4S5S6S7S8 C1 C2 C3 C4 C5 C6 C7 C8PF(Ri-1,Ki)寫成寫成 8個個6bit 串串 DES 的的F函數函數6bit8=48bit4bit 8=32bitB1 B2 B3 B4 B5 B6 B7 B8 輸入：輸入：6bit輸出：輸出：4bit預擴展預擴展四川大學電子信息學院27/129F

28、函數中的預擴展函數中的預擴展E：根據一個固定的變位和復制規則擴展根據一個固定的變位和復制規則擴展3232位，位， 3232位的位的R Ri-1i-1 48 48位的位的E(A)E(A)將將Ri-1分成分成8個個4位的塊位的塊，然后，然后（考慮（考慮i-1、i、i+1塊）：塊）： （4位位8 6位位8）b4b1b4b1b1b4b4b1b1b2b3b4第1塊b1b2b3b4最后1塊b1b2b3b4b1b2b3b4b1b2b3b4i+1塊i-1塊i塊（共有（共有8 8塊）塊）對對F F函數的說明函數的說明四川大學電子信息學院28/129參見書參見書P45P454747四川大學電子信息學院29/129

29、F函數中的函數中的S盒變換：盒變換： 一個一個S S盒將盒將6464種可能輸出的每一種種可能輸出的每一種都被映射為一個都被映射為一個4bit4bit輸出：輸出：6bit 4bit6bit 4bit最后這些最后這些 4bit4bit8 = 32 bit 8 = 32 bit 再經過一個再經過一個P P盒實施變位輸出盒實施變位輸出（P47P47，表，表3.53.5）。 S S盒的每一行定義了一個一般的可盒的每一行定義了一個一般的可逆變換（在這一行屬單值映射），而由逆變換（在這一行屬單值映射），而由b b1 1b b6 6來選擇其中的一種。來選擇其中的一種。0000 0001 0010 0011 0

30、100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 11110000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 111100 1110 0100 1101 0001 0010 1111 1011 1000 0011 1010 1010 1100 0101 1001 0000 011100 1110 0100 1101 0001 0010 1111 1011 1000 0011 1010 1010 1100 0101 1001 0000 011

31、101 0000 1111 0111 0100 1110 0010 1101 0001 1010 0110 1100 1011 1001 0101 0011 100001 0000 1111 0111 0100 1110 0010 1101 0001 1010 0110 1100 1011 1001 0101 0011 100010 0100 0001 1110 1000 1101 0110 0010 1011 1111 1100 1001 0111 0011 1010 0101 000010 0100 0001 1110 1000 1101 0110 0010 1011 1111 1100

32、1001 0111 0011 1010 0101 000011 1111 1100 1000 0010 0100 1001 0001 0111 0101 1011 0011 1110 1010 0000 0110 110111 1111 1100 1000 0010 0100 1001 0001 0111 0101 1011 0011 1110 1010 0000 0110 1101b b1 1b b6 6b b2 2b b3 3b b4 4b b5 5S S0 0盒變換盒變換（P46P46，表，表3.43.4）S01S02S03S04b1b2b3b4b5b6S0盒結構c1c2c3c4四川大學

33、電子信息學院30/129DES密鑰的產生密鑰的產生 密鑰(64bit)PC-1K1C0置換選擇置換選擇1(1(去奇偶校驗、置換去奇偶校驗、置換56bit)56bit)D0LS1LS1C1D1LS2LS2C2D2PC-2置換選擇228bit28bit56bitK2PC-256bitLS16LS16C16D16K16PC-256bit轉下頁48bit48bit48bit循環左移四川大學電子信息學院31/129C0D064bit56bit參見書參見書P48P48P49P49其中，第8，16，24，32，40，48，56和64位被丟棄（奇偶校驗位）。置換置換選擇選擇PC-156bit48bit其中，第

34、9，18，22，25，35，38，43和54位被丟棄。置換置換選擇選擇PC-2輪數(i) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 LSi 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 LSi的取值的取值四川大學電子信息學院32/129 DES的解密算法：的解密算法： 同任何同任何Feistel網絡結構密碼一樣，解密使用與加密同樣網絡結構密碼一樣，解密使用與加密同樣的算法，不過的算法，不過子密鑰反序子密鑰反序使用。使用。DES加密的一個例子：加密的一個例子：取取16進制明文分組進制明文分組M：0123456789ABCDEF （8個字節）個

35、字節） 密鑰密鑰K為：為：13 34 57 79 9B BC DF F1 （8個字節）個字節） 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001去掉奇偶校驗位以二進制形式表示的密鑰是：去掉奇偶校驗位以二進制形式表示的密鑰是： 0001001 0011010 0101011 0111100 1001101 1011110 1101111 1111000四川大學電子信息學院33/129DES加密的一個例子加密的一個例子(續續)明文經過初始明文經過初始IP置換，得到：置換，得到： L0=1100110000

36、0000001100110011111111 R0=L1=11110000101010101111000010101010然后進行然后進行16輪加密。輪加密。最后對最后對L16, R16使用使用IP-1得到密文：得到密文： 85E813540F0AB405（8個字節）個字節）明文分組明文分組M：0123456789ABCDEF （8個字節）個字節） 四川大學電子信息學院34/1293. DES算法的幾個問題算法的幾個問題1） 循環次數的考慮循環次數的考慮循環次數越多，進行密碼分析的難度越大。循環次數越多，進行密碼分析的難度越大。2） 函數函數F的設計準則的設計準則原則：函數原則：函數F 的非線

37、性程度越大，進行密碼分析的難度越大。的非線性程度越大，進行密碼分析的難度越大。（1）嚴格雪崩效應準則）嚴格雪崩效應準則（SAC, Strict Avalanche Criterion）: 對于任何的對于任何的 i，j，當任何一個輸入比特當任何一個輸入比特 i 變化時，函數輸變化時，函數輸出比特出比特 j 變化的概率為變化的概率為1/2。 “改變輸入中的改變輸入中的1位，平均要導致一般的位被改變位，平均要導致一般的位被改變”（2）比特獨立準則）比特獨立準則（BIC, Bit Independence Criterion）: 對于任何的對于任何的 i，j，k，當任何一個輸入比特當任何一個輸入比特

38、i 變化時，變化時，函數輸出比特函數輸出比特 j和和k 應當獨立地變化。應當獨立地變化。設計有兩條用于加強分組密碼擴散和擾亂功能的準則：設計有兩條用于加強分組密碼擴散和擾亂功能的準則：四川大學電子信息學院35/1291） 隨機性：隨機性：輸出與輸入之間是無規律的輸出與輸入之間是無規律的2）完全性：）完全性：每個輸出位都是所有輸入位的一個復雜函數。每個輸出位都是所有輸入位的一個復雜函數。3）非線性：）非線性：加密函數對任何密鑰值都是非線性的。加密函數對任何密鑰值都是非線性的。4）相關免疫性：）相關免疫性：輸出是統計上獨立與任何輸入位的子集，輸出是統計上獨立與任何輸入位的子集，不會與輸入位的任何子

39、集相關。不會與輸入位的任何子集相關。 在明文和密文之間不存在明顯的統計關系；在明文和密文之間不存在明顯的統計關系；5）滿足嚴格雪崩準則）滿足嚴格雪崩準則 每當其任一明文輸入位或密鑰位取反時，每一密文每當其任一明文輸入位或密鑰位取反時，每一密文輸出位都將以輸出位都將以1/2的概率變化；的概率變化；4. DES的的特性與安全強度特性與安全強度四川大學電子信息學院36/1296）存在互補特性：）存在互補特性：(證明作為課后練習) 如果：)()(MECMECKK，則有： 選擇明文攻擊：選擇明文攻擊： 若選擇明文集合中有（若選擇明文集合中有（M1,C1）和）和),(21CM)()(1212MECMECk

40、k有： 所以，一旦得出用密鑰所以，一旦得出用密鑰K對明文對明文M1加密得到的密文加密得到的密文C1或或 ，一次就可推出兩個密鑰來。這就使得攻擊之前的，一次就可推出兩個密鑰來。這就使得攻擊之前的工作量減少一半。工作量減少一半。2C四川大學電子信息學院37/129若滿足，若滿足，Ek(Ek(m) = m，則稱，則稱k為為弱密鑰弱密鑰。0101010101010101FEFEFEFEFEFEFEFE1F1F1F1F0E0E0E0EE0E0E0E0F1F1F1F1若滿足，若滿足，Eka(Ekb(m) = m，則稱，則稱ka、 kb為為半弱密鑰半弱密鑰。01FE01FE01FE01FE 01FE01FE

41、01FE01FE 和和 FE01FE01FE01FE01FE01FE01FE01FE011FE01FE00EF10EF1 1FE01FE00EF10EF1 和和 E01FE01FF10EF10EE01FE01FF10EF10E01E001E001F101F1 01E001E001F101F1 和和 E001E001F101F101E001E001F101F1011FFE1FFE0EFE0EFE 1FFE1FFE0EFE0EFE 和和 FE1FFE1FFE0EFE0EFE1FFE1FFE0EFE0E011F011F010E010E 011F011F010E010E 和和 1F011F010E01

42、0E011F011F010E010E01E0FEE0FEF1FEF0FE E0FEE0FEF1FEF0FE 和和 FEE0FEE0FEF1FEF1FEE0FEE0FEF1FEF17）存在）存在4個弱密鑰和個弱密鑰和6對半弱密鑰；對半弱密鑰；四川大學電子信息學院38/129存在存在4個弱密鑰和個弱密鑰和6對半弱密鑰（續）對半弱密鑰（續）回文密鑰回文密鑰(palindromic key) ：如果如果DES使用了弱密鑰，這使用了弱密鑰，這DES的的16個子密鑰就有如下關系：個子密鑰就有如下關系： K1 = K16, K2 = K15, , K8= K9反回文密鑰反回文密鑰(antipalindrom

43、ic key)：其中有其中有8個半弱密鑰個半弱密鑰(紅色紅色)的子密鑰滿足：的子密鑰滿足：98152161.KKKKKK，不動點不動點（fixed point）：若明文分組）：若明文分組 m 滿足滿足Ek(m) = m ，則稱，則稱m為不動點。為不動點。DES中，若使用弱密鑰，則存在中，若使用弱密鑰，則存在 232個不動點。個不動點。反不動點反不動點（antifixed point）：若明文分組）：若明文分組 m 滿足滿足Ek(m) = ，則，則稱稱m為反不動點。在為反不動點。在DES中，若使用反回文半弱密鑰，則存在中，若使用反回文半弱密鑰，則存在 232個反不動點。個反不動點。m四川大學電子

44、信息學院39/129 這是對這是對DES較有效的分析方法，是由較有效的分析方法，是由E.Biham和和A.Shamir在在1993年年提出的。提出的。 是一個較為有效的方法（選擇性明文攻擊）。對于攻擊是一個較為有效的方法（選擇性明文攻擊）。對于攻擊8輪輪DES，在，在486那樣的計算機上，只需那樣的計算機上，只需2分鐘可攻破。分鐘可攻破。 蠻力攻擊法：蠻力攻擊法： 255次嘗試；次嘗試； 參考網站：參考網站： 差分密碼分析法：差分密碼分析法：247次嘗試；次嘗試； 線性密碼分析法：線性密碼分析法：243次嘗試；次嘗試；9) DES的半公開性的半公開性 內部結構內部結構(S盒盒)的設計準則未公開

45、，用戶不能確認的設計準則未公開，用戶不能確認DES的的內部結構有無任何隱藏的弱點或陷阱（內部結構有無任何隱藏的弱點或陷阱（Hidden Trapdoors）。）。10) 56bit的密鑰太短的密鑰太短 1998以前以前DES破譯機只有理論設計，隨后已出現實用化破譯機只有理論設計，隨后已出現實用化的的DES破譯機。破譯機。8) 對對DES的差分密碼分析和線性密碼分析的差分密碼分析和線性密碼分析 （略）四川大學電子信息學院40/129本章主要內容：本章主要內容： 3.1 分組密碼體制概述分組密碼體制概述 3.2 分組密碼的設計原則與評估分組密碼的設計原則與評估 3.3 數據加密標準數據加密標準DE

46、S 3.4 分組密碼的操作方式分組密碼的操作方式 3.5 其它分組密碼算法其它分組密碼算法 (三重三重DES, IDEA, RC5 , AES )四川大學電子信息學院41/1293.4 分組密碼的操作方式分組密碼的操作方式1.1.電子代碼本模式電子代碼本模式（ ECB，Electronic Code Book）: : 示意圖示意圖 將每塊明文加密成相應的密碼塊，若最后一塊不足將每塊明文加密成相應的密碼塊，若最后一塊不足64bit，則用一些任意二進制序列填充。這樣相同的明文塊總被加密成則用一些任意二進制序列填充。這樣相同的明文塊總被加密成相同的密文塊。相同的密文塊。特點特點 ：(1) 一種最簡易

47、的工作方式；一種最簡易的工作方式； (2) 相同密鑰作用下，密文塊與明文塊一一對應，易于相同密鑰作用下，密文塊與明文塊一一對應，易于暴露明文的固有格式；暴露明文的固有格式； (3) 各密文塊間缺乏相關性，信息易于受到塊替換攻擊各密文塊間缺乏相關性，信息易于受到塊替換攻擊 。 算法本質上相當于一個算法本質上相當于一個“大的單字母替換大的單字母替換”。問題的提出：問題的提出： 分組加密如何應用于大數據（如文件）加密分組加密如何應用于大數據（如文件）加密?四川大學電子信息學院42/129返回DES加密加密DES加密加密DES加密加密m1m2mnc1c2cnkkkDES解密解密DES解密解密DES解密

48、解密c1c2cnm1m2mnkkk（a）加密）加密（b）解密）解密四川大學電子信息學院43/129 加入反饋機制，當前明文塊在加密之前加入反饋機制，當前明文塊在加密之前要與前面的密文塊進行異或。要與前面的密文塊進行異或。 設明文塊為設明文塊為m1，m2， mN產生的密文塊產生的密文塊為為c1，c2，, cN 加密密鑰為加密密鑰為K，初始隨機向量，初始隨機向量為為IV，加密算法記為，加密算法記為EK，解密算法記為，解密算法記為DK。EK+MnCnCn-1（CBC加密）c1=EK (m1 IV), c2=EK (m2 c1), cN=EK (mN cN-1), （IV稱為初始化向量）稱為初始化向量

49、）m1=DK(c1) IV m2=DK(c2) c1 mN=DK(cN) cN-1加密加密解密解密2. 密碼塊鏈接模式（密碼塊鏈接模式（CBC，Cipher Block Chain） :四川大學電子信息學院44/129CBC加密過程加密過程四川大學電子信息學院45/129CBC解密過程解密過程四川大學電子信息學院46/129 關于關于CBC初始向量初始向量IV的說明：的說明：加密時，用于第一個明文塊以產生第一個密文塊；加密時，用于第一個明文塊以產生第一個密文塊； 解密時，用于對第一個密文塊的解密輸出進行異或，解密時，用于對第一個密文塊的解密輸出進行異或，以產生第一個明文塊；以產生第一個明文塊；

50、IV必須安全，否則第一個明文塊易受攻擊（假冒攻擊）必須安全，否則第一個明文塊易受攻擊（假冒攻擊） C1= EK(m1 IV) m1= DK(C1) IV 若攻擊者能夠預測性地改變若攻擊者能夠預測性地改變IV的比特，這也可以的比特，這也可以改變接收方改變接收方m1的響應比特值。的響應比特值。四川大學電子信息學院47/129 (1) 同一明文塊會產生不同的密文塊；同一明文塊會產生不同的密文塊；算法不再是一個算法不再是一個“大的單字母替換大的單字母替換” (2) 有誤碼擴散，同時又有自同步特性；有誤碼擴散，同時又有自同步特性； 若若Ci在傳送過程中出錯，則解密時會造成在傳送過程中出錯，則解密時會造成

51、mi和和mi+1兩個兩個明文塊都出錯，但后面的密文塊仍然能自動正確恢復。明文塊都出錯，但后面的密文塊仍然能自動正確恢復。 (3) 只有當所有只有當所有64比特塊到達后才能開始編解碼，不能直比特塊到達后才能開始編解碼，不能直接用于交互式終端。否則傳輸帶寬浪費嚴重。接用于交互式終端。否則傳輸帶寬浪費嚴重。CBC加密特點加密特點 ：四川大學電子信息學院48/129 其它鏈接模式，如其它鏈接模式，如 :IVEKc1Ec2cN圖中，mi = ci Ek(ci1), 1 i N; c0= IVEKK解密解密m1m2mNm1m2mNIVEKc1Ec2cN圖中，ci = mi Ek(ci1), 1 i N;

52、c0= IVEKK加密加密四川大學電子信息學院49/1293. 密碼反饋模式（密碼反饋模式（CFB，Cipher FeedBack ） 可克服可克服CBC方式的第方式的第(3)個問題。個問題。 CFB數據是按比分組小得多的單位進行加密的，密文依數據是按比分組小得多的單位進行加密的，密文依賴于前面所有的明文。賴于前面所有的明文。 C2C3C4C5C6C7C8C9EIV64bit移位寄存器移位寄存器(8字節字節)K+64bit密文P10選擇最左邊 t 位C10C2C3C4C5C6C7C8C9EIV64bit移位寄存器移位寄存器(8字節字節)K+64bit密文C10選擇最左邊t 位P10第7周四川大

53、學電子信息學院50/129 (1) 移位寄存器的的內容與明文整個以前的歷史有移位寄存器的的內容與明文整個以前的歷史有關，同樣需要一個初始向量（寄存器初值）；關，同樣需要一個初始向量（寄存器初值）； (2) 存在誤碼擴散存在誤碼擴散（仍有自同步特性），（仍有自同步特性），加密效率加密效率不及不及CBC 模式模式 (為什么？為什么？) (3) 將分組密碼轉換為流密碼（序列密碼），實現將分組密碼轉換為流密碼（序列密碼），實現及時加密；及時加密；CFB模式特點模式特點 ：四川大學電子信息學院51/1294. 輸出反饋模式（輸出反饋模式（OFB，Output FeedBack ） 與與CFB模式相似，但

54、它是在塊內部進行反饋，其反饋機模式相似，但它是在塊內部進行反饋，其反饋機制既不依賴明文也不依賴密文流，所以又稱為內部反饋模式。制既不依賴明文也不依賴密文流，所以又稱為內部反饋模式。 EIV64bit移位寄存器移位寄存器(8字節字節)K+64bit密文Pi選擇最左邊1字節biCi 偽隨機數據流(與明文、密文無關)+ EIV64bit移位寄存器移位寄存器(8字節字節)K64bit密文Ci選擇最左邊1字節Pi四川大學電子信息學院52/129l OFB模式特點模式特點 ： OFB是以過去的子密鑰是以過去的子密鑰 bi-1 為基礎來產生下一個子密鑰，為基礎來產生下一個子密鑰，OTP密鑰可鑰預先生成；密鑰

55、可鑰預先生成； CFB是以過去的密文塊是以過去的密文塊 Ci-1 作為產生下一個子密鑰的基礎，作為產生下一個子密鑰的基礎，不可預先生成；不可預先生成；(1) 沒有誤碼擴散，適用于傳輸信息長度變化較大的數據，如沒有誤碼擴散，適用于傳輸信息長度變化較大的數據，如語音、圖像等；語音、圖像等；(2) 比比CFB更易受對消息流的篡改；更易受對消息流的篡改； 攻擊者有可能通過對消息數據部分和校驗部分的篡改，攻擊者有可能通過對消息數據部分和校驗部分的篡改，而以檢錯碼不能檢測的方而以檢錯碼不能檢測的方 式篡改密文。式篡改密文。 (3) 鏈接相關性，密文與前面的明文無關。鏈接相關性，密文與前面的明文無關。 (4

56、) 應用時要求一次一密方式應用時要求一次一密方式(OTP，One-Time Pad)OFB與與CFB的比較的比較: 四川大學電子信息學院53/1295. 計數器模式計數器模式 m1m2mN計計數數器器1Ekc1Ec2cN圖中，ci = mi Ek(CTR+i) ;1 i N Ekk加密加密計計數數器器2計計數數器器N解密解密c1c2cN計計數數器器1Ekm1Em2mN圖中，mi = ci Ek(CTR+i) ;1 i N; Ekk計計數數器器2計計數數器器N四川大學電子信息學院54/129 (1) 處理效率高，可進行并行處理，提高數據吞吐量；處理效率高，可進行并行處理，提高數據吞吐量； (2)

57、 可提前進行預處理；可提前進行預處理； (3) 具有隨機訪問特性，可隨機對任意一個密文分組進具有隨機訪問特性，可隨機對任意一個密文分組進行解密處理，對該密文分組的處理與其他密文無關；行解密處理，對該密文分組的處理與其他密文無關； (4) 實現簡單，加、解密階段都只涉及加密函數。（這實現簡單，加、解密階段都只涉及加密函數。（這點與點與ECB和和CBC模式不同）。模式不同）。CTR模式特點模式特點 ：四川大學電子信息學院55/1296. 密文竊取模式密文竊取模式 問題的提出：問題的提出： 注意注意CBC加密模式，其中最后兩個分組的加解加密模式，其中最后兩個分組的加解密過程示意圖如下。密過程示意圖如

58、下。 XN K YN K PN-1 加密加密 CN-2 K YN-1 EN-1 CN X 加密加密 EN-1 K YN EN-1 CN-1 PN 000 L 個字節 僅保留頭 L 個字節作 CN 解密解密 EN-1 YN-1 解密解密 僅頭 L 個 字節為 PN CN-1 CN 000 PN Y PN 000 PN-1 CN-2 PN-1，PN的加密過程 PN-1，PN的解密過程 CSM（Ciphertext Stealing Mode）四川大學電子信息學院56/129 XN K YN K PN-1 加密加密 CN-2 K YN-1 EN-1 CN X 加密加密 EN-1 K YN EN-1

59、CN-1 PN 000 L 個字節 僅保留頭 L 個字節作 CN 解密解密 EN-1 YN-1 解密解密 僅頭 L 個 字節為 PN CN-1 CN 000 PN Y PN 000 PN-1 CN-2 PN-1，PN的加密過程 PN-1，PN的解密過程 6. 密文竊取模式密文竊取模式 CSM（Ciphertext Stealing Mode），最后兩個分組的加解密過程示意圖如下。），最后兩個分組的加解密過程示意圖如下。 四川大學電子信息學院57/129對密碼操作模式的選擇對密碼操作模式的選擇 ：(1) 安全性安全性 抗攻擊能力、安全防護能力和密文隨機性。(2) 高效性高效性 調用分組加密的次數

60、、并行處理能力、存儲空間要求、初始化代價和預處理能力。 (3) 所實現的功能所實現的功能 安全服務：安全服務：機密性、完整性和可鑒別性。 靈活性：靈活性：明文分組和密鑰的長度可變、預計算的不同次數、對消息的長度要求等。 實現方面的脆弱性：實現方面的脆弱性：如對密鑰的數量、IV、隨機數等的要求，誤碼擴散與自同步能力密文與前面的明文無關，以及專利限制等等。 其中，其中，ECB、CBC、CFB和和OFB模式是美國標準與技模式是美國標準與技術協會（術協會（NIST）針對）針對DES定義的四種操作模式。定義的四種操作模式。四川大學電子信息學院58/129 3.1 分組密碼體制概述分組密碼體制概述 3.2