一種基于流處理框架的可重構分簇式分組密碼處理結構模型

陳 韜 羅興國 李校南 李 偉

?

一種基于流處理框架的可重構分簇式分組密碼處理結構模型

陳 韜*羅興國 李校南 李 偉

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

分組密碼；可重構；陣列結構；分級互連；流處理

1 引言

2 可重構密碼處理模型的研究與設計

2.1 可重構分組密碼處理架構設計

可重構密碼處理架構S-RCCPA的整體結構如圖1(a)所示，其核心是分組密碼可重構分簇式處理陣列，其他組成部分包括完成輸入、輸出流控制的流控制器、完成RCCPA陣列控制的微內核控制器與主機接口、基于NoC的可擴展數據網絡接口等。

可重構分簇式處理陣列作為S-RCCPA的核心模塊，由可重構密碼處理塊(Reconfigurable Cipher processing Block, RCB)、可配置互連模塊(Reconfiguration inter-Connection Module, RCM)、存儲模塊(Memory Access Module, MAM)和配置模塊(Configuration Module, CM)等部分共同構成；結構類似二維陣列，在橫向和縱向上組織RCB，同一行上的各RCB可以并行執行，但同一行上的RCB之間除控制連接外，沒有數據交互通路；在列方向上支持流水線操作，第行的RCB()通過RCM()將運算結果傳送到第+1行的RCB()中，最后一行RCB()的運算輸出可以反饋到第1行RCB()的輸入上。

S-RCCPA核心架構采用層次化方式組織其處理單元，以降低互連網絡和處理單元的設計復雜性，如圖1(b)所示，每個RCB包含4個可重構密碼處理簇(Reconfigurable Cipher processing Cluster, RCC)；每個RCC包含針對分組密碼設計的9個32 bit可重構密碼處理單元(Reconfigurable Cipher processing Unit, RCU)，各RCU在RCC中的組織形式如圖1(c)所示，其中32 bit的RCU共7種：S盒替代、移位、GF(2)上的矩陣乘法、算術乘法、算術模加/減、三輸入邏輯運算、二輸入邏輯等單元，另外針對分組密碼運算中出現的128 bit移位和置換操作，專門設置了兩個128 bit位寬的比特置換和基于比特置換的長移位單元；4個RCC組成的RCB可以完成128 bit的密碼操作，S-RCCPA架構中同一行的多個RCB可以并行處理多個密碼分組；對于128 bit的置換和移位單元，將其輸入、輸出分成4組32 bit信號接入到相鄰4個RCC(同一RCB所包含的4個RCC)對應的互連網絡上，使兩個單元在邏輯上為同一RCB的4個RCC所共有。

S-RCCPA架構采用靜態與動態相結合的配置方式，配置模塊CM用于完成S-RCCPA架構的靜態配置與動態控制。S-RCCPA架構中RCU的功能配置采用靜態重構的方式完成，如：S盒替代、比特置換、有限域乘法等單元的功能配置，均采用靜態重構在S-RCCPA架構執行密碼處理任務前完成。動態重構采用基于多重上下文的配置機制實現，主要完成S-RCCPA架構中互連網絡、RCU功能選擇以及數據輸入輸出的控制。靈活的配置方式使S-RCCPA架構能夠實時組織密碼處理路徑、以虛擬流水線的方式完成密碼處理任務。

2.2 分級互連結構研究與設計

S-RCCPA架構中的RCB可以滿足一個或多個分組的處理需求，RCB中的每個RCC可以滿足大多數分組密碼中單個子塊的處理需求，因此S-RCCPA架構中只有同一列的相鄰兩個RCB之間，可以通過RCM進行數據交互，不同列的RCB之間不存在數據交互通路。結合分組密碼子塊間數據交互少、子塊內密碼操作前后連接關系復雜多變的特點，設計了基于Crossbar的分級可配置互連結構。

