作者:林祝興 葉義雄 楊國鴻
本文針對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. 以硬件而言，解密只能重用部分加密的電路。