|
摘要：AES是美國高級加密標準算法,將在未來幾十年里代替DES在各個領域中得到廣泛應用。本文在研究分析AES加密算法原理的基礎上，著重說明算法的實現(xiàn)步驟，并結(jié)合AVR匯編語言完整地實現(xiàn)AES加密和解密。根據(jù)AES原理，提出幾種列變化的優(yōu)化算法，并根據(jù)實驗結(jié)果分析和比較它們的優(yōu)缺點。 關(guān)鍵詞：AES算法 DES AVR匯編語言 加密算法 解密算法 引 言
隨著對稱密碼的發(fā)展,DES數(shù)據(jù)加密標準算法由于密鑰長度較小(56位),已經(jīng)不適應當今分布式開放網(wǎng)絡對數(shù)據(jù)加密安全性的要求，因此1997年NIST公開征集新的數(shù)據(jù)加密標準,即AES[1]。經(jīng)過三輪的篩選,比利時Joan Daeman和Vincent Rijmen提交的Rijndael算法被提議為AES的最終算法。此算法將成為美國新的數(shù)據(jù)加密標準而被廣泛應用在各個領域中。盡管人們對AES還有不同的看法,但總體來說,AES作為新一代的數(shù)據(jù)加密標準匯聚了強安全性、高性能、高效率、易用和靈活等優(yōu)點。AES設計有三個密鑰長度:128,192,256位，相對而言，AES的128密鑰比DES的56密鑰強1021倍[2]。AES算法主要包括三個方面：輪變化、圈數(shù)和密鑰擴展。本文以128為例，介紹算法的基本原理；結(jié)合AVR匯編語言，實現(xiàn)高級數(shù)據(jù)加密算法AES。
1 AES加密、解密算法原理和AVR實現(xiàn)
AES是分組密鑰，算法輸入128位數(shù)據(jù)，密鑰長度也是128位。用Nr表示對一個數(shù)據(jù)分組加密的輪數(shù)（加密輪數(shù)與密鑰長度的關(guān)系如表1所列）。每一輪都需要一個與輸入分組具有相同長度的擴展密鑰Expandedkey(i)的參與。由于外部輸入的加密密鑰K長度有限,所以在算法中要用一個密鑰擴展程序(Keyexpansion)把外部密鑰K擴展成更長的比特串,以生成各輪的加密和解密密鑰。
1.1圈變化
AES每一個圈變換由以下三個層組成:
非線性層——進行Subbyte變換；
線行混合層——進行ShiftRow和MixColumn運算；
密鑰加層——進行AddRoundKey運算。
① Subbyte變換是作用在狀態(tài)中每個字節(jié)上的一種非線性字節(jié)轉(zhuǎn)換,可以通過計算出來的S盒進行映射。
Schange:
ldi zh,＄01;將指針指向S盒的首地址
MOV zl,r2；將要查找的數(shù)據(jù)作為指針低地址
ldtemp,z+；取出這個對應的數(shù)據(jù)
MOV r2,temp；交換數(shù)據(jù)完成查表
.
.
.
ret
② ShiftRow是一個字節(jié)換位。它將狀態(tài)中的行按照不同的偏移量進行循環(huán)移位，而這個偏移量也是根據(jù)Nb的不同而選擇的[3]。
shiftrow:;這是一個字節(jié)換位的子程序
MOV temp,r3;因為是4×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)上的多項式a(x)與固定多項式c(x)相乘的結(jié)果。b(x)=c(x)*a(x)的系數(shù)這樣計算:*運算不是普通的乘法運算,而是特殊的運算，即
b(x)=c(x)·a(x)(mod x4+1)
對于這個運算
b0=02。a0+03。a1+a2+a3
令xtime(a0)=02。a0
其中，符號“。”表示模一個八次不可約多項式的同余乘法[3]。
MOV temp,a0;這是一個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)的計算
.
.
.
xtime:;這是一個子程序
ldi temp1,＄1b
lsl temp
brcs next1;如果最高位是1,則轉(zhuǎn)移
next: ret;否則什么也不變化
next1:eor temp,temp1
rjmp next
 對于逆變化,其矩陣C要改變成相應的D,即b(x)=d(x)＊a(x)。
