在ARM微處理器上實現(xiàn)Rijndael加密算法

1、在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è)計、軍事

2、技術(shù)、各類產(chǎn)業(yè)和商業(yè)文化藝術(shù)以及人們的日常生活等方方面面中，成為目前最熱門的技術(shù)之一。    本文使用北京博創(chuàng)興業(yè)科技有限公司研制的UP-NETARM300嵌入式開發(fā)板，在ARM SDT 2.51集成開發(fā)環(huán)境下，建立基于COS-Il操作系統(tǒng)的工程文件，分別調(diào)用ARM匯編程序和C程序在嵌入式微處理器上實現(xiàn)了Rijndael算法，并比較了兩者的效率。下面以分組長度和密鑰長度都是128位為例，介紹調(diào)用ARM匯編程序?qū)崿F(xiàn)加密算法的過程。本實現(xiàn)算法可以將密鑰長度擴展到192位或256位。1 Rijndael加密算法簡介11 算法流程結(jié)構(gòu)   

3、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);

4、60; /輪密鑰加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(

5、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

6、、3、4行分別循環(huán)左移1、2、3個字節(jié)。(2)列混淆變換MixColumn    可表示為如下基于系數(shù)矩陣CoefMix與State的矩陣乘法：    乘積矩陣中的每個元素S'i,j是系數(shù)矩陣中一行元素CoefMixi，k與State矩陣中對應(yīng)一列元素Statek，j的乘積之和。這里的加法與乘法都定義在有限域GF(28)上：加法即按位異或操作，乘法遵循GF(28)上的多項式乘法規(guī)則。(3)密鑰擴展KeyExpanxsion    以4個字密鑰為輸入，生成44字擴展密鑰數(shù)組44，為初始輪密鑰加階段和

7、后面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é)的值RCj與輪數(shù)j相關(guān)。RC1=1，RCj=2·RCj-1，乘法定義在GF(28)上。RCj值以十六進制表示。(4)輪密鑰加AddRoundKey    是基于State列的操作，即把

8、State一列中的4個字節(jié)與輪密鑰RoundKey的1個字進行“異或”。2 ARM匯編編程實現(xiàn)Rijndael算法的要點2. 1源程序組成及功能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)用子程序KeyExpans

9、ion完成密鑰擴展。    第三，調(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進行輪密鑰加。    最后，

10、對生成的密文進行進一步處理，即把密文視為4×4數(shù)組，將其行與列對調(diào)。    在數(shù)據(jù)段中對轉(zhuǎn)換過程中使用到的部分數(shù)據(jù)或中間變量進行了定義并初始化。如字節(jié)代換中的S盒及列混淆變換中的系數(shù)矩陣等。23 ARM匯編子程序代碼設(shè)計舉例    在所有子程序中，列混淆變換和密鑰擴展的代碼設(shè)計難度較高，算法較復(fù)雜。下面是列混淆子程序的代碼設(shè)計：    MixColumn  ；子程序入口    ldr  r0,=State  ；取變量地址 &#

11、160;  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)入口&

12、#160;   mov  r5,#0  ；k=0    loop_k  ；k循環(huán)入口    mov  r6,r3,lsl #2    add  r6,r6,r5    ldrb  r6,r1,r6  ；讀取CoefMixi,k    mov  r7,r5,lsl #2    add  r7,r7,r4

13、0;   ldrb  r7,r0,r7  ；讀取Statek,j    loop_temp  ；此循環(huán)用來計算        mov  r8,r3,lsl  #2    add  r8,r8,r4    and  r9,r6,#1    cmp  r9,#1  ；判斷CoefMixi,k的最低位是否為1

14、60;   bne notequal  ；若不為1，轉(zhuǎn)向執(zhí)行    ldrb  r9,r2,r8   ；若為1，則Tempi,j)+=Statek,j    eor  r9,r9,r7    strb  r9,r2,r8    notequal    mov  r6,r6,lsr  #1  ；CoefMixi,k邏輯右移1位 &

15、#160;  and  r9,r7,#0x80    mov  r7,r7,lsl  #1  ；Statek,j邏輯左移1位    and  r7,r7,#0xff    cmp  r9,#0x80  ；移位后Statek,j最高位是否為1    blt littlethan  ；如不為1，轉(zhuǎn)向執(zhí)行    eor  r7,r7,#0xlb 

16、; ；如為1，則Statek,j與#0xlb異或littlethan    cmp  r6,#0  ；CoefMixi,k與0比較    bgt loop_temp  ；如大于0，轉(zhuǎn)到標號loop_temp處執(zhí)行，否則讀取CoefMixi,k+1    add r5,r5,#1    cmp r5,#4    blt loop_k  ；執(zhí)行k循環(huán)    add r4,r4,#1

17、    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 r

18、4r0,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子程序所占用的空間明顯小