0 引言

    密碼學(xué)在保證數(shù)據(jù)傳送的安全中扮演了重要角色,。1997年1月，美國國家標(biāo)準(zhǔn)及技術(shù)研究所（NIST）發(fā)起征集高級加密標(biāo)準(zhǔn)（AES）的活動(dòng),，以替換數(shù)據(jù)加密算法（DES）,。在對15個(gè)候選加密算法進(jìn)行兩輪測試和評比后,，NIST最終于2000年10月選擇Rijindael算法作為高級加密標(biāo)準(zhǔn)算法。

    目前,，AES算法在智能卡,、移動(dòng)電話、萬維網(wǎng)服務(wù)器,、ATM機(jī)以及云存儲等領(lǐng)域有著廣泛的應(yīng)用,。同軟件實(shí)現(xiàn)相比，AES算法的硬件實(shí)現(xiàn)提供了更好的物理安全性,，而且處理的速度也更快,。在大數(shù)據(jù)時(shí)代，AES已經(jīng)廣泛地用于保護(hù)云存儲數(shù)據(jù)的安全,，為了滿足數(shù)千萬用戶的同時(shí)需求,，與減少芯片面積、減小消耗相比,，提高AES算法的吞吐率就變得更為重要,。本文主要研究利用流水線結(jié)構(gòu)提高硬件上的AES加密算法的吞吐率。

    目前有3種主流的AES結(jié)構(gòu)優(yōu)化方法可以提高其在硬件上的處理速度：輪外流水線結(jié)構(gòu),，輪內(nèi)流水線結(jié)構(gòu),，循環(huán)迭代結(jié)構(gòu)。流水線結(jié)構(gòu)是在各級運(yùn)算中間插入寄存器,。內(nèi)部流水線與其相似,，是在輪運(yùn)算內(nèi)部復(fù)合域邏輯運(yùn)算中插入寄存器。

    Zhang^[1]利用等價(jià)的復(fù)合域GF(((2)²)²)²算法來實(shí)現(xiàn)一個(gè)快而緊湊的AES字節(jié)代換操作所要求的復(fù)合域乘法逆,，但其設(shè)計(jì)的輪內(nèi)各級流水線路徑長度劃分不夠最優(yōu),。Hodjat^[3]利用完全環(huán)展開的高度輪內(nèi)流水線架構(gòu)，提出兩種字節(jié)代換方案：一個(gè)是對于字節(jié)代換操作利用BlockRAMs來實(shí)現(xiàn)查找表,，另一個(gè)是利用復(fù)合域GF((2)⁴)²算法,。利用復(fù)合域算法是由Rijmen^[2]建議并且由Wolkerstorfer^[3]證明。同樣Hodjat^[4]在7級流水線設(shè)計(jì)中各級關(guān)鍵路徑劃分也不是最優(yōu),，并且循環(huán)展開結(jié)構(gòu)導(dǎo)致AES的吞吐率/面積比率比較小,。Zambreno^[5]同樣采用完全環(huán)展開流水線設(shè)計(jì)，其中最深流水線設(shè)計(jì)是完全展開3級流水線,，關(guān)鍵路徑相對比較長,。Good^[6]根據(jù)級聯(lián)的FPGA查找表(LUT)數(shù)來劃分關(guān)鍵路徑，進(jìn)行完全環(huán)展開流水線設(shè)計(jì),，雖然增加了吞吐率,，但更多的流水級劃分增加了更多的寄存器而增加了面積。本文同樣采取復(fù)合域GF((2)⁴)²算法替換查表法,，而在輪內(nèi)運(yùn)算中重新劃分展開為6級的流水線,，從而更好地平衡了吞吐率和面積的關(guān)系。

1 AES高級加密標(biāo)準(zhǔn)

1.1 加密主體

    AES算法是一種對稱加密算法,，加密服務(wù)器和解密服務(wù)器運(yùn)用相同的密鑰進(jìn)行加密和解密,，一次數(shù)據(jù)位加密長度是128 bit，128 bit的數(shù)據(jù)加密長度可以被分成一個(gè)的狀態(tài)矩陣,，其中每一個(gè)字節(jié)可以用S_ij(0<i<4,，0<j<4)表示。AES所有的算法均可視作基于對這個(gè)狀態(tài)矩陣進(jìn)行操作,。

    AES算法由主體迭代部分和密鑰擴(kuò)展算法構(gòu)成,。每一次的迭代運(yùn)算稱為一輪，而AES算法的總輪數(shù)可以為10輪,、12輪或14輪,，分別對應(yīng)128 bit、196 bit或256 bit的密鑰長度,。每一輪迭代運(yùn)算分為4個(gè)不同的步驟,，分別是S盒置換、行位移,、列混合和密鑰加法,。AES算法加密解密流程圖如圖1所示。

