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

引 言 2000年10月2日，美國(guó)國(guó)家標(biāo)準(zhǔn)局NIST宣布，比利時(shí)密碼學(xué)家Joat Daemen和Vincent Rijmen設(shè)計(jì)的“RijndaeI算法”以安全性好、運(yùn)算速度快、存儲(chǔ)要求低、靈活性強(qiáng)最終當(dāng)選AES。該算法對(duì)目前的各種威脅是免疫的。這標(biāo)志著信息技術(shù)有了新的安全工具，為計(jì)算機(jī)網(wǎng)絡(luò)和電子商務(wù)的發(fā)展提供了強(qiáng)有力的保障。 在當(dāng)前數(shù)字信息技術(shù)和網(wǎng)絡(luò)技術(shù)高速發(fā)展的后PC時(shí)代，嵌入式系統(tǒng)技術(shù)已經(jīng)廣泛地滲透到科學(xué)研究、工程設(shè)計(jì)、軍事技術(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程序在嵌入式微處理器上實(shí)現(xiàn)了Rijndael算法，并比較了兩者的效率。下面以分組長(zhǎng)度和密鑰長(zhǎng)度都是128位為例，介紹調(diào)用ARM匯編程序?qū)崿F(xiàn)加密算法的過程。本實(shí)現(xiàn)算法可以將密鑰長(zhǎng)度擴(kuò)展到192位或256位。 1 Rijndael加密算法簡(jiǎn)介 1.1 算法流程結(jié)構(gòu) Rijndael加密算法的128位輸入分組用以字節(jié)為單位的正方形矩陣描述。該數(shù)組被復(fù)制到State數(shù)組。加密過程分為四個(gè)階段：密鑰擴(kuò)展、輪密鑰加、Nr-1(對(duì)應(yīng)128、192、256位密鑰長(zhǎng)度，Nr分別為10、12、14)輪變換及最后一輪變換。輪變換包括字節(jié)代換、行移位、列混淆和輪密鑰加四個(gè)過程，最后一輪變換包括字節(jié)代換、行移位和輪密鑰加三個(gè)過程。用偽C代碼表示如下： Rijndael (State, CipherKey) { KeyExpansion (CipherKey, ExpandKey); //密鑰擴(kuò)展 AddRoundKey (State, RoundKey); //輪密鑰加 For (i=1;i 乘積矩陣中的每個(gè)元素S"i,j是系數(shù)矩陣中一行元素CoefMix[i，k]與State矩陣中對(duì)應(yīng)一列元素State[k，j]的乘積之和。這里的加法與乘法都定義在有限域GF(28)上：加法即按位異或操作，乘法遵循GF(28)上的多項(xiàng)式乘法規(guī)則。 (3)密鑰擴(kuò)展KeyExpanxsion 以4個(gè)字密鑰為輸入，生成44字?jǐn)U展密鑰數(shù)組ω[44]，為初始輪密鑰加階段和后面10輪變換提供輪密鑰。輸入密鑰直接被復(fù)制到擴(kuò)展密鑰數(shù)組的前4個(gè)字，然后每次用4個(gè)字填充擴(kuò)展密鑰數(shù)組余下的部分。在擴(kuò)展密鑰數(shù)組中，ω[i]值依賴于ω[i-1]和ω[i-4]。ω數(shù)組中下標(biāo)不是4的倍數(shù)時(shí)，ω[i]為 ω[i-1]和ω[i-4]的異或。下標(biāo)為4的倍數(shù)時(shí)，首先將ω[i-1]的4個(gè)字節(jié)循環(huán)左移1個(gè)字節(jié)，然后利用S盒對(duì)每個(gè)字節(jié)進(jìn)行字節(jié)代換，再與輪常量按位異或。輪常量是1個(gè)字，其最右邊3個(gè)字節(jié)為O，最左邊1個(gè)字節(jié)的值RC[j]與輪數(shù)j相關(guān)。RC[1]=1，RC[j]=2%26;#183; RC[j-1]，乘法定義在GF(28)上。RC[j]值以十六進(jìn)制表示。 (4)輪密鑰加AddRoundKey 是基于State列的操作，即把State一列中的4個(gè)字節(jié)與輪密鑰RoundKey的1個(gè)字進(jìn)行“異或”。 2 ARM匯編編程實(shí)現(xiàn)Rijndael算法的要點(diǎn) 2. 1源程序組成及功能 源程序包含main.c和ARM匯編程序Rijndael.s。main.c用C語(yǔ)言編寫，主要完成調(diào)用μC/OS-II函數(shù)進(jìn)行系統(tǒng)初始化及I/O的全部功能，并調(diào)用Rijndael.s對(duì)明文加密。明文、密鑰及密文均在開發(fā)板顯示屏上輸出。 Rijndael.s用ARM匯編編程語(yǔ)言編寫，是實(shí)現(xiàn)加密算法的關(guān)鍵程序。 2. 2 Rijndael.s程序?qū)崿F(xiàn)加密算法步驟 Rijndael.s主要通過ARM匯編子程序調(diào)用完成加密算法，包括1個(gè)代碼段和1個(gè)數(shù)據(jù)段。它把算法所使用的所有變換均用同名ARM匯編子程序?qū)崿F(xiàn)。代碼段包括以下幾個(gè)模塊： 首先，進(jìn)行明文、密鑰預(yù)處理。明文可以從開發(fā)板鍵盤上接收，也可以是常量或參數(shù)傳遞過來的變量。 其次，調(diào)用子程序KeyExpansion完成密鑰擴(kuò)展。 第三，調(diào)用子程序AddRoLundKey完成初始輪密鑰加。 第四，輪變換。包括四個(gè)步驟：①調(diào)用于程序SubByte進(jìn)行字節(jié)代換;②調(diào)用子程序ShiftRow進(jìn)行行移位;③調(diào)用子程序MixColumn進(jìn)行列混淆;④調(diào)用子程序Ad-dRoundKey進(jìn)行輪密鑰加。本過程重復(fù)9次。 第五，最后一輪變換。包括三個(gè)步驟：①調(diào)用子程序SubByte進(jìn)行字節(jié)代換;②調(diào)用子程序ShiftRow進(jìn)行行移位;③調(diào)用子程序 AddRoundKey進(jìn)行輪密鑰加。 最后，對(duì)生成的密文進(jìn)行進(jìn)一步處理，即把密文視為4%26;#215;4數(shù)組，將其行與列對(duì)調(diào)。 在數(shù)據(jù)段中對(duì)轉(zhuǎn)換過程中使用到的部分?jǐn)?shù)據(jù)或中間變量進(jìn)行了定義并初始化。如字節(jié)代換中的S盒及列混淆變換中的系數(shù)矩陣等。 2.3 ARM匯編子程序代碼設(shè)計(jì)舉例 在所有子程序中，列混淆變換和密鑰擴(kuò)展的代碼設(shè)計(jì)難度較高，算法較復(fù)雜。下面是列混淆子程序的代碼設(shè)計(jì)： 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)用來計(jì)算

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)到標(biāo)號(hào)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加密算法實(shí)現(xiàn)效率比較 在調(diào)用ARM匯編程序?qū)崿F(xiàn)Rijndael加密算法之余，還在嵌入式微處理器ARM上通過調(diào)用C子程序?qū)崿F(xiàn)了Rijndael算法，同樣獲得了正確結(jié)果。表1、表2是兩種實(shí)現(xiàn)方式的空間與時(shí)間效率比較。

由表1知，ARM子程序比C子程序所占用的空間明顯小得多，前者僅為后者的55%。由表2，運(yùn)行一次ARM匯編程序Rijndael.s程序完成加密算法，僅需約0.657 tick(此處，1000 tick=1s)，而運(yùn)行一次c子程序約需0.996 tick，比前者增加了52%。 結(jié)語(yǔ) 高級(jí)加密標(biāo)準(zhǔn)Rijndael算法在嵌入式微處理器ARM上的實(shí)現(xiàn)具有一定的實(shí)用價(jià)值。經(jīng)University of Califor-nia，San Diego在因特網(wǎng)上提供的測(cè)試程序Interactive Ri-jndael Test Vectors in JavaScript驗(yàn)證，本實(shí)現(xiàn)算法是正確的。