現代密碼學理論與實踐分組密碼和數據加密標準

1、2024/3/27,Cryptography and Network Security - 3,現代密碼學理論與實踐第3章 分組密碼和數據加密標準,Fourth Edition by William StallingsSlides by 楊壽保syang@ustc.edu.cnhttp://staff.ustc.edu.cn/~syang2012年9月,2024/3/27,Cryptography and Network Se

2、curity - 3,2/35,第3章 分組密碼和數據加密標準,分組密碼是一種加密解密算法，將輸入明文分組當做一個整體處理，輸出一個等長的密文分組。許多分組密碼都采用Feistel結構，這樣的結構由許多相同的輪函數組成。每一輪里，對輸入數據的一半進行代換，接著用一個置換來交換數據的兩個部分，擴展初始的密鑰使得每一輪使用不同的子密鑰。DES是應用最為廣泛的分組密碼，它擴展了經典的Feistel結構。DES的分組和密鑰分別是64位和56

3、位。差分分析和線性分析是兩種重要的密碼分析方法。DES對這兩種攻擊有一定的免疫性。,2024/3/27,Cryptography and Network Security - 3,3/35,3.1 分組密碼的原理,流密碼(Stream Cipher)和分組密碼(Block Cipher) 如果密文不僅與最初給定的算法和密鑰有關，同時也與明文位置有關(是所處位置的函數)，則稱為流密碼體制。加密以明文比特為單位，以偽

4、隨機序列與明文序列模2加后，作為密文序列，一次一比特/字節(jié) 如果經過加密所得到的密文僅與給定的密碼算法和密鑰有關，與被處理的明文數據在整個明文中的位置無關，則稱為分組密碼體制。通常以大于等于64位的數據塊為單位，加密得相同長度的密文。,2024/3/27,Cryptography and Network Security - 3,4/35,乘積密碼的設計思想,1949年，Claude Shannon引進了Substi

5、tution-Permutation (S-P) Networks的思想，即現代的乘積加密器，形成了現代分組加密的基礎。S-P Networks 是基于替代和置換這兩個基本操作的.乘積加密提供了對明文信息處理所做的confusion (擾亂)和diffusion (擴散)Shannon認為，為了對付基于統計分析的密碼破譯，必須對明文作confusion(擾亂)和diffusion(擴散)處理，以減少密文的統計特性，為統計分析制造障礙

6、。diffusion –擴散，明文統計結構擴散消失到大批密文統計特性中，使明文和密文之間統計關系盡量復雜；confusion –擾亂，使密文和加密密鑰之間的關系盡量復雜。,2024/3/27,Cryptography and Network Security - 3,5/35,3.1.2 Feistel密碼結構的設計動機,分組密碼大多數分組密碼基于 Feistel Cipher Structure分組加密器本質上就是一個巨大的替

7、換器64位的分組就有 264種輸入采用了乘積加密器的思想，即輪流使用替代和置換Feistel密碼結構的設計動機分組密碼對n比特的明文分組進行操作，產生一個n比特的密文分組，共有2n個不同的明文分組，每一種都必須產生一個唯一的密文分組，這種變換稱為可逆的或非奇異的。 可逆映射 不可逆映射 00 11 00 11 01 10

8、 01 10 10 00 10 01 11 01 11 01,2024/3/27,Cryptography and Network Security - 3,6/35,n = 4時的一個普通代換密碼的結構,2024/3/27,Cryptography and Network Security

9、- 3,7/35,,2024/3/27,Cryptography and Network Security - 3,8/35,3.1.3 Feistel密碼結構,1973年，Horst Feistel提出了基于可逆乘積加密器概念的Feistel Cipher：將輸入分組分成左右兩部分，實施Shannon’s的substitution-permutation network 概念對左半部數據實施多回合的替代操作(substitutio

10、n)對右半部數據和子密鑰應用輪函數F，其輸出與左一半做異或將這兩部分進行互換(permutation swapping),2024/3/27,Cryptography and Network Security - 3,9/35,分組長度：分組越長則安全性越高，但加/解密速度越低，分組長度為64位是一個合理的折衷密鑰長度：密鑰越長越安全，但加/解密速度越低，64位長的密鑰已被證明是不安全的，128位是常用的長度迭代次數：迭代越多越

