0 引言

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

    目前，AES算法在智能卡、移動電話、萬維網(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)中，通常會使用查表法實(shí)現(xiàn)S盒置換，從而減少運(yùn)算時(shí)間。

1.1.2 行位移

    行位移描述矩陣的行操作。在此步驟中，每一行都向左循環(huán)位移某個(gè)偏移量。在AES中(區(qū)塊大小128 bit)，第一行維持不變，第二行里的每個(gè)字節(jié)都向左循環(huán)移動一格。同理，第三行及第四行向左循環(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é)都會對輸出的4個(gè)字節(jié)造成影響。

1.1.4 輪密鑰加法

    輪密鑰加步驟，回合密鑰將會與原矩陣合并。在每次的加密循環(huán)中，都會由主密鑰產(chǎn)生一把回合密鑰，這把密鑰大小會跟原矩陣一樣，以與原矩陣中每個(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í)行速度快，但是會消耗的大量硬件資源，而且查表法無法細(xì)分為更小的過程。單純地在GF(2⁸)有限域中計(jì)算S盒置換的結(jié)果至少要使用620個(gè)門，同樣會消耗大量的硬件資源。然而，通過使用復(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)行改動，做如圖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.