對(duì)稱(chēng)分組密碼(中AES)

密碼學(xué)

第四講對(duì)稱(chēng)分組密碼AESwzy@武漢大學(xué)高級(jí)加密標(biāo)準(zhǔn)AESAES的概況總體結(jié)構(gòu)AES數(shù)學(xué)基礎(chǔ)算法描述算法的實(shí)現(xiàn)安全性及評(píng)價(jià)補(bǔ)充內(nèi)容：AES數(shù)學(xué)基礎(chǔ)代數(shù)群、環(huán)、域模運(yùn)算與剩余類(lèi)多項(xiàng)式運(yùn)算F2運(yùn)算代數(shù)結(jié)構(gòu)除法與余數(shù)剩余類(lèi)定義比n小的非負(fù)整數(shù)集合為Zn：Zn＝{0，1，…，（n－1）}該集合被稱(chēng)為剩余類(lèi)集，或模n的剩余類(lèi)。

Zn是有乘法單位元的交換環(huán)。模8運(yùn)算模7運(yùn)算剩余類(lèi)Zn是有乘法單位元的交換環(huán)。n為素?cái)?shù)時(shí)，Zn中的每個(gè)非零元素都有乘法逆元，構(gòu)成有限域。有限域的階（元素的個(gè)數(shù)）必須是素?cái)?shù)的冪pn，n為正整數(shù)，記為GF(pn)Z7對(duì)于模7的加法和乘法構(gòu)成有限域GF(7)Z8對(duì)于模2的多項(xiàng)式加法和乘法構(gòu)成有限域GF(23)多項(xiàng)式運(yùn)算n次多項(xiàng)式多項(xiàng)式加法乘法12AES數(shù)學(xué)基礎(chǔ)二元域F2運(yùn)算舉例+：0+0=0，0+1=1*：1*1=1/：1-1=1系數(shù)在二元域中的多項(xiàng)式運(yùn)算既約多項(xiàng)式域F上的多項(xiàng)式f（x）被稱(chēng)為不可約的（既約的）當(dāng)且僅當(dāng)f（x）不能表示為兩個(gè)多項(xiàng)式的積（兩個(gè)多項(xiàng)式都在F上，次數(shù)都低于f(x)的次數(shù)）。與整數(shù)相似,一個(gè)不可約多項(xiàng)式也被稱(chēng)為素多項(xiàng)式。如GF(2)上的多項(xiàng)式f(x)＝x4＋1是可約的因?yàn)閤4＋1＝（x+1）（x3+x2+x+1）

使用有限域GF(2n)的動(dòng)機(jī)與給定的二進(jìn)制位數(shù)所能表達(dá)的信息對(duì)應(yīng)易于軟硬件實(shí)現(xiàn)

但是，以2n為模的運(yùn)算不一定構(gòu)成有限域，如模8運(yùn)算。非零元素1234567在Z8中的出現(xiàn)次數(shù)48412484在GF(23)中的出現(xiàn)次數(shù)7777777模8運(yùn)算GF(23)運(yùn)算GF(pn)運(yùn)算有限域GF(pn)的構(gòu)造方法該運(yùn)算遵循基本代數(shù)規(guī)則中的普通多項(xiàng)式運(yùn)算規(guī)則。系數(shù)運(yùn)算以p為模，即遵循有限域Zp上的運(yùn)算規(guī)則。如果乘法運(yùn)算的結(jié)果是次數(shù)大于n-1的多項(xiàng)式，那么必須將其除以某個(gè)次數(shù)為n的既約多項(xiàng)式m(x)并取余式。對(duì)于多項(xiàng)式f(x)，這個(gè)余數(shù)可表示為r(x)=f(x)modm(x)。GF(23)運(yùn)算選擇一個(gè)3次既約多項(xiàng)式只有兩個(gè)滿(mǎn)足條件的多項(xiàng)式：x3+x2+1和x3+x+1本例中選擇既約多項(xiàng)式x3+x+1生成元為010階為q的有限域F的生成元是一個(gè)元素，記作g，該元素的前q－1個(gè)冪構(gòu)成了F的所有非零元素，即域F的元素為0，g0，…，gq-2。一個(gè)不可約多項(xiàng)式的根g是這個(gè)不可約多項(xiàng)式定義的有限域的生成元，即f(g)=0

GF(23)運(yùn)算22AES數(shù)學(xué)基礎(chǔ)GF(28)

運(yùn)算GF(2)上的多項(xiàng)式運(yùn)算,模11B：x8+x4+x3+x+

1舉例+：(x2+1)+(x+1)=x2+x*：(x4+1)*(x4+x)=x8+x5+x4+x=x5+x3+1/：x*(x7+x3+x2+1)=x8+x4+x3+x=1映射：101+011=110，10001*10010=10100123AES數(shù)學(xué)基礎(chǔ)F28上的多項(xiàng)式運(yùn)算，模x4+1舉例：101x2+011x2=110x2，101x2*011x2=1111x4=1111AES的數(shù)學(xué)基礎(chǔ)(1)有限域GF(28)上定義了4種運(yùn)算：“+”、“·”、“·xtime”和帶系數(shù)的多項(xiàng)式乘運(yùn)算“”。對(duì)字節(jié)b，用多項(xiàng)式表示為：

