第三章分組密碼課件

1、第三章第三章 分組密碼分組密碼分組密碼分組密碼(Block Cipher)，一類對稱密碼算法：，一類對稱密碼算法：將明文消息分組，逐組加密；將明文消息分組，逐組加密；將明文消息編碼表示后的數(shù)字序列將明文消息編碼表示后的數(shù)字序列x0,x1,xi,劃分成長為劃分成長為n的組的組x=(x0,x1,xn-1) （長為（長為n的矢量）的矢量）各組分別在密鑰各組分別在密鑰k=(k0,k1,kt-1) K 控制下變換成輸出序列控制下變換成輸出序列y=(y0,y1,ym-1) Vm (長為長為m的矢量）的矢量）其加密函數(shù)其加密函數(shù)E：VnKVm，K為密鑰空間為密鑰空間分組密碼實質(zhì)上是字長為分組密碼實質(zhì)上是字長

2、為m的數(shù)字序列的代換密碼的數(shù)字序列的代換密碼1/nV算法的輸入長度和輸出長度算法的輸入長度和輸出長度1.通常取通常取m=n (用于加密用于加密)2.若若mn，則為有數(shù)據(jù)擴展，則為有數(shù)據(jù)擴展(mn)/壓縮壓縮(mN/2，則令，則令Kk1,k2,kc如果如果TN/2，則令，則令 Kk1,k2,kc從而可得關(guān)于密鑰比特的一個線性方程。從而可得關(guān)于密鑰比特的一個線性方程。對不同的明文密文對重復(fù)以上過程，可得關(guān)于密鑰的一組線性方程，從對不同的明文密文對重復(fù)以上過程，可得關(guān)于密鑰的一組線性方程，從而確定出密鑰比特。而確定出密鑰比特。 Pi1,i2,ia Cj1,j2,jb=Kk1,k2,kc Ai,j,k

3、=Ai Aj Ak22/ 2/1, 12/1, 0pp 2/1, 12/1, 0pp如果方程成立的概率大于1/2，則由于使得左邊為0的明文數(shù)T大于總明文數(shù)的一半，在所有方程成立的情況中，左邊得0的可能性更大，所以此時令右邊取0。反之方程不成立的概率大于一半，則左邊1多，右邊取1 差分密碼分析選擇明文攻擊差分密碼分析選擇明文攻擊差分密碼分析是迄今已知的攻擊迭代密碼最有效的方法之一差分密碼分析是迄今已知的攻擊迭代密碼最有效的方法之一其基本思想是：其基本思想是： 通過分析通過分析明文對明文對的的差值差值對對密文對密文對的的差值差值的的影響來恢復(fù)某些密鑰比特。影響來恢復(fù)某些密鑰比特。 對分組長度為對分

4、組長度為n的的r輪迭代密碼，兩個輪迭代密碼，兩個n比特串比特串Yi和和Yi*的差的差分定義為分定義為YiYi(Yi*)1。其中表示。其中表示n比特串集上的一個特比特串集上的一個特定群運算，定群運算，(Yi*)1表示表示 Yi*在此群中的逆元。在此群中的逆元。在在DES的差分分的差分分析中差分的計算析中差分的計算選擇選擇YiYi*，因為，因為運算的單位元是運算的單位元是0元元由加密對可得差分序列：由加密對可得差分序列：Y0,Y1,Yr其中其中Y0和和Y0*是明文對，是明文對，Yi和和Yi* (1ir)是第是第i輪的輸出，它輪的輸出，它們同時也是第們同時也是第i+1輪的輸入。第輪的輸入。第i輪的子

5、密鑰記為輪的子密鑰記為Ki，F(xiàn)是輪是輪函數(shù)，且函數(shù)，且Yi=F(Yi-1,Ki)。23/ 差分密碼分析選擇明文攻擊差分密碼分析選擇明文攻擊定義定義4-1：r-輪特征輪特征(r-round characteristic)是一個差分序列：是一個差分序列：0,1,r其中其中0是明文對是明文對Y0和和Y0*的差分，的差分，i(1ir)是第是第i輪輸出輪輸出Yi和和Yi*的差分的差分r-輪特征輪特征=0,1,r的概率是指在明文的概率是指在明文Y0和子密鑰和子密鑰K1,Kr獨立、均勻獨立、均勻隨機時，明文對隨機時，明文對Y0和和Y0*的差分為的差分為0的條件下，第的條件下，第i(1ir)輪輸出輪輸出Yi和

6、和Yi*的差分為的差分為i的概率。的概率。共有共有r個概率值個概率值定義定義4-2：在：在r-輪特征輪特征=0,1,r中，定義中，定義 pi=P(F(Y)=i|Y=i-1)即即pi表示在輸入差分為表示在輸入差分為i-1的條件下，輪函數(shù)的條件下，輪函數(shù)F的輸出差分為的輸出差分為i的概率。的概率。（轉(zhuǎn)移概率）（轉(zhuǎn)移概率） r-輪特征輪特征=0,1,r的概率近似看作的概率近似看作 。24/riip1差分密碼分析選擇明文攻擊差分密碼分析選擇明文攻擊對對r-輪迭代密碼的差分密碼分析過程可綜述為如下步驟：輪迭代密碼的差分密碼分析過程可綜述為如下步驟： 找出一個找出一個(r-1)-輪特征輪特征(r-1)=

7、0 0, , 1 1, r-1-1，使得它的概率達到最大或幾使得它的概率達到最大或幾乎最大。（乎最大。（通過統(tǒng)計分析或者數(shù)學推導(dǎo)的方法通過統(tǒng)計分析或者數(shù)學推導(dǎo)的方法） 均勻隨機地選擇明文均勻隨機地選擇明文Y0并計算并計算Y0*，使得使得Y0和和Y0*的差分為的差分為 0 0，找出找出Y0和和Y0*在實際密鑰加密下所得的密文在實際密鑰加密下所得的密文Yr和和Yr*。若若最后一輪的子密鑰最后一輪的子密鑰Kr（或（或Kr的部分比特）有的部分比特）有2m個可能值個可能值Krj(1j2m)，設(shè)置相應(yīng)的，設(shè)置相應(yīng)的2m個計數(shù)器個計數(shù)器j(1j2m)。用每個用每個Krj解密密文解密密文Yr和和Yr*，得到，

8、得到Y(jié)r-1和和Yr-1*，如果，如果Yr-1和和Yr-1*的的差分是差分是r-1，則給相應(yīng)的計數(shù)器，則給相應(yīng)的計數(shù)器j加加1。 重復(fù)步驟，直到一個或幾個計數(shù)器的值明顯高于其他計數(shù)重復(fù)步驟，直到一個或幾個計數(shù)器的值明顯高于其他計數(shù)器的值，輸出它們所對應(yīng)的子密鑰（或部分比特）。器的值，輸出它們所對應(yīng)的子密鑰（或部分比特）。25/ Feistel 密碼結(jié)構(gòu)密碼結(jié)構(gòu) Feistel密碼結(jié)構(gòu)（一種特殊的密碼結(jié)構(gòu)（一種特殊的SPN結(jié)構(gòu)）結(jié)構(gòu)）早期，很多成功的分組密碼的結(jié)構(gòu)從本質(zhì)上說都是基于一個稱為早期，很多成功的分組密碼的結(jié)構(gòu)從本質(zhì)上說都是基于一個稱為Feistel網(wǎng)絡(luò)的結(jié)構(gòu)網(wǎng)絡(luò)的結(jié)構(gòu)加解密相似加解密相

9、似是是Feistel型密碼的一個實現(xiàn)優(yōu)點，但它對于密碼的型密碼的一個實現(xiàn)優(yōu)點，但它對于密碼的擴散似擴散似乎有些慢乎有些慢，例如需要兩輪才能改變輸入的每一個比特。不過在實用中，例如需要兩輪才能改變輸入的每一個比特。不過在實用中似乎并不會形成較大的影響，只要輪數(shù)足夠多。似乎并不會形成較大的影響，只要輪數(shù)足夠多。Feistel提出利用乘積密碼可獲得簡單代換密碼提出利用乘積密碼可獲得簡單代換密碼多輪迭代多輪迭代每一輪變換實際上是一種每一輪變換實際上是一種SPNFeistel還提出了實現(xiàn)代換和置換的方法還提出了實現(xiàn)代換和置換的方法 其思想實際上是其思想實際上是Shannon提出的提出的利用乘積密碼實現(xiàn)混

10、淆和擴散思想的具體利用乘積密碼實現(xiàn)混淆和擴散思想的具體應(yīng)用應(yīng)用26/ Feistel 密碼結(jié)構(gòu)密碼結(jié)構(gòu)27/1Feistel 加密結(jié)構(gòu)lHorst Feistel在70年代初設(shè)計了這樣的結(jié)構(gòu)，我們現(xiàn)在叫做Feistel cipher l每組明文分成左右兩半L0和R0l其第i輪迭代的輸入為前一輪輸出的函數(shù)：lLiRi1lRiLi1F(Ri1, Ki)lKi是第i 輪用的子密鑰，各輪不同，由密鑰K產(chǎn)生l最后一輪完成后再左右交換Feistel 密碼結(jié)構(gòu)密碼結(jié)構(gòu)Feistel網(wǎng)絡(luò)的實現(xiàn)與以下參數(shù)和特性有關(guān)：網(wǎng)絡(luò)的實現(xiàn)與以下參數(shù)和特性有關(guān)： 分組大小分組大小 分組越大則安全性越高，但加密速度就越慢。分組

11、密碼設(shè)計中最為普分組越大則安全性越高，但加密速度就越慢。分組密碼設(shè)計中最為普遍使用的分組大小是遍使用的分組大小是64比特。當前多使用比特。當前多使用128比特以上比特以上 密鑰大小密鑰大小密鑰越長則安全性越高，但加密速度就越慢?，F(xiàn)在普遍認為密鑰越長則安全性越高，但加密速度就越慢?，F(xiàn)在普遍認為64比特或比特或更短的密鑰長度是不安全的，通常使用更短的密鑰長度是不安全的，通常使用128比特的密鑰長度。比特的密鑰長度。 輪數(shù)輪數(shù) 單輪結(jié)構(gòu)遠不足以保證安全性，但多輪結(jié)構(gòu)可提供足夠的安全性。典單輪結(jié)構(gòu)遠不足以保證安全性，但多輪結(jié)構(gòu)可提供足夠的安全性。典型地，輪數(shù)取為型地，輪數(shù)取為16。 子密鑰產(chǎn)生算法：子

12、密鑰產(chǎn)生算法：該算法的復(fù)雜性越大，則密碼分析的困難性就越大。該算法的復(fù)雜性越大，則密碼分析的困難性就越大。 輪函數(shù)輪函數(shù) ：輪函數(shù)的復(fù)雜性越大，密碼分析的困難性也越大。：輪函數(shù)的復(fù)雜性越大，密碼分析的困難性也越大。28/ Feistel 密碼結(jié)構(gòu)密碼結(jié)構(gòu)在設(shè)計在設(shè)計Feistel網(wǎng)絡(luò)時，還有以下兩個方面需要考慮網(wǎng)絡(luò)時，還有以下兩個方面需要考慮 快速的軟件實現(xiàn)快速的軟件實現(xiàn)在很多情況中，算法是被鑲嵌在應(yīng)用程序中，因而無法用硬件實現(xiàn)。此在很多情況中，算法是被鑲嵌在應(yīng)用程序中，因而無法用硬件實現(xiàn)。此時算法的執(zhí)行速度是考慮的關(guān)鍵時算法的執(zhí)行速度是考慮的關(guān)鍵 算法容易分析算法容易分析如果算法能被無疑義地

13、解釋清楚，就可容易地分析算法抵抗攻擊的能力，如果算法能被無疑義地解釋清楚，就可容易地分析算法抵抗攻擊的能力，有助于設(shè)計高強度的算法有助于設(shè)計高強度的算法2. Feistel 解密結(jié)構(gòu)解密結(jié)構(gòu)Feistel解密過程本質(zhì)上和加密過程是一樣的，使加解密可用同一算法解密過程本質(zhì)上和加密過程是一樣的，使加解密可用同一算法,算法算法使用密文作為輸入使用密文作為輸入，但，但使用子密鑰使用子密鑰Ki的次序與加密過程相反的次序與加密過程相反，即第，即第1輪使用輪使用Kn，第，第2輪使用輪使用Kn-1，最后一輪使用，最后一輪使用K1。29/ Feistel 密碼結(jié)構(gòu)密碼結(jié)構(gòu)加密過程由上而下加密過程由上而下解密過程

14、由下而上解密過程由下而上圖中右邊標出了解密過圖中右邊標出了解密過程中每一輪的中間值與程中每一輪的中間值與左邊加密過程中間值的左邊加密過程中間值的對應(yīng)關(guān)系對應(yīng)關(guān)系即加密過程第即加密過程第i輪的輸輪的輸出是出是LEiREi（表示表示鏈接）鏈接）解密過程第解密過程第17-i輪相輪相應(yīng)的輸入是應(yīng)的輸入是RDiLDi最后一輪輸出密文是最后一輪輸出密文是RE16LE1630/數(shù)據(jù)加密標準數(shù)據(jù)加密標準DESDES的產(chǎn)生的產(chǎn)生美國國家標準局美國國家標準局1973年開始研究除國防部外的其它部門的計算機系統(tǒng)年開始研究除國防部外的其它部門的計算機系統(tǒng)的數(shù)據(jù)加密標準的數(shù)據(jù)加密標準于于1973年年5月月15日和日和19

15、74年年8月月27日先后兩次向公眾發(fā)出了征求加密算日先后兩次向公眾發(fā)出了征求加密算法的公告。加密算法要達到的目的（通常稱為法的公告。加密算法要達到的目的（通常稱為DES 密碼算法要求）主密碼算法要求）主要為以下四點：要為以下四點： （1）提供高質(zhì)量的數(shù)據(jù)保護提供高質(zhì)量的數(shù)據(jù)保護，防止數(shù)據(jù)未經(jīng)授權(quán)的泄露和未被察覺的，防止數(shù)據(jù)未經(jīng)授權(quán)的泄露和未被察覺的修改；修改； （2）計算安全性計算安全性：具有相當高的復(fù)雜性，使得破譯的開銷超過可能獲：具有相當高的復(fù)雜性，使得破譯的開銷超過可能獲得的利益，同時又要便于理解和掌握；得的利益，同時又要便于理解和掌握； （3）基爾霍夫準則基爾霍夫準則：DES密碼體制的

16、安全性應(yīng)該不依賴于算法的保密，密碼體制的安全性應(yīng)該不依賴于算法的保密，其安全性僅以加密密鑰的保密為基礎(chǔ)；其安全性僅以加密密鑰的保密為基礎(chǔ)； （4）可行性可行性：實現(xiàn)經(jīng)濟，運行有效，并且適用于多種完全不同的應(yīng)用。：實現(xiàn)經(jīng)濟，運行有效，并且適用于多種完全不同的應(yīng)用。 31/數(shù)據(jù)加密標準數(shù)據(jù)加密標準DESDES在在1975年年3月月17日首次被公布在聯(lián)邦記錄中日首次被公布在聯(lián)邦記錄中經(jīng)過大量的公開討論后，經(jīng)過大量的公開討論后，1977年年1月月15日美國政府頒布：日美國政府頒布：采采納美國納美國IBM公司設(shè)計的方案公司設(shè)計的方案作為作為非機密數(shù)據(jù)非機密數(shù)據(jù)的正式數(shù)據(jù)加密的正式數(shù)據(jù)加密標準（標準（DE

17、S, Data Encryption Standard），），DES被正式批被正式批準并作為美國聯(lián)邦信息處理標準，即準并作為美國聯(lián)邦信息處理標準，即FIPS-46，同年，同年7月月15日開始生效。日開始生效。它的分組長度為它的分組長度為64比特，密鑰長度為比特，密鑰長度為56比特，是早期的稱比特，是早期的稱作作Lucifer密碼的一種發(fā)展和修改。密碼的一種發(fā)展和修改。DES是迄今為止世界上最為廣泛使用和流行的一種分組密是迄今為止世界上最為廣泛使用和流行的一種分組密碼算法，碼算法，1996年以后，主要是年以后，主要是3DES32/ DES算法描述算法描述加密：加密：明文分組明文分組64bit初始

18、置換初始置換IP16輪的輪的Feistel結(jié)構(gòu)結(jié)構(gòu)初始逆置換初始逆置換IP-1是是IP的逆的逆密鑰編排密鑰編排密鑰密鑰56比特，每比特，每7bit加加1個個奇偶校驗位，總計奇偶校驗位，總計64比特比特置換函數(shù)置換函數(shù)PC-1左循環(huán)移位再置換函數(shù)左循環(huán)移位再置換函數(shù)PC-2輸出本輪子密鑰輸出本輪子密鑰迭代迭代16輪輪33/ DES算法描述算法描述1. 初始置換初始置換表表3-2(a)和和3-2(b)分別給出了初始置換和逆初始置換的定義，這兩個置換分別給出了初始置換和逆初始置換的定義，這兩個置換是互逆的。是互逆的。64比特的明文比特的明文M以以8比特為一行，共比特為一行，共8行，以行順序編號行，以

19、行順序編號由表由表3-2(a)得得X=IP(M)，由，由3-2(b)得得 YIP-1(X)=IP-1(IP(M)=M34/ DES算法描述算法描述2. 輪結(jié)構(gòu)輪結(jié)構(gòu)64比特的輪輸入分為左右兩半，右半部分是本輪子密鑰產(chǎn)生過程比特的輪輸入分為左右兩半，右半部分是本輪子密鑰產(chǎn)生過程35/和Feistel網(wǎng)絡(luò)一樣，每輪變換可由以下公式表示：lLiRi1 lRiLi1 F(Ri1, Ki)l其中輪密鑰Ki為48比特。 DES算法描述算法描述函數(shù)函數(shù)F(R,K)的計算過程的計算過程如上圖所示，輪輸入的右半部分如上圖所示，輪輸入的右半部分R為為32比特，比特，R首先被擴展成首先被擴展成48比特，比特，擴展過

20、程由表擴展過程由表3.2(c)定義，其定義，其中將中將R的的16個比特各重復(fù)一次個比特各重復(fù)一次。36/擴展后的48比特再與子密鑰Ki異或，然后再通過8個S盒，產(chǎn)生32比特的輸出。該輸出再經(jīng)過一個由表3.2(d)定義的置換P，產(chǎn)生的結(jié)果即為函數(shù)F(R,K)的輸出。 DES算法描述算法描述擴展置換擴展置換E和置換和置換P37/ DES算法描述算法描述代換盒，簡稱代換盒，簡稱S盒，盒，substitution boxSF中的代換由中的代換由8個個S盒組成，每個盒組成，每個S盒的輸入長為盒的輸入長為6比特、輸出長為比特、輸出長為4比特，比特，其變換關(guān)系由表其變換關(guān)系由表3.3定義，每個定義，每個S盒

21、給出了盒給出了4個代換（由一個表的個代換（由一個表的4行給行給出）。出）。DES的的S盒定義盒定義38/ DES算法描述算法描述對每個盒對每個盒Si其其6比特輸入中，比特輸入中，第第1個和第個和第6個比特個比特形成一個形成一個2位二進制數(shù)，用來選擇位二進制數(shù)，用來選擇Si的的4個代換中的一個個代換中的一個中間中間4位用來選擇列位用來選擇列。行和列選定后，得到其交叉位。行和列選定后，得到其交叉位置的十進制數(shù)，將這個數(shù)表示為置的十進制數(shù)，將這個數(shù)表示為4位二進制數(shù)即得這一位二進制數(shù)即得這一S盒的輸出。盒的輸出。例如，例如，S1 的輸入為的輸入為011001則行選為則行選為01（即第（即第1行），列

22、選為行），列選為1100（即第（即第12列）列）行列交叉位置的數(shù)為行列交叉位置的數(shù)為9，其，其4位二進制表示為位二進制表示為1001，所以，所以S1的輸出為的輸出為1001。S盒作為該密碼體制的唯一非線性組件對安全性至關(guān)重要盒作為該密碼體制的唯一非線性組件對安全性至關(guān)重要S-盒的設(shè)計準則還沒有完全公開，一些密碼學家懷疑美國盒的設(shè)計準則還沒有完全公開，一些密碼學家懷疑美國NSA(the National Security Agency)設(shè)計設(shè)計S-盒時隱藏了陷門盒時隱藏了陷門，即萬能鑰匙，即萬能鑰匙39/ DES算法描述算法描述3密鑰的產(chǎn)生密鑰的產(chǎn)生實際上，實際上，K是長度為是長度為64的位串，

23、的位串，其中其中56位是密鑰，位是密鑰，8位是奇偶校位是奇偶校驗位（為了檢錯），在密鑰編驗位（為了檢錯），在密鑰編排的計算中，這些校驗位可略排的計算中，這些校驗位可略去。去。DES密鑰編排算法結(jié)構(gòu)圖密鑰編排算法結(jié)構(gòu)圖LSi表示循環(huán)左移一個或兩個位表示循環(huán)左移一個或兩個位置置其中其中i為為1，2，9，16循環(huán)移循環(huán)移1位，位，其余循環(huán)移兩位其余循環(huán)移兩位40/ DES算法描述算法描述綜述加密過程綜述加密過程：(1) 給定給定64位的密鑰位的密鑰K，放棄奇偶校驗位（，放棄奇偶校驗位（8，16，64）形成連續(xù)的）形成連續(xù)的56比特的密鑰，對輸入分組進行固定的比特的密鑰，對輸入分組進行固定的“初始置換

24、初始置換”IP,我們可以將這個我們可以將這個初始置換寫為初始置換寫為 , 稱為稱為“左右半分左右半分組組”32bits(2)再看再看DES加密算法框圖，進行加密算法框圖，進行16輪迭代輪迭代 ： ， ， 輸入算法的輸入算法的56比特密鑰首先經(jīng)過一個置換運算比特密鑰首先經(jīng)過一個置換運算PC-1，該置換由表，該置換由表3.4(a)給出得到給出得到48比特的子串，比特的子串， 稱為布爾函數(shù)，它的特點是交換兩半分組。稱為布爾函數(shù)，它的特點是交換兩半分組。在第在第i 輪分別對輪分別對 進行左循環(huán)移位，所移位數(shù)由表進行左循環(huán)移位，所移位數(shù)由表3.4(c)給出。給出。移位后的結(jié)果作為求下一輪子密鑰的輸入，同

25、時也作為置換選擇移位后的結(jié)果作為求下一輪子密鑰的輸入，同時也作為置換選擇2 PC-2的輸入。通過置換選擇的輸入。通過置換選擇2產(chǎn)生的產(chǎn)生的48比特的比特的Ki，即為本輪的子密鑰，作為，即為本輪的子密鑰，作為函數(shù)函數(shù)F(Ri-1,Ki)的輸入。其中置換選擇的輸入。其中置換選擇2由表由表3.4(b)定義定義（3）DES算法的輸出，我們將最后一步寫為算法的輸出，我們將最后一步寫為: 注意注意 的輸入：在輸入之前，的輸入：在輸入之前，16輪迭代輸出的兩個半分組又進行了輪迭代輸出的兩個半分組又進行了一次交換。一次交換。輸入分組IPRL00,00RL 和16, 2 , 1i1iiRLiiiikRfLR,1

26、1稱為輪密鑰ikf1 - i1 - iRL ，16161,LRIP輸出分組1IP DES算法描述算法描述DES密鑰編排中使用的表（表密鑰編排中使用的表（表3-4） (a) 置換選擇置換選擇1 (b) 置換選擇置換選擇2 (c) 左循環(huán)移位位數(shù)左循環(huán)移位位數(shù) 42/ DES算法描述算法描述4解密解密l和和Feistel密碼一樣，密碼一樣，DES的解密和加密算法使用同一算法，但的解密和加密算法使用同一算法，但子密鑰子密鑰使用的順序相反使用的順序相反解密時子密鑰的產(chǎn)生有兩種方式：解密時子密鑰的產(chǎn)生有兩種方式：l1）是先由）是先由K產(chǎn)生產(chǎn)生16個子密鑰，個子密鑰，再逆續(xù)使用再逆續(xù)使用l2）反序產(chǎn)生。）

27、反序產(chǎn)生。(在前面講過的密鑰擴展過程中若改在前面講過的密鑰擴展過程中若改LSi為為l則也就可以依次產(chǎn)生這逆序的子密鑰。則也就可以依次產(chǎn)生這逆序的子密鑰。43/其它,21692110iiRSi115161621,kkkkkk 例例 在加密密鑰在加密密鑰 下，將明文消息下，將明文消息 加密為密文消息加密為密文消息 。讓我們通過讓我們通過DES算法來確認解密函數(shù)的正確運算，也就是算法來確認解密函數(shù)的正確運算，也就是在在 下，下， 的解密就輸出的解密就輸出 。 解：解：解密算法首先輸入密文解密算法首先輸入密文 作為作為“輸入分組輸入分組”，即即 但是因為但是因為c是實際上是加密算法中最后一是實際上是加

28、密算法中最后一步的步的“輸出分組輸出分組”，即：，即： 在第一輪中，我們有在第一輪中，我們有 這兩個式子的右邊，這兩個式子的右邊， 應(yīng)該用應(yīng)該用 來代替，來代替， 應(yīng)該用應(yīng)該用kmckcmc cIPRL00,161600,LRRL1161600011601,;kLfRLRfLRLRL16L15R16R161515,kRfL 其中其中 ，因此，上面兩個式子實際上是下面的兩個，因此，上面兩個式子實際上是下面的兩個 所以，所以，在第一輪解密以后在第一輪解密以后，我們得到，我們得到因此，因此，在第二輪開始在第二輪開始，兩個半分組是，兩個半分組是 .在隨后的在隨后的15輪中，使用同樣的驗證，我們將獲得輪

29、中，使用同樣的驗證，我們將獲得在在16輪迭代得到的兩個最后的半分組輪迭代得到的兩個最后的半分組 被交換為被交換為 然后輸入到然后輸入到 來消除來消除IP在式中的影響。在式中的影響。解密函數(shù)的輸出確實是最初的明文分組解密函數(shù)的輸出確實是最初的明文分組m.161kk 1516151515151151,;LkRfLRfLRRL151511,LRRL1515,LR001616141422,LRRLLRRL1616,RL001616,LRRL1IPDES的安全性問題的安全性問題完全依賴于所用的密鑰，即算法是公開的完全依賴于所用的密鑰，即算法是公開的DES的設(shè)計特色：的設(shè)計特色： 在在DES算法中函數(shù)是最

30、基本的關(guān)鍵環(huán)節(jié)，其中算法中函數(shù)是最基本的關(guān)鍵環(huán)節(jié)，其中 （1）用）用S盒實現(xiàn)小塊的非線性變換，達到混亂目的盒實現(xiàn)小塊的非線性變換，達到混亂目的 （2）用置換）用置換p實現(xiàn)大塊的非線性變換，達到擴散目的實現(xiàn)大塊的非線性變換，達到擴散目的 （3）置換）置換p的設(shè)計是每層的設(shè)計是每層s盒的盒的4bit輸出進入到下一輸出進入到下一 層的層的4個不同個不同S盒盒 DES的安全性包括：的安全性包括：取反特性取反特性，弱密鑰和半弱密鑰弱密鑰和半弱密鑰，密鑰密鑰與密文和明文的關(guān)系，與密文和明文的關(guān)系，DES評估與窮搜索破譯評估與窮搜索破譯3.6 高級加密標準高級加密標準AES 由于由于DES要花費比較大的軟硬

31、件代價，效率不盡如人意，況且要花費比較大的軟硬件代價，效率不盡如人意，況且DES密密鑰較短不能抵抗群搜索攻擊，于是更好的標準鑰較短不能抵抗群搜索攻擊，于是更好的標準AES走向了前臺。走向了前臺。 2000年年10月月2日日NIST宣布宣布Rijndael作為新的作為新的AES。至此，經(jīng)過。至此，經(jīng)過3年多的討論，年多的討論，Rijndael終終于脫穎而出。于脫穎而出。 2006年，年，AES已然成為了對稱密鑰加密中重要的國際標準之一已然成為了對稱密鑰加密中重要的國際標準之一AES的應(yīng)用產(chǎn)品：有移動硬盤，的應(yīng)用產(chǎn)品：有移動硬盤，USB無線網(wǎng)卡，加密鎖，指紋加密無線網(wǎng)卡，加密鎖，指紋加密U盤，盤，

32、 指紋加密防護盾等。指紋加密防護盾等。 47/ Rijndael的數(shù)學基礎(chǔ)和設(shè)計思想的數(shù)學基礎(chǔ)和設(shè)計思想1. 有限域有限域GF(28)有限域中的元素可以用多種不同的方式表示。有限域中的元素可以用多種不同的方式表示。對于任意對于任意素數(shù)素數(shù)的方冪，都的方冪，都有惟一的一個有限域有惟一的一個有限域，因此因此GF(28)的所有表示是同構(gòu)的的所有表示是同構(gòu)的，但不同的表示但不同的表示方法會影響到方法會影響到GF(28)上運算的復(fù)雜度上運算的復(fù)雜度本算法采用傳統(tǒng)的多項式表示法：本算法采用傳統(tǒng)的多項式表示法：將將b7b6b5b4b3b2b1b0構(gòu)成的字節(jié)構(gòu)成的字節(jié)b看成系數(shù)在看成系數(shù)在GF(2)=0,1中

33、的多項式中的多項式 b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0例如：例如： 十六進制數(shù)十六進制數(shù)57對應(yīng)的二進制為對應(yīng)的二進制為01010111，看成一個字節(jié)，對應(yīng)的多項，看成一個字節(jié)，對應(yīng)的多項式為式為x6+x4+x2+x+148/ Rijndael的數(shù)學基礎(chǔ)和設(shè)計思想的數(shù)學基礎(chǔ)和設(shè)計思想AES的理論基礎(chǔ)定義在的理論基礎(chǔ)定義在GF(28) ,其基本的運算有三種，其基本的運算有三種，分別為加分別為加法，乘法和法，乘法和x乘。乘。加法：加法：在多項式表示中，在多項式表示中，GF(28)上兩個元素的和仍然是一個次數(shù)不超過上兩個元素的和仍然是一個次數(shù)不超過7的多項的多項

34、式，其系數(shù)等于兩個元素對應(yīng)系數(shù)的模式，其系數(shù)等于兩個元素對應(yīng)系數(shù)的模2加（比特異或）。加（比特異或）。例如：例如： 57+83=D4，用多項式表示為，用多項式表示為(x6+x4+x2+x+1)+(x7+x+1)=x7+x6+x4+x2 (mod m(x)用二進制表示為用二進制表示為 01010111+10000011=11010100由于每個元素的加法逆元等于自己，所以減法和加法相同。由于每個元素的加法逆元等于自己，所以減法和加法相同。49/ Rijndael的數(shù)學基礎(chǔ)和設(shè)計思想的數(shù)學基礎(chǔ)和設(shè)計思想乘法：乘法：要計算要計算GF(28)上的乘法，必須先確定一個上的乘法，必須先確定一個GF(2)上

35、的上的8次不可次不可約多項式，約多項式，GF(28)上兩個元素的乘積就是這兩個多項式的模上兩個元素的乘積就是這兩個多項式的模乘，在乘，在Rijndael密碼中，這個密碼中，這個8次不可約多項式確定為次不可約多項式確定為 m(x)=x8+x4+x3+x+1它的十六進制表示為它的十六進制表示為11B。二進制為。二進制為100011011例如，例如，5783=C1可表示為以下的多項式乘法：可表示為以下的多項式乘法：(x6+x4+x2+x+1)(x7+x+1)=x7+x6+1(mod m(x)乘法運算雖然不是標準的按字節(jié)的運算，但也是比較簡單的計乘法運算雖然不是標準的按字節(jié)的運算，但也是比較簡單的計算

36、部件。算部件。50/ Rijndael的數(shù)學基礎(chǔ)和設(shè)計思想的數(shù)學基礎(chǔ)和設(shè)計思想以上定義的以上定義的乘法滿足交換律乘法滿足交換律，且，且有單位元有單位元01。逆元逆元，對任何次數(shù)小于，對任何次數(shù)小于8的多項式的多項式b(x)，可用推廣的歐幾里得算，可用推廣的歐幾里得算法得法得b(x)a(x)+m(x)c(x)=1即即a(x)b(x)=1 mod m(x)，因此，因此a(x)是是b(x)的乘法逆元。的乘法逆元。再者，再者，乘法還滿足分配律乘法還滿足分配律：a(x)(b(x)+c(x)=a(x)b(x)+a(x)c(x)所以，所以，256個字節(jié)值構(gòu)成的集合，在以上定義的加法和乘法運算個字節(jié)值構(gòu)成的集

37、合，在以上定義的加法和乘法運算下，有有限域下，有有限域GF(28)的結(jié)構(gòu)的結(jié)構(gòu)非非0元的乘法滿足元的乘法滿足Abel群，加法滿足群，加法滿足Abel群，群，,滿足分配率滿足分配率51/ Rijndael的數(shù)學基礎(chǔ)和設(shè)計思想的數(shù)學基礎(chǔ)和設(shè)計思想X乘乘GF(28)上還定義了一個運算，稱之為上還定義了一個運算，稱之為x乘法，其定義為乘法，其定義為xb(x)= b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0 x(mod m(x)如果如果b7=0，求模結(jié)果不變，否則為乘積結(jié)果減去，求模結(jié)果不變，否則為乘積結(jié)果減去m(x)，即求乘積結(jié)果與，即求乘積結(jié)果與m(x)的異或。的異或。

38、由此得出由此得出x（十六進制數(shù)（十六進制數(shù)02）乘乘b(x)可以可以先對先對b(x)在字節(jié)內(nèi)左移一位在字節(jié)內(nèi)左移一位（最后（最后一位補一位補0），），若若b7=1，則再與，則再與1B（其二進制為（其二進制為00011011）做逐比特異或做逐比特異或來來實現(xiàn)，實現(xiàn)，該運算記為該運算記為b=xtime(a)。在專用芯片中，在專用芯片中，xtime只需只需4個異或。個異或。x的冪乘運算可以重復(fù)應(yīng)用的冪乘運算可以重復(fù)應(yīng)用xtime來實現(xiàn)。而任來實現(xiàn)。而任意常數(shù)乘法可以通過對中間結(jié)果相加實現(xiàn)。意常數(shù)乘法可以通過對中間結(jié)果相加實現(xiàn)。例如，例如，5708可按如下方式實現(xiàn)：可按如下方式實現(xiàn)： 5702=xti

39、me(57)=AE；5704=xtime(AE)=47；5708=xtime(47)=8E；52/ Rijndael的數(shù)學基礎(chǔ)和設(shè)計思想的數(shù)學基礎(chǔ)和設(shè)計思想2. 系數(shù)在系數(shù)在GF(28)上的多項式上的多項式4個字節(jié)構(gòu)成的向量個字節(jié)構(gòu)成的向量可以表示為可以表示為系數(shù)在系數(shù)在GF(28)上的次數(shù)小于上的次數(shù)小于4的多項式，的多項式，多項式的多項式的加法加法就是對應(yīng)系數(shù)相加，即就是對應(yīng)系數(shù)相加，即4字節(jié)向量的逐比特異或字節(jié)向量的逐比特異或規(guī)定多項式的規(guī)定多項式的乘法運算必須要取模乘法運算必須要取模M(x)=x4+1，這樣使得次數(shù)小于，這樣使得次數(shù)小于4的多項的多項式的乘積仍然是一個次數(shù)小于式的乘積仍

40、然是一個次數(shù)小于4的多項式，將多項式的模乘運算記為的多項式，將多項式的模乘運算記為 設(shè)設(shè)a(x)=a3x3+a2x2+a1x+a0，b(x)=b3x3+b2x2+b1x+b0 c(x)=c3x3+c2x2+c1x+c0，c(x)=a(x)b(x) mod (x4+1) 而而xj mod (x4+1)=xj mod 4，所以，所以c0=a0b0 a3b1 a2b2 a1b3c1=a1b0 a0b1 a3b2 a2b3c2=a2b0 a1b1 a0b2 a3b3c3=a3b0 a2b1 a1b2 a0b353/ Rijndael的數(shù)學基礎(chǔ)和設(shè)計思想的數(shù)學基礎(chǔ)和設(shè)計思想可將上述計算表示為可將上述計算

41、表示為 注意到注意到M(x)不是不是GF(28)上的不可約多項式（甚至也不是上的不可約多項式（甚至也不是GF(2)上的不可約上的不可約多項式），因此非零多項式的這種乘法不是群運算。多項式），因此非零多項式的這種乘法不是群運算。不過在不過在Rijndael密碼中，對多項式密碼中，對多項式b(x)，這種乘法運算只限于乘一個固定，這種乘法運算只限于乘一個固定的有逆元的多項式的有逆元的多項式a(x)=a3x3+a2x2+a1x+a0。定理定理1 系數(shù)在系數(shù)在GF(28)上的多項式上的多項式a3x3+a2x2+a1x+a0是模是模x4+1可逆可逆的，當且僅當以下矩陣在的，當且僅當以下矩陣在GF(28)上

42、可逆。上可逆。54/3210cccc0123301223011230aaaaaaaaaaaaaaaa3210bbbb0123301223011230aaaaaaaaaaaaaaaa55/證明：證明：a3x3+a2x2+a1x+a0是模是模x4+1可逆的，當且僅當存在多項式可逆的，當且僅當存在多項式h3x3+h2x2+h1x+h0，使得，使得(a3x3+a2x2+a1x+a0)( h3x3+h2x2+h1x+h0)=1 mod(x4+1)因此有因此有(a3x3+a2x2+a1x+a0)( h2x3+h1x2+h0 x+h3)=x mod(x4+1) (a3x3+a2x2+a1x+a0)( h1x

43、3+h0 x2+h3x+h2)=x2 mod(x4+1)(a3x3+a2x2+a1x+a0)( h0 x3+h3x2+h2x+h1)=x3 mod(x4+1)；將以上關(guān)系寫成矩陣形式即得將以上關(guān)系寫成矩陣形式即得 = c(x)=xb(x)定義為定義為x與與b(x)的模的模x4+1乘法，即乘法，即c(x)=xb(x)=b2x3+b1x2+b0 x+b3。其矩陣表示中，除。其矩陣表示中，除a1=01外，其他所有外，其他所有ai=00，即，即 因此因此x（或（或x的冪）模乘多項式相當于對字節(jié)構(gòu)成的向量進行字節(jié)循環(huán)移位的冪）模乘多項式相當于對字節(jié)構(gòu)成的向量進行字節(jié)循環(huán)移位012330122301123

44、0aaaaaaaaaaaaaaaa0123301223011230hhhhhhhhhhhhhhhh10000100001000013210cccc000100000000010000000001010000003210bbbbRijndael算法的特點算法的特點 1.AES的加解密算法、密鑰生成算法都是以的加解密算法、密鑰生成算法都是以State為為 輸入輸入 2.加密時，首先進行加密時，首先進行“輪密鑰加輪密鑰加”算法，然后重復(fù)算法，然后重復(fù)9輪基輪基本密碼模塊的迭代算法，每一輪有字節(jié)代換，行移位、列混本密碼模塊的迭代算法，每一輪有字節(jié)代換，行移位、列混淆和輪密鑰加淆和輪密鑰加 四個算法；最

45、后進行第四個算法；最后進行第10輪運算，它與前面輪運算，它與前面9輪比一樣的地方，就是少了列混淆算法。輪比一樣的地方，就是少了列混淆算法。 3.解密時，是執(zhí)行加密的逆過程，但要注意在解密時，字解密時，是執(zhí)行加密的逆過程，但要注意在解密時，字節(jié)代換、行移位和列混淆三種運算是執(zhí)行逆過程，算法設(shè)計節(jié)代換、行移位和列混淆三種運算是執(zhí)行逆過程，算法設(shè)計完全不一樣，只有輪密鑰加算法和加密一樣完全不一樣，只有輪密鑰加算法和加密一樣 2.輪函數(shù)輪函數(shù)Rijndael的輪函數(shù)由的輪函數(shù)由4個不同的計算部件組成，分別是：個不同的計算部件組成，分別是：字節(jié)代換（字節(jié)代換（ByteSub）、行移位（）、行移位（Shi

46、ftRow）列混合（列混合（MixColumn）、密鑰加（）、密鑰加（AddRoundKey）(1) 字節(jié)代換（字節(jié)代換（ByteSub）字節(jié)代換是非線性變換，獨立地對狀態(tài)的每個字節(jié)進行。代換表（即字節(jié)代換是非線性變換，獨立地對狀態(tài)的每個字節(jié)進行。代換表（即S-盒）是可逆的，由以下兩個變換的合成得到：盒）是可逆的，由以下兩個變換的合成得到： 首先，將字節(jié)看作首先，將字節(jié)看作GF(28)上的元素，上的元素，映射到自己的乘法逆元，映射到自己的乘法逆元，00映射到自己。映射到自己。 其次，對字節(jié)做如下的（其次，對字節(jié)做如下的（GF(2)上的，可逆的）仿射變換：上的，可逆的）仿射變換： 上述上述S-盒

47、對狀態(tài)的所有字節(jié)所做的變換記為盒對狀態(tài)的所有字節(jié)所做的變換記為ByteSub (State)57/ 111101110011000110001100111011111000110011101111111101110011000176543210yyyyyyyy 0110001176543210 xxxxxxxx整個變換做成整個變換做成256字節(jié)的代換字節(jié)的代換表，運算時查表即可表，運算時查表即可 算法說明算法說明圖圖3.19是字節(jié)代換示意圖。是字節(jié)代換示意圖。ByteSub的逆變換的逆變換由代換表的逆表做字節(jié)代換，可通過如下兩由代換表的逆表做字節(jié)代換，可通過如下兩步實現(xiàn)步實現(xiàn): 首先進行仿射變

48、換的逆變換首先進行仿射變換的逆變換再求每一字節(jié)在再求每一字節(jié)在GF(28)上逆元上逆元58/S盒盒aijbij 算法說明算法說明(2) 行移位（行移位（ShiftRow）行移位是將狀態(tài)陣列的各行進行循環(huán)移位，不同狀態(tài)行的位移行移位是將狀態(tài)陣列的各行進行循環(huán)移位，不同狀態(tài)行的位移量不同。量不同。第第0行不移動行不移動第第1行循環(huán)左移行循環(huán)左移C1個字節(jié)個字節(jié)第第2行循環(huán)左移行循環(huán)左移C2個字節(jié)個字節(jié)第第3行循環(huán)左移行循環(huán)左移C3個字節(jié)個字節(jié)位移量位移量C1、C2、C3的取值與的取值與Nb有關(guān)，由表有關(guān)，由表3.10給出。給出。 表3.1059/ 算法說明算法說明按指定的位移量對狀態(tài)的行進行的行移

49、位運算記為按指定的位移量對狀態(tài)的行進行的行移位運算記為ShiftRow(State)圖圖3.20是行移位示意圖。是行移位示意圖。ShiftRow的逆變換的逆變換是對狀態(tài)陣列的后是對狀態(tài)陣列的后3列分別以位移量列分別以位移量Nb-C1、Nb-C2、Nb-C3進行循環(huán)移位。進行循環(huán)移位。60/左移左移0位位左移左移1位位左移左移2位位左移左移3位位算法說明算法說明（3）列混合（）列混合（MixColumn）在列混合變換中，在列混合變換中，將狀態(tài)陣列的每個列視為將狀態(tài)陣列的每個列視為GF(28)上的多項式，再與一上的多項式，再與一個固定的多項式個固定的多項式c(x)進行模進行模x4+1乘法乘法。當然要求。當然要求c(x)是模是模x4+1可逆的可逆的多項多項式，否則列混合變換就是不可逆的，因而會使不同的輸入分組對應(yīng)的輸式，否則列混合變換就是不可逆的，因而會使不同的輸入分組對應(yīng)的輸出分組可能相同。出分組可能相同。Rijndael的設(shè)計者給出的的設(shè)計者給出的c(x)為為（系數(shù)用十六進制數(shù)表（系數(shù)用十