摘 要： 種子密鑰是高級(jí)加密標(biāo)準(zhǔn)（AES）的關(guān)鍵參量，而密鑰擴(kuò)展算法則是保護(hù)種子密鑰不被盜取的重要實(shí)現(xiàn)方法。首先對(duì)加密算法的實(shí)現(xiàn)方法與過(guò)程進(jìn)行研究，然后詳細(xì)分析密鑰擴(kuò)展算法的運(yùn)算過(guò)程，最后針對(duì)原有算法存在的安全隱患和破解難度不高的缺點(diǎn)，通過(guò)循環(huán)移位對(duì)密鑰擴(kuò)展算法進(jìn)行改進(jìn)，提出一種具有“運(yùn)算方向單一性”的密鑰擴(kuò)展實(shí)現(xiàn)策略；并在Keil環(huán)境、12 MHz條件下測(cè)試各算法。通過(guò)實(shí)驗(yàn)結(jié)果分析得到，在保證運(yùn)算速率的前提下，這種新算法可以進(jìn)一步改善AES算法中種子密鑰的安全性，并且沒(méi)有破壞與加密算法間的同步特性。

關(guān)鍵詞： 高級(jí)加密標(biāo)準(zhǔn)； 密鑰擴(kuò)展算法； 種子密鑰； 循環(huán)移位

中圖分類(lèi)號(hào)： TN915.08?34； TP391 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）10?0005?04

Analysis of AES algorithm and its key extension algorithm improvement

LIU Yanping， LI Qiuhui

（School of Electronic Information Engineering， Hebei University of Technology， Tianjin 300401， China）

Abstract： Seed key is the key parameter of Advanced Encryption Standard （AES）， however the key extension algorithm is the important realization method for protecting the seed key from being stolen. In this article， the implementation method and process of the encryption algorithm are studied， and the operation process of the key expansion algorithm is analyzed in detail. In view of the shortcomings that hidden trouble in security and low breaking difficulty of the original algorithm， the key expansion algorithm was improved by means of the cyclic shift， and a new key expansion strategy with single operation direction was designed. Each algorithm was tested under the condition of 12 MHz and in KEIL. The experimental result and analysis show that， under the premise of guaranteeing the operation rate， the new algorithm can further enhance the seed key safety of AES algorithm， and doesn’t damage the synchronization feature between the encryption algorithm and key expansion algorithm.

Keywords： advanced encryption standard； key extension algorithm； seed key； cyclic shift

0 引 言

AES（Advanced Encryption Standard）加密算法的原型是由比利時(shí)密碼學(xué)家Joan Daemen和Vincent Rijmen設(shè)計(jì)的Rijndael加密算法。AES作為目前安全性最高標(biāo)準(zhǔn)[1]，已在信息安全領(lǐng)域得到廣泛的應(yīng)用。AES算法是分組密碼[2]設(shè)計(jì)的一種很好的實(shí)現(xiàn)方式，分組密碼設(shè)計(jì)是指存在一個(gè)算法，可以在密鑰的控制下簡(jiǎn)單而迅速地從一個(gè)置換子集中（足夠大且足夠好）選出一個(gè)置換，對(duì)當(dāng)前輸入的明文進(jìn)行加密交換。Rijndael加密算法設(shè)計(jì)具有簡(jiǎn)單性、高效性、對(duì)稱(chēng)性、模塊性等優(yōu)點(diǎn)，但是通過(guò)研究目前對(duì)算法的攻擊方法發(fā)現(xiàn)，AES采用了擴(kuò)充種子密鑰生成子密鑰的方式，密鑰擴(kuò)展算法設(shè)計(jì)的比較簡(jiǎn)單，所以具有高效、快速等優(yōu)點(diǎn)。而能量攻擊[3]和滲透攻擊等攻擊正是在AES算法中的密鑰擴(kuò)展算法中做文章，來(lái)攻擊AES加密算法的安全性。此算法在攻擊者獲得一輪子密鑰，就可以推導(dǎo)出原種子密鑰的缺陷。逆推過(guò)程是密鑰破解者主要的思維方式，那么如果能夠找到一種方法可以使算法的運(yùn)算方向具有單一性，即算法只可以從前往后計(jì)算而不可以從后往前推算，就可以防范攻擊了。在設(shè)計(jì)密鑰擴(kuò)展算法時(shí)要遵循的準(zhǔn)則包括以下幾方面：

（1） 簡(jiǎn)單性，每一次加密都要進(jìn)行10輪的密鑰擴(kuò)展，如若算法比較復(fù)雜，會(huì)影響加密的效率；

