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