高级加密标准（Advanced Encryption Standard，AES）是当前最流行的对称加密算法，也是一种分组加密算法。于2001年11月26日发布于FIPS PUB 197，并在2002年5月26日成为有效的标准。

什么是分组加密？

​ 分组密码就是把明文分为固定长度的一组一组，每次加密一组数据，直到加密完整个明文数据。主要分为四类：

  • 🔧ECB模式
  • 🔨CBC模式
  • 🛠CFB模式
  • ⛏OFB模式

ECB模式

ECB模式 就是加密完一轮数据，接着加密下一轮数据，不同轮次之间的数据间无任何关系。

ecb

CBC模式

CBC模式 就是上面一轮加密的结果与下一轮的明文进行异或，然后进行加密。因为第一个明文分组没有前面的密文与之异或，故需要一个初始向量IV。

CBC

CFB模式

CFB模式 将加密的结果与明文进行异或得到密文，然后再将密文进行加密再与明文异或得到下一个密文，依次类推。同理，在最开始的时候需要一个初始向量IV。由于是讲加密结果与明文进行异或，故初始化向量会先进行一次异或。🤔其实图上也看得出来。

ecb

OFB模式

将一个初始向量一直加密，每加密一次的结果与明文进行异或得到密文。

ofb

ofb

AES简介

AES是一种对称加密，即：

  • 加密：cipher_text = C(plain_text, key)
  • 解密：plain_text = D(cipher_text, key)

这种加密方式加密速度非常快，适合经常发送数据的场合。缺点是密钥的传输比较麻烦🤯。

general

AES算法根据分组长度可以分为AES-128, AES-192，AES-256，其所要求的秘钥长度和加密轮数也各不相同。本文主要以AES-128为例。

密钥长度（32-bits） 分组长度（32-bits） 加密轮数
AES-128 4 4 10
AES-192 6 4 12
AES-256 8 4 14

密钥生成

密钥生成包括两步：

  • 读入16位密钥key_seed
  • 密钥扩展KeyExpansion

读入16位key_seed没什么好讲的，我们重点讲密钥扩展。

首先，我们要了解在AES算法中的矩阵储存方式。和平常不一样，AES的矩阵顺序是竖排的！

straight_example

类似的，我们的密钥储存在一个4x4的矩阵中，储存顺序如下：

key_matrix

在AES加密过程中我们需要用到11歌矩阵密钥，每个矩阵密钥为128位（32x4）。我们用数组u_int32_t w[44]来储存扩展后的密钥。扩展过程如下：

key_Expansion

  • 对于w[0]、w[1]、w[2]、w[3]直接取key_seed的每列四个元素组成32位数据。例如：w[0] = 0x61626364

  • w[4]~w[43]为扩展所得的密钥，他们的计算公式为
    fomula_ke

    其中Mix(x)=SubWord(RotWord(x))

    • RotWord()为循环左移一位，如输入0x12345678，输出0x34567812。

    • SubWord()为字节替换，就是去查sbox得到新值，和des中的方法是一样的，具体操作我会在加密过程中详细说明的。

    • rcon为轮常量异或，常量数组为

      1
      2
      3
      4
      5
      6
      static const u_int32_t Rcon[14] = { 
          0x01000000, 0x02000000,0x04000000, 0x08000000,
          0x10000000, 0x20000000,0x40000000, 0x80000000,
          0x1b000000, 0x36000000,0x6c000000, 0xd8000000,
          0xbd000000, 0x47000000 
          };

      这里的Rcon计算公式我查阅了很多资料才找到：

      ​ Rcon[i] = Rcon[i-1] * 2

      这个乘法是定义在GF(28)上的

    在我的程序中我没有选择查表法找轮常量，我直接通过计算得到轮常量，这能很方便地把AES-128扩展成AES-196、AES-256。计算代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    static u_int8_t GFMul(int n, u_int8_t s) 
    {
        u_int8_t p = 0;

        for (int i=0; i<8; ++i) 
        {
            if (n & 0x01) 
            {
                p ^= s;
            }
    				
            int flag = (s & 0x80);
            s <<= 1;
            if (flag) 
            {
                s ^= 0x1B; /* x^8 + x^4 + x^3 + x + 1 */
            }
            n >>= 1;
        }

        return p;
    }

