應(yīng)用密碼學(xué)第三章分組密碼體制

應(yīng)用密碼學(xué)第三章分組密碼體制 3.1分組密碼概述

分組密碼是一種廣泛使用的對稱密碼。和對稱密碼中的序列密碼(流密碼streamcipher)不同，分組密碼在加密過程中不是將明文按字符逐位加密，而是首先要將待加密的明文進行分組，每組的長度相同，然后對每組明文分別加密得到密文。分組密碼系統(tǒng)采用相同的加密密鑰和解密密鑰，這是對稱密碼系統(tǒng)的顯著特點。例如將明文分為m塊：P0，P1，P2，…，Pm-1，每個塊在密鑰作用下執(zhí)行相同的變換，生成m個密文塊：C0,C1,C2,…,Cm-1，每塊的大小可以是任意長度，但通常是每塊的大小大于等于64位（塊大小為1比特位時，分組密碼就變?yōu)樾蛄忻艽a）。如圖3－1所示是通信雙方最常用的分組密碼基本通信模型。圖3－1分組密碼基本通信模型圖

在圖3－1中，參與通信的實體有發(fā)送方Alice、接收方Bob。而攻擊者是在雙方通信中試圖攻擊發(fā)方或者收方信息服務(wù)的實體，攻擊者經(jīng)常也稱為敵人、對手、搭線者、竊聽者、入侵者等，并且攻擊者通常企圖扮演合法的發(fā)送方或者接收方。