1.1.1 S盒置換

    S盒置換是將狀態(tài)矩陣中每一個(gè)元素視作有限域GF(2⁸)中的一個(gè)元素,，首先進(jìn)行求逆變換,，再將其在GF(2⁸)域中的逆元素進(jìn)行一次仿射變換，得到新的狀態(tài)矩陣,。由于在GF(2⁸)域中求逆運(yùn)算過于復(fù)雜,，所以在具體實(shí)現(xiàn)中，通常會(huì)使用查表法實(shí)現(xiàn)S盒置換,，從而減少運(yùn)算時(shí)間,。

1.1.2 行位移

    行位移描述矩陣的行操作。在此步驟中,，每一行都向左循環(huán)位移某個(gè)偏移量,。在AES中(區(qū)塊大小128 bit)，第一行維持不變,，第二行里的每個(gè)字節(jié)都向左循環(huán)移動(dòng)一格,。同理，第三行及第四行向左循環(huán)位移的偏移量就分別是2和3,。128 bit和192 bit的區(qū)塊在此步驟的循環(huán)位移的模式相同,。經(jīng)過行位移之后，矩陣中每一豎列,，都是由輸入矩陣中的每個(gè)不同列中的元素組成,。對于長度256 bit的區(qū)塊,，第一行仍然維持不變，第二行,、第三行,、第四行的偏移量分別是1 B、3 B,、4 B,。

1.1.3 列混合

    在列混合步驟，每一列的4個(gè)字節(jié)通過線性變換互相組合,。每一列的4個(gè)元素分別當(dāng)作1,、x、x²,、x³的系數(shù),，合并即為GF(2⁸)中的一個(gè)多項(xiàng)式，接著將此多項(xiàng)式和一個(gè)固定的多項(xiàng)式c(x)=3x³+x²+x+2在mod(x⁴)+1下相乘,。列混合函數(shù)接收4個(gè)字節(jié)的輸入,，輸出4個(gè)字節(jié)，每一個(gè)輸入的字節(jié)都會(huì)對輸出的4個(gè)字節(jié)造成影響,。

1.1.4 輪密鑰加法

    輪密鑰加步驟,，回合密鑰將會(huì)與原矩陣合并。在每次的加密循環(huán)中,，都會(huì)由主密鑰產(chǎn)生一把回合密鑰,，這把密鑰大小會(huì)跟原矩陣一樣，以與原矩陣中每個(gè)對應(yīng)的字節(jié)作異或()加法,。

1.1.5 密鑰擴(kuò)展算法

    密鑰擴(kuò)展算法主要進(jìn)行密鑰擴(kuò)展操作,，初始密鑰和擴(kuò)展后的整個(gè)密鑰表可以看作是一個(gè)字序列。在密鑰擴(kuò)展過程中完成了字旋轉(zhuǎn)和字替代兩個(gè)操作,。字旋轉(zhuǎn)操作時(shí)將字的4個(gè)字節(jié)循環(huán)右移一個(gè)單位,，如(W[0]，W[1],，W[2]W[3])經(jīng)過旋轉(zhuǎn)后得到字(W[3],，W[0]，W[1]W[2]),。

