分組密碼 42數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)(續(xù))

1、密碼學(xué)第四章 分組密碼4.2 數(shù)據(jù)加密標(biāo)準(zhǔn)(DES) (續(xù))DES加加密密框框圖圖6464比特明文比特明文fk1L1R1初始置換初始置換6464比特密文比特密文逆初始置換逆初始置換L15R15R16L16L0R0fk16.4.2 數(shù)據(jù)加密標(biāo)準(zhǔn)(DES) (續(xù))n脫密算法脫密算法nDES算法的安全性分析算法的安全性分析n多重多重DES DES的脫密運(yùn)算和加密運(yùn)算用的是同一個(gè)算的脫密運(yùn)算和加密運(yùn)算用的是同一個(gè)算法，二者的法，二者的不同之處不同之處是圈密鑰的使用次序相反，是圈密鑰的使用次序相反，即脫密過程中第即脫密過程中第 i圈圈(i=1,2,16)的圈密鑰是加密的圈密鑰是加密過程中第過程中第17-

2、 i圈的圈密鑰圈的圈密鑰 k17-i 。一、脫密算法一、脫密算法DES脫脫密密框框圖圖6464比特密文比特密文fk16R15L15初始置換初始置換6464比特明文比特明文逆初始置換逆初始置換R1L1L0R0R16L16fk1.則則DES的圈變換可表示為這兩個(gè)函數(shù)的復(fù)合的圈變換可表示為這兩個(gè)函數(shù)的復(fù)合( , )( , ),)( ,( , )kD F x yD xf y kyyxf y k有有( , )( , ),)( , )( , ),)( ,)kkkF F x yF xf y kyxf y kf y kyxy( ,)( ,)( ,)D D xyD yxxy若設(shè)函數(shù)若設(shè)函數(shù)( , )( , ),

3、),kF x yxf y ky就是說就是說 ， 都是恒等變換都是恒等變換。kkFFID DI( , )( , )D x yy xyx f (y,k)x (32位位)y (32位位)fk一、脫密算法一、脫密算法定理定理1：1()DESDES mm其中其中m為明文數(shù)據(jù)，為明文數(shù)據(jù)， 、 分別為加、脫密變換。分別為加、脫密變換。DES1DES證明：證明：設(shè)加密過程第設(shè)加密過程第i 圈的圈子密鑰為圈的圈子密鑰為ki，則脫密過程第，則脫密過程第i 圈的圈子密鑰為圈的圈子密鑰為k17-i，于是，于是1615211( )( )kkkkDES mIPFDFDFDFIP m12151611( )( )kkkkD

4、EScIPFDFDFDFIP c161521111()()kkkkDESDES mDESIPFDFDFDFIP m故故12151616152111( )kkkkkkkkIPFDFDFDFIP IPFDFDFDFIP m12151616152111( )kkkkkkkkIPFDFDFDFIP IPFDFDFDFIP m一、脫密算法一、脫密算法又因?yàn)橛忠驗(yàn)閗kFFID DI11IP IPIPIPI故故1()DESDES m12151616152111( )kkkkkkkkIPFDFDFDFIP IPFDFDFDFIP m1215161615211( )kkkkkkkkIPFDFDFD FFDFDF

5、DFIP m121515211( )kkkkkkIPFDFDFD D FDFDFIP mm1()IPIP m一、脫密算法一、脫密算法 定理定理1說明：說明：DES的加、脫密算法用的確實(shí)是同的加、脫密算法用的確實(shí)是同一個(gè)算法，唯一不同的是圈密鑰使用次序相反。一個(gè)算法，唯一不同的是圈密鑰使用次序相反。 加脫密的相似性加脫密的相似性 采用采用Feistel模型設(shè)計(jì)的分組密碼算法的逆向操模型設(shè)計(jì)的分組密碼算法的逆向操作和正向操作實(shí)質(zhì)上具有相同的結(jié)構(gòu)，不同之處是作和正向操作實(shí)質(zhì)上具有相同的結(jié)構(gòu)，不同之處是圈密鑰的使用次序相反。圈密鑰的使用次序相反。 每圈對(duì)圈輸入的一半進(jìn)行變換。這樣做似乎使每圈對(duì)圈輸入的