第+1行RCB()的RCC()中各RCU的數據來源分為3類：第行RCB()的RCC()內各RCU的運算結果，由于每個RCC中包含9種類型的RCU，該類型的輸入共有9個；第行RCB()的RCC()通過Level-2輸入的運算結果，該類型的輸入共有6個；輸入數據，主要指從第+1行數據存儲器中讀取的數據。為方便RCC的處理結果輸出到數據存儲器、子密鑰存儲器或輸出緩沖器中，Level-1互連結構專門設計了數據輸出端口，其數據來源與各RCU的數據來源相同，眾多的數據來源保證了運算結果輸出的靈活性。尤其是在子密鑰生成過程中，上述輸出結構可以實現外部輸入的密碼常數、上級RCC的運算結果、上級其它RCC的處理結果，靈活寫入到當前RCC所對應的子密鑰存儲器中，提高了子密鑰數據的使用靈活性。Level-1的全Crossbar互連結構，適應了分組密碼子塊內密碼操作前后連接關系復雜多變的特性，滿足了密碼處理靈活性的需求。

圖1 S-RCCPA整體結構

圖2 Level-1的互連結構

每個RCC均采用圖3所示的結構將結果輸出到下級其它RCC中，為保證下一行RCC運行時的時序匹配，接入到下級其它RCC中的輸出數據不再進行寄存。Level-2部分Crossbar互連結構，適應了分組密碼子塊間數據交互較少的特性，為子塊間進行數據通信提供了一定的交互帶寬，使每列的RCB能夠通過子塊間的數據交互，靈活組織成1個128 bit, 2個64 bit或4個32 bit的流水線。

2.3 分離-分布式存儲結構設計

為方便臨時數據和子密鑰數據的靈活存取，針對S-RCCPA架構特點，設計了分布式的存儲結構，其整體結構如圖4所示。S-RCCPA架構為每個RCB設置了4個數據存儲器和4個密鑰存儲器，分別對應RCB模塊中的4個RCC，每個數據存儲器和子密鑰存儲器均包含1個讀端口和1個寫端口。如圖4(a)所示，第行RCB()中的各RCC可以通過Level-1總線中為各RCC設置的輸入數據端口，直接讀取對應數據存儲器的內容。通過Level-2的總線可實現RCC對其它數據存儲器的間接讀取。4個密鑰存儲器KDM-A(Key Data Memory A), KDM-B, KDM-C以及KDM-D，分別將密鑰輸出端口接入到RCC(1), RCC(2), RCC(3), RCC(4)中各RCU的密鑰輸入端口上，實現了RCC從對應子密鑰存儲器中讀取子密鑰數據。

圖3 Level-2的互連結構

圖4 分離-分布式存儲器結構

3 S-RCCPA模型處理模式研究

分組密碼具有深度流水特性，非常適合流水執行，可以使用單向流水結構加速密碼處理。S-RCCPA架構具有靈活的互連結構、豐富的密碼運算資源，可以充分開發分組密碼的流水特性。

3.1 S-RCCPA模型可變位寬流水處理模式

通過配置RCM可以使同一列的RCB組成密碼處理流水線，加速分組密碼任務的處理。分組密碼存在分組間以及分組內兩個方面的并行性，S-RCCPA架構可以充分開發分組密碼兩個方面的并行性，S-RCCPA架構中的RCB可以并行處理同一分組間的多個子塊，同一行上的多個RCB可以并行處理多個密碼分組。

對于分組長度為128 bit，需要4個RCC同時參與運算的分組密碼算法，如：AES, Twofish, SMS4等算法，規模為×1的S-RCCPA架構可以將同一列上的RCB組織成1個128 bit的流水線，完成密碼分組的處理如圖5所示，4個RCC中的RCU在橫向上可以完成1個128 bit的密碼操作，最后一行RCB的處理結果可以反饋到第1行的RCB中。由于每列相鄰兩個RCB之間采用基于Crossbar的分級互連結構，提供了較大的互連帶寬，雖然只包含行的互連結構和行的處理單元，但是可以提供遠大于2級的流水線深度。只要RCB的同一RCC中用于密碼處理的RCU不存在沖突、RCM滿足帶寬需求，同一時刻可以有多個RCU進行密碼運算。理想情況下，當分組密碼輪函數的步操作均使用不同的RCU時，每個RCC中個不同類型的RCU可以同時工作，結構的資源利用率和流水深度得到有效提高。