（2） 即時(shí)性，加密過(guò)程的每一輪運(yùn)算都離不開(kāi)輪密鑰，無(wú)需等到所得的密鑰全部生成再進(jìn)行加密運(yùn)算，加密與密鑰擴(kuò)展二者可以同時(shí)進(jìn)行。

1 AES加密算法研究

有限域[4]通俗的定義就是函數(shù)的運(yùn)算結(jié)果全部都在一個(gè)域中，與熟悉的實(shí)數(shù)域不同，在有限域中規(guī)定一個(gè)最大的值，例如有限域GF（28）這個(gè)域的最大值是256，其他所有超過(guò)這個(gè)最大值的數(shù)都會(huì)通過(guò)一定的方法使其回歸到不超過(guò)最大值的這個(gè)域中。有限域的概念在密碼學(xué)中被廣泛應(yīng)用，而有限域的乘法運(yùn)算更是AES算法實(shí)現(xiàn)的數(shù)學(xué)基礎(chǔ)，在下面將會(huì)對(duì)有限域的乘法逆運(yùn)算進(jìn)行敘述。

AES算法的實(shí)現(xiàn)過(guò)程主要包括兩大部分，加密過(guò)程和密鑰擴(kuò)展，其是一個(gè)數(shù)據(jù)塊和密鑰塊均可變的迭代分組加密算法，有三種分組長(zhǎng)度128位，192位，256位，下面以128位為例介紹算法的加密過(guò)程。

AES的明文分組（即各輪的輸入與輸出以及每一次變換所產(chǎn)生的中間量）稱(chēng)之為狀態(tài)，所有的運(yùn)算均是以狀態(tài)為單位進(jìn)行的。如圖1所示，加密部分主要分為四個(gè)步驟：S盒變換（作用在狀態(tài)中每個(gè)字節(jié)上的一種非線性字節(jié)轉(zhuǎn)換，可以通過(guò)計(jì)算出來(lái)的S盒進(jìn)行映射）、行變換、列變換、輪密鑰加。

圖1 128位數(shù)據(jù)分組加密過(guò)程

1.1 S盒變換

作為算法實(shí)現(xiàn)過(guò)程中惟一一個(gè)非線性部件，S盒變換的作用是實(shí)現(xiàn)混淆功能。AES采用的S盒是由限域GF（28）下以模[mx=x8+x4+x3+x+1]的乘法逆運(yùn)算和GF（2）下的仿射變換[5]實(shí)現(xiàn)的，選取的S盒具有最佳的線性偏差和差分均勻性。

圖3 密鑰擴(kuò)展算法實(shí)現(xiàn)過(guò)程

表1 輪常量RC[i]值表

如圖3所示，子密鑰后三個(gè)字由本輪密鑰的前一個(gè)字與上一輪密鑰得到，即Wi與Wi-3異或得到Wi+1，Wi+1與Wi-2異或得到Wi+2，Wi+2與Wi-1異或得到Wi+3。

由此，最后得到的擴(kuò)展密鑰是一個(gè)直線陣列，最初的前4 B由種子密鑰填充，其他字節(jié)以4 B為一個(gè)單位字，由前4 B按照這種遞歸算法生成后面的4字。

從密鑰擴(kuò)展的實(shí)現(xiàn)過(guò)程得知，雖然每輪都進(jìn)行一次復(fù)雜化的運(yùn)算，但是每輪密鑰與它的上輪密鑰有著較強(qiáng)的相關(guān)性。假設(shè)攻擊者獲取某一輪子密鑰，那么只需要猜測(cè)232次便可以利用已知子密鑰推導(dǎo)出其上一輪的子密鑰，以致可以推導(dǎo)出包括種子密鑰在內(nèi)的所有輪密鑰。需要截獲4輪之后的輪密鑰窮盡次數(shù)達(dá)到2128次，此時(shí)才能達(dá)到暴力破解的強(qiáng)度，這正好給能量攻擊和滲透攻擊破解算法帶來(lái)了突破口。所以在此希望可以找到一種方式既可以保留原密鑰擴(kuò)展算法的高效性，又可以盡可能提高算法的單向性，使得算法的逆推不可實(shí)現(xiàn)。

2.2 密鑰擴(kuò)展算法的改進(jìn)

