基于粗粒度可重構密碼陣列的AES算法映射實現

李遠銘　嚴迎建　李　偉

(解放軍信息工程大學　河南 鄭州 450001)

0　引　言

隨著網絡空間成為與陸、海、空、天并列的第五空間，其安全問題顯得尤為重要和緊迫[1]，而密碼技術是防護網絡安全的基礎與核心手段之一。其中分組密碼算法AES[2]具有速度快、結構簡單、易于標準化等特點，被廣泛運用于諸多領域[3]。

文獻[4-5]采用了VLIW結構的密碼專用指令處理器實現AES算法，雖開發了指令級并行，但仍由指令流驅動，一個時鐘周期只可實現一個密碼操作，AES算法性能提升有限。文獻[6]采用ASIC方式實現AES算法，采用流水和并行思想，對相應結構進行優化，具有較高吞吐率和資源面積效率，但不具靈活性。文獻[7]采用了FPGA實現AES算法，利用6個并行AES算法核實現，在Altera公司的Stratix III EP3SL340F151713上的處理速度可以達到5.96 Gbit/s，但未考慮配置開銷和功耗開銷。而文獻[8]在提出的BCORE結構上映射實現了AES算法，利用陣列充足的計算資源對AES算法加速，吞吐率可達2.327 Gbit/s，但其運算單元的粒度為8 bit，對于32 bit處理位寬的AES算法加速有限。

上述AES算法實現方式都存在若干問題。同時隨著安全防護力度的不斷提升，需要定期更換子密鑰，上述文獻很少考慮到AES子密鑰實時生成問題。因此本文在提出的CGRCA上映射實現了AES子密鑰生成算法和AES加密算法。針對不同的應用場景，本文實現了兩種AES加密算法映射：面積最小和流水展開。通過分析該陣列具有的特殊單元結構，同一運算單元可以合并實現多個密碼操作，減少資源占用。同時考慮了輪運算關鍵路徑的延時差異，選擇性插入寄存器，AES加密算法吞吐率得到不同程度的提高，滿足了實際應用的需求。

1　AES算法介紹

AES算法是一種迭代型算法，分組長度固定為128 bit，密鑰長度可選擇為128、196或者256 bit，對應的輪變換次數Nr分別為10、12和14，密鑰長度取決于所需的安全等級，其算法流程如圖1所示。本文中分組長度和密鑰長度都采用128 bit。完整的AES算法由AES加/解密算法和AES子密鑰生成算法組成，其中加/解密算法結構類似，只是順序不一樣，本文僅實現加密算法。

圖1　AES算法流程圖

圖1(a)為AES加密算法流程圖，主要基于代替/置換網絡結構，完成數據的混亂與擴散。由三部分組成：初始運算、輪運算和輸出運算，一般將128 bit明文分組排成4×4的字節矩陣，稱為狀態state，然后先進行初始運算，之后進行9輪輪運算，最后的輸出運算少了列混合這一步。完整的輪運算需要經過字節替換(SubBytes)、行移位(ShiftRows)、列混合(MixColumns)和密鑰加(AddRoundKeys)。

圖1(b)為AES子密鑰生成算法流程圖。子密鑰生成算法主要由密鑰拓展和子密鑰選取兩個部分組成。其中密鑰拓展的核心為G函數，主要由字移位、S盒及與常量的異或操作構成，輸入的128 bit主密鑰K0，也是第1個子密鑰，經過密鑰拓展得到44字共11輪的子密鑰，供接下來AES加密算法使用。

2　CGRCA平臺

2.1　陣列結構

本文依托的陣列平臺為CGRCA，面向密碼算法高速處理而設計。采用了數據流加配置流驅動方式，通過配置信息的配置，完成多種分組密碼算法的實時重構，具有高效率和高并行特點。CGRCA結構圖如圖2所示。

圖2　CGRCA結構圖

整個平臺主要由4部分組成：配置子系統、控制子系統、數據交互子系統和運算子系統。

配置子系統由4個配置頁面和配置解析器組成，完成對陣列控制器和運算子系統的重構。為了實現配置信息的快速切換，采用了多配置頁面技術，配置切換時間大大縮短。通過配置解析器的解析配置，實現陣列的部分重構和實時重構。

控制子系統即陣列控制器，該陣列的控制器采用可重構設計，通過配置信息的配置，可以靈活產生所需要的控制信號，保證分組密碼算法的正確有序執行。

