基于選擇空間的AES密鑰擴展算法

摘 要： 傳統AES密鑰擴展算法在已知某輪子密鑰的情況下容易遭受攻擊，為了避免這種情況的發生，通過采用單向性思路，使用輪密鑰常駐內存的工作方式以提高數據吞吐率，并提出基于選擇空間的AES密鑰擴展算法，對原有算法的加密強度進行了改善。通過FPGA仿真實現，實驗結果表明，該方法既能保證密鑰擴展算法的安全性，亦能充分結合FPGA設計高效并行的特點，提高其運行效率。

關鍵詞： AES； 密鑰擴展算法； 選擇空間； FPGA

中圖分類號： TN911?34； TP309 文獻標識碼： A 文章編號： 1004?373X（2013）20?0027?04

0 引 言

AES算法由于自身結構簡單并能夠允許128位、192位、256位可變密鑰長度，且能夠在不同的硬件上高效工作，目前已得到廣泛的應用。目前對于AES算法的研究主要集中于其自身安全性的分析[1?2]，以及對于專用硬件實現方案的改進及分析[3?4]。

傳統的AES算法實現方案在設計初期即確定了固定的密鑰擴展算法，特別是專用的硬件加密模塊[5]，為了獲得更高的數據加密吞吐能力，一般采用擴展密鑰常駐工作內存的方式，一方面減少了密鑰編排方案的計算代價，另一方面單一的加密方式避免了出錯的概率。但如果加密模塊中的密鑰擴展算法已被攻擊方獲取，或者本身結構較為簡單，一旦一輪子密鑰被攻擊方獲知，那么對方只需要通過有限的運算即可獲取全部密鑰，繼而知悉所有明文詳情。在這種情況下為保證加密通信的安全性，傳統的方法是必須通過更換密鑰以達到通信的再次安全，但在密鑰擴展算法已被敵方獲取的情況下，密鑰更換的信道只有在被確保絕對安全的情況下才是有效的。本文在研究AES算法加密過程以及密鑰擴展算法特征的基礎上，提出了利用原有子密鑰空間的基于選擇空間的密鑰擴展算法，通過這種方式間接的達到了更換密鑰的效果。針對子密鑰被敵方獲取的情況，這種設計方式可以有效的保證整個加解密過程的安全性，同時也充分的利用到了傳統設計方式中擴展密鑰常駐工作內存的特點，直接對擴展密鑰加工以產生新的輪密鑰，并通過FPGA進行仿真驗證。該算法充分利用FPGA并行高效的特點，與傳統單一FPGA?AES加密算法相比具有更高的安全性和實用性。

1 傳統 AES的密鑰擴展算法分析

AES的密鑰擴展算法又稱密鑰編排方案，由密鑰的擴展和輪密鑰選取組成。而密鑰的擴展指的是如何由現有密碼密鑰產生新一輪Expand?Key的過程，同時它必須根據以下準則[5]進行設計。

（1）效 率

①工作內存：應當能用少量的工作內存來執行密鑰編排方案。

②性能：在多種處理器上均應具有高性能。

（2）對稱消除：應當使用輪常量來消除對稱性。

（3）擴散：應當將密碼密鑰的差分有效地擴散到擴展密鑰中。

（4）非線性：應該具有足夠的非線性，以便有效的抵御差分和線性密碼分析。

針對AES的密鑰擴展算法[6]，以10輪128位初始密鑰長度為例，由于加密的過程要求一個輪密鑰用于初始密鑰加法，而且每輪都需要一個輪密鑰，因此Expanded?Key（擴展密鑰）中的全部比特數等于分組長度乘以輪數加1，即總共需要11輪密鑰。將128位初始密鑰排成一個4×4的字節矩陣，因此在這個矩陣附加40列后產生擴展密鑰空間。將第i列定義為W（i），那么前4個列即為W（0），W（1），W（2），W（3）。依據初始密鑰循環產生下一輪子密鑰，密鑰擴展規則如式（1）所示[7]：

[Wi=Wi-4⊕Wi-1， if i%4！=0Wi=Wi-4⊕TWi-1， if i%4=0] （1）

式中T（W（i-1））是W（i-1）經過循環移位，并借助S-盒進行字節替換，以達到增大其非線性關系，最終對W（4i）進行復雜化。依次擴展得到了第i輪循環的循環密鑰W（4i），W（4i+1），W（4i+2），W（4i+3）。以初始密鑰產生第1輪密鑰為例，如圖1所示，由于子密鑰的生成過程僅是對每輪首字節進行處理但這并不影響輪密鑰之間的關系，假設現在已經知道了某一輪子密鑰W（4i），W（4i+1），W（4i+2），W（4i+3），那么由圖1可知，可以通過W（4i+2），W（4i+3）知道W（4i-1），通過W（4i+1），W（4i+2）知道W（4i?2），通過W（4i），W（4i+1）知道W（4i-3），再通過W（4i-1），W（4i）知道W（4i-4），這樣便得到了前一輪的全部子密鑰。也可以通過W（4i），W（4i+3）知道W（4i+4），通過W（4i+1），W（4i+4）知道W（4i+5），通過W（4i+2），W（4i+5）知道W（4i+6），通過W（4i+3），W（4i+6）知道W（4i+7），從而得到了后一輪子密鑰。