密钥扩展就讲完了，我们在这里放一个例子方便日后程序验证。

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
char key_seed[16] = "0123456789ABCDEF";

u_int8_t ket_seed_marix[4][4] = {
		0x30, 0x34, 0x38, 0x43,
		0x31, 0x35, 0x39, 0x44,
		0x32, 0x36, 0x41, 0x45,
		0x33, 0x37, 0x42, 0x46
};

u_int32_t w[44];
w[0] = 0x30313233;
w[1] = 0x34353637;
w[2] = 0x38394142;
w[3] = 0x43444546;
/* 这里我把w[4]~w[7]的计算结果都写出来 */
/* 左移 */
w'[3] = 0x44454643; /* 左移8*3 */
/* 字节替换 */
w''[3] = 0x1b6e5a1a
/* 轮常量异或 */
w[4] = 0x2a5f6829;
/* w[5] ~ w[7]就很简单不赘述了 */
w[5] = 0x1e6a5e1e;
w[6] = 0x26531f5c;
w[7] = 0x65175a1a;

加密

加密流程如图所示：

cipher_general

轮密钥加

轮密钥加是将128位的密钥矩阵与状态矩阵（待加密的数据所保存的矩阵）进行逐位异或。

addRoundKey

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
/**
 * 轮密钥加
 * u_int8_t array[4][4] 状态矩阵
 * u_int32_t *w 即w[44]存储44个32位密钥，每4个组成一个密钥矩阵
 * int round 进行密钥轮加的轮数，用来确定用哪个密钥矩阵
 */
static void addRoundKey(u_int8_t array[4][4], u_int32_t *w, int round)
{
    u_int8_t warray[4][4];

    int j=0;
  	/* 这里把4x32位的密钥矩阵拆成4x4x8位的密钥矩阵 */
    for(int i = 0; i < 4; i++) 
    {
        warray[0][i] = (w[round*4+i]>>24) & 0xff;
        warray[1][i] = (w[round*4+i]>>16) & 0xff;
        warray[2][i] = (w[round*4+i]>>8) & 0xff;
        warray[3][i] = w[round*4+i] & 0xff;
    }
		/* 逐位异或 */
    for(int i = 0; i < 4; i++)
    {
        for(int j = 0; j < 4; j++)
        {
            array[i][j] ^= warray[i][j];
        }
    }
}

字节代换

AES的字节代换其实就是一个简单的查表操作。

状态矩阵中每个元素为8位，高4位决定行，低4位决定列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * S盒
 */
static const int S[16][16] = { 
    0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
    0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
    0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
    0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
    0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
    0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
    0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
    0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
    0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
    0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
    0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
    0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
    0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
    0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
    0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
    0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16 
    };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void subBytes(u_int8_t array[4][4])
{
    for(int i = 0; i < 4; i++)
    {
        for(int j = 0; j < 4; j++)
        {
            /* 确定行 */
          	u_int8_t row = (array[i][j]>>4) & 0x0f;
          	/* 确定列 */
            u_int8_t column = array[i][j] & 0x0f;
          	/* 查表得新字节 */
            array[i][j] = S[row][column];
        }
    }
}

行移位

行移位是一个简单的左循环移位操作。状态矩阵的第0行左移0字节，第1行左移1字节，第2行左移2字节，第3行左移3字节。

ShiftRow

1
2
3
4
5
6
7
8
9
10
11
12
13
void shift_Left_Rows(u_int8_t array[4][4])
{
    u_int8_t tmp[4];
    for(int i = 1; i < 4; i++)
    {
        for(int j = 0; j < 4; j++)
            tmp[j] = array[i][j];
        for(int j = 0; j < 4; j++)
        {
            array[i][j] = tmp[(i+j)%4];
        }
    }
}

列混合

这是加密核心的核心。

列混合通过矩阵相乘来实现，经过移位后的矩阵左乘一个固定的矩阵，得到混淆后的矩阵。

mixColumn1

状态矩阵中的第j列的列混合可以表示为：

mixColumn2

