現(xiàn)代密碼學(xué)

第3章分組密碼

3.1分組密碼概述3.2數(shù)據(jù)加密標(biāo)準(zhǔn)3.3差分密碼分析與線性密碼分析3.4分組密碼的運(yùn)行模式3.5IDEA3.6AES算法--3.7中國商業(yè)密碼SM43.8祖沖之密碼第三章分組密碼3.1分組密碼概述第三章分組密碼3.1.1代換3.1.2擴(kuò)散和混淆3.1.3Feistel密碼結(jié)構(gòu)3.1分組密碼概述第三章分組密碼分組密碼是將明文消息編碼表示后的數(shù)字序列

劃分成長為n的組，各組(長為n的矢量)分別在密鑰控制下變換成等長的輸出數(shù)字序列(長為m的矢量)，其加密函數(shù)E：Vn×KVm，Vn和Vm分別是n維和m維矢量空間，K為密鑰空間，參看圖3-1所示。圖3-1分組密碼框圖第三章分組密碼3.1.1代換如果明文和密文的分組長都為比特，則明文的每一個(gè)分組都有個(gè)可能的取值。為使加密運(yùn)算可逆（使解密運(yùn)算可行），明文的每一個(gè)分組都應(yīng)產(chǎn)生惟一的一個(gè)密文分組，這樣的變換是可逆的，稱明文分組到密文分組的可逆變換為代換。不同可逆變換的個(gè)數(shù)有個(gè)。第三章分組密碼3.1.1代換圖3-2表示的代換密碼的一般結(jié)構(gòu)，4比特輸入產(chǎn)生16個(gè)可能輸入狀態(tài)中的一個(gè)，由代換結(jié)構(gòu)將這一狀態(tài)映射為16個(gè)可能輸出狀態(tài)中的一個(gè)，每一輸出狀態(tài)由4個(gè)密文比特表示。加密映射和解密映射可由代換表來定義，如表3-1所示。這種定義法是分組密碼最常用的形式，能用于定義明文和密文之間的任何可逆映射。第三章分組密碼3.1.1代換圖3-2 代換結(jié)構(gòu)第三章分組密碼3.1.1代換明文密文明文密文00001110100000110001010010011010001011011010011000110001101111000100001011000101010111111101100101101011111000000111100011110111密文明文密文明文00001110100001110001001110011101001001001010100100111000101101100100000111001011010111001101001001101010111000000111111111110101表3-1 圖3-2對(duì)應(yīng)的代換表但這種代換結(jié)構(gòu)在實(shí)用中還有一些問題需考慮。如果分組長度太小，如，系統(tǒng)則等價(jià)于古典的代換密碼，容易通過對(duì)明文的統(tǒng)計(jì)分析而攻破。這個(gè)弱點(diǎn)不是代換結(jié)構(gòu)固有的，只是因?yàn)榉纸M長度太小。如果分組長度足夠大，而且從明文到密文可有任意可逆的代換，那么明文的統(tǒng)計(jì)特性將被隱藏而使以上的攻擊不能奏效。3.1.1代換第三章分組密碼3.1.2擴(kuò)散和混淆第三章分組密碼擴(kuò)散和混淆是由Shannon提出的設(shè)計(jì)密碼系統(tǒng)的兩個(gè)基本方法，目的是抗擊敵手對(duì)密碼系統(tǒng)的統(tǒng)計(jì)分析。如果敵手知道明文的某些統(tǒng)計(jì)特性，如消息中不同字母出現(xiàn)的頻率、或可能出現(xiàn)的特定單詞或短語，而且這些統(tǒng)計(jì)特性以某種方式在密文中反映出來，敵手就有可能得出加密密鑰或其一部分、或包含加密密鑰的一個(gè)可能密鑰集合。在Shannon稱之為理想密碼的密碼系統(tǒng)中，密文的所有統(tǒng)計(jì)特性都與所使用的密鑰獨(dú)立。3.1.2擴(kuò)散和混淆第三章分組密碼擴(kuò)散，就是將明文的統(tǒng)計(jì)特性散布到密文中去，實(shí)現(xiàn)方式是使得密文中每一位由明文中多位產(chǎn)生。例如對(duì)英文消息

