AES 1

向右看齐 2022-10-30 11:25 145阅读 0赞

本文针对 Rijndael 加密算法的数学理论背景，算法的架构，回合的转换，金钥的产生，以及各种攻击破密法等等，做了一些简单的介绍。

一、简介

在 AES ( Advanced Encryption Standard ) 的选拔中，从最初的十五个算法，到十个、五个，逐步筛选出适合用来作为下一代加密算法的标准。 Rijndael 在经过了一番时日的考验之后，也一直名列前矛。直至十月二日， Rijndael 才脱颖而出，这篇文章便是针对 Rijndael 作简要的介绍。

Rijndael 是一个反复运算的加密算法，它允许可变动的数据区块及金钥的长度。数据区块与金钥长度的变动是各自独立的。

在 Rijndael 算法中定义了几个名词，分述如下：

State ：在运算过程中所产生的中间值，是一个 4 × Nb 的矩阵， Nb 可由数据长度除以 32 位求得，也就是把数据分割成 Nb 个区块。

Cipher Key ：用来做加密运算的金钥，形式是一个 4 × Nk 的矩阵， Nk 可由金钥长度除以 32 位求得，也就是把金钥分割成 Nk 个 32 位的子金钥。

在 Rijndael 算法中，运算的回合数 (Nr) 是由 Nb 及 Nk 所决定的，回合数的变动定义如下表。

**二、**  **Rijndael**  **的数学背景**

在 Rijndael 中使用了许多字节层级的运算，而这些运算是以 GF(28 ) 为基础架构。也有一些采用了 4-byte 的字组运算。在这部分，我们将介绍这些基本的数学原理。

**(1)**  **GF(28 )**  **的定义**

假设一个字节 b 由 b7 b6 b5 b4 b3 b2 b1 b0 组成，我们可以把这些 bi 想象成一个 7 次多项式的系数，而这些系数不是 0 就是 1 ：

b7 x7 + b6 x6 + b5 x5 + b4 x4 + b3 x3 + b2 x2 + b1 x + b0 ，

例如， (57)16 的二进制表示法为 (0101,0111)2 表示成多项式，则为：

x6 + x4 + x2 + x + 1 .

**(2)**  **加法**

两个多项式的加法，则是定义为相同指数项的系数和再模余 2 ，简单的说就是作 EXOR 运算 (i.e., 1+1=0) 。例如：

(57)16 +(83)16 =(01010111)2 +(10000011)2 = (11010100)2 = (D4)16

或是 (x6 +x4 +x2 +x+1) + (x7 +x+1) = x7 +x6 +x4 +x2

**(3)**  **乘法**

在乘法里面，多项式相乘之后的结果很容易造成溢位的问题，解决溢位的方式是把相乘的结果，再模余一个不可分解的多项式 m(x) 。在 Rijndael 中，定义一个这样子的多项式为

m(x)=x8 +x4 +x3 +x+1 或是 (11B)16

例如：

(57)16 ‧ (83)16 = ( x6 + x4 + x2 + x + 1) ‧ ( x7 + x + 1) = x13 + x11 + x9 + x8 + x7 +x7 + x5 + x3 + x2 +x+x6 + x4 + x2 + x + 1

= (x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1+x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1) modulo (x8 + x4 + x3 + x + 1)

= x7 + x6 + 1=(C1)16

**(4)**  **乘以**  **x**

若把 b(x) 乘上 x ，得到 b7 x8 + b6 x7 + b5 x6 + b4 x5 + b3 x4 + b2 x3 + b1 x2 + b0 x 。若 b7 =0 ，不会发生溢位问题，答案即是正确的；若 b7 =1 ，发生溢位问题，必须减去 m(x) 。我们可以把这种运算表示为 xtime(x) ，其运算方式为 left shift( 若溢位则和 (1B)16 做 EXOR 运算 ) ，例如： ‘57’ · ‘13’ = ‘FE’

‘57’ · ‘02’ = xtime(57) = ‘AE’

‘57’ · ‘04’ = xtime(AE) = ‘47’

‘57’ · ‘08’ = xtime(47) = ‘8E’