其中矩阵的乘法和加法并不是通常意义上的乘法和加法，而是定义在伽罗华域上的二元运算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void mixColumns(u_int8_t array[4][4])
{
    u_int8_t tempArray[4][4];
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 4; j++)
            tempArray[i][j] = array[i][j];
    
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 4; j++)
        {
            /* GFMul 在密钥扩展求轮常量的时候出现过了 */
          	array[i][j] = 
                GFMul(colM[i][0], tempArray[0][j]) ^ GFMul(colM[i][1], tempArray[1][j])
                ^ GFMul(colM[i][2], tempArray[2][j]) ^ GFMul(colM[i][3], tempArray[3][j]);
        }
}

总结

AES-128的加密步骤都讲完了，整体代码框架为：

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
void aes_128bit(u_int8_t p_array[4][4], u_int32_t *w, char *plain_text, u_int8_t *key)
{
    printf("Encrypting by using 128-bit seed_key...\n");
    printf("plaintext=");
    for(int i=0; i<16; i++)
        printf("%c", plain_text[i]);
    printf("\n");
    printf("seed_key=");
    for(int i=0; i<16; i++)
        printf("%c", key[i]);
    printf("\n");
    
    /* 起始的轮密钥加 */
    addRoundKey(p_array, w, 0);

    for(int i=1; i<10; i++)
    {
        /* 字节代换 */
        subBytes(p_array);
        /* 行移位 */
        shift_Left_Rows(p_array);
        /* 列混合 */
        mixColumns(p_array);
        /* 轮密钥加 */
        addRoundKey(p_array, w, i);
    }

    /* 第十轮(没有列混合) */
    search_sbox(p_array);
    shift_Left_Rows(p_array);
    addRoundKey(p_array, w, 10);

    printf("ciphertext=");
    for(int i=0; i<4; i++)
        for(int j=0; j<4; j++)
            printf("%02X", p_array[j][i]);
    printf("\n");
}

运行结果：

result_128

解密

虽然文章标题是 AES加密解析 但我觉得讲完加密不讲解密有点奇怪，所以我这里就简单讲一下。

既然AES是对称加密，故AES解密就是加密每个步骤都逆过程罢了。

解密流程如下：

deco

这个流程图在密钥轮加的时候还要对密钥进行一次逆列混合，但是在每一轮中，先进行密钥轮加再进行逆行移位也可以实现解密。

所以我的整体架构为：

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
/**
* AES-128解密函数
* p_array是密文
*/
void deaes_128bit(u_int8_t p_array[4][4], u_int32_t *w)
{
    printf("Decrypting...\n");
    /* 起始的轮密钥加 */
    addRoundKey(p_array, w, 10);

    for(int i=9; i>=1; i--)
    {
        /* 逆字节代换 */
        desubBytes(p_array);
        /* 逆行移位 */
        shift_Right_Rows(p_array);       
        /* 密钥轮加 */
        addRoundKey(p_array, w, i);
        /* 逆列混合 */
        demixColumns(p_array);
        
    }
    
    desearch_sbox(p_array);
    shift_Right_Rows(p_array);
    addRoundKey(p_array, w, 0);

    printf("plaintext=");
    for(int i=0; i<4; i++)
        for(int j=0; j<4; j++)
            printf("%c", p_array[j][i]);
    printf("\n");
    printf("==========================================\n");
}

逆字节代换

逆字节代换操作过程和字节代换别无二致，只是查的表不一样罢了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 逆S盒
 */
static const int S2[16][16] = { 
    0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38, 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb,
    0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87, 0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb,
    0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d, 0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e,
    0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2, 0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25,
    0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92,
    0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda, 0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84,
    0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a, 0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06,
    0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02, 0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b,
    0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea, 0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73,
    0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85, 0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e,
    0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89, 0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b,
    0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20, 0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4,
    0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31, 0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f,
    0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d, 0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef,
    0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0, 0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61,
    0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26, 0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d 
    };
1
2
3
4
5
6
7
8
9
10
11
12
void desubBytes(u_int8_t array[4][4])
{
    for(int i = 0; i < 4; i++)
    {
        for(int j = 0; j < 4; j++)
        {
            u_int8_t row = (array[i][j]>>4) & 0x0f;
            u_int8_t column = array[i][j] & 0x0f;
            array[i][j] = S2[row][column];
        }
    }
}

逆行移位

行移位向左移，逆行移位就向右移。