的加密操作：其中是求字母對(duì)應(yīng)的序號(hào)，是求序號(hào)對(duì)應(yīng)的字母，密文字母是由明文中個(gè)連續(xù)的字母相加而得。這時(shí)明文的統(tǒng)計(jì)特性將被散布到密文，因而每一字母在密文中出現(xiàn)的頻率比在明文中出現(xiàn)的頻率更接近于相等，雙字母及多字母出現(xiàn)的頻率也更接近于相等。在二元分組密碼中，可對(duì)數(shù)據(jù)重復(fù)執(zhí)行某個(gè)置換再對(duì)這一置換作用以一函數(shù)，可獲得擴(kuò)散。3.1.2擴(kuò)散和混淆第三章分組密碼混淆是使密文和密鑰之間的統(tǒng)計(jì)關(guān)系變得盡可能復(fù)雜，以使敵手無法得到密鑰。因此即使敵手能得到密文的一些統(tǒng)計(jì)關(guān)系，由于密鑰和密文之間統(tǒng)計(jì)關(guān)系復(fù)雜化，敵手無法得到密鑰。使用復(fù)雜的代換算法可得預(yù)期的混淆效果，而簡單的線性代換函數(shù)得到的混淆效果不夠理想。擴(kuò)散和混淆成功地實(shí)現(xiàn)了分組密碼的本質(zhì)屬性，因而成為設(shè)計(jì)現(xiàn)代分組密碼的基礎(chǔ)。3.1.3Feistel密碼結(jié)構(gòu)第三章分組密碼Feistel提出利用乘積密碼可獲得簡單的代換密碼，乘積密碼指順序地執(zhí)行兩個(gè)或多個(gè)基本密碼系統(tǒng)，使得最后結(jié)果的密碼強(qiáng)度高于每個(gè)基本密碼系統(tǒng)產(chǎn)生的結(jié)果Feistel還提出了實(shí)現(xiàn)代換和置換的方法。其思想實(shí)際上是Shannon提出的利用乘積密碼實(shí)現(xiàn)混淆和擴(kuò)散思想的具體應(yīng)用。3.1.3Feistel密碼結(jié)構(gòu)第三章分組密碼Feistel加密結(jié)構(gòu)：圖3-3是Feistel網(wǎng)絡(luò)示意圖，加密算法的輸入是分組長為的明文和一個(gè)密鑰。將每組明文分成左右兩半和，在進(jìn)行完輪迭代后，左右兩半再合并到一起以產(chǎn)生密文分組。其第輪迭代的輸入為前輪輸出的函數(shù)：其中是第輪用的子密鑰，由加密密鑰得到。一般，各輪子密鑰彼此不同而且與也不同。3.1.3Feistel密碼結(jié)構(gòu)第三章分組密碼圖3-3Feistel網(wǎng)絡(luò)3.1.3Feistel密碼結(jié)構(gòu)Feistel加密結(jié)構(gòu)：第三章分組密碼Feistel網(wǎng)絡(luò)中每輪結(jié)構(gòu)都相同，每輪中右半數(shù)據(jù)被作用于輪函數(shù)后，再與左半數(shù)據(jù)進(jìn)行異或運(yùn)算，這一過程就是上面介紹的代換。每輪輪函數(shù)的結(jié)構(gòu)都相同，但以不同的子密鑰作為參數(shù)。代換過程完成后，再交換左、右兩半數(shù)據(jù)，這一過程稱為置換。這種結(jié)構(gòu)是Shannon提出的代換──置換網(wǎng)絡(luò)SPN（Substitution-PermutationNetwork）的特有形式。3.1.3Feistel密碼結(jié)構(gòu)Feistel網(wǎng)絡(luò)的實(shí)現(xiàn)與以下參數(shù)和特性有關(guān)：第三章分組密碼分組大?。悍纸M越大則安全性越高，但加密速度就越慢。密鑰大?。好荑€越長則安全性越高，但加密速度就越慢。輪數(shù)：單輪結(jié)構(gòu)遠(yuǎn)不足以保證安全性，多輪結(jié)構(gòu)可提供足夠的安全性。子密鑰產(chǎn)生算法：該算法的復(fù)雜性越大，則密碼分析的困難性就越大。輪函數(shù)：輪函數(shù)的復(fù)雜性越大，密碼分析的困難性也越大。3.1.3Feistel密碼結(jié)構(gòu)Feistel解密結(jié)構(gòu)：第三章分組密碼Feistel解密過程本質(zhì)上和加密過程是一樣的，算法使用密文作為輸入，但使用子密鑰的次序與加密過程相反，即第一輪使用，第二輪使用，一直下去，最后一輪使用。這一特性保證了解密和加密可采用同一算法。如下圖（圖3-4）的左邊表示16輪Feistel網(wǎng)絡(luò)的加密過程，右邊表示解密過程，加密過程由上而下，解密過程由下而上。3.1.3Feistel密碼結(jié)構(gòu)第三章分組密碼圖3-4 Feistel加解密過程3.1.3Feistel密碼結(jié)構(gòu)Feistel解密結(jié)構(gòu)：第三章分組密碼加密算法每輪的左右兩半用和表示，解密算法每輪的左右兩半用和表示。在加密過程中：在解密過程中：3.2數(shù)據(jù)加密標(biāo)準(zhǔn)第三章分組密碼3.2.1DES描述3.2.2二重DES3.2.3兩個(gè)密鑰的三重DES3.2.43個(gè)密鑰的三重DES第三章分組密碼3.2.1DES描述DES（DataEncryptionStandard）是迄今為止世界上最為廣泛使用和流行的一種分組密碼算法，它的分組長度為64比特，密鑰長度為56比特，它是由美國IBM公司研制的，是早期的稱作Lucifer密碼的一種發(fā)展和修改。每隔五年由美國國家保密局（NSA—NationalSecurityAgency）作出評(píng)估，并重新批準(zhǔn)它是否繼續(xù)作為聯(lián)邦加密標(biāo)準(zhǔn)。最后一次評(píng)估是在1994年1月，美國已決定1998年12月以后將不再使用DES。美國國家標(biāo)準(zhǔn)和技術(shù)協(xié)會(huì)已征集并進(jìn)行了幾輪評(píng)估篩選產(chǎn)生了稱之為AES(AdvancedEncryptionStandard)的新加密標(biāo)準(zhǔn)。3.2.1DES描述第三章分組密碼圖3-5是DES加密算法的框圖，其中明文分組長為64比特，密鑰長為56比特。圖的左邊是明文的處理過程，有三個(gè)階段，首先是一個(gè)初始置換IP，用于重排明文分組的64比特?cái)?shù)據(jù)。然后是具有相同功能的16輪變換，每輪中都有置換和代換運(yùn)算，第16輪變換的輸出分為左右兩半，并被交換次序。最后再經(jīng)過一個(gè)逆初始置換IP-1（為IP的逆）從而產(chǎn)生64比特的密文。除初始置換和逆初始置換外，DES的結(jié)構(gòu)和圖3-3所示的Feistel密碼結(jié)構(gòu)完全相同。3.2.1DES描述第三章分組密碼圖3-5DES加密算法框圖3.2.1DES描述第三章分組密碼1.初始置換表3-2DES的置換表(a)初始置換IP（b）逆初始置換IP-1表3-2（a）和表3-2（b）分別給出了初始置換和逆初始置換的定義，為了顯示這兩個(gè)置換的確是彼此互逆的。3.2.1DES描述第三章分組密碼1.初始置換表3-2DES的置換表（c）選擇擴(kuò)展運(yùn)算E（d）置換運(yùn)算P3.2.1DES描述第三章分組密碼2.輪結(jié)構(gòu)圖3-6是DES加密算法的輪結(jié)構(gòu)，首先看圖的左半部分。將64比特的輪輸入分為各為32比特的左、右兩半，分別記為L和R。和Feistel網(wǎng)絡(luò)一樣，每輪變換可由以下公式表示：3.2.1DES描述2.輪結(jié)構(gòu)第三章分組密碼圖3-6DES加密算法的輪結(jié)構(gòu)3.2.1DES描述第三章分組密碼2.輪結(jié)構(gòu)其中輪密鑰為48比特，函數(shù)的計(jì)算如圖3-7所示。輪輸入的右半部分R為32比特，R首先被擴(kuò)展成48比特，擴(kuò)展過程由表3-2（c）定義，其中將R的16個(gè)比特各重復(fù)一次。擴(kuò)展后的48比特再與子密鑰異或，然后再通過一個(gè)S盒，產(chǎn)生32比特的輸出。該輸出再經(jīng)過一個(gè)由表3-2（d）定義的置換，產(chǎn)生的結(jié)果即為函數(shù)的輸出。第三章分組密碼3.2.1DES描述2.輪結(jié)構(gòu)圖3-7函數(shù)的計(jì)算過程3.2.1DES描述2.輪結(jié)構(gòu)第三章分組密碼中的代換由8個(gè)S盒組成，每個(gè)S盒的輸入長為6比特、輸出長為4比特，其變換關(guān)系由表3-3定義，每個(gè)S盒給出了4個(gè)代換（由一個(gè)表的4行給出）。行\(zhòng)列0123456789101112131415S101441312151183106125907101574142131106121195382411481362111512973105031512824917511314100613S201518146113497213120510131347152815120110691152014711104131581269321531381013154211671205149對(duì)每個(gè)盒Si，其6比特輸入中，第1個(gè)和第6個(gè)比特形成一個(gè)2位二進(jìn)制數(shù)，用來選擇Si的四個(gè)代換中的一個(gè)。6比特輸入中，中間4位用來選擇列。行和列選定后，得到其交叉位置的十進(jìn)制數(shù)，將這個(gè)數(shù)表示為4位二進(jìn)制數(shù)即得這一S盒的輸出。例如，S1的輸入為011001，行選為01（即第1行），列選為1100（即第12列），行列交叉位置的數(shù)為9，其4位二進(jìn)制表示為1001，所以S1的輸出為1001。S盒的每一行定義了一個(gè)可逆代換，圖3-2（在前一節(jié)）表示S1第0行所定義的代換。3.2.1DES描述2.輪結(jié)構(gòu)第三章分組密碼3.2.1DES描述3.密鑰的產(chǎn)生再看圖3-5和圖3-6，輸入算法的56比特密鑰首先經(jīng)過一個(gè)置換運(yùn)算，該置換由表3-4（a）給出，然后將置換后的56比特分為各為28比特的左、右兩半，分別記為C0和D0。在第i輪分別對(duì)Ci-1和Di-1進(jìn)行左循環(huán)移位，所移位數(shù)由表3-4（c）給出。

移位后的結(jié)果做為求下一輪子密鑰的輸入，同時(shí)也作為置換選擇2的輸入。通過置換選擇2產(chǎn)生的48比特的，即為本輪的子密鑰，作為函數(shù)的輸入。第三章分組密碼3.2.1DES描述3.密鑰的產(chǎn)生第三章分組密碼表3-4 DES密鑰編排中使用的表(a)置換選擇1(b)置換選擇23.2.1DES描述3.密鑰的產(chǎn)生第三章分組密碼表3-4 DES密鑰編排中使用的表（c）左循環(huán)移位位數(shù)4.解密和Feistel密碼一樣，DES的解密和加密使用同一算法，但子密鑰使用的順序相反。3.2.2二重DES第三章分組密碼為了提高DES的安全性，并利用實(shí)現(xiàn)DES的現(xiàn)有軟硬件，可將DES算法在多密鑰下多重使用。圖3-8二重DES3.2.2二重DES第三章分組密碼二重DES是多重使用DES時(shí)最簡單的形式，如圖3-8所示。其中明文為，兩個(gè)加密密鑰為和，密文為：解密時(shí)，以相反順序使用兩個(gè)密鑰：因此，二重DES所用密鑰長度為112比特，強(qiáng)度極大地增加。然而，如果對(duì)任意兩個(gè)密鑰和，能夠找出另一密鑰，使得那么，二重DES以及多重DES都沒有意義，因?yàn)樗鼈兣c56比特密鑰的單重DES等價(jià)。3.2.2二重DES第三章分組密碼但上式對(duì)DES并不成立。將DES加密過程64比特分組到64比特分組的映射看作一個(gè)置換，如果考慮個(gè)所有可能的輸入分組，則密鑰給定后，DES的加密將把每個(gè)輸入分組映射到一個(gè)惟一的輸出分組。否則，如果有兩個(gè)輸入分組被映射到同一分組，則解密過程就無法實(shí)施。對(duì)

