第二章分組密碼PPT課件

1、第二章 分組密碼 分組密碼在許多密碼系統(tǒng)中都是最重要的組成部分。它能實(shí)現(xiàn)保密性。作為基本的建筑塊，它可以用在許多方面，如：構(gòu)造偽隨機(jī)數(shù)生成器、流密碼、認(rèn)證碼和哈希函數(shù)。更進(jìn)一步在消息認(rèn)證技術(shù)、數(shù)據(jù)完整性機(jī)制、實(shí)體認(rèn)證協(xié)議及數(shù)字簽名方案中也可以作為核心部件。 一種分組加密算法不可能適用所有場(chǎng)合。在實(shí)際應(yīng)用中往往對(duì)速度有要求、存儲(chǔ)量及實(shí)現(xiàn)平臺(tái)有限制。應(yīng)用中必須對(duì)各種運(yùn)算模式的承受能力等諸多因素進(jìn)行平衡。 分組加密函數(shù)是從n位明文塊到n位密文塊的映射， n稱(chēng)為塊長(zhǎng)。nnkE1 , 01 , 0: 解密函數(shù) 應(yīng)滿(mǎn)足 。為解密的唯一性，要求加密函數(shù)必須是雙射，即把加密函數(shù)看成n維向量的置換，由不同的k定

2、義不同的置換。這里假設(shè)敵手能夠竊聽(tīng)在線(xiàn)路上傳送的全部密文，并且知道加密函數(shù)的全部細(xì)節(jié)，只是不知道密鑰 k。 評(píng)價(jià)分組加密和使用模式的標(biāo)準(zhǔn)是：1kkEDmmEDkk)(1)預(yù)估的安全水平（多長(zhǎng)時(shí)間能被攻破，破譯需要的預(yù)估的安全水平（多長(zhǎng)時(shí)間能被攻破，破譯需要的密文數(shù)量等）密文數(shù)量等）;(2)密鑰的有效位長(zhǎng)密鑰的有效位長(zhǎng); (3) (3)塊的大小塊的大小;(4)加密映射的復(fù)雜性加密映射的復(fù)雜性;(5)數(shù)據(jù)的擴(kuò)張數(shù)據(jù)的擴(kuò)張(Data Expansion);(Data Expansion);(6)錯(cuò)誤的擴(kuò)散錯(cuò)誤的擴(kuò)散(Error Propagation);(Error Propagation); C.

3、E.Shannon C.E.Shannon在他的論文在他的論文“Communication Theory Communication Theory of Secrecy Systemof Secrecy System”中提出設(shè)計(jì)分組加密的組合密碼中提出設(shè)計(jì)分組加密的組合密碼系統(tǒng)的觀點(diǎn)。為了便于實(shí)現(xiàn)，實(shí)際應(yīng)用中常常將簡(jiǎn)單系統(tǒng)的觀點(diǎn)。為了便于實(shí)現(xiàn)，實(shí)際應(yīng)用中常常將簡(jiǎn)單且容易實(shí)現(xiàn)的密碼系統(tǒng)組合成比較復(fù)雜、密鑰量大的且容易實(shí)現(xiàn)的密碼系統(tǒng)組合成比較復(fù)雜、密鑰量大的密碼系統(tǒng)。一些最有效、最實(shí)際的分組密碼主都是采密碼系統(tǒng)。一些最有效、最實(shí)際的分組密碼主都是采用乘積組合方法。用乘積組合方法。假設(shè)假設(shè)是子密碼系

