密碼學(xué)：AES的實(shí)現(xiàn)與分析-課程設(shè)計(jì)

背景說(shuō)明密碼學(xué)中的高級(jí)加密標(biāo)準(zhǔn)（AdvancedEncryptionStandard，AES），又稱高級(jí)加密標(biāo)準(zhǔn)Rijndael加密法，是美國(guó)聯(lián)邦政府采用的一種區(qū)塊加密標(biāo)準(zhǔn)。這個(gè)標(biāo)準(zhǔn)用來(lái)替代原先的DES，已經(jīng)被多方分析且廣為全世界所使用。經(jīng)過(guò)五年的甄選流程，高級(jí)加密標(biāo)準(zhǔn)由美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院（NIST）于2001年11月26日發(fā)布于FIPSPUB197，并在2002年5月26日成為有效的標(biāo)準(zhǔn)。2006年，高級(jí)加密標(biāo)準(zhǔn)已然成為對(duì)稱密鑰加密中最流行的算法之一。美國(guó)美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院(NIST)于2001年引入了AES加密算法，取代老舊的DES(數(shù)字加密標(biāo)準(zhǔn))，后者當(dāng)時(shí)應(yīng)用非常廣泛，但屢屢被證明已變得相當(dāng)脆弱。AES現(xiàn)在廣泛用于金融財(cái)務(wù)、在線交易、無(wú)線通信、數(shù)字存儲(chǔ)等領(lǐng)域，經(jīng)受了最嚴(yán)格的考驗(yàn)。AES提供128位密鑰，因此，128位AES的加密強(qiáng)度是56位DES加密強(qiáng)度的1021倍還多。假設(shè)可以制造一部可以在1秒內(nèi)破解DES密碼的機(jī)器，那么使用這臺(tái)機(jī)器破解一個(gè)128位AES密碼需要大約149億萬(wàn)年的時(shí)間。AES有一個(gè)固定的128位的塊大小和128，192或256位大小的密鑰大小，并且用128位(16字節(jié))分組加密和解密數(shù)據(jù)。與公共密鑰密碼使用密鑰對(duì)不同，對(duì)稱密鑰密碼使用相同的密鑰加密和解密數(shù)據(jù)。通過(guò)分組密碼返回的加密數(shù)據(jù)的位數(shù)與輸入數(shù)據(jù)相同。迭代加密使用一個(gè)循環(huán)結(jié)構(gòu)，在該循環(huán)中重復(fù)置換(permutations)和替換(substitutions)輸入數(shù)據(jù)。該算法為比利時(shí)密碼學(xué)家JoanDaemen和VincentRijmen所設(shè)計(jì)，結(jié)合兩位作者的名字，以Rijndael之命名之，投稿高級(jí)加密標(biāo)準(zhǔn)的甄選流程。（Rijdael的發(fā)音近于"Rhinedoll"。）AES在軟體及硬件上都能快速地加解密，相對(duì)來(lái)說(shuō)較易于實(shí)作,且只需要很少的記憶體。作為一個(gè)新的加密標(biāo)準(zhǔn),目前正被部署應(yīng)用到更廣大的范圍。

