美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)局(National Institute of Standard and Technology,,NIST)于1997年1月提出發(fā)展AES" title="AES">AES(Advanced Encryption Standard)加密算法,并于同年9月12日推出AES的早期基本算法,。在研究了一系列早期算法之后,,Rijndael算法被確定為先進(jìn)加密標(biāo)準(zhǔn)(Advanced Encryption Standard,AES),。由于其較高的保密級(jí)別,,AES算法被用來(lái)替代DES和3-DES,以適應(yīng)更為嚴(yán)苛的數(shù)據(jù)加密需要,。
與此同時(shí),,市場(chǎng)迫切需要AES的FPGA" title="FPGA">FPGA和ASIC的硬件解決方案,因?yàn)槠渑c用軟件實(shí)現(xiàn)相比更安全而且更省電,。在一些應(yīng)用,,如:信用卡,,手機(jī),PDA等中,,硬件的復(fù)雜度是影響成本和能耗的一個(gè)非常重要的因素,。因此,在加密和解密中都非常需要優(yōu)化AES的主要操作部分,。在AES算法中,,S-box是惟一的非線性單元,在加密解密,,特別是字節(jié)替代和逆字節(jié)替代操作時(shí)需要分別執(zhí)行S-box和逆S-box,。建立一個(gè)16×16的S-box,以往通常采用查找表的方式實(shí)現(xiàn),,占用大量硬件資源,。因此,對(duì)S-box進(jìn)行優(yōu)化是實(shí)現(xiàn)高效AES的重要步驟,。
在此首先通過(guò)在S-box和逆S-box中共用一個(gè)look-up列表,,簡(jiǎn)化非線性單元的復(fù)雜度,然后通過(guò)選擇合適的即約多項(xiàng)式,,進(jìn)行域GF(28)到GF(24)的同構(gòu)映射,,對(duì)S-box的算法進(jìn)行優(yōu)化,,并采用組合邏輯電路實(shí)現(xiàn),,使優(yōu)化后的S-box在同等頻率條件下較顯著地減少了硬件資源的消耗。同時(shí)介紹了一種減小列混合(MixColumn)單元硬件復(fù)雜度的方案,,可以明顯地減少列混合單元的設(shè)計(jì)面積,。
1 S-box的優(yōu)化設(shè)計(jì)
在AES標(biāo)準(zhǔn)算法中定義了兩個(gè)較大的列表。S-box和逆S-box,。將S-box用于兩個(gè)應(yīng)用:字節(jié)替代和密鑰擴(kuò)展,。而逆S-box則用于逆字節(jié)替代。這兩個(gè)列表是不相同的,,因此必須建立兩個(gè)不同的ROM(256×8 b),,用以存儲(chǔ)這兩個(gè)列表。另外,,在AES設(shè)計(jì)中使用平行結(jié)構(gòu),,這就需要用到多個(gè)列表,這樣會(huì)使硬件過(guò)于復(fù)雜,,需要對(duì)其進(jìn)行優(yōu)化,。以下主要對(duì)S-box模塊進(jìn)行結(jié)構(gòu)優(yōu)化。
1.1 S-box和逆S-box的組合
在一個(gè)高速128 b的AES設(shè)計(jì)中,,一般需要總共20個(gè)S-box模塊和16個(gè)逆S-box模塊,。其中,,16個(gè)S-box模塊用于實(shí)現(xiàn)字節(jié)替代的功能,4個(gè)S-box用于實(shí)現(xiàn)密鑰擴(kuò)展的功能,,而16個(gè)逆S-box模塊用于實(shí)現(xiàn)逆字節(jié)替代功能,。在這種情形下,如果字節(jié)替代和逆字節(jié)替代時(shí)使用不同的列表,,就會(huì)占用大量的硬件資源,。所以非常需要一種減少硬件復(fù)雜性的方法。
就如AES標(biāo)準(zhǔn)所描述的那樣,,S-box的操作過(guò)程可以表示為:
因?yàn)閙ultiplicative_inverse(乘法求逆)是一個(gè)相當(dāng)復(fù)雜的方程,,最常用的實(shí)現(xiàn)S-box的方法是運(yùn)用look-up列表來(lái)由x得到y(tǒng)。等式(1)的逆等式如下:
因?yàn)閙ultiplicative_inverse-1和multiplicative_inverse是相同的,,所以等式(3)可以表述為:
關(guān)鍵字:FPGA AES算法 S-box
最后,,必須找到M-1,即矩陣M的有限域逆矩陣,。由有限域逆矩陣的運(yùn)算方法可知,,可以計(jì)算出矩陣M的逆矩陣,命名為M’,,如式(5)所示:
在式(1)和式(6)中,,只使用了一個(gè)普通的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盒的生成電路由加密仿射電路(實(shí)現(xiàn)out=(in+c)M-1等式功能),解密仿射電路(實(shí)現(xiàn)out=in·M+c等式功能)以及乘法求逆電路三個(gè)模塊組成,。要減少組合邏輯的復(fù)雜度,,需要對(duì)乘法求逆電路進(jìn)行優(yōu)化。下面說(shuō)明求逆電路的優(yōu)化過(guò)程,。
S-box硬件實(shí)現(xiàn)時(shí)的主要部件是乘法求逆,。在有限域GF(28)上,乘法求逆是一種相當(dāng)復(fù)雜的函數(shù),,直接在域GF(28)上生成S-box盒,,組合邏輯復(fù)雜度高,會(huì)使電路中邏輯電路的門(mén)數(shù)大大增加,。根據(jù)有限域的性質(zhì),,利用域GF(28)與GF[(24)2]的同構(gòu)變換,把GF(28)上的求逆轉(zhuǎn)化在GF[(24)2]上的求逆運(yùn)算,從而生成S-box單元,,可以降低邏輯關(guān)系運(yùn)算的復(fù)雜度,,優(yōu)化S-box的面積。
所采用有限域GF(28)上的乘法求逆電路模塊優(yōu)化過(guò)程如圖2所示,。優(yōu)化的乘法求逆過(guò)程可表述如下:
(1)通過(guò)線性變換T將GF(28)的輸入X映射到域GF(24)上的元素b,,c;
(2)構(gòu)建相應(yīng)的域GF(24)的一次多項(xiàng)式,,定義域GF(24)上的加法,、乘法和求逆運(yùn)算。利用域GF(24)上的加法,、乘法和求逆運(yùn)算,,得到域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),。
關(guān)鍵字:FPGA AES算法 S-box
由有限域的知識(shí)可知,,復(fù)合域GF[(24)2]中每個(gè)元素都可表示為系數(shù)在GF(24)上的一次多項(xiàng)式bx+c。設(shè)定義有限域GF[(24)2]的乘法的二次不可約多項(xiàng)式x2+Ax+B,,可驗(yàn)證此時(shí)GF[(24)2]中的任一元素bx+c的乘逆元素是:
式中:(b2B+bcA+c2)-1是b2B+bcA+c2在GF(24)上的乘法逆元,。各部分的邏輯實(shí)現(xiàn)過(guò)程可描述如下:
(1)有限域GF(28)到復(fù)合域GF[(24)2]映射。通過(guò)GF(28)上的即約多項(xiàng)式p(x)=x2+Ax+B構(gòu)造線性變換T,,根據(jù)式(8)將GF(28)的輸入x映射到GF(24)上的元素b,,c:
式中:B是GF(24)上的常量元素;T是一個(gè)8×8的矩陣,,矩陣的元素是0或1,T矩陣由B的取值決定,;A取1,,B取8;
(2)GF[(24)2]到GF(28)的逆映射,。構(gòu)造線性變換T-1,,GF(24)上的逆p,q映射到GF(28)上的逆元素y,,如式(10)所示,。其中,線性變換T-1和乘法求遞步驟(1)中的線性變換T滿足:TT-1=E。
(3)通過(guò)域GF(24)上的運(yùn)算,,求b,,C的逆p,q,。首先構(gòu)建GF(24),,q(x)=x4+x+1作為域GF(24)上的本源多項(xiàng)式,a(x),,d(x),,e(x)∈GF(24)。其中,,a(x)=a3x3+a2x2+a1x+a0,,d(x)=d3x3+d2x2+d1x+d0,e(x)=e3x3+e2x2+e1x+e0定義域GF(24)上的加法,、乘法,、逆運(yùn)算。
?、偌臃榘次划惢?。
②乘法為多項(xiàng)式相乘后用q(x)取模,,按公式e(x)=a(x)œ⊗d(x)mod q(x)進(jìn)行運(yùn)算,;
③求逆根據(jù)公式公式a·a-1=1 mod q(x),,計(jì)算GF(24)上元素a的逆a-1,;
構(gòu)造GF(24)上的一次多項(xiàng)式bx+c,并利用上述GF(24)上的加法,、乘法和求逆運(yùn)算進(jìn)行運(yùn)算,,得到GF(24)上的元素b,c的逆p,,q,,由式(7)可得:
p,q的計(jì)算是S-box中最復(fù)雜的邏輯運(yùn)算,,占用了大量的邏輯關(guān)系,,關(guān)于p,q的分量元素計(jì)算是由上述算法中的分量元素代入式(13),、式(14)求得,。
在這種設(shè)計(jì)方案中,求逆運(yùn)算模塊中所選用的即約多項(xiàng)式p(x)和本源多項(xiàng)式q(x)不同,,減低了求逆模塊的復(fù)雜度,。根據(jù)理論分析,,本文中用到的p(x)和q(x)不會(huì)減低AES算法的安全性。
關(guān)鍵字:FPGA AES算法 S-box
2 列混合單元的優(yōu)化設(shè)計(jì)
在列混合(MixColumn)和逆列混合(InvMixColumn)的操作中,,由以下兩式定義了兩個(gè)主要操作:
將式(15)和式(16)所做的操作及結(jié)果列于表1中,,由步驟1~步驟5處理的結(jié)果得到outx,接著由outx和w8得到outy,。因此,,在執(zhí)行過(guò)程中,操作所用到的硬件資源及其所得結(jié)果可以應(yīng)用到步驟9,,步驟10中,。如圖3所示,這種新型結(jié)構(gòu)(字節(jié)-列混合模塊)僅需8個(gè)加法器和4個(gè)乘法器,。與原方案相比,,此設(shè)計(jì)大大減少了硬件復(fù)雜度并顯著節(jié)省了資源的消耗。
圖3中:Xt模塊(AES中的乘法器)的計(jì)算公式為:
更進(jìn)一步,,會(huì)發(fā)現(xiàn),,要建立一個(gè)全局的逆選擇列混合模塊,需要將4個(gè)字節(jié)一列混合模塊集成在一起,,形成一個(gè)全新的字一列混合模塊(Word_MixColumn模塊),,如圖4所示。
這種模塊設(shè)計(jì)可以通過(guò)部分分享硬件來(lái)同時(shí)實(shí)現(xiàn)列混合和逆列混合的功能,,實(shí)現(xiàn)了硬件資源的節(jié)省,。
關(guān)鍵字:FPGA AES算法 S-box
3 綜合結(jié)果
在同等頻率要求的前提下,對(duì)S-box及列混合單元進(jìn)行了優(yōu)化,,目的是減小設(shè)計(jì)面積,。優(yōu)化后的算法在ModelSimSE 6.2b下進(jìn)行仿真,并在Xilinx Spartan 3系列FPGA上進(jìn)行綜合驗(yàn)證,,時(shí)鐘頻率達(dá)到166 MHz,,占用3 212個(gè)基本邏輯門(mén)(一個(gè)基本邏輯門(mén)等效于兩輸入/輸出的與門(mén)),與參考文獻(xiàn)[1]中方法相比節(jié)約52%,。由于本文中S-box和InvS-box共用求逆電路,,與文獻(xiàn)[2]中的優(yōu)化方法相比硬件資源節(jié)約66%。
其中硬件復(fù)雜度為門(mén)級(jí)電路個(gè)數(shù),。
4 結(jié) 語(yǔ)
在AES的經(jīng)典算法中S-box常常采用查找表的形式來(lái)實(shí)現(xiàn),,這樣會(huì)占用大量的硬件資源。本文采用S-box與逆S-box組合以及GF(28)到GF(24)同構(gòu)變換的方法對(duì)S-box進(jìn)行優(yōu)化,,同時(shí),對(duì)AES中較復(fù)雜的列混合模塊進(jìn)行了集成優(yōu)化,。優(yōu)化后的方案在不降低密碼算法安全性的前提下,,較好的降低了硬件復(fù)雜度,非常適用于信用卡以及其它對(duì)硬件規(guī)模要求嚴(yán)格的應(yīng)用。