數據交互子系統由接口控制器和輸入/出FIFO組成，輸入FIFO存儲明文數據，輸出FIFO存儲密文數據,其中接口控制器完成數據的分配、組裝等操作。

運算子系統由8×8個可重構運算塊BPU組成，其中每2行左右8個BPU各共享1組RKB和RSB。RKB由寄存器堆搭建，完成子密鑰的存取；RSB由RAM塊搭建，完成S盒操作；BPU由路由單元CB、SB和密碼運算單元RCB組成，完成數據的路由和處理，BPU、RSB和RKB之間的連接采用了專用通道。為了適應相關分組密碼算法的大位寬處理需求，可將同一行多個BPU級聯完成64 bit、128 bit運算，如圖2的虛線所示。并設定第1行和第5行為輸入行，由接口控制器負責數據注入和運算啟動。

2.2　RCB結構

核心RCB結構如圖3(a)所示，由4類互斥的密碼模塊組成，分別為算法類AL、邏輯類TL、非線性函數類NF和置換類BP。可在配置信息重構下實現多種密碼操作，其處理位寬皆為32 bit， REG_IN為明文寄存器，僅第1行RCB具有,而REG為中間態寄存器。此外，因Input/Output Crossbar Network(INET/ONET)的存在，各密碼模塊可以任意組合連接和任意輸出。同時4類密碼模塊處理后的數據都要經過旁路寄存器Bypass Reg(BR),可選擇數據的寄存與否，具有寄存器的動態插入特點。對圖3(b)中的任意重構模塊來說，根據配置信號Sel的選擇不同，模塊內部所走路徑不同，路徑延時也不同，例子中的路徑1和2延時分別為0.9 ns和0.55 ns。對于分組密碼算法的輪運算來說，通過在合適地方插入寄存器，雖增大了時鐘周期數，但也提高了時鐘頻率，吞吐率反而可以提高。所以需要根據關鍵路徑延時差異，動態插入旁路寄存器，提升分組密碼算法的吞吐率。

圖3　RCB結構及路徑延時差異

3　AES算法映射

通過前文對AES子密鑰生成算法和加密算法的研究，結合CGRCA結構，本文在該陣列上映射實現了這兩種算法。以AES子密鑰生成算法為例簡述了映射步驟，而AES加密算法采用了兩種策略進行實現，分別為：面積最小映射和流水展開映射。同時在分析了輪運算的關鍵路徑延時差異后，充分利用RCB中的旁路寄存器，選擇性插入寄存器，最大程度提升AES加密算法實現性能。

3.1　AES子密鑰生成算法映射

AES子密鑰生成算法往往運行一次，只需生成完整的子密鑰集，并將其存入RKB即可，子密鑰生成時間相對整個數據任務包批處理時間而言，可忽略不計。所以對于AES子密鑰生成算法的映射，只需要滿足CGRCA相關限制即可，不用考慮性能等要求。

為了完成AES子密鑰生成算法需進行以下步驟：

步驟1根據算法描述得到其需要的密碼操作種類及其數量。

由第1節中的算法結構可以看出，AES子密鑰生成算法將相同的輪運算循環迭代10次后生成10個子密鑰，其中第1個子密鑰就是外部注入的主密鑰，因此只需要考慮輪運算的映射。需要1個移位操作，1個S盒操作，5個異或操作。

步驟2根據密碼操作種類確定相應的密碼模塊種類及數量。

其中移位操作由BP模塊實現，S盒操作由RSB模塊實現，異或操作由LG或AL模塊實現，所以共需1個BP模塊，1個S盒模塊，5個LG或AL模塊。

步驟3完成RCB內部映射，RCB內應盡量合并多個密碼操作，從而減少RCB數量。

外部主密鑰的注入只能存入第1行，生成的子密鑰通過專用通道存入RKB，所以128 bit的主密鑰需4個RCB，且4個RCB所包含的密碼模塊種類及數量滿足需求，完成的RCB內密碼模塊的映射連接如圖4所示。其中RCB(1,1)，RCB(1,2) 和RCB(1,3)各自只實現異或操作，RCB(1,4)需要實現2個異或操作，1個移位操作和1個S盒操作。接下來以RCB(1,4)說明，主要使用了AL、BP、TL和共享RSB實現其需要的操作，未用到NF模塊，RCB內的箭頭代表執行順序，并根據執行順序對各密碼模塊連線進行配置。

圖4　RCB內部映射

步驟4完成RCB間外部映射，根據各RCB需要的輸入輸出方向，完成外部互連網絡的連接。外部映射如圖5所示，實箭頭走的是CB和SB，而虛箭頭走的RKB專用通道。