由圖3－1所示，一個分組密碼系統(tǒng)(BlockCipherSystem，簡稱BCS）可以用一個五元組來表示：BCS={P,C,K,E,D}。其中，P、C、K、E、D分別代表明文空間、密文空間、密鑰空間、加密算法、解密算法。

設(shè)X={x0,x1,…,xn-2,xn-1}為一組長度為n的明文塊，在密鑰K={k0,k1,…,kt-1}的加密作用下得到密文塊Y={y0,y1,…,ym-2,ym-1}，其中xi,yj,kr∈GF(2)，且0≤i≤n-1,0≤j≤m-1,0≤r≤t-1若n=m，明文塊長度等于密文塊長度，稱之為無數(shù)據(jù)擴展和壓縮的分組密碼；若n>m，明文塊長度大于密文塊長度，稱之為有數(shù)據(jù)壓縮的分組密碼；若n<m，明文塊長度小于密文塊長度，稱之為有數(shù)據(jù)擴展的分組密碼。為了保證分組密碼的安全強度，設(shè)計分組密碼時應(yīng)遵循如下的基本原則：

（1）分組長度足夠長，防止明文窮舉攻擊，例如DES（DataEncryptionStandard）、IDEA（InternationalDataEncryptionAlgorithm）等分組密碼算法，分組塊大小為64bit，在生日攻擊下用232組密文，破解成功的概率為0.5，同時要求232×64bit=215MB大小的存儲空間，故在目前環(huán)境下采用窮舉攻擊DES、IDEA等密碼算法是不可能的；而AES明文分組為128bit，同樣在生日攻擊下用264組密文，破解成功的概率為0.5，同時要求存儲空間大小為264×128bit=248MB，所以采用窮舉攻擊AES算法在計算上就更不可行。

(2)密鑰量足夠大，同時需要盡可能消除弱密鑰的使用，防止密鑰窮舉攻擊，但是由于對稱密碼體制存在密鑰管理問題，密鑰也不能過大。

（3）密鑰變換足夠復(fù)雜，能抵抗各種已知攻擊，如差分攻擊、線性攻擊、邊信道攻擊等，即使得攻擊者除了窮舉攻擊外找不到其它有效的攻擊方法。

（4）加密和解密的運算簡單，易于軟硬件高速實現(xiàn)。

（5）數(shù)據(jù)擴展足夠小，一般無數(shù)據(jù)擴展。

（6）差錯傳播盡可能小，加密或解密某明文或密文分組出錯，對后續(xù)密文解密的影響也盡可能小。

3.2分組密碼的原理

20世紀40年代末，ClaudeShannon（香農(nóng)）在遵循Kerckhoff(柯克霍夫)原則前提下，提出了設(shè)計密碼系統(tǒng)的兩個基本方法——擴散和混淆，目的是抗擊攻擊者對密碼系統(tǒng)的統(tǒng)計分析。

（1）擴散：將明文的統(tǒng)計特性散布到密文中去，實現(xiàn)方式是使得明文的每一位影響密文中多位的值，等價于密文中每一位均受明文中多位的影響。在分組密碼中，對數(shù)據(jù)重復(fù)執(zhí)行某個置換，再對這一置換作用于一函數(shù)，可獲得擴散。

（2）混淆：使密文和密鑰之間的統(tǒng)計關(guān)系變得盡可能復(fù)雜，使得攻擊者無法得到密文和密鑰之間的統(tǒng)計，從而攻擊者無法得到密鑰。

1．代替—置換網(wǎng)絡(luò)

1949年，ClaudeShannon（香農(nóng)）在他的論文中提出了一種乘積密碼，實現(xiàn)混淆和擴散。乘積密碼通常伴隨一系列置換與代替操作，常見的乘積密碼是迭代密碼。許多分組密碼重復(fù)一個或幾個步驟：代替然后換位，之后再代替，再換位等，并且每個步驟的過程都由密鑰來控制。目前的大多數(shù)分組密碼同時使用代替-置換網(wǎng)絡(luò)以達到混淆和擴散的目標(biāo)。

代替-置換網(wǎng)絡(luò)是由多重代替變換(S)和置換變換（P）構(gòu)成，如圖3－2所示，S代替操作起到混淆的作用，P置換操作起到擴散的作用。圖3－2一個代替—置換網(wǎng)絡(luò)圖

2．Feistel密碼結(jié)構(gòu)

最典型的乘積密碼是在1973年由Feistel提出的，整個處理過程包括多輪的代替和置換操作，主密鑰分為一個子密鑰集，每輪使用一個子密鑰。在每輪中，明文被分為左右兩部分,分別記為L0和R0，兩部分分別進行交換，其中一個部分與子密鑰混合，進行相應(yīng)變換。在進行完n輪迭代之后，左右兩半合并在一起再產(chǎn)生密文。Feistel加密法的其中一輪的操作如圖3－3所示。圖3－3

Feistel一輪的加密每輪迭代運算的邏輯關(guān)系可表示如下：其中,Ki表示第i輪用的子密鑰，Li表示第i輪的左半部，Ri表示第i輪的右半部，F(xiàn)表示輪函數(shù)。圖3－4為Feistel網(wǎng)絡(luò)示意圖。圖3－4

Feistel網(wǎng)絡(luò)結(jié)構(gòu)示意圖

Feistel網(wǎng)絡(luò)中除了最后一輪，每輪結(jié)構(gòu)相同，每輪右半部分在子密鑰控制下數(shù)據(jù)先進入輪函數(shù)F，然后與左半部分異或得到下一輪的右半部分，而下一輪的左半部分直接為上一輪的右半部分。最后一輪的結(jié)構(gòu)則是上一輪右半部分在子密鑰控制下數(shù)據(jù)先進入輪函數(shù)F，然后與左半部分異或得到下一輪的左半部分，而右半部分是上一輪的右半部分。

Feistel網(wǎng)絡(luò)結(jié)構(gòu)已成為現(xiàn)代對稱密碼體制結(jié)構(gòu)的基礎(chǔ)，如DES算法設(shè)計就是最典型的Feistel結(jié)構(gòu)，那么在采用Feistel網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計分組密碼的過程中，為了保證分組密碼的安全性，與分組密碼算法原則非常類似，F(xiàn)eistel網(wǎng)絡(luò)結(jié)構(gòu)的實現(xiàn)與以下參數(shù)和特性有關(guān)：

（1）分組大小。分組越大則安全性越高，但加密速度就越慢。分組密碼設(shè)計中最為普遍使用的分組大小是64bit。

（2）密鑰大小。密鑰越長則安全性越高，但加密速度就越慢?，F(xiàn)在通常使用128bit的密鑰長度。

（3）輪數(shù)。單輪結(jié)構(gòu)遠不足以保證安全性，但多輪結(jié)構(gòu)可提供足夠的安全性。典型地，輪數(shù)取為16。

（4）子密鑰產(chǎn)生算法。該算法的復(fù)雜性越大，則密碼分析的困難性就越大。

（5）輪函數(shù)。輪函數(shù)的復(fù)雜性越大，密碼分析的困難性也越大。

3.Feistel解密結(jié)構(gòu)

如圖3－5所示，左邊為Feistel加密過程，右邊為Feistel解密過程。從圖中可以看出，F(xiàn)eistel解碼過程所在的變換與加密過程完全一樣，只是算法的輸入不一樣。加密輸入的數(shù)據(jù)為明文，子密鑰的順序為K1,K2,…,Kr-1，Kr,而Feistel解密過程輸入的數(shù)據(jù)為密文，子密鑰的順序與加密過程剛好相反，為Kr,Kr-1,…,K2,K1。因此采用Feistel網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計分組密碼算法，加解密可采用同一種算法。圖3－5

Feistel加解密過程

DES算法概述

數(shù)據(jù)加密標(biāo)準(zhǔn)（DataEncryptionStandard，DES）是由美國IBM公司于20世紀70年代中期的一個密碼算法（LUCIFER算法）發(fā)展而來的，在1977年1月15日，美國國家標(biāo)準(zhǔn)局（NBS）正式公布實施，并得到了ISO的認可。在過去近20多年的時間里，DES被廣泛應(yīng)用于美國聯(lián)邦和各種商業(yè)信息的安全保密工作中，經(jīng)受住了各種密碼分析和攻擊，體現(xiàn)出了令人滿意的安全性。但隨著密碼分析技術(shù)和計算能力的提高，1994年，美國決定1998年12月以后不再使用DES算法，目前DES算法已被更為安全的Rijndael算法取代。雖然這樣，但是目前還無法將DES加密算法徹底地破解掉，而且DES算法的加解密過程非常快，仍是目前使用最為普遍的對稱密碼算法。在國內(nèi)，隨著三金工程尤其是金卡工程的啟動，DES算法在POS、ATM、磁卡及智能卡(IC卡)、加油站、高速公路收費站等領(lǐng)域被廣泛應(yīng)用，以此來實現(xiàn)關(guān)鍵數(shù)據(jù)的保密，如信用卡持卡人的PIN碼加密傳輸，IC卡與POS機之間的雙向認證、金融交易數(shù)據(jù)包的MAC校驗等，均用到DES算法。3.3數(shù)據(jù)加密標(biāo)準(zhǔn)

DES算法是一種采用傳統(tǒng)的代替和置換操作加密的分組密碼，明文以64比特為分組，密鑰長度為64比特，有效密鑰長度為56比特，其中加密密鑰有8比特是奇偶校驗，DES算法的加密和解密用的是同一算法，它的安全性依賴于所用的密鑰。它首先把需要加密的明文劃分為每64比特二進制的數(shù)據(jù)塊，用56比特有效密鑰對64比特二進制數(shù)據(jù)塊進行加密，每次加密可對64比特的明文輸入進行16輪的替換和移位后，輸出完全不同的64比特密文數(shù)據(jù)。由于DES算法僅使用最大為64比特的標(biāo)準(zhǔn)算術(shù)和邏輯運算，運算速度快，密鑰產(chǎn)生容易，適合于在當(dāng)前大多數(shù)計算機上用軟件方法實現(xiàn)，同時也適合于在專用芯片上實現(xiàn)。

DES算法描述

DES算法的加密過程首先對明文分組進行操作，需要加密的明文分為固定大小為64比特的塊。圖3－6是DES算法的加密流程，圖的左邊是一個64比特的明文分組塊的加密處理過程，右邊為密鑰擴展處理過程。圖3－6

DES加密算法流程（右邊矩形框內(nèi)虛線為子密鑰生成過程）

1. 初始置換（IP）

首先輸入的64比特的明文塊為，按照初始置換(IP)表進行置換，DES的初始置換表如圖3－7所示。圖3－7初始置換表如圖3－7可以看出，輸入的m1m2…m64經(jīng)過初始置換表輸出m58m50…m8m57m49…m7，即把明文塊按照序號順序產(chǎn)生一個8×8矩陣，然后根據(jù)初始置換矩陣進行變換。

2．輪結(jié)構(gòu)經(jīng)過DES算法第一階段的初始置換得到64比特的塊為：，然后分為兩部分，前32位為左半部分，記為L0，后32位為右半部分，記為R0。如圖3－8所示，DES算法的輪結(jié)構(gòu)和Feistel輪結(jié)構(gòu)一樣，分為左右兩部分各32比特在每一輪中被獨立處理。具體過程為：下一輪左半部分的32比特Li等于上一輪右半部分32比特Ri-1；而下一輪右半部分的32比特Ri的計算則先由上一輪右半部分Ri-1和輪密鑰Ki輸入到F函數(shù)中（圖3－9）進行變換，變換的結(jié)果再與上一輪左半部分Li進行異或運算，得到Ri。因此每一輪變換可由下面公式表示：圖3－8DES算法的一輪結(jié)構(gòu)變換圖圖3－9

F函數(shù)的計算過程下面將給出DES算法的一輪結(jié)構(gòu)變換的具體計算過程。首先根據(jù)F函數(shù)計算過程給出右半部的變換過程（圖3－9）。若右半部分R0，則進行E盒變換，將32比特擴展為48比特，E盒擴充方式如圖3－10所示。具體變換過程為把輸入32比特按照8行4列方式依次排列，形成一個8×4的矩陣，然后E盒擴展之后輸出為8×6矩陣。圖3－10擴展E盒變換在我們的示例中輸入R0，按照圖3－10所示的E盒變換之后為：E盒變換之后的48比特輸出為：100000000001011111111110100000001101010000000110根據(jù)示意圖3－9，下一步的操作是E盒的輸出48比特作為輸入與子密鑰進行異或（XOR）操作，若子密鑰48比特為：，則操作如下：輸入：100000000001011111111110100000001101010000000110密鑰：001111011000111111001101001101110011111101001000輸出：101111011001100000110011101101111110101101001110輸出新的48比特將作為S盒的輸入，進入S盒變換，48比特壓縮為32比特，如圖3－9所示。S盒的安全性能是保證DES算法安全性的源泉，DES算法總共有8種不同的S盒，其定義見圖3－11，每個S盒接收6位的輸入，輸出4位。一個S盒有16列和4行，它的每個元素是4位，通常用十進制表示。每個S盒的使用方法為：S盒接收到6比特的輸入，其中第1個比特和最后1比特構(gòu)成的2位二進制為該S盒的行號，中間的4位二進制為該S盒的列號，然后由該S盒的定義表根據(jù)行號和列號查表得到對應(yīng)的值（一般為十進制），該值就是S盒變換的輸出，并轉(zhuǎn)化為二進制。具體變換過程為：若輸入為第i個S盒的6比特為Bi=b1b2…b6，然后計算r=2·b1+b6，c=23·b2+22·b3+2·b4+b5，r、c分別為Si盒中的行號和列號，則輸出塊為Si盒中相應(yīng)列號和行號的對應(yīng)值。例如B1=101111，輸入第1個S盒，S1(101111)計算為r=3，c=7，對應(yīng)十進制7，即二進制0111。圖3－11

DES算法的S盒圖3-12P盒的置換

P盒置換輸出：其左半部分的32比特為上一輪右半部分的32比特，L1=R0，而下一輪右半部為經(jīng)過P盒作用之后輸出32比特與左半部分L0的32位進行異或，得到右半部分最終的R1的32比特：XOR01000100001000001001111010011111111111111011100001110110010101110000000011111111000001101000001110111011100110001110100011001000

經(jīng)過一輪完整變換之后，左半部分L1，右半部分R1，作為下一輪的輸入，總共有16輪的運算。

3.逆初始置換（IP-1）

DES算法進行完16輪運算之后，需要進行逆初始置換，逆初始置換正好為初始置換的逆，若一個矩陣進行初始置換之后輸出，再進行一次逆初始置換的輸出結(jié)果為初始矩陣。

假若經(jīng)過16輪加密之后，輸入逆初始置換的64比特的塊為，按照逆初始置換(IP)表進行置換，DES的初始置換表如圖3－13所示。圖3－13逆初始置換表按照圖3－13中逆初始置換表操作如下：逆初始置換輸出為，按照序號排出8×8的列。經(jīng)過逆初始置換之后的64比特塊為：，即密文C。

根據(jù)上面實例可知，DES算法的加密流程可以分為下面四個階段：設(shè)輸入64比特的明文塊記為m1m2…m64，初始64比特密鑰記為K0=k1k2…k64，密鑰擴展之后的輪密鑰分別記為K1,K2,…,K15,K16，算法描述如下：

(1)(L0,R0)←IP(m1m2…m64)，首先通過一個初始置換IP（如圖3－7），把64比特明文塊重排，然后將明文分組成左半部分和右半部分，各為32比特，即L0=m58m50…m8，R0=m57m49…m7。

(2)然后進行16輪完全相同的運算（圖3－8），i從1到16，通過F函數(shù)（圖3－9），數(shù)據(jù)與輪密鑰結(jié)合，分別計算出Li和Ri，其中F函數(shù)計算可記為：其中E表示E盒變換（圖3－10），S表示S盒變換（圖3－11），P表示P盒變換（圖3－12），具體變換過程如下所示：①T←E(Ri)，即將右半部的32比特的Ri=r1r2…r32輸入E盒擴展為48比特，記為T。②T′←T+Ki，將得到的48比特的字串T與子密鑰Ki異或得到T′，然后將T′平分為8個塊，分別記為B1,…,B8，即為T′=(B1,…,B8)，每個塊Bi為6比特。F(Ri-1,Ki)=P(S(E(Ri-1)Ki))③T″←(S1(B1),S2(B2),…,S8(B8))，將8個B1,…,B8比特塊分別進行S盒變換（圖3－11），將輸入的48比特壓縮為32比特輸出，記為T″，其中每個S盒變換可記為Si(Bi)，具體變換過程參見下面的輪結(jié)構(gòu)描述。

④T←P(T″)，T″作為輸入，進行P盒置換輸出，記為T’’’。

⑤Li←Ri-1,Ri←T’’’Li-1，輸出的左半部Li為上一輪右半部Ri-1，而輸出的右半部Ri為T與上一輪左半部Li-1進行異或操作。+

(3)b1b2…b64←(R16,L16)，經(jīng)過上面16輪變換之后，把最后分組(L16,R16)進行交換，得到(R16,L16)作為輸出。

(4)C←IP-1(b1b2…b64)，將第(3)步的輸出進行IP逆置換最后得到密文C（圖3－13）。

4．子密鑰產(chǎn)生過程描述

子密鑰產(chǎn)生過程的輸入，為用戶持有的64比特初始密鑰，但若用戶只提供56比特（通常是用ASCII碼表示的7個字母的單詞作為密鑰）。其余8比特由算法提供，分別放在8、16、24、32、40、48、56和64位上（位的序號為8的倍數(shù)）。因此初始密鑰中每8位的密鑰包含用戶提供的7位和DES確定的1位。DES算法添加的位稱為奇偶校驗位，即每8位的密鑰塊中都有奇數(shù)個奇偶校驗（1的個數(shù)為奇數(shù)）。用戶將初始密鑰64位輸入到子密鑰產(chǎn)生流程中，首先經(jīng)過密鑰置換PC－1，將初始密鑰的8個奇偶較驗位去掉。留下真正的56比特初始密鑰。接著，分為兩個28比特分組C0及D0，再分別經(jīng)過一個循環(huán)左移函數(shù)，每一半左移1或2位（每個階段情況不同），連接成56比特數(shù)據(jù)，再按密鑰置換PC－2做重排，進行壓縮，拋棄8位后，便可輸出子密鑰的48比特，作為F函數(shù)的密鑰輸入部分。該過程如圖3－14所示。圖3－14

DES的輪密鑰的產(chǎn)生

要注意的是，密鑰置換PC－1的輸入為64比特，輸出為56比特；而密鑰置換PC－2的輸入和輸出分別為56比特和48比特。

在我們所用示例中用戶初始輸入的56比特有效密鑰為：。

分別在8、16、24、32、40、48、56和64位上插入DES算法提供的8位，變成64比特密鑰為，然后作為選擇置換PC－1的輸入，按照下面的置換表進行重新編排和壓縮，編排方式如圖3－15所示。圖3－15置換選擇PC－1輸入：PC－1輸出：置換選擇PC－1輸出的56比特分為兩半，前28比特為C0，后半部分的28比特為D0。然后根據(jù)左循環(huán)移位函數(shù)進行左循環(huán)移位1或2位，各輪移位位數(shù)如表3－1所示。表3－1循環(huán)左移位

根據(jù)表3-1所示，C0及D0分別左循環(huán)1位得到C1=1101100100110010001101110111D1=0110100010110001000111001101，然后C1和D1連接56位為11011001001100100011011101110110100010110001000111001101作為置換選擇PC-2的輸入，進行重新編排和壓縮，輸出48位，得到子密鑰K1，而C1和D1作為下一輪子密鑰的輸入。置換選擇PC-2的編排和壓縮規(guī)則如圖3-16所示。圖3-16置換選擇PC-2通過PC－2置換選擇輸出的就是DES第1輪的子密鑰K1，為，作為DES算法輪結(jié)構(gòu)變換F函數(shù)的輸入。在分組密碼算法中可以看出，密鑰隨著明文的每一輪變換而變換。DES算法有16輪運算，子密鑰也有16個。

DES的各種變形算法

1.二重DES

二重DES算法是DES各種變形算法中最簡單的形式，對明文加密不是使用一個密鑰，而是采用兩個互不相同的密鑰K1和K2進行連續(xù)加密，因此二重DES的有效密鑰長度實際為112比特，比起一重DES的56比特的有效密鑰長度，其強度極大的增強。其加密和解密過程如圖3－17所示。圖3－17二重DES設(shè)二重DES兩加密密鑰分別為K1和K2，則首先用密鑰K1對明文P進行加密，然后再用密鑰K2進行加密，其密文為：解密時，首先用K2進行解密，然后再用K1進行解密，密鑰順序正好與加密密鑰順序相反，即

2.三重DES

在二重DES的基礎(chǔ)上，又提出了三重DES算法。3DES的使用有如下四種不同模式：

（1）DES－EEE3模式。如圖3－18所示，使用三個互不相同的密鑰，實現(xiàn)方式為加密－加密－加密，密鑰分別為K1、K2、K3，其密文為：解密時，密鑰順序正好與加密密鑰順序相反，即圖3－18三重DES－EEE3模式（2）DES－EDE3模式。如圖3－19所示，使用三個互不相同的密鑰，依次采用加密－解密－加密算法，密鑰分別為K1、K2、K3，其密文為：解密時，密鑰順序正好與加密密鑰順序相反，依次采用解密－加密－解密的順序，即圖3－19三重DES－EDE3模式（3）DES－EEE2模式，如圖3－20所示，使用兩個互不相同的密鑰K1、K2，實現(xiàn)方式為加密－加密－加密算法，其中第1次和第3次加密采用相同的密鑰，分別為K1=K3，其密文為：解密時，密鑰順序正好與加密密鑰順序相反，即圖3－20三重DES－EEE2模式（4）DES－EDE2模式，如圖3－21所示，使用兩個互不相同的密鑰K1、K2，實現(xiàn)方式為加密－解密－加密算法，簡記為EDE。此方案已在密鑰管理標(biāo)準(zhǔn)和ISO8732中被采用。密鑰分別為K1=K3，其密文為：解密時，密鑰順序正好與加密密鑰順序相反，依次采用解密－加密－解密的順序，即四種不同三重DES算法中，前兩種模式的密鑰長度為168比特，而后兩種模式的密鑰長度為112比特，已在因特網(wǎng)的許多應(yīng)用（如PGP和S/MIME）中被采用。

3.4高級加密標(biāo)準(zhǔn)(AES)

算法中的數(shù)學(xué)基礎(chǔ)知識

1.因子

設(shè)a、b是兩個整數(shù)，b≠0，如果存在整數(shù)k，使得a=kb,則稱b整除a，記為b|a。否則稱b不整除a，記為ba。

一個基本性質(zhì)是：若b|s、b|t，則對任意整數(shù)u、v，有b|us+vt。

證明：由b|s、b|t，則存在整數(shù)m、n，使得s=mb,t=nb，則us+vt=umb+vnb=(um+vn)b故b|us+vt。

2.模運算

設(shè)n是正整數(shù)，a是整數(shù)，如果用n去除a，得商為q，余數(shù)為r，則可以表示為：us+vt=umb+vnb=(um+vn)b用amodn表示余數(shù)r，則r≡a（modn）。例如：令a=17，n=5,則17=3×5+2，r=2≡17mod5

3.同余

設(shè)n是正整數(shù)，a,b是整數(shù)，如果amodn≡bmodn，則稱整數(shù)a和b模n同余，記為a≡bmodn。

顯然，a≡b

（modn），則n|(a-b).

例如：a=17,b=-8,n=5,因為17=3×5+2,-8=-2×5+2,則17mod5≡-8mod5，通常記為：

17≡-8mod5.

4.歐幾里德除法

設(shè)a、b是整數(shù)，則a、b的所有公因數(shù)中最大的一個公因數(shù)叫做最大公因數(shù)，通常記為gcd(a,b)。

例如，12和-18的最大公因數(shù)為6，記為gcd(12,-18)=6。

如果兩個整數(shù)的絕對值都比較小，求它們的最大公因數(shù)是比較容易的。如果兩個數(shù)都比較大，可以用廣義歐幾里德除法，也稱輾轉(zhuǎn)相除法。

在介紹歐幾里得除法前，介紹一個關(guān)于同余的性質(zhì)。

對任何非負整數(shù)a和非負整數(shù)b，設(shè)a≥b，a=bq+r，0≤r<|b|，則gcd（a，b）=gcd(b，r)。證明：設(shè)gcd（a,b）=d,則d|a,d|b,則d|a-bq即d|r.同理，設(shè)gcd(b,r)=k,則k|b,k|r,則k|bq+r,即k|a.所以，結(jié)論成立。

例如，96=28×3+12，故gcd(96,28)=gcd(28,12)=4.

又如，88=11×8+0，故gcd(88,11)=gcd(11,0)=11.

歐幾里得除法

設(shè)a,b＞0,且都為整數(shù)，進行下列計算:因為例如，求gcd(182，136)。因此gcd(182,136)=gcd(136,40)=gcd(48,8)=8

5.逆元

設(shè)m是正整數(shù)，a是整數(shù)，如果存在a′，使得a×a′≡1(mod

m)成立，則a叫模m的可逆元，a′叫a模m的逆元。

例如，設(shè)m為11，則8模11的逆元為7，因為8×7≡1(mod11)

在a和m互素的情況下，即（a,m）=1,則a的模m的逆元總是存在的，且可以用上面的輾轉(zhuǎn)相除法求得。

例如，我們知道89是素數(shù)，求60模89的逆元，可以用下面的方法。89=1×60+2960=2×29+229=14×2+11=29-14×2=29-14×(60-2×29)=29×29-14×60=(89-60)×29-14×60=89×29-60×43則等式兩端同時mod89得：60×(-43)≡1(mod89)故60模89的逆元為-43，為方便記為最小非負數(shù)，因為-43≡46(mod89)，故一般說60模89的逆元為45。

實際上，這里的逆元通常稱為乘法逆元。從后面的學(xué)習(xí)可以看到，定義不同的運算和單位元，就可能有不同情況下的逆元。

8.有限域

由于有限域涉及的知識比較多，我們按內(nèi)容的遞進關(guān)系，分成小的知識點，介紹如下。

（1）有限域的定義

非空集合元素F，若在F中定義了加和乘兩種運算，且滿足下述公理：

（1）F關(guān)于加法構(gòu)成交換群。其加法恒等元記為0。

（2）F中非零元素全體對乘法構(gòu)成交換群。其乘法恒等元（單位元）記為1。

（3）加法和乘法間有如下分配律：a×(b+c)=a×b+a×c(b+c)×a=b×a+c×a則稱F為一個域。若F中的元素個數(shù)有限，稱F為有限域(FiniteField)。有限域也叫伽羅瓦(GaloisField)域。

例如，對于非空集合F={0,1,2,3,4,5,6,7,8,9,10}，在mod11的情況下做加法和乘法運算，定義運算規(guī)則為：

加法：如果a,b∈F,則

a+b≡r(mod11),r∈F

乘法：如果a,b∈F,則

a×b≡s（mod11）,s∈F

由前面的例題易得，F(xiàn)關(guān)于加法構(gòu)成交換群，其加法恒等元為0；F中非零元素全體對乘法構(gòu)成交換群，其乘法恒等元為1；分配律也是成立的。故F在mod11的情況下做加法和乘法運算構(gòu)成有限域。其中：ci=ai+bimodp。在Zp［x］上的乘法也要求系數(shù)模p。

在實踐中，用得比較多的是Z2［x］。

例如：這8個域元素的系數(shù)為(000,001,010,011,100,101,110,111)

6）有限域元素加運算

要計算兩個域元素的和，可進行多項式相加（這里是在Z2［x］中的加法，系數(shù)是模2加）。例：(x2+1)＋(x2+x+1)=2x2+x+2≡xmod（x3+x+1）

7）有限域元素乘運算

要計算兩個域元素的乘積，可進行多項式相乘，并且模x3+x+1約化（即用x3+x+1去除，找出余式）。由于是用一個三次多項式去除，余式的次數(shù)至多是2，因此余式是該域中的元素。例如：因此，在Z2［x］中，（x2+1）(x2+x+1)≡x2+xmod（x3+x+1）

AES算法描述

Rijndael是一種靈活的算法，加密明文分組塊的長度可變、密鑰長度也可變的。分組長度、密鑰長度彼此獨立地確定為128、192、256比特，因而Rijndael算法可以有9種不同的版本，而迭代次數(shù)與明文分組塊的大小和密鑰有關(guān)（如表3－3所示）。表3－3

Rijndael算法不同分組大小和密鑰長度的加密輪次Rijndael算法不像DES算法，采用包含置換操作的典型的Feistel輪結(jié)構(gòu)，而是進行多輪的替換、列混合和密鑰加操作。AES算法和Rijndael密碼算法并不完全一樣，AES算法限定了明文分組大小為128比特，而密鑰長度可為128、192、256比特，因而實際上AES有三個版本：AES－128、AES－192、AES－256，相應(yīng)的迭代輪數(shù)為10輪、12輪、14輪。AES算法是Rijndael算法的子集，但實際應(yīng)用中，術(shù)語AES和Rijndael視為等價，可以交替使用。

AES算法的加密過程是在一個4×4的字節(jié)矩陣上運作，這個矩陣又稱為“體（state）”或者“狀態(tài)”，其初值就是一個明文區(qū)塊（矩陣中一個元素單位大小就是明文區(qū)塊中的一個字節(jié)（8比特））。加密時，明文塊與子密鑰首先進行一次輪密鑰加，然后各輪AES加密循環(huán)（除最后一輪外）均包含4個步驟，其結(jié)構(gòu)如圖3－22所示。圖3－22

AES算法加密結(jié)構(gòu)

(1)字節(jié)代替（SubBytes）：通過一個非線性的替換函數(shù)，用查找表的方式把每個字節(jié)替換成對應(yīng)的字節(jié)。

(2)行移位（ShiftRows）：將矩陣中的每個橫列進行循環(huán)式移位。

(3)列混合（MixColumns）：為了充分混合矩陣中各個直行的操作，這個步驟使用線性轉(zhuǎn)換來混合每行內(nèi)的四個字節(jié)。

（4）輪密鑰加（AddRoundKey）：矩陣中的每一個字節(jié)都與該次循環(huán)的子密鑰（roundkey）做XOR邏輯運算；每個子密鑰由密鑰生成方案產(chǎn)生。

最后一個加密循環(huán)中省略列混合（MixColumns）步驟，而以另一個輪密鑰加（AddRoundKey）取代。例如：字節(jié)‘57’（十六進制數(shù)）對應(yīng)的二進制為01010111，為GF(28)上域元素，字節(jié)‘57’對應(yīng)的多項式為x6+x4+x2+x+1。（1）b7＝0實例舉例：02·54=(00000010)·(01010100)

=(x)·(x6+x4+x2)

=x7+x5+x3≡x7+x5+x3(modp(x))

=(10101000）由上面的規(guī)則：相當(dāng)于把字節(jié)(01010100)左移一位即得（10101000）（最后一位補0）。（2）b7＝1實例舉例:02·D4=(00000010)·(11010100)

=(x)·(x7+x6+x4+x2)(modp(x))

=x8+x7+x5+x3(modp(x))≡(x4+x3+x+1)+x7+x5+x3(modp(x))≡x7+x5+x4+x+1(modp(x))多項式x7+x5+x4+x+1映射為二進制即為(10110011)。由上面的規(guī)則：先把(11010100)在字節(jié)內(nèi)左移一位即得（10101000）（最后一位補0），因為b7＝1，故（10101000）再與（00011011）異或得（10110011）。

4.GF(28)上域元素的乘法逆元

在有限域GF(28)中，域元素的乘法滿足交換律，且有單位元，并且每個域元素都有乘法逆元。在GF(28)中求乘法逆元可利用多項式的擴展的歐幾里德算法計算出來。

求次數(shù)小于8的非零多項式b(x)的乘法逆元，首先利用多項式的擴展歐幾德得算法得出兩個多項式a(x)和c(x)，使得滿足b(x)a(x)+p(x)c(x)=1，即滿足a(x)·b(x)≡1modp(x)，因此a(x)是b(x)的乘法逆元。

例如：求GF(28)上域元素“F5”(十六進制)的乘法逆元。（1）“F5”對應(yīng)二進制為11111001，則用多項式表示為b(x)=x7+x6+x5+x4+x2+1，然后計算兩個多項式a(x)和c(x)滿足:(x7+x6+x5+x4+x2+1)·a(x)+p(x)c(x)=1

(2)采用多項式的擴展歐幾里得算法按照如下步驟計算：因為(x8+x4+x3+x+1)=(x7+x6+x5+x4+x2+1)(x+1)+x2

(x7+x6+x5+x4+x2+1)=x2(x5+x4+x3+x2+1)+1所以基本變換

AES算法每次明文分組以及每次變換的中間結(jié)果分組稱為狀態(tài)（State）。狀態(tài)用以字節(jié)（8比特位）為基本構(gòu)成元素的矩陣陣列來表示，該陣列有4行，即每列為32比特，因而列數(shù)為分組長度除以32，通常記為Nb。Rijndael算法列數(shù)Nb可以取的值為4、6、8，對應(yīng)的分組長度為128、192、256比特。而AES算法的分組長度固定為128比特，以字節(jié)為基本單位轉(zhuǎn)換為狀態(tài)字節(jié)，依順序a00，a10，a20，a30，a01，…，a23，a33，前4個字節(jié)組成第1列，后四個字節(jié)組成第2列，依次類推，AES算法明文分組可以構(gòu)成一個4×4的字節(jié)矩陣，如圖3－23所示，加密結(jié)束時，輸出也是從狀態(tài)字節(jié)中按相同的順序提取。圖3－23陣列狀態(tài)

AES算法加密和解密過程中密碼密鑰（CipherKey）同樣以字節(jié)為基本單位進行計算，順序依次為k00，k10，k20，k30，k01，…，k23，k33，…，用一個4行的矩陣陣列來表示，前4個字節(jié)組成第1列，后4個字節(jié)組成第2列，依次類推，列數(shù)記為Nk。密鑰Rijndael算法和AES算法的密碼密鑰的列數(shù)Nk可以取的值為4、6、8，對應(yīng)的密鑰長度為128、192、256比特，因而密碼密鑰構(gòu)成一個4×4、4×6、4×8的密鑰字節(jié)矩陣。如圖3－24所示為192比特密鑰的密碼密鑰矩陣，其中Nk為6。圖3－24密碼密鑰陣列狀態(tài)下面我們以一個128位塊為例，開始分別介紹AES加密算法基本變換的具體過程。若示例塊是由0和1組成的，輸入的128位塊為10000000010111100110101000110110010100110010010100111010011001100110001100110101011010010000001100100000011011000010100000000110，為了表達簡潔，下面的AES算法基本變換的中間結(jié)果都用16進制來表示。則128比特二進制示例塊用16進制表示則對應(yīng)為805E6A3653253A6663356903206C2806(如表3-4所示).表3－4

AES算法實例明文分組在進行AES加密算法過程中，首先把輸入明文128比特示例塊805E6A3653253A6663356903206C2806按照AES算法規(guī)則構(gòu)成一個構(gòu)成一個4×4的字節(jié)矩陣，如圖3-25所示。圖3－25陣列狀態(tài)

1．字節(jié)變換（SubBytes）

Rijndael算法的字節(jié)變換是一個基于S盒（不像DES算法使用8個S盒）的非線性置換。如表3－5所示，它將輸入或中間態(tài)的每一個字節(jié)通過一個簡單查表操作，映射為另外一個字節(jié)。映射方法是：輸入字節(jié)前4位指定S盒的行值，后4位指定S盒的列值，行和列所確定S盒位置的元素作為輸出（如圖3－26），例如輸入字節(jié)為“03”，行值為0，列值為3，根據(jù)表3－5可以得知第0行第3列對應(yīng)的值為“7B”，輸出字節(jié)為“7B”。表3－5

S盒（十六進制）圖3－26

Rijndael算法字節(jié)代替操作例如，輸入矩陣（用十六進制表示）進入S盒替換操作，則相應(yīng)的輸出如下所示：S盒字節(jié)替代—>在上面的示例中，第1個輸入字節(jié)為“F5”，它將被S盒中第“F”行、第“5”列的元素“E6”代替，其余的輸出也用相同的方法進行代替。上面的仿射變換用矩陣可以表示如下：（3－1）（2）十六進制“46”其二進制為01000110，進行第2步的仿射變換，代入矩陣運算運行：即二進制結(jié)果為11100110，對應(yīng)十六進制結(jié)果為“E6”，與查表S盒替代操作結(jié)果一樣。

2.行移位（ShiftRows）

在Rijndael算法中，行移位操作作用于S盒的輸出。其中，狀態(tài)陣列的4個行循環(huán)以字節(jié)為基本單位進行左移，而每1行循環(huán)左移的偏移量是由明文分組的大小和所在行數(shù)共同確定的，即列數(shù)Nb和行號確定。設(shè)狀態(tài)陣列的每行用Ci來表示，那么每行偏移量如表3－6所示。圖3－27行移位操作例如，輸入矩陣（用十六進制表示）進入行移位操作，則相應(yīng)的輸出如下所示：接下來進行列混合操作。

3.列混合（MixColumns）

列混合操作可以將輸入的狀態(tài)矩陣的每列看做是有限域GF(28)上的多項式b(x)，與多項式s(x)=03x3+01x2+01x+02相乘然后模多項式x4＋1，其中多項式的系數(shù)為有限域GF(28)的運算。其方法為：令c(x)=s(x)×b(x)mod（x4＋1），因而列混合是可以表示為矩陣相乘來實現(xiàn)的，進行移位后的矩陣與固定矩陣（十六進制表示）相乘，如下所示：圖3－28列混合操作例如，輸入矩陣（用十六進制表示）進入列混合操作，則相應(yīng)的輸出如下所示：輸入矩陣輸出矩陣可以看到通過列混合操作第1列包含字節(jié)為B2、38、75、4A，經(jīng)過這些操作明文經(jīng)過幾輪迭代后高度打亂了，同時還使輸入和輸出之間的關(guān)聯(lián)變了。

4.輪密鑰加（AddRoundKey）

最后一階段是將列混合的狀態(tài)矩陣與子密鑰進行XOR邏輯運算（子密鑰是從初始密鑰派生而來的），即將輪密鑰與狀態(tài)按比特異或。輪密鑰是通過密鑰調(diào)度過程從密碼密鑰中得到的，輪密鑰長度等于分組長度。如圖3－29所示，這便完成了算法的一次迭代。

例如，輸入狀態(tài)矩陣和子密鑰矩陣（用十六進制表示）進入輪密鑰加操作，則相應(yīng)的輸出如下所示：圖3－29輪密鑰加密鑰擴展

Rijndael算法的密鑰同樣以字節(jié)為基本單位進行計算，用一個4行的矩陣陣列來表示。密鑰按照矩陣的列進行分組，密鑰比特的總數(shù)等于明文分組長度乘以輪數(shù)加1，即密鑰比特的總數(shù)＝分組長度×（輪數(shù)Round＋1）。例如當(dāng)明文分組長度為128比特和輪數(shù)Round為10時，輪密鑰長度為128×(10＋1)＝1408比特，則需要添加40個新列來進行擴充；當(dāng)明文分組為128比特和輪數(shù)Round為12時，輪密鑰長度為128×(12＋1)＝1664比特，則需要添加48個新列來進行擴充。Rijndael算法由于密碼密鑰Nk列數(shù)的不同，其密鑰擴展算法有所不同。下面給出Rijndael算法的密鑰擴展程序偽代碼。若Nk≤6，則有：KeyExpansion（byteKey[4*Nk]，W[Nb*(Nr+1)]）{for(i=0;i<Nk;i++)W[i]=(Key[4*i],Key[4*i+1],Key[4*i+2],Key[4*i+3]);

for(i=Nk;i<Nb*(Nr+1);i++)

{temp=W[i-1];if(i%Nk==0)

temp=SubByte(RotByte(temp))^Rcon[i/Nk];W[i]=W[i-Nk]^temp;

}}其中，“^”表示異或運算，Key［］表示初始密鑰列向量，W［］表示密鑰的列向量，SubBytes為小節(jié)的S盒的字節(jié)代替（如圖3－26），RotWord則是以字節(jié)為單位的向左循環(huán)移位。而Rcon［i］=(RC［i］，′00′，′00″00′)，RC［0］=′01′，RC［i］=2*(RC［i-1］)，前10輪數(shù)RC［i］的值（用十六進制表示）如表3－7所示，對應(yīng)Rcon［i］（用十六進制表示）如表3－8所示。表3－7

RC［i］表3－8

Rcon［i］圖3－30

Nk=4的密鑰擴展示意圖首先初始密鑰按照矩陣列進行分組，前4列初始密鑰記為K0，K1，K2，K3，那么新的列Ki遞歸如下：

（1）如果Ki中，i不是4的倍數(shù)，那么i列由如下等式確定：Ki=Ki-4XORKi-1

(2)如果Ki中，i是4的倍數(shù)，那么i列由如下等式確定：Ki=Ki-4XORT［Ki-1］其中T［Ki-1］是Ki-1的一種轉(zhuǎn)換形式，按以下方式實現(xiàn)：①循環(huán)地將Ki-1的元素左移位，每次一個字節(jié)，如abcd變成bcda；

②將這4個字節(jié)作為S盒的輸入，輸出新的4個字節(jié)efgh；

③計算一輪的常量r(i)=2(i-4)/4；

④這樣生成轉(zhuǎn)換后的列：［eXORr(i)，f，g，h］。

第i輪的輪密鑰組成了列K4i，K4i+1，K4i+2，K4i+3。

例如：設(shè)初始種子密鑰為K0=75356B99，K1=05613956，K2=73620531，K3=00550932，下一個子密鑰段為K4，由于i是4的倍數(shù)，所以K4計算如下：K4=K0XORT(K3)

T(K3)的計算步驟如下：

（1）循環(huán)將K3按照字節(jié)為單位左移1字節(jié)，00550932變成了55093200;

（2）將55093200作為S盒的輸入，查表得到輸出fc012363;

（3）計算常量Rcon［i］=(RC(j)，00，00，00)，RC(j)=20=01(十六進制)；

（4）將01000000與fc012363f異或運算得fd012363。

因此

T(K3)=fd012363K4=75356B99XORfd012363=883448fa密鑰選取非常簡單，從擴展密鑰中取出輪密鑰：第一個輪密鑰由擴展密鑰的第一個Nb個字（其實就是Nb列），第二個輪密鑰由接下來的Nb個字組成，以此類推。其結(jié)構(gòu)如圖3－31所示。圖3－31輪密鑰選擇解密過程

AES算法解密過程中的基本運算，除了輪密鑰加AddRoundKey與AES加密算法中一樣，其它基本運算字節(jié)替代（SubBytes）、行移位（ShiftRows）、列混合（MixColumns）都要求逆，解密過程中的基本運算為逆字節(jié)替代（InvSubBytes）、逆行移位（InvShiftRows）、逆列混合（InvMixColumns）。下面簡要介紹一下解密過程中的基本運算，其解密結(jié)構(gòu)如圖3－32所示。圖3－32

AES算法解密結(jié)構(gòu)1．逆字節(jié)代替（InvSubBytes）

Rijndael算法的逆字節(jié)變換（InvSubBytes）是與字節(jié)替代一樣，它將輸入或中間態(tài)的每一個字節(jié)通過一個簡單查表操作，只是查表操作變?yōu)椴槟鍿盒，如表3－9所示。映射方法是：輸入字節(jié)前4位指定逆S盒的行值，后4位指定逆S盒的列值，行和列所確定逆S盒位置的元素作為輸出。表3－9逆S盒（十六進制）

同樣，Rijndael的逆S盒替代操作也包括兩個變換，其變換順序與S盒剛好相反，先進行仿射變換的逆變換，然后進行求逆運算：

（1）在GF(2)上進行下面的仿射變換，每個字節(jié)可以依次記為（b7，b6，b5，b4，b3，b2，b1，b0），依次做下面的仿射變換：其中di是指字節(jié)（05=00000101）中的第i位的值。上面逆仿射變換用矩陣可以表示如下：

2.逆行移位（InvShiftRows）

在Rijndael算法中，逆行移位操作與行移位操作相反，行移位操作循環(huán)向左移，而逆行移位操作則循環(huán)向右移。若AES算法中Nb為4，即第1行循環(huán)右移0字節(jié)，第2行循環(huán)右移1字節(jié)，第3行循環(huán)右移2字節(jié)，第4行循環(huán)右移3字節(jié)，如圖3－33所示。圖3－33逆行移位操作

3.逆列混合（InvMixColumns）

逆列混合操作與列混合操作一樣，只是多項式不同，則逆列混合操作多項式d(x)=0Bx3+0Dx2+09x+0E相乘然后模x4＋1，因而逆列混合是可以表示為矩陣相乘來實現(xiàn)，輸入的矩陣與固定矩陣（十六進制表示）相乘，如下所示：圖3－34逆列混合操作具體實例

假設(shè)AES加密的明文消息為128比特，密鑰為128比特。明文示例塊十六進制表示為：805E6A3653253A6663356903206C2806，128比特初始密鑰十六進制表示為：?，F(xiàn)在我們來跟蹤AES加密算法一輪加密過程，以觀察所有操作對輸出的影響。

首先，128比特的明文塊和初始密鑰分別依次寫成4×4的狀態(tài)矩陣形式。

明文示例塊805E6A3653253A6663356903206C2806依次寫成4×4的矩陣形式為：初始密鑰也為128比特，十六進制表示為：

75356B99056139567362053100550932

則寫成4×4的矩陣形式為：接下來首先明文分組陣列與初始密鑰進行一次輪密鑰加操作，如下所示：然后進入循環(huán)迭代操作，第一步為輪密鑰加的輸出作為S盒的輸入，進行字節(jié)替代操作（如圖3－26），如下所示：第二步，S盒的輸出作為行移位的輸入，進入行移位操作（如圖3－27），如下所示：第三步，列混合（MixColumn）（如圖3－28），在GF(28)域上進行如下矩陣運算：第四步，列混合的輸出與子密鑰進行輪密鑰加，在這之前先進行密鑰擴展，得到子密鑰。設(shè)初始密鑰擴展之后下一輪子密鑰（K4、K5、K6、K7），如下：故迭代循環(huán)操作中第一輪第四步——輪密鑰加為：輸入 子密鑰 輸出根據(jù)小節(jié)密鑰擴展算法，如下計算K4：K4=K1⊕SubByte(RotByte(K3))⊕Rcon[1]第一步，對K3執(zhí)行RotByte(K3)，然后字節(jié)替代SubByte(RotByte(K3))。在密鑰擴展中，先進行RotByte操作，然后根據(jù)S盒表3－4進行替代。如下所示：明文矩陣初始密鑰輸出矩陣第二步，K4=K0SubByte(RotByte(K3))Rcon［1］，其中Rcon［1］值如表3－8所示。第三步，計算K5、K6、K7。

3.5

SMS4密碼算法

SMS4描述

繼美國將Rijndael算法作為高級加密標(biāo)準(zhǔn)(AES)、歐洲將Camellia等算法作為NESSIE分組加密標(biāo)準(zhǔn)之后，中國國家密碼管理局于2006年1月6日發(fā)布第7號公告，將我國無線局域網(wǎng)產(chǎn)品的加密算法確定為SMS4算法。這是國內(nèi)官方公布的第一個商用密碼算法。本算法是一個分組算法。該算法的分組長度為128比特，密鑰長度為128比特。加密算法與密鑰擴展算法都采用32輪非線性迭代結(jié)構(gòu)。解密算法與加密算法的結(jié)構(gòu)相同，只是輪密鑰的使用順序相反，解密輪密鑰是加密輪密鑰的逆序。

1．基本運算

SMS4算法采用以下基本運算：

表示32bit異或

<<<I表示32比特t循環(huán)左移i位圖3－35

SMS4輪函數(shù)計算圖3－36非線性變換τS盒的置換規(guī)則：輸入的前4位為行號，后4位為列號，行列交叉點處S盒列表中的數(shù)據(jù)為輸出（如表3－10），例如輸入“ef”，則行號為“e”，列號為“f”，根據(jù)表3－10，于是S盒的輸出值為“84”，即Sbox（ef）=84。

3)線性變換L