6、一半進(jìn)行變換。這樣做似乎使得加、脫密速度變慢，但其最大的好處是使得人們得加、脫密速度變慢，但其最大的好處是使得人們可以自由地選擇可以自由地選擇f函數(shù)而不要求其可逆，但能保證圈函數(shù)而不要求其可逆，但能保證圈函數(shù)可逆。函數(shù)可逆。一、脫密算法一、脫密算法6464比特明文比特明文fk1L1R1初始置換初始置換6464比特密文比特密文逆初始置換逆初始置換L15R15R16L16L0R0fk16.二、二、DES算法的算法的安全性分析安全性分析PS1S8S2S7S6S4S35S4821 kkk4821 aaa3221 aaaES5 DES分組密碼算法是以分組密碼算法是以Shannon提出的乘積密提出的乘積密

7、碼為基礎(chǔ)設(shè)計(jì)的碼為基礎(chǔ)設(shè)計(jì)的, ,它以代替它以代替（S盒盒）和置換和置換（P盒盒）為基本變換環(huán)節(jié)，經(jīng)過十六次迭代來實(shí)現(xiàn)所謂的混為基本變換環(huán)節(jié)，經(jīng)過十六次迭代來實(shí)現(xiàn)所謂的混亂和擴(kuò)散。亂和擴(kuò)散。 S盒是一個(gè)盒是一個(gè)6進(jìn)進(jìn)4出的非線性函數(shù)，它起到了混出的非線性函數(shù)，它起到了混亂和局部擴(kuò)散的效果，是亂和局部擴(kuò)散的效果，是DES的核心的核心。 P盒將本圈的一個(gè)盒將本圈的一個(gè)S盒的輸出擴(kuò)散到下一圈盡可盒的輸出擴(kuò)散到下一圈盡可能多的能多的S盒中，起到了全體擴(kuò)散的效果盒中，起到了全體擴(kuò)散的效果。二、二、DES算法的安全性分析算法的安全性分析（一）（一）DES算法的互補(bǔ)對(duì)稱性算法的互補(bǔ)對(duì)稱性定理定理2：( ,

8、)( , )DES m kDES m k證明：證明：對(duì)于對(duì)于DES的的f函數(shù)函數(shù)，當(dāng)輸入為當(dāng)輸入為 和和 時(shí)時(shí)，1(,)nnR K1(,)nnRK由于由于11()()nnnnE RKE RK因此因此11(,)(,)nnnnf R Kf R K而而111;(,)nnnnnnLRRLf R K因此當(dāng)圈輸入和圈密鑰都取補(bǔ)時(shí)，可得：因此當(dāng)圈輸入和圈密鑰都取補(bǔ)時(shí)，可得：111(,)(,)nnnnnnnLf RKLf R KR1nnLR二、二、DES算法的安全性分析算法的安全性分析又因?yàn)楫?dāng)初始密鑰取補(bǔ)時(shí)，所得圈密鑰也取補(bǔ)，又因?yàn)楫?dāng)初始密鑰取補(bǔ)時(shí)，所得圈密鑰也取補(bǔ)，并且并且11( )( )IPxIPx( )

9、( )IP mIP m所以有：所以有：( , )( , )DES m kDES m k證畢證畢 定理定理2說明說明：在用在用DES加密時(shí)，若原來的明文加密時(shí)，若原來的明文和原來的密鑰都取補(bǔ)，則相應(yīng)的加密結(jié)果等于對(duì)原和原來的密鑰都取補(bǔ)，則相應(yīng)的加密結(jié)果等于對(duì)原加密結(jié)果取補(bǔ)。加密結(jié)果取補(bǔ)。 DES的互補(bǔ)對(duì)稱性的互補(bǔ)對(duì)稱性二、二、DES算法的安全性分析算法的安全性分析 利用利用DES的互補(bǔ)對(duì)稱性，在選擇明文攻擊時(shí)可的互補(bǔ)對(duì)稱性，在選擇明文攻擊時(shí)可減少一半的窮盡量。減少一半的窮盡量。 已知條件為已知條件為c = DES(m, k)，對(duì)密鑰空間，對(duì)密鑰空間K窮盡，窮盡，試圖恢復(fù)當(dāng)前密鑰試圖恢復(fù)當(dāng)前密鑰k

