在ARM微處理器上實現(xiàn)Rijndael加密算法
引 言
2000年10月2日,美國國家標準局NIST宣布,比利時密碼學(xué)家Joat Daemen和Vincent Rijmen設(shè)計的“RijndaeI算法”以安全性好、運算速度快、存儲要求低、靈活性強最終當選AES。該算法對目前的各種威脅是免疫的。這標志著信息技術(shù)有了新的安全工具,為計算機網(wǎng)絡(luò)和電子商務(wù)的發(fā)展提供了強有力的保障。
在當前數(shù)字信息技術(shù)和網(wǎng)絡(luò)技術(shù)高速發(fā)展的后PC時代,嵌入式系統(tǒng)技術(shù)已經(jīng)廣泛地滲透到科學(xué)研究、工程設(shè)計、軍事技術(shù)、各類產(chǎn)業(yè)和商業(yè)文化藝術(shù)以及人們的日常生活等方方面面中,成為目前最熱門的技術(shù)之一。
本文使用北京博創(chuàng)興業(yè)科技有限公司研制的UP-NETARM300嵌入式開發(fā)板,在ARM SDT 2.51集成開發(fā)環(huán)境下,建立基于μC/OS-Il操作系統(tǒng)的工程文件,分別調(diào)用ARM匯編程序和C程序在嵌入式微處理器上實現(xiàn)了Rijndael算法,并比較了兩者的效率。下面以分組長度和密鑰長度都是128位為例,介紹調(diào)用ARM匯編程序?qū)崿F(xiàn)加密算法的過程。本實現(xiàn)算法可以將密鑰長度擴展
到192位或256位。
1 Rijndael加密算法簡介
1.1 算法流程結(jié)構(gòu)
Rijndael加密算法的128位輸入分組用以字節(jié)為單位的正方形矩陣描述。該數(shù)組被復(fù)制到State數(shù)組。加密過程分為四個階段:密鑰擴展、輪密鑰加、Nr-1(對應(yīng)128、192、256位密鑰長度,Nr分別為10、12、14)輪變換及最后一輪變換。輪變換包括字節(jié)代換、行移位、列混淆和輪密鑰加四個過程,最后一輪變換包括字節(jié)代換、行移位和輪密鑰加三個過程。用偽C代碼表示如下:
Rijndael (State, CipherKey) {
KeyExpansion (CipherKey, ExpandKey); //密鑰擴展
AddRoundKey (State, RoundKey); //輪密鑰加
For (i=1;i<Nr;i++)
Round (State, ExpandKey+4*i); //輪變換
FinalRound (State, ExpandKey+4 * Nr); //最后一輪變換}
Round (State, RoundKey){ //輪變換
SubByte (State); //字節(jié)代換
ShiftRow(State); //行移位
MixColumn(State); //列混淆
AddRoundKey(State, RoundKey); 輪密鑰加
FinalRound(State, RoundKey) { //最后一輪變換
SubByte(State);
ShiftRow(State);
AddRoundKey(State,RoundKey);
1. 2算法所使用的主要變換
(1)字節(jié)代換SubByte
用一個簡單的查表操作代替了基于矩陣乘法的復(fù)雜仿射變換。Rijndael定義了一個16×16字節(jié)的S盒矩陣,包含8位值所能表達的256種可能的變換。把Statc中每個字節(jié)的高4位作為行值,低4位作為列值,取出S盒中對應(yīng)行列的元素作為新的字節(jié)輸出。
行移位變換ShiftRow:State的第一行保持不變,第2、3、4行分別循環(huán)左移1、2、3個字節(jié)。
(2)列混淆變換MixColumn
可表示為如下基于系數(shù)矩陣CoefMix與State的矩陣乘法:
乘積矩陣中的每個元素S'i,j是系數(shù)矩陣中一行元素CoefMix[i,k]與State矩陣中對應(yīng)一列元素State[k,j]的乘積之和。這里的加法與乘法都定義在有限域GF(28)上:加法即按位異或操作,乘法遵循GF(28)上的多項式乘法規(guī)則。
(3)密鑰擴展KeyExpanxsion
以4個字密鑰為輸入,生成44字擴展密鑰數(shù)組ω[44],為初始輪密鑰加階段和后面10輪變換提供輪密鑰。輸入密鑰直接被復(fù)制到擴展密鑰數(shù)組的前4個字,然后每次用4個字填充擴展密鑰數(shù)組余下的部分。在擴展密鑰數(shù)組中,ω[i]值依賴于ω[i-1]和ω[i-4]。ω數(shù)組中下標不是4的倍數(shù)時,ω[i]為ω[i-1]和ω[i-4]的異或。下標為4的倍數(shù)時,首先將ω[i-1]的4個字節(jié)循環(huán)左移1個字節(jié),然后利用S盒對每個字節(jié)進行字節(jié)代換,再與輪常量按位異或。輪常量是1個字,其最右邊3個字節(jié)為O,最左邊1個字節(jié)的值RC[j]與輪數(shù)j相關(guān)。RC[1]=1,RC[j]=2·RC[j-1],乘法定義在GF(28)上。RC[j]值以十六進制表示。
(4)輪密鑰加AddRoundKey
是基于State列的操作,即把State一列中的4個字節(jié)與輪密鑰RoundKey的1個字進行“異或”。
2 ARM匯編編程實現(xiàn)Rijndael算法的要點
2. 1源程序組成及功能
源程序包含main.c和ARM匯編程序Rijndael.s。main.c用C語言編寫,主要完成調(diào)用μC/OS-II函數(shù)進行系統(tǒng)初始化及I/O的全部功能,并調(diào)用Rijndael.s對明文加密。明文、密鑰及密文均在開發(fā)板顯示屏上輸出。
Rijndael.s用ARM匯編編程語言編寫,是實現(xiàn)加密算法的關(guān)鍵程序。
2. 2 Rijndael.s程序?qū)崿F(xiàn)加密算法步驟
Rijndael.s主要通過ARM匯編子程序調(diào)用完成加密算法,包括1個代碼段和1個數(shù)據(jù)段。它把算法所使用的所有變換均用同名ARM匯編子程序?qū)崿F(xiàn)。代碼段包括以下幾個模塊:
首先,進行明文、密鑰預(yù)處理。明文可以從開發(fā)板鍵盤上接收,也可以是常量或參數(shù)傳遞過來的變量。
其次,調(diào)用子程序KeyExpansion完成密鑰擴展。
第三,調(diào)用子程序AddRoLundKey完成初始輪密鑰加。
第四,輪變換。包括四個步驟:①調(diào)用于程序SubByte進行字節(jié)代換;②調(diào)用子程序ShiftRow進行行移位;③調(diào)用子程序MixColumn進行列混淆;④調(diào)用子程序Ad-dRoundKey進行輪密鑰加。本過程重復(fù)9次。
第五,最后一輪變換。包括三個步驟:①調(diào)用子程序SubByte進行字節(jié)代換;②調(diào)用子程序ShiftRow進行行移位;③調(diào)用子程序AddRoundKey進行輪密鑰加。
最后,對生成的密文進行進一步處理,即把密文視為4×4數(shù)組,將其行與列對調(diào)。
在數(shù)據(jù)段中對轉(zhuǎn)換過程中使用到的部分數(shù)據(jù)或中間變量進行了定義并初始化。如字節(jié)代換中的S盒及列混淆變換中的系數(shù)矩陣等。
2.3 ARM匯編子程序代碼設(shè)計舉例
在所有子程序中,列混淆變換和密鑰擴展的代碼設(shè)計難度較高,算法較復(fù)雜。下面是列混淆子程序的代碼設(shè)計:
MixColumn ;子程序入口
ldr r0,=State ;取變量地址
ldr r1,=CoefMix
ldr r2,=Temp ;Temp中間變量
mov r3,#0 ;i=0
loop_i ;i循環(huán)入口
mov r4,#0 ;j=0
loop_j ;j循環(huán)入口
mov r5,#0 ;k=0
loop_k ;k循環(huán)入口
mov r6,r3,lsl #2
add r6,r6,r5
ldrb r6,[r1,r6] ;讀取CoefMix[i,k]
mov r7,r5,lsl #2
add r7,r7,r4
ldrb r7,[r0,r7] ;讀取State[k,j]
loop_temp ;此循環(huán)用來計算
mov r8,r3,lsl #2
add r8,r8,r4
and r9,r6,#1
cmp r9,#1 ;判斷CoefMix[i,k]的最低位是否為1
bne notequal ;若不為1,轉(zhuǎn)向執(zhí)行
ldrb r9,[r2,r8] ;若為1,則Temp[i,j)+=State[k,j]
eor r9,r9,r7
strb r9,[r2,r8]
notequal
mov r6,r6,lsr #1 ;CoefMix[i,k]邏輯右移1位
and r9,r7,#0x80
mov r7,r7,lsl #1 ;State[k,j]邏輯左移1位
and r7,r7,#0xff
cmp r9,#0x80 ;移位后State[k,j]最高位是否為1
blt littlethan ;如不為1,轉(zhuǎn)向執(zhí)行
eor r7,r7,#0xlb ;如為1,則State[k,j]與#0xlb異或littlethan
cmp r6,#0 ;CoefMix[i,k]與0比較
bgt loop_temp ;如大于0,轉(zhuǎn)到標號loop_temp處執(zhí)行,否則讀取CoefMix[i,k+1]
add r5,r5,#1
cmp r5,#4
blt loop_k ;執(zhí)行k循環(huán)
add r4,r4,#1
cmp r4,#4
blt loop_j ;執(zhí)行j循環(huán)
add r3,r3,#1
cmp r3,#4
blt loop_I ;執(zhí)行i循環(huán)
mov r3,#0
renew ;用Temp更新State
ldrb r4,[r2,r3]
strb r4[r0,r3]
add r3,r3,#1
cmp r3,#16
blt renew
MixColumnend
mov pc,lr ;子程序返回
3 Rijndael加密算法實現(xiàn)效率比較
在調(diào)用ARM匯編程序?qū)崿F(xiàn)Rijndael加密算法之余,還在嵌入式微處理器ARM上通過調(diào)用C子程序?qū)崿F(xiàn)了Rijndael算法,同樣獲得了正確結(jié)果。表1、表2是兩種實現(xiàn)方式的空間與時間效率比較。
由表1知,ARM子程序比C子程序所占用的空間明顯小得多,前者僅為后者的55%。由表2,運行一次ARM匯編程序Rijndael.s程序完成加密算法,僅需約0.657 tick(此處,1000 tick=1s),而運行一次c子程序約需0.996 tick,比前者增加了52%。
結(jié)語
高級加密標準Rijndael算法在嵌入式微處理器ARM上的實現(xiàn)具有一定的實用價值。經(jīng)University of Califor-nia,San Diego在因特網(wǎng)上提供的測試程序Interactive Ri-jndael Test Vectors in JavaScript驗證,本實現(xiàn)算法是正確的。