非線性變換τ的輸出是線性變換L的輸入，如圖3－37所示，設(shè)輸入為B∈Z322，輸出為C∈Z322，這里，圖3－37線性變換L表3－10

SMS4算法S盒（十六進制）算法流程圖3－38SMS4加密算法流程圖3-39SMS4密鑰擴展算法流程圖具體實例

以下為本算法ECB工作方式的運算實例，用以驗證密碼算法實現(xiàn)的正確性。其中，數(shù)據(jù)采用十六進制表示。

實例一：對一組明文用密鑰加密一次。

明文:0123456789abcdeffedcba9876543210

加密密鑰:0123456789abcdeffedcba9876543210

實例二：利用相同加密密鑰對一組明文反復(fù)加密1000000次。

明文:0123456789abcdeffedcba9876543210

加密密鑰:0123456789abcdeffedcba9876543210

密

文:595298c7c6fd271f0402f804c33d3f66 3.6其他典型的對稱密碼體制簡介

RC6對稱密碼體制

RC6是AES候選算法之一，是由Rivest、Robshaw、Sidney和Yin提交的，它可能是最簡單的AES算法，RC6是RC5的進一步改進。它的明文分組塊大小為128比特，密鑰可以為128、192或256比特，共進行20輪的加密。

RC6整個加密過程需要44個子密鑰，這些密鑰都是從初始的128比特密鑰通過一系列復(fù)雜運算而生成的。初始128比特密鑰分成四個32位字，存放在L(0)，L(1)，L(2)，L(3)[JP]四個寄存器數(shù)組中，而44個子密鑰存放在S(0)，S(1)，…，S(43)44個寄存器數(shù)組中。首先對S(0)，S(1)，…，S(43)進行初始化，密鑰生成算法中需要使用兩個自然常數(shù)，一個是e(自然對數(shù)的基數(shù))，另一個是?（黃金分割率），則子密鑰擴展算法如下：S[0]=b7e1519B(十六進制)Fori=1to43，doS[i]:=S[i-1]×9e3779B9(十六進制)A=B=i=j=0Fork=1to132，doA=S(i)=[S(i)+A+B]<<<3A=L(j)=[L(j)+A+B]<<<(A+B)i=(i+1)mod44j=(j+1)mod44

