对Rijndael算法中密钥扩展的优化

王根义

（陕西职业技术学院 陕西 西安 710100）

因为Rijndael是AES数据加密新标准的算法中最常用的一种。Rijndael数据加密技术在我国被推行时间较短，而且Rijndael蜜钥扩展技术比较深奥，所以好多学者和数据加密方面工作人员对Rijndael密钥扩展的原理没有掌握，更谈不上创新一种高效的密钥扩展方法来改进密钥扩展工作，本作者抱着推广Rijndael密钥扩展技术，讲清密Rijndael钥扩展原理，提出实现Rijndael密钥扩展的优化方法的目的，特写此论文。

1 密钥扩展的相关概念

Rijndael数据加密钥的过程，所用的子密钥是由一个密钥扩展函数KeyExpansion（）用种子密钥产生的，种子密钥也叫初始密钥或主密钥。把一个种子密钥划分成若干块，每一块也叫作一个字，一个字中所含的字节数用N b来表示，这个种子密钥中所含的字数叫作种子密钥的Nk，所有的子密钥和主密钥构成密钥数组W[]，共（N r+1）*N b个字节，其中r叫作加密钥的轮数[1-2]。

2 密钥扩展函数KeyExpansion（）的实现方案

KeyExpansion（）的定义方案如下所示[3-5]：

KeyExpansion（byte[]key， byte[][4]w）

{

copy the seed key into the first rows of w

for each remaining row of w

{

use two of the previous rows to create a new row

}

}

“use two of the previous rows to create a new row” 例程使用2个子例程 （RotWord和 SubWord），以及一个名为 Rcon的常数表（用于“循环常数”）。让我们看一看这三项中的每一项，然后返回到整个KeyExpansion例程。RotWord例程非常简单，它接受 4字节的数组并将它们排列，请注意，由KeyExpansion使用的 RotWord函数与由加密算法使用的非常相似，唯一的区别就是它作用于密钥次序表w[]的单行，而不是同ShiftRows例程作用于整个被加密的状态表 State[]。SubWord例程使用置换表 Sbox，针对密钥次序表 w[]的给定行执行逐字节置换[6]。KeyExpansion运算中的置换方法与加密算法中的置换方法完全相同。要被置换的输入字节分成（x，y）对，该对用作置换表 Sbox的索引。例如，置换 0x27将导致 x=2，y=7，而且 Sbox[2，7]将返回 0xcc[7]。

3 Rijndael算法中加法和乘法的数学域理论

Rijndael算法基于名为 GF（28） 的域。 GF（28） 域包括一组从 0x00到 0xff（共28=256个）的值以及加法和乘法。GF代表伽罗华域，它以创建域理论的数学家命名。GF（28）有一个特征就是，加法或乘法运算的结果必须位于集合 {0x00...0xff}中。尽管域理论相当深奥，但是 GF（28）加法的最终结果非常简单：GF（28） 加法只是 XOR 运算。 但是，GF（28）乘法却比较复杂。在 GF（28）中，一个数与 0x01相乘是特殊的，它与普通算术中的乘以1相对应，即任何值与 0x01相乘都等于它本身。现在，让我们看看与0x02相乘会怎样。在多项式表示中，GF（28）的乘法对应于多项式乘法模除次数 为8的不可约多项式（x8+x4+x3+x+1）。如果一个多项式除了1和它本身之外没有其它因子，则称它为不可约分的。对于Rijndael，这个模除用的多项式叫做 m（x）：m（x） = （x8+x4+x3+x+1），它所对应的十六进制数表示为'11BH'，对应的二进制数表示为9比特的‘100011011B’。以下是一个乘法的例子[15－16]：

上式对应的十六进制数表示式为：

