1、第第3章章 分組密碼實(shí)際分組密碼實(shí)際3.1 分組密碼概述分組密碼概述3.2 DES3.3 分組密碼的設(shè)計(jì)原理分組密碼的設(shè)計(jì)原理3.4 分組密碼的任務(wù)方式分組密碼的任務(wù)方式3.1 分組密碼概述分組密碼概述 分組密碼，就是一個(gè)明文分組被當(dāng)作一分組密碼，就是一個(gè)明文分組被當(dāng)作一個(gè)整體來(lái)產(chǎn)生一個(gè)等長(zhǎng)通常的密文個(gè)整體來(lái)產(chǎn)生一個(gè)等長(zhǎng)通常的密文分組的密碼，通常運(yùn)用的是分組的密碼，通常運(yùn)用的是128位分組大位分組大小。小。 分組密碼的本質(zhì)是，設(shè)計(jì)一種算法，能分組密碼的本質(zhì)是，設(shè)計(jì)一種算法，能在密鑰控制下，把在密鑰控制下，把n比特明文簡(jiǎn)單而又迅比特明文簡(jiǎn)單而又迅速地置換成獨(dú)一速地置換成獨(dú)一n比特密文，并且這種變

2、比特密文，并且這種變換是可逆的解密。換是可逆的解密。3.1 分組密碼概述分組密碼概述(Cont.)分組密碼的設(shè)計(jì)思想分組密碼的設(shè)計(jì)思想C.E. Shannon)：分散分散(diffusion)將明文及密鑰的影響盡能夠迅速地分布到將明文及密鑰的影響盡能夠迅速地分布到較多個(gè)輸出的密文中將明文冗余度分散較多個(gè)輸出的密文中將明文冗余度分散到密文中。產(chǎn)生分散的最簡(jiǎn)一方法是通到密文中。產(chǎn)生分散的最簡(jiǎn)一方法是通過過“置換置換(Permutation)比如：重新排比如：重新排列字符。列字符。分組密碼的設(shè)計(jì)思想分組密碼的設(shè)計(jì)思想(Cont.) 混淆混淆(confusion) 其目的在于使作用于明文的密鑰和密文其

3、目的在于使作用于明文的密鑰和密文之之 間的關(guān)系復(fù)雜化，是明文和密文之間、間的關(guān)系復(fù)雜化，是明文和密文之間、密密 文和密鑰之間的統(tǒng)計(jì)相關(guān)特性極小化，文和密鑰之間的統(tǒng)計(jì)相關(guān)特性極小化，從從 而使統(tǒng)計(jì)分析攻擊不能奏效。通常的方而使統(tǒng)計(jì)分析攻擊不能奏效。通常的方法法 是是“代換代換Substitution)回想愷撒密回想愷撒密 碼。碼。3.1 分組密碼概述分組密碼概述(Cont.)分組密碼設(shè)計(jì)的要求：分組密碼設(shè)計(jì)的要求：分組長(zhǎng)度足夠大分組長(zhǎng)度足夠大64128比特比特密鑰量要足夠大密鑰量要足夠大64128算法足夠復(fù)雜包括子密鑰產(chǎn)生算法算法足夠復(fù)雜包括子密鑰產(chǎn)生算法加密、解密算法簡(jiǎn)單，易軟、硬件實(shí)現(xiàn)加密、

4、解密算法簡(jiǎn)單，易軟、硬件實(shí)現(xiàn)便于分析破譯是困難的，但算法卻簡(jiǎn)約便于分析破譯是困難的，但算法卻簡(jiǎn)約明晰明晰3.23.2數(shù)據(jù)加密規(guī)范數(shù)據(jù)加密規(guī)范DES)DES) DES的歷史的歷史 1971 IBM，由，由Horst Feistel 指點(diǎn)的密碼指點(diǎn)的密碼研研 究工程組研討出究工程組研討出LUCIFER算法。并運(yùn)用算法。并運(yùn)用于于 商業(yè)領(lǐng)域。商業(yè)領(lǐng)域。 1973美國(guó)規(guī)范局征求規(guī)范，美國(guó)規(guī)范局征求規(guī)范，IBM提交結(jié)提交結(jié)果，果， 在在1977年，被選為數(shù)據(jù)加密規(guī)范。年，被選為數(shù)據(jù)加密規(guī)范。3.23.2數(shù)據(jù)加密規(guī)范數(shù)據(jù)加密規(guī)范Cont.)Cont.)4.2.1 4.2.1 簡(jiǎn)化的簡(jiǎn)化的DESDES Si

