关于AES加密的讲解不再叙述，详细内容可参见《密码编码学与网络安全——原理与实践(第六版)》第5章节。这里从代码实现的角度给出AES加密算法的讲解。
首先，给出AES加密算法的总体结构
AES加密分为两部分：迭代变换和密钥扩展。迭代变换具体来讲是下面这样一个过程：
轮密钥加(AddRoundKey)：明文状态字节与对应轮密钥的异或(Xor)操作；
字节代换(Subsitute Bytes)：明文状态字节的非线性变换，实际上就是所谓的S盒映射；
行移位(ShiftRows)：明文状态字节的简单置换；
列混淆(MixColumns)：一个矩阵乘积(定义在有限域GF(2^8)上的矩阵运算)。
上述步骤中要实现构造S盒，S盒的构造过程如下图：
注意到上图中需要在GF(2^8)内求逆以及矩阵运算，包括迭代变换过程中的运算操作，并非简单的实数集上的算术运算，实际上涉及到数论和有限域的一些概念，关于这部分知识还是推荐参考《密码编码学与网络安全——原理与实践(第六版)一书。这里仅从运用的角度进行一些简单讲解，下文所提到的运算操作，在不指明的情况下都默认为在有限域GF(2^8)上的运算。
有限域可以理解为有限个元素的集合，包含加减乘除运算，并且运算必须满足以下条件：
1、封闭性：若任意两元素a·b∈GF(q)，则有a+b∈GF(q) a·b∈GF(q);
2、结合性：若任意a、b、c∈GF(q)，则有(a+b)+c=a+(b+c)，(a·b)c=a(b·c);
3、交换律：若任意a、b∈GF(q)，则有a+b=b+a，a·b=b·a;
4、加法单位元：GF(q)中存在一个元素0，使得对于GF(q)中的任意元素a+0=0+a=a;
5、加法逆元：对于GF(q)中的任意元素a，GF(q)中一定存在元素-a，使得a+(-a)=(-a)+a=0。
AES算法中涉及到的有限域GF(2^8)是一种特殊的有限域，在该有限域内加减运算等效于模2加法运算(或者说等效于异或运算)，乘法运算等效于多项式(将元素对应的二进制作为多项式对应项的系数)乘法运算，具体原因及讲解参见推荐书籍，这里只说结论。
GF(2^8)上的两个元素a,b的乘法运算定义如下：
假设，元素a、b对应的多项式分别为
$$f(x)=\sum_{i=0}^7{a_ix^i}$$
和
$$g(x)=\sum_{i=0}^7{b_ix^i}$$
，则有限域GF(2^8)上定义的乘法运算为
$$h(x)=f(x)*g(x)$$
(注意在合并同类项时的加减法是有限域GF(2^8)内的运算，即模2加)，结果对应的二进制位是多项式h(x)的各项系数。注意到多项式f(x)和g(x)相乘有可能结果次数会超过7次，对于这种情况，需要将结果模除一个8次既约多项式(既约多项式：不可进行因式分解的多项式，这样的8次既约多项式总共有30多个，AES算法只取其中一个
$$m(x)=x^8+x^4+x^3+x+1$$
)以使得结果次数不超过7。这样的定义对于计算机实现显然无从下手，所以有另外的计算机实现的方式。
只考虑乘法x*f(x)，则有
$$x*f(x)=\sum_{i=0}^7{a_ix^{i+1}}$$
，由上述定义规则
$$x*f(x)=(a_7x^8+a_6x^7+a_5x^6+a_4x^5+a_3x^4+a_2x^3+a_1x^2+a_0x) mod m(x)$$，那么就有：
$$x*f(x) = \begin{cases} (a_6a_5a_4a_3a_2a_1a_00), & \text{$a_7=0$} \\ (a_6a_5a_4a_3a_2a_1a_00)\oplus(00011011), & \text{$a_7=0$} \end{cases}$$
这样对于其他乘法运算，可以组合的来处理，比如：
$$f(x)=x^6+x^4+x^2+x+1,g(x)=x^7+x+1,m(x)=x^8+x^4+x^3+x+1$$
，计算如下：
$$f(x)*g(x)=f(x)*x^7 \oplus f(x)*x \oplus f(x)$$
，对于像$$x^7*f(x)$$
，可以通过迭代地乘x来实现。GF(2^8)上的乘法运算规则如上，具体不再多述，下面给出GF(2^8)上乘法运算的代码实现：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31//file: gf_math.c
typedef unsigned char byte; //GF(2^8)内的元素都是8位的
//计算f(x)*x^n
static byte multi_x_n(const byte a, const byte n){
byte temp=a,nn=n;
while(--nn){
if(temp&0x80)
temp = (temp<<1)^0x1B;
else
temp = temp<<1;
}
return temp;
}
//计算f(x)*g(x)
byte multi(const byte a, const byte b){
byte s=0,i=0;
byte temp=b;
while(temp){
i++;
if(temp&0x01)
s ^= multi_x_n(a, i);
temp >>= 1;
}
return s;
}
接下来是构造S盒过程中用到的另一种运算：有限域GF(2^8)上元素的(乘法)逆：
乘法逆的定义是：如果GF(p)(一般域)上的元素a,b满足a*b mod p=1，则称元素a,b互逆，a称作b的乘法逆元(同样地，b也可以称作a的乘法逆元)。 关于乘法逆元的求算，《密码编码学与网络安全——原理与实践(第六版)》中已经有详细讲解，主要是借助欧几里得(求两个整数最大公因子的算法)扩展算法。
在给出乘法逆实现代码之前，有必要先了解一下有限域GF(2^8)上的除法运算。GF(2^8)上的两个元素a,b的模除运算定义如下：
上述计算过程和实数集上的多项式除法相差不大，注意这里的加减运算还是模2加(异或运算)，下面的代码给出了GF(2^8)上的模除实现：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26//file: gf_math.c
//计算x对应的二进制最高位1的位置
static byte indexof_top1(const int x){
byte i=0;
int temp=x;
if(0==x)
return 0;
while(temp>>=1)
i++;
return i;
}
//求有限域GF(2^8)上元素a/b。函数返回值为除法的商，指针r中存放除法得到的余数
byte div(const int a, const byte b, int *r){
byte len=indexof_top1(a)-indexof_top1(b);
int temp_a=a;
byte temp_b=b;
if(a<b){
*r = temp_a;
return 0;
}
temp_a = temp_a^(temp_b<<len);
return (1<<len) | div(temp_a, temp_b, r);
}
以下直接给出求GF(2^8)上元素乘法逆元的代码实现：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22//file: gf_math.c
//求元素b在GF(2^8)上的乘法逆元 *m(x)取x^8+x^4+x^3+x+1
byte extand_gcd(byte b){
byte v=1,w=0;
byte v0=0,w0=1;
byte v_=v0,w_=w0;
int r=0x11B; //m(x)=x^8+x^4+x^3+x+1对应的GF(2^8)上的元素
byte r0=b;
byte q;
int r_=r0;
while(r_){
q = div(r, r0, &r_);
v_ = v^multi(q, v0); v=v0;v0=v_;
w_ = w^multi(q, w0); w=w0;w0=w_;
r = r0;
r0 = r_;
}
return w;
}
S盒构造步骤三：字节到位列向量的转换。等效为矩阵按位的乘法：
S盒实现
1 | //file: s_box.c |
最终得到的S盒如下：
接着是解密钥扩展。AES算法中输入的密钥长度和明文长度一样，为128bit。在加密过程中，实际上每轮加密使用的密钥都是不一样的，这就需要对输入密钥进行扩展，对于10轮的加密，需要扩展出来128bit*10=16*10字节=40*4个32位字。密钥扩展过程如下图所示：
密钥扩展过程可以由递推公式表示为：
$$w_i = \begin{cases} w_{i-4}\oplus g(w_{i-1}), & \text{i%4=0}\\ w_{i-4}\oplus w_{i-1}, & \text{i%4!=0} \end{cases}$$
公式中的函数g又是令一个复杂变换，可以描述为：
输入w是一个32位的字(4个字节$$B_0,B_1,B_2,B_3$$)，输入w经过一轮循环移位变换，即将输入字$$[B_0,B_1,B_2,B_3]$$变换成$$[B_1,B_2,B_3,B_0]$$，接着每个字节经过一次S盒替换，最后再将第一个字节同轮常量Rcon异或。
AES密钥扩展代码实现如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44//file: key.c
typedef unsigned char byte;
byte Key[44][4]={0};
//S盒代换
static byte sub(byte x){
return S[x];
}
//g函数
static void g_function(const byte *x, byte *temp, byte n){
byte RC[10]={0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x80,0x1B,0x36};
temp[0] = sub(x[1])^RC[n];
temp[1] = sub(x[2]);
temp[2] = sub(x[3]);
temp[3] = sub(x[0]);
}
//密钥字异或
static void key_xor(byte *s, const byte *x, const byte *y){
byte i=0;
for(i=0;i<4;i++)
s[i] = x[i]^y[i];
}
//密钥扩展
void keyExpansion(byte *key, byte w[44][4]){
byte i=0,j=0;
byte temp[4];
for(i=0;i<4;i++) //将初始密钥复制到密钥数组里
for(j=0;j<4;j++)
w[i][j] = key[4*i+j];
for(i=4;i<44;i++){
temp[0] = w[i-1][0];
temp[1] = w[i-1][1];
temp[2] = w[i-1][2];
temp[3] = w[i-1][3];
if(i%4==0)
g_function(&w[i-1][0], temp, i/4-1);
key_xor(w[i], w[i-4], temp);
}
}
接下来是AES加密的主干部分——迭代变换：
迭代变换分为四个步骤：
字节代换
1 | //file: aes.c |
行位移
1 | //file: aes.c |
列混淆
1 | //file: aes.c |
轮密钥加
1 | //file: aes.c |
最后，AES加密的完整实现代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41//file: aes.c
//下面三个变量在其他文件中声明为外部变量
byte S[256];
byte key[16];
byte keys[44][4];
//明文初始化(按列排成4x4矩阵形式)
static void init_C(byte *c){
byte i=0,j=0;
byte temp[16];
for(i=0;i<16;i++)
temp[i] = c[i];
for(i=0;i<4;i++)
for(j=0;j<4;j++)
c[i+4*j] = temp[4*i+j];
}
int main(){
byte count=0;
//16字节的明文
byte c[]={0x01,0x23,0x45,0x67,0x89,0xAB,0xCD,0xEF,
0xFE,0xDC,0xBA,0x98,0x76,0x54,0x32,0x10};
init_C(c);
S_box_generator(S); //S盒生成
//初始密钥初始化
key[0]=0x0E; key[1]=0x15; key[2]=0x71; key[3]=0xC9; key[4]=0x47; key[5]=0xD9; key[6]=0xE8; key[7]=0x59;
key[8]=0x0C; key[9]=0xB7; key[10]=0xAD; key[11]=0xD6; key[12]=0xAF; key[13]=0x7F; key[14]=0x67; key[15]=0x98;
keyExpansion(key, keys);
addRoundKey(c, keys); //首先是一次轮密钥加
for(count=0;count<10;count++){
subBytes(c, S);
shiftRows(c);
if(count!=9) //最后一轮迭代不需要列混淆
mixColumns(c, b);
addRoundKey(c, keys+4*(count+1));
}
}
至此，AES加密算法全部实现完成，解密算法可以类似来实现，在此不做探究。
参考资料
1、《密码编码学与网络安全——原理与实践(第六版)》
2、叶夏沉思的博客——AES128加密-S盒和逆S盒构造推导及代码实现