由此可以看出，子密鑰的擴展算法一旦遭到破解，密文的安全就是非常脆弱的，而且固有硬件加密模塊主要是通過及時更換密鑰來保證密文的安全，但通過上述討論證明密鑰的更換并不能確保密文的安全。因此單純更換密鑰的方式是不可靠的。假設現在針對的是某通信數據加密，一旦密鑰遭到泄露，考慮到直接更換密鑰一方面可能引發原有更換密鑰信道遭受攻擊的可能，而一旦新的更換的密鑰被截獲通信的安全就會喪失，另一方面由于密鑰擴展算法并沒有即時改變，那么新的密鑰也將更容易遭受破解。

圖1 密鑰破解

2 基于選擇空間的密鑰擴展方法

針對傳統密鑰擴展算法[8]的不足，目前主要的改進方式主要集中于改變傳統的輪密鑰之間的強依賴關系，使得攻擊者一旦得到一輪密鑰無法通過有效途徑得到包括種子密鑰在內的全部子密鑰[9]。與此同時，新的密鑰生成算法必須滿足上文中提到的密鑰擴展算法的設計準則，這就要求密鑰的生成過程必須高效可行，且具有足夠的非線性特點。

胡亮等將密鑰擴展過程不可逆的思想稱為單向性思路[10]，在原有的密鑰擴展算法基礎上，通過利用單向性思路交換輪密鑰的順序以達到不可逆的特點。而楊小東等則通過對原有的輪密鑰進行移位異或操作，并通過隨機性函數對其進行變換[11]，這樣便增大了其破解的難度。這兩種方法雖然解決了傳統密鑰擴展算法的不足，但對于固化的專用硬件邏輯設計而言，一旦其密鑰擴展算法遭到破解，而當前的加解密模塊由于采用了固定的擴展算法，而這種擴展算法在專用硬件邏輯上是與整個加密算法邏輯高效整合的，也就產生了無法擴展的問題，必須重新進行設計以滿足安全性的要求。因此在面向專用硬件邏輯（或FPGA）設計時，密鑰擴展算法在保證單向性的前提下還要能夠滿足可擴充的特性。

本文在單向性思路的基礎上，結合FPGA設計的特點通過引入可替換的選擇空間模塊進行改進設計。同樣以10輪的AES算法為例，首先通過傳統的密鑰擴展算法生成種子密鑰之外的10輪子密鑰，假定以32位的字為單位，那么11輪子密鑰將產生11×4的子密鑰空間，選擇空間模塊設計成一個向量矩陣，如式（2）所示：

通過子密鑰空間與選擇空間的結合，將原有子密鑰空間的字順序進行改變。假設只是將第2輪子密鑰與第4輪子密鑰進行調換，通過第1節對傳統子密鑰擴展的分析知道下一輪子密鑰是通過上一輪子密鑰產生的，那么如果攻擊方獲取了一輪子密鑰，要對更改后的子密鑰進行攻擊的話，假設獲取的只是除第2輪和第4輪外的輪密鑰的話，那么必將導致至少第2輪和第4輪是錯誤的，從而保證了密文的安全。而如果一旦獲得的是第2輪或者第4輪的密鑰，那么其余9輪勢必是錯誤的，這樣破解的結果也就必然是錯誤的。同時也可在選擇空間中定義運算方式對現有子密鑰空間進行加工，這樣將使得新產生的子密鑰組在上述場景中更加難以破解。

通過改變原有以128位明文為加密的基本單位，引入單元塊的概念，定義一個N個單元分組的單元塊，而每個單元分組為128位。具體的設計思想如圖2所示。

以單元塊為加/解密的基本單位一方面相當于在原有加/解密基礎上進行了二次加密，使得密文具有更高的安全性，另一方面這種思路可用于解決相同明文加密結果相同的問題，這是由于每一個子密鑰分組均由初始子密鑰空間擴展而來，其相當于由初始密鑰擴展產生了新的11輪密鑰，而每一個子密鑰分組是由選擇空間中不同的行列與子密鑰空間進行組合產生的，這樣選擇空間不同的行列值保證了子密鑰組之間的差異性，使得單元塊中相同明文分組的加密結果不同。單從效果上來講，這種基于選擇空間的密鑰擴展算法的加密效果與不同密鑰組合的加密效果相一致。新的子密鑰分組的安全性也是得到保證的。以字為單位的情況下，新的子密鑰空間相當于原有子密鑰空間全排列（（11×4）！=2.658×1054）的一種，而單元塊化的設計又相當于在這種全排列的基礎上產生一個序列N的組合，在N=4時這種密鑰加強強度已經達到了4.991×10217，針對于這樣設計的有效攻擊方式也就只能采取窮舉的方式。同時為了使得產生的子密鑰分組能夠滿足更好的非線性要求，可以對新的子密鑰分組采取移位或異或等簡單操作的非線性化處理，在增強其安全性的前提下并沒有增加多少時間消耗，滿足了其本身的高效性。

