密码学基础与应用——AES算法分析

     AES在中文中表示为高级加密标准，它是分组密码当中的一种，密码学当中又称RIJNDAEL算法，如今是对称密钥加密中最为流行的算法之一，已经被推广为全世界所使用。在这里，小编就给大家介绍一下这个算法的来源以及他的基础知识，希望大家可以通过学习了解这个算法。

　　美国政府于1997年叉开始公开征集新的数据加密标准算法AES，以取代1998年底废止的DES。经过三轮筛选， 2000年10月2日美国政府正式宣布选中比利时密码学家Joan Daemen 和Vincent Rijmen提出的一种密码算法RIJNDAEL作为AES。2001年11月26日，美国政府正式颁布AES为美国国家标准(编号为FIST PUBS 197)。这是密码史上的又一个重要事件，世界各国都高度重视这一事件。目前AES己经被一些国际标准化组织(OSO，IETF, IEEE802.11等)采纳作为标准。RIJNDAEL算法之所以能够最终被选为AES的原因是其安全、性能好、效率高、实用、灵活。

　　RIJNDAEL算法是一个数据块长度和密钥长度都可变的分组加密算法，其数据块长度和密钥长度都可独立地选定为大于等于128位且小于等于256位的32位的任意倍数。而美国颁布AES时却规定数据块的长度为128位、密钥的长度可分别选择为128位，192位或256位。

     AES算法的结构

　　RIJNDAEL算法仍然采用分组密码的一种通用结构:对轮函数实施迭代的结构。只是轮函数结构采用的是代替/置换网络结构(SP 结构)，没有采用DES的Feistel结构。如图2-12 所示 RIJNDAEL的轮函数由以下三层组成。

图2-12 RIJNDAEL的算法结构

　　（1）非线性层：进行非线性S盒变换ByteSub，由16个S盒并置而成，起到混淆的作用。

　　（2）线性混合层：进行行移位变换ShiftRow和列混合变换MixColumn以确保多圈之上的高度扩散。

     （3）密铝加层：进行圈密钥加变换AddRoundKey，将圈密钥简单地异或到中问状态上，实现密钥的加密控制作用。

      AES算法的状态

　　在RIJNDAEL算法中，加解密要经过多次数据变换操作，每一次变换操作产生一个中间结果，称这个中间结果叫做状态。各种不向的密码变换都是对状态进行的。

　　把状态表示为二维字节数组(每个元素为一个字节)，它有四行，Nb列。Nb等于数据块长度除以32数据块长度为128时，Nb=4。数据块长度为192时，Nb=6。数据块长度为256时， Nb=8。因为状态数组有四行，每个元素为一个字节，所以状态的每列便为一个四字节的字。有些密码变换是对字节进行的，有些密码变换是对宇进行的。

　　例如，数据块长度为128的状态如表2-5所示。

表2-5数据块长度为128的状态

      数据块长度为128的状态在进行加密处理的时候，数据块需按照列优先的顺序来写入状态，也就是说要按a_0,0,a_1,0,a_2,0,a_3,0,a_0,1,a_1,1,a_2,1,a_3,1,a_0,2,a_1,2,a_2,2,a_3,2,a_0,3,a_1,3,a_2,3,a_3,3的顺序写入状态中。当加密的操作结束时，密文也需要按照同样的顺序从状态中取出。

　　类似地，密钥也可表示为二维字节数组(每个元素为一个字节)，它有四行，Nk列。Nk等于密钥块长度除32。密钥长度为128的二维字节数组如表2-6所示。密钥也是按照列优先的顺序存储到密钥二维字节数组中，即按k_0,0,k_1,0,k_2,0,k_3,0,k_0,1,k_1,1,k_2,1,k_3,1,k_0,2,k_1,2,k_2,2,k_0,3,k_1,3,k_2,3,k_3,3的顺序把它放到密钥二维字节数组中存储起来。如下表：

表2-6密钥长度为128二维字节数组

     RIJNDAEL算法的迭代圈数Nr由Nb和Nk共同决定，具体取值列在表2-7中。

