摘要 AES是美國(guó)高級(jí)加密標(biāo)準(zhǔn)算法,將在未來(lái)幾十年里代替DES在各個(gè)領(lǐng)域中得到廣泛應(yīng)用。本文在研究分析AES加密算法原理的基礎(chǔ)上,著重說(shuō)明算法的實(shí)現(xiàn)步驟,并結(jié)合AVR匯編語(yǔ)言完整地實(shí)現(xiàn)AES加密和解密。根據(jù)AES原理,提出幾種列變化的優(yōu)化算法,并根據(jù)實(shí)驗(yàn)結(jié)果分析和比較它們的優(yōu)缺點(diǎn)。

引言

隨著對(duì)稱密碼的發(fā)展,DES數(shù)據(jù)加密標(biāo)準(zhǔn)算法由于密鑰長(zhǎng)度較小(56位),已經(jīng)不適應(yīng)當(dāng)今分布式開(kāi)放網(wǎng)絡(luò)對(duì)數(shù)據(jù)加密安全性的要求,因此1997年NIST公開(kāi)征集新的數(shù)據(jù)加密標(biāo)準(zhǔn),即AES[1]。經(jīng)過(guò)三輪的篩選,比利時(shí)Joan Daeman和Vincent Rijmen提交的Rijndael算法被提議為AES的最終算法。此算法將成為美國(guó)新的數(shù)據(jù)加密標(biāo)準(zhǔn)而被廣泛應(yīng)用在各個(gè)領(lǐng)域中。盡管人們對(duì)AES還有不同的看法,但總體來(lái)說(shuō),AES作為新一代的數(shù)據(jù)加密標(biāo)準(zhǔn)匯聚了強(qiáng)安全性、高性能、高效率、易用和靈活等優(yōu)點(diǎn)。AES設(shè)計(jì)有三個(gè)密鑰長(zhǎng)度:128,192,256位,相對(duì)而言,AES的128密鑰比DES的56密鑰強(qiáng)1021倍[2]。AES算法主要包括三個(gè)方面：輪變化、圈數(shù)和密鑰擴(kuò)展。本文以128為例,介紹算法的基本原理;結(jié)合AVR匯編語(yǔ)言,實(shí)現(xiàn)高級(jí)數(shù)據(jù)加密算法AES。

1  AES加密、解密算法原理和AVR實(shí)現(xiàn)

AES是分組密鑰,算法輸入128位數(shù)據(jù),密鑰長(zhǎng)度也是128位。用Nr表示對(duì)一個(gè)數(shù)據(jù)分組加密的輪數(shù)（加密輪數(shù)與密鑰長(zhǎng)度的關(guān)系如表1所列）。每一輪都需要一個(gè)與輸入分組具有相同長(zhǎng)度的擴(kuò)展密鑰Expandedkey(i)的參與。由于外部輸入的加密密鑰K長(zhǎng)度有限,所以在算法中要用一個(gè)密鑰擴(kuò)展程序(Keyexpansion)把外部密鑰K擴(kuò)展成更長(zhǎng)的比特串,以生成各輪的加密和解密密鑰。

1.1  圈變化

　　AES每一個(gè)圈變換由以下三個(gè)層組成:
　　非線性層——進(jìn)行Subbyte變換;
　　線行混合層——進(jìn)行ShiftRow和MixColumn運(yùn)算;
　　密鑰加層——進(jìn)行AddRoundKey運(yùn)算。

①  Subbyte變換是作用在狀態(tài)中每個(gè)字節(jié)上的一種非線性字節(jié)轉(zhuǎn)換,可以通過(guò)計(jì)算出來(lái)的S盒進(jìn)行映射。

　　Schange:
　　　　ldi zh,＄01;將指針指向S盒的首地址
　　　　mov zl,r2;將要查找的數(shù)據(jù)作為指針低地址
　　　　ldtemp,z+;取出這個(gè)對(duì)應(yīng)的數(shù)據(jù)
　　　　mov r2,temp;交換數(shù)據(jù)完成查表
　　　　…
　　　　ret

②  ShiftRow是一個(gè)字節(jié)換位。它將狀態(tài)中的行按照不同的偏移量進(jìn)行循環(huán)移位,而這個(gè)偏移量也是根據(jù)Nb的不同而選擇的[3]。

