AES算法的研究與其密鑰擴展算法改進

劉艷萍，李秋慧（河北工業(yè)大學(xué)電子信息工程學(xué)院，天津　300401）

?

AES算法的研究與其密鑰擴展算法改進

劉艷萍，李秋慧
（河北工業(yè)大學(xué)電子信息工程學(xué)院，天津300401）

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

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

0　引　言

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

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

（2）即時性，加密過程的每一輪運算都離不開輪密鑰，無需等到所得的密鑰全部生成再進行加密運算，加密與密鑰擴展二者可以同時進行。

1　AES加密算法研究

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

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

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

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

1.1S盒變換

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

（1）有限域GF（28）中的乘法逆運算

若ω∈GF（28），存在ω的逆元素X，則X表示為：

其中‘00’就是其本身。

（2）GF（2）下的仿射變換

假設(shè)X在GF（28）中的元素分量表示為（X7，X6，X5，X4，X3，X2，X1，X0），變換如下：

1.2行變換

行變換（Shiftrows）的實質(zhì)就是字節(jié)的換位，它將狀態(tài)中的各行按照不同的偏移量進行循環(huán)移位，如圖2所示，狀態(tài)中第1行不做任何變換，第2行做1 B的循環(huán)左移，第3行做2 B的循環(huán)左移，第4行做3 B的循環(huán)左移。狀態(tài)是一個128 b的分組數(shù)組，行變換是將一個字節(jié)從一列移到另一列，實際字節(jié)移動的線性距離最小的也是4 B。

圖2　行變換移位圖

1.3列變換

列變換的操作對象是狀態(tài)的各列，列中的每個字節(jié)通過一種映射關(guān)系得到一個新的字節(jié)，如式（3）所示，其加、乘運算都是基于有限域GF（28），使得每列字得到充分的混淆。

在此變換中的乘法運算是有限域GF（28）的乘法，它為模GF（2）域的一個8次不可約多項式乘法，表示為，這個不可約多項式為m(x) = x8+ x4+ x3+ x + 1。若c(x) = a(x)b(x)，則c(x) = a(x) *b(x) mod m(x)。

將式（3）寫成：

S0，m′={02 }16S0，m+{03 }16S1，m+{01 }16S2，m+{01 }16S3，m

S1，m′={01 }16S0，m+{02 }16S1，m+{03 }16S2，m+{01 }16S3，m

S2，m′={01 }16S0，m+{01 }16S1，m+{02 }16S2，m+{03 }16S3，m

S3，m′={03 }16S0，m+{01 }16S1，m+{01 }16S2，m+{02 }16S3，m

例如：{02}16×{54}16={A8}16，{02}16寫成GF（28）域的多項式為x，{54}16寫成GF（28）域的多項式為x6+ x4+ x2，有：

1.4輪密鑰加

輪密鑰加運算就是每輪的狀態(tài)與對應(yīng)的128 b的輪密鑰的異或運算。由此可以看出輪密鑰擴展的復(fù)雜度直接影響著算法的安全性。下面就針對密鑰擴展算法進行詳細(xì)分析。

2　密鑰擴展算法分析與改進

2.1AES原密鑰擴展算法

AES加密算法密鑰擴展的實現(xiàn)是直接采用把種子密鑰直接擴充的方式，其是面向字節(jié)的，這樣使得算法實現(xiàn)具有較高的效率。128 b的加密要進行10輪的運算，再加上最初的種子密鑰，一次完整的加密過程需要11個分組，若以列為單位則最終的密鑰總長度為44字。密鑰擴展的過程如圖3所示，由Wi-4Wi-3Wi-2Wi-1計算出WiWi+1Wi+2Wi+3首先是Wi-1進行RotByte移位變換由W[0][i-1]W[1][i-1]W[2][i-1]W[3][i-1]變?yōu)閃[1][i-1]W[2][i-1]W[3][i-1]W[0][i-1]，變換后的數(shù)列進行一次SubWord變換，最后再與Wi-4和輪常量Rcon[]進行異或運算得到Wi，Rcon[]=（RC[i]，00，00，00），均為16進制，其中i表示輪數(shù)，RC[i]的值如表1所示。其中，SubWord變換是非線性運算，將輸入的每個字節(jié)替換成S盒中對應(yīng)的值；RotByte變換是一個移位運算，它將輸入的一個4 B的字進行了1 B的循環(huán)移位，例如輸入（A0，A1，A2，A3）經(jīng)RotByte變換得到（A1，A2，A3，A0）。

圖3　密鑰擴展算法實現(xiàn)過程

表1　輪常量RC[i]值表

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

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

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

2.2密鑰擴展算法的改進

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

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

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

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

圖4　改進方法一密鑰擴展算法實現(xiàn)過程

圖5　改進方法二密鑰擴展算法實現(xiàn)過程

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

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

圖6　改進方法三算法數(shù)據(jù)位置變換關(guān)系

3　實驗結(jié)果分析

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

表2　改進算法與原算法對比表

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

4　結(jié)　語

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

參考文獻

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

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

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

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

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

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

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

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

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

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 expan?sion 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 al?gorithm，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

中圖分類號：TN915.08?34；TP391

文獻標(biāo)識碼：A

文章編號：1004?373X（2016）10?0005?04

doi：10.16652/j.issn.1004?373x.2016.10.002

收稿日期：2015?09?25

基金項目：國家“863”計劃項目（2007aa05z23）

作者簡介：劉艷萍（1966—），女，河北秦皇島人，教授，博士。主要研究方向為DSP技術(shù)及FPGA技術(shù)。李秋慧（1990—），女，在讀碩士研究生。主要研究方向為電子信息技術(shù)與工程。