‘57’ · ‘10’ = xtime(8E) = ‘07’

‘57’ · ‘13’ = ‘57’ · (‘01’ ⊕ ‘02’ ⊕ ‘10’) = ‘57’ ⊕ ‘AE’ ⊕ ‘07’ = ‘FE’

**三、**  **Rijndael**  **的加密架构**

Rijndael 加密算法是由一个 initial Round Key addition ， Nr-1 个回合运算，及一个 final round 所组成。加密过程以 C 语言伪码叙述如下：

Rijndael(State, CipherKey)

//state 表示输入的数据明文，

//CipherKey 表示使用的加密金钥，

//ExpandedKey 表示每个 Round 使用的子金钥。

KeyExpansion(CipherKey, ExpandedKey);

AddRoundKey(State, ExpandedKey);

For ( i=1; i<Nr; i++)

Round(State, ExpandedKey+Nb × i);

FinalRound(State, ExpandedKey+Nb × Nr);

上述算法中的 Key Expansion ，可以先行计算出来，所以加密过程可以简化为：

Rijndael(State,ExpandedKey)

//State 表示输入的数据明文，

//ExpandedKey 表示每个 Round 使用的子金钥。

AddRoundKey(State,ExpandedKey);

For( i=1 ; i<Nr ; i++ )

Round(State,ExpandedKey + Nb × i) ;

FinalRound (State, ExpandedKey + Nb × Nr);

各个子运算介绍如下。

**回合转换**  **(Round transformation)**  **：**

回合转换包含四个不同的工作，其算法如下：

Round(State,RoundKey)

//State 表示输入的数据明文，

//RoundKey 表示每个 Round 使用的子金钥。

ByteSub(State);

ShiftRow(State);

MixColumn(State);

AddRoundKey(State,RoundKey);

算法中的终止回合 (Final round) 包含下列工作项目：

FinalRound(State,RoundKey)

//State 表示输入的数据明文，

//RoundKey 表示每个 Round 使用的子金钥。

ByteSub(State) ;

ShiftRow(State) ;

AddRoundKey(State,RoundKey);

以下针对每个回合转换的运算过程，作一个深入的介绍，可以更清楚算法的过程。

**1.**  **字节取代转换**  **(ByteSub transformation)**  **：**

字节转换是一个以字节为单位的非线性取代运算，取代表 (S-Box) 是经过两个运算过程而建立，并且是可逆的。

首先找出每个字节在 GF(28 ) 中的乘法反元素；

接着经过一个仿射 (Affine) 转换运算，定义如下：

( 本图摘录自参考文献 \[1\])

字节取代 (ByteSub) 运算对 State 的影响，如下图所示：

( 本图摘录自参考文献 \[1\])

字节取代 (ByteSub) 转换的反运算：

计算仿射对应之后的相反运算可得到 S-1 -Box ，以此 S-1 -Box 做字节取代 (ByteSub) 即可。

**2.**  **移列转换**  **( ShiftRow transformation )**  **：**

在这个转换中， State 的每一列以不同的偏移量做环状位移，第 0 列不动，第一列位移 C1 个字节，第二列位移 C2 个字节，第三列位移 C3 个字节。位移的偏移量 C1,C2,C3 跟区块的数目 (Nb) 有关，定义如下表：

移列转换 (ShiftRow) 运算对于 State 的影响，图示如下：

( 本图摘录自参考文献 \[1\])

移列转换 (ShiftRow) 的反运算：

对第二第三及第四列做 Nb-C1,Nb-C2,Nb-C3 个字节的环状位移即可。

**3.**  **混行转换**  **(MixColumn transformation)**  **：**

在这个转换中，把 State 当作一个存在 GF(28 ) 中的多项式。并且对一个固定的多项式 c(x) 作乘法，如果发生溢位，则再模余 x4 +1 。表示如下：

c(x) = ‘03’ x3 + ‘01’ x2 + ‘01’ x + ‘02’ .

c(x) 与 x4 +1 互质，令 b(x) = c(x) Ä a(x) ，以矩阵乘法表示如下：

( 本图摘录自参考文献 \[1\])