4、統(tǒng)，是子密碼系統(tǒng)，是乘是乘積密碼系統(tǒng)，積密碼系統(tǒng)，它相應(yīng)的加密函數(shù)是子密碼系統(tǒng)加密函它相應(yīng)的加密函數(shù)是子密碼系統(tǒng)加密函數(shù)的合成函數(shù)。乘積密碼的基本思想是把幾個(gè)簡(jiǎn)單運(yùn)數(shù)的合成函數(shù)。乘積密碼的基本思想是把幾個(gè)簡(jiǎn)單運(yùn)算合成一個(gè)復(fù)雜的加密函數(shù)。這些簡(jiǎn)單運(yùn)算可以是塊算合成一個(gè)復(fù)雜的加密函數(shù)。這些簡(jiǎn)單運(yùn)算可以是塊內(nèi)符號(hào)簡(jiǎn)單換位（內(nèi)符號(hào)簡(jiǎn)單換位（Transposition）、異或運(yùn)算）、異或運(yùn)算(XOR)、線(xiàn)性變換線(xiàn)性變換(LinearTransformation)、算術(shù)運(yùn)算、模乘、算術(shù)運(yùn)算、模乘(ModularMultiplication)、簡(jiǎn)單替換、簡(jiǎn)單替換(Substitution)等。等。12,lS

5、 SS12lSS SS將加密函數(shù)反復(fù)多次執(zhí)行形成迭代密碼將加密函數(shù)反復(fù)多次執(zhí)行形成迭代密碼(IteratedBlockCipher)是一種最簡(jiǎn)單的乘積密碼。為了挫敗敵手的統(tǒng)是一種最簡(jiǎn)單的乘積密碼。為了挫敗敵手的統(tǒng)計(jì)分析計(jì)分析Shannon還建議采用兩種方法，一個(gè)是在加密還建議采用兩種方法，一個(gè)是在加密前去掉語(yǔ)言的剩余度，另一個(gè)是采用擴(kuò)散和混淆方法。前去掉語(yǔ)言的剩余度，另一個(gè)是采用擴(kuò)散和混淆方法。所謂擴(kuò)散所謂擴(kuò)散(Diffusion)是指將密鑰和明文的任何一位都是指將密鑰和明文的任何一位都影響密文的許多位。前者防止對(duì)密鑰進(jìn)行分段破譯，影響密文的許多位。前者防止對(duì)密鑰進(jìn)行分段破譯，后者用于隱藏明文

6、的統(tǒng)計(jì)特性。后者用于隱藏明文的統(tǒng)計(jì)特性?；煜煜?Confusion)是指把密鑰和明文、密文和密文之間的依是指把密鑰和明文、密文和密文之間的依賴(lài)關(guān)系復(fù)雜化，使得密碼分析者無(wú)法利用這種依賴(lài)性。所賴(lài)關(guān)系復(fù)雜化，使得密碼分析者無(wú)法利用這種依賴(lài)性。所有加密和解密算法都是有計(jì)算機(jī)硬件或軟件實(shí)現(xiàn)的。在設(shè)有加密和解密算法都是有計(jì)算機(jī)硬件或軟件實(shí)現(xiàn)的。在設(shè)計(jì)過(guò)程中必須考慮計(jì)算機(jī)的特點(diǎn)。例如：密碼運(yùn)算要在子計(jì)過(guò)程中必須考慮計(jì)算機(jī)的特點(diǎn)。例如：密碼運(yùn)算要在子塊上進(jìn)行，那么子塊長(zhǎng)度最好是塊上進(jìn)行，那么子塊長(zhǎng)度最好是8 8，1616，32 32 位。運(yùn)算最好位。運(yùn)算最好采用機(jī)器的基本指令，如加法，乘法采用機(jī)器的基本指

7、令，如加法，乘法, , 移位等。另外加密移位等。另外加密和解密算法最好具有同樣的組件結(jié)構(gòu)，以便使用大規(guī)模集和解密算法最好具有同樣的組件結(jié)構(gòu)，以便使用大規(guī)模集成電路實(shí)現(xiàn)。成電路實(shí)現(xiàn)。 2.1數(shù)據(jù)加密標(biāo)準(zhǔn)數(shù)據(jù)加密標(biāo)準(zhǔn)（DataEncryptionStandard簡(jiǎn)稱(chēng)簡(jiǎn)稱(chēng)DES） DESDES算法是最為廣泛使用的一種分組密算法是最為廣泛使用的一種分組密碼算法。碼算法。DESDES對(duì)推動(dòng)密碼理論的發(fā)展和應(yīng)對(duì)推動(dòng)密碼理論的發(fā)展和應(yīng)用起了重大作用。學(xué)習(xí)用起了重大作用。學(xué)習(xí)DESDES算法對(duì)于掌握算法對(duì)于掌握分組密碼的基本理論、設(shè)計(jì)思想和實(shí)際應(yīng)分組密碼的基本理論、設(shè)計(jì)思想和實(shí)際應(yīng)用都有重要參考價(jià)值。用都有重