對于分組長度為64 bit，需要2個RCC同時參與運算的分組密碼算法，如：DES, Skipiack, SAFER, LOKI91等算法，規模為×1的S-RCCPA架構可以將同一列RCB中的RCC組成2個64 bit的流水線并行處理；類似地，對于只需要1個RCC參與運算的分組密碼算法，如GOST算法，規模為×1的S-RCCPA架構可以將同一列RCB中的RCC組成4個32 bit位寬的密碼處理流水線，用于處理相同或不同的密碼算法；對于規模為×的S-RCCPA架構，其流水線的組織形式更加靈活，可以同時組織成若干條128 bit位寬，64 bit位寬以及32 bit位寬的流水線，同樣即使組織成相同位寬的流水線，流水線完成的密碼任務也可以不同。這種靈活的流水線處理結構，使S-RCCPA架構能夠同時完成多個相同或不同分組密碼的處理。

圖5 S-RCCPA架構128 bit位寬的流水處理結構

3.2 S-RCCPA虛擬流水處理模式

若S-RCCPA架構規模不能支持以流水方式實現一個輪函數或分組密碼時，需要將復雜輪函數或密碼算法分多次映射到S-RCCPA架構上，從而影響S-RCCPA架構的處理性能[11]。為減小或隱藏多次映射帶來的配置時間消耗，本文采用動態配置信息自動切換的方式，在有限的硬件資源上實現多級流水，通過將配置消耗隱藏于執行過程中，以充分發揮流水線性能。

為簡化動態配置的復雜度，針對每個RCB及其對應的RCM, MAM設計了動態配置信息存儲器，如圖6所示。系統工作時在微內核控制器的作用下，配置模塊CM為每個RCB選擇正確的配置上下文，并進行動態配置信息的譯碼、緩存，將譯碼生成的控制信息輸入到S-RCCPA架構每個處理單元和互連單元的控制端上。每個上下文的有效時間為一個時鐘周期，CM將上下文信息依次從配置信息存儲器中讀取、譯碼、激活，實現了處理單元執行密碼運算的同時，完成動態配置信息的自動切換。

動態配置信息的自動切換實現了S-RCCPA架構計算過程的流水化，通過自動切換不同的配置上下文，實現了S-RCCPA架構處理資源的流水線分級和管理，進而實現了分組密碼處理任務在S-RCCPA架構中的流水化計算，通過在有限的處理資源上“虛擬”出無限硬件資源，有效支持了復雜分組密碼處理任務，提高了硬件資源的利用率。圖7描述了S-RCCPA架構以4級流水線執行多級密碼處理任務的操作情況。通過配置信息的自動切換，可以使S-RCCPA架構以4級流水線虛擬執行具有多級流水的密碼處理任務，提高了S-RCCPA架構的適應性和單元利用率。

圖6　S-RCCPA架構配置信息的自動切換

圖7 S-RCCPA架構4級虛擬流水處理結構

4 實現驗證與性能分析

本文在Stratix III系列型EP3SL340H1152C3的FPGA上實現了1×1規模的S-RCCPA架構，實現性能如表1所示。

表1 基于FPGA的驗證原型實現性能

表2基于ASIC的驗證原型實現性能

對以AES, DES, IDEA, SHA, MD5為代表的40多種公開密碼算法[12]的適配結果表明，S-RCCPA架構可以高效處理構造分組密碼的SP網絡、Feistel網絡及LM網絡模型。典型的AES算法虛擬流水適配流程如圖8所示。