1
2
3
4
5
6
7
8
9
10
11
12
13
void shift_Right_Rows(u_int8_t array[4][4])
{
    u_int8_t tmp[4];
    for(int i = 1; i < 4; i++)
    {
        for(int j = 0; j < 4; j++)
            tmp[j] = array[i][j];
        for(int j = 0; j < 4; j++)
        {
            array[i][j] = tmp[(4-i+j)%4];
        }
    }
}

逆列混合

逆列混合中，状态矩阵所乘的矩阵是列混合里矩阵的逆矩阵。

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * 逆列混合用到的矩阵
 * |0xe 0xb 0xd 0x9|    |0x02 0x03 0x01 0x01|     |1 0 0 0|
 * |0x9 0xe 0xb 0xd|		|0x01 0x02 0x03 0x01| ==\ |0 1 0 0|
 * |0xd 0x9 0xe 0xb|		|0x01 0x01 0x02 0x03| ==/ |0 0 1 0|
 * |0xb 0xd 0x9 0xe|		|0x03 0x01 0x01 0x02|     |0 0 0 1|
 */
static const int decolM[4][4] = { 
    0xe, 0xb, 0xd, 0x9,
    0x9, 0xe, 0xb, 0xd,
    0xd, 0x9, 0xe, 0xb,
    0xb, 0xd, 0x9, 0xe 
    };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void demixColumns(u_int8_t array[4][4])
{
    u_int8_t tempArray[4][4];
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 4; j++)
            tempArray[i][j] = array[i][j];
    
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 4; j++)
        {
            array[i][j] = 
                GFMul(decolM[i][0], tempArray[0][j]) ^ GFMul(decolM[i][1], tempArray[1][j])
                ^ GFMul(decolM[i][2], tempArray[2][j]) ^ GFMul(decolM[i][3], tempArray[3][j]);
        }
}

附录：AES-128加密解密完整代码

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
#include <stdio.h>

/**
 * S盒
 */
static const int S[16][16] = { 
    0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
    0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
    0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
    0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
    0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
    0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
    0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
    0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
    0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
    0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
    0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
    0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
    0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
    0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
    0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
    0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16 
    };
/**
 * 逆S盒
 */
static const int S2[16][16] = { 
    0x52, 0x09, 0x6a, 0xd5, 0x30, 0x36, 0xa5, 0x38, 0xbf, 0x40, 0xa3, 0x9e, 0x81, 0xf3, 0xd7, 0xfb,
    0x7c, 0xe3, 0x39, 0x82, 0x9b, 0x2f, 0xff, 0x87, 0x34, 0x8e, 0x43, 0x44, 0xc4, 0xde, 0xe9, 0xcb,
    0x54, 0x7b, 0x94, 0x32, 0xa6, 0xc2, 0x23, 0x3d, 0xee, 0x4c, 0x95, 0x0b, 0x42, 0xfa, 0xc3, 0x4e,
    0x08, 0x2e, 0xa1, 0x66, 0x28, 0xd9, 0x24, 0xb2, 0x76, 0x5b, 0xa2, 0x49, 0x6d, 0x8b, 0xd1, 0x25,
    0x72, 0xf8, 0xf6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xd4, 0xa4, 0x5c, 0xcc, 0x5d, 0x65, 0xb6, 0x92,
    0x6c, 0x70, 0x48, 0x50, 0xfd, 0xed, 0xb9, 0xda, 0x5e, 0x15, 0x46, 0x57, 0xa7, 0x8d, 0x9d, 0x84,
    0x90, 0xd8, 0xab, 0x00, 0x8c, 0xbc, 0xd3, 0x0a, 0xf7, 0xe4, 0x58, 0x05, 0xb8, 0xb3, 0x45, 0x06,
    0xd0, 0x2c, 0x1e, 0x8f, 0xca, 0x3f, 0x0f, 0x02, 0xc1, 0xaf, 0xbd, 0x03, 0x01, 0x13, 0x8a, 0x6b,
    0x3a, 0x91, 0x11, 0x41, 0x4f, 0x67, 0xdc, 0xea, 0x97, 0xf2, 0xcf, 0xce, 0xf0, 0xb4, 0xe6, 0x73,
    0x96, 0xac, 0x74, 0x22, 0xe7, 0xad, 0x35, 0x85, 0xe2, 0xf9, 0x37, 0xe8, 0x1c, 0x75, 0xdf, 0x6e,
    0x47, 0xf1, 0x1a, 0x71, 0x1d, 0x29, 0xc5, 0x89, 0x6f, 0xb7, 0x62, 0x0e, 0xaa, 0x18, 0xbe, 0x1b,
    0xfc, 0x56, 0x3e, 0x4b, 0xc6, 0xd2, 0x79, 0x20, 0x9a, 0xdb, 0xc0, 0xfe, 0x78, 0xcd, 0x5a, 0xf4,
    0x1f, 0xdd, 0xa8, 0x33, 0x88, 0x07, 0xc7, 0x31, 0xb1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xec, 0x5f,
    0x60, 0x51, 0x7f, 0xa9, 0x19, 0xb5, 0x4a, 0x0d, 0x2d, 0xe5, 0x7a, 0x9f, 0x93, 0xc9, 0x9c, 0xef,
    0xa0, 0xe0, 0x3b, 0x4d, 0xae, 0x2a, 0xf5, 0xb0, 0xc8, 0xeb, 0xbb, 0x3c, 0x83, 0x53, 0x99, 0x61,
    0x17, 0x2b, 0x04, 0x7e, 0xba, 0x77, 0xd6, 0x26, 0xe1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0c, 0x7d 
    };