RC6加密算法作為AES候選算法，首先將128比特的明文分組劃分成4個32比特的塊，分別存放在A、B、C、D中，44個子密鑰為S(0)，S(1)，…，S(43)，其加密算法如下所示：B=B+S[0]D=D+S[1]fori=1to20do{t=(B×(2B+1))<<<5u=(D×(2D+1))<<<5A=((At)<<<u)+S[2i]C=((Cu)<<<t)+S[2i+1]

(A,B,C,D)=(B,C,D,A)}A=A+S[42]C=C+S[43]注：算法中“+”、“-”、“×”符號表示模2w的加、減、乘運算（w表示字，即232），而符號“<<<”、“”分別表示循環(huán)左移和異或操作。(A，B，C，D)=(B，C，D，A)表示賦值操作即A=B、B=C、C=D、D=A。

RC6算法20輪的加密操作中，包括了XOR邏輯運算、移位、模2w的加、減、乘運算。第i輪操作如圖3－40所示。圖3－40

RC6一輪加密結(jié)構(gòu)其中F盒執(zhí)行一個乘法和加法操作，具體定義如下：t=(B×(2B+1))<<<5u=(D×(2D+1))<<<5

RC6解密過程與加密過程不同，但是基本操作類似，也非常簡單。同樣首先將解密的128比特的密文分成4個32比特的A、B、C、D塊和44個子密鑰作為輸入，具體解密算法如下： C=C-S[43]