State 经过混行 (MixColumn) 运算之后的变化如下：

( 本图摘录自参考文献 \[1\])

混行 (MixColumn) 转换的反运算，则是乘上一个特殊的多项式 d(x) ，

(‘03’x3 + ‘01’x2 + ‘01’x + ‘02’ ) Ä d(x) = ‘01’,

d(x) = ‘0B’x3 + ‘0D’x2 + ‘09’x + ‘0E’ .

**4.**  **The Round Key Addition**  **：**

这个运算主要是把每一个回合金钥 (Round Key) 透过简单的 bitwise EXOR 加入到每一个 State 中，以图示如下：

( 本图摘录自参考文献 \[1\])

**四、金钥的排程**  **(Key Schedule)**

回合金钥 (Round Key) 是从加密金钥 (Cipher Key) 经过运算产生出来的。金钥排程 (Key Schedule) 是由金钥扩充 (Key Expansion) 及回合金钥的选择 (Round Key Selection) 组成的，基本的理论如下：

所有回合金钥的总位数是把区块长度 (block length) 乘上回合数加 1 ， ( 有 Nr-1 个回合，加上一个终止回合 (final round)) ，例如， 128 个位的区块长度经过 10 个回合运算，所需要用到的所有回合金钥的总位数为 1408 个位。

加密金钥 (Cipher Key) 必须扩充为扩充金钥 (Expanded Key) 。

回合金钥是从扩充金钥中选出来的，选择的方式如下：

第一个回合金钥由前 Nb 个字组组成，第二个回合金钥由接下来的 Nb 个字组组成，余此类推。

**(1)**  **金钥的扩充**  **( Key Expansion )**  **：**

扩充后的金钥是一个 4-byte 的线性数组，表示为 W\[Nb × (Nr+1)\] 。前 Nk 个字组包含了加密金钥 (Cipher Key) 。

金钥扩充函式和 Nk 是息息相关的，分为两种情况运作，一是当 Nk 小于或等于 6 ，另外则是当 Nk 大于 6 ，以伪码叙述如下：

当 Nk ≦ 6 时，

KeyExpansion(byte Key\[4 × Nk\] word W\[Nb × (Nr+1)\])

for(i = 0; i < Nk; i++)

W\[i\] = (Key\[4 × i\], Key\[4 × i+1\], Key\[4 × i+2\], Key\[4 × i +3\] );

for(i = Nk; i < Nb × (Nr + 1); i++)

temp = W\[i - 1\];

if (i % Nk == 0)

temp = SubByte(RotByte(temp)) ^ Rcon\[i / Nk\];

W\[i\] = W\[i - Nk\] ^ temp;

在上面的子程序中， SubByte(W) 传回一个 4-byte 的字组，这些字组是输入的字组经过 S-box 的转换所产生的相对字组。 RotByte(W) 则是传回经过旋转的字组。

当 Nk ＞ 6 时，

KeyExpansion(byte Key\[4 × Nk\] word W\[Nb × (Nr+1)\])

for(i = 0; i < Nk; i++)

W\[i\] = (key\[4 × i\],key\[4 × i+1\], key\[4 × i+2\], key\[4 × i+3\] );

for(i = Nk; i < Nb × (Nr + 1); i++)

temp = W\[i - 1\];

if (i % Nk == 0)

temp = SubByte(RotByte(temp)) ^ Rcon\[i / Nk\];

else if (i % Nk == 4)

temp = SubByte(temp);

W\[i\] = W\[i - Nk\] ^ temp;

以上两种情况的相异处在于当 Nk ≦ 6 时， (i-4) 是 Nk 的倍数时，对于 W\[i-1\] 先执行 SubByte ，再执行 EXOR 。

上述回合常数定义如下：

Rcon\[i\] = (RC\[i\],‘00’,‘00’,‘00’) ，其中 RC\[0\]=’01’ ， RC\[i\]=xtime(Rcon\[i-1\]) 。

**(2)**  **选择回合金钥**  **(Round Key Selection)**

第 i 个回合金钥是指在存在回合金钥缓冲区的字组 W\[Nb\*i\] 到 W\[Nb\*(i+1)\] ，图示如下：

