現(xiàn)代密碼學(xué)理論與實(shí)踐分組密碼和數(shù)據(jù)加密標(biāo)準(zhǔn)

1、2024/3/27,Cryptography and Network Security - 3,現(xiàn)代密碼學(xué)理論與實(shí)踐第3章 分組密碼和數(shù)據(jù)加密標(biāo)準(zhǔn),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章 分組密碼和數(shù)據(jù)加密標(biāo)準(zhǔn),分組密碼是一種加密解密算法，將輸入明文分組當(dāng)做一個(gè)整體處理，輸出一個(gè)等長(zhǎng)的密文分組。許多分組密碼都采用Feistel結(jié)構(gòu)，這樣的結(jié)構(gòu)由許多相同的輪函數(shù)組成。每一輪里，對(duì)輸入數(shù)據(jù)的一半進(jìn)行代換，接著用一個(gè)置換來(lái)交換數(shù)據(jù)的兩個(gè)部分，擴(kuò)展初始的密鑰使得每一輪使用不同的子密鑰。DES是應(yīng)用最為廣泛的分組密碼，它擴(kuò)展了經(jīng)典的Feistel結(jié)構(gòu)。DES的分組和密鑰分別是64位和56

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

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

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

6、。diffusion –擴(kuò)散，明文統(tǒng)計(jì)結(jié)構(gòu)擴(kuò)散消失到大批密文統(tǒng)計(jì)特性中，使明文和密文之間統(tǒng)計(jì)關(guān)系盡量復(fù)雜；confusion –擾亂，使密文和加密密鑰之間的關(guān)系盡量復(fù)雜。,2024/3/27,Cryptography and Network Security - 3,5/35,3.1.2 Feistel密碼結(jié)構(gòu)的設(shè)計(jì)動(dòng)機(jī),分組密碼大多數(shù)分組密碼基于 Feistel Cipher Structure分組加密器本質(zhì)上就是一個(gè)巨大的替

7、換器64位的分組就有 264種輸入采用了乘積加密器的思想，即輪流使用替代和置換Feistel密碼結(jié)構(gòu)的設(shè)計(jì)動(dòng)機(jī)分組密碼對(duì)n比特的明文分組進(jìn)行操作，產(chǎn)生一個(gè)n比特的密文分組，共有2n個(gè)不同的明文分組，每一種都必須產(chǎn)生一個(gè)唯一的密文分組，這種變換稱為可逆的或非奇異的。 可逆映射 不可逆映射 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時(shí)的一個(gè)普通代換密碼的結(jié)構(gòu),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密碼結(jié)構(gòu),1973年，Horst Feistel提出了基于可逆乘積加密器概念的Feistel Cipher：將輸入分組分成左右兩部分，實(shí)施Shannon’s的substitution-permutation network 概念對(duì)左半部數(shù)據(jù)實(shí)施多回合的替代操作(substitutio

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

11、安全，通常為16次迭代子密鑰產(chǎn)生算法：越復(fù)雜則密碼分析越困難輪循環(huán)函數(shù)：越復(fù)雜則抗密碼分析的能力越強(qiáng)快速的軟件加密/解密：算法的執(zhí)行速度很重要簡(jiǎn)化分析難度：算法簡(jiǎn)潔清楚，易于分析弱點(diǎn)，發(fā)現(xiàn)問(wèn)題Feistel解密算法：以密文作為算法的輸入，以相反的次序使用密鑰Ki，Kn、Kn－1、...、K0.,Feistel加密器設(shè)計(jì)原則,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領(lǐng)導(dǎo)開發(fā)了Lucifer Cipher，使用128位密鑰加密64位的分組Tuchman-Mayer在此基礎(chǔ)上開發(fā)了一個(gè)商用密碼，使用56位密鑰加密64位分組，容易在單個(gè)芯片上硬件實(shí)現(xiàn)

13、1973美國(guó)國(guó)家標(biāo)準(zhǔn)局NBS全面征集加密方案，作為國(guó)家密碼標(biāo)準(zhǔn)IBM提交了經(jīng)過(guò)修改的Lucifer加密器，并最終在1976年被接受，公布為數(shù)據(jù)加密標(biāo)準(zhǔn)DESDES加密,3.2 數(shù)據(jù)加密標(biāo)準(zhǔn)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,擴(kuò)充置換(E)和置換函數(shù)(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子密鑰做以下動(dòng)作使用置換表E，將32位右半部R擴(kuò)展成48位與48位子密鑰做異或48位結(jié)果送給8個(gè)替換盒S-boxes，得到32位結(jié)果最后使用32位置換表P，把32位結(jié)果再進(jìn)行一次置換處理,Feistel Cipher分組加密循環(huán)細(xì)節(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個(gè)將6位數(shù)據(jù)映射成4位數(shù)據(jù)的S盒 6到4的映射規(guī)則是外側(cè)的第1位和第6位用作行選擇其余4位(2-5bit)用作列選擇這樣每盒就有4行16列，輸出4位，8個(gè)S盒輸出32位行的選擇依賴于數(shù)據(jù)和密鑰例如 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,子密鑰的產(chǎn)生,每一輪都要生成一個(gè)子密鑰以供加密使用子密鑰生成過(guò)程包括使用密鑰置換選擇1(PC-1)，將56位密鑰分成兩半，每一部分28位使用置換選

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

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

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

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

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

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

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

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

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

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

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

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

30、進(jìn)行攻擊，可以在有243個(gè)已知明文的情況下破譯DES密鑰，但仍然是不可行的。基本原理令明文分組為P[1], ..., P[n], 密文分組為C[1], ..., C[n], 密鑰為K[1], ..., K[m], 則定義： A[i, j, ..., k] = A[i]⊕A[j]⊕...⊕A[k]線性密碼分析的目標(biāo)是找到如下有效線性方程： 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越遠(yuǎn)，方程越有效。對(duì)于大量的明文密文對(duì)，計(jì)算方程左邊的值，如果結(jié)果中有一半以上為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的設(shè)計(jì)準(zhǔn)則：增加擾亂性輸出比特不應(yīng)太接近輸入比特的一個(gè)線性函數(shù)每一行應(yīng)該包括所有16種比特組合兩個(gè)輸入相差一個(gè)比特，輸出必須相差兩個(gè)比特如果兩個(gè)輸入剛好在兩個(gè)中間比特上不同，輸出必須在至少兩個(gè)比特上不同兩個(gè)輸入前兩位不同而最后兩位相同，兩個(gè)輸出必須不同具有非零6比特差值的輸入，32對(duì)中有不

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

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

35、難S盒的組織：要求高度非線性，隨機(jī)性密鑰擴(kuò)展算法選擇子密鑰時(shí)要使得推測(cè)各子密鑰和由此推出主密鑰難度盡可能大，保證密鑰/密文的嚴(yán)格雪崩效應(yīng)準(zhǔn)則和位獨(dú)立準(zhǔn)則。,分組密碼的設(shè)計(jì)原理,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(有錯(cuò))，3.14【注意】：3.13(a)中，等式 應(yīng)改