11、安全，通常為16次迭代子密鑰產生算法：越復雜則密碼分析越困難輪循環(huán)函數：越復雜則抗密碼分析的能力越強快速的軟件加密/解密：算法的執(zhí)行速度很重要簡化分析難度：算法簡潔清楚，易于分析弱點，發(fā)現問題Feistel解密算法：以密文作為算法的輸入，以相反的次序使用密鑰Ki，Kn、Kn－1、...、K0.,Feistel加密器設計原則,2024/3/27,Cryptography and Network Security - 3,10/3

12、5,Feistel Cipher Encryption and Decryption,2024/3/27,Cryptography and Network Security - 3,11/35,歷史的回顧IBM公司在1971年由Horst Feistel領導開發(fā)了Lucifer Cipher，使用128位密鑰加密64位的分組Tuchman-Mayer在此基礎上開發(fā)了一個商用密碼，使用56位密鑰加密64位分組，容易在單個芯片上硬件實現

13、1973美國國家標準局NBS全面征集加密方案，作為國家密碼標準IBM提交了經過修改的Lucifer加密器，并最終在1976年被接受，公布為數據加密標準DESDES加密,3.2 數據加密標準DES,2024/3/27,Cryptography and Network Security - 3,12/35,DES加密算法的一般描述,2024/3/27,Cryptography and Network Security - 3,13/3

14、5,初始置換IP (Initial Permutation)和逆置換IP-1,2024/3/27,Cryptography and Network Security - 3,14/35,擴充置換(E)和置換函數(P),2024/3/27,Cryptography and Network Security - 3,15/35,將明文分成左右兩部分 Li = Ri–1 Ri = Li–1 xor F(Ri–1,

15、Ki)將32-bit右半部和48-bit子密鑰做以下動作使用置換表E，將32位右半部R擴展成48位與48位子密鑰做異或48位結果送給8個替換盒S-boxes，得到32位結果最后使用32位置換表P，把32位結果再進行一次置換處理,Feistel Cipher分組加密循環(huán)細節(jié),2024/3/27,Cryptography and Network Security - 3,16/35,2024/3/27,Cryptography a

16、nd Network Security - 3,17/35,S盒(Substitution Boxes),有8個將6位數據映射成4位數據的S盒 6到4的映射規(guī)則是外側的第1位和第6位用作行選擇其余4位(2-5bit)用作列選擇這樣每盒就有4行16列，輸出4位，8個S盒輸出32位行的選擇依賴于數據和密鑰例如 S(18 09 12 3d 11 17 38 39) = 5fd25e03,2024/3/27,Cryptogr

17、aphy and Network Security - 3,18/35,2024/3/27,Cryptography and Network Security - 3,19/35,2024/3/27,Cryptography and Network Security - 3,20/35,子密鑰的產生,每一輪都要生成一個子密鑰以供加密使用子密鑰生成過程包括使用密鑰置換選擇1(PC-1)，將56位密鑰分成兩半，每一部分28位使用置換選

18、擇2(PC-2)，從每一半中選出24位，形成48位子密鑰用在某一輪的F函數中根據密鑰左移表K將這兩半分別左移1位或2位重復置換選擇2(PC-2)，形成新的48位子密鑰用在下一輪的F函數中,2024/3/27,Cryptography and Network Security - 3,21/35,子密鑰的產生,2024/3/27,Cryptography and Network Security - 3,22/35,子密鑰的產生,,D

19、ES的解密 DES的解密是加密的逆過程，采用相同算法，但是子密鑰使用的次序正好相反。,2024/3/27,Cryptography and Network Security - 3,23/35,DES加密的雪崩效應,雪崩效應 Avalanche Effect 明文或密鑰的一比特的變化，引起密文許多比特的改變。如果變化太小，就可能找到一種方法減小有待搜索的明文和密文空間的大小。如果用同樣密鑰加密只差一比特的兩個明文：