　　shiftrow:;這是一個(gè)字節(jié)換位的子程序
　　　　mov temp,r3;因?yàn)槭?×4
　　　　mov r3,r7; r2 r6 r10 r14 r2 r6 r10 r14
　　　　mov r7,r11; r3 r7 r11 r15---r7 r11 r15 r3
　　　　mov r11,r15; r4 r8 r12 r17 r12 r17 r4 r8
　　　　mov r15,temp; r5 r9 r13 r18 r18 r5 r9 r13
　　　　mov temp,r4
　　　　mov temp1,r8
　　　　mov r4,r12
　　　　mov r8,r17
　　　　mov r12,temp
　　　　mov r17,temp1
　　　　mov temp,r18
　　　　mov r18,r13
　　　　mov r13,r9
　　　　mov r9,r5
　　　　mov r5,temp
　　　　ret

③  在MixColumn變換中,把狀態(tài)中的每一列看作GF(28)上的多項(xiàng)式a(x)與固定多項(xiàng)式c(x)相乘的結(jié)果。b(x)=c(x)*a(x)的系數(shù)這樣計(jì)算:*運(yùn)算不是普通的乘法運(yùn)算,而是特殊的運(yùn)算,即

　　b(x)=c(x)·a(x)(mod x4+1)

對(duì)于這個(gè)運(yùn)算

　　b0=02。a0+03。a1+a2+a3

令xtime(a0)=02。a0

其中,符號(hào)“。”表示模一個(gè)八次不可約多項(xiàng)式的同余乘法[3]。

　　　　mov temp,a0;這是一個(gè)mixcolimn子程序
　　　　rcall xtime;調(diào)用xtime程序
　　　　mov a0,temp
　　　　mov temp,a1
　　　　rcall xtime
　　　　eor a0,a1
　　　　eor a0,temp
　　　　eor a0,a2
　　　　eor a0,a3;完成b(x)的計(jì)算
　　　　…
　　xtime:;這是一個(gè)子程序
　　　　ldi temp1,＄1b
　　　　lsl temp
　　　　brcs next1;如果最高位是1,則轉(zhuǎn)移
　　next: ret;否則什么也不變化
　　next1:eor temp,temp1
　　　　rjmp next

對(duì)于逆變化,其矩陣C要改變成相應(yīng)的D,即b(x)=d(x)＊a(x)。

④  密鑰加層運(yùn)算(addround)是將圈密鑰狀態(tài)中的對(duì)應(yīng)字節(jié)按位“異或”。

⑤  根據(jù)線性變化的性質(zhì)[1],解密運(yùn)算是加密變化的逆變化。這里不再詳細(xì)敘述。

1.2  輪變化

對(duì)不同的分組長(zhǎng)度,其對(duì)應(yīng)的輪變化次數(shù)是不同的,如表1所列。

表1  AES類型與基參數(shù)的關(guān)系

1.3  密鑰擴(kuò)展

AES算法利用外部輸入密鑰K(密鑰串的字?jǐn)?shù)為Nk),通過(guò)密鑰的擴(kuò)展程序得到共計(jì)4(Nr+1)字的擴(kuò)展密鑰。它涉及如下三個(gè)模塊:

　　①  位置變換(rotword)——把一個(gè)4字節(jié)的序列[A,B,C,D]變化成[B,C,D,A];

　?、?nbsp; S盒變換(subword)——對(duì)一個(gè)4字節(jié)進(jìn)行S盒代替;

　?、?nbsp; 變換Rcon[i]——Rcon[i]表示32位比特字[xi-1,00,00,00]。這里的x是（02）,如
Rcon[1]=[01000000];Rcon[2]=[02000000];Rcon[3]=[04000000]……

擴(kuò)展密鑰的生成：擴(kuò)展密鑰的前Nk個(gè)字就是外部密鑰K;以后的字W[[ｉ]]等于它前一個(gè)字W[[i-1]]與前第Nk個(gè)字W[[i-Nk]]的“異或”,即W[[ｉ]]=W[[i-1]]?W[[ｉ- Nk]]。但是若ｉ為Nk的倍數(shù),則W[ｉ]=W[i-Nk]?Subword(Rotword(W[[ｉ-1]]))?Rcon[i/Nk]。

程序執(zhí)行的時(shí)候,主要調(diào)用以上幾個(gè)子程序,具體實(shí)現(xiàn)如下：

　　Keyexpansion:
　　　　rcall rotwoed
　　　　rcall subword
　　　　rcall Rcon
　　　　…
　　　　AES的加密與解密流程如圖1所示。

圖1  AES的加密和解密流程

2  AES加密、解密算法的優(yōu)化

由以上算法的流程中可以清楚地看到,整個(gè)算法中程序耗時(shí)最多的就是圈變化部分,因此對(duì)于算法的優(yōu)化也就在此;而圈變化部分可以優(yōu)化的也就是列變化。因?yàn)榱凶兓且粋€(gè)模乘同余規(guī)則。由于AES加密和解密是不對(duì)稱的,如果不對(duì)其進(jìn)行優(yōu)化,會(huì)使算法的解密速度遠(yuǎn)遠(yuǎn)大于加密的速度[1]。