b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0“+”運(yùn)算：兩個(gè)字節(jié)相加，相當(dāng)于字節(jié)的每一位簡(jiǎn)單異或。例：’57’＋’83’＝‘d4’(57)16=(01010111)2→x6+x4+x2+x+1(83)16=(10000011)2→x7+x+1’57’＋’83’→(x6+x4+x2+x+1)+(x7+x+1)=x7+x6+x4+x2→(11010100)2＝(d4)16AES的數(shù)學(xué)基礎(chǔ)(2)“·”運(yùn)算：選擇一個(gè)不可約多項(xiàng)式：m(x)=x8+x4+x3+x+1，“·”運(yùn)算為兩多項(xiàng)式相乘后進(jìn)行模m(x)的運(yùn)算。例：’57’·’83’＝‘c1’(57)16=(01010111)2→x6+x4+x2+x+1(83)16=(10000011)2→x7+x+1’57’·’83’→(x6+x4+x2+x+1)·(x7+x+1)mod(x8+x4+x3+x+1)=x13+x11+x9+x8+x7+x7+x5+x3+x2+

x+x6+x4+x2+x+1)mod(x8+x4+x3+x+1)

=(x13+x11+x9+x8+x6+x5+x4+x3+1)mod(x8+x4+x3+x+1)

＝x7+x6+1→(11000001)2＝(c1)16(x13+x11+x9+x8+x6+x5+x4+x3+1)mod(x8+x4+x3+x+1)

:X5+x3x8+x4+x3+x+1x13+x11+x9+x8+x6+x5+x4+x3+1x13+x9+x8+x6+x5x7+x6+1x11+x4+x3+1x11+x7+x6+x4+x3AES的數(shù)學(xué)基礎(chǔ)(2)倍乘“xtime”運(yùn)算：定義為x·b(x)modm(x)。例：xtime(57)＝x（x6+x4+x2+x+1）modx8+x4+x3+x+1=x7+x5+x3+x2+x＝’AE’按定義有：等價(jià)于：AES的數(shù)學(xué)基礎(chǔ)(2)帶系數(shù)的多項(xiàng)式乘運(yùn)算“”：GF(28)上的多項(xiàng)式a(x)和b(x)相乘模x4+1的積（表示為c(x)=a(x)·b(x)x·b(x)=b2x3+b1x2+b0x1+b3modx4+1

高級(jí)加密標(biāo)準(zhǔn)AESAES的概況總體結(jié)構(gòu)AES數(shù)學(xué)基礎(chǔ)算法描述算法的實(shí)現(xiàn)安全性及評(píng)價(jià)一、AES的概況1、歷史時(shí)間：1997年美國(guó)政府向社會(huì)公開(kāi)征集高級(jí)數(shù)據(jù)加密標(biāo)準(zhǔn)（AES）；1998年8月20日從應(yīng)征的21個(gè)算法中選出15個(gè)。1999年8月又選中其中5個(gè)算法。2000年10月2日再選出1個(gè)算法。2001年11月26日接受其作為標(biāo)準(zhǔn)。2001年12月4日正式公布：FIPS－197。一、AES的概況2、AES產(chǎn)生的背景①1984年12月里根總統(tǒng)下令由國(guó)家保密局研制新密碼標(biāo)準(zhǔn)，以取代DES。②1991年新密碼開(kāi)始試用并征求意見(jiàn)。民眾要求公開(kāi)算法，并去掉法律監(jiān)督。

③1994年頒布新密碼標(biāo)準(zhǔn)（EES）。④1995年5月貝爾實(shí)驗(yàn)室的博士生M.Blaze在PC機(jī)上用45分鐘攻擊法律監(jiān)督字段獲得成功。

⑤1995年7月美國(guó)政府放棄用EES加密數(shù)據(jù)。AES產(chǎn)生的背景1997年4月15日，NIST發(fā)起征集高級(jí)加密標(biāo)準(zhǔn)（AdvancedEncryptionStandard）AES的活動(dòng)，活動(dòng)目的是確定一個(gè)非保密的、可以公開(kāi)技術(shù)細(xì)節(jié)的、全球免費(fèi)使用的分組密碼算法，作為新的數(shù)據(jù)加密標(biāo)準(zhǔn)。對(duì)AES的基本要求是：比三重DES快、至少與三重DES一樣安全；無(wú)類(lèi)別的；可公開(kāi)的；無(wú)特權(quán)的；數(shù)據(jù)分組長(zhǎng)度為128比特；密鑰長(zhǎng)度為128/192/256比特。AES產(chǎn)生的背景1998年6月NIST共收到21個(gè)提交的算法，在同年的8月首屆AES會(huì)議上指定了15個(gè)候選算法。1999年3月22日第二次AES會(huì)議上，將候選名單減少為5個(gè)，這5個(gè)算法是MARS，RC6，Rijndael，SERPENT，和Twofish。AES產(chǎn)生的背景MARS（由IBM公司研究部門(mén)的一個(gè)龐大團(tuán)隊(duì)發(fā)布，對(duì)它的評(píng)價(jià)是算法復(fù)雜、速度快、安全性高）RC6（由RSA實(shí)驗(yàn)室發(fā)布，對(duì)它的評(píng)價(jià)是極簡(jiǎn)單、速度極快、安全性低）Rijndael（由JoanDaemen和VincentRijmen兩位比利時(shí)密碼專(zhuān)家發(fā)布，對(duì)它的評(píng)價(jià)是算法簡(jiǎn)潔、速度快、安全性好）Serpent（由RossAnderson,EliBiham和LarsKnudsen發(fā)布，對(duì)它的評(píng)價(jià)是算法簡(jiǎn)潔、速度慢、安全性極高）Twofish（由Counterpane公司一個(gè)龐大的團(tuán)隊(duì)發(fā)布，對(duì)它的評(píng)價(jià)是算法復(fù)雜、速度極快、安全性高）AES產(chǎn)生的背景從全方位考慮，Rijndael匯聚了安全，性能，效率，易用和靈活等優(yōu)點(diǎn)，使它成為AES最合適的選擇2000年10月NIST宣布Rijndael算法被選為高級(jí)加密標(biāo)準(zhǔn)2001年11月發(fā)布為聯(lián)邦信息處理標(biāo)準(zhǔn)(FederalInformationProcessingStandard，F(xiàn)IPS),用于美國(guó)政府組織保護(hù)敏感信息的一種特殊的加密算法，即FIPSPUB197標(biāo)準(zhǔn)一、AES的概況⑥美國(guó)密碼政策的變化