圖5　RCB間外部映射

步驟5完成配置信息生成，根據映射完成的數據路徑和所需的控制時序，生成相應的配置信息，其中默認RCB中的旁路寄存器為不寄存模式。

3.2　AES加密算法映射

為了滿足AES加密算法不同應用場景的需求，分別在CGRCA上實現了面積最小和流水展開映射。該算法流程原本由三部分組成：初始運算、輪運算和輸出運算，如圖1(a)所示。其中初始運算僅由異或操作組成，為了減少映射資源的占用，對算法流程進行了調整，如圖6所示，僅由輪運算和輸出運算組成。

圖6　修改后的AES加密算法流程圖

首先按照3.1節提出的映射步驟完成了AES加密算法的面積最小映射，如圖7(a)所示。該方法充分利用了陣列的并行性，采用 4路并行方式實現算法映射，只需橫排4個RCB。通過操作合并，每個RCB都可完整實現輪運算和輸出運算中的密碼操作，其中輪運算中單個RCB采用如圖7(a)的RCB配置1，輸出運算中單個RCB采用如圖7(a)的RCB配置2。因此實現完整的AES加密算法需要4個RCB，其中4橫排的RCB首先在RCB配置1下完成前9輪的輪運算，最后在陣列控制器控制下切換到配置2，完成最后的輸出運算。

圖7　AES加密算法映射實現

在Synopsys公司的Design Compiler軟件綜合下得到整個陣列延時信息，同時在Verdi仿真軟件下得到了算法輪運算實際經過橫排4個RCB中各模塊的路徑延時信息，其中統計的延時信息如表1所示。

表1　RCB中輪運算延時信息

輪運算每次從REG開始，其中S盒的實現采用RAM塊實現，進入RAM塊的數據必須寄存，故完成一輪輪運算最少需要2個時鐘周期。最大時鐘頻率由RCB內部兩個寄存器間關鍵路徑決定，此時為RCB(1,4)中RSB到REG路徑，對應延時為6.294 ns，換算后的時鐘頻率為158.8 MHz。如果在BP模塊后配置BR為寄存模式，對應關鍵路徑為3.996 ns，換算為時鐘頻率為250.3 MHz，一輪輪運算增加為3個時鐘周期。對輸出運算而言，整個RCB配置除LG的功能不一樣，其余都一樣，但LG實現列混合操作遠大于異或，故最大頻率由輪運算決定，吞吐率計算公式如下：

(1)

式中：L為分組長度，F為時鐘頻率，C為時鐘周期數。BR旁路模式時，完整AES加密算法用時24時鐘周期(多的4周期由2個配置切換周期、啟動周期和結束周期)，BR寄存模式時，用時34時鐘周期，各自吞吐率分別為846.9 Mbit/s和942.3 Mbit/s。結果表明，通過利用路徑延時差異，動態插入寄存器，提高了算法吞吐率。因此需要在3.1節基礎上增加步驟6。

步驟6計算配置完成后的路徑延時信息，并根據實際情況動態插入寄存器，最大程度提升算法性能，并重新生成配置信息。

為充分利用陣列具有的大量計算資源，適應需要較高吞吐率場景的需求，AES加密算法的流水展開映射方式如圖7(b)所示。每1輪需要4個RCB，全流水展開需要40個RCB(小于CGRCA的64個RCB)，上一行RCB的數據分別對應傳輸到下一行的RCB中，前9排采用RCB配置1，最后一排采用RCB配置2。每次輪運算完成后不再寄存于當前RCB的REG，而是寄存于下一輪RCB的REG，此時會經過CB模塊，導致關鍵路徑延時增加。且整個映射過程不存在配頁面的切換開銷。輪運算的BR為旁路模式時，最大延時6.64 ns，即時鐘頻率為150.6 MHz;BR為寄存模式時，最大延時為4.342 ns，即時鐘頻率為230.3 MHz，理想情況下，數據量無限大，此時吞吐率計算公式如下：

(2)

式中：II為迭代間隔，此時各自吞吐率為9 638.4 Mbit/s和9 826.1 Mbit/s，流水展開方式的吞吐率較面積最小方式吞吐率有很大提高，同樣動態插入寄存器后，其吞吐率也有所提高。

4　性能評估

本文所有延時信息基于CMOS 55 nm工藝，陣列綜合后的面積約為15.5 mm2，通過第3節的分析可知，給定的映射步驟分別實現了AES加密算法的面積最小和流水展開映射方式。在計算了關鍵路徑延時差異后，通過動態插入寄存器，在原來基礎上提升了吞吐率，4種方式的比較如表2所示。

