AES 高级加密标准

AES 高级加密标准

基本情况

高级加密标准(Advanced Encryption Standard)又称 Rijndael 加密法,用来代替原先的 DES 算法。Rijndael 使用置换-组合架构,在软件和硬件上都能快速地加解密。

严格意义上讲,AES 和 Rijndael 不完全一样,AES 的分组区块长度固定为 128 位,密钥长度可以是 128,192 或 256 位(AES-128, AES-192, AES-256);而 Rigndael 使用的密钥和长度可以是 32 的整数倍,以 128 位为下限,256 位为上限。

术语定义

输入和输出

输入与输出都是 128 比特的序列,加密密钥可选 128 位、192 位或 256 位。

字节

AES 中最基本的数据处理单元是字节,所有的字节都可以表示为如下串联:

\[\{b_7,b_6,b_5,b_4,b_3,b_2,b_1,b_0 \}\]

亦用在有限域中的多项式表示:

\[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^1+b_0 x^0 = \sum_{i=0}^7 b_i x^i \]

例如:{01100011} 表示为有限域中的元素 \(x^6 +x^5+x+1\),用十六进制表示是0x53。用四位二进制表示十六进制数也是 AES 常用方式。

字节数组

128 位的输入序列 \(input_0 input_1 input_2 ... input_{127}\) 表示为 16 个字节数组,(密钥同样可以如此表示)。

\[a_n=\{input_{8n},input_{8n+1},...,input_{8n+7} \}\]

状态

AES 算法的操作都是在一个二维字节数组上进行的,每一个二位字节数组称为一个状态(State)。

State array input and output
State array input and output

每一个状态又可以表现为字(Word)的行式,每一列为一字(32 bit)。

数学基础

在有限域中,两个多项式的加法,就是其对应字节,逐比特位异或,亦是模二加法。例如:

\[\begin{align}&(x^6+x^4+x^2+x+1)+(x^7+x+1)=x^7+x^6+x^4+x^2 \ &(polynomial \ notation)\\ &\{01010111\} \oplus \{10000011\}=\{11010100\} \ &(binary \ notation) \\ &\{57\} \oplus \{83\}=\{d4\} \ & (hexadecimal \ notation) \end{align}\]

在有限域 \(GF(2^8)\) 中,两个多项式的乘法,结果需要对一个不可约多项式取模,这个不可约多项式是:\(m(x)=x^8+x^4+x^3+x+1\),十六进制是 {01}{1b}。

例如,\(\{57\}\cdot \{83\} =\{c1\}\),因为:

\[\begin{align} (x^6+x^4+x^2+x+1)(x^7+x+1)= \ & x^{13}+x^{11}+x^9+x^8+x^7+ \\ & x^7+x^5+x^3+x^2+x+ \\ &x^6+x^4+x^2+x+1 \\ = \ &x^{13}+x^{11}+x^9+x^8+x^6+ \\ & x^5+x^4+x^2+x+1 \end{align}\]

\[\begin{align} x^{13}+x^{11}+x^9+x^8+x^6+ x^5+x^4+x^2+x+1 & \ modulo \ (x^8+x^4+x^3+x+1) \\ & =x^7+x^6+1 \end{align}\]

在有限域 \(GF(2^8)\) 中,求一个多项式的乘法逆元。由扩展欧几里得算法总可以求出满足 \(b(x)a(x)+m(x)c(x)=1\) 的 a(x)。这样,多项式 b(x) 的乘法逆元为:

\[b^{-1}(x)=a(x)mod \ m(x)\]

在有限域 \(GF(2^8)\) 中,仅用 x({00000010} 或 {02})乘以任意一个多项式,结果如下:

\[ b_7 x^8+b_6 x^7+b_5 x^6+b_4 x^5+b_3 x^4+b_2 x^3+b_1 x^2+b_0 x \]

这个结果就是对原字节进行左移位,如果 \(b_7 =0\),则这个结果不用再取模(最高位已经小于 8);若 \(b_7=1\),则对不可约多项式取模,实际上就是结果对 {1b} 取模。