( 本图摘录自参考文献 \[1\])

五、安全性分析

我们针对以下已知的攻击法对 Rijndael 的安全性分析作一简要叙述，包括差分攻击法 (Differential Cryptanalysis) ，线性攻击法 (Linear Cryptanalysis) ，平方攻击法 (The Square Attack) ，内插攻击法 (Interpolation attacks) 等攻击方式。

(1) 差分攻击法 ( Differential Cryptanalysis )

此攻击法是一种 Chosen-plaintext attack ，利用大量已知的明文 / 密文对之间的差异，据以推测出金钥的位值。在大部分的回合运算中 ( 回合数超过 3) ，若存在超过 21-n (n 指的是区块长度 ) 比例的可预测性的差异，这个攻击法就可以推测出金钥的位值。在 Rijndael 中，已经证明在经过 Rijndael 四个回合的运算后，存在不超过 2-150 比例的可预测性差异，在八个回合运算中不超过 2-300 。详细证明过程，请参照参考文献。

(2) 线性攻击法 ( Linear Cryptanalysis )

这是一种 Known-plaintext 攻击法，利用大量搜集到的明文 / 密文对的相关性，对加密法进行攻击。明文 / 密文对的相关性由线性轨迹 (Linear trails) 所组成，由于线性轨迹的相关系数与 Round keys 的值有密切关系，透过相关系数的正负号，线性攻击法就可以找出金钥值。要对抗这种攻击法，有一个必要条件就是使这种相关系数大于 2n/2 的线性轨迹不存在。在 Rijndael 中，已经证明出当执行四个回合时，不存在相关系数大于 2-75 的线性轨迹；在执行八个回合时，其相关系数大于 2-150 的相关系数亦不存在。详细证明过程请参照参考文献。

(3) 平方攻击法 ( The Square attack )

这种攻击法是一种 chosen- plaintext attack ，而且和字节取代 (ByteSub) ，混行 (MixColumn) 时的多项式乘法，金钥的排程 (Key Schedule) 等运算无关。当 Rijndael 执行 6 个回合以上时，此种方式比完全的金钥搜寻 (exhaustive key search) 来的更有效率。关于此种攻击方式的详尽描述及 Rijndael 如何延伸此种攻击方式，请参照参考文献。

(4) 内插攻击法 ( Interpolation attacks )

在这种攻击法中，攻击者利用加密的输入及输出配对，建立一些多项式。如果加密的组件有一个简洁的代数展开式，并且和管理的复杂度结合在一起时，这种攻击法便是可行的。基本的攻击方式是如果攻击者建立的代数展开式的阶度 (degree) 很小，只需要一些加密法的输入及输出配对就可以得到代数展开式的各项系数。然而，在 GF(28 ) 中的取代矩阵 (S-box) ，它的展开式为： 63+8fx127 +b5x191 +01x223 +f4x239 +25x247 +f9x251 +09x253 +05x254 。其余介绍，请参照参考文献。

(5) 、弱金钥 (Weak keys)

关于弱金钥的发生，基本上是因为加密法的非线性运算与实际金钥值有密切关系。而这种问题不存在于 Rijndael 之中，因为在 Rijndael 中，金钥是以 EXOR 运算，而所有的非线性运算都定义在取代矩阵 (S-box) 中。在 Rijndael 中，对金钥的选择，是没有限制的。

六、结论：

以上对 Rijndael 作一简要介绍之后，我们以 Rijndael 的优点与限制作为我们的结论。

(1) 、 Rijndael 有以下优点 —

以实作观点而言

1. Rijndael 可以实作在 Pentium ( Pro ) 等计算机上，并已相当快的速度处理运算；而在表格大小与效率之间是可以做取舍的。

2. Rijndael 可以实作在智能卡 (Smart Card) 上，使用少量的 RAM ，少量的程序代码；在 ROM 与效率之间也是可以做取舍的。

3. 在设计上，回合的转换是可平行处理的。

4. 加密法不采用算术运算，不会因为不同处理器架构而有所偏差。

设计简单化：

1. 设计上不引用其它加密组件，如 S-box 。