AES算法的主要数学基础是抽象代数,其中算法中的许多运算是按单字节(8bits)和4字节(32bits)定义的,单字节可看成有限域GF(28)中的一个元素,而4字节则可以看成系数在GF(28)中并且次数小于4的多项式(亦可以理解为:GF(2564)),单字节上的运算有两种:有限域GF(28)上一个8次不可约多项式的模加、点乘(为方便代码实现,推出了X乘的概念),其中,这个不可约多项式为:m(x)= x8+x4+x3+x+1,类似地,4字节运算也分为两种:模加、乘法(为方便代码实现,推出了模乘的概念),而此时使用的模取M(x)=x4+1,由于x4+1=(
x2+1)( x2+1)= ( x+1) ( x+1) ( x+1) ( x+1),即非不可约,导致非0多项式乘法逆元(逆元求取主要用到了欧几里德(Euclid)算法)不一定存在,所以在AES算法中,只限于乘一个固定的有逆元的多项式:a(x)={03}x3+{01}x2+{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行,列数Nb为分组长度除32;
l 种子密钥:以字节为元素的矩阵阵列描述,阵列为4行,列数Nk为密钥长度除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(28)上的一个多项式,并将此多项式与一个具有逆元的多项式进行多项式乘法,这个具有逆元的多项式即为前述的a(x)={03}x3+{01}x2+{01}x+{02},它的逆元为:a-1(x)={0b}x3+{0d}x2+{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 逆移位变换与逆字节替代变换之间是可以相互调换位置的。
源代码:
/*128bits密钥长度及分组长度AES加解密代码 *作者:Jeffrey.zhu */ #include #include //#include //#include //#include //#include typedef long u32; typedef typedef char u8; static const u32 0xc66363a5U, 0xfff2f20dU, 0x60303050U, 0xe7fefe19U, 0x8fcaca45U, 0xeffafa15U, 0x41adadecU, 0x239c9cbfU, 0x75b7b7c2U, 0x6c36365aU, 0x6834345cU, 0xe2717193U, 0x0804040cU, 0x30181828U, 0x0e070709U, |