实际上这个操作在 AES 中记为 xtime()。可以证明,任意高位的多项式乘法,都可以用其来进行替代操作。例如,\(\{57\}\cdot \{13\} =\{fe\}\),因为:

\[\begin{align}\{57\}\cdot \{02\} =xtime(\{57\})= \{ae\} \\ \{57\}\cdot \{04\} =xtime(\{ae\}) =\{47\} \\ \{57\}\cdot \{08\} =xtime(\{47\})=\{8e\} \\ \{57\}\cdot \{10\} =xtime(\{8e\}) =\{07\} \end{align}\]

所以:

\[\begin{align} \{57\}\cdot \{13\} &=\{57\} \cdot (\{01\}\oplus \{02\} \oplus \{10\}) \\ &=\{57\} \oplus \{ae\} \oplus \{07\} \\ &=\{fe\} \end{align}\]

加密算法

根据 AES 密钥长度的不同,加密轮数也不同,由下表定义:

Key-Block-Round Combination
Key-Block-Round Combination

每一轮,由字节代换(SubBytes)、行移位(ShiftRows)、列混合(MixColumns)、轮密钥加(AddRoundKey)四部分组成。最后一轮没有列混合,算法伪代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])
begin
byte state[4,Nb] = 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[round*Nb, (round+1)*Nb-1])

out = state
end

字节代换

字节代换是一个非线性的字节替代,由两个变换合成得到。

  1. 将字节在有限域 \(GF(2^8)\) 中求乘法逆元,{00} 映射到自身。

  2. 对字节在 \(GF(2^8)\) 上做如下仿射变换,c 是 {63}

    \(b'_i=b_i\oplus b_{(i+4)mod \ 8}\oplus b_{(i+5)mod \ 8}\oplus b_{(i+6)mod \ 8}\oplus b_{(i+7)mod \ 8}\oplus c_i\)

实际上就是用下图的 S-box 代输入状态的每一字节。

S-box
S-box

方式如下:

SubBytes applies the S-box
SubBytes applies the S-box

行移位

将状态阵列的各行进行循环左移,不同行的位移量不同。偏移量与分组长度、行号有关。第 0 行不动,第 i 行循环 \(C_i\) 字节,如下表所示:

Nb C1 C2 C3
4 1 2 3
6 1 2 3
8 1 3 4

以 Nb = 4 为例:

ShiftRows
ShiftRows

列混合

将状态阵列的每一列看作有限域 \(GF(2^8)\) 上的多项式 s(x),与多项式

\(a(x)=\{03\}x^3+\{01\}x^2+\{01\}x+\{02\}\)\(x^4+1\) 相乘,写成矩阵形式:

MixColumns
MixColumns

轮密钥加

将轮密钥与状态按比特异或。轮密钥是通过密钥扩展算法生成的。

AddRoundKey
AddRoundKey

密钥扩展算法

密钥扩展算法一共生成 Nb(Nr+1) 字。每一字对应子密钥的一列。生成算法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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

解密算法

解密算法与加密类似,但不相同。解密算法框架如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
InvCipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])
begin
byte state[4,Nb] = 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
InvShiftRows

逆字节代换

代换表为:

Inverse S-box
Inverse S-box

逆列混合

将状态阵列的每一列看作有限域 \(GF(2^8)\) 上的多项式 s(x),与多项式

\(a^{-1}(x)=\{0b\}x^3+\{0d\}x^2+\{09\}x+\{0e\}\)\(x^4+1\) 相乘,写成矩阵形式:

InvMixColumns
InvMixColumns

等价的解密算法

由于字节代换和行移位两个算法是可以交换顺序的,且列混合运算是对输入线性有关的。则,等价的解密算法框图可表示为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
EqInvCipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])
begin
byte state[4,Nb] = in

AddRoundKey(State, w[Nr*Nb, (Nr+1)*Nb-1])

for round = Nr-1 step -1 downto 1
InvSubBytes(state)
InvShiftRows(State)
InvMixColumns(state)
AddRoundKey(State, w[round*Nb, (round+1)*Nb-1])
end for

InvSubBytes(state)
InvShiftRows(state)
AddRoundKey(State, w[0, Nb-1])

out = state
end

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×