上周好几天都在搞AES，总算是把Rijndael算法搞明白了。包括密钥扩展，ByteSub（字节代换），ShiftRow（行移位），MixColumn （列混合），AddRoundKey的过程分析。本片会仔细介绍AES（Rijndael算法），后两篇会介绍AES的java实现和php实现。
AES（Rijndael算法）
Rijndael算法首先是一个密钥分组加密的算法，通过置换（permutations ）和替换(substitutions）迭代加密，进过多轮操作形成密文。AES算是Rijndael算法的一种特殊实现，选的分组为128bit（16字节），密钥可以使用128、192 和 256bit三种。
分组
上面已经说了AES分组为16个字节，下面说说他的排列，其实就是一个4x4的矩阵，不过要注意是竖着排的。
AES原文：a1a2a3a4 a5a6a7a8 a9a10a11a12 a13a14a15a16...
a1 a5 a9 a13
a2 a6 a10 a14
a3 a7 a11 a15
a4 a8 a12 a16
密钥
AES的密钥虽然有三种，但是并不意味着这三种密钥的AES差异很大，相反加密过程其实完全一样，只是种子密钥是128，192，256bit三种而已。密钥在AES与分组数据并没有做非常复杂的变化，其实只是简单的&（与）操作而已。不过又因为AES算法有很多轮，所有单单的种子密钥是不够的，所有AES有自己的扩展密钥的方法。还要提一下，密钥扩展后也是竖着排成方阵的。
key：k1k2k3k4 k5k6k7k8 k9k10k11k12 k13k14k15k16...
k1 k5 k9 k13
k2 k6 k10 k14
k3 k7 k11 k15
k4 k8 k12 k16
轮数
轮数主要跟种子密钥长度有关。一般习惯用Nk表示密钥所含的数据字数，一字表示32bit，也就是4字节，也就是一竖排。128，192，256bit对应Nk=4，6，8，一般习惯用Nr表示轮数，Nr = Nk+6也就是10，12，14。
密钥扩展
对与密钥扩展其实只要关心两点：一是扩展成多长，这个其实跟加密过程有关，暂时只要知道密钥总长度为（分组大小=16个字节）*（Nr+1），也就是4*（Nr+1）字，下面讲过程的时候就会明白为什么要这么长。二是密钥扩展的算法，密钥的算法其实比较复杂，但是却不难理解。
注：Nk密钥字数，字为4字节也就是一竖排。
算法步骤
密钥扩展
Nk ≤ 6
1）最前面的 Nk 个字是由种子密钥填充的。
2）之后的每一个字 W[j] 等于前面的字 W[j-1] 的与 Nk 个位置之前的字 W[j-Nk]的异或。
3）而且对于 Nk 的整数倍的位置处的字，在异或之前，对 W[j-1] 的进行如下变换：
.字节的循环移位 RotByte->即当输入字为 (a,b,c,d) 时，输出字为 (b , c, d, a )
.用 S 盒进行变换次位元组
.异或轮常数 Rcon[i/Nk]
KeyExpansion (byteKey[4*Nk] , W[Nb*(Nr+1)])
{
for (i =0; i < Nk; i ++)
W[i]=(Key[4* i],Key[4* i +1],Key[4* i +2],Key[4* i +3] );
//扩展密钥的前面4个字由种子密钥组成
for (i =Nk; i <Nb*(Nr+1); i ++){
temp=W[i-1];
if (i % Nk= =0)
temp=SubByte (RotByte (temp))^Rcon[i /Nk];
//i是NK的整数倍是要特殊处理
W[i]=W[i-Nk]^ temp;
}
}Nk > 6
KeyExpansion (byte Key[4*Nk] , W[Nb*(Nr+1)])
{
for (i=0; i < Nk; i ++)
W[i]=(Key[4* i], Key[4* i +1], Key[4* i +2], Key[4* i +3] );
//扩展密钥的前面4个字由种子密钥组成
for (i =Nk; i <Nb*(Nr+1); i ++){
temp=W[i -1];
if (i % Nk= =0)
temp=SubByte (RotByte (temp))^Rcon[i /Nk];
//i是NK的整数倍是要特殊处理
else if (i % Nk==4)
temp=SubByte (temp);
//i是4的整数倍是要特殊处理
W[i]=W[i - Nk]^ temp;
}
}异或轮常数 Rcon[i/Nk] :Rcon[i/Nk]=(RC[i/Nk]],’00’,’00’,’00’)（i一定会大于Nk）
RC[1]=‘01’
RC[x]=2⊙RC[x-1]
（其实我也不懂Rcon，不过有人已经算好了如下
RC[1]=(01, 00, 00, 00),
RC[2]=(02, 00, 00, 00),
RC[3]=(04, 00, 00, 00),
RC[4]=(08, 00, 00, 00),
RC[5]=(10, 00, 00, 00),
RC[6]=(20, 00, 00, 00),
RC[7]=(40, 00, 00, 00),
RC[8]=(80, 00, 00, 00),
RC[9]=(1b, 00, 00, 00),
RC[10]=(36, 00, 00, 00)）到此准备工作就完成了
接下来就是真正的加密流程
每一轮分组（源数据）都要经过4种变换，分别是ByteSub ShiftRow MixColumn AddRoundKey
ByteSub（字节代换）
这个比较简单，就是查表替代。对于分组的16字节都进行字节代换就行，还有字节一般写成16进制的也就是如FF这种。sbox如下图：
ShiftRow（行移位）
对于分组4x4有4行，进行如下规则位移
第 0 行不移位，
第1行左移1字节，
第2行左移2字节，
第3行左移3字节。
MixColumn （列混合）
列混合其实比较难理解。原理是数学矩阵相乘，如下图s为原数据，s‘为加密后数据。
不过这里的乘法和加法都是数学域操作，说白了就是一种新的运算。
加法
a+b=a^b
加法就是做两者的异或操作
乘法
0x01*b=b
0x02*b 只要b小于0x80，b<<1。如果b大于或等于0x80，(b<<1)^0x1b
对于大于0x02可以分解成0x02和0x01的算法，这牵扯到数学域GF（2 ^8），可以分解成2的幂次方，在这不多做介绍，其实是本文作者能力有限，讲不清楚。
b * 0x03 = b * (0x02 + 0x01)
= (b * 0x02) + (b * 0x01)
b * 0x0d = b * (0x08 + 0x04 + 0x01)
= (b * 0x08) + (b * 0x04) + (b * 0x01)
= (b * 0x02 * 0x02 * 0x02) + (b * 0x02 * 0x02) + (b * 0x01)
b * 0x09 = b * (0x08 + 0x01)
= (b * 0x02 * 0x02 * 0x02) + (b * 0x01)
b * 0x0b = b * (0x08 + 0x02 + 0x01)
= (b * 0x02 * 0x02 * 0x02) + (b * 0x02) + (b * 0x01)
b * 0x0e = b * (0x08 + 0x04 + 0x02)
= (b * 0x02 * 0x02 * 0x02) + (b * 0x02 * 0x02) + (b * 0x02)AddRoundKey
就是4x4的原数据与4x4的扩展密钥做异或运算
总结
下面是加密流程的伪代码，到此aes算法就介绍完了
Encryption(State,CipherKey){
KeyExpansion(CipherKey, RoundKey)
AddRoundKey(State, RoundKey)//第0轮只做AddRoundKey
For(i=1;i<Nr;i++)
Round(State, RoundKey){
ByteSub(State);
ShiftRow(State);
MixColumn(State);
AddRoundKey(State, RoundKey)}
FinalRound(State, RoundKey){//最后一轮不做mixcolumn
ByteSub(State);
ShiftRow(State);
AddRoundKey(State, RoundKey)；}
} 