分組密碼 41分組密碼設(shè)計原則和設(shè)計方法

1、密碼學(xué)第四章 分組密碼主要內(nèi)容：主要內(nèi)容：分組密碼的基本概念，分組密碼的基本分組密碼的基本概念，分組密碼的基本設(shè)計原則和設(shè)計方法，典型的分組密碼算法，常見設(shè)計原則和設(shè)計方法，典型的分組密碼算法，常見的分組密碼攻擊方法，以及分組密碼的工作模式等。的分組密碼攻擊方法，以及分組密碼的工作模式等。重點(diǎn)：重點(diǎn)：數(shù)據(jù)加密標(biāo)準(zhǔn)數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)、高級加密標(biāo)準(zhǔn)、高級加密標(biāo)準(zhǔn)(AES)。 希望希望大家能理解分組密碼設(shè)計的原理與方法，大家能理解分組密碼設(shè)計的原理與方法，掌握掌握DES、AES等分組密碼算法，了解常見的分組等分組密碼算法，了解常見的分組密碼安全性分析方法。密碼安全性分析方法。第四章 分組密碼4.

2、1 分組密碼設(shè)計原則和設(shè)計方法 分組密碼概述分組密碼概述分組密碼設(shè)計原則分組密碼設(shè)計原則 分組密碼設(shè)計方法分組密碼設(shè)計方法4.1 分組密碼設(shè)計原則和設(shè)計方法 分組密碼分組密碼是將明文數(shù)據(jù)序列按固定長度是將明文數(shù)據(jù)序列按固定長度進(jìn)行分組，然后在同一密鑰控制下用同一算進(jìn)行分組，然后在同一密鑰控制下用同一算法逐組進(jìn)行加密，從而將各個明文分組變換法逐組進(jìn)行加密，從而將各個明文分組變換成一個長度固定的密文分組的密碼。成一個長度固定的密文分組的密碼。一、分組密碼概述一、分組密碼概述 二進(jìn)制明文的分組長度稱為該分組密碼二進(jìn)制明文的分組長度稱為該分組密碼的的分組長度分組長度或或分組規(guī)模分組規(guī)模。同樣，二進(jìn)制密

3、鑰。同樣，二進(jìn)制密鑰的長度稱為分組密碼的的長度稱為分組密碼的密鑰長度密鑰長度或或密鑰規(guī)模密鑰規(guī)模。主要特點(diǎn)：主要特點(diǎn)：同一密鑰，同一加密算法，同一密鑰，同一加密算法， 分組加密，分組長度固定。分組加密，分組長度固定。 1212122nnnnmmx xx xxx 加加密密算算法法k加加密密算算法法k 1212122ccssssy yy yyy 明文明文密文密文加密加密：(),1,2,ikicEmi12,cc c12mm m一、分組密碼概述一、分組密碼概述 明文分組長度為明文分組長度為n，密文分組長度為，密文分組長度為s，若若n s，則稱其為有數(shù)據(jù)，則稱其為有數(shù)據(jù)壓縮壓縮的分組密碼；的分組密碼；若

4、若n s，則稱其為有數(shù)據(jù)，則稱其為有數(shù)據(jù)擴(kuò)展擴(kuò)展的分組密碼。的分組密碼。本章我們都取本章我們都取 n = s例例1 移位密碼中的電文倒置法移位密碼中的電文倒置法明文為：明文為： 2346 3498密文為：密文為： 6432 8943密鑰（密鑰（4321）一、分組密碼概述一、分組密碼概述例例2 代替密碼代替密碼 明文為：明文為： 2346 3498密文為：密文為： 4560 5628一、分組密碼概述一、分組密碼概述 安全原則安全原則 實(shí)現(xiàn)原則實(shí)現(xiàn)原則二、分組密碼基本設(shè)計原則二、分組密碼基本設(shè)計原則 安全原則安全原則二、分組密碼基本設(shè)計原則二、分組密碼基本設(shè)計原則 安全性安全性是分組密碼設(shè)計時應(yīng)考

