N1BOOK-第七章 CTF之CRYPTO章-N1AES

Posted on Edited on In , Views: Symbols count in article: 15k Reading time ≈ 14 mins.

 

知识理论没跟上，先记录步骤

  • 考点：AES加解密过程及原理

题目代码如下，提供了AES的加密，其中魔改了mix_columns，尤其是伽罗华域乘法运算的模数，shift_rows。需要我们实现解密

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
#!/usr/bin/env python

def xor(a, b):
    return ''.join(chr(ord(ac) ^ ord(bc)) for ac, bc in zip(a, b))


Sbox = (
    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,
)

InvSbox = (
    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,
)


xtime = lambda a: (((a << 1) ^ 99) & 0xFF) if (a & 0x80) else (a << 1)

Rcon = [0x0,0x1,0x2,0x4,0x8,0x10,0x20,0x40,0x80,0x1b,0x36,0x6c,0xd8,0xab,0x4d,0x9a,0x2f,0x5e,0xbc,0x63,0xc6,0x97,0x35,0x6a,0xd4,0xb3,0x7d,0xfa,0xef,0xc5,0x91,0x39]

def xx(i,j):
    t = i
    res = 0
    while j != 0:
        if j & 1:
            res ^= t
        t = xtime(t)
        j >>= 1
    return res

def text2matrix(text):
    matrix = []
    for i in range(16):
        byte = ord(text[i])
        if i % 4 == 0:
            matrix.append([byte])
        else:
            matrix[i / 4].append(byte)
    return matrix


def matrix2text(matrix):
    text = ''
    for i in range(4):
        for j in range(4):
            text = text + chr(matrix[i][j])
    return text


class N1AES:
    def __init__(self, master_key=None):
        if master_key:
            self.change_key(master_key)

    def change_key(self, master_key):
        self.skey = int(master_key.encode('hex'),16)

        self.round_keys = text2matrix(master_key)

        for i in range(4, 4 * 11):
            self.round_keys.append([])
            if i % 4 == 0:
                byte = self.round_keys[i - 4][0] \
                       ^ Sbox[self.round_keys[i - 1][1]] \
                       ^ Rcon[i / 4]
                self.round_keys[i].append(byte)

                for j in range(1, 4):
                    byte = self.round_keys[i - 4][j] \
                           ^ Sbox[self.round_keys[i - 1][(j + 1) % 4]]
                    self.round_keys[i].append(byte)
            else:
                for j in range(4):
                    byte = self.round_keys[i - 4][j] \
                           ^ self.round_keys[i - 1][j]
                    self.round_keys[i].append(byte)

    def encrypt(self, plaintext):
        self.plain_state = text2matrix(plaintext)
        self.add_round_key(self.plain_state, self.round_keys[:4])
        for i in range(1, 10):
            self.round_encrypt(self.plain_state, self.round_keys[4 * i: 4 * (i + 1)])
        self.sub_bytes(self.plain_state)
        self.shift_rows(self.plain_state)
        self.add_round_key(self.plain_state, self.round_keys[40:])

        return matrix2text(self.plain_state)

    def add_round_key(self, s, k):
        for i in range(4):
            for j in range(4):
                s[i][j] ^= k[i][j]

    def round_encrypt(self, state_matrix, key_matrix):
        self.sub_bytes(state_matrix)
        self.shift_rows(state_matrix)
        self.mix_columns(state_matrix)
        self.add_round_key(state_matrix, key_matrix)

    def sub_bytes(self, s):
        for i in range(4):
            for j in range(4):
                s[i][j] = Sbox[s[i][j]]

    def shift_rows(self, s):
        r = [14, 12, 10, 11, 3, 2, 0, 13, 9, 5, 4, 8, 15, 1, 6, 7]
        t = []
        for i in xrange(4):
            for j in xrange(4):
                t.append(s[i][j])
        for i in xrange(16):
            s[i/4][i%4] = t[r[i]]

    def mix_columns(self, s):
        wt = [3, 10, 8, 6]
        for i in range(4):
            s0 = xx(s[0][i],wt[0]) ^ xx(s[1][i],wt[1]) ^ xx(s[2][i],wt[2]) ^ xx(s[3][i],wt[3])
            s1 = xx(s[0][i],wt[1]) ^ xx(s[1][i],wt[2]) ^ xx(s[2][i],wt[3]) ^ xx(s[3][i],wt[0])
            s2 = xx(s[0][i],wt[2]) ^ xx(s[1][i],wt[3]) ^ xx(s[2][i],wt[0]) ^ xx(s[3][i],wt[1])
            s3 = xx(s[0][i],wt[3]) ^ xx(s[1][i],wt[0]) ^ xx(s[2][i],wt[1]) ^ xx(s[3][i],wt[2])
            s[0][i] = s0
            s[1][i] = s1
            s[2][i] = s2
            s[3][i] = s3

