AES(ADVANCED ENCRYPTION STANDARD)是一种对称加解密算法。
以下内容字长均为4字节。
下图给出了AES加解密的流程,从图中可以看出:1)解密算法的每一步分别对应加密算法的逆操作,2)加解密所有操作的顺序正好是相反的。正是由于这几点(再加上加密算法与解密算法每步的操作互逆)保证了算法的正确性。加解密中每轮的密钥分别由种子密钥经过密钥扩展算法得到。算法中16字节的明文、密文和轮子密钥都以一个4x4的矩阵表示。
Bytes
字节的每一位按{ b 7 , b 6 , b 6 , b 2 , b 3 , b 3 , b 2 , b 1 , b 0 } \{b_{7},\ \ b_{6},\ \ b_{6},\ \ b_{2},\ \ b_{3},\ \ b_{3},\ \ b_{2},\ \ b_{1},\ \ b_{0}\} { b 7 , b 6 , b 6 , b 2 , b 3 , b 3 , b 2 , b 1 , b 0 } 表示,
b ( x ) = b 7 x 7 + b 6 x 6 + b 5 x 5 + b 4 x 4 + b 3 x 3 + b 2 x 2 + b 1 x + b 0 = ∑ i = 0 7 b i x i b(x)=b_{7}x^{7}+b_{6}x^{6}+b_{_5}x^{5}+b_{_4}x^{4}+b_{_3}x^{3}+b_{_2}x^{2}+b_{_1}x+b_{_0}=\sum_{i=0}^{7}b_{_i}x^{i}
b ( x ) = b 7 x 7 + b 6 x 6 + b 5 x 5 + b 4 x 4 + b 3 x 3 + b 2 x 2 + b 1 x + b 0 = i = 0 ∑ 7 b i x i
因为二进制只能表示0和1,所以系数为偶数项的消除,奇数项保留为1。
Addition
例:
57 + 83 = d 4 ( x 6 + x 4 + x 2 + x + 1 ) + ( x 7 + x + 1 ) = x 7 + x 6 + x 4 + x 2 57 + 83 = d4\\
(x^{6}+x^{4}+x^{2}+x+1)+(x^{7}+x+1)\,=\,x^{7}+x^{6}+x^{4}+x^{2}
57 + 83 = d 4 ( x 6 + x 4 + x 2 + x + 1 ) + ( x 7 + x + 1 ) = x 7 + x 6 + x 4 + x 2
Multiplication
G F ( 2 8 ) GF(2^8) GF ( 2 8 ) 的乘法,为模为8次的不可约多项式乘法,在AES中,模为:
m ( x ) = x 8 + x 4 + x 3 + x + 1 = { 01 } { 1 b } \begin{aligned}
m(x)&=x^{8}+x^{4}+x^{3}+x+1\\
&=\{01\}\{1b\}
\end{aligned}
m ( x ) = x 8 + x 4 + x 3 + x + 1 = { 01 } { 1 b }
57 ⋅ 83 = c 1 ( x 6 + x 4 + x 2 + x + 1 ) ( x 7 + x + 1 ) = x 13 + x 11 + x 9 + x 8 + x 6 + x 5 + x 4 + x 3 + 1 ( x 13 + x 11 + x 9 + x 8 + x 6 + x 5 + x 4 + x 3 + 1 ) m o d ( x 8 + x 4 + x 3 + x 1 + 1 ) = x 7 + x 6 + 1 57 \cdot 83 = c1\\
(x^{6}+x^{4}+x^{2}+x+1)(x^{7}+x+1)=x^{13}+x^{11}+x^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x^{3}+1\\
(x^{13}+x^{11}+x^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x^{3}+1)\bmod(x^{8}+x^{4}+x^{3}+x^{1}+1) = x^{7}+x^{6}+1
57 ⋅ 83 = c 1 ( x 6 + x 4 + x 2 + x + 1 ) ( x 7 + x + 1 ) = x 13 + x 11 + x 9 + x 8 + x 6 + x 5 + x 4 + x 3 + 1 ( x 13 + x 11 + x 9 + x 8 + x 6 + x 5 + x 4 + x 3 + 1 ) mod ( x 8 + x 4 + x 3 + x 1 + 1 ) = x 7 + x 6 + 1
Multiplication by x
计算x ⋅ b ( x ) x\cdot b(x) x ⋅ b ( x ) 时可以转成x倍数进行计算:最高位不为1时,左移;为1时,左移然后异或0x1B(为G F ( 2 8 ) GF(2^8) GF ( 2 8 ) 的模值)。使用函数
xtime
表示这一过程:
x ⋅ b ( x ) = x t i m e { b ( x ) } = 2 ⋅ b ( x ) = { a 6 a 5 a 4 a 3 a 2 a 1 a 0 0 , a 7 = 0 a 6 a 5 a 4 a 3 a 2 a 1 a 0 0 ⊕ 1 b , a 7 ≠ 0 \begin{aligned}
x \cdot b(x)&=xtime\{b(x)\}\\
&=2\cdot b(x)\\
&=
\begin{cases}
a_6a_5a_4a_3a_2a_1a_00\ ,\ a_7 = 0\\
a_6a_5a_4a_3a_2a_1a_00\ \oplus\ 1b ,\ a_7 \ne 0
\end{cases}
\end{aligned}
x ⋅ b ( x ) = x t im e { b ( x )} = 2 ⋅ b ( x ) = { a 6 a 5 a 4 a 3 a 2 a 1 a 0 0 , a 7 = 0 a 6 a 5 a 4 a 3 a 2 a 1 a 0 0 ⊕ 1 b , a 7 = 0
例:
∵ { 57 } ⋅ { 01 } = { 57 } { 57 } ⋅ { 02 } = x t i m e { 57 } = { a e } { 57 } ⋅ { 04 } = x t i m e { a e } = { 47 } { 57 } ⋅ { 08 } = x t i m e { 47 } = { 8 e } { 57 } ⋅ { 10 } = x t i m e { 8 e } = { 07 } { 57 } ⋅ { 20 } = x t i m e { 07 } = { 0 e } { 57 } ⋅ { 40 } = x t i m e { 0 e } = { 1 c } { 57 } ⋅ { 80 } = x t i m e { 1 c } = { 38 } ∴ 57 ⋅ 83 = 57 ⊕ a e ⊕ 38 = c 1 \begin{aligned}
\because \{57\}\cdot\{01\}&=\{57\}\\
\{57\}\cdot\{02\}&=xtime\{57\}=\{ae\}\\
\{57\}\cdot\{04\}&=xtime\{ae\}=\{47\}\\
\{57\}\cdot\{08\}&=xtime\{47\}=\{8e\}\\
\{57\}\cdot\{10\}&=xtime\{8e\}=\{07\}\\
\{57\}\cdot\{20\}&=xtime\{07\}=\{0e\}\\
\{57\}\cdot\{40\}&=xtime\{0e\}=\{1c\}\\
\{57\}\cdot\{80\}&=xtime\{1c\}=\{38\}\\
\therefore
57 \cdot 83 &= 57 \oplus ae\oplus 38\\
&=c1
\end{aligned}
∵ { 57 } ⋅ { 01 } { 57 } ⋅ { 02 } { 57 } ⋅ { 04 } { 57 } ⋅ { 08 } { 57 } ⋅ { 10 } { 57 } ⋅ { 20 } { 57 } ⋅ { 40 } { 57 } ⋅ { 80 } ∴ 57 ⋅ 83 = { 57 } = x t im e { 57 } = { a e } = x t im e { a e } = { 47 } = x t im e { 47 } = { 8 e } = x t im e { 8 e } = { 07 } = x t im e { 07 } = { 0 e } = x t im e { 0 e } = { 1 c } = x t im e { 1 c } = { 38 } = 57 ⊕ a e ⊕ 38 = c 1
Cipher
N b N_b N b : Number of columns(32-bit words).
N k N_k N k : Number of 32-bit words comprising the Cipher Key.
N r N_r N r : Number of rounds.
AES加密算法涉及4种操作:字节替代(SubBytes
)、行移位(ShiftRows
)、列混淆(MixColumns
)和轮密钥加(AddRoundKey
)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w[0, Nb-1]) for round = 1 step 1 to Nr–1 SubBytes(state) ShiftRows(state) MixColumns(state) AddRoundKey(state, w[round*Nb, (round+1)*Nb-1]) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) out = state end
SubBytes
S-Box:
x\y
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
0
63
7C
77
7B
F2
6B
6F
C5
30
01
67
2B
FE
D7
AB
76
1
CA
82
C9
7D
FA
59
47
F0
AD
D4
A2
AF
9C
A4
72
C0
2
B7
FD
93
26
36
3F
F7
CC
34
A5
E5
F1
71
D8
31
15
3
04
C7
23
C3
18
96
05
9A
07
12
80
E2
EB
27
B2
75
4
09
83
2C
1A
1B
6E
5A
A0
52
3B
D6
B3
29
E3
2F
84
5
53
D1
00
ED
20
FC
B1
5B
6A
CB
BE
39
4A
4C
58
CF
6
D0
EF
AA
FB
43
4D
33
85
45
F9
02
7F
50
3C
9F
A8
7
51
A3
40
8F
92
9D
38
F5
BC
B6
DA
21
10
FF
F3
D2
8
CD
0C
13
EC
5F
97
44
17
C4
A7
7E
3D
64
5D
19
73
9
60
81
4F
DC
22
2A
90
88
46
EE
B8
14
DE
5E
0B
DB
A
E0
32
3A
0A
49
06
24
5C
C2
D3
AC
62
91
95
E4
79
B
E7
C8
37
6D
8D
D5
4E
A9
6C
56
F4
EA
65
7A
AE
08
C
BA
78
25
2E
1C
A6
B4
C6
E8
DD
74
1F
4B
BD
8B
8A
D
70
3E
B5
66
48
03
F6
0E
61
35
57
B9
86
C1
1D
9E
E
E1
F8
98
11
69
D9
8E
94
9B
1E
87
E9
CE
55
28
DF
F
8C
A1
89
0D
BF
E6
42
68
41
99
2D
0F
B0
54
BB
16
ShiftRows
第一行保持不变,第二行循环左移8比特,第三行循环左移16比特,第四行循环左移24比特
S ′ [ i ] [ j ] = S [ i ] [ ( j + i ) m o d N b ] , i ∈ [ 0 , 3 ] , j ∈ [ 0 , N b ) S'[i][j] = S[i][(j+i)\mod N_b], i\in[0,3],j\in[0,N_b)
S ′ [ i ] [ j ] = S [ i ] [( j + i ) mod N b ] , i ∈ [ 0 , 3 ] , j ∈ [ 0 , N b )
MixColumns
这一步的字节乘法是是基于有限域G F ( 2 8 ) GF(2^8) GF ( 2 8 ) 的多项式乘法的,它的不可约的多项式是:x 8 + x 4 + x 3 + x + 1 x^8 + x^4 + x^3 + x + 1 x 8 + x 4 + x 3 + x + 1 。
2 ⋅ ( a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0 ) = { a 6 a 5 a 4 a 3 a 2 a 1 a 0 0 , a 7 = 0 a 6 a 5 a 4 a 3 a 2 a 1 a 0 0 ⊕ 0001101 1 b , a 7 ≠ 0 2\cdot(a_7a_6a_5a_4a_3a_2a_1a_0) =
\begin{cases}
a_6a_5a_4a_3a_2a_1a_00\ ,\ a_7 = 0\\
a_6a_5a_4a_3a_2a_1a_00\ \oplus\ 00011011_b ,\ a_7 \ne 0
\end{cases}
2 ⋅ ( a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0 ) = { a 6 a 5 a 4 a 3 a 2 a 1 a 0 0 , a 7 = 0 a 6 a 5 a 4 a 3 a 2 a 1 a 0 0 ⊕ 0001101 1 b , a 7 = 0
3 ⋅ ( a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0 ) = ( 1 0 b ⊕ 0 1 b ) ⋅ ( a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0 ) = ( 1 0 b ⋅ a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0 ) ⊕ ( a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0 ) \begin{aligned}
3\cdot(a_7a_6a_5a_4a_3a_2a_1a_0)
&= (10_b\oplus01_b)\cdot(a_7a_6a_5a_4a_3a_2a_1a_0)\\
&= (10_b \cdot a_7a_6a_5a_4a_3a_2a_1a_0) \oplus(a_7a_6a_5a_4a_3a_2a_1a_0)
\end{aligned}
3 ⋅ ( a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0 ) = ( 1 0 b ⊕ 0 1 b ) ⋅ ( a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0 ) = ( 1 0 b ⋅ a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0 ) ⊕ ( a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0 )
列混淆:逐列对数据进行在G F ( 2 8 ) GF(2^8) GF ( 2 8 ) 域上的乘和加,此操作主要提供扩散元素。
[ S o , c ′ S 1 , c ′ S 2 , c ′ S 3 , c ′ ] = [ 02 03 01 01 01 02 03 01 01 01 02 03 03 01 01 02 ] [ S 0 , c S 1 , c S 2 , c S 3 , c ] , 0 ≤ c < N b \begin{bmatrix}
S'_{o,c}\\
S'_{1,c}\\
S'_{2,c}\\
S'_{3,c}\\
\end{bmatrix}
=
\begin{bmatrix}
02 & 03 & 01 & 01\\
01 & 02 & 03 & 01\\
01 & 01 & 02 & 03\\
03 & 01 & 01 & 02\\
\end{bmatrix}
\begin{bmatrix}
S_{0,c}\\
S_{1,c}\\
S_{2,c}\\
S_{3,c}\\
\end{bmatrix}
,0\le c\lt N_b
S o , c ′ S 1 , c ′ S 2 , c ′ S 3 , c ′ = 02 01 01 03 03 02 01 01 01 03 02 01 01 01 03 02 S 0 , c S 1 , c S 2 , c S 3 , c , 0 ≤ c < N b
S 0 , c ′ = ( { 02 } ⋅ S 0 , c ) ⊕ ( { 03 } ⋅ S 1 , c ) ⊕ S 2 , c ⊕ S 3 , c S 1 , c ′ = S 0 , c ⊕ ( { 02 } ⋅ S 1 , c ) ⊕ ( { 03 } ⋅ s 2 , c ) ⊕ S 3 , c S 2 , c ′ = S 0 , c ⊕ S 1 , c ⊕ ( { 02 } ⋅ S 2 , c ) ⊕ ( { 03 } ⋅ S 3 , c ) S 3 , c ′ = ( { 03 } ⋅ S 0 , c ) ⊕ S 1 , c ⊕ S 2 , c ⊕ ( { 02 } ⋅ S 3 , c ) \begin{aligned}
S_{0,c}^{\prime}&=(\{02\}\cdot\;S_{0,c})\oplus(\{03\}\cdot\;S_{1,c})\oplus\;S_{2,c}\oplus\;S_{3,c}\\
S_{1,c}^{\prime}&=S_{0,c}\oplus(\{02\}\cdot\;S_{1,c})\oplus(\{03\}\cdot\;s_{2,c})\oplus\;S_{3,c}\\
S_{2,c}^{\prime}&=S_{0,c}\oplus\;S_{1,c}\oplus\;(\{02\}\cdot\;S_{2,c})\oplus\;(\{03\}\cdot\;S_{3,c})\\
S_{3,c}^{\prime}&=(\{03\}\cdot\;S_{0,c})\oplus\;S_{1,c}\oplus\;S_{2,c}\oplus\;(\{02\}\cdot\;S_{3,c})
\end{aligned}
S 0 , c ′ S 1 , c ′ S 2 , c ′ S 3 , c ′ = ({ 02 } ⋅ S 0 , c ) ⊕ ({ 03 } ⋅ S 1 , c ) ⊕ S 2 , c ⊕ S 3 , c = S 0 , c ⊕ ({ 02 } ⋅ S 1 , c ) ⊕ ({ 03 } ⋅ s 2 , c ) ⊕ S 3 , c = S 0 , c ⊕ S 1 , c ⊕ ({ 02 } ⋅ S 2 , c ) ⊕ ({ 03 } ⋅ S 3 , c ) = ({ 03 } ⋅ S 0 , c ) ⊕ S 1 , c ⊕ S 2 , c ⊕ ({ 02 } ⋅ S 3 , c )
AddRoundKey
先计算轮密钥,然后将上一步的结果与轮密钥异或。
AES KEY Expansion
轮密钥为4字长的线性数组,表示为:w [ i ] , 0 ≤ i < N b × ( N r + 1 ) w[i],\ 0\le i\lt N_b\times(N_r+1) w [ i ] , 0 ≤ i < N b × ( N r + 1 ) 。
RotWord
: RotWord是一种对一个字进行循环左移的操作,即将最左边的字节移到最右边,其他字节依次向左移动一位。
R o t W o r d ( W o r d [ a 0 , a 1 , a 2 , a 3 ] ) = W o r d ′ [ a 1 , a 2 , a 3 , a 0 ] RotWord(Word[a_{0},a_{1},a_{2},a_{3}]) = Word'[a_{1},a_{2},a_{3},a_{0}]
R o t W or d ( W or d [ a 0 , a 1 , a 2 , a 3 ]) = W or d ′ [ a 1 , a 2 , a 3 , a 0 ]
R c o n [ i / N k ] = [ x i − 1 , { 00 } , { 00 } , { 00 } ] , i = N k , 2 N k , . . . N r N k , x = { 02 } i n G F ( 2 8 ) . Rcon[i/N_{k}]=[x^{i-1},\{00\},\{00\},\{00\}],\ i=N_k,2N_k,...N_rN_k,\ x=\{02\}\ in\ GF(2^8).
R co n [ i / N k ] = [ x i − 1 , { 00 } , { 00 } , { 00 }] , i = N k , 2 N k , ... N r N k , x = { 02 } in GF ( 2 8 ) .
其中x i − 1 x^{i-1} x i − 1 表示为:x x x 在G F ( 2 8 ) GF(2^8) GF ( 2 8 ) 域的幂。
R c o n [ j ] = [ R C j , 0x00, 0x00, 0x00 ] AES128: R C j = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36} AES192: R C j = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80} AES256: R C j = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40} \begin{aligned}
Rcon[j]&=[RC_j,\text{ 0x00, 0x00, 0x00}]\\
\text{AES128: }RC_j &= \text{\{0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36\}}\\
\text{AES192: }RC_j &= \text{\{0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80\}}\\
\text{AES256: }RC_j &= \text{\{0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40\}}
\end{aligned}
R co n [ j ] AES128: R C j AES192: R C j AES256: R C j = [ R C j , 0x00, 0x00, 0x00 ] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36} = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80} = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40}
RoundKey
将种子密钥按序排列,其中k 0 , k 1 , . . . , k 15 k_{0},k_{1},...,k_{15} k 0 , k 1 , ... , k 15 依次表示种子密钥的一个字节;
w [ i ] = { [ k 4 i , k 4 i + 1 , k 4 i + 2 , k 4 i + 3 ] , 0 ≤ i < 4 w [ i − 4 ] ⊕ g ( w [ i − 1 ] ) , i m o d 4 = 0 , i < N b × ( N r + 1 ) w [ i − 4 ] ⊕ w [ i − 1 ] , i < N b × ( N r + 1 ) w[i]=
\begin{cases}
[k_{4i},\ k_{4i+1},\ k_{4i+2},\ k_{4i+3}],\ 0\le i\lt 4\\
w[i-4]\oplus g(w[i-1]),\ i\mod 4 = 0,\ i\lt N_b\times(N_r+1)\\
w[i-4]\oplus w[i-1],\ i\lt N_b\times(N_r+1)
\end{cases}
w [ i ] = ⎩ ⎨ ⎧ [ k 4 i , k 4 i + 1 , k 4 i + 2 , k 4 i + 3 ] , 0 ≤ i < 4 w [ i − 4 ] ⊕ g ( w [ i − 1 ]) , i mod 4 = 0 , i < N b × ( N r + 1 ) w [ i − 4 ] ⊕ w [ i − 1 ] , i < N b × ( N r + 1 )
函数g g g 的流程说明:
将w循环左移8比特:RotWord
。
分别对每个字节做S盒置换:SubWord
。
与32比特的常量Rcon
进行异或。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)], Nk) begin word temp i = 0 while (i < Nk) w[i] = word(key[4*i], key[4*i+1], key[4*i+2], key[4*i+3]) i = i+1 end while i = Nk while (i < Nb * (Nr+1)) temp = w[i-1] if (i mod Nk = 0) temp = SubWord(RotWord(temp)) xor Rcon[i/Nk] else if (Nk > 6 and i mod Nk = 4) temp = SubWord(temp) end if w[i] = w[i-Nk] xor temp i = i + 1 end while end
Inverse Cipher
解密为加密的逆过程,流程相似。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 InvCipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w[Nr*Nb, (Nr+1)*Nb-1]) for round = Nr-1 step -1 downto 1 InvShiftRows(state) InvSubBytes(state) AddRoundKey(state, w[round*Nb, (round+1)*Nb-1]) InvMixColumns(state) end for InvShiftRows(state) InvSubBytes(state) AddRoundKey(state, w[0, Nb-1]) out = state end
InvShiftRows
第一行保持不变,第二行循环右移8比特,第三行循环右移16比特,第四行循环右移24比特
S ′ [ i ] [ j ] = S [ i ] [ ( j − i + N b ) m o d N b ] , i ∈ [ 0 , 3 ] , j ∈ [ 0 , N b ) S'[i][j] = S[i][(j-i+N_b)\mod N_b], i\in[0,3],j\in[0,N_b)
S ′ [ i ] [ j ] = S [ i ] [( j − i + N b ) mod N b ] , i ∈ [ 0 , 3 ] , j ∈ [ 0 , N b )
InvSubBytes
Inverse S-Box:
x\y
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
0
52
09
6A
D5
30
36
A5
38
BF
40
A3
9E
81
F3
D7
FB
1
7C
E3
39
82
9B
2F
FF
87
34
8E
43
44
C4
DE
E9
CB
2
54
7B
94
32
A6
C2
23
3D
EE
4C
95
0B
42
FA
C3
4E
3
08
2E
A1
66
28
D9
24
B2
76
5B
A2
49
6D
8B
D1
25
4
72
F8
F6
64
86
68
98
16
D4
A4
5C
CC
5D
65
B6
92
5
6C
70
48
50
FD
ED
B9
DA
5E
15
46
57
A7
8D
9D
84
6
90
D8
AB
00
8C
BC
D3
0A
F7
E4
58
05
B8
B3
45
06
7
D0
2C
1E
8F
CA
3F
0F
02
C1
AF
BD
03
01
13
8A
6B
8
3A
91
11
41
4F
67
DC
EA
97
F2
CF
CE
F0
B4
E6
73
9
96
AC
74
22
E7
AD
35
85
E2
F9
37
E8
1C
75
DF
6E
A
47
F1
1A
71
1D
29
C5
89
6F
B7
62
0E
AA
18
BE
1B
B
FC
56
3E
4B
C6
D2
79
20
9A
DB
C0
FE
78
CD
5A
F4
C
1F
DD
A8
33
88
07
C7
31
B1
12
10
59
27
80
EC
5F
D
60
51
7F
A9
19
B5
4A
0D
2D
E5
7A
9F
93
C9
9C
EF
E
A0
E0
3B
4D
AE
2A
F5
B0
C8
EB
BB
3C
83
53
99
61
F
17
2B
04
7E
BA
77
D6
26
E1
69
14
63
55
21
0C
7D
InvMixColumns
[ S 0 , c ′ S 1 , c ′ S 2 , c ′ S 3 , c ′ ] = [ 0 e 0 b 0 d 09 09 0 e 0 b 0 d 0 d 09 0 e 0 b 0 b 0 d 09 0 e ] [ S o , c S 1 , c S 2 , c S 3 , c ] , 0 ≤ c < N b \begin{bmatrix}
S'_{0,c}\\
S'_{1,c}\\
S'_{2,c}\\
S'_{3,c}\\
\end{bmatrix}
=
\begin{bmatrix}
0e & 0b & 0d & 09\\
09 & 0e & 0b & 0d\\
0d & 09 & 0e & 0b\\
0b & 0d & 09 & 0e\\
\end{bmatrix}
\begin{bmatrix}
S_{o,c}\\
S_{1,c}\\
S_{2,c}\\
S_{3,c}\\
\end{bmatrix}
,0\le c\lt N_b
S 0 , c ′ S 1 , c ′ S 2 , c ′ S 3 , c ′ = 0 e 09 0 d 0 b 0 b 0 e 09 0 d 0 d 0 b 0 e 09 09 0 d 0 b 0 e S o , c S 1 , c S 2 , c S 3 , c , 0 ≤ c < N b
S 0 , c ′ = ( { 0 e } ⋅ S 0 , c ) ⊕ ( { 0 b } ⋅ S 1 , c ) ⊕ ( { 0 d } ⋅ S 2 , c ) ⊕ ( { 09 } ⋅ S 3 , c ) S 1 , c ′ = ( { 09 } ⋅ S 0 , c ) ⊕ ( { 0 e } ⋅ S 1 , c ) ⊕ ( { 0 b } ⋅ S 2 , c ) ⊕ ( { 0 d } ⋅ S 3 , c ) S 2 , c ′ = ( { 0 d } ⋅ S 0 , c ) ⊕ ( { 09 } ⋅ S 1 , c ) ⊕ ( { 0 e } ⋅ S 2 , c ) ⊕ ( { 0 b } ⋅ S 3 , c ) S 3 , c ′ = ( { 0 b } ⋅ S 0 , c ) ⊕ ( { 0 d } ⋅ S 1 , c ) ⊕ ( { 09 } ⋅ S 2 , c ) ⊕ ( { 0 e } ⋅ S 3 , c ) \begin{aligned}
S_{0,c}^{\prime}&=(\{0e\}\cdot\;S_{0,c})\oplus(\{0b\}\cdot\;S_{1,c})\oplus(\{0d\}\cdot\;S_{2,c})\oplus\;(\{09\}\cdot\;S_{3,c})\\
S_{1,c}^{\prime}&=(\{09\}\cdot\;S_{0,c})\oplus(\{0e\}\cdot\;S_{1,c})\oplus(\{0b\}\cdot\;S_{2,c})\oplus\;(\{0d\}\cdot\;S_{3,c})\\
S_{2,c}^{\prime}&=(\{0d\}\cdot\;S_{0,c})\oplus(\{09\}\cdot\;S_{1,c})\oplus(\{0e\}\cdot\;S_{2,c})\oplus\;(\{0b\}\cdot\;S_{3,c})\\
S_{3,c}^{\prime}&=(\{0b\}\cdot\;S_{0,c})\oplus(\{0d\}\cdot\;S_{1,c})\oplus(\{09\}\cdot\;S_{2,c})\oplus\;(\{0e\}\cdot\;S_{3,c})
\end{aligned}
S 0 , c ′ S 1 , c ′ S 2 , c ′ S 3 , c ′ = ({ 0 e } ⋅ S 0 , c ) ⊕ ({ 0 b } ⋅ S 1 , c ) ⊕ ({ 0 d } ⋅ S 2 , c ) ⊕ ({ 09 } ⋅ S 3 , c ) = ({ 09 } ⋅ S 0 , c ) ⊕ ({ 0 e } ⋅ S 1 , c ) ⊕ ({ 0 b } ⋅ S 2 , c ) ⊕ ({ 0 d } ⋅ S 3 , c ) = ({ 0 d } ⋅ S 0 , c ) ⊕ ({ 09 } ⋅ S 1 , c ) ⊕ ({ 0 e } ⋅ S 2 , c ) ⊕ ({ 0 b } ⋅ S 3 , c ) = ({ 0 b } ⋅ S 0 , c ) ⊕ ({ 0 d } ⋅ S 1 , c ) ⊕ ({ 09 } ⋅ S 2 , c ) ⊕ ({ 0 e } ⋅ S 3 , c )
Inverse AddRoundKey
和上文步骤AddRoundKey 一致。
Modes
Electronic Codebook Book(ECB)
Cipher Block Chaining (CBC)
Cipher FeedBack (CFB)
Output FeedBack (OFB)
Counter (CTR)
Example
以下为AES-ECB-128加密例子:
Plain text: 32 43 f6 a8 88 5a 30 8d 31 31 98 a2 e0 37 07 34
Cipher key: 2b 7e 15 16 28 ae d2 a6 ab f7 15 88 09 cf 4f 3c
Cipher text: 39 25 84 1d 02 dc 09 fb dc 11 85 97 19 6a 0b 32
Openssl
1 echo 3243f6a8885a308d313198a2e0370734 | xxd -r -ps | openssl aes-128-ecb -e -K 2b7e151628aed2a6abf7158809cf4f3c -nopad | xxd
FirstRound
First AddRoundKey:
[ 32 88 31 e 0 43 5 a 31 37 f 6 30 98 07 a 8 8 d a 2 34 ] ⊕ [ 2 b 28 a b 09 7 e a e f 7 c f 15 d 2 15 4 f 16 a 6 88 3 c ] = [ 19 a 0 9 a e 9 3 d f 4 c 6 f 8 e 3 e 2 8 d 48 b e 2 b 2 a 08 ] \begin{bmatrix}
32 & 88 & 31 & e0 \\
43 & 5a & 31 & 37 \\
f6 & 30 & 98 & 07 \\
a8 & 8d & a2 & 34 \\
\end{bmatrix}
\oplus
\begin{bmatrix}
2b & 28 & ab & 09 \\
7e & ae & f7 & cf \\
15 & d2 & 15 & 4f \\
16 & a6 & 88 & 3c \\
\end{bmatrix}
=
\begin{bmatrix}
19 & a0 & 9a & e9 \\
3d & f4 & c6 & f8 \\
e3 & e2 & 8d & 48 \\
be & 2b & 2a & 08 \\
\end{bmatrix}
32 43 f 6 a 8 88 5 a 30 8 d 31 31 98 a 2 e 0 37 07 34 ⊕ 2 b 7 e 15 16 28 a e d 2 a 6 ab f 7 15 88 09 c f 4 f 3 c = 19 3 d e 3 b e a 0 f 4 e 2 2 b 9 a c 6 8 d 2 a e 9 f 8 48 08
SecoundRound
SubBytes:
[ s b o x ( 1 , 9 ) s b o x ( a , 0 ) s b o x ( 9 , a ) s b o x ( e , 9 ) s b o x ( 3 , d ) s b o x ( f , 4 ) s b o x ( c , 6 ) s b o x ( f , 8 ) s b o x ( e , 3 ) s b o x ( e , 2 ) s b o x ( 8 , d ) s b o x ( 4 , 8 ) s b o x ( b , e ) s b o x ( 2 , b ) s b o x ( 2 , a ) s b o x ( 0 , 8 ) ] = [ d 4 e 0 b 8 1 e 27 b f b 4 41 11 98 5 d 52 a e f 1 e 5 30 ] \begin{bmatrix}
sbox(1,9) & sbox(a,0) & sbox(9,a) & sbox(e,9) \\
sbox(3,d) & sbox(f,4) & sbox(c,6) & sbox(f,8) \\
sbox(e,3) & sbox(e,2) & sbox(8,d) & sbox(4,8) \\
sbox(b,e) & sbox(2,b) & sbox(2,a) & sbox(0,8) \\
\end{bmatrix}
=
\begin{bmatrix}
d4 & e0 & b8 & 1e \\
27 & bf & b4 & 41 \\
11 & 98 & 5d & 52 \\
ae & f1 & e5 & 30 \\
\end{bmatrix}
s b o x ( 1 , 9 ) s b o x ( 3 , d ) s b o x ( e , 3 ) s b o x ( b , e ) s b o x ( a , 0 ) s b o x ( f , 4 ) s b o x ( e , 2 ) s b o x ( 2 , b ) s b o x ( 9 , a ) s b o x ( c , 6 ) s b o x ( 8 , d ) s b o x ( 2 , a ) s b o x ( e , 9 ) s b o x ( f , 8 ) s b o x ( 4 , 8 ) s b o x ( 0 , 8 ) = d 4 27 11 a e e 0 b f 98 f 1 b 8 b 4 5 d e 5 1 e 41 52 30
ShiftRows:
[ d 4 e 0 b 8 1 e 27 b f b 4 41 11 98 5 d 52 a e f 1 e 5 30 ] = > [ d 4 e 0 b 8 1 e b f b 4 41 27 5 d 52 11 98 30 a e f 1 e 5 ] \begin{bmatrix}
d4 & e0 & b8 & 1e \\
27 & bf & b4 & 41 \\
11 & 98 & 5d & 52 \\
ae & f1 & e5 & 30 \\
\end{bmatrix}
=>
\begin{bmatrix}
d4 & e0 & b8 & 1e \\
bf & b4 & 41 & 27 \\
5d & 52 & 11 & 98 \\
30 & ae & f1 & e5 \\
\end{bmatrix}
d 4 27 11 a e e 0 b f 98 f 1 b 8 b 4 5 d e 5 1 e 41 52 30 => d 4 b f 5 d 30 e 0 b 4 52 a e b 8 41 11 f 1 1 e 27 98 e 5
MixColumns:
[ 02 03 01 01 01 02 03 01 01 01 02 03 03 01 01 02 ] [ d 4 e 0 b 8 1 e b f b 4 41 27 5 d 52 11 98 30 a e f 1 e 5 ] = [ ( 02 ⋅ d 4 ) ⊕ ( 03 ⋅ b f ) ⊕ 5 d ⊕ 30 ⋯ ⋯ ⋯ ⋮ ⋮ ⋱ ⋮ ⋯ ⋯ ⋯ ( 03 ⋅ 1 e ) ⊕ 27 ⊕ 98 ⊕ ( 02 ⋅ e 5 ) ] = [ 04 e 0 48 28 66 c b f 8 06 81 19 d 3 26 e 5 9 a 7 a 4 c ] \begin{aligned}
\begin{bmatrix}
02 & 03 & 01 & 01\\
01 & 02 & 03 & 01\\
01 & 01 & 02 & 03\\
03 & 01 & 01 & 02\\
\end{bmatrix}
\begin{bmatrix}
d4 & e0 & b8 & 1e \\
bf & b4 & 41 & 27 \\
5d & 52 & 11 & 98 \\
30 & ae & f1 & e5 \\
\end{bmatrix}
&=
\begin{bmatrix}
(02 \cdot d4) \oplus (03 \cdot bf) \oplus 5d \oplus 30 & \cdots & \cdots & \cdots \\
\vdots & \vdots &\ddots & \vdots\\
\\
\cdots & \cdots & \cdots & (03 \cdot 1e) \oplus 27 \oplus 98 \oplus (02 \cdot e5)
\end{bmatrix}\\
&=
\begin{bmatrix}
04 & e0 & 48 & 28 \\
66 & cb & f8 & 06 \\
81 & 19 & d3 & 26 \\
e5 & 9a & 7a & 4c \\
\end{bmatrix}
\end{aligned}
02 01 01 03 03 02 01 01 01 03 02 01 01 01 03 02 d 4 b f 5 d 30 e 0 b 4 52 a e b 8 41 11 f 1 1 e 27 98 e 5 = ( 02 ⋅ d 4 ) ⊕ ( 03 ⋅ b f ) ⊕ 5 d ⊕ 30 ⋮ ⋯ ⋯ ⋮ ⋯ ⋯ ⋱ ⋯ ⋯ ⋮ ( 03 ⋅ 1 e ) ⊕ 27 ⊕ 98 ⊕ ( 02 ⋅ e 5 ) = 04 66 81 e 5 e 0 c b 19 9 a 48 f 8 d 3 7 a 28 06 26 4 c
RotWord:
[ 2 b 28 a b 09 7 e a e f 7 c f 15 d 2 15 4 f 16 a 6 88 3 c ] = [ w 0 w 1 w 2 w 3 ] w 0 = 2 b 7 e 1516 w 1 = 28 a e d 2 a 6 w 2 = a b f 71588 w 3 = 09 c f 4 f 3 c \begin{bmatrix}
2b & 28 & ab & 09 \\
7e & ae & f7 & cf \\
15 & d2 & 15 & 4f \\
16 & a6 & 88 & 3c \\
\end{bmatrix}
=
\begin{bmatrix}
w_0 & w_1 & w_2 & w_3 \\
\end{bmatrix}\\
w_0 = 2b7e1516 \\
w_1 = 28aed2a6 \\
w_2 = abf71588 \\
w_3 = 09cf4f3c \\
2 b 7 e 15 16 28 a e d 2 a 6 ab f 7 15 88 09 c f 4 f 3 c = [ w 0 w 1 w 2 w 3 ] w 0 = 2 b 7 e 1516 w 1 = 28 a e d 2 a 6 w 2 = ab f 71588 w 3 = 09 c f 4 f 3 c
KeyExpansion:
RotWord:
R o t W o r d ( w 3 ) = R o t W o r d ( 09 c f 4 f 3 c ) = c f 4 f 3 c 09 \begin{aligned}
RotWord(w_3)&=RotWord(09cf4f3c)\\
&=cf4f3c09
\end{aligned}
R o t W or d ( w 3 ) = R o t W or d ( 09 c f 4 f 3 c ) = c f 4 f 3 c 09
SubWord:
S u b W o r d ( c f 4 f 3 c 09 ) = s b o x ( c , f ) , s b o x ( 4 , f ) , s b o x ( 3 , c ) , s b o x ( 0 , 9 ) = 8 a 84 e b 01 \begin{aligned}
SubWord(cf4f3c09) &= sbox(c,f),sbox(4,f),sbox(3,c),sbox(0,9)\\
&=8a84eb01
\end{aligned}
S u bW or d ( c f 4 f 3 c 09 ) = s b o x ( c , f ) , s b o x ( 4 , f ) , s b o x ( 3 , c ) , s b o x ( 0 , 9 ) = 8 a 84 e b 01
Rcon:
R c o n ( 0 ) = [ 01 , 00 , 00 , 00 ] 8 a 84 e b 01 ⊕ R c o n ( 0 ) = 8 b 84 e b 01 Rcon(0) = [01,00,00,00]
8a84eb01 \oplus Rcon(0) = 8b84eb01
R co n ( 0 ) = [ 01 , 00 , 00 , 00 ] 8 a 84 e b 01 ⊕ R co n ( 0 ) = 8 b 84 e b 01
XOR with w[i-Nk]
w 4 = 8 b 84 e b 01 ⊕ w 0 = a 0 f a f e 17 w 5 = a 0 f a f e 17 ⊕ w 1 = 88542 c b 1 w 6 = 88542 c b 1 ⊕ w 2 = 23 a 33939 w 5 = 23 a 33939 ⊕ w 3 = 2 a 6 c 7605 = > [ a 0 88 23 2 a f a 54 a 3 6 c f e 2 c 39 76 17 b 1 39 05 ] \begin{aligned}
w_4&=8b84eb01 \oplus w_0\\
&=a0fafe17\\
w_5&=a0fafe17 \oplus w_1\\
&=88542cb1\\
w_6&=88542cb1 \oplus w_2\\
&=23a33939\\
w_5&=23a33939 \oplus w_3\\
&=2a6c7605
\end{aligned}
=>
\begin{bmatrix}
a0 & 88 & 23 & 2a \\
fa & 54 & a3 & 6c \\
fe & 2c & 39 & 76 \\
17 & b1 & 39 & 05 \\
\end{bmatrix}\\
w 4 w 5 w 6 w 5 = 8 b 84 e b 01 ⊕ w 0 = a 0 f a f e 17 = a 0 f a f e 17 ⊕ w 1 = 88542 c b 1 = 88542 c b 1 ⊕ w 2 = 23 a 33939 = 23 a 33939 ⊕ w 3 = 2 a 6 c 7605 => a 0 f a f e 17 88 54 2 c b 1 23 a 3 39 39 2 a 6 c 76 05
AddRoundKey:
[ 04 e 0 48 28 66 c b f 8 06 81 19 d 3 26 e 5 9 a 7 a 4 c ] ⊕ [ a 0 88 23 2 a f a 54 a 3 6 c f e 2 c 39 76 17 b 1 39 05 ] = [ a 4 68 6 b 02 9 c 9 f 5 b 6 a 7 f 35 e a 50 f 2 2 b 43 49 ] \begin{bmatrix}
04 & e0 & 48 & 28 \\
66 & cb & f8 & 06 \\
81 & 19 & d3 & 26 \\
e5 & 9a & 7a & 4c \\
\end{bmatrix}
\oplus
\begin{bmatrix}
a0 & 88 & 23 & 2a \\
fa & 54 & a3 & 6c \\
fe & 2c & 39 & 76 \\
17 & b1 & 39 & 05 \\
\end{bmatrix}
=
\begin{bmatrix}
a4 & 68 & 6b & 02 \\
9c & 9f & 5b & 6a \\
7f & 35 & ea & 50 \\
f2 & 2b & 43 & 49 \\
\end{bmatrix}
04 66 81 e 5 e 0 c b 19 9 a 48 f 8 d 3 7 a 28 06 26 4 c ⊕ a 0 f a f e 17 88 54 2 c b 1 23 a 3 39 39 2 a 6 c 76 05 = a 4 9 c 7 f f 2 68 9 f 35 2 b 6 b 5 b e a 43 02 6 a 50 49
2~9 Rounds
…
LastRound
最后一轮不需要MixColumn。
得到最终加密结果:
[ 39 02 d c 19 25 d c 11 6 a 84 09 85 0 b 1 d f b 97 32 ] \begin{bmatrix}
39 & 02 & dc & 19 \\
25 & dc & 11 & 6a \\
84 & 09 & 85 & 0b \\
1d & fb & 97 & 32 \\
\end{bmatrix}
39 25 84 1 d 02 d c 09 f b d c 11 85 97 19 6 a 0 b 32
References
[1] Federal Information. Specification for the ADVANCED ENCRYPTION STANDARD (AES) [S]. 2001.11.26.
[2] ReadingLover. 密码算法详解—AES [OL]. https://www.cnblogs.com/luop/p/4334160.html . 2017.11.19.
[3] Morris Dworkin. Recommendation for Block Cipher Modes of Operation Methods and Techniques [S]. 2001.12.