系統(tǒng)展示圖2.1圖2.2系統(tǒng)功能原理字節(jié)替換SubByte圖3.1行移位ShiftRow圖3.2列混合MixColumn圖3.3輪密鑰加AddRoundKey圖3.4逆字節(jié)替換InvByteSub通過(guò)逆S盒的映射變換得到。逆行移位InvShiftRow圖3.6逆列混淆InvMixColumn圖3.7加密流程圖圖3.8解密流程圖圖3.9系統(tǒng)程序設(shè)計(jì)字節(jié)替換字節(jié)代換是非線性變換，獨(dú)立地對(duì)狀態(tài)的每個(gè)字節(jié)進(jìn)行查表代換。代換表（S盒）是可逆的，由以下兩個(gè)變換合成得到：首先，將字節(jié)看作GF（28）上的元素，映射到自己的乘法逆元。b(x)=a(x)modm(x)其中m(x)=x8+x4+x3+x+1，當(dāng)a(x)=0時(shí)，其逆元素也為0，即’00’映射到自己。其次，對(duì)字節(jié)作如下的（GF（2）上的，可逆的）仿射變換，如圖4.1所示。圖4.1S盒仿射變換將從00到FF的十六進(jìn)制數(shù)經(jīng)過(guò)上述運(yùn)算就可以得到一個(gè)16*16的字節(jié)代換表，也就是用于加密的S盒。代碼：voidSubBytes(inta[4][4],ints_box[256])/*s_box[256]是s盒*/{ inti,j; for(i=0;i<4;i++) for(j=0;j<4;j++) a[i][j]=s_box[a[i][j]];}行位移行移位是根據(jù)不同的分組長(zhǎng)度將狀態(tài)矩陣中的各行進(jìn)行相應(yīng)循環(huán)移位。在加密過(guò)程中，狀態(tài)矩陣的后三行要按字節(jié)進(jìn)行左移位。在解密過(guò)程中則要進(jìn)行逆行移位，即將狀態(tài)矩陣中的后三行按字節(jié)進(jìn)行右移位。表3給出了在分組不同的情況下移位量，即在后三行的第1行要移位c1個(gè)字節(jié)，第2行要移位c2個(gè)字節(jié)，第3行要移位c3個(gè)字節(jié)。代碼：voidShiftRows(inta[4][4],intdecrypt){ inti,j,b; if(decrypt==0) {/*此時(shí)實(shí)現(xiàn)加密行移位功能*/ for(i=1;i<4;i++) { if(i==1) { j=a[i][0]; a[i][0]=a[i][1]; a[i][1]=a[i][2]; a[i][2]=a[i][3]; a[i][3]=j;} if(i==2) { j=a[i][0]; b=a[i][1]; a[i][0]=a[i][2]; a[i][1]=a[i][3]; a[i][2]=j; a[i][3]=b;} if(i==3) { j=a[i][3]; a[i][3]=a[i][2]; a[i][2]=a[i][1]; a[i][1]=a[i][0]; a[i][0]=j;} } }列混合在列混合變換中，將狀態(tài)矩陣中的一列看作在GF（28）上的多項(xiàng)式，與一個(gè)常數(shù)多項(xiàng)式c(x)相乘并模x4+1。其中，c(x)=’03’x3+’01’x2+’01’x+’02’（系數(shù)用十六進(jìn)制表示）c(x)是與x4+1互素的，因此模x4+1是可逆的。列混合預(yù)算也可寫(xiě)為矩陣乘法（圖4.3）。設(shè)b(x)=c(x)⊕a(x)，則圖4.3列混合的矩陣表示這個(gè)運(yùn)算需要做GF（28）上的乘法，代碼實(shí)現(xiàn)如下：intmul(inta,intb) { return(a!=0&&b!=0)?alog[(log[a&0xFF]+log[b&0xFF])%255]:0; }采用查對(duì)數(shù)表和反對(duì)數(shù)表的方法，可以簡(jiǎn)單方便的找到元素的逆元。代碼：voidMixColumns(inta[4][4],intb[4][4])/*b[4][4]為列混合時(shí)的固定矩陣*/{ inttemp[4][4]={0}; intd[3]={0x80,0x1B,0x02}; inti,j,m,k; for(m=0;m<4;m++) for(i=0;i<4;i++) for(j=0;j<4;j++) { if(b[i][j]==1) temp[i][m]=a[j][m]^temp[i][m]; else if(b[i][j]==2) if(a[j][m]<d[0]) temp[i][m]=(b[i][j]*a[j][m])^temp[i][m]; else { k=a[j][m]^d[0]; temp[i][m]=((b[i][j]*k)^d[1])^temp[i][m];} else {if(a[j][m]<d[0]) temp[i][m]=((a[j][m]*d[2])^a[j][m])^temp[i][m]; else { k=a[j][m]^d[0]; temp[i][m]=(((k*d[2])^d[1])^a[j][m])^temp[i][m];}}} for(i=0;i<4;i++) for(j=0;j<4;j++) a[i][j]=temp[i][j];}密鑰加密鑰加是將輪密鑰簡(jiǎn)單地與狀態(tài)進(jìn)行逐比特異或。輪密鑰由種子密鑰通過(guò)密鑰編排算法得到，輪密鑰長(zhǎng)度等于分組長(zhǎng)度Nb。代碼：voidAddRoundKey(inta[4][4],introundKey[4][4]){ inti,j; for(i=0;i<4;i++) for(j=0;j<4;j++) a[i][j]=a[i][j]^roundKey[i][j];}密鑰擴(kuò)展擴(kuò)展密鑰用數(shù)組w(Nb*(Nr+1))表示，前Nk個(gè)字是種子密鑰，其它的密鑰字通過(guò)遞歸定義生成。SubByte(w)是一個(gè)返回4個(gè)字節(jié)的函數(shù)，每個(gè)字節(jié)都是它輸入字中相應(yīng)位置字節(jié)通過(guò)S盒作用后的結(jié)果；而函數(shù)RobByte(w)返回的是這4個(gè)字節(jié)經(jīng)循環(huán)置換后的字，即將該字循環(huán)左移一個(gè)字節(jié)。擴(kuò)展密鑰的前Nk個(gè)字由種子密鑰構(gòu)成，隨后的字w[i]等于字w[i-1]經(jīng)一些變換后得到的字temp和字w[i-Nk]異或而成；而且對(duì)位置為Nk倍數(shù)的字變換中不僅運(yùn)用了循環(huán)左移變換RotByte和子字節(jié)變換SubByte，還運(yùn)用了輪常數(shù)Rcon對(duì)變換后的字temp進(jìn)行異或。對(duì)輪常數(shù)的定義為：Rocn[i]=(Rc[i],’00’,’00’,’00’);而Rc[i]便是在有限域GF(28)中的xi-1的值，即：Rc[1]=1(即’01’)Rc[i]=x?(Rc[i-1])=xi-1(即’02’?(Rc[i-1]))。代碼：voidKeyExpansion(introundkey[4][4],ints_box[256],inttemp[4][44]){ inti,j,n,m,a,b,x,y; intw[4],r[4],q[4]; for(i=0;i<4;i++) for(j=0;j<4;j++) { temp[i][j]=roundkey[i][j];} for(i=4;i<44;i++) { a=i-4;b=i-1; if(i%4!=0)/*i不是4的倍數(shù)*/ { for(j=0;j<4;j++) q[j]=temp[j][a]^temp[j][b]; for(y=0;y<4;y++) temp[y][i]=q[y];} else { for(x=0;x<4;x++) w[x]=temp[x][b]; n=w[0];/*左移一位*/ w[0]=w[1]; w[1]=w[2]; w[2]=w[3]; w[3]=n; for(j=0;j<4;j++) w[j]=s_box[w[j]];/*字節(jié)替代*/ w[0]=rcon[(i-4)/4]^w[0]; for(m=0;m<4;m++) r[m]=temp[m][a]^w[m]; for(y=0;y<4;y++) temp[y][i]=r[y]; } }}獲取RoundKey輪密鑰i（即第i個(gè)輪密鑰）由輪密鑰緩沖字W[Nb*i]到W[Nb*(i+1)-1]給出，如圖4.6所示。W0W1W2W3W4W5W6W7W8W9W10W11W12W13W14…輪密鑰0輪密鑰1……圖4.6Nb=6且Nk=4時(shí)的密鑰擴(kuò)展與輪密鑰選取代碼：voidGetRoundKey(introundKey[4][4],inttemp[4][44],intn){ inti,j; for(i=0;i<4;i++) for(j=0;j<4;j++) roundKey[i][j]=temp[i][j+4*n];}逆字節(jié)替換與字節(jié)代替類(lèi)似，逆字節(jié)代替基于逆S盒實(shí)現(xiàn)。代碼：voidInvSubBytes(inta[4][4],intInverS_box[256])/*InverS_box[256]是逆S盒*/{ inti,j; for(i=0;i<4;i++) for(j=0;j<4;j++) a[i][j]=InverS_box[a[i][j]];}逆行位移與行移位相反，逆行移位將態(tài)state的后三行按相反的方向進(jìn)行移位操作，即第0行保持不變，第1行循環(huán)向右移一個(gè)字節(jié)，第2行循環(huán)向右移動(dòng)兩個(gè)字節(jié)，第3行循環(huán)向右移動(dòng)三個(gè)字節(jié)。代碼：if(decrypt==1) {/*此時(shí)實(shí)現(xiàn)解密行移位功能*/ for(i=1;i<4;i++) { if(i==1) { j=a[i][3]; a[i][3]=a[i][2]; a[i][2]=a[i][1]; a[i][1]=a[i][0]; a[i][0]=j;} if(i==2) { j=a[i][0]; b=a[i][1]; a[i][0]=a[i][2]; a[i][1]=a[i][3]; a[i][2]=j; a[i][3]=b;} if(i==3) { j=a[i][0]; a[i][0]=a[i][1]; a[i][1]=a[i][2]; a[i][2]=a[i][3]; a[i][3]=j;} } }}逆列混合逆列混淆的處理辦法與MixColumns（）類(lèi)似，每一列都通過(guò)與一個(gè)固定的多項(xiàng)式d(x)相乘進(jìn)行交換。代碼：voidInvMixColumns(inta[4][4],intc[4][4])/*c[4][4]為逆列混合時(shí)的固定矩陣*/{ inttemp[4][4]={0}; intd[7]={0x80,0x1B,0x02,0x0e,0x0b,0x0d,0x09}; inti,j,m,n,e,k,p,q,x,y; for(m=0;m<4;m++) for(i=0;i<4;i++) for(j=0;j<4;j++) { e=a[j][m];y=a[j][m]; if(c[i][j]==d[3]) { for(n=0;n<3;n++) { if(y<d[0]) y=y*d[2]; else { k=y^d[0]; y=(k*d[2])^d[1];} if(n==0) { p=y;} else if(n==1) {q=y;} else {x=y;}} temp[i][m]=p^q^x^temp[i][m];} if(c[i][j]==d[4]) { for(n=0;n<3;n++) { if(y<d[0]) y=y*d[2]; else { k=y^d[0]; y=(k*d[2])^d[1];} if(n==0) q=y; if(n==2) x=y;} temp[i][m]=e^q^x^temp[i][m];} if(c[i][j]==d[5]) { for(n=0;n<3;n++) { if(y<d[0]) y=y*d[2]; else { k=y^d[0]; y=(k*d[2])^d[1];} if(n==1){q=y;} if(n==2){x=y;}} temp[i][m]=e^q^x^temp[i][m];} if(c[i][j]==d[6]) { for(n=0;n<3;n++) { if(y<d[0]) y=y*d[2]; else { k=y^d[0]; y=(k*d[2])^d[1];} } temp[i][m]=e^y^temp[i][m];} } for(i=0;i<4;i++) for(j=0;j<4;j++) a[i][j]=temp[i][j];}加密AES加密算法由初始輪密鑰加和Nr輪的輪變換組成，它的輸入為初始狀態(tài)矩陣和輪密鑰，執(zhí)行加密算法后產(chǎn)生一個(gè)輸出狀態(tài)矩陣，輸入明文和輸出密文均為128比特。代碼：voidEncrypt(inta[4][4],introundKey[4][4],inttemp[4][44]){ inti,j,n; intdecrypt=0; AddRoundKey(a,roundKey);/*輪密鑰加*/ for(n=1;n<=10;n++) { if(n==10) { SubBytes(a,s_box);/*字節(jié)替代*/ ShiftRows(a,decrypt);/*行移位*/ GetRoundKey(roundKey,temp,n);/*獲取輪密鑰*/ printf("\n"); printf("第%d輪加密密鑰為：\n",n); for(i=0;i<4;i++) { for(j=0;j<4;j++) { if(roundKey[i][j]<16) printf("0%x",roundKey[i][j]); else printf("%x",roundKey[i][j]);} printf("\n");} printf("\n\n"); AddRoundKey(a,roundKey);/*輪密鑰加*/ printf("\n"); printf("第10輪加密結(jié)果為:\n"); for(i=0;i<4;i++) { for(j=0;j<4;j++) { if(a[i][j]<16) printf("0%x",a[i][j]); else printf("%x",a[i][j]);} printf("\n");} printf("第10輪加密結(jié)束\n"); printf("\n\n"); } else { SubBytes(a,s_box);/*字節(jié)替代*/ ShiftRows(a,decrypt);/*行移位*/ MixColumns(a,b);/*列混合*/ GetRoundKey(roundKey,temp,n);/*獲取輪密鑰*/ printf("\n"); printf("第%d輪加密密鑰為：\n",n); for(i=0;i<4;i++) { for(j=0;j<4;j++) { if(roundKey[i][j]<16) printf("0%x",roundKey[i][j]); else printf("%x",roundKey[i][j]);} printf("\n");} printf("\n\n"); AddRoundKey(a,roundKey);/*輪密鑰加*/ printf("\n"); printf("第%d輪加密結(jié)果為:\n",n); for(i=0;i<4;i++) { for(j=0;j<4;j++) { if(a[i][j]<16) printf("0%x",a[i][j]); else printf("%x",a[i][j]);} printf("\n");} printf("第%d輪加密結(jié)束\n",n); printf("\n\n"); } }}解密解密算法和加密算法類(lèi)似，只是在解密算法中使用的變換為加密時(shí)相應(yīng)變換的逆變換，并且在第一輪到地Nr-1輪之間逆字節(jié)替代與逆行移位，逆列混合和逆輪密鑰加交換了位置。代碼：voidDecrypt(inta[4][4],introundKey[4][4],inttemp[4][44]){ inti,j,n,m; intdecrypt=1; intr[10]={0,9,8,7,6,5,4,3,2,1}; m=10; GetRoundKey(roundKey,temp,m); AddRoundKey(a,roundKey); for(n=1;n<=10;n++) { if(n==10) { ShiftRows(a,decrypt); InvSubBytes(a,Invers_box); m=0; GetRoundKey(roundKey,temp,m); printf("\n"); printf("第10輪解密密鑰為：\n"); for(i=0;i<4;i++) { for(j=0;j<4;j++) { if(roundKey[i][j]<16) printf("0%x",roundKey[i][j]); else printf("%x",roundKey[i][j]);} printf("\n");} printf("\n\n"); AddRoundKey(a,roundKey); printf("\n"); printf("第10輪解密結(jié)果為:\n"); for(i=0;i<4;i++) { for(j=0;j<4;j++) { if(a[i][j]<16) printf("0%x",a[i][j]); else printf("%x",a[i][j]);} printf("\n");} printf("第10輪解密結(jié)束\n"); printf("\n\n");} else {ShiftRows(a,decrypt); InvSubBytes(a,Invers_box); m=r[n]; GetRoundKey(roundKey,temp,m); printf("\n"); printf("第%d輪解密密鑰為：\n",n); for(i=0;i<4;i++) { for(j=0;j<4;j++) { if(roundKey[i][j]<16) printf("0%x",roundKey[i][j]); else printf("%x",roundKey[i][j]);} printf("\n");} printf("\n\n"); AddRoundKey(a,roundKey); InvMixColumns(a,c); printf("\n"); printf("第%d輪解密結(jié)果為:\n",n); for(i=0;i<4;i++) { for(j=0;j<4;j++) { if(a[i][j]<16) printf("0%x",a[i][j]); else printf("%x",a[i][j]);} printf("\n");} printf("第%d輪解密結(jié)束\n",n); printf("\n\n"); } }}總結(jié)與分析在選擇課程設(shè)計(jì)題目的時(shí)候，當(dāng)看到“DES的實(shí)現(xiàn)與分析”這個(gè)課題的時(shí)候，我就非常想選，因?yàn)镈ES歷史悠久，而且參考的資料也非常多。到考慮到隨著時(shí)代的發(fā)展，DES被窮舉破解的