a = N1AES("THEAESPARTN1BOOK")
b = a.encrypt(flag[:16]) +  a.encrypt(flag[16:])
print(b.encode('hex')) # 588aa4c53819273bd2cdd6a20de7453ca21ef63d75077daa42b30e7fad50b39f

AES10轮的加解密流程大致如下，此外

  • 10rounds对应128bits
  • 12rounds对应192bits
  • 14rounds对应256bits

preview

所以解密我们需要逆round_encrypt，sub_bytes，shift_rows和mix_columns，其中前三者比较简单，对着写就好

逆round_encrypt

1
2
3
4
5
6
7
8
9
10
11
def round_encrypt(self, state_matrix, key_matrix):
    self.sub_bytes(state_matrix)
    self.shift_rows(state_matrix)
    self.mix_columns(state_matrix)
    self.add_round_key(state_matrix, key_matrix)

def round_decrypt(self, state_matrix, key_matrix):
    self.add_round_key(state_matrix, key_matrix)
    self.inv_mix_columns(state_matrix)
    self.inv_shift_rows(state_matrix)
    self.inv_sub_bytes(state_matrix)

逆sub_bytes

1
2
3
4
5
6
7
8
9
def sub_bytes(self, s):
    for i in range(4):
        for j in range(4):
            s[i][j] = Sbox[s[i][j]]

def inv_sub_bytes(self, s):
    for i in range(4):
        for j in range(4):
            s[i][j] = InvSbox[s[i][j]]

逆shift_rows

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def shift_rows(self, s):
    r = [14, 12, 10, 11, 3, 2, 0, 13, 9, 5, 4, 8, 15, 1, 6, 7]
    t = []
    for i in range(4):
        for j in range(4):
            t.append(s[i][j])
            for i in range(16):
                s[i/4][i%4] = t[r[i]]

def inv_shift_rows(self, s):
    r = [6, 13, 5, 4, 10, 9, 14, 15, 11, 8, 2, 3, 1, 7, 0, 12]
    t = []
    for i in range(4):
        for j in range(4):
            t.append(s[i][j])
            for i in range(16):
                s[i/4][i%4] = t[r[i]]

逆mix_columns

让我们观察下mix_columns，其是在$GF(2^8)$域上模多项式$x^8 + x^6 + x^5 + x + 1$（把99化成二进制）相乘一个矩阵
$$
\begin{bmatrix} 3 & 6 & 8 & 10 \\ 10 & 3 & 6 & 8 \\ 8 & 10 & 3 & 6 \\ 6 & 8 & 10 & 3 \end{bmatrix}\notag
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
xtime = lambda a: (((a << 1) ^ 99) & 0xFF) if (a & 0x80) else (a << 1)

def xx(i,j):
    t = i
    res = 0
    while j != 0:
        if j & 1:
            res ^= t
        t = xtime(t)
        j >>= 1
    return res

def mix_columns(self, s):
        wt = [3, 10, 8, 6]
        for i in range(4):
            s0 = xx(s[0][i],wt[0]) ^ xx(s[1][i],wt[1]) ^ xx(s[2][i],wt[2]) ^ xx(s[3][i],wt[3])
            s1 = xx(s[0][i],wt[1]) ^ xx(s[1][i],wt[2]) ^ xx(s[2][i],wt[3]) ^ xx(s[3][i],wt[0])
            s2 = xx(s[0][i],wt[2]) ^ xx(s[1][i],wt[3]) ^ xx(s[2][i],wt[0]) ^ xx(s[3][i],wt[1])
            s3 = xx(s[0][i],wt[3]) ^ xx(s[1][i],wt[0]) ^ xx(s[2][i],wt[1]) ^ xx(s[3][i],wt[2])
            s[0][i] = s0
            s[1][i] = s1
            s[2][i] = s2
            s[3][i] = s3

所以逆mix_columns需要求出如下矩阵下的逆，这里直接抄自从0到1书中代码

