Felix

技术源于积累,成功始于执着! 个人邮箱:justlxy@mail.dhu.edu.cn QQ:1576109464

【转】详解AES加密算法

0
阅读(365) 评论(0)

AES加密算法是密码学中的高级加密标准(Advanced Encryption Standard,AES),又称Rijndael加密法,是美国联邦政府采用的一种区块加密标准。这个标准用来替代原先的DES,已经被多方分析且广为全世界所使用。经过五年的甄选流程,高级加密标准由美国国家标准与技术研究院(NIST)于2001年11月26日发布于FIPS PUB 197,并在2002年5月26日成为有效的标准。


一、AES简介

  我们知道数据加密标准(Data Encryption Standard: DES)的密钥长度是56比特,因此算法的理论安全强度是256。但二十世纪中后期正是计算机飞速发展的阶段,元器件制造工艺的进步使得计算机的处理能力越来越强,DES将不能提供足够的安全性。1997年1月2号,美国国家标准技术研究所(National Institute of Standards and Technology: NIST)宣布希望征集高级加密标准(Advanced Encryption Standard: AES)[3],用以取代DES。AES得到了全世界很多密码工作者的响应,先后有很多人提交了自己设计的算法。最终有5个候选算法进入最后一轮:Rijndael,Serpent,Twofish,RC6和MARS,下图分别为其中的5位作者。最终经过安全性分析、软硬件性能评估等严格的步骤,Rijndael算法获胜。

  Rijndael由比利时两位非常著名的密码学家Joan Daemen和Vincent Rijmen设计。Rijndael是一个分组密码算法族,其分组长度包括128比特、160比特、192比特、224比特、256比特,密钥长度也包括这五种长度,但是最终AES只选取了分组长度为128比特,密钥长度为128比特、192比特和256比特的三个版本。本文主要结合AES-128进行介绍,AES-196和AES-256的思路基本一样,只是密钥扩展算法的过程会稍有不同,加解密的轮数会适当增加,但加解密的操作都是一样的。另外,本文只对AES算法的各个模块、基本原理进行介绍,旨在加深对算法流程、密码算法实现的了解。在正式软件运用中并不推荐自己编写代码,很多开源项目如Linux,OPENSSL,SRTP等都有非常高效的实现。由于数学知识的缺陷,本文不介绍算法安全性分析相关的知识,有兴趣的读者可以自行阅读相关文献。

  AES是一个分组密码,属于对称密码范畴,AES算法的模块在对称密码领域特别是分组密码领域常有使用。


二、算法流程

  AES加密算法涉及4种操作:字节替代(SubBytes)、行移位(ShiftRows)、列混淆(MixColumns)和轮密钥加(AddRoundKey)。下图给出了AES加解密的流程,从图中可以看出:1)解密算法的每一步分别对应加密算法的逆操作,2)加解密所有操作的顺序正好是相反的。正是由于这几点(再加上加密算法与解密算法每步的操作互逆)保证了算法的正确性。加解密中每轮的密钥分别由种子密钥经过密钥扩展算法得到。算法中16字节的明文、密文和轮子密钥都以一个4x4的矩阵表示。

11.png


2.1、字节代替

  字节代替的主要功能是通过S盒完成一个字节到另外一个字节的映射。S盒的详细构造方法可以参考文献[4]。这里直接给出构造好的结果,下图(a)为S盒,图(b)为S-1(S盒的逆)。S盒用于提供密码算法的混淆性

12.png

2.png

  S和S-1分别为16x16的矩阵,完成一个8比特输入到8比特输出的映射,输入的高4-bit对应的值作为行标,低4-bit对应的值作为列标。假设输入字节的值为a=a7a6a5a4a3a2a1a0,则输出值为S[a7a6a5a4][a3a2a1a0],S-1的变换也同理。

  例如:字节00000000B替换后的值为(S[0][0]=)63H,再通过S-1即可得到替换前的值,(S-1 [6][3]=)00H


2.2、行移位

  行移位是一个4x4的矩阵内部字节之间的置换,用于提供算法的扩散性

  1) 正向行移位

  正向行移位用于加密,其原理图如下。其中:第一行保持不变,第二行循环左移8比特,第三行循环左移16比特,第四行循环左移24比特。

  假设矩阵的名字为state,用公式表示如下:state’[i][j] = state[i][(j+i)%4];其中i、j属于[0,3]。

3.png

  2) 逆向行移位

  逆向行移位即是相反的操作,即:第一行保持不变,第二行循环右移8比特,第三行循环右移16比特,第四行循环右移24比特。

  用公式表示如下:state’[i][j] = state[i][(4+j-i)%4];其中i、j属于[0,3]。


