對Rijndael算法中密鑰擴(kuò)展的優(yōu)化

王根義

（陜西職業(yè)技術(shù)學(xué)院 陜西 西安 710100）

因為Rijndael是AES數(shù)據(jù)加密新標(biāo)準(zhǔn)的算法中最常用的一種。Rijndael數(shù)據(jù)加密技術(shù)在我國被推行時間較短，而且Rijndael蜜鑰擴(kuò)展技術(shù)比較深奧，所以好多學(xué)者和數(shù)據(jù)加密方面工作人員對Rijndael密鑰擴(kuò)展的原理沒有掌握，更談不上創(chuàng)新一種高效的密鑰擴(kuò)展方法來改進(jìn)密鑰擴(kuò)展工作，本作者抱著推廣Rijndael密鑰擴(kuò)展技術(shù)，講清密Rijndael鑰擴(kuò)展原理，提出實現(xiàn)Rijndael密鑰擴(kuò)展的優(yōu)化方法的目的，特寫此論文。

1 密鑰擴(kuò)展的相關(guān)概念

Rijndael數(shù)據(jù)加密鑰的過程，所用的子密鑰是由一個密鑰擴(kuò)展函數(shù)KeyExpansion（）用種子密鑰產(chǎn)生的，種子密鑰也叫初始密鑰或主密鑰。把一個種子密鑰劃分成若干塊，每一塊也叫作一個字，一個字中所含的字節(jié)數(shù)用N b來表示，這個種子密鑰中所含的字?jǐn)?shù)叫作種子密鑰的Nk，所有的子密鑰和主密鑰構(gòu)成密鑰數(shù)組W[]，共（N r+1）*N b個字節(jié)，其中r叫作加密鑰的輪數(shù)[1-2]。

2 密鑰擴(kuò)展函數(shù)KeyExpansion（）的實現(xiàn)方案

KeyExpansion（）的定義方案如下所示[3-5]：

KeyExpansion（byte[]key， byte[][4]w）

{

copy the seed key into the first rows of w

for each remaining row of w

{

use two of the previous rows to create a new row

}

}

“use two of the previous rows to create a new row” 例程使用2個子例程 （RotWord和 SubWord），以及一個名為 Rcon的常數(shù)表（用于“循環(huán)常數(shù)”）。讓我們看一看這三項中的每一項，然后返回到整個KeyExpansion例程。RotWord例程非常簡單，它接受 4字節(jié)的數(shù)組并將它們排列，請注意，由KeyExpansion使用的 RotWord函數(shù)與由加密算法使用的非常相似，唯一的區(qū)別就是它作用于密鑰次序表w[]的單行，而不是同ShiftRows例程作用于整個被加密的狀態(tài)表 State[]。SubWord例程使用置換表 Sbox，針對密鑰次序表 w[]的給定行執(zhí)行逐字節(jié)置換[6]。KeyExpansion運(yùn)算中的置換方法與加密算法中的置換方法完全相同。要被置換的輸入字節(jié)分成（x，y）對，該對用作置換表 Sbox的索引。例如，置換 0x27將導(dǎo)致 x=2，y=7，而且 Sbox[2，7]將返回 0xcc[7]。

3 Rijndael算法中加法和乘法的數(shù)學(xué)域理論

Rijndael算法基于名為 GF（28） 的域。 GF（28） 域包括一組從 0x00到 0xff（共28=256個）的值以及加法和乘法。GF代表伽羅華域，它以創(chuàng)建域理論的數(shù)學(xué)家命名。GF（28）有一個特征就是，加法或乘法運(yùn)算的結(jié)果必須位于集合 {0x00...0xff}中。盡管域理論相當(dāng)深奧，但是 GF（28）加法的最終結(jié)果非常簡單：GF（28） 加法只是 XOR 運(yùn)算。 但是，GF（28）乘法卻比較復(fù)雜。在 GF（28）中，一個數(shù)與 0x01相乘是特殊的，它與普通算術(shù)中的乘以1相對應(yīng)，即任何值與 0x01相乘都等于它本身。現(xiàn)在，讓我們看看與0x02相乘會怎樣。在多項式表示中，GF（28）的乘法對應(yīng)于多項式乘法模除次數(shù) 為8的不可約多項式（x8+x4+x3+x+1）。如果一個多項式除了1和它本身之外沒有其它因子，則稱它為不可約分的。對于Rijndael，這個模除用的多項式叫做 m（x）：m（x） = （x8+x4+x3+x+1），它所對應(yīng)的十六進(jìn)制數(shù)表示為'11BH'，對應(yīng)的二進(jìn)制數(shù)表示為9比特的‘100011011B’。以下是一個乘法的例子[15－16]：

上式對應(yīng)的十六進(jìn)制數(shù)表示式為：