①  加密運(yùn)算。對(duì)列變換（Mixcolumn）可以通過(guò)調(diào)用xtime子程序進(jìn)行優(yōu)化。具體算法[1]實(shí)現(xiàn)如下:

另一種有效的優(yōu)化方法就是離線構(gòu)造一個(gè)表格,即列變化表格。這樣只要通過(guò)查表的方式就可以提高加密速度。

②  解密算法的優(yōu)化。由于解密的列變換的系數(shù)分別是09、0E、0B和0D。在AVR單片機(jī)上實(shí)現(xiàn)以上的乘法顯然是需要很多的時(shí)間,從而導(dǎo)致了解密的性能降低。

優(yōu)化方法一：對(duì)列變化進(jìn)行分解使倍乘次數(shù)降低。

仔細(xì)研究解密矩陣的系數(shù),不難發(fā)現(xiàn)解密矩陣和加密矩陣有著一定的聯(lián)系,即解密矩陣等于加密矩陣和一個(gè)矩陣的相乘。通過(guò)這樣的聯(lián)系,就可以對(duì)算法進(jìn)行優(yōu)化：

這樣一來(lái),只用幾個(gè)簡(jiǎn)單的“異或”就可以實(shí)現(xiàn)列變化,使倍乘的次數(shù)降低,提高解密的速度。

優(yōu)化方法二：構(gòu)造表格。

同加密構(gòu)造方法一樣,可以構(gòu)造四個(gè)表格T[ea]=e×a; T[9a]=9×a;T[9a]=9×a;T[ba]=b×a。這樣一來(lái),也只需要進(jìn)行查表和簡(jiǎn)單的異或就可以完成解密的任務(wù)。雖然這種方法將增加額外的開(kāi)銷,但是它卻是一種有效的方法。

3  AES加密與解密的實(shí)驗(yàn)仿真

根據(jù)以上實(shí)驗(yàn)步驟和優(yōu)化方法得出表2、3所列實(shí)驗(yàn)結(jié)果。

表2  AES-128不同加密方法性能比較

設(shè)主密鑰為:000102030405060708090a0b0c0d0e0f(128bit)。
加密明文:00112233445566778899AABBCCDDEEFF。
密文:69C4E0D86A7B0430D8CDB78070B4C55A。
解密密文:69C4E0D86A7B0430D8CDB78070B4C55A。
明文:00112233445566778899AABBCCDDEEFF。

總之,AES密碼是一個(gè)非對(duì)稱密碼體制,它的解密要比加密復(fù)雜和費(fèi)時(shí)。解密優(yōu)化算法沒(méi)有增加存儲(chǔ)空間的基礎(chǔ)上,以列變化為基礎(chǔ)進(jìn)行處理,程序比原始的要小,而且節(jié)約了時(shí)間。解密優(yōu)化方法速度最快,效率最高,但要增加系統(tǒng)的存儲(chǔ)空間,因此它的程序也是最大的一個(gè)。

注：AES-128數(shù)據(jù)加密解密程序見(jiàn)本刊網(wǎng)站(www.dpj.com.cn)。

結(jié)語(yǔ)

AES高級(jí)數(shù)據(jù)加密算法不管是從安全性、效率,還是密鑰的靈活性等方面都優(yōu)于DES數(shù)據(jù)加密算法,在今后將逐步代替DES而被廣泛應(yīng)用。本文基于AVR的高速計(jì)算性能實(shí)現(xiàn)了AES算法,并結(jié)合匯編語(yǔ)言進(jìn)行了算法的優(yōu)化。根據(jù)實(shí)際應(yīng)用的具體需要,可以選用相應(yīng)的方法。

參考文獻(xiàn)

1  宋震,等. 密碼學(xué). 北京：中國(guó)水利水電出版社,2002
2  楊義先.現(xiàn)代密碼新理論.北京：科學(xué)出版社,2002
3  谷大武,等.高級(jí)加密標(biāo)準(zhǔn)（AES）算法—Rijndael的設(shè)計(jì).北京：清華大學(xué)出版社,2003
4  耿德根,等.AVR單片機(jī)應(yīng)用技術(shù).北京：北京航空航天大學(xué)出版社,2002
5  宋建國(guó),等.AVR高速嵌入式單片機(jī)原理與應(yīng)用.北京：北京航空航天大學(xué)出版社,2001
6  NIST. Advanced Encryption Standard (AES) .Federal Information Processing Standards Publication,2001