圖8 AES在4×1的S-RCCPA架構上的映射

AES-128算法由3部分組成：初始輪密鑰加、中間輪變換、末尾輪變換。其中，中間輪變換包括：字節代替、行移位、列混合和密鑰加4個步驟，共需要循環迭代9次；末尾輪變換包含：字節代替、行移位和密鑰加3個處理步驟。由于S-RCCPA架構中每個RCB在橫向上可以完成128 bit的密碼操作，因此每行中個RCB可以并行處理個AES-128算法。AES算法映射時，輪運算中4個32 bit的字節代替操作可使用4個S盒替代單元實現，128 bit行移位通過128 bit的置換單元實現，4個32 bit的列混合和密鑰加操作使用4個RCC中帶后異或的GF(2)上矩陣乘法單元實現，S-RCCPA架構以虛擬流水方式處理AES算法時，每個RCC中可以有3個RCU同時工作，由于RCU和RCM均包含一級寄存器，因此可以形成深度為24的虛擬流水線，即4×1的S-RCCPA架構上能夠以流水方式處理24個AES密碼分組。

DES算法在規模為4×1的S-RCCPA架構上的映射如圖9所示。S-RCCPA架構通過將DES算法處理過程流水化，依次映射到S-RCCPA架構各行的RCB上，考慮到DES算法的輪變換雖然只對右半部分32 bit數據進行操作，但每輪變換中有多個48 bit的運算，共需要2個RCC并行處理，1個RCB可以在橫向上同時處理2個DES分組，因此，4×1的S-RCCPA架構可以組成兩條64 bit位寬的流水線，分別以虛擬流水線的方式完成DES算法的處理。

為了能夠在每條流水線中處理更多的DES分組，將初始置換后的數據暫停了一級(通過將數據與“0”異或實現處理暫停)，同時不再將異或操作合并在置換單元中。在流水線1中DES算法的64-64的初始IP置換、末尾IP逆置換以及輪運算中32-48的E盒擴展等操作使用RCC(1), RCC(2)中的比特置換單元完成，輪運算中48 bit的密鑰加操作使用RCC(1), RCC(2)的二輸入邏輯完成，查找表、P盒置換、異或等操作分別使用RCC(1)中的S盒查找表、置換以及二輸入邏輯完成。S-RCCPA架構的RCC中可以有2個RCU同時工作，由于RCU和RCM均包含一級寄存器，因此每條虛擬流水線的深度為16，即4×1的S-RCCPA架構中每條流水線能夠流水處理16個DES密碼分組，2條流水線可以同時處理32個分組。

基于待處理數據、子密鑰分量均已準備好，且不考慮系統配置、數據輸入/輸出、密鑰擴展等時間消耗的這一常用假定，在1×1規模配置下，將典型的AES, DES, IDEA這3種不同結構、不同分組寬度、不同操作位寬的算法在S-RCCPA架構上進行映射實現，與其它幾種專用密碼處理結構的實現性能進行了比較分析，結果如圖10所示。其中，RCBCP[2]是一款可重構分組密碼處理器；SophSEC[3]是復旦大學設計的可擴展的密碼處理結構；RCPA[9], RHCA[10]是陣列結構可重構密碼處理系統的代表；PipeRench[11]是基于線性陣列結構部分動態可重構系統；Crypto-Maniac[13]采用了一種具有4路并行的VLIW處理器結構；COBRA[14]是一款專用可重構分組密碼處理器；RELOG_DIGG[15]是北京科技大學研制的可重組密碼邏輯；Cryptonite[16]采用一種兩路并行的RISC結構，每一路RISC處理器能夠處理64 bit位寬數據。

圖9　DES在4×1的S-RCCPA架構上的映射

圖10 不同架構上的典型算法實現性能對比

