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

引 言
    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代码表示如下：

Rijndael (State, CipherKey)  {

KeyExpansion (CipherKey, ExpandKey);  //密钥扩展

AddRoundKey (State, RoundKey);  //轮密钥加

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(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、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]=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汇编子程序代码设计举例
    在所有子程序中，列混淆变换和密钥扩展的代码设计难度较高，算法较复杂。下面是列混淆子程序的代码设计：

    MixColumn  ；子程序入口

    ldr  r0,=State  ；取变量地址

    ldr  r1,=CoefMix

    ldr  r2,=Temp   ；Temp中间变量

    mov  r3,#0   ；i=0

    loop_i    ；i循环入口

    mov  r4,#0    ；j=0

    loop_j    ；j循环入口

    mov  r5,#0  ；k=0

    loop_k  ；k循环入口

    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  ；此循环用来计算

    mov  r8,r3,lsl  #2

    add  r8,r8,r4

    and  r9,r6,#1

    cmp  r9,#1  ；判断CoefMix[i,k]的最低位是否为1

    bne notequal  ；若不为1，转向执行

    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，转向执行

    eor  r7,r7,#0xlb  ；如为1，则State[k,j]与#0xlb异或littlethan

    cmp  r6,#0  ；CoefMix[i,k]与0比较

    bgt loop_temp  ；如大于0，转到标号loop_temp处执行，否则读取CoefMix[i,k+1]

    add r5,r5,#1

    cmp r5,#4

    blt loop_k  ；执行k循环

    add r4,r4,#1

    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 r4[r0,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子程序所占用的空间明显小得多，前者仅为后者的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验证，本实现算法是正确的。