公開(kāi)設(shè)計(jì)秘密設(shè)計(jì)公開(kāi)設(shè)計(jì)3、設(shè)計(jì)原則

①安全性：抵抗所有已知攻擊；

②實(shí)用性：適應(yīng)各種環(huán)境，速度快；

③擴(kuò)展性：分組長(zhǎng)度和密鑰長(zhǎng)度可擴(kuò)展。

DESEESAESDES和AES的比較DESAES日期1976年1999年分組大小64b128b、192b、256b密鑰長(zhǎng)度56b(有效長(zhǎng)度)128b、192b、256b(可能更長(zhǎng))加密原語(yǔ)代替、置換代替、移位、位混合算法公開(kāi)公開(kāi)設(shè)計(jì)基本原理未公開(kāi)公開(kāi)選擇過(guò)程保密保密，但接受公開(kāi)評(píng)論來(lái)源IBM,由NSA加強(qiáng)比利時(shí)密碼學(xué)家一、AES的概況4、整體特點(diǎn)

①分組密碼:明文長(zhǎng)度、密文長(zhǎng)度、密鑰長(zhǎng)度可變（128/192/256等）?，F(xiàn)在一般取128。

②面向二進(jìn)制的密碼算法:能夠加解密任何形式的計(jì)算機(jī)數(shù)據(jù)。

③不是對(duì)合運(yùn)算:加、解密使用不同的算法。④綜合運(yùn)用置換、代替、代數(shù)等多種密碼技術(shù)⑤整體結(jié)構(gòu)：基本輪函數(shù)加迭代。圈數(shù)可變，≥10分組長(zhǎng)度（bit）128192256密鑰長(zhǎng)度（bit）128192256表1.分組長(zhǎng)度和密鑰長(zhǎng)度的不同取值A(chǔ)ES算法簡(jiǎn)介AES算法的輪數(shù)和明文分組長(zhǎng)度及密鑰長(zhǎng)度的關(guān)系為：除最后一輪不做列混淆變換外，每一輪都經(jīng)過(guò)4步相同的操作：輪數(shù)明文128b明文192b明文256b密鑰128b101214密鑰192b121214密鑰256b141414Round(State,RoundKey){ByteSub(State);//S-盒

ShiftRow(State);//行循環(huán)左移

MixColumn(State);//列混淆變換

AddRoundKey(State,RoundKey);//與擴(kuò)展密鑰相異或}一、AES的概況5、應(yīng)用

①許多國(guó)際組織采用為標(biāo)準(zhǔn)。②已經(jīng)大范圍應(yīng)用。③產(chǎn)品形式：軟件（嵌入式，應(yīng)用軟件）硬件（單片，插卡） Intel指令集6、結(jié)論只有通過(guò)實(shí)際應(yīng)用的檢驗(yàn)才能證明其安全。我們相信：經(jīng)過(guò)全世界廣泛分析的AES是不負(fù)眾望的。二、總框圖128位明文初始圈密鑰加S盒變換行移位與列混淆圈密鑰加128位密文迭代控制密鑰圈密鑰產(chǎn)生圈函數(shù)AES算法中的數(shù)據(jù)結(jié)構(gòu)AES算法中進(jìn)行運(yùn)算的單位包括：1個(gè)字節(jié)1列1行用字節(jié)數(shù)組表示的整個(gè)加密塊加密塊數(shù)組中，n可以是3，5，7，所代表的加密塊分別表示128bit，192bit和256bit。ai,ja0,ja1,ja2,ja3,jai,0ai,1…ai,3a0,2a0,3a1,2a1,3a2,2a2,3a0,0a0,1a1,0a1,1a2,0a2,1a3,0a3,1a3,2a3,3…a0,n…a1,n…a2,n…a3,nAES算法中的數(shù)據(jù)結(jié)構(gòu)1、AES的數(shù)學(xué)基礎(chǔ)是有限域GF(28)一個(gè)GF(2)上的8次既約多項(xiàng)式可生成一個(gè)GF(28)GF(28)的全體元素構(gòu)成加法群，線(xiàn)性空間。GF(28)的非零元素構(gòu)成乘法循環(huán)群。GF(28)中的元素有多種表示：字節(jié)次數(shù)低于8次的多項(xiàng)式指數(shù)形式

對(duì)數(shù)形式

GF(28)的特征為2。

三、數(shù)學(xué)基礎(chǔ)有限域GF(28)上定義了4種運(yùn)算：定義3-2：“+”加法定義3-3：“·”乘法定義3-5：“·xtime”x乘定義3-8：帶系數(shù)的多項(xiàng)式乘運(yùn)算“”三、數(shù)學(xué)基礎(chǔ)49數(shù)學(xué)基礎(chǔ)GF(28)

運(yùn)算GF(2)上的多項(xiàng)式運(yùn)算,模11B：x8+x4+x3+x+

1舉例+：(x2+1)+(x+1)=x2+x*：(x4+1)*(x4+x)=x8+x5+x4+x=x5+x3+1/：x*(x7+x3+x2+1)=x8+x4+x3+x=1映射：101+011=110，10001*10010=101001三、數(shù)學(xué)基礎(chǔ)2、AES的GF(28)表示AES采用的模多項(xiàng)式生成GF(28)：

m(x)=x8+x4+x3+x+1AES采用GF(28)的多項(xiàng)式元素表示。

字節(jié)B＝b7b6b5b4b3b2b1b0可表示成GF(2)上的多項(xiàng)式：

b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x1+b0

例：字節(jié)57＝01010111的多項(xiàng)式表示：

01010111x6+x4+x2+x+1

三、數(shù)學(xué)基礎(chǔ)2、AES的GF(28)表示加法：兩元素多項(xiàng)式的系數(shù)按位模2加例2：57＋83＝D4(x6+x4+x2+x+1)⊕(x7+x+1)=x7+x6+x4+x2

乘法：兩元素多項(xiàng)式相乘，模m(x)

例3：57×83＝C1

(x6+x4+x2+x+1)×(x7+x+1)=x7+x6+1modm(x)

乘法單位元：字節(jié)01多項(xiàng)式1乘法逆元：設(shè)a(x)的逆元為b(x)，則a(x)b(x)=1modm(x)。根據(jù)Euclid算法求出。

三、數(shù)學(xué)基礎(chǔ)“·”運(yùn)算：選擇一個(gè)不可約多項(xiàng)式：m(x)=x8+x4+x3+x+1，“·”運(yùn)算為兩多項(xiàng)式相乘后進(jìn)行模m(x)的運(yùn)算。例：’57’·’83’＝‘c1’(57)16=(01010111)2→x6+x4+x2+x+1(83)16=(10000011)2→x7+x+1’57’·’83’→(x6+x4+x2+x+1)·(x7+x+1)mod(x8+x4+x3+x+1)=x13+x11+x9+x8+x7+x7+x5+x3+x2+

x+x6+x4+x2+x+1)mod(x8+x4+x3+x+1)

