AES演算法實現

AES演算法實現

高級加密標準

1997年9月12日NIST（National Institute of Standards and Technology）發布了徵集演算法公告，要求AES具有128比特的分組長度，並支持128，192和256比特長度的密鑰長度，並且要求AES可在全世界範圍內免費得到。

1998年6月15日，在提交的21個演算法里，有15個滿足所有必備的條件並被接納為AES的候選演算法。1999年三月，NIST舉行了「第二屆AES候選大會」，之後，在1999年8月，5個候選演算法入圍最後決賽：MARS、RC6、Rijndael、Serpent和Twofish。

2000年10月2日，Rijndael被評為高級加密標準。

說了這麼多就是告訴你Rijndael被評為AES是經過層層選拔而來的，是實至名歸。

那麼它究竟怎麼實現，才是這篇文章的重點

從上面的文字我們要知道以下幾點：

1.AES具有128比特的分組長度

2.AES有三種可選的密鑰長度

3.AES是一個迭代型密碼

好了我們在分別說一下

1.什麼是分組長度？

2.三種可選擇的密鑰長度有什麼不同？

3.什麼是迭代密碼？

1.分組長度：

說到分組長度，自然要講分組密碼

2.不同在於：

密鑰為128比特，則Nr=10

密鑰為192比特，則Nr=12

密鑰為256比特，則Nr=14

3.迭代密碼

常見的乘積密碼是迭代密碼

一個典型的迭代密碼：這種密碼要明確定義一個輪函數和一個密鑰編排方案，一個明文的加密將經過Nr輪類似的過程。

註：

乘積密碼（通過「乘積」組合密碼體制）

「乘積」要滿足：

具有相同的明文空間（密文空間）

說了這麼多，大家懂的也不用聽我瞎BB（反正這些也是教材上說的），不懂的聽我說也是不懂。。。

下面我們切入正題：

怎麼實現？

首先我們看一下最簡單的密鑰為128比特的流程圖：

注釋：

Add round key:密鑰加

Substitute bytes:位元組代換

Mix columns:列混淆

Shift rows:行移位

（只看左邊，右邊是逆過程。）

從圖中我們可以看出在10輪中

第一步：明文與密鑰加

第二步：密鑰擴展

第三步：進入第一輪

.......

最後：進入第十輪

那麼每一輪都有什麼呢？

首先我們要注意：前面的幾輪與最後一輪是不同的

前幾輪：1.密鑰加，2.位元組代換，3.行移位，4.列混淆

最後一輪：1.密鑰加，2.位元組代換，3.行移位

所以可以看出列混淆比其他的操作要少一輪！

密鑰加應該都會吧。。。

例如明文為：

密鑰為：

就是每個格子里的數對應

舉個例子就是

322b

因為是16進位數，也就是

32：00110010

2b：00101011

00011001=19

好接下來我們在解決每一輪的是如何完成這些操作的：

1.密鑰擴展

對於密鑰擴展來說就是將

應該能看懂吧。。。

這裡輸入128比特的密鑰是一位數組，每個元素是16進位，也就是8個比特，共16個元素，要擴展成44個。

2.位元組代換

位元組代換會引入一個S盒的概念，會有人問S盒在不同的演算法里是否一致，答案當然是不一樣咯。S盒的概念在SPN（代換-置換網路）中有詳細的解釋，就不多說了。（想知道的，在下一篇文章中再說吧）這裡為了方便，姑且認為這個S盒是統一的吧。

你可以選擇在演算法里一個個的輸入到二維數組中存儲，但是。。。。我比較偷懶，所以在找了一個可以計算S盒的演算法出自於論文：《AES加密演算法中的S盒及其C語言實現》

出處：AES加密演算法中的S盒及其C語言實現

有了S盒之後，那麼只需要將每次密鑰加的結果位元組代換到S盒中

舉個例子就是

以19為例，就是S盒中第1行第9列中的十六進位數為：d4

最後的結果就是

3.行移位

行移位很簡單：

無非就是第一行不變

第二行每位向左移一位

第三行每位向左移兩位

第四行每位向左移三位

4.列混淆

列混淆會複雜一點：

大家應該學過線性代數吧，所以這個就是一個行列式的計算，但是這裡還有一個多項式的域運算問題：

簡單來說也就是

Xtime就是：

D4：11000100

因為d4的二進位開頭是1

所以：

從第二位開始向左進一位在最後一位補充0

於是：

10001000

再和「1B」

10001000

00011011

結果為：

10010011=93

（如果開頭是0，那麼就直接從第二位開始向左移一位，在最後一位補0即可）

D4·02=xtime（d4）=93

D4·03=d4xtime（d4）=57

11000100

10010011

01010111=57

D4·01=d4

那麼d4對應的列混淆就是

D4·02d4·03d4·01d4·01=04

所以最後的結果就是：

好了解決了各個部分之後，我們在來分別實現代碼

C語言

1.密鑰擴展:

//KeyExpansion密鑰擴展void KeyExpansion(int sbx_tab[][16],int keys[][44]){ int Rcon[11]={0,1,2,4,8,16,32,64,128,27,54}; int past[4]; int i,j; printf("input the keys:
"); for(i=0;i<4;i++) for(j=0;j<4;j++) scanf("%x",&keys[j][i]); for(i=4;i<44;i++) { if(i%4==0){ for(j=1;j<=4;j++) past[j-1]=keys[j%4][i-1]; for(j=0;j<4;j++){ if(j==0) keys[j][i]=sbx_tab[past[j]/16][past[j]%16]^Rcon[i/4]^keys[j][i-4]; else keys[j][i]=sbx_tab[past[j]/16][past[j]%16]^keys[j][i-4]; } } else{ for(j=0;j<4;j++){ keys[j][i]=keys[j][i-4]^keys[j][i-1]; } } }}

