0 引言

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

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

    目前有3種主流的AES結構優化方法可以提高其在硬件上的處理速度：輪外流水線結構，輪內流水線結構，循環迭代結構。流水線結構是在各級運算中間插入寄存器。內部流水線與其相似，是在輪運算內部復合域邏輯運算中插入寄存器。

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

1 AES高級加密標準

1.1 加密主體

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

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

1.1.1 S盒置換

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

1.1.2 行位移

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

1.1.3 列混合

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

1.1.4 輪密鑰加法

    輪密鑰加步驟，回合密鑰將會與原矩陣合并。在每次的加密循環中，都會由主密鑰產生一把回合密鑰，這把密鑰大小會跟原矩陣一樣，以與原矩陣中每個對應的字節作異或()加法。

1.1.5 密鑰擴展算法

    密鑰擴展算法主要進行密鑰擴展操作，初始密鑰和擴展后的整個密鑰表可以看作是一個字序列。在密鑰擴展過程中完成了字旋轉和字替代兩個操作。字旋轉操作時將字的4個字節循環右移一個單位，如(W[0]，W[1]，W[2]W[3])經過旋轉后得到字(W[3]，W[0]，W[1]W[2])。

1.2 復合域計算法實現S盒置換

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

    使用擴展歐幾里得算法，s_hx+s_l的逆變換可以計算得：

    所以S盒置換可以由圖2結構通過運算來代替，因為通過復合域運算將GF(2⁸)中的運算轉換到GF((2⁴)²)中，GF((2⁴)²)中的運算可以進一步分解到GF(2²)中，進而被分解至GF(2)中。在GF(2)域中一次乘法運算就是一個簡單的邏輯與運算，減輕了電路的開銷。同時這樣的結構也為接下來內部流水線的建立提供了可能。

2 內外混合流水線

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

2.1 外部流水線結構

    外部循環流水線結構由循環展開結構發展而來。具體方法是在組合電路與每一輪加密運算對應的部件之間都插入額外的寄存器。該方法可以在同一時刻處理多個數據分組，提高系統在單位時間內處理數據的速度。圖3為外部10輪流水線流程圖。

    根據AES算法結構，容易發現該算法具有以下幾個顯著的特點：

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

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

    根據上述特點可知，AES算法可以采用流水線形式實現，把子密鑰的生成插入到每一次輪操作的過程中，將10次輪操作解開為一個10級的流水線。用外部循環結構實現的加解密算法，模塊的面積與流水線級數成正比。AES加密算法展開為10級的流水線后效率提高為原來的10倍。 

2.2 內部流水線

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

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

3 測試方法和結果

3.1 仿真與測試

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

    本文采用Altera Quarters II工具在芯片為Cyclone IV的FPGA上進行驗證，所獲得的數據已在表1中給出。

3.2 性能分析

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

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

4 結論

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

參考文獻

[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.