学步园

AUTHOR:   Jeffrey.zhu

                                    BLOG：http://blog.csdn.net/gueter/

AES算法的主要数学基础是抽象代数，其中算法中的许多运算是按单字节（8bits）和4字节（32bits）定义的，单字节可看成有限域GF(2⁸)中的一个元素，而4字节则可以看成系数在GF(2⁸)中并且次数小于4的多项式（亦可以理解为：GF(256⁴)），单字节上的运算有两种：有限域GF(2⁸)上一个8次不可约多项式的模加、点乘（为方便代码实现，推出了X乘的概念），其中，这个不可约多项式为：m(x)= x⁸+x⁴+x³+x+1，类似地，4字节运算也分为两种：模加、乘法（为方便代码实现，推出了模乘的概念），而此时使用的模取M(x)=x⁴+1，由于x⁴+1=( x²+1)( x²+1)= ( x+1) ( x+1) ( x+1) ( x+1)，即非不可约，导致非0多项式乘法逆元（逆元求取主要用到了欧几里德（Euclid）算法）不一定存在，所以在AES算法中，只限于乘一个固定的有逆元的多项式：a(x)={03}x³+{01}x²+{01}x+{02}。

AES（128bits密钥）主要加解密流程如下图所示：

图中左边是加密流程，右边是解密流程，其中，Plaintext为明文，Ciphertext为密文，密钥长度可变，可指定为128、192、256比特，不同密钥长度决定了加解密算法的轮数（128位：10轮，192位：12轮，256位：14轮），算法征集之初，6轮迭代便可抵抗当时世界上已知的所有攻击，AES标准中至少留了4轮余量，按照这种说法，可以推知轮数越多，AES破解难度越大，也就是密钥越长越安全，所以今年8月份有人说256bits密钥长度的AES算法被破解，而128bits未被破解是没有根据的。

理解AES需要知道以下两个概念：

l  状态：算法中间的结果也需要分组，称之为状态，状态可以用以字节为元素的矩阵阵列表示，该阵列有4行，列数N_b为分组长度除32；

l  种子密钥：以字节为元素的矩阵阵列描述，阵列为4行，列数N_k为密钥长度除32，其中根据种子密钥，可以推导出各轮子密钥w[ , ]，此过程亦称作密钥扩展，针对不同密钥长度的密钥扩展算法可以参照阅读AES算法标准发布文档。

    1）下面简单分析一下AES(128bits密钥)的加密流程：

    AESEncrypt (State, ExpandedKey)

    {

        AddRoundKey (State, ExpandedKey); //种子密钥加，实际已经进行过子密钥扩展

        for (i=1; i <Nr; i ++)            //Nr根据密钥长度进行取值   

            Round (State, ExpandedKey+Nb* i);//加密轮函数

        FinalRound (State, ExpandedKey+Nb*Nr);//加密最后一轮轮函数

}

l  加密轮函数：

Round (State, RoundKey)

{

    ByteSub (State); //字节替代变换

    ShiftRow (State);//行移位变换

    MixColumn (State);//列混合变换

    AddRoundKey (State, RoundKey)//子密钥加（其实是一个简单的逐比特模2加）

}

l  加密最后一轮轮函数：

FinalRound (State, RoundKey)

{

    ByteSub (State);//字节替代变换

    ShiftRow (State);//行移位变换

    AddRoundKey (State, RoundKey);//子密钥加

}

以上加密过程具体算法可参照AES标准发布文档，需要注意的地方有以下几点：

l  字节替代变换是一种非线性变换，主要有两个可逆变换组成：求逆元、仿射变换，在具体实现中，根据两个过程的特点，逐一计算00~FF共256种字节替代变换结果，可以推导出一个固定的、加密用的S盒表；

l  列混合变换，即将状态的每一列视为有限域GF(2⁸)上的一个多项式，并将此多项式与一个具有逆元的多项式进行多项式乘法，这个具有逆元的多项式即为前述的a(x)={03}x³+{01}x²+{01}x+{02}，它的逆元为：a^-1(x)={0b}x³+{0d}x²+{09}x+{0e}；

l  基于种子密钥的子密钥扩展过程必须发生在调用加密函数之前，且加密完之后，传送到解密方的是种子密钥，也就是说，在调用解密函数之前也必须基于种子密钥进行子密钥扩展，此外，针对不同的密钥长度有不同的子密钥扩展算法，具体参照AES标准发布文档；

l  最后一轮轮函数之所以去掉列混合，是因为最后一轮的列混合并未增加AES算法的安全性，反而增加其实现难度，降低算法效率。

    2）下面简单分析一下AES(128bits密钥)的解密流程：

AESDecrypt (State, ExpandedKey)

{

    AddRoundKey (State, ExpandedKey+Nb*Nr);//子密钥加

    for (i= Nr-1; i >=1; i --)             // Nr根据密钥长度进行取值

        InvRound (State, InvMixColumn (ExpandedKey+Nb* i));//解密轮函数

    InvFinalRound (State, ExpandedKey);    //解密最后一轮轮函数

}

l  解密轮函数：

InvRound (State, RoundKey)

{

    InvShiftRow (State);//逆移位变换

    InvByteSub (State);//逆字节替代变换

    AddRoundKey (State, RoundKey);//子密钥加

    InvMixColumn (State); //逆列混合变换

}

l  解密最后一轮轮函数：

InvFinalRound (State, RoundKey)

{  

    InvShiftRow (State);//逆移位变换

    InvByteSub (State);//逆字节替代变换

    AddRoundKey (State, RoundKey);//逆列混合变换

}

以上解密过程具体算法可参照AES标准发布文档，需要注意的地方有以下几点：

l  加密过程中的子密钥加的逆变换即为同一子密钥继续加，所以的解密算法调用之前要对扩展后的子密钥进行逆序；

l  加解密是使用同一个S盒表？还是分别采用各自的S盒表？是一个时间复杂度和空间复杂度的权衡（作者在实现中将加解密S盒表分开做）；

l  逆移位变换与逆字节替代变换之间是可以相互调换位置的。

源代码：