個(gè)輸入分組，總映射個(gè)數(shù)為。另一方面，對(duì)每個(gè)不同的密鑰，DES都定義了一個(gè)映射，總映射數(shù)為。因此，可假定用兩個(gè)不同的密鑰兩次使用DES，可得一個(gè)新映射，而且這一新映射不出現(xiàn)在單重DES定義的映射中。3.2.2二重DES第三章分組密碼但對(duì)二重DES有以下一種稱為中途相遇攻擊的攻擊方案，這種攻擊不依賴于DES的任何特性，因而可用于攻擊任何分組密碼。其基本思想如下：

如果有

那么（看圖3-8）

3.2.2二重DES第三章分組密碼如果已知一個(gè)明──密文對(duì)，攻擊的實(shí)施可如下進(jìn)行：首先，用

個(gè)所有可能的對(duì)加密，將加密結(jié)果存入一表并對(duì)表按排序，然后用

個(gè)所有可能的對(duì)解密，在上述表中查找與解密結(jié)果相匹配的項(xiàng)，如果找到，則記下相應(yīng)的和。最后再用一新的明文密文對(duì)檢驗(yàn)上面找到的和

，用和對(duì)兩次加密，若結(jié)果等于，就可確定和是所要找的密鑰。3.2.2二重DES第三章分組密碼對(duì)已知的明文，二重DES能產(chǎn)生

個(gè)可能的密文而可能的密鑰個(gè)數(shù)為

，所以平均來說，對(duì)一個(gè)已知的明文，有個(gè)密鑰可產(chǎn)生已知的密文。而再經(jīng)過另外一對(duì)明文密文的檢驗(yàn)，誤報(bào)率將下降到。所以在實(shí)施中途相遇攻擊時(shí)，如果已知兩個(gè)明文密文對(duì)，則找到正確密鑰的概率為。3.2.2兩個(gè)密鑰的三重DES第三章分組密碼抵抗中途相遇攻擊的一種方法是使用3個(gè)不同的密鑰做3次加密，從而可使已知明文攻擊的代價(jià)增加到

。然而，這樣又會(huì)使密鑰長度增加到比特，因而過于笨重。一種實(shí)用的方法是僅使用兩個(gè)密鑰做三次加密，實(shí)現(xiàn)方式為加密──解密──加密，簡記為EDE(Encrypt-Decrypt-Encrypt)，看圖3-9，即：第2步解密的目的僅在于使得用戶可對(duì)一重DES加密的數(shù)據(jù)解密。此方案已在密鑰管理標(biāo)準(zhǔn)ANSX.917和ISO8732中被采用。3.2.2兩個(gè)密鑰的三重DES第三章分組密碼圖3-9 兩個(gè)密鑰的三重DES3.2.3三個(gè)密鑰的三重DES第三章分組密碼三個(gè)密鑰的三重DES密鑰長度為168比特，加密方式為

令或，則變?yōu)橐恢谼ES。 三個(gè)密鑰的三重DES已在因特網(wǎng)的許多應(yīng)用（如PGP和S/MIME）中被采用。3.3差分密碼分析與線性密碼分析3.3.1差分密碼分析3.3.2線性密碼分析第三章分組密碼3.3.1差分密碼分析第三章分組密碼差分密碼分析是迄今已知的攻擊迭代密碼最有效的方法之一，其基本思想是：通過分析明文對(duì)的差值對(duì)密文對(duì)的差值的影響來恢復(fù)某些密鑰比特。對(duì)分組長度為的輪迭代密碼，兩個(gè)比特串和的差分定義為：其中表示比特串集上的一個(gè)特定群運(yùn)算，表示

在此群中的逆元。由加密對(duì)可得差分序列：其中和是明文對(duì)，和是第輪的輸出，它們同時(shí)也是第+1輪的輸入。第輪的子密鑰記為，是輪函數(shù)，且。3.3.1差分密碼分析第三章分組密碼定義3-1-輪特征(r-roundcharacteristic)是一個(gè)差分序列：其中是明文對(duì)和的差分，是第輪輸出

和的差分。定義3-2在-輪特征=中，定義=即表示在輸入差分為的條件下，輪函數(shù)的輸出差分為的概率。3.3.1差分密碼分析第三章分組密碼定義3-3-輪特征=的概率定義為：對(duì)-輪迭代密碼的差分密碼分析可綜述為如下的算法。算法：找出一個(gè)（-1）-輪特征=，使得它的概率達(dá)到最大或幾乎最大。3.3.1差分密碼分析第三章分組密碼均勻隨機(jī)地選擇明文并計(jì)算，使得和的差分為，找出和在實(shí)際密鑰加密下所得的密文和。若最后一輪的子密鑰（或的部分比特）有個(gè)可能值，設(shè)置相應(yīng)的個(gè)計(jì)數(shù)器；用每個(gè)解密密文和，得到和，如果和的差分是，則給相應(yīng)的計(jì)數(shù)器加1。

重復(fù)步驟上一步，直到一個(gè)或幾個(gè)計(jì)數(shù)器的值明顯高于其它計(jì)數(shù)器的值，輸出它們所對(duì)應(yīng)的子密鑰（或部分比特）。3.3.1差分密碼分析第三章分組密碼一種攻擊的復(fù)雜度可以分為兩部分：數(shù)據(jù)復(fù)雜度和處理復(fù)雜度。數(shù)據(jù)復(fù)雜度是實(shí)施該攻擊所需輸入的數(shù)據(jù)量；而處理復(fù)雜度是處理這些數(shù)據(jù)所需的計(jì)算量。這兩部分的主要部分通常被用來刻畫該攻擊的復(fù)雜度。差分密碼分析的數(shù)據(jù)復(fù)雜度兩倍于成對(duì)加密所需的選擇明文對(duì)（，）的個(gè)數(shù)。差分密碼分析的處理復(fù)雜度是從找出子密鑰（或的部分比特）的計(jì)算量，它實(shí)際上與無關(guān)，而且由于輪函數(shù)是弱的，所以此計(jì)算量在大多數(shù)情況下相對(duì)較小。因此，差分密碼分析的復(fù)雜度取決于它的數(shù)據(jù)復(fù)雜度。3.3.2線性密碼分析第三章分組密碼線性密碼分析是對(duì)迭代密碼的一種已知明文攻擊，它利用的是密碼算法中的“不平衡（有效）的線性逼近”。設(shè)明文分組長度和密文分組長度都為比特，密鑰分組長度為比特。記明文分組為，密文分組為，密鑰分組為。定義。線性密碼分析的目標(biāo)就是找出以下形式的有效線性方程：

其中。3.3.2線性密碼分析第三章分組密碼如果方程成立的概率，則稱該方程是有效的線性逼近。如果是最大的，則稱該方程是最有效的線性逼近。設(shè)表示明文數(shù)，是使方程左邊為0的明文數(shù)。如果，則令：3.3.2線性密碼分析第三章分組密碼如果，則令：從而可得關(guān)于密鑰比特的一個(gè)線性方程。對(duì)不同的明文密文對(duì)重復(fù)以上過程，可得關(guān)于密鑰的一組線性方程，從而確定出密鑰比特。3.3.2線性密碼分析第三章分組密碼研究表明，當(dāng)充分小時(shí)，攻擊成功的概率是這一概率只依賴于，并隨著或的增加而增加。3.3.2線性密碼分析第三章分組密碼