10、。 任取任取 ，計(jì)算，計(jì)算 11(,)DES m kc1kK(1) 若若c =c1，則，則k1為真，因?yàn)闉檎?，因?yàn)镈ES (m1, k)= c1，否則，否則 (2) 若若 ，則，則 為真為真， 1k2cc選擇用當(dāng)前密鑰選擇用當(dāng)前密鑰k 加密的兩個(gè)明密對(duì)加密的兩個(gè)明密對(duì)(m1,c1), (m2,c2)c1=DES(m1, k), c2=DES(m2, k)，且，且21mm二、二、DES算法的安全性分析算法的安全性分析因?yàn)橐驗(yàn)?，即，即 ，211(,)DES m kcc221(,)DES m kc=由互補(bǔ)對(duì)稱性知由互補(bǔ)對(duì)稱性知 ，212(,)DES m kc=又因又因 DES (m2, k)=c2

11、，則，則 為真。為真。 1k(3) 若兩種情況都不成立，則重新選取不同的密若兩種情況都不成立，則重新選取不同的密鑰鑰k重復(fù)上述過程。重復(fù)上述過程。 當(dāng)我們選取密鑰空間中一個(gè)密鑰當(dāng)我們選取密鑰空間中一個(gè)密鑰k時(shí)，可同時(shí)時(shí)，可同時(shí)驗(yàn)證驗(yàn)證k和和k的補(bǔ)，因此只需搜索密鑰空間的補(bǔ)，因此只需搜索密鑰空間K中的一半中的一半元素即可，也就是說可減少一半的窮盡量。元素即可，也就是說可減少一半的窮盡量。 二、二、DES算法的安全性分析算法的安全性分析（二）關(guān)于逐位模（二）關(guān)于逐位模2加運(yùn)算加運(yùn)算 逐位模2加(按位異或)運(yùn)算是最簡(jiǎn)單的拉丁方變換，它使得變換的輸入、輸出是相關(guān)免疫的。我們以一比特?cái)?shù)據(jù)為例來說明這一點(diǎn)