根据二进制数的性质，可以推出GF（28）域乘数为2的乘法可以这样进行：如果被乘数小于 0x80，那么，乘法结果只是向左位移 1位的值。如果被乘数大于或等于 0x80，那么，乘法结果将是向左位移 1位后再与0x1b值执行 XOR运算的值。这将防止出现“域溢出”，并使乘法结果落在范围内。0x80○×0x02=0x1b是 0x80向左移 1位，然后与 0x1b执行XOR运算。一旦建立了与 GF（28）中的 0x02的加法和乘法，就可以使用它们来定义与任何常数的乘法。要与 GF（28）中的0x03相乘，可以将 0x03分解为2的幂和加法。要将任意字节 b与 0x03相乘，会看到 0x03=0x02+0x01。因此：

4 Rijndael算法中KeyExpansion（）函数的优化

KeyExpansion（）的实现方法

当 Nk＜=6 时（Nk=4 or 6）[8－11]：

KeyExpansion（byte Key[4*Nk]，byte&W[Nb*（Nr+1）][4]）

{

for（i=0；i＜Nk；i++）

W[i]=（Key[4*i]， Key[4*i+1]， Key[4*i+2]， Key[4*i+3]）；

for（i=Nk；i＜Nb*（Nr+1）；i++）

{

temp=W[i－1]；

if（i%Nk==0）

temp=ByteSub（temp＜＜8）^Rcon[i/Nk]；

W[i]=W[i－Nk]^temp；

}

}；

当Nk=8：

KeyExpansion（byte Key[4*Nk]， byte&W[Nb*（Nr+1）Key][4]）

{

for（i=0；i＜Nk；i++）

W[i]=（Key[4*i]， Key[4*i+1]， Key[4*i+2]， Key[4*i+3]）；

for（i=Nk；i＜Nb*（Nr+1）；i++） {

temp=W[i－1]；

if（i%Nk==0）

temp=ByteSub（temp＜＜8）^Rcon[i/Nk]；

else if（i%Nk==4）

temp=ByteSub（temp＜＜8）；

W[i]=W[i－Nk]^temp；

}；

}；

Rcon[i]定义为[12][13][14]：

Rcon[i]= （RC[i]，‘00’，‘00’，‘00’）

RC[1]=1，RC[2]=2，RC[3]=4，……

RC[i]=2（i－1）

以往的KeyExpansion（）函数使用名为循环常数表的数组Rcon[]中，每个循环常数最左边的字节是 GF（28）域中 2的幂。即第一个循环常数最左边的字节是1，往后每个值都是上一个值按 GF（28）中的乘法法则乘以 0x02。

由于Rijndael算法的子密钥的前N k个字完全由种子密钥填充而成，这样做虽然密钥的离散性非常好，减少了密钥间的线性关系，但是密钥的雪崩效应就减弱了，同时它的轮密钥是通过递归定义生成的，也就是说，对某一轮的密钥可以由前一轮或几轮的轮密钥推导而来。如果我们知道了这前N k个字的部分密钥字，就可以根据递推公式得到与这些部分密钥字相关的密钥字。当泄露的密钥信息达到一定程度时，其它的种子密钥或许就可以通过穷举法获得，进而获得全部轮子密钥。对于公开的算法来说，如果密钥已知，轻而易举地就可以由密文译出明文，信息的保密就受到了威胁。那么，怎样在优化线性关系和雪崩效应的同时提高密钥的保密性呢?从安全的角度来分析，为了使攻击者更难于找到加密密钥特别是种子密钥，应该提高密钥生成算法的混淆性来有效抵抗密码攻击。

由此提出了在子密钥生成阶段和密钥选择阶段引入一个随机函数的方法来避免上述缺陷，具体方法如下：

第一次生成RC[I]的时候按照原来的方式利用线性同余法生成伪随机数I，从而选择运算对象rand[I]，具体的公式如下：

RC[I]=（RC[I－1]）·Random（K） 其中 k 为小于 I的任何数

产生Random（K）的函数：

Random（n，m，seed，a，b）

{

r0=seed；

for（i=1；i＜=n；i++）

ri=（a*ri－1+b）mod m；

}

其中将种子参数seed设为计算机当前的日期或者时间；m是一个较大数，可以把它取为2w，w是计算机的字长；a可以是0.01w和0.99w之间的任何整数；n等于当前（I－1）。