5、mplified DES Simplified DES方案，簡(jiǎn)稱方案，簡(jiǎn)稱S-DESS-DES方案。它方案。它是一個(gè)供教學(xué)而非平安的加密算法，它與是一個(gè)供教學(xué)而非平安的加密算法，它與DESDES的特性和構(gòu)造類似，但參數(shù)小。的特性和構(gòu)造類似，但參數(shù)小。注：注：1.1.* * 加密算法涉及五個(gè)函數(shù)：加密算法涉及五個(gè)函數(shù)：(1)(1)初始置換初始置換IP(initial permutation)IP(initial permutation)(2)(2)復(fù)合函數(shù)復(fù)合函數(shù)fk1fk1，它是由密鑰，它是由密鑰K K確定的，具確定的，具有置換和代換的運(yùn)算。有置換和代換的運(yùn)算。 (3)(3)置換函數(shù)置換函數(shù)S

6、WSW(4)(4)復(fù)合函數(shù)復(fù)合函數(shù)fk2fk2(5)(5)初始置換初始置換IPIP的逆置換的逆置換IP-1IP-1 加密10bit密鑰 解密8bit明文P108bit明文IP移位IP-1P8fkfkSWSW移位P8fkfkIPIP-18bit密文8bit密文K2K2K1K1S-DES方案表示圖方案表示圖 2*. 加密算法的數(shù)學(xué)表示：加密算法的數(shù)學(xué)表示：IP-1*fk2*SW*fk1*IP也可寫為也可寫為密文密文=IP-1fk2(SW(fk1(IP(明文明文)其中其中 K1=P8(移位移位(P10(密鑰密鑰K)K2=P8(移位移位(移位移位(P10(密鑰密鑰K)解密算法的數(shù)學(xué)表示：解密算法的數(shù)學(xué)

7、表示：明文明文=IP-1fk1(SW(fk2(IP(密文密文)對(duì)對(duì)S-DES的深化描畫的深化描畫1 S-DES的密鑰生成：的密鑰生成：設(shè)設(shè)10bit的密鑰為的密鑰為 k1,k2,k10 )置換置換P10是這樣定義的是這樣定義的P10(k1,k2,k10)=(k3,k5,k2,k7,k4,k10,k1,k9,k8,k6) P8= (k1,k2,k10)=(k6,k3,k7,k4,k8,k5,k10,k9 ) LS-1為循環(huán)左移為循環(huán)左移1位，位， LS-2為循環(huán)左移為循環(huán)左移2位位按照上述條件按照上述條件,假設(shè)假設(shè)K選為選為(1010000010), 產(chǎn)產(chǎn)生的兩個(gè)子密鑰分別為生的兩個(gè)子密鑰分別為

8、K1=(1 0 1 0 0 1 0 0),K2=(0 1 0 0 0 0 1 1)S-DES的密鑰生成的密鑰生成10-bit密鑰P10LS-1LS-1LS-2LS-2K18K255558(2) S-DES的加密運(yùn)算的加密運(yùn)算: 初始置換用初始置換用IP函數(shù)函數(shù): IP= 1 2 3 4 5 6 7 8 2 6 3 1 4 8 5 7 末端算法的置換為末端算法的置換為IP的逆置換的逆置換:IP-1= 1 2 3 4 5 6 7 8 4 1 3 5 7 2 8 6 易見易見IP-1(IP(X)=X S-DES加密圖加密圖8-bit 明文IP+P4+LR4K1844fkF4S-DES加密圖加密圖(續(xù)

9、續(xù))+8K2P4+IP-18-bit 密文密文4844fkF44228SW函數(shù)函數(shù)fk，是加密方案中的最重要部分，它可表示為：，是加密方案中的最重要部分，它可表示為：f k ( L , R ) = ( LF ( R , S K ) , R )其中其中L，R為為8位輸入位輸入, 左右各為左右各為4位位, F為從為從4位集到位集到4位集位集的一個(gè)映射的一個(gè)映射, 并不要求是并不要求是1-1的。的。SK為子密鑰。為子密鑰。對(duì)映射對(duì)映射F來(lái)說：來(lái)說：首先輸入是一個(gè)首先輸入是一個(gè)4-位數(shù)位數(shù)n1,n2,n3,n4，第一步運(yùn)算是，第一步運(yùn)算是擴(kuò)張擴(kuò)張/置換置換E/P運(yùn)算：運(yùn)算： E/P 4 1 2 3 2

10、 3 4 1 現(xiàn)實(shí)上，它的直觀表現(xiàn)方式為：現(xiàn)實(shí)上，它的直觀表現(xiàn)方式為：n4 n1 n2 n3n2 n3 n4 n18-bit子密鑰：子密鑰：K1=(k11,k12,k13,k14,k15,k16,k17,k18),然后與然后與E/P的結(jié)果作異或運(yùn)算得：的結(jié)果作異或運(yùn)算得：n4+k11 n1+k12 n2+k13n3+k14n2+k15 n3+k16n4+k17n1+k18把它們重記為把它們重記為8位：位： P0,0 P0,1 P0,2 P0,3 P1,0 P1,1 P1,2 P1,3上述第一行輸入進(jìn)上述第一行輸入進(jìn)S-盒盒S0，產(chǎn)生，產(chǎn)生2-位的位的輸出；第二行的輸出；第二行的4位輸入進(jìn)位輸入

11、進(jìn)S盒盒S1，產(chǎn)，產(chǎn)生生2-位的輸出。位的輸出。兩個(gè)兩個(gè)S盒按如下定義：盒按如下定義：2313312001232301321032100S3012010331023210321032101SS盒按下述規(guī)那么運(yùn)算：盒按下述規(guī)那么運(yùn)算：將第將第1和第和第4的輸入比特做為的輸入比特做為2- bit數(shù)，指示為數(shù)，指示為S盒的盒的一個(gè)行；將第一個(gè)行；將第2和第和第3的輸入比特做為的輸入比特做為S盒的一個(gè)列。盒的一個(gè)列。如此確定為如此確定為S盒矩陣的盒矩陣的i,j數(shù)。數(shù)。例如：例如：P0,0, P0,3=(00),并且并且(P0,1,P0,2)=(1 0)確定了確定了S0中的第中的第0行行2列列0，2的系

12、數(shù)為的系數(shù)為3，記為，記為1 1輸出。輸出。由由S0, S1輸出輸出4-bit經(jīng)置換經(jīng)置換 P4 2 4 3 1它的輸出就是它的輸出就是F函數(shù)的輸出。函數(shù)的輸出。作業(yè) 試證明S-DES的加密、解密是互逆的，即：D( E(M,K), K)M。Feistel 密碼結(jié)構(gòu)Feistel 密碼設(shè)計(jì)原那么 分組大小分組大小 increasing size improves security, but slows cipher 密鑰長(zhǎng)度密鑰長(zhǎng)度 increasing size improves security, makes exhaustive key searching harder, but may

13、slow cipher 輪次數(shù)輪次數(shù) increasing number improves security, but slows cipher 子密鑰生成子密鑰生成 greater complexity can make analysis harder, but slows cipher 輪函數(shù)輪函數(shù) greater complexity can make analysis harder, but slows cipher 快速軟件加密快速軟件加密/解密解密 are more recent concerns for practical use and testingFeistel 密碼解密3

14、.2 DES的描畫的描畫 DES利用利用56比特串長(zhǎng)度的密鑰比特串長(zhǎng)度的密鑰K來(lái)加密長(zhǎng)度為來(lái)加密長(zhǎng)度為64位的明文，位的明文，得到長(zhǎng)度為得到長(zhǎng)度為64位的密文位的密文 該算法分三個(gè)階段實(shí)現(xiàn)：該算法分三個(gè)階段實(shí)現(xiàn)：1. 給定明文給定明文X，經(jīng)過一個(gè)固定的初始置換，經(jīng)過一個(gè)固定的初始置換IP來(lái)陳列來(lái)陳列X中的中的位，得到位，得到X0。X0=IPX=L0R0其中其中L0由由X0前前32位組成，位組成，R0由由X0的后的后32位組成。位組成。2.計(jì)算函數(shù)計(jì)算函數(shù)F的的16次迭代次迭代, 根據(jù)下述規(guī)那么來(lái)計(jì)算根據(jù)下述規(guī)那么來(lái)計(jì)算LiRi(1=i=16 Li=Ri-1, Ri=Li-1 F(Ri-1, K

15、i)其中其中Ki是長(zhǎng)為是長(zhǎng)為48位的子密鑰。子密鑰位的子密鑰。子密鑰K1，K2，K16是是作為密鑰作為密鑰K56位的函數(shù)而計(jì)算出的。位的函數(shù)而計(jì)算出的。 3.對(duì)比特串對(duì)比特串R16L16運(yùn)用逆置換運(yùn)用逆置換IP-1得到密文得到密文Y。Y=IP-1R16L16DES 算法的普通描畫一輪加密的簡(jiǎn)圖一輪加密的簡(jiǎn)圖 Li-1 Ri-1F+Li RiKi 對(duì)對(duì)F F函數(shù)的闡明：類比于函數(shù)的闡明：類比于S-DESS-DESF FRi-1, KiRi-1, Ki函數(shù)函數(shù)F F以長(zhǎng)度為以長(zhǎng)度為3232的比特串的比特串A=RA=R32bits32bits作第一個(gè)輸入，作第一個(gè)輸入，以長(zhǎng)度為以長(zhǎng)度為4848的比特

16、串變?cè)谋忍卮冊(cè)狫=K(48bits)J=K(48bits)作為第二個(gè)輸入。作為第二個(gè)輸入。產(chǎn)生的輸出為長(zhǎng)度為產(chǎn)生的輸出為長(zhǎng)度為3232的位串。的位串。(1)(1)對(duì)第一個(gè)變?cè)獙?duì)第一個(gè)變?cè)狝 A，由給定的擴(kuò)展函數(shù)，由給定的擴(kuò)展函數(shù)E E，將其擴(kuò)展成，將其擴(kuò)展成4848位串，位串，E EA A(2)(2)計(jì)算計(jì)算E EA A+J+J，并把結(jié)果寫成延續(xù)的，并把結(jié)果寫成延續(xù)的8 8個(gè)個(gè)6 6位串位串, , B=b1b2b3b4b5b6b7b8 B=b1b2b3b4b5b6b7b8(3)(3)運(yùn)用運(yùn)用8 8個(gè)個(gè)S S盒，每個(gè)盒，每個(gè)SjSj是一個(gè)固定的是一個(gè)固定的4 41616矩陣，它的元矩陣，它的

17、元素取素取015015的整數(shù)。給定長(zhǎng)度為的整數(shù)。給定長(zhǎng)度為6 6個(gè)比特串，如個(gè)比特串，如Bj=b1b2b3b4b5b6Bj=b1b2b3b4b5b6計(jì)算計(jì)算Sj(Bj)Sj(Bj)如下：如下：b1b6b1b6兩個(gè)比特確定了兩個(gè)比特確定了SjSj的行數(shù)的行數(shù), , r(0=r=3); r(0=r=3); 而而b2b3b4b5b2b3b4b5四個(gè)比特確定了四個(gè)比特確定了SjSj的列數(shù)的列數(shù)c c0=c=150=c=15。最后。最后Sj(Bj)Sj(Bj)的值為的值為S-S-盒矩陣盒矩陣SjSj中中r r行行c c列的列的元素元素r,cr,c, , 得得Cj=Sj(Bj)Cj=Sj(Bj)。(4)

18、(4) 最后，最后，P P為固定置換。為固定置換。 A=R(32 bits)J=K(48 bits)EE(A)為48 bits+B1 B2 B3 B4 B5 B6 B7 B8 S1S2S3S4S5S6S7S8C1 C2 C3 C4 C5 C6 C7 C8P32 bits F(A,J)B寫成8個(gè)6比特串DES 的的F函數(shù)函數(shù) DES中運(yùn)用的其它特定函數(shù)：中運(yùn)用的其它特定函數(shù)：初始置換初始置換IP：從表：從表3.2中看出中看出X的第的第58個(gè)比特是個(gè)比特是IPX的第一個(gè)比特；的第一個(gè)比特；X的第的第50個(gè)比特是個(gè)比特是IPX的第二個(gè)比的第二個(gè)比特特逆置換逆置換IP-1；擴(kuò)展函數(shù)；擴(kuò)展函數(shù)E；置換函

19、數(shù)；置換函數(shù)P。 從密鑰從密鑰K計(jì)算子密鑰：計(jì)算子密鑰： 實(shí)踐上，實(shí)踐上，K是長(zhǎng)度為是長(zhǎng)度為64的位串，其中的位串，其中56位是密鑰，位是密鑰，8位是奇偶校驗(yàn)位為了檢錯(cuò)，在密鑰編排的計(jì)算中，位是奇偶校驗(yàn)位為了檢錯(cuò)，在密鑰編排的計(jì)算中，這些校驗(yàn)位可略去。這些校驗(yàn)位可略去。(1). 給定給定64位的密鑰位的密鑰K，放棄奇偶校驗(yàn)位，放棄奇偶校驗(yàn)位8，16，64并根據(jù)固定置換并根據(jù)固定置換PC-1見見144頁(yè)圖頁(yè)圖4-4-9來(lái)陳列來(lái)陳列K中剩下的位。我們寫中剩下的位。我們寫 PC-1(K)=C0D0其中其中C0由由PC-1K的前的前28位組成；位組成；D0由后由后28位組成。位組成。 (2)對(duì)對(duì)1=i

20、=16，計(jì)算，計(jì)算Ci=LSi(Ci-1)Di=LSi(Di-1)LSi表示循環(huán)左移表示循環(huán)左移2或或1個(gè)位置，取決于個(gè)位置，取決于i的的值。的的值。i=1,2,9和和16 時(shí)移時(shí)移1個(gè)位置，否那么移個(gè)位置，否那么移2位置。位置。Ki=PC-2(CiDi), PC-2為固定置。為固定置。 注：一共注：一共16輪，每一輪運(yùn)用輪，每一輪運(yùn)用K中中48位組成一個(gè)位組成一個(gè)48比特比特密鑰?？伤愠雒荑€?？伤愠?6個(gè)表，第個(gè)表，第i個(gè)表中的元素可對(duì)應(yīng)上第個(gè)表中的元素可對(duì)應(yīng)上第i輪輪密鑰運(yùn)用密鑰運(yùn)用K中第幾比特！如：中第幾比特！如：第第7輪的表輪的表7：K7取取K中的比特情況：中的比特情況：52 57 1

21、1 1 26 59 10 34 44 51 25 199 41 3 2 50 35 36 43 42 33 60 1828 7 14 29 47 46 22 5 15 63 61 394 31 13 38 53 62 55 20 23 37 30 6圖表密鑰生成圖表密鑰生成KiKPC-1C0 D0LS1LS1C1 D1LS2LS2LS16LS16C16 D16PC-2PC-2K1K16 DES加密的一個(gè)例子加密的一個(gè)例子取取16進(jìn)制明文進(jìn)制明文X：0123456789ABCDEF密鑰密鑰K為：為：133457799BBCDFF1去掉奇偶校驗(yàn)位以二進(jìn)制方式表示的密鑰是去掉奇偶校驗(yàn)位以二進(jìn)制方式表

22、示的密鑰是00010010011010010101101111001001101101111011011111111000運(yùn)用運(yùn)用IP，我們得到：，我們得到：L0=11001100000000001100110011111111L1=R0=11110000101010101111000010101010然后進(jìn)展然后進(jìn)展16輪加密。輪加密。最后對(duì)最后對(duì)L16, R16運(yùn)用運(yùn)用IP-1得到密文：得到密文：85E840F0AB4053.2.3 DES的爭(zhēng)論的爭(zhēng)論 DES的中心是的中心是S盒，除此之外的計(jì)算是屬盒，除此之外的計(jì)算是屬線性的。線性的。S盒作為該密碼體制的非線性組盒作為該密碼體制的非線性組

23、件對(duì)平安性至關(guān)重要。件對(duì)平安性至關(guān)重要。 S盒的設(shè)計(jì)準(zhǔn)那么：盒的設(shè)計(jì)準(zhǔn)那么：1. S盒不是它輸入變量的線性函數(shù)盒不是它輸入變量的線性函數(shù)2.改動(dòng)改動(dòng)S盒的一個(gè)輸入位至少要引起兩位盒的一個(gè)輸入位至少要引起兩位的輸出改動(dòng)的輸出改動(dòng)3. 對(duì)任何一個(gè)對(duì)任何一個(gè)S盒，假設(shè)固定一個(gè)輸入比盒，假設(shè)固定一個(gè)輸入比特，其它輸入變化時(shí)，輸出數(shù)字中特，其它輸入變化時(shí)，輸出數(shù)字中0和和1的總數(shù)近于相等。的總數(shù)近于相等。 公眾依然不知道公眾依然不知道S盒的構(gòu)造中能否還運(yùn)用盒的構(gòu)造中能否還運(yùn)用了進(jìn)一步的設(shè)計(jì)準(zhǔn)那么有陷門？。了進(jìn)一步的設(shè)計(jì)準(zhǔn)那么有陷門？。 密鑰長(zhǎng)度能否足夠？密鑰長(zhǎng)度能否足夠？ 迭代的長(zhǎng)度？迭代的長(zhǎng)度？8、1

24、6、32？3.3 分組密碼的設(shè)計(jì)原理分組密碼的設(shè)計(jì)原理 可變密鑰長(zhǎng)度可變密鑰長(zhǎng)度 混合操作混合操作 依賴數(shù)據(jù)的循環(huán)移位依賴數(shù)據(jù)的循環(huán)移位 依賴于密鑰的循環(huán)移位依賴于密鑰的循環(huán)移位 依賴密鑰的依賴密鑰的S盒子盒子 冗長(zhǎng)的密鑰調(diào)度算法冗長(zhǎng)的密鑰調(diào)度算法 可變的可變的F函數(shù)和可變的明文函數(shù)和可變的明文/密文長(zhǎng)度密文長(zhǎng)度 可變的循環(huán)次數(shù)可變的循環(huán)次數(shù) 在每次循環(huán)中都對(duì)兩半數(shù)據(jù)進(jìn)展操作在每次循環(huán)中都對(duì)兩半數(shù)據(jù)進(jìn)展操作分組密碼的任務(wù)方式 分組密碼加密固定長(zhǎng)度的數(shù)據(jù)分組 需求運(yùn)用一些實(shí)踐的方法來(lái)加密恣意數(shù)量的明文 五種任務(wù)方式Electronic Codebook Book (ECB)電碼本方式電碼本方式E

25、CB的優(yōu)勢(shì)與局限 一樣的明文對(duì)于一樣的密文 構(gòu)造化明文 音訊有反復(fù)部分 主要用于發(fā)送少數(shù)量的分組數(shù)據(jù) Cipher Block Chaining (CBC)密碼分組鏈接方式密碼分組鏈接方式Advantages and Limitations of CBC each ciphertext block depends on all message blocks thus a change in the message affects all ciphertext blocks after the change as well as the original block need Initial V

26、alue (IV) known to sender & receiver however if IV is sent in the clear, an attacker can change bits of the first block, and change IV to compensate hence either IV must be a fixed value (as in EFTPOS) or it must be sent encrypted in ECB mode before rest of message at end of message, handle possible last short block by padding either with known non-data value (eg nulls) or pad last block with count of pad size eg. b1 b2 b3 0 0 0 0 5 - 3 data bytes, then 5 bytes pad+count Cipher FeedBack (CFB)密碼反響方式密碼反響方式Advantages and Limitations of CFB appropriate when data arrives in bits/by