AES加密算法从原理到CPP实现#

1
k0 k1 k2 k3 k4 k5 k6 k7 k8 k9 k10 k11 k12 k13 k14 k15
2

3
每4字节为一个字
4

5
W[0] = [ k0  k1  k2  k3  ]
6
W[1] = [ k4  k5  k6  k7  ]
7
W[2] = [ k8  k9  k10 k11 ]
8
W[3] = [ k12 k13 k14 k15 ]

1
// ============================================================
2
// AES 常量表
3
// ============================================================
4
namespace tables
5
{
6

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

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

45
    // 轮常数 Rcon（只用到前 10 个）
46
    constexpr std::array<uint8_t, 11> RCON = {
47
        0x00, // 不用
48
        0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1B, 0x36};
49

50
} // namespace tables

1
// ============================================================
2
// GF(2^8) 乘法 公式：c = a · b mod m(x)
3
// ============================================================
4
static inline uint8_t gf_mul(uint8_t a, uint8_t b)
5
{
6
    uint8_t p = 0;//p是累加器，返回值也是他。
7
    for (int i = 0; i < 8; i++)
8
    {//循环8次，意味着是bit视角
9
        if (b & 1)//每次从b的最后一个bit开始看，如果 b 当前最低位是 1，就把 a 异或进 p。
10
            p ^= a;//相当于普通乘法里的“这一位有值，我们给他加上，在GF(2^8)里异或就是加法。
11
        uint8_t hi = a & 0x80; //看 a 的最高位是不是 1。hi 只用于判断，后面左移后要异或 0x1B。
12
        a <<= 1; //a 左移一位，相当于“乘以 x（也就是乘以 2）”
13
        if (hi) //如果刚才最高位是 1，左移后溢出了 x^8 项。
14
            a ^= 0x1B; // AES 不可约多项式 x^8 + x^4 + x^3 + x + 1
15
        b >>= 1;  //b 右移一位，处理下一位。
16
    }
17
    return p;
18
}
19

20
// 快速版：乘 2 和乘 3
21
static inline uint8_t xtime(uint8_t x)
22
{
23
    return (uint8_t)((x << 1) ^ ((x & 0x80) ? 0x1B : 0x00));
24
}
25
static inline uint8_t mul2(uint8_t x) { return xtime(x); }
26
static inline uint8_t mul3(uint8_t x) { return xtime(x) ^ x; }

1
// ============================================================
2
// PKCS#7 填充（块大小 16）
3
// ============================================================
4
namespace pkcs7
5
{
6

7
    std::vector<uint8_t> pad(const std::vector<uint8_t> &data, size_t blockSize)
8
    {
9
        size_t padLen = blockSize - (data.size() % blockSize);
10
        std::vector<uint8_t> out = data;
11
        out.insert(out.end(), padLen, static_cast<uint8_t>(padLen));
12
        return out;
13
    }
14

15
    std::vector<uint8_t> unpad(const std::vector<uint8_t> &data)
16
    {
17
        if (data.empty())
18
            throw std::runtime_error("empty data");
19

20
        uint8_t padLen = data.back();
21
        if (padLen == 0 || padLen > 16 || padLen > data.size())
22
        {
23
            throw std::runtime_error("invalid PKCS#7 padding");
24
        }
25
        for (size_t i = data.size() - padLen; i < data.size(); ++i)
26
        {
27
            if (data[i] != padLen)
28
            {
29
                throw std::runtime_error("invalid PKCS#7 padding");
30
            }
31
        }
32
        return std::vector<uint8_t>(data.begin(), data.end() - padLen);
33
    }
34

35
} // namespace pkcs7