这样就可以方便的产生出随机的参与异或运算的对象rand[I]。密钥生成后把所有的子密钥形成一个表，而在密钥选择阶段同样可以使用随机函数，打乱子密钥选择的规律性，使生成各列子密钥的过程具有完全的随机性。但是由于算法中用到了加密者的本地时间作为seed，而解密者不一定与加密者时间统一，为了解决这个问题，我们决定用数字时间戳（digital time－stamp）系统，该系统可以让通信双方遵守同样的时间，而算法中只要把取的系统时间加入到密文里的某个只有双方才知道的特殊位置 （或者直接加入明文里加密也可）就可以使解密者很容易地对密文进行解密了。当然，以上方法只能应用在网络中，但是它给Rijndael带来的安全性是前所未有的，并且跟通信系统紧密联合在一起，在应用方面将会有很大的用武之地。

5 KeyExpansion（）的实现方法的改进

上述5中提出的方法中的主循环由于用了分支程序，代码较多，另外执行时速度较慢。为了克服这两个缺点，笔者设计了下列循环语句来实现[17－19]主循环：

for（i=Nk； i＜ Nb* （Nr+1）； ++i）

{

temp=w[i－1]

if（i%Nk==0）

temp=SubWord[RotWord（temp）]xor Rcon[i/Nk]

else if（Nk==8 and row%Nk==4）

temp=SubWord（temp）

[i]=w[i－Nk]xor temp

}

这个主循环的代码经过上机实验证明完全正确可靠，可以克服5中的主循环的缺点，节约软硬件资源，提高代码的运行速度。

6 结束语

文中创新点：用简单、明了和新颖的逻辑关系阐明了密钥扩展的原理，提出了具体实现AES密钥扩展的两种新方法。文中提出的具体实现AES密钥扩展的两种新方法，可根据计算机的特点，灵活的应用在不同的数据加密工程当中，以提高数据加密工程的效率和速度；文中对密钥扩展的原理阐述方法可改进有关密钥扩展的教材及书籍。

[1]戴宗坤.信息安全管理指南 [M].北京：中国电力出版社，2008.

[2]谭方勇.网络安全技术实用教程[M].重庆：重庆出版社，2000.

[3]黄月江.信息安全保密：现代与未来战争的信息卫士[M].北京：国防工业出版社，2008.

[4]武新华.黑客攻防秘技实战解析[M].北京：人民大学出版社，2008.

[5]宋震.密码学[M].北京：中国水利水电出版社，2002.

[6]杨义先.现代密码新理论[M].北京：科学出版社，2002.

[7]谷大武.高级加密标准 （AES）算法—Rijndael的设计[M].北京：清华大学出版社，2003.

[8]高峻.AES算法的改进用法及其在数据库加密中的应用[J].中南民族大学学报：自然科学版，2002（04）：67－69.GAO Jun.Improved usage of AES algorithm and its application in data encryption technology[J].Journal of South-Central University For Nationalities:Natural Science Edition，2002（04）：67－69，90.

[9]徐卉.WLAN数据加密技术中AES算法的分析与改进[J].电脑知识与技术，2009（03）：591－592，609.XU Hui.Analysis and improvement of AESalgorithm in data encryption technology WLAN[J].Computer Knowledge and Technology，2009（03），591－592，609.

[10]Bertino E.Data secureity[J].Data&Knowledge Engineering，1998，25（1－2）:199－216.

[11]萨师煊，王珊.数据库系统概论[M].北京，高等教育出版社，2000.

[12]戴宗坤.信息安全管理指南[M].北京：中国电力出版社，2008.

[13]黄月江.信息安全保密：现代与未来战争的信息卫士[M].北京：国防工业出版社，2008.

[14]武新华.黑客攻防秘技实战解析[M].北京：人民大学出版社，2008.

[15]宋震.密码学[M].北京：中国水利水电出版社，2002.

[16]杨义先.现代密码新理论[M].北京：科学出版社，2002.

[17]谷大武.高级加密标准（AES）算法—Rijndael的设计[M].北京：清华大学出版社，2003.

[18]谭方勇.网络安全技术实用教程[M].重庆出版社，2000.