1.2 復(fù)合域計(jì)算法實(shí)現(xiàn)S盒置換

    由于S盒置換的數(shù)學(xué)過程十分復(fù)雜,，所以這個(gè)過程通常采用查表法實(shí)現(xiàn)，這樣雖然執(zhí)行速度快,，但是會(huì)消耗的大量硬件資源,，而且查表法無法細(xì)分為更小的過程。單純地在GF(2⁸)有限域中計(jì)算S盒置換的結(jié)果至少要使用620個(gè)門，同樣會(huì)消耗大量的硬件資源,。然而,，通過使用復(fù)合域算法可以顯著地降低運(yùn)算中所需要邏輯門的數(shù)量，即將GF(2⁸)中的運(yùn)算轉(zhuǎn)換到GF((2⁴)²)中,。在復(fù)合域運(yùn)算中,，實(shí)現(xiàn)將GF(2⁸)域中的元素轉(zhuǎn)換到GF((2⁴)²)域中的同構(gòu)映射可以用12個(gè)異或門實(shí)現(xiàn)，關(guān)鍵路徑上只有4個(gè)異或門,。同時(shí)，同構(gòu)映射的逆變換,，以及仿射變換都只需要19個(gè)異或門來實(shí)現(xiàn),，關(guān)鍵路徑上也只有4個(gè)異或門。在復(fù)合域GF((2⁴)²)中,，一個(gè)元素可以被表示為s_hx+s_l,，s_h，sl∈GF(2⁴),。

    使用擴(kuò)展歐幾里得算法,，s_hx+s_l的逆變換可以計(jì)算得：

    所以S盒置換可以由圖2結(jié)構(gòu)通過運(yùn)算來代替，因?yàn)橥ㄟ^復(fù)合域運(yùn)算將GF(2⁸)中的運(yùn)算轉(zhuǎn)換到GF((2⁴)²)中,，GF((2⁴)²)中的運(yùn)算可以進(jìn)一步分解到GF(2²)中,，進(jìn)而被分解至GF(2)中。在GF(2)域中一次乘法運(yùn)算就是一個(gè)簡單的邏輯與運(yùn)算,，減輕了電路的開銷,。同時(shí)這樣的結(jié)構(gòu)也為接下來內(nèi)部流水線的建立提供了可能。

2 內(nèi)外混合流水線

    流水線技術(shù)就是在邏輯電路中插入流水線寄存器,，以縮短組合邏輯路徑長度,，達(dá)到提高工作頻率、實(shí)現(xiàn)高吞吐率的目的,。由于總體的延時(shí)取決于延時(shí)最長的一級,，因此要使流水線結(jié)構(gòu)的功能最優(yōu)化，就必須使得流水線中各級的延遲時(shí)間相等,。下面分別闡述本文實(shí)現(xiàn)內(nèi)外流水線的方法,。

2.1 外部流水線結(jié)構(gòu)

    外部循環(huán)流水線結(jié)構(gòu)由循環(huán)展開結(jié)構(gòu)發(fā)展而來。具體方法是在組合電路與每一輪加密運(yùn)算對應(yīng)的部件之間都插入額外的寄存器,。該方法可以在同一時(shí)刻處理多個(gè)數(shù)據(jù)分組,，提高系統(tǒng)在單位時(shí)間內(nèi)處理數(shù)據(jù)的速度。圖3為外部10輪流水線流程圖,。

    根據(jù)AES算法結(jié)構(gòu),，容易發(fā)現(xiàn)該算法具有以下幾個(gè)顯著的特點(diǎn)：

    (1)AES算法加解密過程的核心是10次輪操作，前一輪操作的輸出是下一輪操作的輸入,。

    (2)AES算法每次輪操作需要一組子密鑰,，而一組子密鑰的產(chǎn)生僅與上一組子密鑰相關(guān),。

    根據(jù)上述特點(diǎn)可知，AES算法可以采用流水線形式實(shí)現(xiàn),，把子密鑰的生成插入到每一次輪操作的過程中,，將10次輪操作解開為一個(gè)10級的流水線。用外部循環(huán)結(jié)構(gòu)實(shí)現(xiàn)的加解密算法,，模塊的面積與流水線級數(shù)成正比,。AES加密算法展開為10級的流水線后效率提高為原來的10倍。 

2.2 內(nèi)部流水線

    內(nèi)部流水線是在內(nèi)部復(fù)合域邏輯運(yùn)算中插入寄存器,，可以使其邏輯長度更為縮短,，從而大大提高吞吐率。采用輪內(nèi)流水線技術(shù)進(jìn)行高性能AES硬件實(shí)現(xiàn)設(shè)計(jì)的關(guān)鍵就是如何利用最簡單的組合電路實(shí)現(xiàn)AES的輪單元及如何進(jìn)行流水線劃分使得關(guān)鍵路徑最短,。本文對每一輪加密過程進(jìn)行改動(dòng),，做如圖4劃分，分成6級的流水線,。

    由表1可以看出,，輪內(nèi)劃分的六部分的關(guān)鍵路徑都基本相等，所以各部分延時(shí)也基本相同,，因而將輪內(nèi)操作分成6輪是合理的,。與文獻(xiàn)[1]中將輪內(nèi)流水分成7輪相比，分成6輪雖然損失了部分速度,，但是面積利用率更高,。

3 測試方法和結(jié)果