表2　不同方式的綜合比較

由上述4種方式可以看出，面積最小方式占據最少的面積，僅4個RCB，且時鐘頻率較高，但需要兩個配置頁面，每輪輪運算存在配置切換開銷，對性能有所影響，適合一些吞吐率要求不高場所。而流水展開方式最大程度利用了陣列充足的計算資源，吞吐率大大提高，達到9.8 Gbit/s，但是資源占據較多，也意味著較大的功耗，適合高吞吐率場景使用。此外通過利用輪運算中關鍵路徑的延時差異，動態插入寄存器，面積最小2和流水展開4相比面子最小1和流水展開2各自吞吐率提高了11.3%和1.9%。

為了客觀反映本文AES加密算法的實現性能，通過與幾種密碼處理結構及FPGA實現方式進行性能比較，結果如表3所示。其中文獻[9]中采用了流處理架構SRCCPA對分組密碼算法進行加速，取得了較好的加速效果。因不同處理結構的使用的工藝不一樣，為進行公平比較，本文借鑒了文獻[10]的工藝性能公式：Pa=Pb×Lb/La。其中Pa表示工藝換算后性能，Pb表示原工藝性能，Lb表示原工藝特征尺寸，La表示新工藝特征尺寸。

表3　與其他平臺性能對比

由表3中的比較結果可以看出，基于CGRCA實現的AES加密算法具有較高的吞吐率，相比文獻[5]SophSEC平臺有最大7.37倍的性能提高，相比文獻[7]的FPGA實現方式有最小1.73倍的性能提高。但是不如文獻[9]中SRCCPA結構實現的性能，原因在于文獻[9]采用了4倍資源復制的4×1流處理架構對AES算法進行加速，最大資源面積是13 381 704×4=53 526 816 μm2，約為53.5 mm2，此時面積開銷是本文陣列的好幾倍，通過資源面積增大的代價來換取性能提高。總的來說，本文通過采取流水展開方式實現的AES加密算法性能，可達其他平臺的1.73～7.37倍，且具有較大的靈活性，可適應多種場景的算法映射實現。

5　結　語

本文首先分析了映射平臺CGRCA具有的結構特點，尤其是RCB的特殊結構：不僅可以實現多個密碼操作，而且可以選擇性插入寄存器。然后本文映射實

現了AES子密鑰生成算法和AES加密算法。針對AES加密算法，考慮應用場景不同分別完成了面積最小和流水展開兩種映射方式。同時考慮到輪運算關鍵路徑延時差異，選擇性插入寄存器，一定程度上提高了算法實現的吞吐率。特別是流水展開方式最大程度利用陣列資源，相比別的平臺，具有很大的吞吐率優勢。未來基于該陣列可以映射實現AES算法其余變種及其他種類的密碼算法。

[1] 范愛鋒,程啟月.賽博空間面臨的威脅與挑戰[J].火力與指揮控制,2013,38(4):1-3.

[2] Fox D.Advanced Encryption Standard (AES)[J].Gateway,1999,23(3):511-576.

[3] 德門.高級加密標準(AES)算法:Rijndael的設計[M].北京:清華大學出版社,2003.

[4] 孟濤,戴紫彬.分組密碼處理器的可重構分簇式架構[J].電子與信息學報,2009,31(2):453-456.

[5] Huang W,Han J,Wang S,et al.A low-complexity heterogeneous multi-core platform for security soc[C]//Solid State Circuits Conference.IEEE,2010:1-4.

[6] Kotturi D,Yoo S M,Blizzard J.AES crypto chip utilizing high-speed parallel pipelined architecture[C]//IEEE International Symposium on Circuits and Systems.IEEE,2005:4653-4656.

[7] 李冬冬,楊軍.并行AES算法加密解密電路的高效實現[J].微電子學與計算機,2015,32(3):100-103.

[8] 郭巖松,劉雷波.一種面向分組密碼的粗粒度可重構陣列及AES算法映射[J].微電子學與計算機,2015(9):1-5.

[9] 陳韜,羅興國,李校南,等.一種基于流處理框架的可重構分簇式分組密碼處理結構模型[J].電子與信息學報,2014,36(12):3027-3034.

[10] Liu B,Baas B M.Parallel AES Encryption Engines for Many-Core Processor Arrays[J].IEEE Transactions on Computers,2013,62(3):536-547.