20、 0000000000000000......00000000 1000000000000000......00000000 3次循環(huán)以后密文有21個比特不同，16次循環(huán)后有34個比特不同如果用只差一比特的兩個密鑰加密同樣明文： 3次循環(huán)以后密文有14個比特不同，16次循環(huán)后有35個比特不同,2024/3/27,Cryptography and Network Security - 3,24/3

21、5,2024/3/27,Cryptography and Network Security - 3,25/35,密鑰的長度問題56-bit 密鑰有256 = 72,057,584,037,927,936 ≈ 7.2億億之多強力搜索( brute force search ) 似乎很困難，20世紀70年代估計要1000－2000年技術進步使窮舉搜索成為可能1997年1月29日，RSA公司發(fā)起破譯RC4、RC5、MD2、MD5，以及

22、DES的活動，破譯DES獎勵10000美金。明文是：Strong cryptography makes the world a safer place. 結果僅搜索了24.6%的密鑰空間便得到結果，耗時96天。1998年在一臺專用機上(EFF)只要三天時間即可 1999年在超級計算機上只要22小時!現在只需要10小時！,3.3 DES的安全強度,2024/3/27,Cryptography and Network Security

23、 - 3,26/35,S-box問題其設計標準沒有公開，但是迄今沒有發(fā)現S盒存在致命弱點計時攻擊計時攻擊利用的事實是加密或解密算法對于不同的輸入所花的時間有細微的差別DES能夠很好地抵抗計時攻擊差分密碼分析攻擊問題DES對差分分析攻擊有較好的免疫力針對DES的密碼分析攻擊主要利用了加密器的深層結構搜集加密信息最終設法恢復部分或全部子密鑰的位如果必要的話對其余部分再輔以窮舉搜索這些攻擊實際上是統計分析，包括差分分析

24、、線性分析、相關密鑰攻擊,DES的安全強度,2024/3/27,Cryptography and Network Security - 3,27/35,3.5 差分分析和線性分析,差分密碼分析Differential Cryptanalysis1990年，Murphy、Biham和Shamir首次提出用差分密碼分析攻擊分組密碼和散列函數，是第一種可以以少于255的復雜性對DES進行破譯的方法。若有247個選擇明文，用差分分析就可以在2

25、47次加密運算內成功攻擊DES。盡管247比255小得多，但是要擁有247個選擇明文的條件使得這種方法只具有理論上的意義。對DES并不奏效。差分密碼分析攻擊方法 關注一對明文在加密過程中通過輪函數的演變情況，而不是觀測單個明文分組的演變。兩個報文的異或Δm=m⊕m’，中間過程有Δmi=mi⊕mi’，則,2024/3/27,Cryptography and Network Security - 3,28/35,差分密碼攻擊,假

26、設函數f有許多對具有相同差分的輸入，當使用相同的子密鑰時產生相同差分的輸出。精確地說，若差分為X的所有輸入，產生差分為Y的輸出占所有輸出的百分比為p，則稱由差分X導致差分Y的概率為p。假設有許多X都會以很高的概率產生某些特定的差分，因此如果我們以很高的概率知道Δmi-1和Δmi，就能以很高的概率知道Δmi+1。而且，如果知道很多有關差分的數據，那么確定函數f所使用的子密鑰就是可行的。,2024/3/27,Cryptography an

27、d Network Security - 3,29/35,Differential Cryptanalysis,反復加密已知輸入異或的明文對，直到得到期望的輸出異或如果找到中間輪次有滿足所需的異或，則找到了正確的一對輸入right pairs否則找到的是錯誤的一對輸入wrong pairs，對攻擊來說比例是S/N這樣可以推測中間輪次使用的密鑰值right pairs 說明了同樣的密鑰位wrong pairs 說明是隨機數

28、對于大輪次加密來說，找到正確的概率很低，要分析的對數比存在的64-bit inputs多 Biham和Shamir表明，13輪的分析可以破解整個16輪的DES,2024/3/27,Cryptography and Network Security - 3,30/35,如果使用相同子密鑰，對于f，具有系統差值的許多輸入對將產生相同的輸出差值，即如果在異或值為X的輸入對中，有p部分使輸出異或值為Y，則X產生Y的概率為p。假定存在很多X，具

