AES算法中S-box和列混合單元的優化及FPGA技術實現

由于其較高的保密級別，AES算法被用來替代DES和3-DES，以適應更為嚴苛的數據加密需要。

美國國家標準與技術局(National Institute ofStandard and Technology，NIST)于1997年1月提出發展AES(Advanced Encryption Standard)加密算法，并于同年9月12日推出AES的早期基本算法。在研究了一系列早期算法之后，Rijndael算法被確定為先進加密標準(Advanced Encryption Standard，AES)。

AES/EBU接口標準：http://www.1cnz.cn/article/87/107/2009/2009080182448.html

與此同時，市場迫切需要AES的FPGA和ASIC的硬件解決方案，因為其與用軟件實現相比更安全而且更省電。在一些應用，如：信用卡，手機，PDA等中，硬件的復雜度是影響成本和能耗的一個非常重要的因素。因此，在加密和解密中都非常需要優化AES的主要操作部分。在AES算法中，S-box是惟一的非線性單元，在加密解密，特別是字節替代和逆字節替代操作時需要分別執行S-box和逆S-box。建立一個16×16的S-box，以往通常采用查找表的方式實現，占用大量硬件資源。因此，對S-box進行優化是實現高效AES的重要步驟。

在此首先通過在S-box和逆S-box中共用一個look-up列表，簡化非線性單元的復雜度，然后通過選擇合適的即約多項式，進行域GF(28)到GF(24)的同構映射，對S-box的算法進行優化，并采用組合邏輯電路實現，使優化后的S-box在同等頻率條件下較顯著地減少了硬件資源的消耗。同時介紹了一種減小列混合(MixColumn)單元硬件復雜度的方案，可以明顯地減少列混合單元的設計面積。

1 S-box的優化設計

在AES標準算法中定義了兩個較大的列表。S-box和逆S-box。將S-box用于兩個應用：字節替代和密鑰擴展。而逆S-box則用于逆字節替代。這兩個列表是不相同的，因此必須建立兩個不同的ROM(256×8 b)，用以存儲這兩個列表。另外，在AES設計中使用平行結構，這就需要用到多個列表，這樣會使硬件過于復雜，需要對其進行優化。以下主要對S-box模塊進行結構優化。

1.1 S-box和逆S-box的組合

在一個高速128 b的AES設計中，一般需要總共20個S-box模塊和16個逆S-box模塊。其中，16個S-box模塊用于實現字節替代的功能，4個S-box用于實現密鑰擴展的功能，而16個逆S-box模塊用于實現逆字節替代功能。在這種情形下，如果字節替代和逆字節替代時使用不同的列表，就會占用大量的硬件資源。所以非常需要一種減少硬件復雜性的方法。

就如AES標準所描述的那樣，S-box的操作過程可以表示為：



因為multiplicative_inverse(乘法求逆)是一個相當復雜的方程，最常用的實現S-box的方法是運用look-up列表來由x得到y。等式(1)的逆等式如下：



因為multiplicative_inverse^-1和multiplicative_inverse是相同的，所以等式(3)可以表述為：



最后，必須找到M^-1，即矩陣M的有限域逆矩陣。由有限域逆矩陣的運算方法可知，可以計算出矩陣M的逆矩陣，命名為M’，如式(5)所示：



在式(1)和式(6)中，只使用了一個普通的look-up列表，從而將S-box和逆S-box集成，大大減少了字節替代和逆字節替代的硬件需求。圖1展示了集成的S-box／逆S-box模塊，可應用于AES的加密和解密。



1.2 S-box單元中乘法求逆電路的優化

由第1.1節可知，S-box盒的生成電路由加密仿射電路(實現out=(in+c)M^-1等式功能)，解密仿射電路(實現out=in·M+c等式功能)以及乘法求逆電路三個模塊組成。要減少組合邏輯的復雜度，需要對乘法求逆電路進行優化。下面說明求逆電路的優化過程。

S-box硬件實現時的主要部件是乘法求逆。在有限域GF(2⁸)上，乘法求逆是一種相當復雜的函數，直接在域GF(2⁸)上生成S-box盒，組合邏輯復雜度高，會使電路中邏輯電路的門數大大增加。根據有限域的性質，利用域GF(2⁸)與GF[(2⁴)²]的同構變換，把GF(2⁸)上的求逆轉化在GF[(2⁴)²]上的求逆運算，從而生成S-box單元，可以降低邏輯關系運算的復雜度，優化S-box的面積。

所采用有限域GF(2⁸)上的乘法求逆電路模塊優化過程如圖2所示。優化的乘法求逆過程可表述如下：

(1)通過線性變換T將GF(2⁸)的輸入X映射到域GF(2⁴)上的元素b，c；

(2)構建相應的域GF(2⁴)的一次多項式，定義域GF(2⁴)上的加法、乘法和求逆運算。利用域GF(2⁴)上的加法、乘法和求逆運算，得到域GF(2⁴)上元素b，c的逆元素p，q；