12、。設(shè)ykx若 k 服從均勻分布，且與 x 獨(dú)立，則有5 . 0)0()(kPxyP 因此異或運(yùn)算使得變換前后的數(shù)據(jù)具有靜態(tài)相關(guān)免疫性。但是從動(dòng)態(tài)的角度來考察，異或運(yùn)算后輸入差與輸出差以1的概率保持不變，即我們必須經(jīng)過S盒的非線性變換來消除這個(gè)缺陷。yxp1二、二、DES算法的安全性分析算法的安全性分析（三）關(guān)于（三）關(guān)于S盒盒 S盒的設(shè)計(jì)準(zhǔn)則：盒的設(shè)計(jì)準(zhǔn)則：1. 每個(gè)每個(gè)S盒的每一行都是盒的每一行都是0到到15的一個(gè)置換。的一個(gè)置換。2.每個(gè)每個(gè)S盒的每一位輸出都不是輸入的線性或仿射函數(shù)。盒的每一位輸出都不是輸入的線性或仿射函數(shù)。3. S盒輸入變化盒輸入變化1比特，輸出至少變化比特，輸出至少變

13、化2比特。比特。4. 對(duì)任意對(duì)任意S盒和盒和任意輸入任意輸入 x0,16，s(x)和和s(x 001100)至少有兩比特不同。至少有兩比特不同。5.對(duì)任意對(duì)任意S盒和盒和任意輸入任意輸入 x0,16，以及任意的以及任意的a, b 0,1， s(x) s(x 11ab00) 。6. 對(duì)任意對(duì)任意S盒，盒，當(dāng)它當(dāng)它的輸入位中某一位固定，其他的輸入位中某一位固定，其他5位位變化時(shí)，所有輸出數(shù)字中變化時(shí)，所有輸出數(shù)字中0和和1的總數(shù)接近相等的總數(shù)接近相等。二、二、DES算法的安全性分析算法的安全性分析（四）關(guān)于（四）關(guān)于P盒置換盒置換 P盒置換起到了盒置換起到了整體擴(kuò)散整體擴(kuò)散的作用，它設(shè)計(jì)得好的作用

14、，它設(shè)計(jì)得好壞，對(duì)壞，對(duì)DES算法的安全強(qiáng)度是非常重要的，算法的安全強(qiáng)度是非常重要的，P盒的盒的設(shè)計(jì)原則為：設(shè)計(jì)原則為： 經(jīng)過經(jīng)過S盒變換后輸出的盒變換后輸出的4個(gè)比特，經(jīng)個(gè)比特，經(jīng)P盒變換后盒變換后作為下一圈迭代的輸入時(shí)，不再進(jìn)入同一個(gè)作為下一圈迭代的輸入時(shí)，不再進(jìn)入同一個(gè)S盒，盒，保證最大限度的擴(kuò)散。保證最大限度的擴(kuò)散。二、二、DES算法的安全性分析算法的安全性分析（五）關(guān)于密鑰（五）關(guān)于密鑰 DES的密鑰生成算法的設(shè)計(jì)思想是將的密鑰生成算法的設(shè)計(jì)思想是將56比特比特有效密鑰中的每一比特，均勻作用于圈密鑰上，有效密鑰中的每一比特，均勻作用于圈密鑰上，即初始密鑰中的每一比特的使用次數(shù)基本相同

15、即初始密鑰中的每一比特的使用次數(shù)基本相同（12次至次至15次之間）次之間）。 在圈密鑰生成算法中，每一圈循環(huán)左移的位在圈密鑰生成算法中，每一圈循環(huán)左移的位數(shù)不盡相同，這是為了抵抗對(duì)數(shù)不盡相同，這是為了抵抗對(duì)DES實(shí)施相關(guān)密鑰實(shí)施相關(guān)密鑰攻擊。攻擊。二、二、DES算法的安全性分析算法的安全性分析（六）弱密鑰和半弱密鑰（六）弱密鑰和半弱密鑰 DES存在著弱密鑰、半弱密鑰等，但它們出存在著弱密鑰、半弱密鑰等，但它們出現(xiàn)的概率極小，以至于小到可以忽略的程度，因現(xiàn)的概率極小，以至于小到可以忽略的程度，因此從應(yīng)用的角度來看，是沒有必要考慮的。此從應(yīng)用的角度來看，是沒有必要考慮的。 對(duì)初始密鑰對(duì)初始密鑰k，

16、若通過密鑰生成算法生成的圈，若通過密鑰生成算法生成的圈密鑰都相同，則稱密鑰都相同，則稱k為為弱密鑰弱密鑰；若通過密鑰生成算；若通過密鑰生成算法生成的圈密鑰只有兩種取值，且這兩種取值各法生成的圈密鑰只有兩種取值，且這兩種取值各占一半，則稱占一半，則稱k為為半弱密鑰半弱密鑰或或二分之一弱密鑰二分之一弱密鑰；類；類似地，還可以定義四分之一弱密鑰等。似地，還可以定義四分之一弱密鑰等。二、二、DES算法的安全性分析算法的安全性分析（七）完全性（七）完全性 所謂所謂完全性完全性是指經(jīng)過若干圈迭代后，輸出的是指經(jīng)過若干圈迭代后，輸出的64比特中的每一比特都包含有輸入的每一比特信息。比特中的每一比特都包含有輸

17、入的每一比特信息。 一個(gè)分組密碼算法的完全性是其安全性的基本一個(gè)分組密碼算法的完全性是其安全性的基本要求，要求，DES是通過是通過E盒和盒和S盒的局部混亂和擴(kuò)散以及盒的局部混亂和擴(kuò)散以及P盒的整體擴(kuò)散來實(shí)現(xiàn)完全性的。盒的整體擴(kuò)散來實(shí)現(xiàn)完全性的。 DES經(jīng)過經(jīng)過幾幾圈迭代能實(shí)現(xiàn)完全性呢？圈迭代能實(shí)現(xiàn)完全性呢？二、二、DES算法的安全性分析算法的安全性分析Pa1 a2 a32S1S8S2S7S6S4S3S5DES算法的算法的 f 函數(shù)函數(shù)Ea1 a2 a3 a48k1 k2 k3 k48將進(jìn)入將進(jìn)入4個(gè)個(gè)S盒盒1iiLR11(,)iiiiRLf Rki圈圈：Li 實(shí)現(xiàn)對(duì)實(shí)現(xiàn)對(duì)Ri-1的的1比特?cái)U(kuò)散

