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