AES算法中S-box和列混合單元的優(yōu)化及FPGA技術(shù)實現(xiàn)
在AES標(biāo)準(zhǔn)算法中定義了兩個較大的列表。S-box和逆S-box。將S-box用于兩個應(yīng)用:字節(jié)替代和密鑰擴(kuò)展。而逆S-box則用于逆字節(jié)替代。這兩個列表是不相同的,因此必須建立兩個不同的ROM(256×8 b),用以存儲這兩個列表。另外,在AES設(shè)計中使用平行結(jié)構(gòu),這就需要用到多個列表,這樣會使硬件過于復(fù)雜,需要對其進(jìn)行優(yōu)化。以下主要對S-box模塊進(jìn)行結(jié)構(gòu)優(yōu)化。
1.1 S-box和逆S-box的組合
在一個高速128 b的AES設(shè)計中,一般需要總共20個S-box模塊和16個逆S-box模塊。其中,16個S-box模塊用于實現(xiàn)字節(jié)替代的功能,4個S-box用于實現(xiàn)密鑰擴(kuò)展的功能,而16個逆S-box模塊用于實現(xiàn)逆字節(jié)替代功能。在這種情形下,如果字節(jié)替代和逆字節(jié)替代時使用不同的列表,就會占用大量的硬件資源。所以非常需要一種減少硬件復(fù)雜性的方法。
就如AES標(biāo)準(zhǔn)所描述的那樣,S-box的操作過程可以表示為:
因為multiplicative_inverse(乘法求逆)是一個相當(dāng)復(fù)雜的方程,最常用的實現(xiàn)S-box的方法是運用look-up列表來由x得到y(tǒng)。等式(1)的逆等式如下:
因為multiplicative_inverse-1和multiplicative_inverse是相同的,所以等式(3)可以表述為:
最后,必須找到M-1,即矩陣M的有限域逆矩陣。由有限域逆矩陣的運算方法可知,可以計算出矩陣M的逆矩陣,命名為M’,如式(5)所示:
在式(1)和式(6)中,只使用了一個普通的look-up列表,從而將S-box和逆S-box集成,大大減少了字節(jié)替代和逆字節(jié)替代的硬件需求。圖1展示了集成的S-box/逆S-box模塊,可應(yīng)用于AES的加密和解密。
1.2 S-box單元中乘法求逆電路的優(yōu)化
由第1.1節(jié)可知,S-box盒的生成電路由加密仿射電路(實現(xiàn)out=(in+c)M-1等式功能),解密仿射電路(實現(xiàn)out=in?M+c等式功能)以及乘法求逆電路三個模塊組成。要減少組合邏輯的復(fù)雜度,需要對乘法求逆電路進(jìn)行優(yōu)化。下面說明求逆電路的優(yōu)化過程。
S-box硬件實現(xiàn)時的主要部件是乘法求逆。在有限域GF(28)上,乘法求逆是一種相當(dāng)復(fù)雜的函數(shù),直接在域GF(28)上生成S-box盒,組合邏輯復(fù)雜度高,會使電路中邏輯電路的門數(shù)大大增加。根據(jù)有限域的性質(zhì),利用域GF(28)與GF[(24)2]的同構(gòu)變換,把GF(28)上的求逆轉(zhuǎn)化在GF[(24)2]上的求逆運算,從而生成S-box單元,可以降低邏輯關(guān)系運算的復(fù)雜度,優(yōu)化S-box的面積。
所采用有限域GF(28)上的乘法求逆電路模塊優(yōu)化過程如圖2所示。優(yōu)化的乘法求逆過程可表述如下:
(1)通過線性變換T將GF(28)的輸入X映射到域GF(24)上的元素b,c;
(2)構(gòu)建相應(yīng)的域GF(24)的一次多項式,定義域GF(24)上的加法、乘法和求逆運算。利用域GF(24)上的加法、乘法和求逆運算,得到域GF(24)上元素b,c的逆元素p,q;
(3)構(gòu)建線性變換T-1,將域GF(24)上的元素p,q映射到域GF(28)上,得到域GF(28)上的元素x的逆元素y=T-1(p,q)。
由有限域的知識可知,復(fù)合域GF[(24)2]中每個元素都可表示為系數(shù)在GF(24)上的一次多項式bx+c。設(shè)定義有限域GF[(24)2]的乘法的二次不可約多項式x2+Ax+B,可驗證此時GF[(24)2]中的任一元素bx+c的乘逆元素是:
式中:(b2B+bcA+c2)-1是b2B+bcA+c2在GF(24)上的乘法逆元。各部分的邏輯實現(xiàn)過程可描述如下:
(1)有限域GF(28)到復(fù)合域GF[(24)2]映射。通過GF(28)上的即約多項式p(x)=x2+Ax+B構(gòu)造線性變換T,根據(jù)式(8)將GF(28)的輸入x映射到GF(24)上的元素b,c:
式中:B是GF(24)上的常量元素;T是一個8×8的矩陣,矩陣的元素是0或1,T矩陣由B的取值決定;A取1,B取8;
評論