8、要參考價(jià)值。 2.1.1 DES2.1.1 DES發(fā)展歷史發(fā)展歷史 19721972美國(guó)商業(yè)部所屬的國(guó)家標(biāo)準(zhǔn)局美國(guó)商業(yè)部所屬的國(guó)家標(biāo)準(zhǔn)局(NBS)(NBS)開(kāi)始實(shí)開(kāi)始實(shí)施施計(jì)算機(jī)數(shù)據(jù)保護(hù)標(biāo)準(zhǔn)的開(kāi)發(fā)計(jì)劃。計(jì)算機(jī)數(shù)據(jù)保護(hù)標(biāo)準(zhǔn)的開(kāi)發(fā)計(jì)劃。1973.5.13NBS發(fā)布文告征集在傳輸和存貯數(shù)據(jù)中保護(hù)發(fā)布文告征集在傳輸和存貯數(shù)據(jù)中保護(hù) 計(jì)算機(jī)數(shù)據(jù)的密碼算法計(jì)算機(jī)數(shù)據(jù)的密碼算法.1975.3.17首次公布首次公布DES算法描述算法描述,真地進(jìn)行公開(kāi)討論真地進(jìn)行公開(kāi)討論. 1977.1.151977.1.15正式批準(zhǔn)為無(wú)密級(jí)應(yīng)用的加密標(biāo)準(zhǔn)正式批準(zhǔn)為無(wú)密級(jí)應(yīng)用的加密標(biāo)準(zhǔn)(FIPS-46)(FIPS-46)，7

9、7月月1515日正式生效。每隔五年美國(guó)國(guó)家安全局日正式生效。每隔五年美國(guó)國(guó)家安全局(NSA)(NSA)作出作出評(píng)估，并重新確定是否繼續(xù)作為加密標(biāo)準(zhǔn)。最近的一次評(píng)評(píng)估，并重新確定是否繼續(xù)作為加密標(biāo)準(zhǔn)。最近的一次評(píng)估是在估是在19941994年年1 1月，決定在月，決定在19981998年年1212月以后不再作為加密月以后不再作為加密標(biāo)準(zhǔn)標(biāo)準(zhǔn).（補(bǔ)充美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)局（補(bǔ)充美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)局NISTNIST從從19971997年年4 4月月1515日開(kāi)日開(kāi)始征集和評(píng)估新的數(shù)據(jù)加密標(biāo)準(zhǔn)始征集和評(píng)估新的數(shù)據(jù)加密標(biāo)準(zhǔn)AESAESAdvanced Advanced Encryption Standard

10、Encryption Standard。到。到19991999年年3 3月選出月選出1515個(gè)，個(gè)，5 5月再?gòu)脑略購(gòu)闹羞x出中選出5 5個(gè)，預(yù)計(jì)（？）在個(gè)，預(yù)計(jì)（？）在20012001年出臺(tái)年出臺(tái)AESAES。）。）2.1.2 DES2.1.2 DES算法描述算法描述 DES DES算法中密鑰長(zhǎng)度算法中密鑰長(zhǎng)度5656位位(bit)(bit),明文和密文長(zhǎng)度明文和密文長(zhǎng)度6464位位(bit).(bit). DES DES是一個(gè)使用是一個(gè)使用5656位有效密鑰的位有效密鑰的6464位分組密碼。它的加密位分組密碼。它的加密算法與解密算法相同，只是解密使用子密鑰與加密子密鑰的使算法與解密算法相同，