根據(jù)二進(jìn)制數(shù)的性質(zhì)，可以推出GF（28）域乘數(shù)為2的乘法可以這樣進(jìn)行：如果被乘數(shù)小于 0x80，那么，乘法結(jié)果只是向左位移 1位的值。如果被乘數(shù)大于或等于 0x80，那么，乘法結(jié)果將是向左位移 1位后再與0x1b值執(zhí)行 XOR運(yùn)算的值。這將防止出現(xiàn)“域溢出”，并使乘法結(jié)果落在范圍內(nèi)。0x80○×0x02=0x1b是 0x80向左移 1位，然后與 0x1b執(zhí)行XOR運(yùn)算。一旦建立了與 GF（28）中的 0x02的加法和乘法，就可以使用它們來定義與任何常數(shù)的乘法。要與 GF（28）中的0x03相乘，可以將 0x03分解為2的冪和加法。要將任意字節(jié) b與 0x03相乘，會看到 0x03=0x02+0x01。因此：

4 Rijndael算法中KeyExpansion（）函數(shù)的優(yōu)化

KeyExpansion（）的實現(xiàn)方法

當(dāng) Nk＜=6 時（Nk=4 or 6）[8－11]：

KeyExpansion（byte Key[4*Nk]，byte&W[Nb*（Nr+1）][4]）

{

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=ByteSub（temp＜＜8）^Rcon[i/Nk]；

W[i]=W[i－Nk]^temp；

}

}；

當(dāng)Nk=8：

KeyExpansion（byte Key[4*Nk]， byte&W[Nb*（Nr+1）Key][4]）

{

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=ByteSub（temp＜＜8）^Rcon[i/Nk]；

else if（i%Nk==4）

temp=ByteSub（temp＜＜8）；

W[i]=W[i－Nk]^temp；

}；

}；

Rcon[i]定義為[12][13][14]：

Rcon[i]= （RC[i]，‘00’，‘00’，‘00’）

RC[1]=1，RC[2]=2，RC[3]=4，……

RC[i]=2（i－1）

以往的KeyExpansion（）函數(shù)使用名為循環(huán)常數(shù)表的數(shù)組Rcon[]中，每個循環(huán)常數(shù)最左邊的字節(jié)是 GF（28）域中 2的冪。即第一個循環(huán)常數(shù)最左邊的字節(jié)是1，往后每個值都是上一個值按 GF（28）中的乘法法則乘以 0x02。

由于Rijndael算法的子密鑰的前N k個字完全由種子密鑰填充而成，這樣做雖然密鑰的離散性非常好，減少了密鑰間的線性關(guān)系，但是密鑰的雪崩效應(yīng)就減弱了，同時它的輪密鑰是通過遞歸定義生成的，也就是說，對某一輪的密鑰可以由前一輪或幾輪的輪密鑰推導(dǎo)而來。如果我們知道了這前N k個字的部分密鑰字，就可以根據(jù)遞推公式得到與這些部分密鑰字相關(guān)的密鑰字。當(dāng)泄露的密鑰信息達(dá)到一定程度時，其它的種子密鑰或許就可以通過窮舉法獲得，進(jìn)而獲得全部輪子密鑰。對于公開的算法來說，如果密鑰已知，輕而易舉地就可以由密文譯出明文，信息的保密就受到了威脅。那么，怎樣在優(yōu)化線性關(guān)系和雪崩效應(yīng)的同時提高密鑰的保密性呢?從安全的角度來分析，為了使攻擊者更難于找到加密密鑰特別是種子密鑰，應(yīng)該提高密鑰生成算法的混淆性來有效抵抗密碼攻擊。

由此提出了在子密鑰生成階段和密鑰選擇階段引入一個隨機(jī)函數(shù)的方法來避免上述缺陷，具體方法如下：

第一次生成RC[I]的時候按照原來的方式利用線性同余法生成偽隨機(jī)數(shù)I，從而選擇運(yùn)算對象rand[I]，具體的公式如下：

RC[I]=（RC[I－1]）·Random（K） 其中 k 為小于 I的任何數(shù)

產(chǎn)生Random（K）的函數(shù)：

Random（n，m，seed，a，b）

{

r0=seed；

for（i=1；i＜=n；i++）

ri=（a*ri－1+b）mod m；

}

其中將種子參數(shù)seed設(shè)為計算機(jī)當(dāng)前的日期或者時間；m是一個較大數(shù)，可以把它取為2w，w是計算機(jī)的字長；a可以是0.01w和0.99w之間的任何整數(shù)；n等于當(dāng)前（I－1）。