表2-7算法迭代圈数Nr

     AES算法的轮函数

     RIJNDAEL加密算法的轮函数是由列混合变换MixColumn、S盒变换ByteSub、圈密钥加变换AddRoundKey、行移位变换ShiftRow组成，采用代替/置换网络结构(SP 结构)。用伪C语言可写为:

　　Round(State, RoundKey)

　　( ByteSub(State);

　　ShiftRow(State);

　　MixColumn(State);

　　AddRoundKey(State, RoundKey);

　　加密算法中的最后一圈的轮函数与上面的标准轮函数略有不同。定义如下:

　　FinalRound(State, RoundKey)

　　( ByteSub(State);

　　ShiftRow(State);

　　AddRoundKey(State , RoundKey);

　　容易看出，最后一圈的轮函数与标准轮函数相比，去掉了列混合变换MixColumn(State) 。

1. 列混合变换MixColumn

　　MixColumn变换是对状态的列进行一个混合变换。在MixColumn的变换中,状态中的每一列均可以看作GF（2⁸）上的一个多项式，然后与一个固定多项式c(x)相乘后模多项式x⁴+1其中c(x)为:

　　c(x) =‘03'x³+‘01'x² +‘01x'+'02'                         (2-15)

　　由于c(x)与x⁴+1是互素的，从而可以保证c(x)存在着逆多项式d（x），而c(x)d(x)=l mod x⁴+1。只有在逆多项式d(x)存在的情况下才能够进行正确的解密。

　　 2.S盒变换ByteSub

　　ByteSub需要对状态的每个字节进行替换，也称为S盒变换。而为了确保加密算法是可逆的，ByteSub的变换必须是可逆的。它可以在状态中每个字节上的一种非线性字节变换当中起到作用。

      其步骤为：

　　 ①用乘法逆来代替字节的值，其中'00'的逆就是它自己。

       ②经过①的处理后，字节值再进行下面定义的仿射变换：

                                             

（2-16）

　　需要注意的是:

　　(1)S盒变换的第一步是用乘法逆来代替字节的值，是一种非线性变换。

　　(2) 由于式(1-6)的系数矩阵中每列都有5个1，也就是说如果改变输入中的任意一位，都会使得输出中的5位发生变化。

　　(3)由于式((1-6)的系数矩阵中每行都有5个1，也就是说输出中的每一位与输入中的5位都有关系。

　　(4) ByteSub的变换与DES中得到S盒子相当，是一种8位输入、8位输出的非线性变换，加密算法安全性的关键也是为加密算法提供非线性。

　　3.圈密钥加变换AddRoundKey

　　AddRoundKey变换是利用圈密钥对状态进行模2相加的变换。在这个操作中，圈密钥被简单地异或到状态中去。圈密钥根据圈密钥产生算法通过密钥得到。圈密钥长度等于数据块长度，即与会话密钥KOEXOR,得到B=Nb× 4个S-box,每个S-box有s=8bit。

　　4.行移位变换ShiftRow

　　对状态的行进行循环移位变换就是ShiftRowd的变换。在ShiftRowd变换中，状态的后三行用不同的移位值循环"左"移。第0行不移位，第1行移C1字节，第2行移C2字节，第3行移C3字节。

移位值Cl，C2和C3与M有关，具体为

表2-8移位值

　　 AES算法的圈密钥产生算法

      圈密钥是根据圈密钥产生算法由用户密钥产生得到。它的产生分两步进行:密钥扩展和圈密钥选择。且遵循以下原则。

　　(1)圈密钥的比特总数为数据块长度与圈数加l的积。例如，对于128位的分组长度和10圈迭代，圈密钥的总长度为128(10+1)=1408位。

　　(2)首先将用户密钥扩展为一个扩展密钥。

　　(3)再从扩展密钥中选出圈密钥:第一个圈密钥由扩展密钥中的前Nb个字组成，第二个圈密钥由接下来的Nb个字组成，以此类推。

       1、密钥扩展 

      用一个字(四个字节)元素的一维数组W[b*(Nr+1)]存储扩展密钥。用户密钥包含在数组W最开始的Nk个字中，其他的字由它前面的字经过处理后得到。有Nk小于等于6 和Nk大于6 两种密钥扩展策略.

　　(1)对于Nk≤6，有下面密钥扩展策略:

　　符号说明: CipherKey表示用户的密钥，它是一个有Nk个密钥字的一维数组。W为存储扩展密钥的一维数组。

　　KeyExpansion(CipherKey, W)

　　{ For(I=O; I<NK;I++) p ;< CipherKey[工] W[I]>

　　For(I=O; 1< Nb*(Nr+1); 1++)

　　{Temp=W[I-1];

　　IF(I%Nk= =0)

　　Temp=SubByte(Rot1(Temp) ^Rcon[I!Nk]);

　　W[I] =W[I-Nk] ^Temp;

　　}

　　可以看出，最前面的Nk个字是由用户密钥填充的。这之后的每一个字W[I]等于前面的字W[I斗与Nk个位置之前的字W[I-1]进行的异或。如果I是Nk的整数倍，在异或之前，要先对W[I-l]进行Rotl变换和ByteSub变换，再异或一个圈常数Rcon。

　　其中，Rotl是对一个字里的字节以字节为单位进行循环移位的函数，设W=(A,B,C,D)，则Rotl(W)=(B,C,D,A)。

　　圈常数Rcon与Nk无关，且定义为:

　　Rcon[i]=(RC [i],'00','00', '00' )

　　RC[0]='01'

　　RC[i]=xtime(RC[i-1])

　　(2)对于Nk>6，有下面的密钥扩展策略:

　　KeyExpansion(CipherKey，W)

　　{For(I=0;I<NK;I++) W[I]="CipherKey[I];

　　For(I=0; I<NB*(NR+1);I++)< p>

　　{Temp=W[I-1];

　　IF(I%Nk= =0)

　　Temp=SubByte (Rotl (Temp) ^Rcon[I!Nk]);

　　ELSE 工F(I 宅Nk= =4)

　　Temp=SubByte(Temp);

　　W[I]=W[I-Nk] ^Temp;

}

　　Nk>6的密钥扩展策略与Nk ≤6的密钥扩展策略相比，区别在于当I是4的整数倍时，需要先将W[I-l]进行ByteSub变换。这样就在扩展密钥中增加了部分字的ByteSub变换，从而提高了扩展密钥的安全性。这是因为当Nk>6时密钥很长，仅仅对M的整数倍的位置处的字进行ByteSub变换，就显得ByteSub变换的密度较稀，安全程度不够强。

      2、圈密钥选择

　　圈密钥I由圈密钥缓冲区W[Nb*I]到W[Nb*(I+l)]的字组成。例如，Nb=4且Nk=4的圈密钥选择如图1-8所示。

图2-13 Nb=4且Nk=4的圈密钥选择

　　RIJNDAEL加密与解密算法

　　1.加密算法

　　一个初始圈密钥加、Nr-l 圈的标准轮函数以及最后一圈的非标准轮函数就组成了加密的算法

　　用伪码来表示则让如下:

　　Rijndael(State, CipherKey)

　　KeyExpansion(CipherKey, ExpandedKey)

　　AddRoundKey(State, ExpandedKey)

　　For(I=l;I

　　Round(State，ExpandKey+Nb*I)

　　{ByteSub(state);

　　ShiftRow(State);

　　MixColumn(State);

　　AddRoundKey(State,ExpandedKey+Nb*I)}

　　FinalRound(State,ExpandedKey+Nb*Nr)

　　{ByteSub(State);

　　ShiftRow(State);

　　AddRoundKey(State , ExpandedKey+Nb*Nr); }

　　注意第一步和最后一步都用了圈密钥加，因为任何没有密钥参与的变换都是容易被攻破的。

2. 解密算法

　　由于RIJNDAEL算法不是对合运算，所以RIJNDAEL的解密算法与加密算法不同。根据解密算法应当是加密算法的逆，最直接的办法是担加密算法倒序执行，便得到解密算法。但是这样得到的解密算法不便于工程实现。

　　由于RIJNDAEL设计得非常巧妙，使得我们只要略稍改变一下密钥扩展策略，便可以得到等价的解密算法，等价解密算法的结构与加密算法的结构相同，从而方便了工程实现。等价解密算法中的变换为加密算法中相应变换的逆变换。

　　（1）逆变换

　　ShiftRow的逆是状态的后三行分别移动Nb-C1,Nb-C2和Nb-C3个字节。

　　MixColumn的逆类似于MixColumn，把状态的每列都乘以一个固定的多项式d(x):

　　d(x)=‘OB'X3+OD'X2+'09x'+‘OE'                         （2-17）

　　容易验证，式1-5的c(x)与式1-9的d(x)的积等于单位元'01'。所以d(x)是c(x)的逆多项式。

　　AddRoundKey的逆就是它自己。

　　ByteSub的逆是把S_box的逆作用到状态的每个字节上。ByteSub的逆变换按如下方法得到，首先进行式(18)的逆变换，然后再取GF(28)上的乘法逆。式(1-10)是根据式(1-8)推出的，两式中的矩阵互为逆矩阵。

　　                                                                                                             

    （2-18）

　　（2）逆轮函数的定义

　　逆轮函数的定义如下:

　　Inv_Round(State，Inv RoundKey)

　　{ InvByteSub(State);

　　InvShiftRow(State);

　　InvMixColunm(State);

　　AddRoundKey(State,Inv_RoundKey); }

　　最后一圈的非标准逆轮函数如下:

　　Inv_Fina1Round(State, Inv_RoundKey)

　　{InvByteSub(State);

　　InvShiftRow(State);

　　AddRoundKey(State, Inv_RoundKey);}

　　(3解密算法

　　利用逆轮函数可将解密算法表述如下:

      Inv_Rijndae1(State,CipherKey)

{

　　{Inv_KeyExpansion(CipherKey，Inγ_ExpandedKey) ;

　　AddRoundKey(State，Inv_ExpandedKey+Nb*Nr);

　　For(I= Nr-1;I>0; I--)

　　Inv_Round(State，Inv_ExpandedKey+Nb*I) ) ;

　　{InvByteSub(State);

　　InvShiftRow(State);

　　InvMixCo1umn(State);

　　AddRoundKey(State, Inv_ExpandedKey+Nb*I); }

　　Inv_Fina1Round(State，Inv_ExpandedKey)

　　{InvByteSub(State);

　　InvShiftRow(State);

      AddRoundKey(State，Inv_ExpandedKey); }

}

　　注意:解密算法与加密算法使用的圈密铝的顺序相反。

　　其中解密算法的密钥扩展定义为:

　　(1)加密算法的密钥扩展。

　　(2) 把InvMixColumn应用到除第一圈和最后一圈之外的所有圈密钥上。

　　用伪C码表示如下：

　　Inv_KeyExpansion(CipherKey，Inv_ExpandedKey)

　　Key_Expansion(CipherKey,Inv_ExpandedKey);

　　For(I=1; I<Nr; I++); InvMixCo1umn(Inv_ExpandedKey+Nb*I++)     }

     RIJNDEAEL的安全性

　　RIJNDEAEL算法的安全设计策略是宽轨迹策略(Wide Trai1 Strategy) 。宽轨迹策略是针对差分攻击和线性攻击提出来的。它的最大优点是可以给出算法的最佳差分特征的概率以及最佳线性逼近的偏差界，由此可以分析算法抵抗差分攻击和线性攻击的能力。从而确保密码算法具有所需要的抵抗差分攻击和线性攻击的能力，确保密码算法的安全。

　　以上技术设计，使得RIJNDEAEL密码算法具有很高的安全性。据目前的分析，RIJNDEAEL密码算法能有效抵抗自前己知的攻击，如差分攻击、线性攻击、相关密钥攻击和插值攻击等。目前在理论上攻击RIJNDEAEL密码算法的最有效方法还是穷举攻击，但是阳JNDAEL 密码算法的最短密钥是128位，这使得穷举攻击在实际上是不可能的。

　　RIJNDEAEL的数据块长度和密钥长度都可变，因此能够适应不同的安全应用环境。即使今后计算能力和攻击能力提高了，只要及时提高密钥的长度，便可获得满意的安全，因此密码的安全使用寿命长。

　　当然，就算现在还没有发现RIJNDEAEL的严重的缺陷，但你也不能说它就是完美无缺的，有优点也会有缺点，这世界上哪有事物是真正意义上的完美呢。但RIJNDEAEL对比DES来讲，其安全性肯定是比较较强的，不然也不会用它来替代DES了。