作者:林祝興 葉義雄 楊國鴻
本文針對Rijndael加密算法的數(shù)學理論背景，算法的架構(gòu)，回合的轉(zhuǎn)換，金鑰的產(chǎn)生，以及各種攻擊破密法等等，做了一些簡單的介紹。
一、簡介
在AES ( Advanced Encryption Standard ) 的選拔中，從最初的十五個算法，到十個、五個，逐步篩選出適合用來作為下一代加密算法的標準。Rijndael在經(jīng)過了一番時日的考驗之后，也一直名列前矛。直至十月二日，Rijndael才脫穎而出，這篇文章便是針對Rijndael作簡要的介紹。
Rijndael是一個反復運算的加密算法，它允許可變動的數(shù)據(jù)區(qū)塊及金鑰的長度。數(shù)據(jù)區(qū)塊與金鑰長度的變動是各自獨立的。
在Rijndael算法中定義了幾個名詞，分述如下：
State：在運算過程中所產(chǎn)生的中間值，是一個4×Nb的矩陣，Nb可由數(shù)據(jù)長度除以32位求得，也就是把數(shù)據(jù)分割成Nb個區(qū)塊。
Cipher Key：用來做加密運算的金鑰，形式是一個4×Nk的矩陣，Nk可由金鑰長度除以32位求得，也就是把金鑰分割成Nk個32位的子金鑰。
在Rijndael算法中，運算的回合數(shù)(Nr)是由Nb及Nk所決定的，回合數(shù)的變動定義如下表。
|
Nr
|
Nb=4
|
Nb=6
|
Nb=8
|
|
Nk=4
|
10
|
12
|
14
|
|
Nk=6
|
12
|
12
|
14
|
|
Nk=8
|
14
|
14
|
14
|
二、Rijndael的數(shù)學背景
在Rijndael中使用了許多字節(jié)層級的運算，而這些運算是以GF(28)為基礎(chǔ)架構(gòu)。也有一些采用了4-byte的字組運算。在這部分，我們將介紹這些基本的數(shù)學原理。
(1) GF(28)的定義
假設(shè)一個字節(jié)b由b7b6b5b4b3b2b1b0組成，我們可以把這些bi想象成一個7次多項式的系數(shù)，而這些系數(shù)不是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) 加法
兩個多項式的加法，則是定義為相同指數(shù)項的系數(shù)和再模余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) 乘法
在乘法里面，多項式相乘之后的結(jié)果很容易造成溢位的問題，解決溢位的方式是把相乘的結(jié)果，再模余一個不可分解的多項式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，不會發(fā)生溢位問題，答案即是正確的；若b7=1，發(fā)生溢位問題，必須減去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的加密架構(gòu)
Rijndael加密算法是由一個initial Round Key addition，Nr-1個回合運算，及一個final round所組成。加密過程以C語言偽碼敘述如下：
Rijndael(State, CipherKey)
//state表示輸入的數(shù)據(jù)明文，
//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表示輸入的數(shù)據(jù)明文，
//ExpandedKey表示每個Round使用的子金鑰。
{
AddRoundKey(State,ExpandedKey);
For( i=1 ; i<Nr ; i++ )
{
Round(State,ExpandedKey + Nb×i) ;
}
FinalRound (State, ExpandedKey + Nb×Nr);
}
各個子運算介紹如下。
回合轉(zhuǎn)換(Round transformation)：
回合轉(zhuǎn)換包含四個不同的工作，其算法如下：
Round(State,RoundKey)
//State表示輸入的數(shù)據(jù)明文，
//RoundKey表示每個Round使用的子金鑰。
{
ByteSub(State);
ShiftRow(State);
MixColumn(State);
AddRoundKey(State,RoundKey);
}
算法中的終止回合(Final round)包含下列工作項目：
FinalRound(State,RoundKey)
//State表示輸入的數(shù)據(jù)明文，
//RoundKey表示每個Round使用的子金鑰。
{
ByteSub(State) ;
ShiftRow(State) ;
AddRoundKey(State,RoundKey);
}
以下針對每個回合轉(zhuǎn)換的運算過程，作一個深入的介紹，可以更清楚算法的過程。
1. 字節(jié)取代轉(zhuǎn)換(ByteSub transformation)：
字節(jié)轉(zhuǎn)換是一個以字節(jié)為單位的非線性取代運算，取代表(S-Box)是經(jīng)過兩個運算過程而建立，并且是可逆的。
首先找出每個字節(jié)在GF(28)中的乘法反元素；
接著經(jīng)過一個仿射(Affine)轉(zhuǎn)換運算，定義如下：
(本圖摘錄自參考文獻[1])
字節(jié)取代(ByteSub)運算對State的影響，如下圖所示：
(本圖摘錄自參考文獻[1])
字節(jié)取代(ByteSub)轉(zhuǎn)換的反運算：
計算仿射對應(yīng)之后的相反運算可得到S-1-Box，以此S-1-Box做字節(jié)取代(ByteSub)即可。
2. 移列轉(zhuǎn)換( ShiftRow transformation )：
在這個轉(zhuǎn)換中，State的每一列以不同的偏移量做環(huán)狀位移，第0列不動，第一列位移C1個字節(jié)，第二列位移C2個字節(jié)，第三列位移C3個字節(jié)。位移的偏移量C1,C2,C3跟區(qū)塊的數(shù)目(Nb)有關(guān)，定義如下表：
|
Nb
|
C1
|
C2
|
C3
|
|
4
|
1
|
2
|
3
|
|
6
|
1
|
2
|
3
|
|
8
|
1
|
3
|
4
|
移列轉(zhuǎn)換(ShiftRow)運算對于State的影響，圖示如下：
(本圖摘錄自參考文獻[1])
移列轉(zhuǎn)換(ShiftRow)的反運算：
對第二第三及第四列做Nb-C1,Nb-C2,Nb-C3個字節(jié)的環(huán)狀位移即可。
3. 混行轉(zhuǎn)換(MixColumn transformation)：
在這個轉(zhuǎn)換中，把State當作一個存在GF(28)中的多項式。并且對一個固定的多項式c(x)作乘法，如果發(fā)生溢位，則再模余x4+1。表示如下：
c(x) = ‘03’ x3 + ‘01’ x2 + ‘01’ x + ‘02’ .
c(x)與x4+1互質(zhì)，令b(x) = c(x) Ä a(x)，以矩陣乘法表示如下：
(本圖摘錄自參考文獻[1])
State經(jīng)過混行(MixColumn)運算之后的變化如下：
(本圖摘錄自參考文獻[1])
混行(MixColumn)轉(zhuǎn)換的反運算，則是乘上一個特殊的多項式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)經(jīng)過運算產(chǎn)生出來的。金鑰排程(Key Schedule)是由金鑰擴充(Key Expansion)及回合金鑰的選擇(Round Key Selection)組成的，基本的理論如下：
所有回合金鑰的總位數(shù)是把區(qū)塊長度(block length)乘上回合數(shù)加1，(有Nr-1個回合，加上一個終止回合(final round))，例如，128個位的區(qū)塊長度經(jīng)過10個回合運算，所需要用到的所有回合金鑰的總位數(shù)為1408個位。
加密金鑰(Cipher Key)必須擴充為擴充金鑰(Expanded Key)。
回合金鑰是從擴充金鑰中選出來的，選擇的方式如下：
第一個回合金鑰由前Nb個字組組成，第二個回合金鑰由接下來的Nb個字組組成，余此類推。
(1) 金鑰的擴充( Key Expansion )：
擴充后的金鑰是一個4-byte的線性數(shù)組，表示為W[Nb×(Nr+1)]。前Nk個字組包含了加密金鑰(Cipher Key)。
金鑰擴充函式和Nk是息息相關(guān)的，分為兩種情況運作，一是當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的字組，這些字組是輸入的字組經(jīng)過S-box的轉(zhuǎn)換所產(chǎn)生的相對字組。RotByte(W)則是傳回經(jīng)過旋轉(zhuǎn)的字組。
當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的倍數(shù)時，對于W[i-1]先執(zhí)行SubByte，再執(zhí)行EXOR。
上述回合常數(shù)定義如下：
Rcon[i] = (RC[i],‘00’,‘00’,‘00’)，其中RC[0]=’01’，RC[i]=xtime(Rcon[i-1])。
(2) 選擇回合金鑰(Round Key Selection)
第i個回合金鑰是指在存在回合金鑰緩沖區(qū)的字組W[Nb*i]到W[Nb*(i+1)]，圖示如下：
(本圖摘錄自參考文獻[1])
五、安全性分析
我們針對以下已知的攻擊法對Rijndael的安全性分析作一簡要敘述，包括差分攻擊法(Differential Cryptanalysis)，線性攻擊法(Linear Cryptanalysis)，平方攻擊法(The Square Attack)，內(nèi)插攻擊法(Interpolation attacks)等攻擊方式。
(1) 差分攻擊法( Differential Cryptanalysis )
此攻擊法是一種Chosen-plaintext attack，利用大量已知的明文/密文對之間的差異，據(jù)以推測出金鑰的位值。在大部分的回合運算中(回合數(shù)超過3)，若存在超過21-n(n指的是區(qū)塊長度)比例的可預測性的差異，這個攻擊法就可以推測出金鑰的位值。在Rijndael中，已經(jīng)證明在經(jīng)過Rijndael四個回合的運算后，存在不超過2-150比例的可預測性差異，在八個回合運算中不超過2-300。詳細證明過程，請參照參考文獻。
(2) 線性攻擊法( Linear Cryptanalysis )
這是一種Known-plaintext攻擊法，利用大量搜集到的明文/密文對的相關(guān)性，對加密法進行攻擊。明文/密文對的相關(guān)性由線性軌跡(Linear trails)所組成，由于線性軌跡的相關(guān)系數(shù)與Round keys的值有密切關(guān)系，透過相關(guān)系數(shù)的正負號，線性攻擊法就可以找出金鑰值。要對抗這種攻擊法，有一個必要條件就是使這種相關(guān)系數(shù)大于2n/2的線性軌跡不存在。在Rijndael中，已經(jīng)證明出當執(zhí)行四個回合時，不存在相關(guān)系數(shù)大于2-75的線性軌跡；在執(zhí)行八個回合時，其相關(guān)系數(shù)大于2-150的相關(guān)系數(shù)亦不存在。詳細證明過程請參照參考文獻。
(3) 平方攻擊法( The Square attack )
這種攻擊法是一種chosen- plaintext attack，而且和字節(jié)取代(ByteSub)，混行(MixColumn)時的多項式乘法，金鑰的排程(Key Schedule)等運算無關(guān)。當Rijndael執(zhí)行6個回合以上時，此種方式比完全的金鑰搜尋(exhaustive key search)來的更有效率。關(guān)于此種攻擊方式的詳盡描述及Rijndael如何延伸此種攻擊方式，請參照參考文獻。
(4) 內(nèi)插攻擊法( Interpolation attacks )
在這種攻擊法中，攻擊者利用加密的輸入及輸出配對，建立一些多項式。如果加密的組件有一個簡潔的代數(shù)展開式，并且和管理的復雜度結(jié)合在一起時，這種攻擊法便是可行的。基本的攻擊方式是如果攻擊者建立的代數(shù)展開式的階度(degree)很小，只需要一些加密法的輸入及輸出配對就可以得到代數(shù)展開式的各項系數(shù)。然而，在GF(28)中的取代矩陣(S-box)，它的展開式為：63+8fx127+b5x191+01x223+f4x239+25x247+f9x251+09x253+05x254。其余介紹，請參照參考文獻。
(5)、弱金鑰(Weak keys)
關(guān)于弱金鑰的發(fā)生，基本上是因為加密法的非線性運算與實際金鑰值有密切關(guān)系。而這種問題不存在于Rijndael之中，因為在Rijndael中，金鑰是以EXOR運算，而所有的非線性運算都定義在取代矩陣(S-box)中。在Rijndael中，對金鑰的選擇，是沒有限制的。
六、結(jié)論：
以上對Rijndael作一簡要介紹之后，我們以Rijndael的優(yōu)點與限制作為我們的結(jié)論。
(1)、Rijndael有以下優(yōu)點—
以實作觀點而言
1. Rijndael可以實作在Pentium ( Pro ) 等計算機上，并已相當快的速度處理運算；而在表格大小與效率之間是可以做取舍的。
2. Rijndael可以實作在智能卡(Smart Card)上，使用少量的RAM，少量的程序代碼；在ROM與效率之間也是可以做取舍的。
3. 在設(shè)計上，回合的轉(zhuǎn)換是可平行處理的。
4. 加密法不采用算術(shù)運算，不會因為不同處理器架構(gòu)而有所偏差。
設(shè)計簡單化：
1. 設(shè)計上不引用其它加密組件，如S-box。
2. 安全度不建立在一些分析不夠明確的算術(shù)運算之上。
3. 加密法緊湊，不易藏入暗門等程序代碼。
除此之外，Rijndael更允許可變動的區(qū)塊長度及金鑰長度，其長度可由128位到256位之間；所以回合數(shù)也是可變動的。
(2)Rijndael的限制：
在解密過程中有以下限制
1. 實作在智慧卡時，解密不如加密來的有效率，解密需要更多的程序代碼及cycles，但是跟其它算法比起來，仍然是快速的。
2. 以軟件而言，加密和解密使用不同的程序和表格。
3. 以硬件而言，解密只能重用部分加密的電路。