在ARM微处理器上实现Rijndael加密算法

1、在ARM微处理器上实现Rijndael加密算法    引 言    2000年10月2日，美国国家标准局NIST宣布，比利时密码学家Joat Daemen和Vincent Rijmen设计的“RijndaeI算法”以安全性好、运算速度快、存储要求低、灵活性强最终当选AES。该算法对目前的各种威胁是免疫的。这标志着信息技术有了新的安全工具，为计算机网络和电子商务的发展提供了强有力的保障。    在当前数字信息技术和网络技术高速发展的后PC时代，嵌入式系统技术已经广泛地渗透到科学研究、工程设计、军事

2、技术、各类产业和商业文化艺术以及人们的日常生活等方方面面中，成为目前最热门的技术之一。    本文使用北京博创兴业科技有限公司研制的UP-NETARM300嵌入式开发板，在ARM SDT 2.51集成开发环境下，建立基于COS-Il操作系统的工程文件，分别调用ARM汇编程序和C程序在嵌入式微处理器上实现了Rijndael算法，并比较了两者的效率。下面以分组长度和密钥长度都是128位为例，介绍调用ARM汇编程序实现加密算法的过程。本实现算法可以将密钥长度扩展到192位或256位。1 Rijndael加密算法简介11 算法流程结构   

3、Rijndael加密算法的128位输入分组用以字节为单位的正方形矩阵描述。该数组被复制到State数组。加密过程分为四个阶段：密钥扩展、轮密钥加、Nr-1(对应128、192、256位密钥长度，Nr分别为10、12、14)轮变换及最后一轮变换。轮变换包括字节代换、行移位、列混淆和轮密钥加四个过程，最后一轮变换包括字节代换、行移位和轮密钥加三个过程。用伪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);  /字节代换ShiftRow(State);  /行移位MixColumn(State);  /列混淆AddRoundKey(State, RoundKey);  轮密钥加FinalRound(

5、State, RoundKey)   /最后一轮变换SubByte(State);ShiftRow(State);AddRoundKey(State,RoundKey); 1. 2算法所使用的主要变换(1)字节代换SubByte    用一个简单的查表操作代替了基于矩阵乘法的复杂仿射变换。Rijndael定义了一个16×16字节的S盒矩阵，包含8位值所能表达的256种可能的变换。把Statc中每个字节的高4位作为行值，低4位作为列值，取出S盒中对应行列的元素作为新的字节输出。行移位变换ShiftRow：State的第一行保持不变，第2

6、、3、4行分别循环左移1、2、3个字节。(2)列混淆变换MixColumn    可表示为如下基于系数矩阵CoefMix与State的矩阵乘法：    乘积矩阵中的每个元素S'i,j是系数矩阵中一行元素CoefMixi，k与State矩阵中对应一列元素Statek，j的乘积之和。这里的加法与乘法都定义在有限域GF(28)上：加法即按位异或操作，乘法遵循GF(28)上的多项式乘法规则。(3)密钥扩展KeyExpanxsion    以4个字密钥为输入，生成44字扩展密钥数组44，为初始轮密钥加阶段和

7、后面10轮变换提供轮密钥。输入密钥直接被复制到扩展密钥数组的前4个字，然后每次用4个字填充扩展密钥数组余下的部分。在扩展密钥数组中，i值依赖于i-1和i-4。数组中下标不是4的倍数时，i为i-1和i-4的异或。下标为4的倍数时，首先将i-1的4个字节循环左移1个字节，然后利用S盒对每个字节进行字节代换，再与轮常量按位异或。轮常量是1个字，其最右边3个字节为O，最左边1个字节的值RCj与轮数j相关。RC1=1，RCj=2·RCj-1，乘法定义在GF(28)上。RCj值以十六进制表示。(4)轮密钥加AddRoundKey    是基于State列的操作，即把

8、State一列中的4个字节与轮密钥RoundKey的1个字进行“异或”。2 ARM汇编编程实现Rijndael算法的要点2. 1源程序组成及功能2. 2 Rijndael.s程序实现加密算法步骤    Rijndael.s主要通过ARM汇编子程序调用完成加密算法，包括1个代码段和1个数据段。它把算法所使用的所有变换均用同名ARM汇编子程序实现。代码段包括以下几个模块：    首先，进行明文、密钥预处理。明文可以从开发板键盘上接收，也可以是常量或参数传递过来的变量。    其次，调用子程序KeyExpans

9、ion完成密钥扩展。    第三，调用子程序AddRoLundKey完成初始轮密钥加。    第四，轮变换。包括四个步骤：调用于程序SubByte进行字节代换；调用子程序ShiftRow进行行移位；调用子程序MixColumn进行列混淆；调用子程序Ad-dRoundKey进行轮密钥加。本过程重复9次。    第五，最后一轮变换。包括三个步骤：调用子程序SubByte进行字节代换；调用子程序ShiftRow进行行移位；调用子程序AddRoundKey进行轮密钥加。    最后，

10、对生成的密文进行进一步处理，即把密文视为4×4数组，将其行与列对调。    在数据段中对转换过程中使用到的部分数据或中间变量进行了定义并初始化。如字节代换中的S盒及列混淆变换中的系数矩阵等。23 ARM汇编子程序代码设计举例    在所有子程序中，列混淆变换和密钥扩展的代码设计难度较高，算法较复杂。下面是列混淆子程序的代码设计：    MixColumn  ；子程序入口    ldr  r0,=State  ；取变量地址 &#

11、160;  ldr  r1,=CoefMix    ldr  r2,=Temp   ；Temp中间变量    mov  r3,#0   ；i=0    loop_i    ；i循环入口    mov  r4,#0    ；j=0    loop_j    ；j循环入口&

12、#160;   mov  r5,#0  ；k=0    loop_k  ；k循环入口    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  ；此循环用来计算        mov  r8,r3,lsl  #2    add  r8,r8,r4    and  r9,r6,#1    cmp  r9,#1  ；判断CoefMixi,k的最低位是否为1

14、60;   bne notequal  ；若不为1，转向执行    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，转向执行    eor  r7,r7,#0xlb 

16、; ；如为1，则Statek,j与#0xlb异或littlethan    cmp  r6,#0  ；CoefMixi,k与0比较    bgt loop_temp  ；如大于0，转到标号loop_temp处执行，否则读取CoefMixi,k+1    add r5,r5,#1    cmp r5,#4    blt loop_k  ；执行k循环    add r4,r4,#1

17、    cmp r4,#4    blt loop_j  ；执行j循环    add r3,r3,#1    cmp r3,#4    blt loop_I  ；执行i循环    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加密算法实现效率比较    在调用ARM汇编程序实现Rijndael加密算法之余，还在嵌入式微处理器ARM上通过调用C子程序实现了Rijndael算法，同样获得了正确结果。表1、表2是两种实现方式的空间与时间效率比较。    由表1知，ARM子程序比C子程序所占用的空间明显小