A=A-S[42]

fori=20downto1do

{(A,B,C,D)=(D,A,B,C)

u=(D×(2D+1))<<<5

t=(B×(2B+1))<<<5

C=((C-S[2i+1])>>>t)^u

A=((A-S[2i])>>>u)^t

}

D=D-S[1]

B=B-S[0]

Twofish對稱密碼體制

Twofish是Counterpane公司向NIST提交的一種滿足AES要求的加密算法，設(shè)計者為Schneier。Twofish采用128比特數(shù)據(jù)塊(128bitblock)，128、192、256比特可變長度密鑰。Twofish算法是進入NIST第二輪5種加密算法中的一種，它同時具有RC6和Rijndael[JP]的某些特性，與DES算法一樣，使用了16輪的Feistel結(jié)構(gòu)來加密明文，并應(yīng)用了一些特殊的操作，例如與密鑰相關(guān)的S盒和矩陣相乘操作等，下面簡單介紹一下Twofish加密算法。

Twofish加密過程中需要40個子密鑰，由初始密鑰通過復(fù)雜的密鑰生成算法而生成。其中子密鑰既要用于Feistel結(jié)構(gòu)的各輪F盒中，也用于生成與密鑰相關(guān)的S盒，因而S盒具有動態(tài)特性，使得攻擊者無法預(yù)先分析，增強了算法的安全性。

