Rijndael加密算法的介紹

 作者:林祝興 葉義雄 楊國(guó)鴻

本文針對(duì)Rijndael加密算法的數(shù)學(xué)理論背景，算法的架構(gòu)，回合的轉(zhuǎn)換，金鑰的產(chǎn)生，以及各種攻擊破密法等等，做了一些簡(jiǎn)單的介紹。

一、簡(jiǎn)介

在AES ( Advanced Encryption Standard ) 的選拔中，從最初的十五個(gè)算法，到十個(gè)、五個(gè)，逐步篩選出適合用來(lái)作為下一代加密算法的標(biāo)準(zhǔn)。Rijndael在經(jīng)過(guò)了一番時(shí)日的考驗(yàn)之后，也一直名列前矛。直至十月二日，Rijndael才脫穎而出，這篇文章便是針對(duì)Rijndael作簡(jiǎn)要的介紹。

Rijndael是一個(gè)反復(fù)運(yùn)算的加密算法，它允許可變動(dòng)的數(shù)據(jù)區(qū)塊及金鑰的長(zhǎng)度。數(shù)據(jù)區(qū)塊與金鑰長(zhǎng)度的變動(dòng)是各自獨(dú)立的。

在Rijndael算法中定義了幾個(gè)名詞，分述如下：

State：在運(yùn)算過(guò)程中所產(chǎn)生的中間值，是一個(gè)4×Nb的矩陣，Nb可由數(shù)據(jù)長(zhǎng)度除以32位求得，也就是把數(shù)據(jù)分割成Nb個(gè)區(qū)塊。

Cipher Key：用來(lái)做加密運(yùn)算的金鑰，形式是一個(gè)4×Nk的矩陣，Nk可由金鑰長(zhǎng)度除以32位求得，也就是把金鑰分割成Nk個(gè)32位的子金鑰。

在Rijndael算法中，運(yùn)算的回合數(shù)(Nr)是由Nb及Nk所決定的，回合數(shù)的變動(dòng)定義如下表。

 

二、Rijndael的數(shù)學(xué)背景

在Rijndael中使用了許多字節(jié)層級(jí)的運(yùn)算，而這些運(yùn)算是以GF(2⁸)為基礎(chǔ)架構(gòu)。也有一些采用了4-byte的字組運(yùn)算。在這部分，我們將介紹這些基本的數(shù)學(xué)原理。

(1)       GF(2⁸)的定義

假設(shè)一個(gè)字節(jié)b由b₇b₆b₅b₄b₃b₂b₁b₀組成，我們可以把這些b_i想象成一個(gè)7次多項(xiàng)式的系數(shù)，而這些系數(shù)不是0就是1：

b₇ x⁷+ b₆ x⁶+ b₅ x⁵+ b₄ x⁴+ b₃ x³+ b₂ x²+ b₁ x + b₀，

例如，(57)₁₆的二進(jìn)制表示法為(0101,0111)₂表示成多項(xiàng)式，則為：

x⁶+ x⁴+ x²+ x + 1 .

(2)       加法

兩個(gè)多項(xiàng)式的加法，則是定義為相同指數(shù)項(xiàng)的系數(shù)和再模余2，簡(jiǎn)單的說(shuō)就是作EXOR運(yùn)算(i.e., 1+1=0)。例如：

(57)₁₆+(83)₁₆=(01010111)₂+(10000011)₂ = (11010100)₂ = (D4)₁₆

       或是(x⁶+x⁴+x²+x+1) + (x⁷+x+1) = x⁷+x⁶+x⁴+x²

(3)       乘法

在乘法里面，多項(xiàng)式相乘之后的結(jié)果很容易造成溢位的問(wèn)題，解決溢位的方式是把相乘的結(jié)果，再模余一個(gè)不可分解的多項(xiàng)式m(x)。在Rijndael中，定義一個(gè)這樣子的多項(xiàng)式為

