AES列混合變換

1、Ri12H. !歹|打昆亨亜?chuàng)Q文u二、AES算法概述AES笄法是送代型分組密碼算法°分組長(zhǎng)度二128上匕特。密鑰長(zhǎng)度：128、192或256上匕特。圈縷I密鋼長(zhǎng)度1281<>2256圈痿俎1O1214日月文M1O 圈 迭 代Irm字節(jié)矩陣（一）字節(jié)代替變換（S盒）設(shè)128比特輸入數(shù)據(jù)mQao，a、, 3 ,嗎夕 4 » <5 ,> a7> % » d c a H I ,已"“134，已 s 0r他s“aIa】a 5a t|“2“6«1O“14IJ11“IS代替(S盒)代替變換是對(duì)字節(jié)進(jìn)行的變換。它將字節(jié)矩陣中每個(gè)字

2、節(jié)用同一個(gè)s盒變換成另 外一個(gè)字節(jié)。有限JGF(28)上元素的運(yùn)算設(shè)字節(jié)b7xy®A6x6®bc5® b4x®b3x3 ®h2x2®h)x®Ao/>,丘 <o,i例：010101110-x7® 1 甘 ®() x5® 1 x4 ®O- x3 ® 1 x2 ® 1 x® 1=x" ®ex e 1AES中面向字節(jié)的運(yùn)算加法和乘法加法：兩個(gè)字節(jié)相加，其和為兩個(gè)字節(jié)按比 特異或的結(jié)果。用“”表示。 AES面向字節(jié)的運(yùn)算加法aa(x)

3、 =a 1x1®afix6®a«3x3®z2x2,x®©©b/?(x) =Z?7x7©/j6JC6®/75x5®h4x4 ®b3x?®hc2 ®hxx®hQc(x) =e7X7®C6x6 ®c*5x5 ©CX4 ®e3X3 ©CX2 ©CXC-Qc=ai®biAES面向字節(jié)的運(yùn)算乘法乘法： 兩個(gè)字節(jié)才目乘，其積為劉應(yīng)多項(xiàng)式的乘牙只模上二元域GF(2)上的8次不可纟勺多項(xiàng)式m(x) = x