18、；比特?cái)U(kuò)散； Ri實(shí)現(xiàn)對(duì)實(shí)現(xiàn)對(duì)Li-1 的的1比比特?cái)U(kuò)散和對(duì)特?cái)U(kuò)散和對(duì)Ri-1 的的4比特?cái)U(kuò)散。比特?cái)U(kuò)散。DES經(jīng)過經(jīng)過5圈迭代實(shí)現(xiàn)了完全性。圈迭代實(shí)現(xiàn)了完全性。二、二、DES算法的安全性分析算法的安全性分析（八）差分與線性密碼分析（八）差分與線性密碼分析 1990年，年，Eli Biham和和Adi Shamir提出了差分密提出了差分密碼分析方法，利用這種方法，他們找到了一個(gè)選擇碼分析方法，利用這種方法，他們找到了一個(gè)選擇明文的明文的DES攻擊方法，對(duì)一個(gè)攻擊方法，對(duì)一個(gè)16輪輪DES的最佳攻擊的最佳攻擊需要需要247個(gè)選擇明文，比窮盡攻擊有效。個(gè)選擇明文，比窮盡攻擊有效。 如果利用已知明文

19、攻擊，對(duì)低于如果利用已知明文攻擊，對(duì)低于16輪的輪的DES要要比窮盡攻擊有效，但恰好比窮盡攻擊有效，但恰好16輪時(shí)卻需要輪時(shí)卻需要255個(gè)已知明個(gè)已知明文。因此，差分密碼分析對(duì)文。因此，差分密碼分析對(duì)16輪輪DES僅有理論上的僅有理論上的價(jià)值。價(jià)值。二、二、DES算法的安全性分析算法的安全性分析（八）差分與線性密碼分析（八）差分與線性密碼分析 1993年，年，Mitsuru Matsui提出了線性密碼分析提出了線性密碼分析方法，利用這種方法攻擊完整的方法，利用這種方法攻擊完整的16輪輪DES，當(dāng)已知，當(dāng)已知明文的平均數(shù)為明文的平均數(shù)為243時(shí)可得到密鑰。到目前為止，它時(shí)可得到密鑰。到目前為止，

20、它還是最有效的攻擊還是最有效的攻擊DES的方法。的方法。二、二、DES算法的安全性分析算法的安全性分析（一）密鑰長(zhǎng)度（一）密鑰長(zhǎng)度（二）迭代次數(shù)（二）迭代次數(shù)（三）（三）S盒盒DES的的安全性安全性二、二、DES算法的安全性分析算法的安全性分析 隨著密碼分析技術(shù)和計(jì)算能力的提高，隨著密碼分析技術(shù)和計(jì)算能力的提高，DES的的安全性受到質(zhì)疑和威脅。安全性受到質(zhì)疑和威脅。密鑰較短密鑰較短是是 DES的一個(gè)的一個(gè)主要缺陷。為了提高主要缺陷。為了提高DES的安全性能并充分利用有的安全性能并充分利用有關(guān)關(guān)DES的現(xiàn)有資源，有人提出利用的現(xiàn)有資源，有人提出利用DES和多個(gè)密鑰和多個(gè)密鑰進(jìn)行多次加密，這方面的兩個(gè)典型例子是雙重進(jìn)行多次加密，這方面的兩個(gè)典型例子是雙重DES和三重和三重DES。三、多重三、多重DES（一）雙重（一）雙重DES 雙重雙重DES是分別用兩個(gè)不同的密鑰是分別用兩個(gè)不同的密鑰k1和和k2