如何對(duì)差分密碼分析和線性密碼分析進(jìn)行改進(jìn)，降低它們的復(fù)雜度仍是現(xiàn)在理論研究的熱點(diǎn)，目前已推出了很多改進(jìn)方法，例如：高階差分密碼分析、截段差分密碼分析（TruncatedDifferentialCryptanalysis）、不可能差分密碼分析、多重線性密碼分析、非線性密碼分析、劃分密碼分析和差分──線性密碼分析。針對(duì)密鑰編排算法的相關(guān)密鑰攻擊、基于Lagrange插值公式的插值攻擊及基于密碼器件的能量分析(PowerAnalysis)。另外還有錯(cuò)誤攻擊、時(shí)間攻擊、“Square”攻擊和Davies攻擊等。3.4分組密碼的運(yùn)行模式3.4.1電碼本模式3.4.2密碼分組鏈接模式3.4.3密碼反饋模式3.4.4輸出反饋模式第三章分組密碼3.4.1電碼本模式（ECB）第三章分組密碼ECB(ElectronicCodebook)模式是最簡單的運(yùn)行模式，它一次對(duì)一個(gè)64比特長的明文分組加密，而且每次的加密密鑰都相同，如圖3-10所示。當(dāng)密鑰取定時(shí)，對(duì)明文的每一個(gè)分組，都有一個(gè)惟一的密文與之對(duì)應(yīng)。因此我們可以形象地認(rèn)為有一個(gè)非常大的電碼本，對(duì)任意一個(gè)可能的明文分組，電碼本中都有一項(xiàng)對(duì)應(yīng)于它的密文。如果消息長于64比特，則將其分為長為64比特的分組，最后一個(gè)分組如果不夠64比特，則需要填充。解密過程也是一次對(duì)一個(gè)分組解密，而且每次解密都使用同一密鑰。圖3-10中，明文是由分組長為64比特的分組序列構(gòu)成，相應(yīng)的密文分組序列是。3.4.1電碼本模式（ECB）第三章分組密碼ECB在用于短數(shù)據(jù)（如加密密鑰）時(shí)非常理想，因此如果我們需要安全地傳遞DES密鑰，ECB是最合適的模式。圖3-10 ECB模式示意圖3.4.1電碼本模式（ECB）第三章分組密碼ECB的最大特性是同一明文分組在消息中重復(fù)出現(xiàn)的話，產(chǎn)生的密文分組也相同。ECB用于長消息時(shí)可能不夠安全，如果消息有固定結(jié)構(gòu)，密碼分析者有可能找出這種關(guān)系。例如，如果已知消息總是以某個(gè)預(yù)定義字段開始，那么分析者就可能得到很多明文密文對(duì)。如果消息有重復(fù)的元素而重復(fù)的周期是64的倍數(shù)，那么密碼分析者就能夠識(shí)別這些元素。以上這些特性都有助于密碼分析者，有可能為其提供對(duì)分組的代換或重排的機(jī)會(huì)。3.4.2密碼分組鏈接模式（ECB）第三章分組密碼為了解決ECB的安全缺陷，可以讓重復(fù)的明文分組產(chǎn)生不同的密文分組，CBC（CipherBlockChaining）模式就可滿足這一要求。圖3-11是CBC模式示意圖，它一次對(duì)一個(gè)明文分組加密，每次加密使用同一密鑰,加密算法的輸入是當(dāng)前明文分組和前一次密文分組的異或，因此加密算法的輸入不會(huì)顯示出與這次的明文分組之間的固定關(guān)系，所以重復(fù)的明文分組不會(huì)在密文中暴露出這種重復(fù)關(guān)系。3.4.2密碼分組鏈接模式（ECB）第三章分組密碼圖3-11 CBC模式示意圖3.4.2密碼分組鏈接模式（ECB）第三章分組密碼解密時(shí)，每一個(gè)密文分組被解密后，再與前一個(gè)密文分組異或，即：（設(shè)）在產(chǎn)生第一個(gè)密文分組時(shí)，需要有一個(gè)初始向量IV與第一個(gè)明文分組異或。解密時(shí)，IV和解密算法對(duì)第一個(gè)密文分組的輸出進(jìn)行異或以恢復(fù)第一個(gè)明文分組。3.4.2密碼分組鏈接模式（ECB）第三章分組密碼IV對(duì)于收發(fā)雙方都應(yīng)是已知的，為使安全性最高，IV應(yīng)象密鑰一樣被保護(hù)，可使用ECB加密模式來發(fā)送IV。保護(hù)IV的原因如下：如果敵手能欺騙接收方使用不同的IV值，敵手就能夠在明文的第一個(gè)分組中插入自己選擇的比特值，這是因?yàn)椋河帽硎?4比特分組的第個(gè)比特，那么

