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

王根義

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

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

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

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

2 密鑰擴(kuò)展函數(shù)KeyExpansion（）的實(shí)現(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個(gè)子例程 （RotWord和 SubWord），以及一個(gè)名為 Rcon的常數(shù)表（用于“循環(huán)常數(shù)”）。讓我們看一看這三項(xiàng)中的每一項(xiàng)，然后返回到整個(gè)KeyExpansion例程。RotWord例程非常簡(jiǎn)單，它接受 4字節(jié)的數(shù)組并將它們排列，請(qǐng)注意，由KeyExpansion使用的 RotWord函數(shù)與由加密算法使用的非常相似，唯一的區(qū)別就是它作用于密鑰次序表w[]的單行，而不是同ShiftRows例程作用于整個(gè)被加密的狀態(tài)表 State[]。SubWord例程使用置換表 Sbox，針對(duì)密鑰次序表 w[]的給定行執(zhí)行逐字節(jié)置換[6]。KeyExpansion運(yùn)算中的置換方法與加密算法中的置換方法完全相同。要被置換的輸入字節(jié)分成（x，y）對(duì)，該對(duì)用作置換表 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個(gè)）的值以及加法和乘法。GF代表伽羅華域，它以創(chuàng)建域理論的數(shù)學(xué)家命名。GF（28）有一個(gè)特征就是，加法或乘法運(yùn)算的結(jié)果必須位于集合 {0x00...0xff}中。盡管域理論相當(dāng)深?yuàn)W，但是 GF（28）加法的最終結(jié)果非常簡(jiǎn)單：GF（28） 加法只是 XOR 運(yùn)算。 但是，GF（28）乘法卻比較復(fù)雜。在 GF（28）中，一個(gè)數(shù)與 0x01相乘是特殊的，它與普通算術(shù)中的乘以1相對(duì)應(yīng)，即任何值與 0x01相乘都等于它本身。現(xiàn)在，讓我們看看與0x02相乘會(huì)怎樣。在多項(xiàng)式表示中，GF（28）的乘法對(duì)應(yīng)于多項(xiàng)式乘法模除次數(shù) 為8的不可約多項(xiàng)式（x8+x4+x3+x+1）。如果一個(gè)多項(xiàng)式除了1和它本身之外沒有其它因子，則稱它為不可約分的。對(duì)于Rijndael，這個(gè)模除用的多項(xiàng)式叫做 m（x）：m（x） = （x8+x4+x3+x+1），它所對(duì)應(yīng)的十六進(jìn)制數(shù)表示為'11BH'，對(duì)應(yīng)的二進(jìn)制數(shù)表示為9比特的‘100011011B’。以下是一個(gè)乘法的例子[15－16]：

上式對(duì)應(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相乘，會(huì)看到 0x03=0x02+0x01。因此：

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

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

當(dāng) Nk＜=6 時(shí)（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[]中，每個(gè)循環(huán)常數(shù)最左邊的字節(jié)是 GF（28）域中 2的冪。即第一個(gè)循環(huán)常數(shù)最左邊的字節(jié)是1，往后每個(gè)值都是上一個(gè)值按 GF（28）中的乘法法則乘以 0x02。

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

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

第一次生成RC[I]的時(shí)候按照原來的方式利用線性同余法生成偽隨機(jī)數(shù)I，從而選擇運(yùn)算對(duì)象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ì)算機(jī)當(dāng)前的日期或者時(shí)間；m是一個(gè)較大數(shù)，可以把它取為2w，w是計(jì)算機(jī)的字長(zhǎng)；a可以是0.01w和0.99w之間的任何整數(shù)；n等于當(dāng)前（I－1）。

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

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

上述5中提出的方法中的主循環(huán)由于用了分支程序，代碼較多，另外執(zhí)行時(shí)速度較慢。為了克服這兩個(gè)缺點(diǎn)，筆者設(shè)計(jì)了下列循環(huán)語句來實(shí)現(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

}

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

6 結(jié)束語

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

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

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

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

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

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

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

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

[8]高峻.AES算法的改進(jìn)用法及其在數(shù)據(jù)庫加密中的應(yīng)用[J].中南民族大學(xué)學(xué)報(bào)：自然科學(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í)與技術(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].北京：中國(guó)電力出版社，2008.

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

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

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

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

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

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