Twofish加密算法與RC6算法類似，需初始密鑰128比特，也即16字節(jié)。然后將這16字節(jié)分為4組，每組32比特，即4字節(jié)。在循環(huán)之前首先對這4組數(shù)據(jù)分別用K0、K1、K2、K3進行異或操作，稱之為inputwhitening，然后對異或后的數(shù)據(jù)分組進行計算。計算后將1-3、2-4組的數(shù)據(jù)對換，如此循環(huán)15次，再將1-3、2-4對換一次。對這4組數(shù)據(jù)分別用K4、K5、K6、K7異或操作，稱之為outputwhitening。最后將這4組數(shù)據(jù)組合成16字節(jié)的數(shù)據(jù)，也就是最后的密文，長度跟加密前的明文一樣，同樣是128比特。也是首先將明文分為4個32位的塊，每一輪加密操作都要進行一次XOR邏輯運算、單個位的移位、一個特殊的函數(shù)f以及密鑰生成。其中單輪加密如圖3－41所示。圖3－41

Twofish單輪加密操作

3.7對稱密碼體制的工作模式

ECB電子碼本模式

ECB（ElectronicCodeBook）模式亦即電子碼本模式，是最簡單的模式，直接利用加密算法分別對分組數(shù)據(jù)組加密。明文分成64比特的分組進行加密，必要時填充，每個分組用同一密鑰加密，同樣的明文分組得到相同的密文。

圖3－42演示了這種操作模式。圖3－42

ECB加密/解密運行模式假