對Rijndael算法中密鑰擴展的優化

王根義

（陜西職業技術學院 陜西 西安 710100）

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

1 密鑰擴展的相關概念

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

2 密鑰擴展函數KeyExpansion（）的實現方案

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的常數表（用于“循環常數”）。讓我們看一看這三項中的每一項，然后返回到整個KeyExpansion例程。RotWord例程非常簡單，它接受 4字節的數組并將它們排列，請注意，由KeyExpansion使用的 RotWord函數與由加密算法使用的非常相似，唯一的區別就是它作用于密鑰次序表w[]的單行，而不是同ShiftRows例程作用于整個被加密的狀態表 State[]。SubWord例程使用置換表 Sbox，針對密鑰次序表 w[]的給定行執行逐字節置換[6]。KeyExpansion運算中的置換方法與加密算法中的置換方法完全相同。要被置換的輸入字節分成（x，y）對，該對用作置換表 Sbox的索引。例如，置換 0x27將導致 x=2，y=7，而且 Sbox[2，7]將返回 0xcc[7]。

3 Rijndael算法中加法和乘法的數學域理論

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

上式對應的十六進制數表示式為：

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

4 Rijndael算法中KeyExpansion（）函數的優化

KeyExpansion（）的實現方法

當 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；

}

}；

當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（）函數使用名為循環常數表的數組Rcon[]中，每個循環常數最左邊的字節是 GF（28）域中 2的冪。即第一個循環常數最左邊的字節是1，往后每個值都是上一個值按 GF（28）中的乘法法則乘以 0x02。

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

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

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

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

產生Random（K）的函數：

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

{

r0=seed；

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

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

}

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

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

5 KeyExpansion（）的實現方法的改進

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

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

}

這個主循環的代碼經過上機實驗證明完全正確可靠，可以克服5中的主循環的缺點，節約軟硬件資源，提高代碼的運行速度。

6 結束語

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

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

[2]譚方勇.網絡安全技術實用教程[M].重慶：重慶出版社，2000.

[3]黃月江.信息安全保密：現代與未來戰爭的信息衛士[M].北京：國防工業出版社，2008.

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

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

[6]楊義先.現代密碼新理論[M].北京：科學出版社，2002.

[7]谷大武.高級加密標準 （AES）算法—Rijndael的設計[M].北京：清華大學出版社，2003.

[8]高峻.AES算法的改進用法及其在數據庫加密中的應用[J].中南民族大學學報：自然科學版，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數據加密技術中AES算法的分析與改進[J].電腦知識與技術，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]薩師煊，王珊.數據庫系統概論[M].北京，高等教育出版社，2000.

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

[13]黃月江.信息安全保密：現代與未來戰爭的信息衛士[M].北京：國防工業出版社，2008.

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

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

[16]楊義先.現代密碼新理論[M].北京：科學出版社，2002.

[17]谷大武.高級加密標準（AES）算法—Rijndael的設計[M].北京：清華大學出版社，2003.

[18]譚方勇.網絡安全技術實用教程[M].重慶出版社，2000.