3.1 仿真與測試

    本文采用硬件描述語言Verilog HDL代碼編寫了128 bit的AES算法，經(jīng)過外部10輪流水線改進(jìn)以后的加密算法,，改進(jìn)S盒置換步驟后的AES算法,，實(shí)現(xiàn)內(nèi)部流水線后的AES算法和內(nèi)外混合流水線的AES算法，并用Modelsim對每個(gè)算法逐個(gè)進(jìn)行仿真,。

    本文采用Altera Quarters II工具在芯片為Cyclone IV的FPGA上進(jìn)行驗(yàn)證,，所獲得的數(shù)據(jù)已在表1中給出。

3.2 性能分析

    測試所得結(jié)果與同類論文研究結(jié)果的比較見表2,。

    由表2可以看出,，本文完成的工作使得吞吐率較同類論文結(jié)果平均提升197.5%，最高提升241.3%,，取得顯著進(jìn)步,。同時(shí)，就內(nèi)外流水線而言,，使用外部10輪流水線的吞吐率較原始結(jié)果提升10倍,。同時(shí)使用內(nèi)外流水線相比只使用外部流水線而言，吞吐率增加5.5倍。這與理論基本相符,。當(dāng)然,，吞吐率的增加伴隨著面積的增加，但可以看出,，由于增加內(nèi)部流水線省去了占據(jù)面積巨大的S盒查找表,，一定程度上抑制了面積的增加。因而,，使用內(nèi)外混合流水線,，對于提升吞吐率面積比，也有積極的作用,。

4 結(jié)論

    本文提出了一種可以高效地實(shí)現(xiàn)AES算法的流水線結(jié)構(gòu),，不同于以往采用查找表的方法實(shí)現(xiàn)S盒轉(zhuǎn)換，本文采用組合邏輯電路實(shí)現(xiàn)這一步驟,。采用查找表的方法，雖然可以使處理速度得到提升,，但是占用硬件面積過大,；采用組合邏輯電路，雖然增加了電路的復(fù)雜程度,，但是可以顯著減少占用的硬件面積,，此外，通過使用復(fù)合域算法化簡域內(nèi)的轉(zhuǎn)換,，電路的復(fù)雜度也可以得到降低,。為了獲得更高的處理速度，本文在用于S盒轉(zhuǎn)換的組合邏輯電路內(nèi)部進(jìn)行了內(nèi)部流水線劃分,，最終設(shè)計(jì)了6段流水線,，進(jìn)一步提高了處理速度。

參考文獻(xiàn)

[1] Zhang Xinmiao,，Keshab K.Parhi.High-speed VLSI architectures for the AES algorithm[J].IEEE Transactions on Very Large Scale Integration(VLSI) Systms,，2004，12(9)：957-967.

[2] RIJMEN V.Efficient implementation of the rijindael S-box[J].Katholieke Universiteit Leuven,，Dept.ESAT.Belgium,，2000.

[3] WOLKERSTORFER J，OSWALD E,，LAMBERGER M.An ASIC implementation of the AES SBoxes[M].Topics in  Cryptology-CT-RSA 2002.Springer Berlin Heidelberg,，2002：67-68.

[4] HODJAT A，VERBAUWHEDE I.A 21.54 Gbits/s fully pipelined AES processor on FPGA[C].Field-Programmable Custom Computing Machines,，2004.FCCM 2004.12th Annual IEEE Symposium on.IEEE,，2004：308-309.

[5] ZAMBRENO J，NGUYEN D，CHOUDHARY A.Exploring area/delay tradeoffs in an AES FPGA implementation[M].Field Programmable Logic and Application.Springer Berlin Heidelberg,，2004：575-585.

[6] GOOD T,，BENAISSA M.Pipelined AES on FPGA with support for feedback modes(in a multi-channel environment)[J].IET Information Security，2007,，1(1)：1-10.

[7] FU Y,，HAO L，ZHANG X,，et al.Design of an extremely high performance counter mode AES reconfigurable processor[C].Embedded Software and Systems,，2005.Second International Coference on IEEE，2005：7.

[8] FAN C P,，HWANG J K.Implementations of high throughput sequential and fully pipelined AES processors on FPGA[C].Intelligent Signal Processing and Communication Systems,，2007.ISPACS 2007.International Symposium on.IEEE，2007：353-356.

[9] VANITHA M,，SAKTHIVEL R,，SUBHA S.Highly secured high throughput VLSI architecture for AES algorithm[C].Devices，Circuits and Systems(ICDCS),，2012 International Conference on IEEE,，2012：403-407.