5、慮的最重要因是分組密碼設(shè)計時應(yīng)考慮的最重要因素。人們一般將素。人們一般將Shannon提出的提出的混亂原則混亂原則和和擴(kuò)散擴(kuò)散原則原則作為保證分組密碼安全性的兩個基本設(shè)計原作為保證分組密碼安全性的兩個基本設(shè)計原則。則?；靵y原則混亂原則1.安全原則安全原則擴(kuò)散原則擴(kuò)散原則二、分組密碼基本設(shè)計原則二、分組密碼基本設(shè)計原則 混亂原則混亂原則就是將就是將密文、明文、密鑰密文、明文、密鑰三者之三者之間間的統(tǒng)計關(guān)系和的統(tǒng)計關(guān)系和代數(shù)關(guān)系代數(shù)關(guān)系變得盡可能復(fù)雜，保變得盡可能復(fù)雜，保證密鑰和明文的任何信息既不能由密文利用統(tǒng)證密鑰和明文的任何信息既不能由密文利用統(tǒng)計關(guān)系確定出來，又不能由密文利用代數(shù)方法計關(guān)系確

6、定出來，又不能由密文利用代數(shù)方法確定出來。確定出來。( )( ,)kcE mf k m二、分組密碼基本設(shè)計原則二、分組密碼基本設(shè)計原則 可進(jìn)一步理解為：可進(jìn)一步理解為：（1 1）當(dāng)前明文不能由已知的明文、密文及）當(dāng)前明文不能由已知的明文、密文及少許密鑰比特代數(shù)地表示出來。少許密鑰比特代數(shù)地表示出來。（2 2）當(dāng)前）當(dāng)前密鑰不能由已知的明文、密文及密鑰不能由已知的明文、密文及少許密鑰比特統(tǒng)計地表示出來。少許密鑰比特統(tǒng)計地表示出來。 混亂原則使得分組密碼算法有足夠的混亂原則使得分組密碼算法有足夠的“非線性非線性”因素。因素。二、分組密碼基本設(shè)計原則二、分組密碼基本設(shè)計原則 擴(kuò)散原則要求人們設(shè)計的密

7、碼應(yīng)使得每個擴(kuò)散原則要求人們設(shè)計的密碼應(yīng)使得每個明文明文比特和比特和密鑰密鑰比特影響盡可能多的比特影響盡可能多的密文密文比特。比特。 擴(kuò)散原則應(yīng)將明文的統(tǒng)計規(guī)律和結(jié)構(gòu)規(guī)律擴(kuò)散原則應(yīng)將明文的統(tǒng)計規(guī)律和結(jié)構(gòu)規(guī)律散射到相當(dāng)長的一段統(tǒng)計中去。散射到相當(dāng)長的一段統(tǒng)計中去。二、分組密碼基本設(shè)計原則二、分組密碼基本設(shè)計原則 （1 1）明文和密鑰中的每一位影響密文中的）明文和密鑰中的每一位影響密文中的盡可能多的位；盡可能多的位； （2 2）密文中的每一位都受到明文和密鑰中）密文中的每一位都受到明文和密鑰中的盡可能多位的影響。的盡可能多位的影響。 擴(kuò)散原則使得擴(kuò)散原則使得每個明文比特和密鑰比特均每個明文比特和密