(3)構建線性變換T^-1，將域GF(2⁴)上的元素p，q映射到域GF(2⁸)上，得到域GF(2⁸)上的元素x的逆元素y=T^-1(p，q)。



由有限域的知識可知，復合域GF[(2⁴)²]中每個元素都可表示為系數在GF(2⁴)上的一次多項式bx+c。設定義有限域GF[(2⁴)²]的乘法的二次不可約多項式x²+Ax+B，可驗證此時GF[(2⁴)²]中的任一元素bx+c的乘逆元素是：



式中：(b²B+bcA+c²)^-1是b²B+bcA+c²在GF(2⁴)上的乘法逆元。各部分的邏輯實現過程可描述如下：

(1)有限域GF(2⁸)到復合域GF[(2⁴)²]映射。通過GF(2⁸)上的即約多項式p(x)=x²+Ax+B構造線性變換T，根據式(8)將GF(2⁸)的輸入x映射到GF(2⁴)上的元素b，c：



式中：B是GF(2⁴)上的常量元素；T是一個8×8的矩陣，矩陣的元素是0或1，T矩陣由B的取值決定；A取1，B取8；



(2)GF[(2⁴)²]到GF(2⁸)的逆映射。構造線性變換T-1，GF(2⁴)上的逆p，q映射到GF(2⁸)上的逆元素y，如式(10)所示。其中，線性變換T^-1和乘法求遞步驟(1)中的線性變換T滿足：TT^-1=E。



(3)通過域GF(2⁴)上的運算，求b，C的逆p，q。首先構建GF(2⁴)，q(x)=x⁴+x+1作為域GF(2⁴)上的本源多項式，a(x)，d(x)，e(x)∈GF(2⁴)。其中，a(x)=a₃x³+a₂x²+a₁x+a₀，d(x)=d₃x³+d₂x²+d₁x+d₀，e(x)=e₃x³+e₂x²+e₁x+e₀定義域GF(2⁴)上的加法、乘法、逆運算。

①加法為按位異或。

②乘法為多項式相乘后用q(x)取模，按公式e(x)=a(x)??d(x)mod q(x)進行運算；

③求逆根據公式公式a·a^-1=1 mod q(x)，計算GF(2⁴)上元素a的逆a^-1；

構造GF(2⁴)上的一次多項式bx+c，并利用上述GF(2⁴)上的加法、乘法和求逆運算進行運算，得到GF(2⁴)上的元素b，c的逆p，q，由式(7)可得：



p，q的計算是S-box中最復雜的邏輯運算，占用了大量的邏輯關系，關于p，q的分量元素計算是由上述算法中的分量元素代入式(13)、式(14)求得。

在這種設計方案中，求逆運算模塊中所選用的即約多項式p(x)和本源多項式q(x)不同，減低了求逆模塊的復雜度。根據理論分析，本文中用到的p(x)和q(x)不會減低AES算法的安全性。

2 列混合單元的優化設計

在列混合(MixColumn)和逆列混合(InvMixColumn)的操作中，由以下兩式定義了兩個主要操作：



將式(15)和式(16)所做的操作及結果列于表1中，由步驟1～步驟5處理的結果得到out_x，接著由out_x和w₈得到out_y。因此，在執行過程中，操作所用到的硬件資源及其所得結果可以應用到步驟9，步驟10中。如圖3所示，這種新型結構(字節-列混合模塊)僅需8個加法器和4個乘法器。與原方案相比，此設計大大減少了硬件復雜度并顯著節省了資源的消耗。



圖3中：Xt模塊(AES中的乘法器)的計算公式為：



更進一步，會發現，要建立一個全局的逆選擇列混合模塊，需要將4個字節一列混合模塊集成在一起，形成一個全新的字一列混合模塊(Word_MixColumn模塊)，如圖4所示。



這種模塊設計可以通過部分分享硬件來同時實現列混合和逆列混合的功能，實現了硬件資源的節省。

3 綜合結果

在同等頻率要求的前提下，對S-box及列混合單元進行了優化，目的是減小設計面積。優化后的算法在ModelSimSE 6.2b下進行仿真，并在Xilinx Spartan 3系列FPGA上進行綜合驗證，時鐘頻率達到166 MHz，占用3 212個基本邏輯門(一個基本邏輯門等效于兩輸入／輸出的與門)，與參考文獻[1]中方法相比節約52％。由于本文中S-box和InvS-box共用求逆電路，與文獻[2]中的優化方法相比硬件資源節約66％。



其中硬件復雜度為門級電路個數。

4? 結? 語

在AES的經典算法中S-box常常采用查找表的形式來實現，這樣會占用大量的硬件資源。本文采用S-box與逆S-box組合以及GF(2⁸)到GF(2⁴)同構變換的方法對S-box進行優化，同時，對AES中較復雜的列混合模塊進行了集成優化。優化后的方案在不降低密碼算法安全性的前提下，較好的降低了硬件復雜度，非常適用于信用卡以及其它對硬件規模要求嚴格的應用。