第三章分組密碼課件

第三章分組密碼分組密碼(BlockCipher)，一類對稱密碼算法：將明文消息分組，逐組加密；將明文消息編碼表示后的數(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ù)E：Vn×K→Vm，K為密鑰空間分組密碼實質上是字長為m的數(shù)字序列的代換密碼1/算法的輸入長度和輸出長度1.通常取m=n(用于加密)2.若m≠n，則為有數(shù)據(jù)擴展(m>n)/壓縮(m<n)/的分組密碼(用于認證）

2/

第三章分組密碼1.代換置換網(wǎng)絡SPN

2.堆積引理與S盒的線性逼近

3.線性密碼分析與差分密碼分析

4.數(shù)據(jù)加密標準DES5.高級加密標準AES3.1代換-置換網(wǎng)絡SPN問題：什么是SPN?

預備知識：1.1設l和m都是正整數(shù)，明文密文都是長為lm的二元向量（即lm是該密碼的分組長度）一個SPN包括兩個變換，分別記為

都是置換，置換叫做S盒，

1.2給定一個lm比特的二元串將其看作

1.3SPN由Nr輪組成，在每一輪（除了最后一輪稍有不同外），我們先用異或操作混入該輪的輪密鑰，再用進行m次代換，然后用進行一次置換。密碼體制3.1

代換置換網(wǎng)絡

設和Nr都是正整數(shù)，和都是置換，設,是由初始密鑰K用密鑰編排算法生成的所有可能的密鑰編排方案之集對于一個密鑰編排方案，我們使用算法3.1來加密明文

算法3.1

for

to

在算法3.1中，是第r輪對S盒的輸入，是第r輪對S盒的輸出。由應用置換得到，然后由輪密鑰異或得到（這叫做輪密鑰混合），最后一輪沒有用置換

因此，如果密鑰編排方案作適當修改并用S盒的逆來取代S盒，那么該加密算法也能用來解密。

該SPN的第一個和最后一個操作都是異或輪密鑰，這叫做白化。白化可使一個不知道密鑰的攻擊者，無法開始進行一個加密或解密操作。

圖3.1給出了這個具體的SPN（為后面敘述的方便，在這個圖中我們命名了16個S盒它們都是基于同樣的置換）為了完成該SPN的描述，需要確定一個密鑰編排算法。從一個32比特的密鑰開始，對輪數(shù)，定義是由K中從開始的16個連續(xù)比特組成（選擇這樣的簡單密鑰編排方案只是為了說明SPN，并非是一種很安全的方式）。下面我們使用SPN來進行加密。所有數(shù)據(jù)都用二元形式表示。設密鑰為K=00111010100101001101011000111111則輪密鑰如下：

=00111010100101003.3線性密碼分析1.堆積引理預備：考慮離散隨機變量容易看出具有概率分布：

定義：的偏差為注意：對于

引理3.1（堆積引理）設是獨立隨機變量，表示隨機變量的偏差，則

證明

對k應用歸納法進行證明。當k=1時，結論顯然成立。我們現(xiàn)在來證明k=2時結論成立。使用前面的等式，我們有結論成立。

假設時結論成立，正整數(shù)則當時，我們需要確定的偏差，可將這個隨機變量分為如下兩個部分：

即有歸納假設，的偏差為，而的偏差為。因此，的偏差為

結論成立。注意引理3.1一般只在隨機變量是統(tǒng)計獨立的情況下才成立。反例：假設，由引理3.1有現(xiàn)在考慮隨機變量，顯然如果隨機變量和相互獨立，則有引理3.1可知，然而，由于和并不相互獨立。推論3.2

設時獨立隨機變量，表示隨機變量的偏差，若對某j,有則2.S盒的線性逼近

考慮如下一個S盒，m重輸入均勻隨機的從集合中選取，這就是說每一個坐標定義了一個隨機變量，取之于并且其偏差。更進一步，這m個隨機變量相互獨

立。n重輸出中，每一個坐標定義了一個隨機變量，取值于。這n個隨機變量一般說來并不相互獨立，與也不相互獨立。如果，則

后一公式成立是因為并且，如果，則

此時計算就相對直接多了例3.2我們任然用例3.1中的S盒，在表3.1的行中記下了八個隨機變量所有可能的取值?，F(xiàn)在考慮隨機變量通過計算表3.1中的行數(shù)，可以得到該隨機變量取值為零的概率因此可見，該隨機變量的偏差為0再分析隨機變量可看到該隨機變量的偏差為-3/8.

表3.1一個S盒定義的隨機變量

線性密碼分析－已知明文攻擊線性密碼分析是對迭代密碼的一種已知明文攻擊，它利用的是密碼算法中的“不平衡（有效）的線性逼近”。設明文分組長度和密文分組長度都為n比特，密鑰分組長度m比特，記明文分組為P[1]，P[2]，…，P[n]，比特形式密文分組為C[1]，C[2]，…，C[n]，密鑰分組為K[1]，K[2]，…，K[m]。定義:A[i,j,…,k]=A[i]A[j]…A[k]線性密碼分析的目標就是找出以下形式的線性方程：P[i1,i2,…,ia]C[j1,j2,…,jb]=K[k1,k2,…,kc]，其中1an，1bn，1cm即P中的某a個bit和C中的某b個比特與K中某c個比特滿足線性方程如果對于猜測的密鑰和已知的大量明密文對，方程成立的概率p≠1/2，則稱該方程是有效的線性逼近。如果|p-1/2|是最大的，則稱該方程是最有效的線性逼近。等于1/2時說明隨機性很好，再多明密文對也不暴露任何信息21/

線性密碼分析－已知明文攻擊設N表示明文數(shù)，T是使方程左邊為0的明文數(shù)。如果T>N/2，則令K[k1,k2,…,kc]＝如果T<N/2，則令

K[k1,k2,…,kc]＝從而可得關于密鑰比特的一個線性方程。對不同的明文密文對重復以上過程，可得關于密鑰的一組線性方程，從而確定出密鑰比特。

P[i1,i2,…,ia]

C[j1,j2,…,jb]=K[k1,k2,…,kc]

A[i,j,…,k]=A[i]

A[j]

…

A[k]22/如果方程成立的概率大于1/2，則由于使得左邊為0的明文數(shù)T大于總明文數(shù)的一半，在所有方程成立的情況中，左邊得0的可能性更大，所以此時令右邊取0。反之方程不成立的概率大于一半，則左邊1多，右邊取1

差分密碼分析－選擇明文攻擊差分密碼分析是迄今已知的攻擊迭代密碼最有效的方法之一其基本思想是：通過分析明文對的差值對密文對的差值的影響來恢復某些密鑰比特。對分組長度為n的r輪迭代密碼，兩個n比特串Yi和Yi*的差分定義為ΔYi＝Yi×(Yi*)－1。其中×表示n比特串集上的一個特定群運算，(Yi*)－1表示Yi*在此群中的逆元。在DES的差分分析中差分的計算選擇YiYi*，因為運算的單位元是0元由加密對可得差分序列：ΔY0,ΔY1,…,ΔYr其中Y0和Y0*是明文對，Yi和Yi*(1≤i≤r)是第i輪的輸出，它們同時也是第i+1輪的輸入。第i輪的子密鑰記為Ki，F(xiàn)是輪函數(shù)，且Yi=F(Yi-1,Ki)。23/

差分密碼分析－選擇明文攻擊定義4-1：r-輪特征(r-roundcharacteristic)Ω是一個差分序列：α0,α1,…,αr其中α0是明文對Y0和Y0*的差分，αi(1≤i≤r)是第i輪輸出Yi和Yi*的差分r-輪特征Ω=α0,α1,…,αr的概率是指在明文Y0和子密鑰K1,…,Kr獨立、均勻隨機時，明文對Y0和Y0*的差分為α0的條件下，第i(1≤i≤r)輪輸出Yi和Yi*的差分為αi的概率。共有r個概率值定義4-2：在r-輪特征Ω=α0,α1,…,αr中，定義

piΩ=P(ΔF(Y)=αi|ΔY=αi-1)即piΩ表示在輸入差分為αi-1的條件下，輪函數(shù)F的輸出差分為αi的概率。（轉移概率）

r-輪特征Ω=α0,α1,…,αr的概率近似看作。24/差分密碼分析－選擇明文攻擊對r-輪迭代密碼的差分密碼分析過程可綜述為如下步驟：①找出一個(r-1)-輪特征Ω(r-1)=α0,α1,…,αr-1，使得它的概率達到最大或幾乎最大。（通過統(tǒng)計分析或者數(shù)學推導的方法）②均勻隨機地選擇明文Y0并計算Y0*，使得Y0和Y0*的差分為α0，找出Y0和Y0*在實際密鑰加密下所得的密文Yr和Yr*。若最后一輪的子密鑰Kr（或Kr的部分比特）有2m個可能值Krj(1≤j≤2m)，設置相應的2m個計數(shù)器Λj(1≤j≤2m)。用每個Krj解密密文Yr和Yr*，得到Yr-1和Yr-1*，如果Yr-1和Yr-1*的差分是αr-1，則給相應的計數(shù)器Λj加1。③重復步驟②，直到一個或幾個計數(shù)器的值明顯高于其他計數(shù)器的值，輸出它們所對應的子密鑰（或部分比特）。25/Feistel密碼結構Feistel密碼結構（一種特殊的SPN結構）早期，很多成功的分組密碼的結構從本質上說都是基于一個稱為Feistel網(wǎng)絡的結構加解密相似是Feistel型密碼的一個實現(xiàn)優(yōu)點，但它對于密碼的擴散似乎有些慢，例如需要兩輪才能改變輸入的每一個比特。不過在實用中似乎并不會形成較大的影響，只要輪數(shù)足夠多。Feistel提出利用乘積密碼可獲得簡單代換密碼多輪迭代每一輪變換實際上是一種SPNFeistel還提出了實現(xiàn)代換和置換的方法

其思想實際上是Shannon提出的利用乘積密碼實現(xiàn)混淆和擴散思想的具體應用26/Feistel密碼結構27/1．Feistel加密結構HorstFeistel在70年代初設計了這樣的結構，我們現(xiàn)在叫做Feistelcipher每組明文分成左右兩半L0和R0其第i輪迭代的輸入為前一輪輸出的函數(shù)：Li＝Ri－1Ri＝Li－1F(Ri－1,Ki)Ki是第i輪用的子密鑰，各輪不同，由密鑰K產(chǎn)生最后一輪完成后再左右交換Feistel密碼結構Feistel網(wǎng)絡的實現(xiàn)與以下參數(shù)和特性有關：①分組大小分組越大則安全性越高，但加密速度就越慢。分組密碼設計中最為普遍使用的分組大小是64比特。當前多使用128比特以上②密鑰大小密鑰越長則安全性越高，但加密速度就越慢?，F(xiàn)在普遍認為64比特或更短的密鑰長度是不安全的，通常使用128比特的密鑰長度。③輪數(shù)單輪結構遠不足以保證安全性，但多輪結構可提供足夠的安全性。典型地，輪數(shù)取為16。④子密鑰產(chǎn)生算法：該算法的復雜性越大，則密碼分析的困難性就越大。⑤輪函數(shù)：輪函數(shù)的復雜性越大，密碼分析的困難性也越大。28/Feistel密碼結構在設計Feistel網(wǎng)絡時，還有以下兩個方面需要考慮①快速的軟件實現(xiàn)在很多情況中，算法是被鑲嵌在應用程序中，因而無法用硬件實現(xiàn)。此時算法的執(zhí)行速度是考慮的關鍵②算法容易分析如果算法能被無疑義地解釋清楚，就可容易地分析算法抵抗攻擊的能力，有助于設計高強度的算法2.Feistel解密結構Feistel解密過程本質上和加密過程是一樣的，使加解密可用同一算法,算法使用密文作為輸入，但使用子密鑰Ki的次序與加密過程相反，即第1輪使用Kn，第2輪使用Kn-1，…，最后一輪使用K1。29/Feistel密碼結構加密過程由上而下解密過程由下而上圖中右邊標出了解密過程中每一輪的中間值與左邊加密過程中間值的對應關系即加密過程第i輪的輸出是LEi‖REi（‖表示鏈接）解密過程第17-i輪相應的輸入是RDi‖LDi最后一輪輸出密文是RE16‖LE1630/數(shù)據(jù)加密標準DESDES的產(chǎn)生美國國家標準局1973年開始研究除國防部外的其它部門的計算機系統(tǒng)的數(shù)據(jù)加密標準于1973年5月15日和1974年8月27日先后兩次向公眾發(fā)出了征求加密算法的公告。加密算法要達到的目的（通常稱為DES密碼算法要求）主要為以下四點：（1）提供高質量的數(shù)據(jù)保護，防止數(shù)據(jù)未經(jīng)授權的泄露和未被察覺的修改；（2）計算安全性：具有相當高的復雜性，使得破譯的開銷超過可能獲得的利益，同時又要便于理解和掌握；（3）基爾霍夫準則：DES密碼體制的安全性應該不依賴于算法的保密，其安全性僅以加密密鑰的保密為基礎；（4）可行性：實現(xiàn)經(jīng)濟，運行有效，并且適用于多種完全不同的應用。31/數(shù)據(jù)加密標準DESDES在1975年3月17日首次被公布在聯(lián)邦記錄中經(jīng)過大量的公開討論后，1977年1月15日美國政府頒布：采納美國IBM公司設計的方案作為非機密數(shù)據(jù)的正式數(shù)據(jù)加密標準（DES,DataEncryptionStandard），DES被正式批準并作為美國聯(lián)邦信息處理標準，即FIPS-46，同年7月15日開始生效。它的分組長度為64比特，密鑰長度為56比特，是早期的稱作Lucifer密碼的一種發(fā)展和修改。DES是迄今為止世界上最為廣泛使用和流行的一種分組密碼算法，1996年以后，主要是3DES32/DES算法描述加密：明文分組64bit初始置換IP16輪的Feistel結構初始逆置換IP-1是IP的逆密鑰編排密鑰56比特，每7bit加1個奇偶校驗位，總計64比特置換函數(shù)PC-1左循環(huán)移位再置換函數(shù)PC-2輸出本輪子密鑰迭代16輪33/DES算法描述1.初始置換表3-2(a)和3-2(b)分別給出了初始置換和逆初始置換的定義，這兩個置換是互逆的。64比特的明文M以8比特為一行，共8行，以行順序編號由表3-2(a)得X=IP(M)，由3-2(b)得Y＝IP-1(X)=IP-1(IP(M))=M34/DES算法描述2.輪結構64比特的輪輸入分為左右兩半，右半部分是本輪子密鑰產(chǎn)生過程35/和Feistel網(wǎng)絡一樣，每輪變換可由以下公式表示：Li＝Ri－1

Ri＝Li－1F(Ri－1,Ki)其中輪密鑰Ki為48比特。DES算法描述函數(shù)F(R,K)的計算過程如上圖所示，輪輸入的右半部分R為32比特，R首先被擴展成48比特，擴展過程由表3.2(c)定義，其中將R的16個比特各重復一次。36/擴展后的48比特再與子密鑰Ki異或，然后再通過8個S盒，產(chǎn)生32比特的輸出。該輸出再經(jīng)過一個由表3.2(d)定義的置換P，產(chǎn)生的結果即為函數(shù)F(R,K)的輸出。DES算法描述擴展置換E和置換P37/DES算法描述代換盒，簡稱S盒，substitutionboxSF中的代換由8個S盒組成，每個S盒的輸入長為6比特、輸出長為4比特，其變換關系由表3.3定義，每個S盒給出了4個代換（由一個表的4行給出）。DES的S盒定義38/DES算法描述對每個盒Si其6比特輸入中，第1個和第6個比特形成一個2位二進制數(shù)，用來選擇Si的4個代換中的一個中間4位用來選擇列。行和列選定后，得到其交叉位置的十進制數(shù)，將這個數(shù)表示為4位二進制數(shù)即得這一S盒的輸出。例如，S1

的輸入為011001則行選為01（即第1行），列選為1100（即第12列）行列交叉位置的數(shù)為9，其4位二進制表示為1001，所以S1的輸出為1001。S盒作為該密碼體制的唯一非線性組件對安全性至關重要S-盒的設計準則還沒有完全公開，一些密碼學家懷疑美國NSA(theNationalSecurityAgency)設計S-盒時隱藏了陷門，即萬能鑰匙39/DES算法描述3．密鑰的產(chǎn)生實際上，K是長度為64的位串，其中56位是密鑰，8位是奇偶校驗位（為了檢錯），在密鑰編排的計算中，這些校驗位可略去。DES密鑰編排算法結構圖LSi表示循環(huán)左移一個或兩個位置其中i為1，2，9，16循環(huán)移1位，其余循環(huán)移兩位40/DES算法描述綜述加密過程：(1)給定64位的密鑰K，放棄奇偶校驗位（8，16，…，64）形成連續(xù)的56比特的密鑰，對輸入分組進行固定的“初始置換”IP,我們可以將這個初始置換寫為,稱為“左右半分組”32bits(2)再看DES加密算法框圖，進行16輪迭代：，，輸入算法的56比特密鑰首先經(jīng)過一個置換運算PC-1，該置換由表3.4(a)給出得到48比特的子串，稱為布爾函數(shù)，它的特點是交換兩半分組。在第i輪分別對進行左循環(huán)移位，所移位數(shù)由表3.4(c)給出。移位后的結果作為求下一輪子密鑰的輸入，同時也作為置換選擇2PC-2的輸入。通過置換選擇2產(chǎn)生的48比特的Ki，即為本輪的子密鑰，作為函數(shù)F(Ri-1,Ki)的輸入。其中置換選擇2由表3.4(b)定義（3）DES算法的輸出，我們將最后一步寫為:

注意的輸入：在輸入之前，16輪迭代輸出的兩個半分組又進行了一次交換。DES算法描述DES密鑰編排中使用的表（表3-4）

(a)置換選擇1(b)置換選擇2(c)左循環(huán)移位位數(shù)

42/DES算法描述4．解密和Feistel密碼一樣，DES的解密和加密算法使用同一算法，但子密鑰使用的順序相反解密時子密鑰的產(chǎn)生有兩種方式：1）是先由K產(chǎn)生16個子密鑰，再逆續(xù)使用2）反序產(chǎn)生。(在前面講過的密鑰擴展過程中若改LSi為

則也就可以依次產(chǎn)生這逆序的子密鑰。43/

例

在加密密鑰下，將明文消息加密為密文消息。讓我們通過DES算法來確認解密函數(shù)的正確運算，也就是在下，的解密就輸出。

解：解密算法首先輸入密文作為“輸入分組”，即但是因為c是實際上是加密算法中最后一步的“輸出分組”，即：在第一輪中，我們有這兩個式子的右邊，

應該用

來代替，應該用其中，因此，上面兩個式子實際上是下面的兩個

所以，在第一輪解密以后，我們得到因此，在第二輪開始，兩個半分組是.在隨后的15輪中，使用同樣的驗證，我們將獲得在16輪迭代得到的兩個最后的半分組被交換為

然后輸入到來消除IP在式中的影響。解密函數(shù)的輸出確實是最初的明文分組m.DES的安全性問題完全依賴于所用的密鑰，即算法是公開的DES的設計特色：在DES算法中函數(shù)是最基本的關鍵環(huán)節(jié)，其中（1）用S盒實現(xiàn)小塊的非線性變換，達到混亂目的（2）用置換p實現(xiàn)大塊的非線性變換，達到擴散目的（3）置換p的設計是每層s盒的4bit輸出進入到下一層的4個不同S盒DES的安全性包括：取反特性，弱密鑰和半弱密鑰，密鑰與密文和明文的關系，DES評估與窮搜索破譯3.6高級加密標準AES

由于DES要花費比較大的軟硬件代價，效率不盡如人意，況且DES密鑰較短不能抵抗群搜索攻擊，于是更好的標準AES走向了前臺。

2000年10月2日NIST宣布Rijndael作為新的AES。至此，經(jīng)過3年多的討論，Rijndael終于脫穎而出。2006年，AES已然成為了對稱密鑰加密中重要的國際標準之一AES的應用產(chǎn)品：有移動硬盤，USB無線網(wǎng)卡，加密鎖，指紋加密U盤，指紋加密防護盾等。

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

b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0例如：十六進制數(shù)‘57’對應的二進制為01010111，看成一個字節(jié)，對應的多項式為x6+x4+x2+x+148/Rijndael的數(shù)學基礎和設計思想AES的理論基礎定義在GF(28),其基本的運算有三種，分別為加法，乘法和x乘。加法：在多項式表示中，GF(28)上兩個元素的和仍然是一個次數(shù)不超過7的多項式，其系數(shù)等于兩個元素對應系數(shù)的模2加（比特異或）。例如：‘57’+‘83’=‘D4’，用多項式表示為(x6+x4+x2+x+1)+(x7+x+1)=x7+x6+x4+x2(modm(x))用二進制表示為01010111+10000011=11010100由于每個元素的加法逆元等于自己，所以減法和加法相同。49/Rijndael的數(shù)學基礎和設計思想乘法：要計算GF(28)上的乘法，必須先確定一個GF(2)上的8次不可約多項式，GF(28)上兩個元素的乘積就是這兩個多項式的模乘，在Rijndael密碼中，這個8次不可約多項式確定為

m(x)=x8+x4+x3+x+1它的十六進制表示為‘11B’。二進制為100011011例如，‘57’·‘83’=‘C1’可表示為以下的多項式乘法：(x6+x4+x2+x+1)×(x7+x+1)=x7+x6+1(modm(x))乘法運算雖然不是標準的按字節(jié)的運算，但也是比較簡單的計算部件。50/Rijndael的數(shù)學基礎和設計思想以上定義的乘法滿足交換律，且有單位元‘01’。逆元，對任何次數(shù)小于8的多項式b(x)，可用推廣的歐幾里得算法得b(x)a(x)+m(x)c(x)=1即a(x)·b(x)=1modm(x)，因此a(x)是b(x)的乘法逆元。再者，乘法還滿足分配律：a(x)·(b(x)+c(x))=a(x)·b(x)+a(x)·c(x)所以，256個字節(jié)值構成的集合，在以上定義的加法和乘法運算下，有有限域GF(28)的結構非0元的乘法滿足Abel群，加法滿足Abel群，＋,×滿足分配率51/Rijndael的數(shù)學基礎和設計思想X乘GF(28)上還定義了一個運算，稱之為x乘法，其定義為x·b(x)=b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x(modm(x))如果b7=0，求模結果不變，否則為乘積結果減去m(x)，即求乘積結果與m(x)的異或。由此得出x（十六進制數(shù)‘02’）乘b(x)可以先對b(x)在字節(jié)內左移一位（最后一位補0），若b7=1，則再與‘1B’（其二進制為00011011）做逐比特異或來實現(xiàn)，該運算記為b=xtime(a)。在專用芯片中，xtime只需4個異或。x的冪乘運算可以重復應用xtime來實現(xiàn)。而任意常數(shù)乘法可以通過對中間結果相加實現(xiàn)。例如，‘57’·‘08’可按如下方式實現(xiàn)：‘57’·‘02’=xtime(57)=‘AE’；‘57’·‘04’=xtime(AE)=‘47’；‘57’·‘08’=xtime(47)=‘8E’；52/Rijndael的數(shù)學基礎和設計思想2.系數(shù)在GF(28)上的多項式4個字節(jié)構成的向量可以表示為系數(shù)在GF(28)上的次數(shù)小于4的多項式，多項式的加法就是對應系數(shù)相加，即4字節(jié)向量的逐比特異或規(guī)定多項式的乘法運算必須要取模M(x)=x4+1，這樣使得次數(shù)小于4的多項式的乘積仍然是一個次數(shù)小于4的多項式，將多項式的模乘運算記為×設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)而xjmod(x4+1)=xjmod4，所以c0=a0b0a3b1a2b2a1b3c1=a1b0a0b1a3b2a2b3c2=a2b0a1b1a0b2a3b3c3=a3b0a2b1a1b2a0b353/Rijndael的數(shù)學基礎和設計思想可將上述計算表示為＝注意到M(x)不是GF(28)上的不可約多項式（甚至也不是GF(2)上的不可約多項式），因此非零多項式的這種乘法不是群運算。不過在Rijndael密碼中，對多項式b(x)，這種乘法運算只限于乘一個固定的有逆元的多項式a(x)=a3x3+a2x2+a1x+a0。定理1系數(shù)在GF(28)上的多項式a3x3+a2x2+a1x+a0是模x4+1可逆的，當且僅當以下矩陣在GF(28)上可逆。54/55/證明：a3x3+a2x2+a1x+a0是模x4+1可逆的，當且僅當存在多項式h3x3+h2x2+h1x+h0，使得(a3x3+a2x2+a1x+a0)(h3x3+h2x2+h1x+h0)=1mod(x4+1)因此有(a3x3+a2x2+a1x+a0)(h2x3+h1x2+h0x+h3)=xmod(x4+1)(a3x3+a2x2+a1x+a0)(h1x3+h0x2+h3x+h2)=x2mod(x4+1)(a3x3+a2x2+a1x+a0)(h0x3+h3x2+h2x+h1)=x3mod(x4+1)；將以上關系寫成矩陣形式即得

=

c(x)=x×b(x)定義為x與b(x)的模x4+1乘法，即c(x)=x×b(x)=b2x3+b1x2+b0x+b3。其矩陣表示中，除a1=‘01’外，其他所有ai=‘00’，即＝因此x（或x的冪）模乘多項式相當于對字節(jié)構成的向量進行字節(jié)循環(huán)移位Rijndael算法的特點

1.AES的加解密算法、密鑰生成算法都是以State為輸入

2.加密時，首先進行“輪密鑰加”算法，然后重復9輪基本密碼模塊的迭代算法，每一輪有字節(jié)代換，行移位、列混淆和輪密鑰加四個算法；最后進行第10輪運算，它與前面9輪比一樣的地方，就是少了列混淆算法。

3.解密時，是執(zhí)行加密的逆過程，但要注意在解密時，字節(jié)代換、行移位和列混淆三種運算是執(zhí)行逆過程，算法設計完全不一樣，只有輪密鑰加算法和加密一樣

2.輪函數(shù)Rijndael的輪函數(shù)由4個不同的計算部件組成，分別是：字節(jié)代換（ByteSub）、行移位（ShiftRow）列混合（MixColumn）、密鑰加（AddRoundKey）(1)字節(jié)代換（ByteSub）字節(jié)代換是非線性變換，獨立地對狀態(tài)的每個字節(jié)進行。代換表（即S-盒）是可逆的，由以下兩個變換的合成得到：①首先，將字節(jié)看作GF(28)上的元素，映射到自己的乘法逆元，‘00’映射到自己。②其次，對字節(jié)做如下的（GF(2)上的，可逆的）仿射變換：

上述S-盒對狀態(tài)的所有字節(jié)所做的變換記為ByteSub(State)57/整個變換做成256字節(jié)的代換表，運算時查表即可

算法說明圖3.19是字節(jié)代換示意圖。ByteSub的逆變換由代換表的逆表做字節(jié)代換，可通過如下兩步實現(xiàn):首先進行仿射變換的逆變換再求每一字節(jié)在GF(28)上逆元58/S盒aijbij

算法說明(2)行移位（ShiftRow）行移位是將狀態(tài)陣列的各行進行循環(huán)移位，不同狀態(tài)行的位移量不同。第0行不移動第1行循環(huán)左移C1個字節(jié)第2行循環(huán)左移C2個字節(jié)第3行循環(huán)左移C3個字節(jié)位移量C1、C2、C3的取值與Nb有關，由表3.10給出。

表3.1059/

算法說明按指定的位移量對狀態(tài)的行進行的行移位運算記為ShiftRo