8、鑰比特均應(yīng)影響密文的所有比特應(yīng)影響密文的所有比特。二、分組密碼基本設(shè)計原則二、分組密碼基本設(shè)計原則 實(shí)現(xiàn)原則實(shí)現(xiàn)原則二、分組密碼基本設(shè)計原則二、分組密碼基本設(shè)計原則 硬件硬件實(shí)現(xiàn)原則實(shí)現(xiàn)原則2.實(shí)現(xiàn)原則實(shí)現(xiàn)原則 軟件軟件實(shí)現(xiàn)原則實(shí)現(xiàn)原則二、分組密碼基本設(shè)計原則二、分組密碼基本設(shè)計原則硬件實(shí)現(xiàn)原則硬件實(shí)現(xiàn)原則 硬件實(shí)現(xiàn)分組密碼，通常是硬件實(shí)現(xiàn)分組密碼，通常是將密碼算法做將密碼算法做成一個專用的超大規(guī)模集成電路芯片成一個專用的超大規(guī)模集成電路芯片。這可使。這可使加、脫密運(yùn)算高速完成，但需大批量生產(chǎn)方可加、脫密運(yùn)算高速完成，但需大批量生產(chǎn)方可降低成本。因此，硬件實(shí)現(xiàn)適合對信息快速、降低成本。因此，硬

9、件實(shí)現(xiàn)適合對信息快速、實(shí)時進(jìn)行處理的系統(tǒng)，以及可大規(guī)模生產(chǎn)的時實(shí)時進(jìn)行處理的系統(tǒng)，以及可大規(guī)模生產(chǎn)的時候。候。二、分組密碼基本設(shè)計原則二、分組密碼基本設(shè)計原則硬件實(shí)現(xiàn)原則硬件實(shí)現(xiàn)原則 用硬件實(shí)現(xiàn)的分組密碼應(yīng)遵循下述原則：用硬件實(shí)現(xiàn)的分組密碼應(yīng)遵循下述原則：(1) (1) 加、脫密算法結(jié)構(gòu)相同；加、脫密算法結(jié)構(gòu)相同；(2) (2) 結(jié)構(gòu)的規(guī)則性；結(jié)構(gòu)的規(guī)則性；(3) (3) 設(shè)計成迭代型；設(shè)計成迭代型；(4) (4) 選擇易于硬件實(shí)現(xiàn)的編碼環(huán)節(jié)，避免硬件選擇易于硬件實(shí)現(xiàn)的編碼環(huán)節(jié)，避免硬件難于實(shí)現(xiàn)的編碼環(huán)節(jié)。難于實(shí)現(xiàn)的編碼環(huán)節(jié)。二、分組密碼基本設(shè)計原則二、分組密碼基本設(shè)計原則軟件實(shí)現(xiàn)原則軟件實(shí)現(xiàn)

10、原則 軟件實(shí)現(xiàn)分組密碼，軟件實(shí)現(xiàn)分組密碼，成本較低且可以靈活地成本較低且可以靈活地編程編程，但其速度一般沒有硬件實(shí)現(xiàn)快。，但其速度一般沒有硬件實(shí)現(xiàn)快。 用軟件實(shí)現(xiàn)的分組密碼應(yīng)遵循下述原則：用軟件實(shí)現(xiàn)的分組密碼應(yīng)遵循下述原則：(1) (1) 加、脫密加、脫密算法結(jié)構(gòu)算法結(jié)構(gòu)的相似性；的相似性；(2) (2) 使用子塊；使用子塊；(3) (3) 設(shè)計成迭代型；設(shè)計成迭代型；(4) (4) 使用既簡單又易于軟件實(shí)現(xiàn)的運(yùn)算。使用既簡單又易于軟件實(shí)現(xiàn)的運(yùn)算。二、分組密碼基本設(shè)計原則二、分組密碼基本設(shè)計原則 對一個分組密碼，對一個分組密碼，安全原則安全原則要求其實(shí)現(xiàn)足夠要求其實(shí)現(xiàn)足夠的的混亂混亂和和擴(kuò)散擴(kuò)