=(x13+x11+x9+x8+x6+x5+x4+x3+1)mod(x8+x4+x3+x+1)

＝x7+x6+1→(11000001)2＝(c1)16三、數(shù)學(xué)基礎(chǔ)(x13+x11+x9+x8+x6+x5+x4+x3+1)mod(x8+x4+x3+x+1)

:X5+x3x8+x4+x3+x+1x13+x11+x9+x8+x6+x5+x4+x3+1x13+x9+x8+x6+x5x7+x6+1x11+x4+x3+1x11+x7+x6+x4+x32、AES的GF(28)表示加法：兩元素多項(xiàng)式的系數(shù)按位模2加例2：57＋83＝D4(x6+x4+x2+x+1)⊕(x7+x+1)=x7+x6+x4+x2

乘法：兩元素多項(xiàng)式相乘，模m(x)

例3：57×83＝C1

(x6+x4+x2+x+1)×(x7+x+1)=x7+x6+1modm(x)

乘法單位元：字節(jié)01多項(xiàng)式1乘法逆元：設(shè)a(x)的逆元為b(x)，則a(x)b(x)=1modm(x)。根據(jù)Euclid算法求出。

三、數(shù)學(xué)基礎(chǔ)例：求(x7+x+1)-1modm(x)2、AES的GF(28)表示

x乘法xtime：用x乘GF(28)的元素例：

xtime(57)=x(x6+x4+x2+x+1)=x7+x5+x3+x2+x

xtime(83)=x(x7+x+1)=x8+x2+xmodm(x)=x4+x3+x2+1若x7的系數(shù)＝0，則為簡(jiǎn)單相乘：系數(shù)左移。若x7的系數(shù)＝1，則取模m(x)，加x8+x4+x3+x+1

。

三、數(shù)學(xué)基礎(chǔ)倍乘“xtime”運(yùn)算：定義為x·b(x)modm(x)。例：xtime(57)＝x（x6+x4+x2+x+1）modx8+x4+x3+x+1=x7+x5+x3+x2+x＝’AE’按定義有：等價(jià)于：三、數(shù)學(xué)基礎(chǔ)3、AES的字表示一個(gè)字＝4個(gè)字節(jié)一個(gè)字表示為系數(shù)取自GF(28)上的次數(shù)低于4次的多項(xiàng)式例：

字：57834AD157x3+83x2+4Ax+D1字加法：兩多項(xiàng)式系數(shù)按位模2加

字乘法：設(shè)a和c是兩個(gè)字，a(x)和c(x)是其字多項(xiàng)式，AES定義a和c的乘積為

b(x)=a(x)c(x)modx4+1

三、數(shù)學(xué)基礎(chǔ)60數(shù)學(xué)基礎(chǔ)F28上的多項(xiàng)式運(yùn)算+和，模x4+1定義3-7：101x2+011x2=110x2定義3-8：101x2

011x2=1111x4=1111三、數(shù)學(xué)基礎(chǔ)3、AES的字表示字乘法：設(shè)a(x)=a3x3+a2x2+a1x+a0c(x)=c3x3+c2x2+c1x+c0b(x)=b3x3+b2x2+b1x+b0則c(x)=a(x)b(x)modX4+1的系數(shù)：