文獻(xiàn)[6]中對(duì)算法的改進(jìn)借助其他算法的運(yùn)算方式而且提高了每輪運(yùn)算的復(fù)雜度，這使得原本算法的優(yōu)點(diǎn)不復(fù)存在。在保留AES原始密鑰擴(kuò)展算法的優(yōu)勢(shì)的基礎(chǔ)上，本文針對(duì)其不足之處，從提高攻擊強(qiáng)度并兼顧算法執(zhí)行效率方面進(jìn)行改進(jìn)，提出了以下幾種改進(jìn)方法。

方法一：AES算法原始密鑰擴(kuò)展算法本身有著簡(jiǎn)單、靈活等優(yōu)點(diǎn)，所以在原算法的基礎(chǔ)上進(jìn)行改進(jìn)是最理想的。由原算法分析可知，其最大的缺點(diǎn)就是輪密鑰間的相關(guān)性很強(qiáng)，為了避免這種不足，將密鑰的每個(gè)字都經(jīng)過(guò)一輪復(fù)雜化運(yùn)算，保持原密鑰擴(kuò)展算法中復(fù)雜化運(yùn)算[7]的輪常量Rcon[]的定義，RotByte變換和SubWord變換的運(yùn)算規(guī)則不變，如圖4所示，然后經(jīng)過(guò)復(fù)雜化運(yùn)算獲得字與未復(fù)雜化的字異或后得到下一輪密鑰的一個(gè)字，直接對(duì)種子密鑰進(jìn)行擴(kuò)展。這種改進(jìn)的密鑰擴(kuò)展方法可以使得輪密鑰間的相關(guān)性減小，具有運(yùn)算方向的單一性，即數(shù)據(jù)只可從前往后運(yùn)算，不可從后向前推導(dǎo)，即使是第一輪子密鑰被截獲，由此推導(dǎo)種子密鑰也許要嘗試2128次，可以達(dá)到暴力破解的強(qiáng)度，安全性與原算法相比得到了大大的提高。

方法二：在改進(jìn)方法一中雖然安全強(qiáng)度得到了提高，但是每輪子密鑰的生成都要經(jīng)過(guò)4次復(fù)雜化的運(yùn)算，這使得算法的運(yùn)算效率與原算法相比降低了很多。而原算法最大的弊端就是相鄰兩輪間的相關(guān)性較大，為了減小原算法中相鄰兩輪密鑰間的相關(guān)性[8]，方法二在原來(lái)的基礎(chǔ)上做出如下改進(jìn)：

保留原密鑰擴(kuò)展算法的復(fù)雜化運(yùn)算的各個(gè)步驟：移位變換（RotByte）、SubWord變換、輪常量Rcon[]異或運(yùn)算，和基本操作流程不變，在種子密鑰上進(jìn)行直接擴(kuò)展，密鑰擴(kuò)展改進(jìn)算法的過(guò)程如圖5所示，同樣由Wi-4Wi-3Wi-2Wi-1計(jì)算出Wi Wi+1Wi+2Wi+3，依然是由Wi-4Wi-1經(jīng)過(guò)復(fù)雜運(yùn)算得到Wi，由Wi-3和Wi-2異或得到Wi+1，后2個(gè)字不再采取依靠上輪子密鑰的方式獲取，而是由已生成的本輪密鑰的前2個(gè)字，Wi，Wi+1異或得到Wi+2；Wi+1，Wi+2異或得到Wi+3。

從改進(jìn)算法的實(shí)現(xiàn)過(guò)程可以看出，與原算法相比生成的子密鑰與上一輪的密鑰的相關(guān)性大大減小了，推導(dǎo)出一輪子密鑰需要猜測(cè)次數(shù)由原來(lái)的232次增加264次，即使攻擊者得到一輪子密鑰，對(duì)上輪子密鑰的推導(dǎo)也毫無(wú)意義，改進(jìn)算法已經(jīng)具有了運(yùn)算方向單一的特性。雖然這種改進(jìn)降低了每輪之間的相關(guān)性，但是每輪內(nèi)部的相關(guān)性卻增加了，只要將每輪的前2個(gè)字猜測(cè)出來(lái)，后2個(gè)字可直接獲得，這也使得算法的安全性受到一定程度上的威脅。