④ 密鑰加層運算(addround)是將圈密鑰狀態(tài)中的對應字節(jié)按位“異或”。
⑤ 根據(jù)線性變化的性質(zhì)[1],解密運算是加密變化的逆變化。這里不再詳細敘述。
1.2輪變化
對不同的分組長度，其對應的輪變化次數(shù)是不同的,如表1所列。
1.3密鑰擴展
AES算法利用外部輸入密鑰K(密鑰串的字數(shù)為Nk),通過密鑰的擴展程序得到共計4(Nr+1)字的擴展密鑰。它涉及如下三個模塊:
① 位置變換(rotword)——把一個4字節(jié)的序列[A,B,C,D]變化成[B,C,D,A]；
② S盒變換(subword)——對一個4字節(jié)進行S盒代替；
③ 變換Rcon[i]——Rcon[i]表示32位比特字[xi-1,00,00,00]。這里的x是（02），如
Rcon[1]=[01000000]；Rcon[2]=[02000000]；Rcon[3]=[04000000]……
擴展密鑰的生成：擴展密鑰的前Nk個字就是外部密鑰K；以后的字W[[ｉ]]等于它前一個字W[[i-1]]與前第Nk個字W[[i-Nk]]的“異或”,即W[[ｉ]]=W[[i-1]]W[[ｉ- Nk]]。但是若ｉ為Nk的倍數(shù),則W[ｉ]=W[i-Nk]Subword(Rotword(W[[ｉ-1]]))Rcon[i/Nk]。
程序執(zhí)行的時候,主要調(diào)用以上幾個子程序，具體實現(xiàn)如下：
Keyexpansion:
rcall rotwoed
rcall subword
rcall Rcon
.
.
.
AES的加密與解密流程如圖1所示。
圖1AES的加密和解密流程
2 AES加密、解密算法的優(yōu)化
由以上算法的流程中可以清楚地看到，整個算法中程序耗時最多的就是圈變化部分，因此對于算法的優(yōu)化也就在此；而圈變化部分可以優(yōu)化的也就是列變化。因為列變化是一個模乘同余規(guī)則。由于AES加密和解密是不對稱的,如果不對其進行優(yōu)化,會使算法的解密速度遠遠大于加密的速度[1]。
① 加密運算。對列變換（Mixcolumn）可以通過調(diào)用xtime子程序進行優(yōu)化。具體算法[1]實現(xiàn)如下:
另一種有效的優(yōu)化方法就是離線構(gòu)造一個表格，即列變化表格。這樣只要通過查表的方式就可以提高加密速度。
② 解密算法的優(yōu)化。由于解密的列變換的系數(shù)分別是09、0E、0B和0D。在AVR單片機上實現(xiàn)以上的乘法顯然是需要很多的時間,從而導致了解密的性能降低。
優(yōu)化方法一：對列變化進行分解使倍乘次數(shù)降低。
仔細研究解密矩陣的系數(shù)，不難發(fā)現(xiàn)解密矩陣和加密矩陣有著一定的聯(lián)系，即解密矩陣等于加密矩陣和一個矩陣的相乘。通過這樣的聯(lián)系，就可以對算法進行優(yōu)化：
 這樣一來,只用幾個簡單的“異或”就可以實現(xiàn)列變化，使倍乘的次數(shù)降低,提高解密的速度。
優(yōu)化方法二：構(gòu)造表格。
同加密構(gòu)造方法一樣，可以構(gòu)造四個表格T[ea]=e×a; T[9a]=9×a;T[9a]=9×a;T[ba]=b×a。這樣一來，也只需要進行查表和簡單的異或就可以完成解密的任務。雖然這種方法將增加額外的開銷,但是它卻是一種有效的方法。
3 AES加密與解密的實驗仿真
根據(jù)以上實驗步驟和優(yōu)化方法得出表2、3所列實驗結(jié)果。
設主密鑰為:000102030405060708090a0b0c0d0e0f(128bit)。
加密明文:00112233445566778899AABBCCDDEEFF。
密文:69C4E0D86A7B0430D8CDB78070B4C55A。
解密密文:69C4E0D86A7B0430D8CDB78070B4C55A。
明文:00112233445566778899AABBCCDDEEFF。
總之,AES密碼是一個非對稱密碼體制，它的解密要比加密復雜和費時。解密優(yōu)化算法沒有增加存儲空間的基礎上,以列變化為基礎進行處理，程序比原始的要小，而且節(jié)約了時間。解密優(yōu)化方法速度最快，效率最高，但要增加系統(tǒng)的存儲空間,因此它的程序也是最大的一個。
注：AES128數(shù)據(jù)加密解密程序見本刊網(wǎng)站(www.dpj.com.cn)。
結(jié)語
AES高級數(shù)據(jù)加密算法不管是從安全性、效率，還是密鑰的靈活性等方面都優(yōu)于DES數(shù)據(jù)加密算法,在今后將逐步代替DES而被廣泛應用。本文基于AVR的高速計算性能實現(xiàn)了AES算法,并結(jié)合匯編語言進行了算法的優(yōu)化。根據(jù)實際應用的具體需要，可以選用相應的方法。
參考文獻
1 宋震，等. 密碼學. 北京：中國水利水電出版社，2002
2 楊義先.現(xiàn)代密碼新理論.北京：科學出版社，2002
3 谷大武,等.高級加密標準（AES）算法—Rijndael的設計.北京：清華大學出版社，2003
4 耿德根,等.AVR單片機應用技術(shù).北京：北京航空航天大學出版社，2002
5 宋建國,等.AVR高速嵌入式單片機原理與應用.北京：北京航空航天大學出版社，2001
6 NIST. Advanced Encryption Standard (AES) .Federal Information Processing Standards Publication,2001
|
66821730(技術(shù)支持)
