AES算法加解密原理及安全性分析(DOC)

AES算法加解密原理及安全性分析刘帅卿一、AES算法简介AES算法是高级加密标准算法的简称，其英文名称为AdvancedEncryptionStandard。该加密标准的出现是因为随着对称密码的发展,以前使用的DES（DataEncryptionStandard数据加密标准）算法由于密钥长度较小(56位),已经不适应当今数据加密安全性的要求，因此后来由JoanDaeman和VincentRijmen提交的Rijndael算法被提议为AES的最终算法。AES是一个迭代的、对称密钥分组的密码，它可以使用128、192和256位密钥，并且用128位(16字节)分组加密和解密数据。与公共密钥密码使用密钥对不同，对称密钥密码使用相同的密钥加密和解密数据。通过分组密码返回的加密数据的位数与输入数据相同。迭代加密使用一个循环结构，在该循环中重复置换(permutations)和替换(substitutions)输入数据。加之算法本身复杂的加密过程使得该算法成为数据加密领域的主流。二、AES算法的基本概念1、有限域（GF）由于AES算法中的所有运算都是在有限域当中进行的，所以在理解和实现该算法之前先得打好有限域这一基石才行。通常的数学运算都是在实数域中进行，而AES算法则是在有限域中进行，我们可以将有限域看成是有确定边界范围的正整数集合，在该集合当中，任意两个元素之间的运算结果都仍然落在该集合当中，也即满足运算封闭性。那么如何才能保证这样的“有限性”（也即封闭性）呢？GF（2w）被称之为伽罗华域，是有限域的典型代表。随着w（=4,8,16,…）的取值不同所形成的有限域范围也不同。AES算法中引入了GF域当中对数学运算的基本定义：将两数的加减法定义为两者的异或运算；将两数的乘法定义为多项式间的相乘并求余运算，其中被用于求余运算的除数被称为不可约多项式（或者称为求余多项式），它是固定的一个多项式：m(x)=8431xxxx（数值为十六进制的11B，这里是假定w=8时的情形）。对于某个有限域而言，可能存在不唯一的不可约多项式，选择合适的多项式是某种算法考虑的主要因素之一。2、状态矩阵和密钥矩阵状态矩阵是指将要被加密的若干数据所形成的矩阵，我们暂且用state_matrix来表示；而密钥矩阵则是指密钥数据所形成的矩阵，我们暂且用cipher_matrix来表示。随着输入数据个数的不同，这两个矩阵的维数可以为44,4648或者；例如如果输入的被加密数据为24个字符（此处假定是以字符为数据单位进行加密，当然也可以是以一个整数为单位等进行加密），输入的密钥数据为16个字符（假设与上同），那么可以形成一个46维的state_matrix矩阵和一个44维的cipher_matrix矩阵。可见形成的矩阵的行数是固定的，都为4。因为矩阵的形成是以每4个数据为一列依次构成，所以随着数据的增加只会增加其列数而不会影响其行数。并且我们用Nb表示被加密数据矩阵（state_matrix矩阵）的列数，用Nk表示密钥数据矩阵（cipher_matrix矩阵）的列数。那么有了上述两个矩阵，我们就可以进行AES的加密过程了。3、扩展密钥扩展密钥是从密钥矩阵变换而来，之所以称之为“扩展”是因为在AES的加密过程中，要对数据进行Nr+1轮加密，每次加密的密钥都不一样，我们将着Nr+1轮加密过程中用到的所有的密钥的集合叫做扩展密钥。那么如何去确定这个轮数Nr呢？Nr的取值是根据Nb和Nk的值确定的，AES算法中给出了它们之间如下的对照表：NrNb=4Nb=6Nb=8Nk=4101214Nk=6121214Nk=8141414例如：如果Nb=6，Nk=4那么我们的加密过程应该进行Nr+1=13次，那么也就有13个扩展密钥。由于这些密钥要和state_matirx矩阵做异或运算，所以每个扩展密钥必须转化为一个和state_matirx矩阵同维数的加密矩阵才可以进行每个元素一对一的运算。由Nb和Nr的值，我们可以计算出扩展密钥的整体“长度”。如下公式可以给出：Nb*（Nr+1）；例如Nb=6，Nr=12则“长度”为78；这78个数字每6个为一个扩展密钥（因为Nb=6，所以要这样分组）。那么这78个数字是怎么形成的呢？AES算法中将形成扩展密钥的过程定义为：KeyExpansion()。该过程以cipher_matrix矩阵的值，每一列的4个byte组成一个int数，那么对于Nk=4的cipher_matrix而言必然可以构成4个int数，KeyExpansion()过程（过程的具体实现参照相关文献）就是以这4个整型数为基础，通过它的扩展方式将这4个数字扩展成了78个数字。这78个数字，每6个组成一个密钥（再将int化为char型恰好构成一个46维的扩展密钥矩阵），总共进行13次加密过程。为了存储这78个数字，算法中开辟一个W[i]数组。显然该数组的维数为W[Nb*(Nr+1)]。4、AES加密过程1#前面的Nr轮（0~Nr-1）被称之为Round()过程：Round(){ByteSub();//字节变换过程，该过程参照S_box实现ShiftRow();//行交换过程，该过程参照既定的交换规则实现MixColumn();//列变换过程，该过程参照C(x)矩阵实现AddRoundKey();//扩展密钥加密过程，该过程参照扩展密钥实现}2#最后一轮加密过程（第Nr轮）被称为FinalRound()过程：FinalRound(){ByteSub();ShiftRow();AddRoundkey();}在上述过程中，ByteSub(),ShiftRow(),MixColumn()三个过程的变换是固定的模式，具体的实现可以参照相关文献。它们的调用次数分别为：Nr+1次，Nr+1次，Nr次。而AddRoundkey()过程显然是Nr+1次，它是与扩展密钥相关的。前Nr轮加密中用去了Nr个扩展密钥，第Nr轮加密中用去最后一个扩展密钥，从而实现Nr+1轮加密过程。至此AES算法结束。三、AES算法的实现方案AES加密算法主要分为三大块，即密钥扩展，数据加密和数据解密。1、密钥扩展（1）使用Rotword()函数对数组中的数字实现循环左移一位的运算，即将数组中左端第一个数字移至数组的末端，而原来在它之后的数字依次前移一位。要说明的是，由于数组中的4个数字已经合并为一个数字，因此在程序的实际执行过程中并不是做数组的循环左移运算，而是进行数字的循环移位运算，这样一来便大大简化了运算过程，对运算效率有一定程度的提高。（2）使用SubWord()函数依据S置换表对4个数字进行置换，规则如下。例如，有一个数字为0x2a，则在表1•1中查找‘2’行‘a’列的数字，得到数字e5，则该数字即是数字0x2a的置换数字。此函数的C语言实现相对简单，只是一个查表的问题，但过程比较繁琐细碎，编成时应仔细对待，避免出错。2、数据加密（1）使用SubByte()函数依据S置换表对状态矩阵State[4][4]中的数字进行置换，查表的方法在前文已经介绍，这里不再赘述。有一点需要注意的是，虽然SubByte()函数与SubWord()函数原理相同，但在程序中的运算过程却不尽相同。SubByte()函数是提取状态矩阵State[4][4]中的每一个数组元素进行置换运算，而SubWord()则是提取一unsignedlong整型数字中的某8位数据进行置换运算。SubByte()函数的C语言实现与SubWord()的C语言实现雷同，这里也不再赘述。（2）使用ShiftRow()函数对状态矩阵State[4][4]中的各行数据进行循环移位运算。该函数所进行的循环移位规则如下。状态矩阵State[4][4]中的第一行数据位置不变，第二行数据循环左移一位数字，第三行数据循环左移两位数字，第四行数据循环左移三位数字。在对ShiftRow()函数进行C语言编程时主要是要注意行数以及所对应的移位个数，保证运算的准确性。3、数据解密（1）使用InvSubByte()函数依据S置换表的逆表对状态矩阵State[4][4]中的数字进行置换，置换方法与SubByte()函数相同。该函数的C语言实现与SubByte()函数基本相同，在此不再赘述。（2）使用InvShiftRow()函数对状态矩阵State[4][4]中的各行数据进行循环移位运算。该函数所进行的循环移位规则如下。状态矩阵State[4][4]中的第一行数据位置不变，第二行数据循环右移一位数字，第三行数据循环右移两位数字，第四行数据循环右移三位数字。四、AES实现过程分析AES算法是基于置换和代替的，置换是数据的重新排列，而代替是用一个单元数据替换另一个，其基本密码算法Rijndael使用的是置换-组合架构，而非Feistel架构。AES是一个新的可以用于保护电子数据的加密算法。AES使用了几种不同的技术来实现置换和替换。通过分组密码返回的加密数据的位数与输入数据相同。迭代加密使用一个循环结构，在该循环中重复置换（permutations）和替换(substitutions）输入数据。对AES算法按加密处理和密钥调度两个方面进行分析：1、加密处理加密处理过程：加密时，各轮AES加密循环（除最后一轮外）均包含4个步骤：（1）、SubBytes—透过一个非线性的替换函数，用查找表的方式把每个字节替换成对应的字节。（2）、ShiftRows—将矩阵中的每个横列进行循环式移位。（3）、MixColumns—为了充分混合矩阵中各个直行的操作。这个步骤使用线性转换来混合每行内的四个字节。（4）、AddRoundKey—矩阵中的每一个字节都与该次循环的子密钥（roundkey）做XOR运算；每个子密钥由密钥生成方案产生。最后一个加密循环中省略MixColumns步骤，而以另一个AddRoundKey取代。SubBytes步骤在SubBytes步骤中，矩阵中各字节被固定的8位查找表中对应的特定字节所替换,S;bij=S(aij).如图所示：ShiftRows步骤在ShiftRows步骤中,矩阵中每一列的各个字节循环向左方位移。位移量则随着行数递增而递增。在ShiftRows步骤中,矩阵中每一列的各个字节循环向左方位移。位移量则随着行数递增而递增。MixColumns步驟在MixColumns步骤中，每个直行都在modulox4+1之下，和一个固定多项式c(x)作乘法。AddRoundKey步骤AddRoundKey步骤，子密钥将会与原矩阵合并。在每次的加密循环中，都会由主密钥产生一把子密钥（透过Rijndael密钥生成方案产生），这把子密钥大小会跟原矩阵一样，以与原矩阵中每个对应的字节作异或（⊕）加法。类推继续，完成10轮循环：2、AES密钥调度密钥调度包括两个部分：密钥扩展和轮密钥选取。密钥bit的总数＝分组长度×（轮数Round＋1）例如当分组长度为128bits和轮数Round为10时，轮密钥长度为128×(10＋1)＝1408bits。1）、将密码密钥扩展成一个扩展密钥。类推，经过10轮计算，得到如下轮密钥调度表：2）、从扩展密钥中取出轮密钥：第一个轮密钥由扩展密钥的第一个Nb个4字节字，第二个圈密钥由接下来的Nb个4字节字组成，以此类推。五、AES的安全性分析AES算法作为DES算法和MD5算法的替代产品，10轮循环到目前为止还没有被破解。一般多数人的意见是：它是目前可获得的最安全的加密算法。AES与目前使用广泛的加密算法─DES算法的差別在于，如果一秒可以解DES，则仍需要花費1490000亿年才可破解AES，由此可知AES的安全性。AES已被列为比任何现今其它加密算法更安全的一种算法。目前针对AES的破解主要可以从以下几个方面着手：1、暴力破解。如果不针对所有可能的256位密钥使用强力搜索，任何已知的密码分析学攻击都无法对AES密码进行解密，就这一点来说，用AES加密的数据是牢不可破的。如SONY的PSP和WINRAR采用AES128位数据加密,一台128颗POWER