1
2
3
4
5
6
7
8
9
10
11
12
13
#!/usr/bin/env sage
mix = [3, 6, 8, 10]
k.<a> = GF(2)[]
l.<x> = GF(2^8, modulus = a^8 + a^6 + a^5 + a + 1)
res = []
for i in range(4):
    res2 = []
    t = mix[4-i:] + mix[:4-i]
    for j in range(4):
        res2.append(l.fetch_int(t[j]))
    res.append(res2)
res = Matrix(res)
res.inverse()

image-20220706114015277

得到

1
2
3
4
5
6
7
8
9
10
11
def inv_mix_columns(self, s):
    wt = [0x63, 0xd6, 0xfc, 0xc5]
    for i in range(4):
        s0 = xx(s[0][i],wt[0]) ^ xx(s[1][i],wt[1]) ^ xx(s[2][i],wt[2]) ^ xx(s[3][i],wt[3])
        s1 = xx(s[0][i],wt[1]) ^ xx(s[1][i],wt[2]) ^ xx(s[2][i],wt[3]) ^ xx(s[3][i],wt[0])
        s2 = xx(s[0][i],wt[2]) ^ xx(s[1][i],wt[3]) ^ xx(s[2][i],wt[0]) ^ xx(s[3][i],wt[1])
        s3 = xx(s[0][i],wt[3]) ^ xx(s[1][i],wt[0]) ^ xx(s[2][i],wt[1]) ^ xx(s[3][i],wt[2])
        s[0][i] = s0
        s[1][i] = s1
        s[2][i] = s2
        s[3][i] = s3

最终的exp如下

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
Sbox = (
    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,
)

InvSbox = (
    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,
)


Rcon = [0x0,0x1,0x2,0x4,0x8,0x10,0x20,0x40,0x80,0x1b,0x36,0x6c,0xd8,0xab,0x4d,0x9a,0x2f,0x5e,0xbc,0x63,0xc6,0x97,0x35,0x6a,0xd4,0xb3,0x7d,0xfa,0xef,0xc5,0x91,0x39]
xtime = lambda a: (((a << 1) ^ 99) & 0xFF) if (a & 0x80) else (a << 1)

def xx(i,j):
    t = i
    res = 0
    while j != 0:
        if j & 1:
            res ^= t
        t = xtime(t)
        j >>= 1
    return res