方法三：改進(jìn)方法二中Wi+2是借助Wi，Wi+1；Wi+3借助Wi+1，Wi+2；由此可以得出Wi+2是一個(gè)關(guān)鍵參量，只要破壞其平衡就可以降低每輪內(nèi)部的相關(guān)性。若在全部密鑰生成之后對(duì)其進(jìn)行換位操作會(huì)降低算法的即時(shí)性，影響效率，所以給每輪子密鑰的Wi+2字進(jìn)行1次循環(huán)移位[9]，如圖6所示，從生成的子密鑰的第2輪開(kāi)始將每輪密鑰的第3個(gè)字與前一輪的第3個(gè)字交換，將交換后的分組數(shù)作為最終的子密鑰。這樣可以將10輪子密鑰緊密聯(lián)系起來(lái)，即使猜測(cè)出一輪子密鑰的前2個(gè)字，也無(wú)法推導(dǎo)出第3、第4個(gè)字，若要想獲得一輪子密鑰，必須將10輪密鑰的前兩個(gè)字都猜測(cè)出來(lái)。而就一輪而言則需要窮舉2128次，這完全能與暴力破解的強(qiáng)度相媲美。

3 實(shí)驗(yàn)結(jié)果分析

用C語(yǔ)言實(shí)現(xiàn)原密鑰擴(kuò)展算法和改進(jìn)后的密鑰擴(kuò)展算法，在Keil環(huán)境中模擬12 MHz時(shí)測(cè)試三種改進(jìn)算法的運(yùn)行效率并與原算法進(jìn)行對(duì)比，其安全強(qiáng)度和效率如表2所示。

表2 改進(jìn)算法與原算法對(duì)比表

三種改進(jìn)算法都在一定程度上提高了算法本身的安全性。方法一雖然安全強(qiáng)度增強(qiáng)，但是運(yùn)算效率明顯降低；方法二在沒(méi)有影響效率的前提下很好地提高了密鑰的安全性，而其子密鑰內(nèi)部的相關(guān)性卻很高，子密鑰的安全性降低，在某種程度上也會(huì)影響加密算法的安全性；在此基礎(chǔ)上方法三采用了外輪循環(huán)移位的方法很好的解決了方法二中存在的不足，而且也保證了密鑰的安全強(qiáng)度和運(yùn)算速率，不會(huì)在原算法的基礎(chǔ)上增加任何額外的負(fù)擔(dān)，具有了更強(qiáng)的抗攻擊性，同時(shí)也很好地保留了密鑰生成過(guò)程與加密過(guò)程的同步性。

4 結(jié) 語(yǔ)

本文對(duì)AES算法的實(shí)現(xiàn)過(guò)程進(jìn)行了詳細(xì)的研究與分析，包括S盒變換、行變換、列變換、輪密鑰加和與密鑰運(yùn)算的輪換順序。并針對(duì)AES原密鑰擴(kuò)展算法的缺陷，在其基礎(chǔ)上進(jìn)行改進(jìn)，提出了三種新的密鑰擴(kuò)展算法，并對(duì)其三者進(jìn)行了對(duì)比分析。AES加密算法本身?yè)碛斜姸嗟膬?yōu)良的特性，進(jìn)一步地深入研究對(duì)現(xiàn)代信息安全的保護(hù)具有重大的意義。

參考文獻(xiàn)

[1] 郎榮玲，夏煜，戴冠中.高級(jí)加密標(biāo)準(zhǔn)（AES）算法的研究[J].小型微型計(jì)算機(jī)系統(tǒng)，2003，24（5）：905?908.

[2] 杜欽生，王美琴，曹寶香.Rijndael加密算法的密鑰擴(kuò)展算法的研究[J].信息技術(shù)與信息化，2005（5）：49?52.

[3] 吳文玲，賀也平.Mars和Rijndael的能量攻擊[J].軟件學(xué)報(bào)，2002，13（4）：532?536.

[4] 林志華.Rijndael算法的研究與分析[D].西安：西安電子科技大學(xué)，2004.

[5] 孫愛(ài)娟.基于AES加密算法的改進(jìn)及其Matlab實(shí)現(xiàn)[D].哈爾濱：哈爾濱理工大學(xué)，2009.

[6] 王瑩，何大軍.AES加密算法的改進(jìn)與實(shí)現(xiàn)[J].電腦編程技巧與維護(hù)，2010（17）：84?86.

[7] 楊小東，王毅.AES密鑰擴(kuò)展新方法[J].微電子與計(jì)算機(jī)，2012，29（1）：102?104.

[8] 劉博超.基于不可推導(dǎo)性的AES密鑰生成算法[D].長(zhǎng)春：吉林大學(xué)，2011.

[9] 多磊，李超，趙惠文.循環(huán)移位對(duì)Rijndael密碼安全性的影響[J].通信學(xué)報(bào)，2003，24（9）：153?161.