c0=a0b0+a3b1+a2b2+a1b3c1=a1b0+a0b1+a3b2+a2b3c2=a2b0+a1b1+a0b2+a3b3c3=a3b0+a2b1+a1b2+a0b3

三、數(shù)學(xué)基礎(chǔ)帶系數(shù)的多項(xiàng)式乘運(yùn)算“”：GF(28)上的多項(xiàng)式a(x)和b(x)相乘模x4+1的積（表示為c(x)=a(x)b(x)注意：X4modX4+1=1,X5modX4+1=X,X6modX4+1=X2三、數(shù)學(xué)基礎(chǔ)帶系數(shù)的多項(xiàng)式乘運(yùn)算“”：GF(28)上的多項(xiàng)式a(x)和b(x)相乘模x4+1的積（表示為c(x)=a(x)b(x)modX4+1xb(x)=b2x3+b1x2+b0x1+b3modx4+1

三、數(shù)學(xué)基礎(chǔ)3、AES的字表示字乘法：寫(xiě)成矩陣形式則

c0b0b3b2b1a0c1

=b1b0b3b2a1c2b2b1b0b3a2c3b3b2b1b0a3注意：1.x4+1是可約多項(xiàng)式，字c(x)不一定有逆；2.在AES中選擇c(x)固定，且有逆。

三、數(shù)學(xué)基礎(chǔ)3、AES的字表示字x乘法：p(x)=xa(x)modx4+1寫(xiě)成矩陣形式則

p0=00

00

00

01

a0p1=01

00

00

00

a1p2=00

01

00

00

a2p3=00

00

01

00

a3注意：因?yàn)槟4+1，字x乘法相當(dāng)于字節(jié)循環(huán)移位；

三、數(shù)學(xué)基礎(chǔ)3、AES的字表示字x乘法：p(x)=xa(x)modx4+1模x4+1，字x乘法相當(dāng)于按字節(jié)循環(huán)移1個(gè)字節(jié)；推廣——字xn乘法：p(x)=xna(x)modx4+1思考：相當(dāng)于按字節(jié)循環(huán)移？個(gè)字節(jié)

三、數(shù)學(xué)基礎(chǔ)四、AES的基本變換1、AES的數(shù)據(jù)處理單位

①字節(jié)；②字；③狀態(tài)。2、狀態(tài)

①加解密過(guò)程中的中間數(shù)據(jù)。

②以字節(jié)為元素的矩陣，或二維數(shù)組。AES算法加密部分的實(shí)現(xiàn)明文分組和密鑰的組織排列方式01234567891011121314150481215913261014371115圖1：以明文分組為128bits為例組成的陣列048121591326101437111504812162015913172126101418223711151923048121620242815913172125292610141822263037111519232731圖2.以明文分組（或密鑰）為128bits、192bits、256bits為例組成的陣列四、AES的基本變換2、狀態(tài)

③符號(hào)：Nb－明密文所含的數(shù)據(jù)的字?jǐn)?shù)。

Nk－密鑰所含的數(shù)據(jù)的字?jǐn)?shù)。

Nr－迭代圈數(shù)。④例：Nb＝4時(shí)的狀態(tài)Nk＝4時(shí)的密鑰數(shù)組

a0,0a0,1a0,2a0,3k0,0k0,1k0,2k0,3a1,0a1,1a1,2a1,3k1,0k1,1k1,2k1,3a2,0a2,1a2,2a2,3k2,0k2,1k2,2k2,3a3,0a3,1a3,2a3,3k3,0k3,1k3,2k3,3

四、AES的基本變換2、狀態(tài)

⑤Nb、Nk、Nr之間的關(guān)系：

NrNb=4Nb=6Nb=8Nk=4101214Nk=6121214Nk=8141414

分組長(zhǎng)度和密鑰長(zhǎng)度均為128bits時(shí)的Rijndael加密算法框圖Data/KeyAdditionRnd0Rnd1Rnd8FinalRndKeySchedule密文Key明文四、AES的基本變換3、圈變換－加密輪函數(shù)

①標(biāo)準(zhǔn)圈變換：

Round(State,RoundKey)ByteSub(State);S盒變換

ShiftRow(State);行移位變換

MixColumn(State);列混淆變換

AddRoundKey(State,RoundKey)圈密鑰加變換四、AES的基本變換3、圈變換－加密輪函數(shù)

②最后一圈的圈變換：

Round(State,RounKey)ByteSub(State);S盒變換

ShiftRow(State);行移位變換

AddRoundKey(State,RoundKey)圈密鑰加變換注：最后一圈的圈變換中沒(méi)有列混淆變換。用偽代碼表示的Rijndael輪變換一般的輪變換Round(State,RoundKey){ByteSubstitution;ByteRotation;MixColumn;AddRounKey;}結(jié)尾輪變換FinalRound(State,RoundKey){ByteSubstituion;ByteRotation;AddRoundKey;}RijndaelRound的構(gòu)成ByteSubstitutionByteRotationMixColumn+RoundKey一般的輪變換ByteSubstitutionByteRotation+RoundKey最后一輪的輪變換四、AES的基本變換4、S盒變換ByteSub(State)

①S盒變換是AES的唯一的非線(xiàn)性變換，是AES安全的關(guān)鍵。②AES使用16個(gè)相同的S盒，DES使用8個(gè)不相同的S盒。③AES的S盒有8位輸入8位輸出，DES的S盒有6位輸入4位輸出。