這樣就可以方便的產(chǎn)生出隨機(jī)的參與異或運(yùn)算的對象rand[I]。密鑰生成后把所有的子密鑰形成一個表，而在密鑰選擇階段同樣可以使用隨機(jī)函數(shù)，打亂子密鑰選擇的規(guī)律性，使生成各列子密鑰的過程具有完全的隨機(jī)性。但是由于算法中用到了加密者的本地時間作為seed，而解密者不一定與加密者時間統(tǒng)一，為了解決這個問題，我們決定用數(shù)字時間戳（digital time－stamp）系統(tǒng)，該系統(tǒng)可以讓通信雙方遵守同樣的時間，而算法中只要把取的系統(tǒng)時間加入到密文里的某個只有雙方才知道的特殊位置 （或者直接加入明文里加密也可）就可以使解密者很容易地對密文進(jìn)行解密了。當(dāng)然，以上方法只能應(yīng)用在網(wǎng)絡(luò)中，但是它給Rijndael帶來的安全性是前所未有的，并且跟通信系統(tǒng)緊密聯(lián)合在一起，在應(yīng)用方面將會有很大的用武之地。

5 KeyExpansion（）的實現(xiàn)方法的改進(jìn)

上述5中提出的方法中的主循環(huán)由于用了分支程序，代碼較多，另外執(zhí)行時速度較慢。為了克服這兩個缺點，筆者設(shè)計了下列循環(huán)語句來實現(xiàn)[17－19]主循環(huán)：

for（i=Nk； i＜ Nb* （Nr+1）； ++i）

{

temp=w[i－1]

if（i%Nk==0）

temp=SubWord[RotWord（temp）]xor Rcon[i/Nk]

else if（Nk==8 and row%Nk==4）

temp=SubWord（temp）

[i]=w[i－Nk]xor temp

}

這個主循環(huán)的代碼經(jīng)過上機(jī)實驗證明完全正確可靠，可以克服5中的主循環(huán)的缺點，節(jié)約軟硬件資源，提高代碼的運(yùn)行速度。

6 結(jié)束語

文中創(chuàng)新點：用簡單、明了和新穎的邏輯關(guān)系闡明了密鑰擴(kuò)展的原理，提出了具體實現(xiàn)AES密鑰擴(kuò)展的兩種新方法。文中提出的具體實現(xiàn)AES密鑰擴(kuò)展的兩種新方法，可根據(jù)計算機(jī)的特點，靈活的應(yīng)用在不同的數(shù)據(jù)加密工程當(dāng)中，以提高數(shù)據(jù)加密工程的效率和速度；文中對密鑰擴(kuò)展的原理闡述方法可改進(jìn)有關(guān)密鑰擴(kuò)展的教材及書籍。

[1]戴宗坤.信息安全管理指南 [M].北京：中國電力出版社，2008.

[2]譚方勇.網(wǎng)絡(luò)安全技術(shù)實用教程[M].重慶：重慶出版社，2000.

[3]黃月江.信息安全保密：現(xiàn)代與未來戰(zhàn)爭的信息衛(wèi)士[M].北京：國防工業(yè)出版社，2008.

[4]武新華.黑客攻防秘技實戰(zhàn)解析[M].北京：人民大學(xué)出版社，2008.

[5]宋震.密碼學(xué)[M].北京：中國水利水電出版社，2002.

[6]楊義先.現(xiàn)代密碼新理論[M].北京：科學(xué)出版社，2002.

[7]谷大武.高級加密標(biāo)準(zhǔn) （AES）算法—Rijndael的設(shè)計[M].北京：清華大學(xué)出版社，2003.

[8]高峻.AES算法的改進(jìn)用法及其在數(shù)據(jù)庫加密中的應(yīng)用[J].中南民族大學(xué)學(xué)報：自然科學(xué)版，2002（04）：67－69.GAO Jun.Improved usage of AES algorithm and its application in data encryption technology[J].Journal of South-Central University For Nationalities:Natural Science Edition，2002（04）：67－69，90.

[9]徐卉.WLAN數(shù)據(jù)加密技術(shù)中AES算法的分析與改進(jìn)[J].電腦知識與技術(shù)，2009（03）：591－592，609.XU Hui.Analysis and improvement of AESalgorithm in data encryption technology WLAN[J].Computer Knowledge and Technology，2009（03），591－592，609.

[10]Bertino E.Data secureity[J].Data&Knowledge Engineering，1998，25（1－2）:199－216.

[11]薩師煊，王珊.數(shù)據(jù)庫系統(tǒng)概論[M].北京，高等教育出版社，2000.

[12]戴宗坤.信息安全管理指南[M].北京：中國電力出版社，2008.

[13]黃月江.信息安全保密：現(xiàn)代與未來戰(zhàn)爭的信息衛(wèi)士[M].北京：國防工業(yè)出版社，2008.

[14]武新華.黑客攻防秘技實戰(zhàn)解析[M].北京：人民大學(xué)出版社，2008.

[15]宋震.密碼學(xué)[M].北京：中國水利水電出版社，2002.

[16]楊義先.現(xiàn)代密碼新理論[M].北京：科學(xué)出版社，2002.

[17]谷大武.高級加密標(biāo)準(zhǔn)（AES）算法—Rijndael的設(shè)計[M].北京：清華大學(xué)出版社，2003.

[18]譚方勇.網(wǎng)絡(luò)安全技術(shù)實用教程[M].重慶出版社，2000.