從不同架構上典型算法的性能橫向對比圖可以看出：由于AES算法采用SP模型設計，規模為1×1的S-RCCPA架構能夠以深度為6的虛擬流水線處理AES算法，AES的密碼處理性能可達其它架構的3.3~12.2倍；DES算法采用Feistel模型設計，迭代輪數較多，且輪運算中連續使用置換操作，因此S-RCCPA架構處理DES算法的性能較AES低，在1×1規模下可以配置成2條深度為4的虛擬流水線執行，相較其他結構，DES的處理性能提升約為1.32~11.96倍；IDEA算法采用LM模型設計，輪運算中廣泛使用異或、模216加和模216+1乘等運算，迭代輪數較少，規模為1×1的S-RCCPA架構能夠組成一條128 bit位寬、深度為6的虛擬流水線，可以同時處理12個IDEA分組，性能是其它處理架構的2.8~21倍。

若使用×1規模的多簇結構實現S-RCCPA架構，基于流處理的框架模型可以高效地將多組明文在流控制器的控制下，流入S-RCCPA陣列結構，通過集約的配置文件管理，在不增加1×1規模S-RCCPA結構配置信息的情況下，AES, DES, IDEA這3類密碼算法的實現性能可線性提高到1×1規模S-RCCPA結構性能的倍，具體如表3所示，表中表示S-RCCPA架構可同時處理的分組數，表示分組長度，CP表示系統處理個分組所需要的時鐘周期數。

表3　n×1規模S-RCCPA架構的ASIC原型性能

在典型的4×1規模配置的情況下，S-RCCPA架構的ASIC實現的等效門數為414.97萬門，較1×1規模配置的面積增加約2.13倍，具有良好的資源效率和可擴展性。

5 結束語

本文在流處理框架模型下，基于分級的全互連結構構造了一種粗粒度可重構的分組密碼處理陣列結構模型，可動態改變粗粒度可重構分組密碼處理單元的互連關系，通過分布式的存儲結構、靜態與動態配置方式的配合，能夠以虛擬流水的方式開發可重構陣列的橫向與縱向兩個方向的并行性，相較于其它結構，在同樣的資源情況下大幅提升了分組密碼處理性能。對于AES, DES, IDEA等經典分組密碼算法的適配結果表明，即使規模設定為1×1, S-RCCPA架構的處理性能也可達其它典型架構的1.32~21倍，具有密碼算法結構適應性好，密碼處理性能和單元利用率高，結構可擴展能力強的特點。論文存在的主要不足在于控制的復雜度較高，虛擬流水線的加入使得同時參與運算的數據量極大增長，在帶來單元利用率增加的同時，使得結構控制的復雜度也相應增加；下一步，擬考慮將分簇式多核密碼處理結構與本模型進行有機融合，進一步在密碼處理的資源效率、控制效率、配置效率與互連結構效率上尋求應用上的綜合平衡。

[1] 李可長. 基于FPGA可重構快速密碼芯片設計[J]. 計算機測量與控制, 2011, 19(7): 1665-1667.

Li Ke-chang. Design of fast reconfigurable cipher chip based on FPGA[J].&, 2011, 19(7): 1665-1667.

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

Meng Tao and Dai Zi-bin. Reconfigurable clustered architecture of block cipher processor[J].&, 2009, 31(2): 453-456.

[3] Huang Wei, Han Jun, and Wang Shuai. A low-complexity heterogeneous multi-core platform for security SoC[C]. IEEE Asian Solid-State Circuits Conference, Beijing, 2010: 1-4.

[4] 宋奐寰, 王樹宗, 邵利兵. 基于可重構計算技術的ASIP設計與實現[J]. 艦船科學技術, 2012, 34(5): 78-82.

Song Huan-huan, Wang Shu-zong, and Shao Li-bing. Design and realize for ASIP based on reconfigurable computing[J]., 2012, 34(5): 78-82.

[5] 何乃味. 基于模塊劃分的可重構分組密碼芯片設計[J]. 計算機工程與設計, 2012, 33(12): 4536-4540.

He Nai-wei. Design of block cipher algorithm chip based on module division[J]., 2012, 33(12): 4536-4540.