11、散，實(shí)現(xiàn)原則實(shí)現(xiàn)原則要求其要求其易于軟件和易于軟件和(或或)硬件實(shí)現(xiàn)硬件實(shí)現(xiàn)。 Shannon提出提出乘積密碼乘積密碼的思想。的思想。乘積密碼的乘積密碼的基本思想基本思想是通過將一個是通過將一個易于實(shí)現(xiàn)的易于實(shí)現(xiàn)的具有一定混亂具有一定混亂和擴(kuò)散結(jié)構(gòu)的和擴(kuò)散結(jié)構(gòu)的較弱的密碼函數(shù)較弱的密碼函數(shù)進(jìn)行進(jìn)行多次迭代多次迭代來來產(chǎn)產(chǎn)生一個強(qiáng)的密碼函數(shù)生一個強(qiáng)的密碼函數(shù)。 三、分組密碼設(shè)計方法三、分組密碼設(shè)計方法（一）（一）乘積密碼乘積密碼 Shannon在在1949提出，其主要思想就是通過提出，其主要思想就是通過簡單密碼的乘積來組合密碼體制。簡單密碼的乘積來組合密碼體制。 1111(, ,)SM C K

12、E D2222(, ,)SM C KE D假設(shè)假設(shè) M= C S1和和 S2的乘積密碼體制的乘積密碼體制 S1S2定義為定義為：1212(,)SSM C KKE D密鑰形式為：密鑰形式為：K= ( K1，K2 ) 三、分組密碼設(shè)計方法三、分組密碼設(shè)計方法加密和解密規(guī)則定義如下加密和解密規(guī)則定義如下： 1221(,)( )( )( )KK KKKExExEExy1212(,)( )( )( )KK KKKDyDyDDyx注意：注意：解密次序與加密次序相反解密次序與加密次序相反 12122111(,)( )( )( )K KKKKKKKDyDDEExDExx三、分組密碼設(shè)計方法三、分組密碼設(shè)計方法

13、例例3: (乘法密碼乘法密碼) )設(shè)設(shè) M=C=Z261)26,gcd(:26aZaK對于對于 ，明文明文 x，密文密文 y，定義定義：aK( )(mod26)aExax1( )(mod26)aDya y例例4: (移位密碼移位密碼) )設(shè)設(shè) M=C=K=Z26對于對于 ，明文，明文 x，密文，密文 y，定義，定義：kK( )()(mod26)kExxk( )()(mod26)kDyyk三、分組密碼設(shè)計方法三、分組密碼設(shè)計方法 假設(shè)假設(shè) S1 是乘法密碼，是乘法密碼， S2 是移位密碼，很容是移位密碼，很容易看出易看出 S1 S2 是仿射密碼是仿射密碼。對于對于S1 S2 ，其密鑰形式為，其密

14、鑰形式為（a, k） ( , )( )()(mod26)a kExaxk對于對于S2 S1 ，其密鑰形式為，其密鑰形式為（k, a） ( , )( )()(mod26)()(mod26)k aExa xkaxak三、分組密碼設(shè)計方法三、分組密碼設(shè)計方法 如果將密碼體制如果將密碼體制 S 和自己做乘積，得到密碼和自己做乘積，得到密碼體制體制 SS，記為，記為S 2。如果做。如果做 n 重乘積，得到的密重乘積，得到的密碼體制記為碼體制記為S n。 如果如果S 2= S，稱該密碼體制是冪等的。，稱該密碼體制是冪等的。 如果密碼體制是冪等的，使用乘積系統(tǒng)就毫如果密碼體制是冪等的，使用乘積系統(tǒng)就毫無意義

15、，這是因?yàn)槭褂枚嘤嗟拿荑€，但并不能提無意義，這是因?yàn)槭褂枚嘤嗟拿荑€，但并不能提高更多的安全性。高更多的安全性。 如果密碼體制不是冪等的，多次乘積就有可如果密碼體制不是冪等的，多次乘積就有可能提高安全性。通常是將能提高安全性。通常是將代替密碼代替密碼和和置換密碼置換密碼做做乘積。乘積。三、分組密碼設(shè)計方法三、分組密碼設(shè)計方法（二）（二）迭代密碼迭代密碼 當(dāng)今大多數(shù)分組密碼都是乘積密碼，乘積密當(dāng)今大多數(shù)分組密碼都是乘積密碼，乘積密碼通常伴隨一系列置換與代替操作，常見的乘積碼通常伴隨一系列置換與代替操作，常見的乘積密碼是迭代密碼。密碼是迭代密碼。 迭代密碼通過將一個弱的密碼函數(shù)迭代密碼通過將一個弱的