1
// ============================================================
2
// AES 核心类（AES-128）
3
// ============================================================
4
class AES128
5
{
6
public:
7
    static constexpr size_t BLOCK_SIZE = 16; //分组大小
8
    static constexpr size_t KEY_SIZE = 16;
9
    static constexpr int NR = 10; // 轮数
10

11
    explicit AES128(const std::vector<uint8_t> &key)
12
    {
13
        if (key.size() != KEY_SIZE)
14
        {
15
            throw std::invalid_argument("AES-128 key must be 16 bytes");
16
        }
17
        keyExpansion(key.data());//特妈的上来就扩展，好好好。我们直接看到第90行
18
    }
19

20
    void encryptBlock(uint8_t block[BLOCK_SIZE]) const
21
    {
22
        uint8_t state[4][4];
23
        loadState(state, block);
24

25
        addRoundKey(state, 0);
26

27
        for (int round = 1; round < NR; ++round)
28
        {
29
            subBytes(state);
30
            shiftRows(state);
31
            mixColumns(state);
32
            addRoundKey(state, round);
33
        }
34

35
        // 最后一轮：无 MixColumns
36
        subBytes(state);
37
        shiftRows(state);
38
        addRoundKey(state, NR);
39

40
        storeState(state, block);
41
    }
42

43
    void decryptBlock(uint8_t block[BLOCK_SIZE]) const
44
    {
45
        uint8_t state[4][4];
46
        loadState(state, block);
47

48
        addRoundKey(state, NR);
49

50
        for (int round = NR - 1; round >= 1; --round)
51
        {
52
            invShiftRows(state);
53
            invSubBytes(state);
54
            addRoundKey(state, round);
55
            invMixColumns(state);
56
        }
57

58
        invShiftRows(state);
59
        invSubBytes(state);
60
        addRoundKey(state, 0);
61

62
        storeState(state, block);
63
    }
64

65
private:
66
    uint8_t roundKeys_[11][16]; // 11 个轮密钥
67

68
    // --------------------------------------------------------
69
    // 状态矩阵的加载 / 存储（列优先）
70
    // --------------------------------------------------------
71
    static void loadState(uint8_t state[4][4], const uint8_t block[16])
72
    {
73
        for (int i = 0; i < 16; ++i)
74
        {
75
            state[i % 4][i / 4] = block[i];
76
        }
77
    }
78

79
    static void storeState(uint8_t state[4][4], uint8_t block[16])
80
    {
81
        for (int i = 0; i < 16; ++i)
82
        {
83
            block[i] = state[i % 4][i / 4];
84
        }
85
    }
86

87
    // --------------------------------------------------------
88
    // 密钥扩展：从 16 字节密钥生成 11 个轮密钥
89
    // --------------------------------------------------------
90
    void keyExpansion(const uint8_t key[16])
91
    {
92
        using namespace tables;
93

94
        uint8_t w[44][4]; // 44 个字，每个字 4 字节，一个轮密钥4个字，44也就是11个轮密钥
95

96
        // 前 4 个字 = 原始密钥
97
        for (int i = 0; i < 4; ++i)
98
        {
99
            w[i][0] = key[4 * i + 0];
100
            w[i][1] = key[4 * i + 1];
101
            w[i][2] = key[4 * i + 2];
102
            w[i][3] = key[4 * i + 3];
103
        }
104
        /*
105
        举例
106
        key = 2b 7e 15 16 28 ae d2 a6 ab f7 15 88 09 cf 4f 3c
107
        w[0] = 2b 7e 15 16
108
        w[1] = 28 ae d2 a6
109
        w[2] = ab f7 15 88
110
        w[3] = 09 cf 4f 3c
111
    */
112

113
        // 扩展出后面 40 个字
114
        for (int i = 4; i < 44; ++i)
115
        {
116
            uint8_t temp[4];
117
            std::memcpy(temp, w[i - 1], 4);
118

119
            if (i % 4 == 0)
120
                /*
121
      为什么 i % 4 == 0 才做
122
      每 4 个字是一组轮密钥。
123

124
      每组第一个字需要和上一组“断开”，所以做 RotWord + SubWord + Rcon。
125

126
      后面 3 个字只需要和前一个字、前 4 个字异或，保持链式关系。
127
       */
128
            {
129
                // RotWord：循环左移 1 字节
130
                uint8_t t = temp[0];
131
                temp[0] = temp[1];
132
                temp[1] = temp[2];
133
                temp[2] = temp[3];
134
                temp[3] = t;
135

136
                // SubWord：每字节查 S 盒
137
                for (int j = 0; j < 4; ++j)
138
                {
139
                    temp[j] = SBOX[temp[j]];
140
                }
141

142
                // 异或 Rcon
143
                temp[0] ^= RCON[i / 4];
144
            }
145

146
            // W[i] = W[i-4] ⊕ temp
147
            for (int j = 0; j < 4; ++j)
148
            {
149
                w[i][j] = w[i - 4][j] ^ temp[j];
150
            }
151
        }
152

153
        // 把 44 个字拼成 11 个轮密钥
154
        for (int r = 0; r <= NR; ++r)
155
        {
156
            for (int c = 0; c < 4; ++c)
157
            {
158
                for (int j = 0; j < 4; ++j)
159
                {
160
                    roundKeys_[r][4 * c + j] = w[4 * r + c][j];
161
                }
162
            }
163
        }
164
    }
165

166
    // --------------------------------------------------------
167
    // 四个核心操作
168
    // --------------------------------------------------------
169

170
    // SubBytes：字节替换
171
    // 对 state 中每个字节查 S 盒，做非线性替换
172
    // 这是 AES 里唯一的非线性操作，抵抗线性和差分分析
173
    static void subBytes(uint8_t state[4][4])
174
    {
175
        using namespace tables;
176
        for (int i = 0; i < 4; ++i)              // 遍历 4 行
177
            for (int j = 0; j < 4; ++j)          // 遍历 4 列
178
                state[i][j] = SBOX[state[i][j]]; // 用当前字节做索引查 S 盒
179
    }
180

181
    // InvSubBytes：逆字节替换
182
    // 解密时用，查逆 S 盒，把字节还原
183
    static void invSubBytes(uint8_t state[4][4])
184
    {
185
        using namespace tables;
186
        for (int i = 0; i < 4; ++i)
187
            for (int j = 0; j < 4; ++j)
188
                state[i][j] = INV_SBOX[state[i][j]]; // 查逆 S 盒
189
    }
190

191
    // ShiftRows：行移位
192
    // 第 0 行不动，第 1 行左移 1，第 2 行左移 2，第 3 行左移 3
193
    // 作用：让不同列之间的字节互相混合，增强扩散
194
    static void shiftRows(uint8_t state[4][4])
195
    {
196
        // 第 1 行左移 1 字节
197
        // [a b c d] → [b c d a]
198
        uint8_t t = state[1][0];
199
        state[1][0] = state[1][1];
200
        state[1][1] = state[1][2];
201
        state[1][2] = state[1][3];
202
        state[1][3] = t;
203

204
        // 第 2 行左移 2 字节
205
        // [a b c d] → [c d a b]
206
        // 等价于交换前两个和后两个
207
        t = state[2][0];
208
        state[2][0] = state[2][2];
209
        state[2][2] = t;
210
        t = state[2][1];
211
        state[2][1] = state[2][3];
212
        state[2][3] = t;
213

214
        // 第 3 行左移 3 字节，等价于右移 1 字节
215
        // [a b c d] → [d a b c]
216
        t = state[3][3];
217
        state[3][3] = state[3][2];
218
        state[3][2] = state[3][1];
219
        state[3][1] = state[3][0];
220
        state[3][0] = t;
221
    }
222

223
    // InvShiftRows：逆行移位
224
    // 解密时用，和 ShiftRows 方向相反
225
    // 第 0 行不动，第 1 行右移 1，第 2 行右移 2，第 3 行右移 3
226
    static void invShiftRows(uint8_t state[4][4])
227
    {
228
        // 第 1 行右移 1 字节
229
        // [a b c d] → [d a b c]
230
        uint8_t t = state[1][3];
231
        state[1][3] = state[1][2];
232
        state[1][2] = state[1][1];
233
        state[1][1] = state[1][0];
234
        state[1][0] = t;
235

236
        // 第 2 行右移 2 字节
237
        // [a b c d] → [c d a b]
238
        // 和加密时的交换一样，因为交换两次就还原了
239
        t = state[2][0];
240
        state[2][0] = state[2][2];
241
        state[2][2] = t;
242
        t = state[2][1];
243
        state[2][1] = state[2][3];
244
        state[2][3] = t;
245

246
        // 第 3 行右移 3 字节，等价于左移 1 字节
247
        // [a b c d] → [b c d a]
248
        t = state[3][0];
249
        state[3][0] = state[3][1];
250
        state[3][1] = state[3][2];
251
        state[3][2] = state[3][3];
252
        state[3][3] = t;
253
    }
254

255
    // MixColumns：列混合
256
    // 对每一列做矩阵乘法，矩阵是固定的：
257
    //   [02 03 01 01]
258
    //   [01 02 03 01]
259
    //   [01 01 02 03]
260
    //   [03 01 01 02]
261
    // 乘法在 GF(2^8) 上进行，mul2 = 乘 2，mul3 = 乘 3
262
    // 作用：让一列内的 4 个字节互相影响，增强扩散
263
    static void mixColumns(uint8_t state[4][4])
264
    {
265
        for (int c = 0; c < 4; ++c) // 遍历每一列
266
        {
267
            // 取出这一列的 4 个字节
268
            uint8_t a0 = state[0][c];
269
            uint8_t a1 = state[1][c];
270
            uint8_t a2 = state[2][c];
271
            uint8_t a3 = state[3][c];
272

273
            // 矩阵乘法的第 0 行：02*a0 + 03*a1 + 01*a2 + 01*a3
274
            // GF(2^8) 里加法就是异或，01*a = a
275
            state[0][c] = mul2(a0) ^ mul3(a1) ^ a2 ^ a3;
276

277
            // 第 1 行：01*a0 + 02*a1 + 03*a2 + 01*a3
278
            state[1][c] = a0 ^ mul2(a1) ^ mul3(a2) ^ a3;
279

280
            // 第 2 行：01*a0 + 01*a1 + 02*a2 + 03*a3
281
            state[2][c] = a0 ^ a1 ^ mul2(a2) ^ mul3(a3);
282

283
            // 第 3 行：03*a0 + 01*a1 + 01*a2 + 02*a3
284
            state[3][c] = mul3(a0) ^ a1 ^ a2 ^ mul2(a3);
285
        }
286
    }
287

288
    // InvMixColumns：逆列混合
289
    // 解密时用，矩阵是加密矩阵的逆：
290
    //   [0E 0B 0D 09]
291
    //   [09 0E 0B 0D]
292
    //   [0D 09 0E 0B]
293
    //   [0B 0D 09 0E]
294
    // 每个系数都要在 GF(2^8) 上乘，所以用通用的 gf_mul
295
    static void invMixColumns(uint8_t state[4][4])
296
    {
297
        for (int c = 0; c < 4; ++c)
298
        {
299
            uint8_t a0 = state[0][c];
300
            uint8_t a1 = state[1][c];
301
            uint8_t a2 = state[2][c];
302
            uint8_t a3 = state[3][c];
303

304
            // 第 0 行：0E*a0 + 0B*a1 + 0D*a2 + 09*a3
305
            state[0][c] = gf_mul(a0, 0x0E) ^ gf_mul(a1, 0x0B) ^ gf_mul(a2, 0x0D) ^ gf_mul(a3, 0x09);
306

307
            // 第 1 行：09*a0 + 0E*a1 + 0B*a2 + 0D*a3
308
            state[1][c] = gf_mul(a0, 0x09) ^ gf_mul(a1, 0x0E) ^ gf_mul(a2, 0x0B) ^ gf_mul(a3, 0x0D);
309

310
            // 第 2 行：0D*a0 + 09*a1 + 0E*a2 + 0B*a3
311
            state[2][c] = gf_mul(a0, 0x0D) ^ gf_mul(a1, 0x09) ^ gf_mul(a2, 0x0E) ^ gf_mul(a3, 0x0B);
312

313
            // 第 3 行：0B*a0 + 0D*a1 + 09*a2 + 0E*a3
314
            state[3][c] = gf_mul(a0, 0x0B) ^ gf_mul(a1, 0x0D) ^ gf_mul(a2, 0x09) ^ gf_mul(a3, 0x0E);
315
        }
316
    }
317

318
    // AddRoundKey：轮密钥加
319
    // 把当前 state 和本轮轮密钥逐字节异或
320
    // 这是唯一用到密钥的步骤，其他三步都是固定的
321
    void addRoundKey(uint8_t state[4][4], int round) const
322
    {
323
        for (int i = 0; i < 4; ++i) // 行
324
        {
325
            for (int j = 0; j < 4; ++j) // 列
326
            {
327
                // roundKeys_ 是按列优先存的：
328
                // roundKeys_[round][4*j + i] 对应 state[i][j]
329
                state[i][j] ^= roundKeys_[round][4 * j + i];
330
            }
331
        }
332
    }
333
};