第二章分組密碼PPT課件

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

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

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

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

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

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

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

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

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

10、Encryption Standard。到。到19991999年年3 3月選出月選出1515個，個，5 5月再從月再從中選出中選出5 5個，預(yù)計（？）在個，預(yù)計（？）在20012001年出臺年出臺AESAES。）。）2.1.2 DES2.1.2 DES算法描述算法描述 DES DES算法中密鑰長度算法中密鑰長度5656位位(bit)(bit),明文和密文長度明文和密文長度6464位位(bit).(bit). DES DES是一個使用是一個使用5656位有效密鑰的位有效密鑰的6464位分組密碼。它的加密位分組密碼。它的加密算法與解密算法相同，只是解密使用子密鑰與加密子密鑰的使算法與解密算法相同，

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

12、程得到密文For i = 1 to 16For i = 1 to 16該結(jié)構(gòu)稱為該結(jié)構(gòu)稱為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位，其中擴展了位，其中擴展了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è)計原則沒有完全盒的設(shè)計原則沒有完全公開，美國國家安全局公開，美國國家安全局NSANSA曾在曾在19761976年披露了一些設(shè)計原年披露了一些設(shè)計原則。例如：則。例如： 1 1 所有所有S-盒的每一行是盒

17、的每一行是0,1,15的一個置換；的一個置換； 2 2 所有所有S-S-盒的輸出都不是輸入的線性函數(shù)或仿射函數(shù)；盒的輸出都不是輸入的線性函數(shù)或仿射函數(shù)； 654321bbbbbb61bb5432bbbb3 3S-S-盒的輸入改變?nèi)我庖晃欢紩疠敵鲋兄辽賰晌话l(fā)生盒的輸入改變?nèi)我庖晃欢紩疠敵鲋兄辽賰晌话l(fā)生 變化；變化；4 4 對于任何輸入對于任何輸入x x（6 6位），位），S(x)S(x)與與S(xS(x001100)001100)至少有兩至少有兩 位不同；位不同；5 5 對于任何輸入對于任何輸入x x（6 6位），位），S(x)S(x)與與S(x11ef00)S(x11ef00)不相等，

18、不相等，e, fe, f取取0 0或或1 1；6 6對于任意一個輸入位保持不變而其它五位變化時，它們對于任意一個輸入位保持不變而其它五位變化時，它們 相應(yīng)的輸出中相應(yīng)的輸出中0和和1的數(shù)目幾乎相等。的數(shù)目幾乎相等。 例如：例如：S3 (101101)=1000S3 (101101)=1000。當(dāng)輸入第。當(dāng)輸入第3 3位或第位或第1 1位變化時，位變化時，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的個數(shù)沒變。的個數(shù)沒變。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不涉及奇偶校驗位，不涉及奇偶校驗位，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）運算）運算: 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算法實現(xiàn)及安全性算法實現(xiàn)及安全性DEC公司生產(chǎn)的最快的公司生產(chǎn)的最快的DES芯片，加密芯片，加密/解密速度達解密速度達1Gbit/秒，相當(dāng)秒，相當(dāng)1560萬組萬組/秒。最快的秒。最快的DES軟件加密軟件加密

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

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