S盒(AES)S盒(DES)8864四、AES的基本變換4、S盒變換ByteSub(State)

④S盒變換:a)將輸入字節(jié)用其GF(28)上的逆來(lái)代替；

b)對(duì)a)的結(jié)果作如下的仿射變換：（以x0－x7作輸入，以y0－y7作輸出。）ByteSubstitution

該變換可以用一個(gè)256字節(jié)的表來(lái)實(shí)現(xiàn)B0,0B0,1B0,2B0,3B1,0B1,1B1,2B1,3B2,0B2,1B2,2B2,3B3,0B3,1B3,2B3,3A0,0A0,1A0,2A0,3A1,0A1,1A1,2A1,3A2,0A2,1A2,2A2,3A3,0A3,1A3,2A3,3取逆仿射變換四、AES的基本變換4、S盒變換ByteSub(State)

y010001111x01y111000111x11y211100011x20y3=11110001x3+0y411111000x40y501111100x51y600111110x61y700011111x70四、AES的基本變換4、S盒變換ByteSub(State)

④S盒變換

注意：S盒變換的第一步是把字節(jié)的值用它的乘法逆來(lái)代替，是一種非線(xiàn)性變換。由于系數(shù)矩陣中每列都含有5個(gè)1，這說(shuō)明改變輸入中的任意一位，將影響輸出中的5位發(fā)生變化。由于系數(shù)矩陣中每行都含有5個(gè)1，這說(shuō)明輸出中的每一位，都與輸入中的5位相關(guān)。四、AES的基本變換5、行移位變換ShiftRow(State)①行移位變換對(duì)狀態(tài)的行進(jìn)行循環(huán)移位。②第0行不移位，第1行移C1字節(jié)，第2行移C2字節(jié)，第3行移C3字節(jié)。③C1，C2，C3按表取值

NbC1C2C341236123ByteRotation04812159132610143711150481259131101426153711循環(huán)左移1字節(jié)循環(huán)左移2字節(jié)循環(huán)左移3字節(jié)四、AES的基本變換5、行移位變換ShiftRow(State)④行移位變換屬于置換，本質(zhì)在于把數(shù)據(jù)打亂重排。⑤AES的行移位變換屬于線(xiàn)性變換。四、AES的基本變換6、列混淆變換MixColumn(State)①列混淆變換把狀態(tài)的列視為GF(28)上的多項(xiàng)式a(x)，乘以一個(gè)固定的多項(xiàng)式c(x)，并模x4+1:b(x)=a(x)c(x)modx4+1其中，c(x)=03x3+01x2+01x+02②列混淆變換屬于代替變換。③c(x)與x4+1互素，從而保證c(x)存在逆多項(xiàng)式d(x),而c(x)d(x)=1mod。只有逆多項(xiàng)式d(x)存在，才能正確進(jìn)行解密。MixColumn

這一運(yùn)算作用在每一列上A0,0A0,1A0,2A0,3A1,0A1,1A1,2A1,3A2,0A2,1A2,2A2,3A3,0A3,1A3,2A3,3B0,0B0,1B0,2B0,3B1,0B1,1B1,2B1,3B2,0B2,1B2,2B2,3B3,0B3,1B3,2B3,3×C(X)6、列混淆變換MixColumn(State)b(x)=a(x)c(x)modx4+1寫(xiě)成矩陣形式

b0=02

03

01

01

a0b1=01

02

03

01

a1b2=01

01

02

03

a2b3=03

01

01

02

a3

四、AES的基本變換MixColumn運(yùn)算舉例87F24D976E4C90EC46E74AC3A68CD8954740A34C37D4709F94E43A42EDA5A6BC×C(X)MixColumn運(yùn)算舉例87F24D976E4C90EC46E74AC3A68CD8954740A34C37D4709F94E43A42EDA5A6BC×C(X)MixColumn運(yùn)算舉例87F24D976E4C90EC46E74AC3A68CD8954740A34C37D4709F94E43A42EDA5A6BC×C(X)MixColumn運(yùn)算舉例87F24D976E4C90EC46E74AC3A68CD8954740A34C37D4709F94E43A42EDA5A6BC×C(X)7、圈密鑰加變換AddRoundKey()①

把圈密鑰與狀態(tài)進(jìn)行模2相加。②圈密鑰根據(jù)密鑰產(chǎn)生算法產(chǎn)生。③圈密鑰長(zhǎng)度等于數(shù)據(jù)塊長(zhǎng)度。

四、AES的基本變換A0,0A0,1A0,2A0,3A1,0A1,1A1,2A1,3A2,0A2,1A2,2A2,3A3,0A3,1A3,2A3,3K0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3＋B0,0B0,1B0,2B0,3B1,0B1,1B1,2B1,3B2,0B2,1B2,2B2,3B3,0B3,1B3,2B3,3A3,3＋K3,3＝B3,3(mod2)①圈密鑰根據(jù)密鑰產(chǎn)生算法通過(guò)用戶(hù)密鑰得到。②密鑰產(chǎn)生分兩步進(jìn)行：密鑰擴(kuò)展和圈密鑰選擇③密鑰擴(kuò)展將用戶(hù)密鑰擴(kuò)展為一個(gè)擴(kuò)展密鑰。④密鑰選擇從擴(kuò)展密鑰中選出圈密鑰。

五、圈密鑰生成1、密鑰擴(kuò)展①密鑰擴(kuò)展產(chǎn)生擴(kuò)展密鑰。②用一個(gè)字元素的一維數(shù)組W[Nb*(Nr+1)]表示擴(kuò)展密鑰。