4、8 ®jc4 ®jc3 ®jv后的結(jié)采所対應(yīng)的字節(jié)。用表示。a Qx )bcmo<i m ( x 心兀)例：計(jì)算 0101011110000011解： 肉 01010111»10000011-> (x6®x4®x2 ®x® 1 >(x7®x 1) mod xs®x4®x3®x® 1=x13®x11 川対"©/田/“ mod x8©4®®%© 1=(x5©)* (xg&#

5、174;x4Gx3x01 )®(x7®x6® 1) mod Xs©x4®x3a© 1=x7®x6© 1T 11000001故 01010111«10000011=11000001字節(jié)代替變換由兩個(gè)可逆變換復(fù)合而成將非零字節(jié)變?yōu)橛邢抻騁F(29中的乘法逆, 規(guī)定0變換到其自身，即0 HOtO；對(duì)中的結(jié)果用GF上的仿射變換作用兒一n100011111如1 1rnI1100011X11 1111110001116 1°l1-11100011J1 31®0 111兒I11111000°

6、;l1"11111001 111.11耳lQ0111110|%|1 112001111LrL°JS盒結(jié)構(gòu)字節(jié)代替(s盒)變換由兩個(gè)可逆變換復(fù)合而成：(1) 將每一個(gè)字節(jié)變換為有限域GF(2*)a中的乘法逆元；|-1 a(2) 對(duì)(1)中的結(jié)果進(jìn)行固定仿射變換。丨/()疋伸J: 5(Xd) 解：因 8d = 10001101-x7 0* 1F杓用歐幾里德算法，可求得(工了0 ®X2 ®1)_J = X010 0 10 0 0ii11】1 。11 1111 1 1 1111 1 1I Irii1 o|1 1110 Ou11 1°111 ac011

7、O 1lul1111i ii00|*l|*°l l°lG 11-h ii i故(lOOQllOlf =00000010/(CXJOCXWIO ) - | 111I 0II1I 1ooil。II 1 II ° II aoii1 iio' I o II iII IIoao1ii1i L°JL°JL° 1即：5(8d)=S(10001l01 )=/(0000000再如求s (01)解： 因?yàn)?仁0000 0001利用歐幾里德算法(0000 0001) .( ? ) modm(x)即卩為11B=1由于(0000 0001) .( ?

8、)=( 11A)可以得到？ =11A,再因?yàn)?1A溢出，應(yīng)該取余，11Amod11B=1即為(01)的逆為(01)S(01)=S(0000 0001 )=f(0000 0001代入上式固定仿射得 f(0000 0001)=7c再如求s(02)解： 因?yàn)?02=0000 0010利用歐幾里德算法(0000 0010) .( ? ) modm(x即為11B=1由于(0000 0010) .( ? )=( 11A)可以得到？ =8D,即為(02)的逆為(8D)S(02)=S(0000 0010 )=f(1000 1101代入上式固定仿射得 f(1000 1101)=77AES加密中列混合的具體算法A

9、ES明文在加密過(guò)程中涉及到字節(jié)代換、行移位、列混合、輪密鑰加等過(guò)程。這里對(duì)列混合的算法做岀一些淺顯的解釋。列混合其實(shí)就是對(duì)一個(gè)狀態(tài)的每一列去乘一個(gè)矩陣，其中乘法是在有限域GF(28)內(nèi)進(jìn)行的,不可約多項(xiàng)式為 xA8+xA4+xA3+x+1如圖： bo"p 02030101 -3o bi=01020301aib?01010203az一 ba-03010102 - 呂3 先把算法代碼列出來(lái)：代碼：void AES:MixColum ns(u nsig ned char state4) /列混合un sig ned char t4;in t r,c;for(c=0; c< 4; c+

10、)/按列處理for(r=0; r<4; r+)tr = staterc; /每一列中的每一個(gè)字節(jié)拷貝到tr中for(r=0; r<4; r+)staterc = FFmul(0x02, tr)/矩陣計(jì)算，其中加法為異或a FFmul(0x03, t(r+1)%4)a FFmul(0x01, t( r+2)%4)a FFmul(0x01, t( r+3)%4);unsigned char AES:FFmul(unsigned char a, unsigned char b) /有限域 GF(2A8)上的乘法unsigned char bw4;unsigned char res=0;i

11、nt i;bw0 = b;for(i=1; i<4; i+)bwi = bwi-1<<1;if(bwi-1&0x80)bwiA=0x1b;for(i=0; i<4; i+)if(a>>i)&0x01)res A= bwi;return res;這里重點(diǎn)是有限域 GF(2A8)上的乘法。采用的算法的原理如下：1、GF(2A8) 中任何數(shù)乘 0x01 都不變2、GF(2A8)中計(jì)算乘0x02，可以分兩種情況考慮：(1)、原數(shù)值小于(1000 0000)，即0x80的時(shí)候，乘2后第8個(gè)比特不會(huì)溢岀，那么結(jié)果就是原數(shù)值左移一位；、原數(shù)值大于(1000

12、 0000)，即0x80的時(shí)候，乘2后第8個(gè)比特會(huì)溢岀，這樣計(jì)算：原數(shù)值左移一位后(乘2)再除以m( x) = xA8+xA4+xA3+x+1 (即為成除以11b )后的余數(shù)。如下圖所示*或-70Z6 占 °!J ifl JI n| o'i dI 1141 n t 呼裁舟抵JiTbK)二咚匸山汕小曲苗心 - d沁冊(cè)小d汕匕更二&車(chē)汗心站”戛I-J"如T沙藥肌盹代 ；上肚如血© d炸嚴(yán)也3、類(lèi)似第2點(diǎn)，可以得到GF08)中計(jì)算乘4、乘8的結(jié)果;4、GF(2A8)中計(jì)算乘其它數(shù)時(shí)，可以表示為乘 1、2、4、8的線性組合。根據(jù)以上幾點(diǎn)再對(duì)有限域 GF(2A8)上的乘法源代碼進(jìn)行解釋:代碼:有限域GF(2A8)上un sig ned char AES:FFmul(u nsig ned char a, un sig ned char b) /的乘法un sig ned char bw4;un sig ned char res=0;int i;bw0 = b;for(i=1; i<4; i+)/循環(huán)三次，分別