，由異或的性質(zhì)得：其中撇號(hào)表示比特補(bǔ)。上式意味著如果敵手篡改IV中的某些比特，則接收方收到的中相應(yīng)的比特也發(fā)生變化。3.4.3密碼反饋模式（CFB）第三章分組密碼DES是分組長為64比特的分組密碼，但利用CFB（CipherFeedback）模式或OFB模式可將DES轉(zhuǎn)換為流密碼。流密碼不需要對(duì)消息填充，而且運(yùn)行是實(shí)時(shí)的。因此如果傳送字母流，可使用流密碼對(duì)每個(gè)字母直接加密并傳送。流密碼具有密文和明文一樣長這一性質(zhì)，因此，如果需要發(fā)送的每個(gè)字符長為8比特，就應(yīng)使用8比特密鑰來加密每個(gè)字符。如果密鑰長超過8比特，則造成浪費(fèi)。3.4.3密碼反饋模式（CFB）第三章分組密碼圖3-12是CFB模式示意圖，設(shè)傳送的每個(gè)單元（如一個(gè)字符）是比特長，通常取，與CBC模式一樣，明文單元被鏈接在一起，使得密文是前面所有明文的函數(shù)。加密時(shí)，加密算法的輸入是64比特移位寄存器，其初值為某個(gè)初始向量IV。加密算法輸出的最左（最高有效位）比特與明文的第一個(gè)單元異或，產(chǎn)生出密文的第一個(gè)單元，并傳送該單元。然后將移位寄存器的內(nèi)容左移位并將送入移位寄存器最右邊（最低有效位）位。這一過程繼續(xù)到明文的所有單元都被加密為止解密時(shí)，將收到的密文單元與加密函數(shù)的輸出進(jìn)行異或。3.4.3密碼反饋模式（CFB）第三章分組密碼圖3-12 CFB模式示意圖（a）加密3.4.3密碼反饋模式（CFB）第三章分組密碼圖3-12 CFB模式示意圖（b）解密3.4.4輸出反饋模式（OFB）第三章分組密碼OFB（OutputFeedback）模式的結(jié)構(gòu)類似于CFB，看圖3-13。不同之處如下：OFB模式是將加密算法的輸出反饋到移位寄存器，而CFB模式中是將密文單元反饋到移位寄存器。OFB模式的優(yōu)點(diǎn)是傳輸過程中的比特錯(cuò)誤不會(huì)被傳播。例如中出現(xiàn)一比特錯(cuò)誤，在解密結(jié)果中只有受到影響，以后各明文單元?jiǎng)t不受影響。而在CFB中，也作為移位寄存器的輸入，因此它的一比特錯(cuò)誤會(huì)影響解密結(jié)果中各明文單元的值。3.4.4輸出反饋模式（OFB）第三章分組密碼圖3-13 OFB模式示意圖(a加密）3.4.4輸出反饋模式（OFB）第三章分組密碼圖3-13 OFB模式示意圖(b解密）3.4.4輸出反饋模式（OFB）第三章分組密碼OFB的缺點(diǎn)是它比CFB模式更易受到對(duì)消息流的篡改攻擊，比如在密文中取1比特的補(bǔ)，那么在恢復(fù)的明文中相應(yīng)位置的比特也為原比特的補(bǔ)。因此使得敵手有可能通過對(duì)消息校驗(yàn)部分的篡改和對(duì)數(shù)據(jù)部分的篡改，而以糾錯(cuò)碼不能檢測的方式篡改密文。3.5IDEA3.5.1設(shè)計(jì)原理3.5.2加密過程第三章分組密碼第三章分組密碼3.5.1設(shè)計(jì)原理IDEA（InternationalDataEncryptionAlgorithm，國際數(shù)據(jù)加密算法）由來學(xué)嘉(X.J.Lai)和J.L.Massey提出，其第一版于1990年公布，當(dāng)時(shí)稱為PES（ProposedEncryptionStandard，建議加密標(biāo)準(zhǔn)）。1991年，在Biham和Shamir提出差分密碼分析之后，設(shè)計(jì)者推出了改進(jìn)算法IPES，即改進(jìn)型建議加密標(biāo)準(zhǔn)。1992年，設(shè)計(jì)者又將IPES改名為IDEA。這是近年來提出的各種分組密碼中一個(gè)很成功的方案，已在PGP中采用。3.5.1設(shè)計(jì)原理第三章分組密碼算法中明文和密文分組長度都是64比特，密鑰長128比特。其設(shè)計(jì)原理可從強(qiáng)度和實(shí)現(xiàn)兩方面考慮。算法的強(qiáng)度主要是通過有效的混淆和擴(kuò)散特性而得以保證?；煜峭ㄟ^使用以下三種運(yùn)算而獲得，三種運(yùn)算都有兩個(gè)16比特的輸入和一個(gè)16比特的輸出：逐比特異或，表示為；模（即65536）整數(shù)加法，表示為+，其輸入和輸出作為16位無符號(hào)整數(shù)處理。模+1（即65537）整數(shù)乘法，表示為，其輸入、輸出中除16位全為0作為

處理外，其余都作為16位無符號(hào)整數(shù)處理。3.5.1設(shè)計(jì)原理第三章分組密碼表3-6給出了操作數(shù)為2比特長時(shí)三種運(yùn)算的運(yùn)算表。表3-6 IDEA中的三種運(yùn)算（操作數(shù)為2比特長）XYX

+

YXYXY0000000000100000001010000100010101110000111110110100001000010101100100001101110110111000111010000101110……..………….………….3.5.1設(shè)計(jì)原理第三章分組密碼在以下意義下，三種運(yùn)算是不兼容的：三個(gè)運(yùn)算中任意兩個(gè)都不滿足分配律，例如：三個(gè)運(yùn)算中任意兩個(gè)都不滿足結(jié)合律，例如：a+（bc）!=

(a+b)(a+c)a+（bc）!=

(a+b)c三種運(yùn)算結(jié)合起來使用可對(duì)算法的輸入提供復(fù)雜的變換，從而使得對(duì)IDEA的密碼分析比對(duì)僅使用異或運(yùn)算的DES更為困難。3.5.1設(shè)計(jì)原理第三章分組密碼算法中擴(kuò)散是由稱作乘加（MA-Multiplication/Addition）結(jié)構(gòu)（看圖3-14）的基本單元實(shí)現(xiàn)的。該結(jié)構(gòu)的輸入是兩個(gè)16比特的子段和兩個(gè)16比特的子密鑰，輸出也為兩個(gè)16比特的子段。這一結(jié)構(gòu)在算法中重復(fù)使用了8次，獲得了非常有效的擴(kuò)散效果。3.5.1設(shè)計(jì)原理第三章分組密碼圖3-14 MA結(jié)構(gòu)3.5.2加密過程第三章分組密碼加密過程（如圖3-15所示）由連續(xù)的8輪迭代和一個(gè)輸出變換組成，算法將64比特的明文分組分成4個(gè)16比特的子段，每輪迭代以4個(gè)16比特的子段作為輸入，輸出也為4個(gè)16比特的子段。最后的輸出變換也產(chǎn)生4個(gè)16比特的子段，鏈接起來后形成64比特的密文分組。每輪迭代還需使用6個(gè)16比特的子密鑰，最后的輸出變換需使用4個(gè)16比特的子密鑰，所以子密鑰總數(shù)為52。圖的右部分表示由初始的128比特密鑰產(chǎn)生52個(gè)子密鑰的子密鑰產(chǎn)生器。3.5.2加密過程第三章分組密碼圖3-15 IDEA的加密框圖3.5.2加密過程第三章分組密碼圖3-16是IDEA第一輪的結(jié)構(gòu)示意圖，以后各輪也都是這種結(jié)構(gòu)，但所用的子密鑰和輪輸入不同。從結(jié)構(gòu)圖可見，IDEA不是傳統(tǒng)的Feistel密碼結(jié)構(gòu)。每輪開始時(shí)有一個(gè)變換，該變換的輸入是4個(gè)子段和4個(gè)子密鑰，變換中的運(yùn)算是兩個(gè)乘法和兩個(gè)加法，輸出的4個(gè)子段經(jīng)過異或運(yùn)算形成了兩個(gè)16比特的子段作為MA結(jié)構(gòu)的輸入。MA結(jié)構(gòu)也有兩個(gè)輸入的子密鑰，輸出是兩個(gè)16比特的子段。3.5.2加密過程第三章分組密碼圖3-16 IDEA第一輪的輪結(jié)構(gòu)3.5.2加密過程第三章分組密碼最后，變換的4個(gè)輸出子段和MA結(jié)構(gòu)的兩個(gè)輸出子段經(jīng)過異或運(yùn)算產(chǎn)生這一輪的4個(gè)輸出子段。注意，由產(chǎn)生的輸出子段和由產(chǎn)生的輸出子段交換位置后形成和，目的在于進(jìn)一步增加混淆效果，使得算法更易抵抗差分密碼分析。算法的第九步是一個(gè)輸出變換，如圖3-17所示。它的結(jié)構(gòu)和每一輪開始的變換結(jié)構(gòu)一樣，不同之處在于輸出變換的第二個(gè)和第三個(gè)輸入首先交換了位置，目的在于撤消第八輪輸出中兩個(gè)子段的交換。還需注意，第九步僅需4個(gè)子密鑰而前面8輪中每輪需要6個(gè)子密鑰。3.5.2加密過程第三章分組密碼子密鑰的產(chǎn)生加密過程中52個(gè)16比特的子密鑰是由128比特的加密密鑰按如下方式產(chǎn)生的：前8個(gè)子密鑰直接從加密密鑰中取，即取前16比特（最高有效位），取下面的16比特，等等。然后加密密鑰循環(huán)左移25位，再取下面8個(gè)子密鑰，取法與的取法相同。這一過程重復(fù)下去，直到52子密鑰都被產(chǎn)生為止。解密過程第三章分組密碼解密過程和加密過程基本相同，但子密鑰的選取不同。解密子密鑰是由加密子密鑰按如下方式得到（將加密過程最后一步的輸出變換當(dāng)作第九輪）：第輪解密的前4個(gè)子密鑰由加密過程第輪的前4個(gè)子密鑰得出：其中第1和第4個(gè)解密子密鑰取為相應(yīng)的第1和第4個(gè)加密子密鑰的模

+1乘法逆元，第2和第3個(gè)子密鑰的取法為：當(dāng)輪數(shù)時(shí)，取為相應(yīng)的第3個(gè)和第2個(gè)加密子密鑰的模

加法逆元。和9時(shí)，取為相應(yīng)的第2個(gè)和第3個(gè)加密子密鑰的模

加法逆元。解密過程第三章分組密碼第輪解密的后兩個(gè)子密鑰等于加密過程第輪的后兩個(gè)子密鑰。表3-7是對(duì)以上關(guān)系的總結(jié)。其中的模+1乘法逆元為，滿足：因+1是一素?cái)?shù)，所以每一個(gè)不大于

的非0整數(shù)都有一個(gè)惟一的模+1乘法逆元。的模

加法逆元為，滿足：+解密過程第三章分組密碼表3-7 IDEA加密、解密子密鑰表解密過程第三章分組密碼下面驗(yàn)證解密過程的確得到正確的結(jié)果。圖3-18中左邊為加密過程，由上至下，右邊為解密過程，由下至上。將每一輪進(jìn)一步分為兩步，第一步是變換，其余部分作為第二步，稱為子加密。從下往上考慮。對(duì)加密過程的最后一個(gè)輸出變換，以下關(guān)系成立：Y1=W81

Z49

Y2=W83

Z50Y3=W82

Z51