2.3、列混淆

  列混淆:利用GF(28)域上算术特性的一个代替,同样用于提供算法的扩散性

  1) 正向列混淆

  正向列混淆的原理图如下:

4.png

  根据矩阵的乘法可知,在列混淆的过程中,每个字节对应的值只与该列的4个值有关系。此处的乘法和加法都是定义在GF(28)上的,需要注意如下几点:

  1) 将某个字节所对应的值乘以2,其结果就是将该值的二进制位左移一位,如果原始值的最高位为1,则还需要将移位后的结果异或00011011;[1]

  英文原文描述如下:In particular, multiplication of a value by x (i.e., by {02}) can be implemented as a 1-bit left shift followed by a conditional bitwise XOR with (0001 1011) if the leftmost bit of the original value (prior to the shift) is 1.

  2) 乘法对加法满足分配率,例如:07·S0,0=(01⊕02⊕04)·S0,0= S0,0⊕(02·S0,0)(04·S0,0)

  3) 此处的矩阵乘法与一般意义上矩阵的乘法有所不同,各个值在相加时使用的是模28加法(异或运算)。

  下面举一个例子,假设某一列的值如下图,运算过程如下:

  在计算02与C9的乘积时,由于C9对应最左边的比特为1,因此需要将C9左移一位后的值与(0001 1011)求异或。同理可以求出另外几个值。

  2) 逆向列混淆

  逆向列混淆的原理图如下:

  说明两个矩阵互逆,经过一次逆向列混淆后即可恢复原文。


2.4、轮秘钥加

  这个操作相对简单,其依据的原理是“任何数和自身的异或结果为0”。加密过程中,每轮的输入与轮子密钥异或一次;因此,解密时再异或上该轮的轮子密钥即可恢复。


2.5、秘钥扩展算法

  密钥扩展的原理图如下:

9.png

  密钥扩展过程说明:

  1)  将种子密钥按图(a)的格式排列,其中k0、k1、……、k15依次表示种子密钥的一个字节;排列后用4个32比特的字表示,分别记为w[0]、w[1]、w[2]、w[3];

  2)  按照如下方式,依次求解w[j],其中j是整数并且属于[4,43];

  3)  若j%4=0,则w[j]=w[j-4]⊕g(w[j-1]),否则w[j]=w[j-4]⊕w[j-1];

  函数g的流程说明:

  a)  将w循环左移8比特;

  b)  分别对每个字节做S盒置换;

  c)  与32比特的常量(RC[j/4],0,0,0)进行异或,RC是一个一维数组,其值如下。(RC的值只需要有10个,而此处用了11个,实际上RC[0]在运算中没有用到,增加RC[0]是为了便于程序中用数组表示。由于j的最小取值是4,j/4的最小取值则是1,因此不会产生错误。)

      RC = {0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1B, 0x36}


2.6、小结

  密码算法要求是可逆的,这样解密算法才能正确的恢复明文。拿AES来说,在密钥固定的情况下,明文和密文在整个输入空间是一一对应的。因此算法的各个部件也都是可逆的,再将各个部件的操作顺序设计成可逆的,密文就能正确的解密了。


三、AES加密算法的几种模式

3.1、ECB模式

优点:
1.简单; 
2.有利于并行计算; 
3.误差不会被传送; 
缺点: 
1.不能隐藏明文的模式; 
2.可能对明文进行主动攻击; 


3.2、CBC模式

优点: 
1.不容易主动攻击,安全性好于ECB,适合传输长度长的报文,是SSL、IPSec的标准。 
缺点:
1.不利于并行计算; 
2.误差传递; 
3.需要初始化向量IV


3.3.、CFB模式

优点:
1.隐藏了明文模式; 
2.分组密码转化为流模式; 
3.可以及时加密传送小于分组的数据; 
缺点: 
1.不利于并行计算; 
2.误差传送:一个明文单元损坏影响多个单元; 
3.唯一的IV; 


3.4、OFB模式

优点:
1.隐藏了明文模式; 
2.分组密码转化为流模式; 
3.可以及时加密传送小于分组的数据; 
缺点: 
1.不利于并行计算; 
2.对明文的主动攻击是可能的; 
3.误差传送:一个明文单元损坏影响多个单元; 


参考阅读:

1、http://www.cnblogs.com/luop/p/4334160.html

2、http://www.baike.com/wiki/AES%E5%8A%A0%E5%AF%86%E7%AE%97%E6%B3%95

3、128-位和-256-位-AES-加密.pdf