29、有很大概率產生一個特定的輸出差值。如果已知Δmi-1和Δmi具有很大概率，則Δmi+1也具有很大概率。如果確定很多這樣的差值，則容易確定函數f中使用的子密鑰。右圖說明差值經過三次循環(huán)后的傳播情況，輸出差值為所示差值的概率為0.25x1x0.25=0.0625,2024/3/27,Cryptography and Network Security - 3,31/35,是1993年提出的另一種統計攻擊，基于找到DES中進行變換的線性近似來

30、進行攻擊，可以在有243個已知明文的情況下破譯DES密鑰，但仍然是不可行的?；驹砹蠲魑姆纸M為P[1], ..., P[n], 密文分組為C[1], ..., C[n], 密鑰為K[1], ..., K[m], 則定義： A[i, j, ..., k] = A[i]⊕A[j]⊕...⊕A[k]線性密碼分析的目標是找到如下有效線性方程： P[α1, α2, ..., αa]⊕

31、C[β1, β2, ..., βb] = K[γ1, γ2, ..., γc]其中，x=0或1；1≤a，b≤n，1≤c≤m，α，β和γ等表示固定的唯一的比特位置。方程以概率p≠0.5成立，p離0.5越遠，方程越有效。對于大量的明文密文對，計算方程左邊的值，如果結果中有一半以上為0，則假定K[γ1, γ2, ..., γc] ＝0；如果大多為1，則假定K[γ1, γ2, ..., γc] ＝1。,線性密碼分析Linear Crypta

32、nalysis,2024/3/27,Cryptography and Network Security - 3,32/35,S-boxes的設計準則：增加擾亂性輸出比特不應太接近輸入比特的一個線性函數每一行應該包括所有16種比特組合兩個輸入相差一個比特，輸出必須相差兩個比特如果兩個輸入剛好在兩個中間比特上不同，輸出必須在至少兩個比特上不同兩個輸入前兩位不同而最后兩位相同，兩個輸出必須不同具有非零6比特差值的輸入，32對中有不

33、超過8對輸出相同置換P的設計準則：增加擴散性第i次循環(huán)時每個S盒輸出的四個比特被分布開，以便其中兩個影響下一循環(huán)的中間比特，兩個影響兩端的比特每個S盒輸出的四個比特影響下一循環(huán)的6個不同的S盒，并且任何兩個都不會影響同一個S盒如果Sj的一個輸出比特影響下一循環(huán)Sk的中間比特，則Sk的一個輸出比特就不能影響Sj的一個中間比特。,3.5 分組密碼的設計原理,2024/3/27,Cryptography and Network Sec

34、urity - 3,33/35,迭代輪數迭代次數越多則進行密碼分析的難度就越大，選擇準則是要使已知的密碼分析工作量大于簡單的窮舉密鑰搜索的工作量。函數F的設計函數F的設計準則(非線性、嚴格雪崩效應、位獨立)提供擾亂作用，要求強非線性，良好的雪崩性質S-boxes的設計希望S盒輸入向量的任何變動在輸出方都產生看似隨機的變動，這兩種變動之間的關系應該是非線性的并難以用線性函數近似。S盒的大?。狠^大的抗攻擊能力強，但越大實現越困

35、難S盒的組織：要求高度非線性，隨機性密鑰擴展算法選擇子密鑰時要使得推測各子密鑰和由此推出主密鑰難度盡可能大，保證密鑰/密文的嚴格雪崩效應準則和位獨立準則。,分組密碼的設計原理,2024/3/27,Cryptography and Network Security - 3,34/35,Summary,We have considered in this chapter:Block cipher design principles

36、DESdetailsstrengthDifferential & Linear Cryptanalysis,2024/3/27,Cryptography and Network Security - 3,35/35,Assignments,第四版Chapter 33.9，3.11，3.12，3.13(有錯)，3.14【注意】：3.13(a)中，等式 應改