Rijndael加密算法的介绍

AES加密算法详解随着对称密码的发展，DES数据加密标准由于密钥长度较小(56位)，已经不适应当今分布式开放网络对数据加密安全性的要求。因此，1997年NIST公开征集新的数据加密标准，即AES(AdvancedEncryptionStandard)。经过三轮的筛选，比利时JoanDaeman和VincentRijmen提交的Rijndael算法被提议为AES的最终算法。尽管人们对AES还有不同的看法，但总体来说，AES作为新一代的数据加密标准汇聚了强安全性、高性能、高效率、易用和灵活等优点，成为美国新的数据加密标准而被广泛应用在各个领域中。以下分别介绍Rijndael加密算法的架构，回合的转换，密钥的产生等相关内容。一、Rijndael简介AES是一种迭代的、对称密钥分组的密码，是基于置换和代替的。Rijndael允许数据区块及密钥的长度从128位(16字节)到256位(32字节)之间变动，变化步长为32位(4字节)，而且数据区块的长度与密钥的长度可以独立变化。由于AES规定数据区块的长度为128位，密钥的长度为128、192(事实上无人使用)、256位，所以AES事实上只有两个变种：128位数据区块加上128位密钥或者128位数据区块加上256位密钥。在Rijndael算法中定义了几个名词，分述如下：State：在运算过程中所产生的中间值，是一个4×Nb的矩阵，Nb可由数据长度除以32位求得，也就是把数据分割成Nb个区块。CipherKey：用来做加密运算的金钥，形式是一个4×Nk的矩阵，Nk可由密钥长度除以32位求得，也就是把密钥分割成Nk个32位的子密钥。Rijndael是一个反复运算的加密算法，运算的回合数(Nr)是由Nb及Nk所决定的，如下表。NrNb=4Nb=6Nb=8Nk=4101214Nk=6121214Nk=8141414二、Rijndael的数学背景在Rijndael中使用了许多字节层级的运算，而这些运算是以GF(28)为基础架构。1、GF(28)的定义假设一个字节b由b7b6b5b4b3b2b1b0组成，则b可以表示为一个7次多项式：b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0例如，(57)16表示为二进制(01010111)2，对应的多项式为：x6+x4+x2+x+1。2、加法两个多项式的加法，则是定义为相同指数项的系数和再模余2，也就是EXOR运算。例如：(57)16+(83)16=(01010111)2+(10000011)2=(11010100)2=(D4)16或：(x6+x4+x2+x+1)+(x7+x+1)=x7+x6+x4+x23、乘法在乘法里面，多项式相乘之后的结果很容易造成溢位的问题，解决溢位的方式是把相乘的结果，再模余一个不可分解的多项式m(x)。在Rijndael中，定义一个这样子的多项式为m(x)=x8+x4+x3+x+1或是(11B)16。例如：(57)16‧(83)16=(x6+x4+x2+x+1)‧(x7+x+1)=x13+x11+x9+x8+x7+x7+x5+x3+x2+x+x6+x4+x2+x+1=(x13+x11+x9+x8+x6+x5+x4+x3+1)modulo(x8+x4+x3+x+1)=x7+x6+1=(C1)164、乘以xn即为左移n位运算，若发生溢出，则与(11B)16进行异或运算。例如：(57)·(02)=(01010111)1=(10101110)=(AE)(57)·(04)=(01010111)2=(101011100)^(100011011)=(01000111)=(47)(57)·(08)=(01010111)3=(8E)(57)·(10)=(01010111)4=(07)(57)·(13)=(57)·(01)⊕(57)·(02)⊕(57)·(10)=(57)⊕(AE)⊕(07)=(FE)三、Rijndael的加解密框架下图描述了Rijndael的加密及解密过程，后面将仅对加密过程加以介绍。四、Rijndael的加密架构Rijndael加密算法是由一个initialRoundKeyaddition，Nr-1个回合运算，及一个finalround所组成。加密过程以C语言伪码叙述如下：CiperTextRijndael(State,CipherKey){ExpandKey(CipherKey,rk);XorRoundKey(State,rk[0]);For(i=1;iNr;i++){Substitute(State);RotateRows(State);MixColumns(State);XorRoundKey(State,rk[i]);}Substitute(State);RotateRows(State);XorRoundKey(State,rk[i]);}算法中的State表示输入的数据明文，CipherKey表示使用的加密密钥，算法返回的CiperText表示加密后得到的密文。算法ExpandKey用于将CipherKey扩展为与state大小一致的子密钥rk，每次参与运算的rk都是不同的。rk的计算过程可以独立于数据明文的加密过程。算法用于XorRoundKey将特定的子密钥rk与State进行异或运算，并将结果赋给State。算法描述中的rk[i]，表示第i次参与XorRoundKey运算用于的子密钥，其计算过程会在后面介绍。中间的回合运算包括4个子操作。Substitute用于对State实施S-box变换；RotateRows对State实施行变换；MixColumns对对State实施列变换；XorRoundKey将特定的子密钥rk与State进行异或运算。最后一轮的操作与回合运算类似，只是少了列变换操作。五、密钥扩展运算介绍Rijndael加密过程需要用到Nr+1个子密钥，每个子密钥的大小应该与State一致，即一个4×Nb的矩阵。因此，整个密钥调度表为一个4×(Nb×(Nr+1))的矩阵，即一个4行、Nb×(Nr+1)列的矩阵。密钥调度表的前Nk列即为密钥分割而成的4×Nk的矩阵。现考虑调度表的第Wi(i=Nk)列的生成过程，该过程与Nk相关。当Nk≦6时，相关过程为：CopyWi-1ToWi；若i能整除Nk则对Wi进行位置变换、S盒变换及Rcon变换；与Wi-Nk进行异或运算。当Nk＞6时，相关过程为：CopyWi-1ToWi；若i能整除Nk则对Wi进行位置变换、S盒变换及Rcon变换，若i除Nk余数为4，则对Wi进行S盒变换；与Wi-Nk进行异或运算。以下讨论其中用于的三种变换的具体操作：①位置变换(rotword)。将第一行的数移动到第四行，其他各行向前移动一位。即原来为ABCD的列序调整为BCDA的列序。②S盒变换(subword)。对此列的每个数据(十六进制表示)实施S盒变换，变换规则为：以该数据的第一个数据为行，第二个数据为列，在S盒中找到对应的数据，并替换原数据即可。S盒变换表如下图所示。设第一行的数据为cf，则查找S盒中行为c，列为f的单元格对应的数据，为8a；以8a代替cf即完成变换操作。③Rcon变换。即将Wi与Rcon[i/Nk]进行异或运算。Rcon称为轮常数表的数组，下表给出了Rcon[0]至Rcon[14](十六进制表示)。R0R1R2R3R4R5R6R7R8R9R10R11R12R13R140001020408102040801b366cd8bb4e000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000六、加密处理过程整个解密过程包括如下四个主要操作：Substitute、RotateRows、MixColumns及XorRoundKey。以下分别介绍这四个操作。1、Substitute对State中的每个字节实施S盒变化，变化规则及S盒表都与密钥扩展中的S盒变化方式一样。2、RotateRows对State中的每一行进行循环右移位操作。第0行不动，第1行位移C1个字节，第2行位移C2个字节，第3行位移C3个字节。位移的偏移量C1、C2、C3与区块的数目(Nb)有关，定义如下表：NbC1C2C34123612381343、MixColumns如下表所示，(a0，a1，a2，a3)为State中的某一列，将其左乘这个特殊的矩阵后，先到的(b0，b1，b2，b3)即为混合后的对应的列。比如，设(a0，a1，a2，a3)为(d4，bf，5d，30)，则b0=(02)*(d4)+(03)*(bf)+(01)*(5d)+(01)*(30)。其中的加法与乘法都是以GF(28)为基础架构的。以下给出b0的计算过程。(02)*(d4)=(11010100)1^(100011011)=(10110011)=(b3)(移位后若溢出，则与11B进行异或运算)(03)*(bf)=(bf)*(01)+(bf)*(02)=(10111111)+(01100101)=(11011010)=(ba)(01)*(5d)=(5d)(01)*(30)=(30)B0=(b3)^(ba)^(5d)^(30)=(04)4、XorRoundKey将State与对应的子密钥进行按位异或运算即可。