m(x)=x⁸+x⁴+x³+x+1或是(11B)₁₆

例如：

(57)₁₆?(83)₁₆ = ( x⁶+ x⁴+ x²+ x + 1)? ( x⁷+ x + 1) = x¹³+ x¹¹+ x⁹+ x⁸+ x⁷+x⁷+ x⁵+ x³+ x²+x+x⁶+ x⁴+ x²+ x + 1

= (x¹³+ x¹¹+ x⁹+ x⁸+ x⁶+ x⁵+ x⁴+ x³+ 1+x¹³+ x¹¹+ x⁹+ x⁸+ x⁶+ x⁵+ x⁴+ x³+ 1) modulo (x⁸+ x⁴+ x³+ x + 1)

= x⁷+ x⁶+ 1=(C1)₁₆

(4)       乘以x

若把b(x)乘上x，得到b₇ x⁸+ b₆ x⁷+ b₅ x⁶+ b₄ x⁵+ b₃ x⁴+ b₂ x³+ b₁ x² + b₀x。若b₇=0，不會(huì)發(fā)生溢位問(wèn)題，答案即是正確的；若b₇=1，發(fā)生溢位問(wèn)題，必須減去m(x)。我們可以把這種運(yùn)算表示為xtime(x)，其運(yùn)算方式為left shift(若溢位則和(1B)₁₆做EXOR運(yùn)算)，例如：‘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加密算法是由一個(gè)initial Round Key addition，Nr-1個(gè)回合運(yùn)算，及一個(gè)final round所組成。加密過(guò)程以C語(yǔ)言偽碼敘述如下：

Rijndael(State, CipherKey)

//state表示輸入的數(shù)據(jù)明文，

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

//ExpandedKey表示每個(gè)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，可以先行計(jì)算出來(lái)，所以加密過(guò)程可以簡(jiǎn)化為：

Rijndael(State,ExpandedKey)

//State表示輸入的數(shù)據(jù)明文，

//ExpandedKey表示每個(gè)Round使用的子金鑰。

{

AddRoundKey(State,ExpandedKey);

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

{

Round(State,ExpandedKey + Nb×i) ;

}

FinalRound (State, ExpandedKey + Nb×Nr);

}

各個(gè)子運(yùn)算介紹如下。

回合轉(zhuǎn)換(Round transformation)：

回合轉(zhuǎn)換包含四個(gè)不同的工作，其算法如下：

Round(State,RoundKey)

//State表示輸入的數(shù)據(jù)明文，

//RoundKey表示每個(gè)Round使用的子金鑰。

{

ByteSub(State);

ShiftRow(State);

MixColumn(State);

AddRoundKey(State,RoundKey);

}

 

 

算法中的終止回合(Final round)包含下列工作項(xiàng)目：

FinalRound(State,RoundKey)

//State表示輸入的數(shù)據(jù)明文，

//RoundKey表示每個(gè)Round使用的子金鑰。

{

ByteSub(State) ;

ShiftRow(State) ;

AddRoundKey(State,RoundKey);

}

以下針對(duì)每個(gè)回合轉(zhuǎn)換的運(yùn)算過(guò)程，作一個(gè)深入的介紹，可以更清楚算法的過(guò)程。

1.            字節(jié)取代轉(zhuǎn)換(ByteSub transformation)：

字節(jié)轉(zhuǎn)換是一個(gè)以字節(jié)為單位的非線(xiàn)性取代運(yùn)算，取代表(S-Box)是經(jīng)過(guò)兩個(gè)運(yùn)算過(guò)程而建立，并且是可逆的。

首先找出每個(gè)字節(jié)在GF(2⁸)中的乘法反元素；

接著經(jīng)過(guò)一個(gè)仿射(Affine)轉(zhuǎn)換運(yùn)算，定義如下：

 

(本圖摘錄自參考文獻(xiàn)[1])

字節(jié)取代(ByteSub)運(yùn)算對(duì)State的影響，如下圖所示：

 