/**
 * 常量轮值表
 * RC[i] = 2•RC[i-1] 乘法是定义在域GF(2^8)上的。
 */
static const u_int32_t Rcon[14] = { 
    0x01000000, 0x02000000,
    0x04000000, 0x08000000,
    0x10000000, 0x20000000,
    0x40000000, 0x80000000,
    0x1b000000, 0x36000000,
    0x6c000000, 0xd8000000,
    0xbd000000, 0x47000000 
    };

static const int colM[4][4] = { 
    2, 3, 1, 1,
    1, 2, 3, 1,
    1, 1, 2, 3,
    3, 1, 1, 2 
    };

/**
 * 逆列混合用到的矩阵
 */
static const int decolM[4][4] = { 
    0xe, 0xb, 0xd, 0x9,
    0x9, 0xe, 0xb, 0xd,
    0xd, 0x9, 0xe, 0xb,
    0xb, 0xd, 0x9, 0xe 
    };

static void create_Key(u_int8_t *key_seed, u_int32_t *w, int bits);
static void extendKey(u_int32_t *w, int bits);
static int T(u_int32_t num, int round);
u_int32_t Left_Loop(u_int32_t num);
u_int32_t getNumFromSBox(u_int32_t input);

void aes_128bit(u_int8_t p_array[4][4], u_int32_t *w, char *plain_text, u_int8_t *key);
void aes_192bit(u_int8_t p_array[4][4], u_int32_t *w, char *plain_text, u_int8_t *key);
void convert_ToIntArray(char *plain_text, u_int8_t p_array[4][4]);
static void addRoundKey(u_int8_t array[4][4], u_int32_t *w, int round);
void search_sbox(u_int8_t array[4][4]);
void shift_Left_Rows(u_int8_t array[4][4]);
void mixColumns(u_int8_t array[4][4]);
static u_int8_t GFMul(int n, u_int8_t s);

void deaes_128bit(u_int8_t p_array[4][4], u_int32_t *w, char *plain_text, u_int8_t *key);
void shift_Right_Rows(u_int8_t array[4][4]);
void demixColumns(u_int8_t array[4][4]);
void desearch_sbox(u_int8_t array[4][4]);

int main()
{
    u_int8_t key[16] = {
        '0','1','2','3','4','5','6','7',\
        '8','9','A','B','C','D','E','F'
        };
    u_int8_t key2[25] = {
        '0','1','2','3','4','5','6','7',\
        '8','9','A','B','C','D','E','F',\
        '0','1','2','3','4','5','6','7','8'
        };
    u_int8_t key3[32] = {
        '0','1','2','3','4','5','6','7',\
        '8','9','A','B','C','D','E','F',\
        '0','1','2','3','4','5','6','7',\
        '8','9','A','B','C','D','E','F'
        };
    char plain_text[16] = {'A',' ','Q','u','i','c','k',' ','B','r','o','w','n','F','o','x'};

    /* 生成密钥 */
    u_int32_t w[44];
    create_Key(key, w, 128);

    u_int8_t p_array[4][4], static_p_array[4][4];
    /* 将明文转换成 4*4 的数组 */
    convert_ToIntArray(plain_text, p_array);

    /* AES-128 加密 */
    aes_128bit(p_array,w,plain_text,key);
    /* AES-128 解密 */  
    deaes_128bit(p_array,w,plain_text,key);
    /* AES-192 加密 */
    //aes_192bit(p_array,w,plain_text,key);

    

    return 0;
    
}

