作者:林祝兴 叶义雄 杨国鸿
本文针对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所决定的，回合数的变动定义如下表。
|
Nr
|
Nb=4
|
Nb=6
|
Nb=8
|
|
Nk=4
|
10
|
12
|
14
|
|
Nk=6
|
12
|
12
|
14
|
|
Nk=8
|
14
|
14
|
14
|
二、Rijndael的数学背景
在Rijndael中使用了许多字节层级的运算，而这些运算是以GF(28)为基础架构。也有一些采用了4-byte的字组运算。在这部分，我们将介绍这些基本的数学原理。
(1) GF(28)的定义
假设一个字节b由b7b6b5b4b3b2b1b0组成，我们可以把这些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 + b0x。若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)有关，定义如下表：
|
Nb
|
C1
|
C2
|
C3
|
|
4
|
1
|
2
|
3
|
|
6
|
1
|
2
|
3
|
|
8
|
1
|
3
|
4
|
移列转换(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。
2. 安全度不建立在一些分析不够明确的算术运算之上。
3. 加密法紧凑，不易藏入暗门等程序代码。
除此之外，Rijndael更允许可变动的区块长度及金钥长度，其长度可由128位到256位之间；所以回合数也是可变动的。
(2)Rijndael的限制：
在解密过程中有以下限制
1. 实作在智慧卡时，解密不如加密来的有效率，解密需要更多的程序代码及cycles，但是跟其它算法比起来，仍然是快速的。
2. 以软件而言，加密和解密使用不同的程序和表格。
3. 以硬件而言，解密只能重用部分加密的电路。