11、只是解密使用子密鑰與加密子密鑰的使用順序剛好相反。用順序剛好相反。DESDES在對(duì)明文進(jìn)行初始置換在對(duì)明文進(jìn)行初始置換IPIP之后，執(zhí)行之后，執(zhí)行1616論的迭代密碼。最后經(jīng)論的迭代密碼。最后經(jīng)IPIP的逆變換得到密文。所謂迭代密碼是的逆變換得到密文。所謂迭代密碼是在密鑰控制下多次利用輪函數(shù)進(jìn)行加密變換，以實(shí)現(xiàn)擴(kuò)散和混在密鑰控制下多次利用輪函數(shù)進(jìn)行加密變換，以實(shí)現(xiàn)擴(kuò)散和混淆的效果淆的效果 . . 這里明文塊為這里明文塊為其中其中是是的左的左3232位，位，是是的右的右3232位。給定一個(gè)密鑰位。給定一個(gè)密鑰k，由它生成，由它生成1616個(gè)子密個(gè)子密鑰鑰。通過(guò)下面加密過(guò)程得到密文。通過(guò)下面加密過(guò)

12、程得到密文For i = 1 to 16For i = 1 to 16該結(jié)構(gòu)稱(chēng)為該結(jié)構(gòu)稱(chēng)為FeistelFeistel密碼，它最早由密碼，它最早由Smith 1971Smith 1971年在年在 LuciferLucifer中引入。中引入。000RLM0R0M0L0M1621,kkk1iiLR),(11iiiikRfLR IP IP-158 50 42 34 26 18 10 240 8 48 16 56 24 64 3260 52 44 36 28 20 12 4 39 7 47 15 55 23 63 3162 54 46 38 30 22 14 638 6 46 14 54 22 62

13、3064 56 48 40 32 24 16 8 37 5 45 13 53 21 61 2957 49 41 33 25 17 9 136 4 44 12 52 20 60 2859 51 43 35 27 19 11 3 35 3 43 11 51 19 59 27 61 53 45 37 29 21 13 534 2 42 10 50 18 58 2663 55 47 39 31 23 15 733 1 41 9 49 17 57 25初始置換初始置換IPIP及它的逆置換及它的逆置換 1IP6421mmmm7152334425058)(mmmmmmmmIP1iiRL),(11iiiikR

14、fLR),(),(11iiKiiRLRLi32211rrrRi1323130321321)(rrrrrrrrREi25411222120716)(hhhhhhhhHP3221hhhHFeistelFeistel Cipher 1974 Cipher 1974其中選位表其中選位表E E ： 置換置換P P ： E P E P32 1 2 3 4 5 16 7 20 2132 1 2 3 4 5 16 7 20 21 4 5 6 7 8 9 29 12 28 17 4 5 6 7 8 9 29 12 28 17 8 9 10 11 12 13 1 15 23 26 8 9 10 11 12 13

15、1 15 23 2612 13 14 15 16 17 5 18 31 1012 13 14 15 16 17 5 18 31 1016 17 18 19 20 21 2 8 24 1416 17 18 19 20 21 2 8 24 1420 21 22 23 24 25 32 27 3 920 21 22 23 24 25 32 27 3 924 25 26 27 28 29 19 13 30 624 25 26 27 28 29 19 13 30 628 29 30 31 32 1 22 11 4 2528 29 30 31 32 1 22 11 4 25E E從從3232位變成位變成4

16、848位，其中擴(kuò)展了位，其中擴(kuò)展了1,4,5,8,9,12,13, 1,4,5,8,9,12,13, 16,17,20,21,24,25,28,29,3216,17,20,21,24,25,28,29,32共共1616位。位。S S盒的輸入為：盒的輸入為： ， 是是0 0 3 3的數(shù)。的數(shù)。 是是0 0 1515的數(shù)。的數(shù)。 S -S -盒是盒是DESDES算法的核心。算法的核心。S-S-盒的設(shè)計(jì)原則沒(méi)有完全盒的設(shè)計(jì)原則沒(méi)有完全公開(kāi)，美國(guó)國(guó)家安全局公開(kāi)，美國(guó)國(guó)家安全局NSANSA曾在曾在19761976年披露了一些設(shè)計(jì)原年披露了一些設(shè)計(jì)原則。例如：則。例如： 1 1 所有所有S-盒的每一行是盒

17、的每一行是0,1,15的一個(gè)置換；的一個(gè)置換； 2 2 所有所有S-S-盒的輸出都不是輸入的線(xiàn)性函數(shù)或仿射函數(shù)；盒的輸出都不是輸入的線(xiàn)性函數(shù)或仿射函數(shù)； 654321bbbbbb61bb5432bbbb3 3S-S-盒的輸入改變?nèi)我庖晃欢紩?huì)引起輸出中至少兩位發(fā)生盒的輸入改變?nèi)我庖晃欢紩?huì)引起輸出中至少兩位發(fā)生 變化；變化；4 4 對(duì)于任何輸入對(duì)于任何輸入x x（6 6位），位），S(x)S(x)與與S(xS(x001100)001100)至少有兩至少有兩 位不同；位不同；5 5 對(duì)于任何輸入對(duì)于任何輸入x x（6 6位），位），S(x)S(x)與與S(x11ef00)S(x11ef00)不相等，