Y4=W84

Z52++解密過程第三章分組密碼解密過程中第1輪的第1步產(chǎn)生以下關(guān)系：

J11=Y1

U1

J12=Y2

U2

J13=Y3

U3

J14=Y4

U4++將解密子密鑰由加密子密鑰表達(dá)并將代入以下關(guān)系，有：解密過程第三章分組密碼可見解密過程第1輪第1步的輸出等于加密過程最后一步輸入中第2個(gè)子段和第3個(gè)子段交換后的值。從圖3-16，可得以下關(guān)系：解密過程第三章分組密碼圖3-18 IDEA加密和解密框圖其中是MA結(jié)構(gòu)輸入為和時(shí)的右邊輸出

是左邊輸出。則：V11=J11+MAR（J11+J13，J12+J14）=W81+MAR（W81+W82，W83+W84）=I81+MAR（I81+I83，I82+I84）+MAR[I81+MAR（I81+I83，I82+I84）+I83+MAR（I81+I83，I82+I84），I82+MAL（I81+I83，I82+I84）+I84+MAL（I81+I83，I82+I84）]=I81+MAR（I81+I83，I82+I84）+MAR（I81+I83，I82+I84）=I81解密過程類似地，可有：V12=I83

V13=I82

V14=I84第三章分組密碼解密過程第三章分組密碼所以解密過程第1輪第2步的輸出等于加密過程倒數(shù)第2步輸入中第2個(gè)子段和第3個(gè)子段交換后的值。同理可證圖3-18中每步都有上述類似關(guān)系，這種關(guān)系一直到V81=I11

V82=I13

V84=I14

V83=I12

即除第2個(gè)子段和第3個(gè)子段交換位置外，解密過程的輸出變換與加密過程第1輪第1步的變換完全相同。所以最后得出整個(gè)解密過程的輸出等于整個(gè)加密過程的輸入。3.6AES算法-3.6.1的數(shù)學(xué)基礎(chǔ)和設(shè)計(jì)思想3.6.2算法說明第三章分組密碼3.6.1的數(shù)學(xué)基礎(chǔ)和設(shè)計(jì)思想第三章分組密碼有限域GF(28)有限域中的元素可以用多種不同的方式表示。對(duì)于任意素?cái)?shù)的方冪，都有惟一的一個(gè)有限域，因此GF()的所有表示是同構(gòu)的，但不同的表示方法會(huì)影響到GF()上運(yùn)算的復(fù)雜度，本算法采用傳統(tǒng)的多項(xiàng)式表示法。將構(gòu)成的字節(jié)看成系數(shù)在中的多項(xiàng)式例如：十六進(jìn)制數(shù)‘57’對(duì)應(yīng)的二進(jìn)制為01010111，看成一個(gè)字節(jié)，對(duì)應(yīng)的多項(xiàng)式為。3.6.1的數(shù)學(xué)基礎(chǔ)和設(shè)計(jì)思想第三章分組密碼在多項(xiàng)式表示中，GF()上兩個(gè)元素的和仍然是一個(gè)次數(shù)不超過7的多項(xiàng)式，其系數(shù)等于兩個(gè)元素對(duì)應(yīng)系數(shù)的模2加（比特異或）。例如：‘57’+‘83’=‘D4’，用多項(xiàng)式表示為(x6+x4+x2+x+1)+(x7+x+1)=x7+x6+x4+x2用二進(jìn)制表示為01010111+10000011=11010100

由于每個(gè)元素的加法逆元等于自己，所以減法和加法相同。3.6.1的數(shù)學(xué)基礎(chǔ)和設(shè)計(jì)思想第三章分組密碼

要計(jì)算GF(28)上的乘法，必須先確定一個(gè)GF(2)上的8次不可約多項(xiàng)式；GF(28)上兩個(gè)元素的乘積就是這兩個(gè)多項(xiàng)式的模乘（以這個(gè)8次不可約多項(xiàng)式為模）。在Rijndael密碼中，這個(gè)8次不可約多項(xiàng)式確定為m(x)=x8+x4+x3+x+1它的十六進(jìn)制表示為‘11B’。

例如：‘57’?‘83’=‘C1’可表示為以下的多項(xiàng)式乘法(x6+x4+x2+x+1)?(x7+x+1)=x7+x6+1(modm(x))3.6.1的數(shù)學(xué)基礎(chǔ)和設(shè)計(jì)思想第三章分組密碼以上定義的乘法滿足交換律，且有單位元‘01’。另外，對(duì)任何次數(shù)小于8的多項(xiàng)式b(x)，可用推廣的歐幾里德算法得：b(x)a(x)+m(x)c(x)=1即a(x)?b(x)=1modm(x)，因此a(x)是b(x)的乘法逆元。再者，乘法還滿足分配律：所以，256個(gè)字節(jié)值構(gòu)成的集合，在以上定義的加法和乘法運(yùn)算下，有有限域GF(28)的結(jié)構(gòu)。3.6.1的數(shù)學(xué)基礎(chǔ)和設(shè)計(jì)思想第三章分組密碼GF(28)上還定義了一個(gè)運(yùn)算，稱之為x乘法，其定義為：x?b(x)=b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x(modm(x))如果=0，求模結(jié)果不變，否則為乘積結(jié)果減去m(x)，即求乘積結(jié)果與m(x)的異或。由此得出x（十六進(jìn)制‘02’）乘b(x)可以先對(duì)b(x)在字節(jié)內(nèi)左移一位（最后一位補(bǔ)0），若=1則再與‘1B’（其二進(jìn)制為00011011）做逐比特異或來實(shí)現(xiàn)，該運(yùn)算記b=xtime(a)。在專用芯片中，xtime只需4個(gè)異或。x的冪乘運(yùn)算可以重復(fù)應(yīng)用xtime來實(shí)現(xiàn)。而任意常數(shù)乘法可以通過對(duì)中間結(jié)果相加實(shí)現(xiàn)。3.6.1的數(shù)學(xué)基礎(chǔ)和設(shè)計(jì)思想第三章分組密碼例如：‘57’?‘13’可如下實(shí)現(xiàn)：

‘57’?‘02’=xtime(57)=‘AE’；

‘57’?‘04’=xtime(AE)=‘47’；

‘57’?‘08’=xtime(47)=‘8E’；

‘57’?‘10’=xtime(8E)=‘07’；‘57’?‘13’=‘57’?（‘01’⊕‘02’⊕‘10’）=‘57’⊕‘AE’⊕‘07’=‘FE’。3.6.1的數(shù)學(xué)基礎(chǔ)和設(shè)計(jì)思想第三章分組密碼系數(shù)在GF(28)上的多項(xiàng)式4個(gè)字節(jié)構(gòu)成的向量可以表示為系數(shù)在GF(28)上的次數(shù)小于4的多項(xiàng)式。多項(xiàng)式的加法就是對(duì)應(yīng)系數(shù)相加；換句話說，多項(xiàng)式的加法就是4字節(jié)向量的逐比特異或。規(guī)定多項(xiàng)式的乘法運(yùn)算必須要取模

，這樣使得次數(shù)小于4的多項(xiàng)式的乘積仍然是一個(gè)次數(shù)小于4的多項(xiàng)式，將多項(xiàng)式的模乘運(yùn)算記為。設(shè)

，由于

，所以M(x)=x4+1a(x)=a3x3+a2x2+a1x+a0b(x)=b3x3+b2x2+b1x+b0xjmod

（x4+1）=xjmod43.6.1的數(shù)學(xué)基礎(chǔ)和設(shè)計(jì)思想第三章分組密碼c0=a0b0⊕a3b1⊕a2b2⊕a1b3；c1=a1b0⊕a0b1⊕a3b2⊕a2b3；c2=a2b0⊕a1b1⊕a0b2⊕a3b3；c3=a3b0⊕a2b1⊕a1b2⊕a0b3?？蓪⑸鲜鲇?jì)算表示為3.6.1的數(shù)學(xué)基礎(chǔ)和設(shè)計(jì)思想第三章分組密碼