將已有的子密鑰空間保存于FPGA的RAM中，選擇空間模塊采用LUT（查找表）的方式，在統一時鐘的作用下，每一次時鐘的上升沿便產生了新的輪密鑰，這種硬連接的方式使得新的輪密鑰的產生與上一輪加密過程得以并行執行[12]，同時由于單元塊中各分組明文的加/解密過程相互獨立，這樣可以通過使用流水線的方式提高數據的吞吐能力。選擇空間的模塊化設計使得可以通過預留數據的更新端口，這樣只需要更新選擇空間模塊中向量矩陣的數據便可以產生新的選擇空間，由于AES加/解密算法整體采用模塊化的設計方法，如圖3所示，各模塊之間只是通過互聯的方式整合在一起，單一模塊的數據更新并不會影響到其他模塊，這樣確保了硬件加解密邏輯的可擴充性，同時新的選擇空間的產生保證了子密鑰分組的差異化，從而增強信息的安全性。

3 FPGA實現與仿真

綜合考慮資源與速度等問題，算法的設計采用統一時鐘下的模塊互聯，利用狀態機的方式進行設計實現，所有的算法模塊均采用Verilog HDL實現，在ISE 12.4下進行綜合設計，在Isim下完成了功能仿真和時序仿真。加解密模塊所處理的基本單位為128 b數據，通過引入num控制信號，使得選擇空間模塊產生不同的子密鑰分組，圖4闡述了num控制信號在kld使能信號作用下產生的有效選擇空間序列，對于原始的明文數據以128 b為加密單位，每個單元塊為128×4 b，單元塊內各明文分組數值相同。圖5給出了其加解密統一進行下的仿真結果，結果表明單元塊內每個明文分組最終的加密結果均不相同，但解密后的結果均與原明文分組一致，驗證了基于選擇空間密鑰擴展算法的正確性以及FPGA設計的可行性。同時在多個模塊之間設置全局的使能信號和復位信號進行控制，當使能或者復位信號禁止時，整個系統進入休眠狀態，這樣的設計方式使得控制簡單，系統對環境的適應度增強，也確保了整個設計的穩定與一致。

對于Xilinx Virtex 5系列的xc5vfx70t?1ff1136 FPGA，整個系統模塊占用資源可以從表1中看出，其占用的資源并未達到FPGA瓶頸，且資源占用率較低，而Virtex 5系列的FPGA在整個Xilinx的FPGA產品中目前只處于中低端，因此這種設計方案在FPGA上是完全可行的。

4 結 語

基于單向性思路提出的選擇空間下的AES加解密的設計，增強了加密的強度，同時達到了單一密鑰下多個密鑰加密效果。通過在統一時鐘觸發下并行化設計，有效的減少了資源的利用率，并通過仿真驗證了方案的可行性，而且這種方案可以設計成專用芯片，在民用通信、軍事通信、文件加密等領域均有著廣泛的應用前景。

參考文獻

[1] 毛明.分組迭代密碼函數的安全性研究[D].成都：電子科技大學，2012.

[2] 王薇.分組密碼CLEFIA與基于四圈AES消息認證碼的安全性分析[D].濟南：山東大學，2009.

[3] 韓津生，林家駿，周文錦，等.基于FPGA的AES核設計[J].計算機工程與科學，2013，35（3）：80?84.

[4] 寧乃東，王巖國.基于FPGA的Rijndael可配置密鑰系統優化設計[J].宇航計測技術，2008，28（6）：35?38.

[5] 魯艷蓉.分組密碼算法的設計與分析研究[D].西安：西安電子科技大學，2011.

[6] 胡亮，閆智佳，初劍峰，等.IDEA子密鑰擴展算法的分析與改進[J].吉林大學學報：工學版，2012，42（6）：25?32.

[7] 弟宇鳴，陳榮樺，左光霞.基于AES算法的加密模塊設計[J].電子設計工程，2013，21（2）：53?55.

[8] 曹華平，羅守山，溫巧燕.AES算法輪密鑰與種子密鑰之間的關系研究[J].北京郵電大學學報，2002，25（4）：47?50.

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

[10] 胡亮，袁巍，于孟濤，等.單向性策略與AES密鑰生成算法的改進[J].吉林大學學報：工學版，2009，39（1）：137?142.

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

[12] 師攀攀.基于多核的AES算法的并行優化與實現[D].鄭州：鄭州大學，2012.