/**
 * 生成w[44]密钥
 */
static void create_Key(u_int8_t *key_seed, u_int32_t *w, int bits)
{
    for(int i=0; i<4; i++)
    {
        w[i] = key_seed[i*4]<<24 | key_seed[i*4+1]<<16 | key_seed[i*4+2]<<8 | key_seed[i*4+3];
    }
    
    extendKey(w, bits);
}


/**
 * 扩展密钥，结果是把w[44]中的每个元素初始化
 */

static void extendKey(u_int32_t *w, int bits)
{
    int round = 0, n_ex;
    if(bits == 128)
        n_ex = 44;
    else if(bits == 192)
        n_ex = 52;
    else if(bits == 256)
        n_ex = 60;

    for(int i = 4; i < n_ex; i++) 
    {
        if( i % 4 == 0) 
        {
            w[i] = w[i - 4] ^ T(w[i - 1], round);
            round++;//下一轮
        }
        else 
        {
            w[i] = w[i - 4] ^ w[i - 1];
        }
    }
}

/**
 * 密钥扩展中的T函数
 */
static int T(u_int32_t num, int round)
{
    /* 字循环 */
    num = Left_Loop(num);
    /* 字代换 */
    u_int32_t res = getNumFromSBox(num);
    //printf("res = 0x%08x\n", res);
    //printf("return = 0x%08x\n", res^Rcon[round]);
    return res ^ Rcon[round];
}

/**
 * 密钥扩展时的字循环
 */
u_int32_t Left_Loop(u_int32_t num)
{
    u_int8_t tmp = (num >> 24) & 0xff;
    num = num << 8 | tmp;

    return num;
}

/**
 * 密钥扩展时的字代换
 */
u_int32_t getNumFromSBox(u_int32_t input)
{
    u_int8_t arr[4], res[4];

    int j=0;
    for(int i=3; i>=0; i--)
    {
        arr[j] = input >> i*8;
        u_int8_t row = (arr[j]>>4) & 0x0f;
        u_int8_t column = arr[j] & 0x0f;
        res[j] = S[row][column];
        j++;
    }
    u_int32_t output = res[0] << 24 | res[1] << 16 | res[2] << 8 | res[3];

    return output;
}

void convert_ToIntArray(char *plain_text, u_int8_t p_array[4][4])
{
    for(int i=0; i<4; i++)
    {
        for(int j=0; j<4; j++)
        {
            p_array[j][i] = plain_text[i*4+j];
        }
    }
}


void aes_128bit(u_int8_t p_array[4][4], u_int32_t *w, char *plain_text, u_int8_t *key)
{
    printf("Encrypting by using 128-bit seed_key...\n");
    printf("plaintext=");
    for(int i=0; i<16; i++)
        printf("%c", plain_text[i]);
    printf("\n");
    printf("seed_key=");
    for(int i=0; i<16; i++)
        printf("%c", key[i]);
    printf("\n");
    
    /* 起始的轮密钥加 */
    addRoundKey(p_array, w, 0);

    for(int i=1; i<10; i++)
    {
        /* 字节代换 */
        search_sbox(p_array);
        /* 行移位 */
        shift_Left_Rows(p_array);
        /* 列混合 */
        mixColumns(p_array);
        /* 轮密钥加 */
        addRoundKey(p_array, w, i);
    }

    /* 第十轮 */
    search_sbox(p_array);
    shift_Left_Rows(p_array);
    addRoundKey(p_array, w, 10);

    printf("ciphertext=");
    for(int i=0; i<4; i++)
        for(int j=0; j<4; j++)
            printf("%02X", p_array[j][i]);
    printf("\n");
}

void aes_192bit(u_int8_t p_array[4][4], u_int32_t *w, char *plain_text, u_int8_t *key)
{
    ;
}


/**
 * 轮密钥加
 */