注意到M(x)不是GF(28)上的不可約多項(xiàng)式（甚至也不是GF(2)上的不可約多項(xiàng)式），因此非0多項(xiàng)式的這種乘法不是群運(yùn)算。不過在Rijndael密碼中，對(duì)多項(xiàng)式b(x)，這種乘法運(yùn)算只限于乘一個(gè)固定的有逆元的多項(xiàng)式a(x)=a3x3+a2x2+a1x+a0。我們有如下的定理。定理3-1系數(shù)在GF(28)上的多項(xiàng)式是模x4+1可逆的，當(dāng)且僅當(dāng)矩陣a3x3+a2x2+a1x+a0在GF(28)上可逆。3.6.1的數(shù)學(xué)基礎(chǔ)和設(shè)計(jì)思想第三章分組密碼證明a3x3+a2x2+a1x+a0是模x4+1可逆的，當(dāng)且僅當(dāng)存在多項(xiàng)式h3x3+h2x2+h1x+h0使得(a3x3+a2x2+a1x+a0)(h3x3+h2x2+h1x+h0)=1(modx4+1)因此有(a3x3+a2x2+a1x+a0)(h2x3+h1x2+h0x+h3)=x(modx4+1)(a3x3+a2x2+a1x+a0)(h1x3+h0x2+h3x+h2)=x2(modx4+1)(a3x3+a2x2+a1x+a0)(h0x3+h3x2+h2x+h1)=x3(modx4+1)；將以上關(guān)系寫成矩陣形式即得（定理3-1證畢）3.6.1的數(shù)學(xué)基礎(chǔ)和設(shè)計(jì)思想第三章分組密碼c(x)=xb(x)定義為x與b(x)的模x4+1乘法,即其矩陣表示中，除a1=‘01’

外，其它所有ai=‘00’，即因此，x（或x的冪）模乘多項(xiàng)式相當(dāng)于對(duì)字節(jié)構(gòu)成的向量進(jìn)行字節(jié)循環(huán)移位。3.6.1的數(shù)學(xué)基礎(chǔ)和設(shè)計(jì)思想第三章分組密碼設(shè)計(jì)思想Rijndael密碼的設(shè)計(jì)力求滿足以下3條標(biāo)準(zhǔn)：抵抗所有已知的攻擊。在多個(gè)平臺(tái)上速度快，編碼緊湊。設(shè)計(jì)簡單。當(dāng)前的大多數(shù)分組密碼，其輪函數(shù)是Feistel結(jié)構(gòu)，即將中間狀態(tài)的部分比特不加改變地簡單放置到其它位置。Rijndael沒有這種結(jié)構(gòu)，其輪函數(shù)是由三個(gè)不同的可逆均勻變換組成的，稱它們?yōu)槿齻€(gè)“層”。所謂“均勻變換”是指狀態(tài)的每個(gè)比特都是用類似的方法進(jìn)行處理的。不同層的特定選擇大部分是建立在“寬軌跡策略”的應(yīng)用基礎(chǔ)上的；簡單地說，“寬軌跡策略”就是提供抗線性密碼分析和差分密碼分析能力的一種設(shè)計(jì)。3.6.1的數(shù)學(xué)基礎(chǔ)和設(shè)計(jì)思想第三章分組密碼設(shè)計(jì)思想為實(shí)現(xiàn)寬軌跡策略，輪函數(shù)三個(gè)層中的每一層都有它自己的功能：線性混合層：確保多輪之上的高度擴(kuò)散。非線性層：將具有最優(yōu)的“最壞情況非線性特性”的S盒并行使用。密鑰加層：單輪子密鑰簡單地異或到中間狀態(tài)上，實(shí)現(xiàn)一次性掩蓋。3.6.1的數(shù)學(xué)基礎(chǔ)和設(shè)計(jì)思想第三章分組密碼設(shè)計(jì)思想

在第一輪之前，用了一個(gè)初始密鑰加層，其目的是在不知道密鑰的情況下，對(duì)最后一個(gè)密鑰加層以后的任一層（或者是當(dāng)進(jìn)行已知明文攻擊時(shí)，對(duì)第一個(gè)密鑰加層以前的任一層）可簡單地剝?nèi)ィ虼顺跏济荑€加層對(duì)密碼的安全性無任何意義。許多密碼的設(shè)計(jì)中都在輪變換之前和之后用了密鑰加層，如IDEA、SAFER和Blowfish。

為了使加密算法和解密算法在結(jié)構(gòu)上更加接近，最后一輪的線性混合層與前面各輪的線性混合層不同，這類似于DES的最后一輪不做左右交換一樣?？梢宰C明這種設(shè)計(jì)不以任何方式提高或降低該密碼的安全性。3.6.2算法說明第三章分組密碼狀態(tài)、種子密鑰和輪數(shù)

類似于明文分組和密文分組，算法的中間結(jié)果也須分組，稱算法中間結(jié)果的分組為狀態(tài)，所有的操作都在狀態(tài)上進(jìn)行。狀態(tài)可以用以字節(jié)為元素的矩陣陣列表示，該陣列有4行，列數(shù)記為Nb，Nb等于分組長度除以32。

種子密鑰類似地用一個(gè)以字節(jié)為元素的矩陣陣列表示，該陣列有4行，列數(shù)記為Nk，Nk等于分組長度除以32。表3-8是Nb=6的狀態(tài)和Nk=4的種子密鑰的矩陣陣列表示。3.6.2算法說明第三章分組密碼表3-8Nb=6的狀態(tài)和Nk=4的種子密鑰

有時(shí)可將這些分組當(dāng)作一維數(shù)組，其每一元素是上述陣列表示中的4字節(jié)元素構(gòu)成的列向量，數(shù)組唱的可為4、6、8，數(shù)組元素下標(biāo)的范圍分別是0~3、0~5和0~7。4字節(jié)元素構(gòu)成的列向量有時(shí)也稱為字。3.6.2算法說明第三章分組密碼

算法的輸入和輸出被看成是由8比特字節(jié)構(gòu)成的一維數(shù)組，其元素下標(biāo)的范圍是0~（4Nb-1），因此輸入和輸出以字節(jié)為單位的分組長度分別是16、24和32，其元素下標(biāo)的范圍分別是0~15、0~23和0~31。輸入的種子密鑰也看成是由8比特字節(jié)構(gòu)成的一維數(shù)組，其元素下標(biāo)的范圍是0~（4Nk-1），因此種子密鑰以字節(jié)為單位的分組長度也分別是16、24和32，其元素下標(biāo)的范圍分別是0~15、0~23和0~31。3.6.2算法說明第三章分組密碼

算法的輸入（包括最初的明文輸入和中間過程的輪輸入）以字節(jié)為單位按a00a10a20a30a01a11a21a31…的順序放置到狀態(tài)陣列中。同理，種子密鑰以字節(jié)為單位按k00k10k20k30k01k11k21k31…的順序放置到種子密鑰陣列中。而輸出（包括中間過程的輪輸出和最后的密文輸出），也是以字節(jié)為單位按相同的順序從狀態(tài)陣列中取出。若輸入（或輸出）分組中第n個(gè)元素對(duì)應(yīng)于狀態(tài)陣列的第(i,j)位置上的元素，則n和(i,j)有以下關(guān)系：i=nmod4;j=;

n=i+4j

迭代的輪數(shù)記為Nr，Nr與Nb和Nk有關(guān)，表3-9給出了Nr與Nb和Nk的關(guān)系。3.6.2算法說明第三章分組密碼輪函數(shù)Rijndael的輪函數(shù)由四個(gè)不同的計(jì)算部件組成，分別是：字節(jié)代換（ByteSub）、行移位（ShiftRow）、列混合（MixColumn）、密鑰加（AddRoundKey）。字節(jié)代換（ByteSub）

字節(jié)代換是非線形變換，獨(dú)立地對(duì)狀態(tài)的每個(gè)字節(jié)進(jìn)行。代換表（即S-盒）是可逆的，由以下兩個(gè)變換的合成得到：3.6.2算法說明第三章分組密碼