def text2matrix(text):
    matrix = []
    for i in range(16):
        byte = ord(text[i])
        if i % 4 == 0:
            matrix.append([byte])
        else:
            matrix[i //4].append(byte)
    return matrix

def matrix2text(matrix):
    text = ''
    for i in range(4):
        for j in range(4):
            text = text + chr(matrix[i][j])
    return text


class N1AES:
    def __init__(self, master_key=None, fuck=None):
        if master_key:
            self.change_key(master_key)
            self.fuck = fuck

    def change_key(self, master_key):
        self.skey = int(master_key.encode('hex'),16)
        self.round_keys = text2matrix(master_key)

        for i in range(4, 4 * 11):
            self.round_keys.append([])
            if i % 4 == 0:
                byte = self.round_keys[i - 4][0] \
                       ^ Sbox[self.round_keys[i - 1][1]] \
                       ^ Rcon[i //4]
                self.round_keys[i].append(byte)

                for j in range(1, 4):
                    byte = self.round_keys[i - 4][j] \
                           ^ Sbox[self.round_keys[i - 1][(j + 1) % 4]]
                    self.round_keys[i].append(byte)
            else:
                for j in range(4):
                    byte = self.round_keys[i - 4][j] \
                           ^ self.round_keys[i - 1][j]
                    self.round_keys[i].append(byte)

    def encrypt(self, plaintext):
        self.plain_state = text2matrix(plaintext)
        self.add_round_key(self.plain_state, self.round_keys[:4])
        for i in range(1, 10):
            self.round_encrypt(self.plain_state, self.round_keys[4 * i: 4 * (i + 1)])
        self.sub_bytes(self.plain_state)
        self.shift_rows(self.plain_state)
        self.add_round_key(self.plain_state, self.round_keys[40:])

        return matrix2text(self.plain_state)

    def decrypt(self, ciphertext):
        self.cipher_state = text2matrix(ciphertext)
        self.add_round_key(self.cipher_state, self.round_keys[40:])
        self.inv_shift_rows(self.cipher_state)
        self.inv_sub_bytes(self.cipher_state)
        for i in range(9, 0, -1):
            self.round_decrypt(self.cipher_state, self.round_keys[4 * i: 4 * (i + 1)])
        self.add_round_key(self.cipher_state, self.round_keys[:4])

        return matrix2text(self.cipher_state)

    def add_round_key(self, s, k):
        for i in range(4):
            for j in range(4):
                s[i][j] ^= k[i][j]

    def round_encrypt(self, state_matrix, key_matrix):
        self.sub_bytes(state_matrix)
        self.shift_rows(state_matrix)
        self.mix_columns(state_matrix)
        self.add_round_key(state_matrix, key_matrix)

    def round_decrypt(self, state_matrix, key_matrix):
        self.add_round_key(state_matrix, key_matrix)
        self.inv_mix_columns(state_matrix)
        self.inv_shift_rows(state_matrix)
        self.inv_sub_bytes(state_matrix)

    def sub_bytes(self, s):
        for i in range(4):
            for j in range(4):
                s[i][j] = Sbox[s[i][j]]

    def inv_sub_bytes(self, s):
        for i in range(4):
            for j in range(4):
                s[i][j] = InvSbox[s[i][j]]

    def shift_rows(self, s):
        r = [14, 12, 10, 11, 3, 2, 0, 13, 9, 5, 4, 8, 15, 1, 6, 7]
        t = []
        for i in range(4):
            for j in range(4):
                t.append(s[i][j])
        for i in range(16):
            s[i/4][i%4] = t[r[i]]

    def inv_shift_rows(self, s):
        r = [6, 13, 5, 4, 10, 9, 14, 15, 11, 8, 2, 3, 1, 7, 0, 12]
        t = []
        for i in range(4):
            for j in range(4):
                t.append(s[i][j])
        for i in range(16):
            s[i/4][i%4] = t[r[i]]

    def mix_columns(self, s):
        wt = [3, 10, 8, 6]
        for i in range(4):
            s0 = xx(s[0][i],wt[0]) ^ xx(s[1][i],wt[1]) ^ xx(s[2][i],wt[2]) ^ xx(s[3][i],wt[3])
            s1 = xx(s[0][i],wt[1]) ^ xx(s[1][i],wt[2]) ^ xx(s[2][i],wt[3]) ^ xx(s[3][i],wt[0])
            s2 = xx(s[0][i],wt[2]) ^ xx(s[1][i],wt[3]) ^ xx(s[2][i],wt[0]) ^ xx(s[3][i],wt[1])
            s3 = xx(s[0][i],wt[3]) ^ xx(s[1][i],wt[0]) ^ xx(s[2][i],wt[1]) ^ xx(s[3][i],wt[2])
            s[0][i] = s0
            s[1][i] = s1
            s[2][i] = s2
            s[3][i] = s3

    def inv_mix_columns(self, s):
        wt = self.fuck
        for i in range(4):
            s0 = xx(s[0][i],wt[0]) ^ xx(s[1][i],wt[1]) ^ xx(s[2][i],wt[2]) ^ xx(s[3][i],wt[3])
            s1 = xx(s[0][i],wt[1]) ^ xx(s[1][i],wt[2]) ^ xx(s[2][i],wt[3]) ^ xx(s[3][i],wt[0])
            s2 = xx(s[0][i],wt[2]) ^ xx(s[1][i],wt[3]) ^ xx(s[2][i],wt[0]) ^ xx(s[3][i],wt[1])
            s3 = xx(s[0][i],wt[3]) ^ xx(s[1][i],wt[0]) ^ xx(s[2][i],wt[1]) ^ xx(s[3][i],wt[2])
            s[0][i] = s0
            s[1][i] = s1
            s[2][i] = s2
            s[3][i] = s3



a = N1AES("THEAESPARTN1BOOK", [0x63,0xd6,0xfc,0xc5])
c = '588aa4c53819273bd2cdd6a20de7453ca21ef63d75077daa42b30e7fad50b39f'.decode('hex')

print(a.decrypt(c[:16]) + a.decrypt(c[16:]))
# n1book{~w0w~_Y0u_1e4rN3d_AES!~~}

Appendix

补充在$GF(2^8)$上多项式的模乘和求逆

多项式模乘

在$GF(2^8)$上，指数大于等于8，就要用$x^8=x^4+x^3+x+1$代掉（传统AES），并相同指数的系数异或

参考AES求mix column

image-20220727094515301

多项式求逆

参考求逆元

Bezout恒等式

在求整数逆元的时候，例子如下

image-20220727101721037

在求多项式逆元的时候，例子如下

image-20220727101756105