2.位元組代換

//SubByte位元組替換void SubByte(int sbx_tab[][16],int B[][4]){ int i,j; for(i=0;i<4;i++) for(j=0;j<4;j++){ B[i][j]=B[i][j]%256; B[i][j]=sbx_tab[B[i][j]/16][B[i][j]%16]; } for(i=0;i<4;i++){ for(j=0;j<4;j++) printf("%X ",B[i][j]); printf("
"); }}

3.行移位

//ShitfRow行移位void ShiftRow(int B[][4]){ int m=1; int i,j; while(m<4){ for(i=m;i<4;i++) { int tem = B[i][0]; for (j=0;j<3;j++) B[i][j] = B[i][j+1]; B[i][3] = tem; } m++; } for(i=0;i<4;i++){ for(j=0;j<4;j++) printf("%x ",B[i][j]); printf("
"); }}

3.列混淆

int Xtime(int input){ int temp; temp=input<<1; if(input&0x80) { temp^=0x1b; } return temp;}//MixColumn列混淆void MixColumn(int input[][4]){ int i,j; int output[4][4]; for(j=0;j<4;j++) for(i=0;i<4;i++)//0x02乘法//0x03乘法//0x01乘法//0x01乘法 output[i][j]=Xtime(input[i%4][j])^(input[(i+1)%4][j]^Xtime(input[(i+1)%4][j]))^input[(i+2)%4][j]^input[(i+3)%4][j]; for(i=0;i<4;i++) for(j=0;j<4;j++) input[i][j]=output[i][j]; for(i=0;i<4;i++){ for(j=0;j<4;j++) printf("%02X ",output[i][j]); printf("
"); }}

4.加密（含密鑰加）

//加密int AES_Encrypt(int sbx_tab[][16]){ int e; int plain[4][4]; int keys[4][44]; int i,j,level; printf("
please input the plaintext to encryot information:"); for(i=0;i<4;i++) for(j=0;j<4;j++) { scanf("%X",&e); plain[j][i]=e; } getchar(); KeyExpansion(sbx_tab,keys); printf("
*********************[1]************************
"); printf("Start of [1] round:
"); for(i=0;i<4;i++){ for(j=0;j<4;j++){ plain[i][j]^=keys[i][j]; printf("%x ",plain[i][j]); } printf("
"); } printf("the Key of [1] round:
"); for(i=0;i<4;i++){ for(j=0;j<4;j++){ printf("%x ",keys[i][j]); } printf("
"); } for(level=1;level<10;level++) { printf("the SubByte of [%d] round:
",level); SubByte(sbx_tab,plain); printf("the ShiftRow of [%d] round:
",level); ShiftRow(plain); printf("the MixColumn of [%d] round:
",level); MixColumn(plain); printf("
"); printf("*********************[%d]************************
",level+1); printf("start of [%d] round:
",level+1); for(i=0;i<4;i++){ for(j=0;j<4;j++){ plain[i][j]^=keys[i][level*4+j]; printf("%x ",plain[i][j]); } printf("
"); } printf("the Keys of [%d] round is:
",level+1); for(i=0;i<4;i++){ for(j=0;j<4;j++){ printf("%x ",keys[i][level*4+j]); } printf("
"); } } printf("the SubByte of [10] round:
"); SubByte(sbx_tab,plain);//第十輪循環，注意第十輪加密沒有進行列混淆 printf("the ShiftRow of [10] round:
"); ShiftRow(plain); for(i=0;i<4;i++) for(j=0;j<4;j++) plain[i][j]^=keys[i][40+j]; printf("*******************************************
"); printf("the ciphertext is:
"); for(i=0;i<4;i++){ for(j=0;j<4;j++) printf("%x ", plain[i][j]); printf("
"); } return 0;}

5.運行加密（並列印S盒）

int main(){ int pow_tab[256]; int log_tab[256]; int mid_tab[256]; int sbx_tab[256]; int b[8]={0xf1,0xe3,0xc7,0x8f,0x1f,0x3e,0x7c,0xf8}; int i,j,k,p; //S盒生成 for(i=0,p=1;i<256;i++) { pow_tab[i]=p; log_tab[p]=i; p=p^(p<<1)^(p&0x80?0x11b:0); } for(i=0;i<256;i++) mid_tab[i]=(i?pow_tab[255-log_tab[i]]:0); for(i=0;i<256;i++) { int t=0,m=0,mid=0,tab=0; for(j=0;j<8;j++) { m=mid=(b[j]&mid_tab[i]); for(k=0;k<8;k++) { int n=(mid>>1); if(m!=(n<<1)) t++; mid=n; m=mid; } if(t%2>0) { int temp=1; for(k=0;k<j;k++) temp=temp<<1; tab+=temp; } t=0; } sbx_tab[i]=tab^0x63; } printf("***********AES_Encipher***********
"); printf("the S_Box is:"); for(i=0;i<256;i++) { if((i+16)%16==0)printf("
"); printf("%X ",sbx_tab[i]); } //將sbx_tab放入Temp_tab中去(從一維轉入二維) int Temp_tab[16][16]; for(i=0;i<256;i++) Temp_tab[i/16][i%16]=sbx_tab[i]; AES_Encrypt(Temp_tab);}

結果：

花了3天時間，每天晚上2個小時，再加上一個下午3個小時，終於弄完了，希望對大家有用。

寫完這篇文也快到3點了，困了，各位灰灰~

僅供大家借鑒，如有轉載請註明出處，謝謝大家觀看。