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

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

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

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

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

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

1 AES加密算法研究

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

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

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

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

1.1 S盒變換

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

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

2.2 密鑰擴展算法的改進

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

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

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

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

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

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

3 實驗結果分析

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

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

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

4 結 語

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

參考文獻

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

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

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

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

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

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

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

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

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