(本圖摘錄自參考文獻(xiàn)[1])

字節(jié)取代(ByteSub)轉(zhuǎn)換的反運(yùn)算：

計(jì)算仿射對(duì)應(yīng)之后的相反運(yùn)算可得到S^-1-Box，以此S^-1-Box做字節(jié)取代(ByteSub)即可。

2.            移列轉(zhuǎn)換( ShiftRow transformation )：

在這個(gè)轉(zhuǎn)換中，State的每一列以不同的偏移量做環(huán)狀位移，第0列不動(dòng)，第一列位移C1個(gè)字節(jié)，第二列位移C2個(gè)字節(jié)，第三列位移C3個(gè)字節(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)運(yùn)算對(duì)于State的影響，圖示如下：

(本圖摘錄自參考文獻(xiàn)[1])

移列轉(zhuǎn)換(ShiftRow)的反運(yùn)算：

對(duì)第二第三及第四列做Nb-C1,Nb-C2,Nb-C3個(gè)字節(jié)的環(huán)狀位移即可。

3.            混行轉(zhuǎn)換(MixColumn transformation)：

在這個(gè)轉(zhuǎn)換中，把State當(dāng)作一個(gè)存在GF(2⁸)中的多項(xiàng)式。并且對(duì)一個(gè)固定的多項(xiàng)式c(x)作乘法，如果發(fā)生溢位，則再模余x⁴+1。表示如下：

c(x) = ‘03’ x³ + ‘01’ x² + ‘01’ x + ‘02’ .

c(x)與x⁴+1互質(zhì)，令b(x) = c(x) Ä a(x)，以矩陣乘法表示如下：

 

(本圖摘錄自參考文獻(xiàn)[1])

State經(jīng)過(guò)混行(MixColumn)運(yùn)算之后的變化如下：

 

(本圖摘錄自參考文獻(xiàn)[1])

混行(MixColumn)轉(zhuǎn)換的反運(yùn)算，則是乘上一個(gè)特殊的多項(xiàng)式d(x)，

(‘03’x³ + ‘01’x² + ‘01’x + ‘02’ ) Ä d(x) = ‘01’,

d(x) = ‘0B’x³ + ‘0D’x² + ‘09’x + ‘0E’ .

4.            The Round Key Addition：

這個(gè)運(yùn)算主要是把每一個(gè)回合金鑰(Round Key)透過(guò)簡(jiǎn)單的bitwise EXOR加入到每一個(gè)State中，以圖示如下：

 

(本圖摘錄自參考文獻(xiàn)[1])

四、金鑰的排程(Key Schedule)

回合金鑰(Round Key)是從加密金鑰(Cipher Key)經(jīng)過(guò)運(yùn)算產(chǎn)生出來(lái)的。金鑰排程(Key Schedule)是由金鑰擴(kuò)充(Key Expansion)及回合金鑰的選擇(Round Key Selection)組成的，基本的理論如下：

       所有回合金鑰的總位數(shù)是把區(qū)塊長(zhǎng)度(block length)乘上回合數(shù)加1，(有Nr-1個(gè)回合，加上一個(gè)終止回合(final round))，例如，128個(gè)位的區(qū)塊長(zhǎng)度經(jīng)過(guò)10個(gè)回合運(yùn)算，所需要用到的所有回合金鑰的總位數(shù)為1408個(gè)位。

       加密金鑰(Cipher Key)必須擴(kuò)充為擴(kuò)充金鑰(Expanded Key)。

       回合金鑰是從擴(kuò)充金鑰中選出來(lái)的，選擇的方式如下：

       第一個(gè)回合金鑰由前Nb個(gè)字組組成，第二個(gè)回合金鑰由接下來(lái)的Nb個(gè)字組組成，余此類(lèi)推。

(1)       金鑰的擴(kuò)充( Key Expansion )：