③用戶(hù)密鑰放在數(shù)組最開(kāi)始的Nk個(gè)字中。④其它的字由它前面的字經(jīng)過(guò)處理后得到。⑤有Nk≤6和Nk>6兩種密鑰擴(kuò)展算法。

五、圈密鑰生成1、密鑰擴(kuò)展⑴Nk≤6的密鑰擴(kuò)展①最前面的Nk個(gè)字是由用戶(hù)密鑰填充的。②之后的每一個(gè)字W[j]等于前面的字W[j-1]與Nk個(gè)位置之前的字W[j-Nk]的異或。③而且對(duì)于Nk的整數(shù)倍的位置處的字，在異或之前，對(duì)W[j-1]進(jìn)行Rotl變換和ByteSub變換，再異或一個(gè)圈常數(shù)Rcon。

五、圈密鑰生成五、圈密鑰生成W0W1W2…WNk-1WNkWNk+1…

用戶(hù)密鑰

當(dāng)j不是Nk的整數(shù)倍時(shí):

Wj＝Wj-Nk⊕Wj-1當(dāng)j是Nk的整數(shù)倍時(shí):Wj＝Wj-Nk⊕ByteSub(Rotl(Wj-1))⊕Rcon[j/Nk];

Wi-4Wi-3Wi-2Wi-1WiByteSubstituionByteRotate+Rcons+Keyexpansion4=<i<4(Rnd+1)imod4=0imod4!=0說(shuō)明：

Rotl是一個(gè)字里的字節(jié)以字節(jié)為單位循環(huán)左移位函數(shù)，設(shè)W＝（A，B，C，D），則Rotl（W）＝（B，C，D，A）。圈常數(shù)Rcon與Nk無(wú)關(guān)，且定義為：

Rcon[i]=(RC[i],‘00’，‘

00’，‘

00’)RC[1]=‘01’RC[i]=xtime(RC[i-1])

五、圈密鑰生成密鑰擴(kuò)展K0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3K0K1K2K3K0K1K2K3K4K5K6K7+++K0K1K2K3K4K5K6K7ByteSubstitutionByteRotate+Rcon102

KeyExpansion

KeyLength<=192bit2、圈密鑰選擇

根據(jù)分組的大小，依次從擴(kuò)展密鑰中取出圈密鑰。前面的Nb個(gè)字作為圈密鑰0，接下來(lái)的Nb個(gè)字作為圈密鑰1?！?/p>

WW0W1

…WNb-1WNb…

W2Nb-1…

第一圈密鑰第二圈密鑰

五、圈密鑰生成

輪密鑰選取W0W1W2W3W4W5W6W7W8W9W10W11W12輪密鑰0輪密鑰1輪密鑰21、密鑰擴(kuò)展⑵Nk>6的密鑰擴(kuò)展說(shuō)明：與Nk≤6的密鑰擴(kuò)展相比，Nk>6的密鑰擴(kuò)展的不同之處在于：如果j被Nk除的余數(shù)＝4，則在異或之前，對(duì)W[j-1]進(jìn)行ByteSub變換。

五、圈密鑰生成106

KeyExpansion

KeyLength=256bit六、AES的加密算法AES的加密算法由以下部分組成：①一個(gè)初始圈密鑰加變換。②Nr-1圈的圈變換。③最后一圈變換。Rijndael加密及解密的標(biāo)準(zhǔn)結(jié)構(gòu)Block,KeyLength=128bitsPlaintext(128bits)ByteSubstitutionMixColumn＋Ciphertext(128bits)K0Kii=10ByteRotationfori=1to10Ciphertext(128bits)K10InvMixCoumnInvByteRotationInvByteSubstitution＋＋Ki＋Plaintext(128bits)i=9fori=9to0加密解密六、AES的加密算法Encryption(State,CipherKey)

{

KeyExpansion(CipherKey,RoundKey)AddRoundKey(State,RoundKey)For(I=1;I<Nr;I++)Round(State,RoundKey){ByteSub(State);ShiftRow(State);MixColumn(State);AddRoundKey(State,RoundKey)}六、AES的加密算法FinalRound(State,RoundKey){ByteSub(State);ShiftRow(State);AddRoundKey(State,RoundKey)；}}注意:

第一步和最后一步都用了圈密鑰加，因?yàn)槿魏螞](méi)有密鑰參與的變換都是容易被攻破的。AES算法的一般描述

算法可逆是對(duì)加密算法的基本要求。AES的加密算法不是對(duì)合運(yùn)算，解密算法與加密算法不同。AES的巧妙之處：雖然解密算法與加密算法不同，但解密算法與加密算法的結(jié)構(gòu)相同。把加密算法的基本運(yùn)變換成逆變換，便得到解密算法。

七、AES的基本逆變換AES的各個(gè)基本變換都是可逆的。1、圈密鑰加變換的逆就是其本身

(AddRoundKey)-1=AddRoundKey2、行移位變換的逆是狀態(tài)的后三行分別移位Nb-C1,Nb-C2,Nb-C3個(gè)字節(jié)。

七、AES的基本逆變換3、列混淆變換的逆因?yàn)榱谢煜儞Q是把狀態(tài)的每一列都乘以一個(gè)固定的多項(xiàng)式c(x):b(x)=a(x)c(x)modx4+1所以列混淆變換的逆就是狀態(tài)的每列都乘以c(x)的逆多項(xiàng)式d(x)：