18、不相等，e, fe, f取取0 0或或1 1；6 6對(duì)于任意一個(gè)輸入位保持不變而其它五位變化時(shí)，它們對(duì)于任意一個(gè)輸入位保持不變而其它五位變化時(shí)，它們 相應(yīng)的輸出中相應(yīng)的輸出中0和和1的數(shù)目幾乎相等。的數(shù)目幾乎相等。 例如：例如：S3 (101101)=1000S3 (101101)=1000。當(dāng)輸入第。當(dāng)輸入第3 3位或第位或第1 1位變化時(shí)，位變化時(shí)，S3 (100101)=0100S3 (100101)=0100和和 S3 (001101)=0011S3 (001101)=0011，則輸出變化，則輸出變化位數(shù)分別為位數(shù)分別為2 2和和3 3。當(dāng)輸入除了第。當(dāng)輸入除了第1 1位不變外全都改變

19、，位不變外全都改變，S3 S3 (110010)=0001(110010)=0001，則輸出，則輸出0 0和和1 1的個(gè)數(shù)沒(méi)變。的個(gè)數(shù)沒(méi)變。6421kkkk364449570kkkkC41355630kkkkD5621bbbDCii3229365024111714bbbbbbbbki PC PC1 PC1 PC2 2 57 49 41 33 25 17 9 14 17 11 24 1 5 57 49 41 33 25 17 9 14 17 11 24 1 5 1 58 50 42 34 26 18 3 28 15 6 21 10 1 58 50 42 34 26 18 3 28 15 6 21

20、 10 10 2 59 51 43 35 27 23 19 12 4 26 8 10 2 59 51 43 35 27 23 19 12 4 26 8 19 11 3 60 52 44 36 16 7 27 20 13 2 19 11 3 60 52 44 36 16 7 27 20 13 2 63 55 47 39 31 23 15 41 52 31 37 47 55 63 55 47 39 31 23 15 41 52 31 37 47 55 7 62 54 46 38 30 22 30 40 51 45 33 48 7 62 54 46 38 30 22 30 40 51 45 33 4

21、8 14 6 61 53 45 37 29 44 49 39 56 34 53 14 6 61 53 45 37 29 44 49 39 56 34 53 21 13 5 28 20 12 4 46 42 50 36 29 32 21 13 5 28 20 12 4 46 42 50 36 29 32 PC-1 PC-1不涉及奇偶校驗(yàn)位，不涉及奇偶校驗(yàn)位，PC-2PC-2將將5656位變成位變成4848位，位，前前2828位中的位中的2424為置換，并去掉為置換，并去掉9 9，1818，2222，2525位位后后2828位中的位中的2424為置換，并去掉為置換，并去掉3535，3838，434