static void addRoundKey(u_int8_t array[4][4], u_int32_t *w, int round)
{
    u_int8_t warray[4][4];

    int j=0;
    for(int i = 0; i < 4; i++) 
    {
        warray[0][i] = (w[round*4+i]>>24) & 0xff;
        warray[1][i] = (w[round*4+i]>>16) & 0xff;
        warray[2][i] = (w[round*4+i]>>8) & 0xff;
        warray[3][i] = w[round*4+i] & 0xff;
    }

    for(int i = 0; i < 4; i++)
    {
        for(int j = 0; j < 4; j++)
        {
            array[i][j] ^= warray[i][j];
        }
    }
}

void search_sbox(u_int8_t array[4][4])
{
    for(int i = 0; i < 4; i++)
    {
        for(int j = 0; j < 4; j++)
        {
            u_int8_t row = (array[i][j]>>4) & 0x0f;
            u_int8_t column = array[i][j] & 0x0f;
            array[i][j] = S[row][column];
        }
    }
}

void desearch_sbox(u_int8_t array[4][4])
{
    for(int i = 0; i < 4; i++)
    {
        for(int j = 0; j < 4; j++)
        {
            u_int8_t row = (array[i][j]>>4) & 0x0f;
            u_int8_t column = array[i][j] & 0x0f;
            array[i][j] = S2[row][column];
        }
    }
}

void shift_Left_Rows(u_int8_t array[4][4])
{
    u_int8_t tmp[4];
    for(int i = 1; i < 4; i++)
    {
        for(int j = 0; j < 4; j++)
            tmp[j] = array[i][j];
        for(int j = 0; j < 4; j++)
        {
            array[i][j] = tmp[(i+j)%4];
        }
    }
}

void mixColumns(u_int8_t array[4][4])
{
    u_int8_t tempArray[4][4];
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 4; j++)
            tempArray[i][j] = array[i][j];
    
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 4; j++)
        {
            array[i][j] = 
                GFMul(colM[i][0], tempArray[0][j]) ^ GFMul(colM[i][1], tempArray[1][j])
                ^ GFMul(colM[i][2], tempArray[2][j]) ^ GFMul(colM[i][3], tempArray[3][j]);
        }
}

static u_int8_t GFMul(int n, u_int8_t s) 
{
    u_int8_t p = 0;

    for (int i = 0; i < 8; ++i) {
        if (n & 0x01) {    //
            p ^= s;
        }

        int flag = (s & 0x80);
        s <<= 1;
        if (flag) {
            s ^= 0x1B; /* x^8 + x^4 + x^3 + x + 1 */
        }

        n >>= 1;
    }

    return p;
}

void shift_Right_Rows(u_int8_t array[4][4])
{
    u_int8_t tmp[4];
    for(int i = 1; i < 4; i++)
    {
        for(int j = 0; j < 4; j++)
            tmp[j] = array[i][j];
        for(int j = 0; j < 4; j++)
        {
            array[i][j] = tmp[(4-i+j)%4];
        }
    }
}

void demixColumns(u_int8_t array[4][4])
{
    u_int8_t tempArray[4][4];
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 4; j++)
            tempArray[i][j] = array[i][j];
    
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 4; j++)
        {
            array[i][j] = 
                GFMul(decolM[i][0], tempArray[0][j]) ^ GFMul(decolM[i][1], tempArray[1][j])
                ^ GFMul(decolM[i][2], tempArray[2][j]) ^ GFMul(decolM[i][3], tempArray[3][j]);
        }
}

void deaes_128bit(u_int8_t p_array[4][4], u_int32_t *w, char *plain_text, u_int8_t *key)
{
    printf("Decrypting...\n");
    /* 起始的轮密钥加 */
    addRoundKey(p_array, w, 10);

    for(int i=9; i>=1; i--)
    {
        /* 逆字节代换 */
        desearch_sbox(p_array);
        /* 逆行移位 */
        shift_Right_Rows(p_array);       
        /* 密钥轮加 */
        addRoundKey(p_array, w, i);
        /* 列混合 */
        demixColumns(p_array);
        
    }
    
    desearch_sbox(p_array);
    shift_Right_Rows(p_array);
    addRoundKey(p_array, w, 0);

    printf("plaintext=");
    for(int i=0; i<4; i++)
        for(int j=0; j<4; j++)
            printf("%c", p_array[j][i]);
    printf("\n");
    printf("==========================================\n");
}