16、密碼函數(shù)(稱為圈函稱為圈函數(shù)、輪函數(shù)等數(shù)、輪函數(shù)等)迭代若干次，產(chǎn)生一個強(qiáng)的密碼函迭代若干次，產(chǎn)生一個強(qiáng)的密碼函數(shù)，既能快速、有效地實(shí)現(xiàn)，又能使明文和密鑰數(shù)，既能快速、有效地實(shí)現(xiàn)，又能使明文和密鑰得到必要的混亂和擴(kuò)散。得到必要的混亂和擴(kuò)散。三、分組密碼設(shè)計方法三、分組密碼設(shè)計方法1kF2krkFFF 稱為圈變換、圈函數(shù)或輪稱為圈變換、圈函數(shù)或輪函數(shù)，函數(shù)，r 稱為迭代次數(shù)、圈稱為迭代次數(shù)、圈數(shù)或輪數(shù)。數(shù)或輪數(shù)。12,rk kk是是 r 個圈子密鑰個圈子密鑰三、分組密碼設(shè)計方法三、分組密碼設(shè)計方法 在設(shè)計圈函數(shù)時，要充分在設(shè)計圈函數(shù)時，要充分利用利用代替密碼代替密碼( (實(shí)現(xiàn)混亂實(shí)現(xiàn)混亂) )和

17、和移移位密碼位密碼( (實(shí)現(xiàn)擴(kuò)散實(shí)現(xiàn)擴(kuò)散) )各自的優(yōu)點(diǎn)，各自的優(yōu)點(diǎn)，抵消各自的缺點(diǎn)，保證通過多抵消各自的缺點(diǎn)，保證通過多次迭代，形成一個強(qiáng)的分組密次迭代，形成一個強(qiáng)的分組密碼算法。碼算法。 對于一個給定的密鑰編排方案，圈函數(shù)對于一個給定的密鑰編排方案，圈函數(shù) F的輸入為圈密鑰的輸入為圈密鑰kr和當(dāng)前狀態(tài)和當(dāng)前狀態(tài)wr-1，下一個狀態(tài)，下一個狀態(tài)定義為：定義為：wr=F(wr-1,kr)。初態(tài)。初態(tài) w0定義為明文定義為明文 x，密文密文y定義為經(jīng)過定義為經(jīng)過 r 輪后的狀態(tài)。輪后的狀態(tài)。w0 xw1F(w0,k1)w2F(w1,k2)wr-1F(wr-2,kr-1)wrF(wr-1,kr)y

18、wr加密過程：加密過程： 解密過程：解密過程： wrywr-1F-1(wr,kr)wr-2F-1 (wr-1,kr-1)w1F-1 (w2,k2)w0F-1 (w1,k1)xw0 三、分組密碼設(shè)計方法三、分組密碼設(shè)計方法 迭代密碼迭代密碼的常見模型有的常見模型有S-P網(wǎng)絡(luò)網(wǎng)絡(luò)(代代替替-置換網(wǎng)絡(luò)置換網(wǎng)絡(luò))、 Feistel網(wǎng)絡(luò)網(wǎng)絡(luò)等。等。 三、分組密碼設(shè)計方法三、分組密碼設(shè)計方法（三）（三）代替置換網(wǎng)絡(luò)代替置換網(wǎng)絡(luò)（S-PN） 一個一個S-PN就是一類特殊的迭代密碼。設(shè)就是一類特殊的迭代密碼。設(shè)l和和m都是正整數(shù)，明密文都是長為都是正整數(shù)，明密文都是長為lm的二元向量，一的二元向量，一個個S-PN包含兩個變換，分別記為包含兩個變換，分別記為s和和p。:0,10,1lls實(shí)現(xiàn)實(shí)現(xiàn) l 比特的代替，即比