22、3，5454位位.循環(huán)左移（循環(huán)左移（LSLS）運(yùn)算）運(yùn)算: i i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 161 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 iLS2.1.3 DES2.1.3 DES算法實(shí)現(xiàn)及安全性算法實(shí)現(xiàn)及安全性DEC公司生產(chǎn)的最快的公司生產(chǎn)的最快的DES芯片，加密芯片，加密/解密速度達(dá)解密速度達(dá)1Gbit/秒，相當(dāng)秒，相當(dāng)1560萬(wàn)組萬(wàn)組/秒。最快的秒。最快的DES軟件加密軟件加密

23、/解密速解密速度度500Kbit/秒。秒。資料表明用差分分析和線(xiàn)性分析破譯資料表明用差分分析和線(xiàn)性分析破譯16論論DES分別需要分別需要個(gè)選擇明文和個(gè)選擇明文和個(gè)已知明文。個(gè)已知明文。472432網(wǎng)絡(luò)用戶(hù)聯(lián)網(wǎng)可以破譯網(wǎng)絡(luò)用戶(hù)聯(lián)網(wǎng)可以破譯DES。1997年年1月月28日日RSA公司懸賞公司懸賞1萬(wàn)美元破譯萬(wàn)美元破譯56位密鑰的位密鑰的DES。當(dāng)年。當(dāng)年3月在因特網(wǎng)上數(shù)萬(wàn)名志愿者協(xié)同工作，用了月在因特網(wǎng)上數(shù)萬(wàn)名志愿者協(xié)同工作，用了96天成功找到天成功找到DES密鑰。密鑰。1998年年7月月EFF使用一臺(tái)使用一臺(tái)25萬(wàn)美萬(wàn)美元的計(jì)算機(jī)在元的計(jì)算機(jī)在56小時(shí)內(nèi)破譯了小時(shí)內(nèi)破譯了56位密鑰的位密鑰的DE

24、S。1999年年1月又把破譯時(shí)間縮短到月又把破譯時(shí)間縮短到22小時(shí)小時(shí)15分。這說(shuō)明依靠分布式分。這說(shuō)明依靠分布式計(jì)算能力，破譯計(jì)算能力，破譯56位密鑰的位密鑰的DES已成為可能。隨著計(jì)算已成為可能。隨著計(jì)算能力的增長(zhǎng)，必須相應(yīng)增加算法的密鑰長(zhǎng)度能力的增長(zhǎng)，必須相應(yīng)增加算法的密鑰長(zhǎng)度。2.1.4 DES2.1.4 DES算法的性質(zhì)算法的性質(zhì)l l若若、是是的補(bǔ)、的補(bǔ)、是是的補(bǔ)，則的補(bǔ)，則。所以不要使用互補(bǔ)的密鑰，因?yàn)檫x擇明文攻擊下僅需試所以不要使用互補(bǔ)的密鑰，因?yàn)檫x擇明文攻擊下僅需試驗(yàn)一半驗(yàn)一半密鑰即可密鑰即可.l l DES至少有至少有4個(gè)弱密鑰個(gè)弱密鑰,即即 。這些弱密鑰。這些弱密鑰 是是: : 0101010101010101,1F1F1F1F0E0E0E0E，E0E0E0E0F1F1F1F1,FEFEFEFEFEFEFEFE)(mDESckccmm)(mDESck552mmDESDESkk)(因?yàn)樵诋a(chǎn)生密鑰時(shí)初始密鑰分成兩半，以后各因?yàn)樵诋a(chǎn)生密鑰時(shí)初始密鑰分成兩半，以后各自獨(dú)立地移位。如果每一半都是自獨(dú)立地移位。如果每一半都是0 0或都是或都是1 1，則所有，則所有密鑰