d(x)=(c(x))-1modx4+1c(x)=03x3+01x2+01x+02d(x)=0Bx3+0Dx2+09x+0E七、AES的基本逆變換4、S盒變換的逆首先進(jìn)行逆仿射變換；再把每個(gè)字節(jié)用其在GF(28)中的逆來(lái)代替。

七、AES的基本逆變換S盒的逆仿射變換：

00100101y01x0

10010010y11x101001001y20x210100100y30x3

01010010y4⊕0＝x4

00101001y51x510010100y61x601001010y70x7

七、AES的基本逆變換5、解密的密鑰擴(kuò)展解密的密鑰擴(kuò)展與加密的密鑰擴(kuò)展不同；解密的密鑰擴(kuò)展定義如下：①加密算法的密鑰擴(kuò)展。②把InvMixColumn應(yīng)用到除第一和最后一圈外的所有圈密鑰上。七、AES的基本逆變換6、逆圈變換標(biāo)準(zhǔn)逆圈變換

Inv_Round(State,Inv_RoundKey){Inv_ByteSub(State);Inv_ShiftRow(State);Inv_MixColunm(State);AddRoundKey(State,Inv_RoundKey);}七、AES的基本逆變換6、逆圈變換最后一圈的逆變換：

Inv_FinalRound(State,Inv_RoundKey){Inv_ByteSub(State);Inv_ShiftRow(State);AddRoundKey(State,Inv_RoundKey);}

七、AES的基本逆變換八、AES的解密算法加密算法不是對(duì)合運(yùn)算：

(AES)-1≠AES解密算法的結(jié)構(gòu)與加密算法的結(jié)構(gòu)相同解密中的變換為加密算法變換的逆變換，且密鑰擴(kuò)展策略稍有不同。八、AES的解密算法Decryption(State,CipherKey){Inv_KeyExpansion(CipherKey,Inv_RoundKey);AddRoundKey(State,Inv_RoundKey);For(I=1;I<Nr;I++)Inv_Round(State,Inv_RoundKey);{Inv_ByteSub(State);Inv_ShiftRow(State);Inv_MixColumn(State);AddRoundKey(State,Inv_RoundKey；}

八、AES的解密算法Inv_FinalRound(State,Inv_RoundKey){InvByteSub(State);InvShiftRow(State);AddRoundKey(State,Inv_RoundKey)；}}九、AES的實(shí)現(xiàn)適應(yīng)多種環(huán)境，高效，方便是AES的突出優(yōu)點(diǎn)。由于AES的基本運(yùn)算由ByteSub、MixColumn、ShiftRow和AddRoundKey變換構(gòu)成，因此AES的實(shí)現(xiàn)主要是這些變換的實(shí)現(xiàn)。其中ShiftRow和AddRoundKey的實(shí)現(xiàn)比較容易，因此主要是ByteSub和MixColumn變換的實(shí)現(xiàn)問(wèn)題。有了這些基本運(yùn)算的實(shí)現(xiàn)，便可以有效地實(shí)現(xiàn)整個(gè)AES。九、AES的實(shí)現(xiàn)實(shí)現(xiàn)方法：軟件硬件軟件方法：基于算法描述基于查表

九、AES的實(shí)現(xiàn)1、基于算法描述的軟件實(shí)現(xiàn)AES的算法描述是一種程序化的描述，便于實(shí)現(xiàn)。AES的四種基本變換都比較簡(jiǎn)單，便于實(shí)現(xiàn)。用C語(yǔ)言仿照算法描述，可方便地實(shí)現(xiàn)。這種實(shí)現(xiàn)的速度不是最快的！九、AES的實(shí)現(xiàn)2、基于查表的軟件實(shí)現(xiàn)用查表實(shí)現(xiàn)算法是一種高效的軟件設(shè)計(jì)方法。。時(shí)空折換是信息科學(xué)的基本策略。用查表實(shí)現(xiàn)算法，就是用空間換取時(shí)間。目前計(jì)算機(jī)系統(tǒng)的存儲(chǔ)空間大、而且便宜，為查表實(shí)現(xiàn)算法提供了物資基礎(chǔ)。九、AES的實(shí)現(xiàn)2、基于查表的軟件實(shí)現(xiàn)①S盒的實(shí)現(xiàn)實(shí)現(xiàn)S盒變換的最快方法是，直接計(jì)算出S盒的變換的結(jié)果，并存儲(chǔ)造表，使用時(shí)時(shí)直接查表。因?yàn)锽yteSub變換是字節(jié)函數(shù)，所以表的規(guī)模不大，只含256個(gè)元素。注意：解密時(shí)用的是逆S盒，因此共需要造兩個(gè)S盒表。S盒表逆S盒表

①列混淆變換MixColumn的實(shí)現(xiàn)b(x)=a(x)c(x)modx4+1寫(xiě)成矩陣形式

b0=02

03

01

01

a0b1=01

02

03

01

a1b2=01

01

02

03

a2b3=03

01

01

02

a3主要運(yùn)算是GF(28)上的乘法GF(28)的非零元素構(gòu)成循環(huán)群，可通過(guò)加法和查表實(shí)現(xiàn)乘法。

九、AES的實(shí)現(xiàn)②列混淆變換MixColumn的實(shí)現(xiàn)注意：解密需要逆變換a(x)=b(x)d(x)modx4+1d(x)=0Bx3+0Dx2+09x+0E寫(xiě)成矩陣形式

a0=0E

0B

0D

09