admin 管理员组文章数量: 887021
2023年12月23日发(作者:winform按钮美化)
AES算法加解密原理及安全性分析
刘帅卿
一、AES算法简介
AES算法是高级加密标准算法的简称,其英文名称为Advanced Encryption
Standard。该加密标准的出现是因为随着对称密码的发展,以前使用的DES(Data
Encryption Standard数据加密标准)算法由于密钥长度较小(56位),已经不适应当今数据加密安全性的要求,因此后来由Joan Daeman和Vincent Rijmen提交的Rijndael算法被提议为AES的最终算法。
AES是一个迭代的、对称密钥分组的密码,它可以使用128、192和256位密钥,并且用128位(16字节)分组加密和解密数据。与公共密钥密码使用密钥对不同,对称密钥密码使用相同的密钥加密和解密数据。通过分组密码返回的加密数据的位数与输入数据相同。迭代加密使用一个循环结构,在该循环中重复置换(permutations)和替换(substitutions)输入数据。加之算法本身复杂的加密过程使得该算法成为数据加密领域的主流。
二、AES算法的基本概念
1、有限域(GF)
由于AES算法中的所有运算都是在有限域当中进行的,所以在理解和实现该算法之前先得打好有限域这一基石才行。通常的数学运算都是在实数域中进行,而AES算法则是在有限域中进行,我们可以将有限域看成是有确定边界范围的正整数集合,在该集合当中,任意两个元素之间的运算结果都仍然落在该集合当中,也即满足运算封闭性。
那么如何才能保证这样的“有限性”(也即封闭性)呢?
GF(2w)被称之为伽罗华域,是有限域的典型代表。随着w(=4,8,16,…)的取值不同所形成的有限域范围也不同。AES算法中引入了GF域当中对数学运算的基本定义:将两数的加减法定义为两者的异或运算;将两数的乘法定义为多
项式间的相乘并求余运算,其中被用于求余运算的除数被称为不可约多项式(或843者称为求余多项式),它是固定的一个多项式:m(x) =xxxx1(数值为十六进制的11B,这里是假定w=8时的情形)。对于某个有限域而言,可能存在不唯一的不可约多项式,选择合适的多项式是某种算法考虑的主要因素之一。
2、状态矩阵和密钥矩阵
状态矩阵是指将要被加密的若干数据所形成的矩阵,我们暂且用state_matrix来表示;而密钥矩阵则是指密钥数据所形成的矩阵,我们暂且用cipher_matrix来表示。随着输入数据个数的不同,这两个矩阵的维数可以为44,46或者48;例如如果输入的被加密数据为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算法中给出了它们之间如下的对照表:
Nr
Nk=4
Nk=6
Nk=8
Nb=4
10
12
14
Nb=6
12
12
14
Nb=8
14
14
14
例如:如果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()过程:
{
ByteSub(); //字节变换过程,该过程参照 Round()
S_box实现
ShiftRow(); //行交换过程,该过程参照既定的交换规则实现
阵实现
AddRoundKey(); //扩展密钥加密过程,该过程参照 MixColumn(); //列变换过程,该过程参照C(x)矩扩展密钥实现
}
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()则是提取一unsigned long 整型数字中的某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 — 矩阵中的每一个字节都与该次循环的子密钥(round
key)做XOR运算;每个子密钥由密钥生成方案产生。
最后一个加密循环中省略MixColumns步骤,而以另一个AddRoundKey取代。
SubBytes 步骤
在SubBytes步骤中,矩阵中各字节被固定的8位查找表中对应的特定字节所替换,S; bij = S(aij).如图所示:
ShiftRows 步骤
在ShiftRows 步骤中,矩阵中每一列的各个字节循环向左方位移。位移量则随着行数递增而递增。在ShiftRows 步骤中,矩阵中每一列的各个字节循环向左方位移。位移量则随着行数递增而递增。
MixColumns 步驟
在 MixColumns 步骤中,每个直行都在modulo x4 + 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处理器的巨型计算器破解128BIT的AES需要225年。要破解AES加密过的数据,需要当今最强大的计算机计算1010年时间。如果密钥长度为 256 位,还没有已知的攻击可以在一个可接受的时间内破解 AES。
2、时间选择攻击。针对 AES 密码最可能成功的攻击来自一个允许时间选择攻击的弱实现。攻击者用不同的密钥并精确地测量出加密例程所需的时间。如果加密例程被粗心编码 ,因此执行时间便依赖于密钥值,它就有可能推导出有关密钥的信息。在 AES 中,这种事情最可能发生在 MixColumns 例程中,因为有域乘。针对这种攻击的两个安全措施是加入虚指令,以便所以所有乘法都需要相同数量的指令,或者将域乘实现为一个查询表。
3、旁道攻击。针对AES唯一的成功攻击是旁道攻击。旁道攻击不攻击密码本身,而是攻击那些实作于不安全系统(会在不经意间泄漏资讯,如Cache等)上的加密系统。
4、数学结构攻击:不像其他区块加密系统,AES具有相当井然有序的代数结构。虽然相关的代数攻击尚未出现,但有许多学者认为,把安全性建立于未经透彻研究过的结构上是有风险的。
5、能量攻击法:与软件加密相比,硬件加密具有运行速度更快,保密性更强的优点,所以硬件加密设备已在通信、金融和信息安全等领域中得到广泛的应用。但是硬件加密设备运行时必须消耗能量,整个能量消耗过程可以通过电流或电压的变化反映出来。这种能量消耗包含了设备当前正在处理的数据的信息,而这些数据又与加密密钥有关,所以攻击者可以通过测量并分析能量消耗数据破解密钥,突破硬件加密系统,这种攻击被称为能量分析攻击,它是一种强有力的密码分析新方法。如边频攻击:通过观测电路中的物理量如能量耗散、电磁辐射和执行时间的变化规律,攻击者能够分析系统中的加密数据或者干扰系统的加密行为,这即是边频攻击(Side-channel Attacks)。PA攻击是目前应用最为广泛的,成本较低的一种。
6、基于AES对称性的攻击方法:该思想利用了AES的对称性,并在此基础上把逆序Square攻击扩展到7轮,同时提出逆序碰撞攻击的概念,并以此对
7轮AES进行分析.结果表明该方法的效率是相当高的,其复杂度大约是2,需选择2组密文。但对7轮以后的攻击结果不明。
7、远程侵入:由于目前AES技术上是“安全的”,可以考虑从远程侵入想要攻击的对象,以获取相应的明码或密钥,或在其网络传输过程中进行窃获。如不能得到其数据,可考虑在传输过程中想办法破坏其数据,也可达到一定的目的,或许更实用。
六、小结
总之,AES密码是一个非对称密码体制,它的解密要比加密复杂和费时。解密优化算法没有增加存储空间的基础上,以列变化为基础进行处理,程序比原始的要小,而且节约了时间。解密优化方法速度最快,效率最高,但要增加系统的存储空间,因此它的程序也是最大的一个。AES高级数据加密算法不管是从安全性、效率,还是密钥的灵活性等方面都优于DES数据加密算法,在今后将逐步代替DES而被广泛应用。
参考文献:
1、 Joan Daemen, Vicent Rijmen. 高级加密标准(AES)算法——Rijndael的设计[M]. 谷大武, 徐胜波译. 北京: 清华大学出版社, 2003.
2 、杨义先.现代密码新理论.北京:科学出版社,2002
3 、谷大武,等.高级加密标准(AES)算法—Rijndael的设计.北京:清华大学出版社,2003
4 、(美) Behrouz an,马振晗 贾军保译. 密码学与网络安全[M] . 北京:清华大学出版社, 2009年
5、 (美) William Stallings.杨明 胥光辉 齐望东等译.密码编码学与网络安全:原理与实践[M] . 北京:电子工业出版社 2001年
6 、NIST. Advanced Encryption Standard (AES) .Federal Information Processing
Standards Publication,2001
版权声明:本文标题:AES算法加解密原理及安全性分析(DOC) 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.freenas.com.cn/free/1703301886h446091.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论