[6] 何乃味. 分組密碼算法的可重構設計模型與結構分析[J]. 河池學院學報, 2012, 32(5): 98-103.

He Nai-wei. Reconstructure design model and structure analysis for block cipher algorithm[J]., 2012, 32(5): 98-103.

[7] 朱敏, 劉雷波, 尹首一. 面向對稱密碼領域的可重構陣列設計[J]. 微電子學, 2012, 42(6): 815-818.

Zhu Min, Liu Lei-bo, and Yin Shou-yi. Design of reconfigurable architecture for symmetric cipher domain[J]., 2012, 42(6): 815-818.

[8] 李可長. 粒度可配置的密碼算法重構單元設計[J]. 計算機測量與控制, 2012, 20(3): 830-835.

Li Ke-chang. Design of reconstructure cells for cryptographic algorithm with configurable granularity[J].&, 2012, 20(3): 830-835.

[9] 楊曉輝, 戴紫彬, 張永福. 可重構分組密碼處理結構模型研究與設計[J]. 計算機研究與發展, 2009, 46(6): 962-967.

Yang Xiao-hui, Dai Zi-bin, and Zhang Yong-fu. Research and design of reconfigurable computing targeted at block cipher processing[J]., 2009, 46(6): 962-967.

[10] 姜晶菲. 可重構密碼處理結構的研究與設計[D]. [博士論文], 國防科學技術大學, 2004.

Jiang Jing-fei. The research and design of reconfigurable cipher processing architecture[D]. [Ph.D. dissertation], National University of Defense Technology, 2004.

[11] Goldstein S C, Schmit H, and Moe M. PipeRench: a coprocessor for streaming multimedia acceleration[J]., 1999, 27(2): 28-39.

[12] 戴紫彬. 面向分組密碼處理的協處理器體系結構研究與設計實現[D]. [博士論文], 解放軍信息工程大學, 2007.

Dai Zi-bin. The research and implementation of the coprocessor architecture for block cipher[D]. [Ph.D. dissertation], PLA Information Engineering University, 2007.

[13] Wu L, Weaver C, and Austin T. Cryptomaniac: a fast flexible architecture for secure communication[C]. The 28th Annual International Symposium on Computer Architecture, G6teborg, Sweden, 2001: 110-119.

[14] Elbirt A J and Paar C. Instruction-level distributed processing for symmetric-key cryptography[J]., 2005, 16(5): 468-480.

[15] 曲英杰. 可重組密碼邏輯的研究與設計[D]. [博士論文], 北京科技大學, 2002.

Qu Ying-jie. The research and design of reconfigurable cryptographic logic[D]. [Ph.D. dissertation], University of Science and Technology Beijing, 2002.

[16] Buchty R. Cryptonite: a programmable crypto processor architecture for high-bandwidth applications[D]. [Ph.D. dissertation], Institut fur Informatik der Technischen Universitat Munchen, 2002.

陳韜： 男，1979年生，講師，研究方向為通信與信息安全專用集成電路設計、專用指令集處理器體系結構設計技術、多屬性決策方法.

羅興國： 男，1951年生，教授，研究方向為數字通信、移動通信與高效能計算機體系結構.

李校南： 男，1986年生，工程師，研究方向為信息安全專用集成電路設計.

李偉： 男，1983年生，講師，研究方向為信息安全專用集成電路設計.

An Architecture of Stream Based ReconfigurableClustered Block Cipher Processing Array

Chen Tao Luo Xing-guo Li Xiao-nan Li Wei

(,450001,)

Block cipher; Reconfigurable; Array architecture; Hierarchical interconnection; Stream processing

TP309.7; TN492

A

1009-5896(2014)12-3027-08

10.3724/SP.J.1146.2014.00023

陳韜 chentaoic@aliyun.com

2014-01-06收到，2014-05-26改回

國家863計劃項目(2009AA012201)和國家自然科學基金(61302107)資助課題