擴(kuò)充后的金鑰是一個(gè)4-byte的線(xiàn)性數(shù)組，表示為W[Nb×(Nr+1)]。前Nk個(gè)字組包含了加密金鑰(Cipher Key)。

       金鑰擴(kuò)充函式和Nk是息息相關(guān)的，分為兩種情況運(yùn)作，一是當(dāng)Nk小于或等于6，另外則是當(dāng)Nk大于6，以偽碼敘述如下：

當(dāng)Nk≦6時(shí)，

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)傳回一個(gè)4-byte的字組，這些字組是輸入的字組經(jīng)過(guò)S-box的轉(zhuǎn)換所產(chǎn)生的相對(duì)字組。RotByte(W)則是傳回經(jīng)過(guò)旋轉(zhuǎn)的字組。

當(dāng)Nk＞6時(shí)，

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;

}

}

以上兩種情況的相異處在于當(dāng)Nk≦6時(shí)，(i-4)是Nk的倍數(shù)時(shí)，對(duì)于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個(gè)回合金鑰是指在存在回合金鑰緩沖區(qū)的字組W[Nb*i]到W[Nb*(i+1)]，圖示如下：

 

(本圖摘錄自參考文獻(xiàn)[1])

五、安全性分析

       我們針對(duì)以下已知的攻擊法對(duì)Rijndael的安全性分析作一簡(jiǎn)要敘述，包括差分攻擊法(Differential Cryptanalysis)，線(xiàn)性攻擊法(Linear Cryptanalysis)，平方攻擊法(The Square Attack)，內(nèi)插攻擊法(Interpolation attacks)等攻擊方式。

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

       此攻擊法是一種Chosen-plaintext attack，利用大量已知的明文/密文對(duì)之間的差異，據(jù)以推測(cè)出金鑰的位值。在大部分的回合運(yùn)算中(回合數(shù)超過(guò)3)，若存在超過(guò)2^1-n(n指的是區(qū)塊長(zhǎng)度)比例的可預(yù)測(cè)性的差異，這個(gè)攻擊法就可以推測(cè)出金鑰的位值。在Rijndael中，已經(jīng)證明在經(jīng)過(guò)Rijndael四個(gè)回合的運(yùn)算后，存在不超過(guò)2^-150比例的可預(yù)測(cè)性差異，在八個(gè)回合運(yùn)算中不超過(guò)2^-300。詳細(xì)證明過(guò)程，請(qǐng)參照參考文獻(xiàn)。

(2)       線(xiàn)性攻擊法( Linear Cryptanalysis )

       這是一種Known-plaintext攻擊法，利用大量搜集到的明文/密文對(duì)的相關(guān)性，對(duì)加密法進(jìn)行攻擊。明文/密文對(duì)的相關(guān)性由線(xiàn)性軌跡(Linear trails)所組成，由于線(xiàn)性軌跡的相關(guān)系數(shù)與Round keys的值有密切關(guān)系，透過(guò)相關(guān)系數(shù)的正負(fù)號(hào)，線(xiàn)性攻擊法就可以找出金鑰值。要對(duì)抗這種攻擊法，有一個(gè)必要條件就是使這種相關(guān)系數(shù)大于2^n/2的線(xiàn)性軌跡不存在。在Rijndael中，已經(jīng)證明出當(dāng)執(zhí)行四個(gè)回合時(shí)，不存在相關(guān)系數(shù)大于2^-75的線(xiàn)性軌跡；在執(zhí)行八個(gè)回合時(shí)，其相關(guān)系數(shù)大于2^-150的相關(guān)系數(shù)亦不存在。詳細(xì)證明過(guò)程請(qǐng)參照參考文獻(xiàn)。

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

       這種攻擊法是一種chosen- plaintext attack，而且和字節(jié)取代(ByteSub)，混行(MixColumn)時(shí)的多項(xiàng)式乘法，金鑰的排程(Key Schedule)等運(yùn)算無(wú)關(guān)。當(dāng)Rijndael執(zhí)行6個(gè)回合以上時(shí)，此種方式比完全的金鑰搜尋(exhaustive key search)來(lái)的更有效率。關(guān)于此種攻擊方式的詳盡描述及Rijndael如何延伸此種攻擊方式，請(qǐng)參照參考文獻(xiàn)。