首先，將字節(jié)看作GF(28)上的元素，映射到自己的乘法逆元，‘00’映射到自己。其次，對(duì)字節(jié)做如下的（GF(2)上的，可逆的）仿射變換：3.6.2算法說明第三章分組密碼上述S-盒對(duì)狀態(tài)的所有字節(jié)所做的變換記為：ByteSub(State)圖3-19是字節(jié)代換示意圖。

ByteSub的逆變換由代換表的逆表做字節(jié)代換，可通過如下兩步實(shí)現(xiàn)，首先進(jìn)行仿射變換的逆變換，再求每一字節(jié)在GF(28)上逆元。3.6.2算法說明第三章分組密碼行移位（ShiftRow）

行移位是將狀態(tài)陣列的各行進(jìn)行循環(huán)移位，不同狀態(tài)行的位移量不同。第0行不移動(dòng)，第一行循環(huán)左移C1個(gè)字節(jié)，第二行循環(huán)左移C2個(gè)字節(jié)，第三行循環(huán)左移C3個(gè)字節(jié)。位移量C1、C2、C3的取值與Nb有關(guān)，由表3-10給出。表3-10對(duì)應(yīng)于不同分組長度的位移量3.6.2算法說明第三章分組密碼

按指定的位移量對(duì)狀態(tài)的行進(jìn)行的行移位運(yùn)算記為:ShiftRow(State)圖3-20行移位示意圖ShiftRow的逆變換是對(duì)狀態(tài)陣列的后三列分別以位移量Nb-C1、Nb-C2、Nb-C3進(jìn)行循環(huán)移位，使得第i行第j列的字節(jié)移位到(j+Nb-Ci)modNb。3.6.2算法說明第三章分組密碼列混合（MixColumn）

在列混合變換中，將狀態(tài)陣列的每個(gè)列視為GF(28)上的多項(xiàng)式，再與一個(gè)固定的多項(xiàng)式c(x)進(jìn)行模x4+1乘法。當(dāng)然要求c(x)是模x4+1可逆的多項(xiàng)式，否則列混合變換就是不可逆的，因而會(huì)使不同的輸入分組對(duì)應(yīng)的輸出分組可能相同。Rijndael的設(shè)計(jì)者給出的c(x)為（系數(shù)用16進(jìn)制數(shù)表示）：c(x)='03'x3+'01'x2+'01'x+'02'c(x)是與x4+1互素的，因此是模x4+1可逆的。列混合運(yùn)算也可寫為矩陣乘法。設(shè)b(x)=c(x)a(x)，則3.6.2算法說明第三章分組密碼

這個(gè)運(yùn)算需要做GF(28)上的乘法，但由于所乘的因子是三個(gè)固定的元素02、03、01，所以這些乘法運(yùn)算仍然是比較簡單的。

對(duì)狀態(tài)State的所有列所做的列混合運(yùn)算記為：MixColumn（State）3.6.2算法說明第三章分組密碼圖3-21列混合運(yùn)算示意圖列混合運(yùn)算的逆運(yùn)算是類似的，即每列都用一個(gè)特定的多項(xiàng)式d(x)相乘。d(x)滿足（'03'x3+'01'x2+'01'x+'02'）d(x)='01'd(x)='0B'x3+'0D'x2+'09'x+'0E'3.6.2算法說明第三章分組密碼密鑰加（AddRoundKey）

密鑰加是將輪密鑰簡單地與狀態(tài)進(jìn)行逐比特異或。輪密鑰由種子密鑰通過密鑰編排算法得到，輪密鑰長度等于分組長度Nb。

狀態(tài)State與輪密鑰RoundKey的密鑰加運(yùn)算表示為：AddRoundKey(State,RoundKey)圖3-22密鑰加運(yùn)算示意圖3.6.2算法說明第三章分組密碼密鑰加運(yùn)算的逆運(yùn)算是自己。

綜上所述，組成Rijndael輪函數(shù)的計(jì)算部件簡潔快速，功能互補(bǔ)。輪函數(shù)的偽C代碼如下：Round(State,RoundKey){ByteSub(State);ShiftRow(State);MixColumn(State);AddRoundKey(State,RoundKey)}

結(jié)尾輪的輪函數(shù)與前面各輪不同，將MixColumn這一步去掉。FinalRound(State,RoundKey){ByteSub(State);ShiftRow(State);AddRoundKey(State,RoundKey)}

在以上偽C代碼記法中，State、RoundKey可用指針類型，“函數(shù)”Round、FinalRound、ByteSub、ShiftRow、MixColumn、AddRoundKey都在指針State、RoundKey所指向的陣列上進(jìn)行運(yùn)算。3.6.2算法說明第三章分組密碼3.6.2算法說明第三章分組密碼密鑰編排

密鑰編排是指從種子密鑰得到輪密鑰的過程，它由密鑰擴(kuò)展和輪密鑰選取兩部分組成。其基本原則如下：

輪密鑰的比特?cái)?shù)等于分組長度乘以輪數(shù)加1；種子密鑰被擴(kuò)展成為擴(kuò)展密鑰；3輪密鑰從擴(kuò)展密鑰中取，其中第1輪輪密鑰取擴(kuò)展密鑰的前Nb個(gè)字，第2輪輪密鑰取接下來的Nb個(gè)字，如此下去。3.6.2算法說明第三章分組密碼密鑰擴(kuò)展

擴(kuò)展密鑰是以4字節(jié)字為元素的一維陣列，表示為W[Nb*(Nr+1)]，其中前Nk個(gè)字取為種子密鑰，以后每個(gè)字按遞歸方式定義。擴(kuò)展算法根據(jù)Nk≤6和Nk>6有所不同。3.6.2算法說明第三章分組密碼當(dāng)Nk≤6時(shí)，擴(kuò)展算法為3.6.2算法說明第三章分組密碼

其中Key[4*Nk]為種子密鑰，看作以字節(jié)為元素的一維陣列。函數(shù)SubByte()返回4字節(jié)字，其中每一個(gè)字節(jié)都是用Rijndael的S盒作用到輸入字對(duì)應(yīng)的字節(jié)得到。函數(shù)RotByte()也返回4字節(jié)字，該字由輸入的字循環(huán)移位得到，即當(dāng)輸入字為(a,b,c,d)時(shí)，輸出字為(b,c,d,a)。

可以看出，擴(kuò)展密鑰的前Nk個(gè)字即為種子密鑰，之后的每個(gè)字W[i]等于前一個(gè)字W[i-1]與Nk個(gè)位置之前的字W[i-Nk]的異或；不過當(dāng)i/Nk為整數(shù)時(shí)，須先將前一個(gè)字W[i-1]經(jīng)過以下一系列的變換：1字節(jié)的循環(huán)移位RotByte→用S盒進(jìn)行變換SubByte→異或輪常數(shù)Rcon[i/Nk]。3.6.2算法說明第三章分組密碼當(dāng)Nk>6時(shí)，擴(kuò)展算法為3.6.2算法說明第三章分組密碼Nk>6與Nk≤6的密鑰擴(kuò)展算法的區(qū)別在于：當(dāng)i為Nk的4的倍數(shù)時(shí)，須先將前一個(gè)字W[i-1]經(jīng)過SubByte變換。

以上兩個(gè)算法中，Rcon[i/Nk]為輪常數(shù)，其值與Nk無關(guān)，定義為（字節(jié)用16進(jìn)制表示，同時(shí)理解為GF(28)上的元素）：Rcon[i]=(RC[i],‘00’,‘00’,‘00’)其中RC[i]是GF(28)中值為xi-1的元素，因此RC[1]=1（即‘01’）RC[i]=x（即‘02’）?RC[i-1]=xi-1輪密鑰選取3.6.2算法說明第三章分組密碼

輪密鑰i（即第i

個(gè)輪密鑰）由輪密鑰緩沖字W[Nb*i]到W[Nb*(i+1)-1]給出，如圖3-23所示。圖3-23Nb=6且Nk=4時(shí)的密鑰擴(kuò)展與輪密鑰選取3.6.2算法說明第三章分組密碼加密算法加密算法為順序完成以下操作：初始的密鑰加；(Nr-1)輪迭代；一個(gè)結(jié)尾輪。即第三章分組密碼3.6.2算法說明

其中CipherKey是種