(4)       內(nèi)插攻擊法( Interpolation attacks )

       在這種攻擊法中，攻擊者利用加密的輸入及輸出配對(duì)，建立一些多項(xiàng)式。如果加密的組件有一個(gè)簡(jiǎn)潔的代數(shù)展開(kāi)式，并且和管理的復(fù)雜度結(jié)合在一起時(shí)，這種攻擊法便是可行的。基本的攻擊方式是如果攻擊者建立的代數(shù)展開(kāi)式的階度(degree)很小，只需要一些加密法的輸入及輸出配對(duì)就可以得到代數(shù)展開(kāi)式的各項(xiàng)系數(shù)。然而，在GF(2⁸)中的取代矩陣(S-box)，它的展開(kāi)式為：63+8fx¹²⁷+b5x¹⁹¹+01x²²³+f4x²³⁹+25x²⁴⁷+f9x²⁵¹+09x²⁵³+05x²⁵⁴。其余介紹，請(qǐng)參照參考文獻(xiàn)。

(5)、弱金鑰(Weak keys)

       關(guān)于弱金鑰的發(fā)生，基本上是因?yàn)榧用芊ǖ姆蔷€(xiàn)性運(yùn)算與實(shí)際金鑰值有密切關(guān)系。而這種問(wèn)題不存在于Rijndael之中，因?yàn)樵?/span>Rijndael中，金鑰是以EXOR運(yùn)算，而所有的非線(xiàn)性運(yùn)算都定義在取代矩陣(S-box)中。在Rijndael中，對(duì)金鑰的選擇，是沒(méi)有限制的。

六、結(jié)論：

       以上對(duì)Rijndael作一簡(jiǎn)要介紹之后，我們以Rijndael的優(yōu)點(diǎn)與限制作為我們的結(jié)論。

(1)、Rijndael有以下優(yōu)點(diǎn)—

以實(shí)作觀(guān)點(diǎn)而言

1.            Rijndael可以實(shí)作在Pentium ( Pro ) 等計(jì)算機(jī)上，并已相當(dāng)快的速度處理運(yùn)算；而在表格大小與效率之間是可以做取舍的。

2.            Rijndael可以實(shí)作在智能卡(Smart Card)上，使用少量的RAM，少量的程序代碼；在ROM與效率之間也是可以做取舍的。

3.            在設(shè)計(jì)上，回合的轉(zhuǎn)換是可平行處理的。

4.            加密法不采用算術(shù)運(yùn)算，不會(huì)因?yàn)椴煌幚砥骷軜?gòu)而有所偏差。

設(shè)計(jì)簡(jiǎn)單化：

1.            設(shè)計(jì)上不引用其它加密組件，如S-box。

2.            安全度不建立在一些分析不夠明確的算術(shù)運(yùn)算之上。

3.            加密法緊湊，不易藏入暗門(mén)等程序代碼。

除此之外，Rijndael更允許可變動(dòng)的區(qū)塊長(zhǎng)度及金鑰長(zhǎng)度，其長(zhǎng)度可由128位到256位之間；所以回合數(shù)也是可變動(dòng)的。

(2)Rijndael的限制：

在解密過(guò)程中有以下限制

1.            實(shí)作在智慧卡時(shí)，解密不如加密來(lái)的有效率，解密需要更多的程序代碼及cycles，但是跟其它算法比起來(lái)，仍然是快速的。

2.            以軟件而言，加密和解密使用不同的程序和表格。

3.            以硬件而言，解密只能重用部分加密的電路。

posted on 2007-08-06 22:45 bilicon 閱讀(1158) 評(píng)論(2)  編輯 收藏 引用