面向分组密码算法的高面积效率可重构架构

杨锦江　 曹　鹏　 杨　军

(东南大学国家专用集成电路系统工程技术研究中心, 南京 210096)



面向分组密码算法的高面积效率可重构架构

杨锦江 曹鹏 杨军

(东南大学国家专用集成电路系统工程技术研究中心, 南京 210096)

为了提升安全应用中分组密码算法的面积效率,提出了一种基于粗粒度可重构计算的硬件架构．在可重构架构设计过程中采用了2种优化方案,即利用Benes网络优化可重构计算阵列的层间互联和基于配置信息的使用频度优化配置信息的组织方式．实验结果表明：采用基于Benes网络的层间互联方案后,可重构阵列中层间互联的面积开销减少了51.61%;采用基于使用频度的配置信息层次化组织方式后, AES分组密码算法和DES分组密码算法的配置时间分别缩短了80%和88%,配置时间占总时间的百分数分别下降了42%和39%．这2种分组密码算法在该可重构架构上实现的面积效率为同类架构的3.95和1.51倍．因此,所提的2种优化方案能够有效降低面积开销,提高可重构架构的性能,有助于分组密码算法高面积效率的实现．

分组密码算法;粗粒度可重构架构;层次化配置;面积效率

随着信息技术与网络通信的发展,网络传输对安全的需求不断上升,研究者们据此提出了许多安全协议．密码算法是安全协议的基础,其实现性能对系统性能具有重大影响．安全协议一般需要同时支持多种密码算法,协议中具体使用哪种密码算法由通信双方事先协商决定．日益增加的网络数据带宽对密码算法的性能提出了越来越高的要求．例如,在IPSec和SSL协议中,可以选择AES或DES分组密码算法对大规模数据进行加密．传统的实现方案中,通用处理器实现方案[1]虽然能保证灵活性,但不能满足密码算法高性能的需求;专用集成电路实现方案[2]可以使密码算法获得较好的性能,但缺乏灵活性,不能满足安全协议支持多种密码算法的需求．可重构计算可以在灵活性和高性能之间取得较好的平衡[3]．在可重构架构中,计算任务被高效地映射到硬件资源上,保证了高度并行性,此外,还可以通过配置信息改变其功能,保证了在硅实现后的灵活性．FPGA作为一种细粒度可重构架构,广泛应用于密码算法实现中[4-5],AES,DES等分组密码算法在FPGA上取得了较好的性能,但同时也消耗了大量的面积资源,面积效率不高．粗粒度可重构架构将FPGA中的LUT单元替换成粗粒度的计算单元,精简了FPGA的互联类型,在执行算法时面积效率高于FPGA．研究者们提出了多种面向分组密码算法的粗粒度可重构架构,如RCPA/RCBA[6-7],ADRES[8],AESTHETIC[9]等．然而,粗粒度可重构架构的局部互联灵活性导致互联结构较为复杂,实现过程中需要较多的面积资源和配置信息,从而制约了整个可重构系统的执行性能．本文根据分组密码算法的特点,提出了一种面向分组密码算法的高面积效率的粗粒度可重构架构,有效降低了架构面积,提高了数据处理吞吐率．

1　分组密码算法

分组密码算法将明文分为一系列固定位宽的数据分组,加密过程以数据分组为最小单位,因此分组密码通常在安全协议中被用作大规模数据传输时的加密．分组密码算法可以按照结构特征分为SP结构和Feistel结构2类．前者的扩散速度较快;后者的扩散速度较慢,但加/解密过程一致．

分组密码算法的基本特征如下:

1) 数据并行度大．分组密码算法对明文/密文数据按固定长度进行分组,每组数据又可被分割成多块等长的数据进行运算．例如,AES分组密码算法按128 bit进行分组,在进行字节替换时,每组数据被进一步分割成16个8 bit数据进行操作．各组数据之间、组内各块数据之间均无数据依赖,因此多组/块数据可以并行执行．

2) 计算过程规则． 在分组密码算法中,明文分组后经过多轮迭代得到密文,每轮迭代操作基本一致,仅首轮或末轮的轮函数可能存在微小差异．典型的分组密码算法流程图如图1所示．由图可知,AES分组密码算法分10轮迭代进行,与前9轮操作相比,第10轮仅省去列混合操作;DES分组密码算法分16轮迭代进行,与前15轮操作相比,第16轮省去数据的左右交换．

(a) AES分组密码算法

(b) DES分组密码算法

3) 基本算子趋同．虽然分组密码算法的具体运算过程各不相同,但都是由一些基本算子组成的．文献[10]统计了41种常见的分组密码算法,将基本操作归纳为7种类型.逻辑操作、S盒替换、移位/循环移位操作、模加/减、比特置换、模乘和Galois域上的模乘．其中,逻辑操作、S盒操作、移位/循环移位操作的发生概率超过60%．

4) 数据通路复杂．分组密码算法在扩散过程中使用了比特置换和移位等操作,从而使得算法执行的数据通路具有丰富的变化形式．

2　面向分组密码算法的可重构架构

根据分组密码算法的基本特征,给出了面向分组密码算法的粗粒度可重构架构(见图2)．架构由配置控制器、计算阵列、输入FIFO、输出FIFO以及数据缓存等部分组成．其中,配置控制器用于解析索引信息,从配置信息中选取与索引对应的配置信息,对计算阵列进行配置;计算阵列根据配置信息执行算法;输入、输出FIFO分别用于明文的输入和密文的输出;数据缓存用于存储计算阵列计算过程中产生的中间结果数据．

(a) 架构总体框图

(b) 计算阵列框图

2.1计算阵列

计算阵列为面向分组密码算法的可重构架构中的核心模块,其架构框图如图2(b)所示．计算阵列以行为基本单元,每行包括读入、写出、层间互联和PE等单元．针对分组密码算法数据并行度大的特点,每行阵列中包含多个PE以并行处理数据．读入单元用于从输入FIFO或数据缓存中读入数据至该行阵列,写出单元用于从该行阵列中写出结果至输出FIFO或数据缓存．阵列的行与行之间通过层间互联单元进行数据传输.

2.2配置控制器

配置控制器负责对计算阵列进行配置,使得阵列通过切换不同的数据流图来执行完整个算法．配置控制器中包含配置信息存储器和索引信息存储器,分别存放整个算法的子图配置信息以及索引信息．其中,算法子图配置信息包含了该子图中数据的输入输出形式和计算功能,而索引信息用于快速索引到这些配置信息,并有效避免配置信息的重复存储．配置控制器的执行步骤如下:① 系统在重置时对算法的索引信息和配置信息进行初始化;② 当计算阵列准备就绪,配置控制器开始执行;③ 解析索引信息,根据索引信息选取对应的配置信息,对计算阵列进行配置;④ 判断是否需要终止配置,如果终止则退出配置解析,否则当计算阵列再次准备就绪时,跳转到步骤③．

3　可重构架构的硬件设计优化

3.1面向低硬件开销的层间互联方案优化

由第1节可知,分组密码算法具有数据通路复杂的特点．为了保证算法中比特置换等核心算子的执行效率,层间互联需要满足PE行间全互联的数据通路需求,同时需要有效控制丰富的互联需求导致的硬件开销增长．Crossbar结构[11]和Benes网络是2种主要的全互联实现形式．以Crossbar结构的方式实现全互联,可以较少的配置信息完成其功能配置,然而需要消耗较多的硬件资源;而以Benes的方式实现全互联,需要的硬件资源较少,但需要更多的配置信息进行功能配置．

图3为基于Crossbar结构的层间互联示意图．如图所示,Crossbar结构的层间互联将前一行的L个输出数据连接到当前行的输入中．

图3　基于Crossbar结构的层间互联示意图

由图3可见,Crossbar结构层间互联传输数据的位宽与PE计算数据的位宽一致．然而,在分组密码算法中,比特置换和移位等操作的位宽通常大于PE计算位宽比特,因此,虽然Crossbar结构层间互联的控制方式简单,但无法满足分组密码算法中置换和移位等数据传输需求．

256 bit的Benes网络实现示意图见图4．由图可知,该网络可由2个128 bit的Benes网络构成,并可以进一步向下拆分,网络中的基本元件为一个2×2的置换开关,每个2×2的置换开关存在交叉和直通2个状态,由2个1 bit的2选1数据选择器组成．256 bit数据经过Benes网络构成的层间互联后,可以得到该数据的任意置换．由此可知,Benes网络可实现比特置换、移位等操作．

图4　Benes网络实现示意图

Crossbar结构和Benes网络需要的2输入1输出的数据选择器数量分别为

Cmuxer=N(N-1)m

(1)

Bmuxer=2(mN)log2(mN)-mN

(2)

式中,N为每行PE的数量;m为每行PE的数据位宽.

如图5所示,随着每行PE数目的增长,Crossbar结构的层间互联实现所需资源的增长速度明显快于Benes网络．

图5　层间互联实现所需硬件开销对比

与Grossbar结构相比，Benes网络的层间互联消耗资源更少,但需要更多的配置信息．2种层间互联所需的配置信息量分别为

Cconf=Nlog2N

(3)

Bconf=mNlog2(mN)-mN

(4)

式中,Cconf,Bconf分别为Crossbar结构和Benes网络的层间互联所需要的配置信息量．

图6为2种互联结构需要的配置信息量比较．由图可知,随着PE数目的增长,Benes网络所需要的配置信息急剧增加．配置信息量过大会影响配置的效率,从而影响整个算法的性能．

综上所述,采用Benes网络作为层间互联的形式有助于减少面积资源消耗,但是需要消除其配置信息量过大对于整个系统执行性能的影响．

图6　层间互联实现所需配置信息量对比

3.2面向高性能的配置信息组织形式优化

架构中计算和互联等模块都可以重构,故需要使用配置信息对整个架构进行配置[6]．算法的执行时间为

Ttotal=Tconf+Tcalc

(5)

式中,Tconf,Tcalc分别为配置时间和计算时间．

由式(5)可知,通过减少Tconf可以有效减小整体执行时间Ttotal，其计算公式为

(6)

式中,M为算法中需要切换的子图数目;tconf-i为第i次子图切换时需要的配置时间．

图7描述了阵列全局配置与局部配置情况下算法总执行时间的关系．图中,tmax为切换子图时对阵列进行全局配置所需要的最大配置时间;tcalc-i为第i次子图的计算时间;Tconf-M和Tcalc-M分别为最后一张子图的计配置时间和计算时间．由图可知,在算法执行过程中,局部配置可以有效地减小配置时间．

图7　阵列局部配置与全局配置执行时间

由分组密码算法的特征可知,计算过程规则和基本算子趋同会导致算法中不同子图间存在相似性．因此,可以按照配置信息使用的频度对配置信息的组织形式进行优化．

图8描述了配置信息组织形式优化前后的存储形式．由图可知,优化前更新子图需要将第0～R行的配置全部更新．优化后则可按照配置信息不同的使用频度进行层次化存储,在更新子图时,每行只需要更新部分配置信息．同时,如果该行的部分配置与更新前一致,则在动态生成配置时无需重复生成．因此,在配置过程中只需更新一部分配置信息即可,使得每次更新子图时Tconf-i

图8　基于使用频度的配置信息组织形式优化

综上所述,3.1节利用Benes网络层间互联替换传统的Crossbar结构层间互联,从而优化了层间互联的面积;然而,Benes网络层间互联需要较大的配置信息量，影响了配置速度,从而使得整体性能下降．因此，本节中提出了面向高性能的配置信息组织形式,减少了配置信息传输量,加快了配置速度,提升了阵列的整体性能．

4　结果和比较

4.1硬件实现

采用RTL硬件描述语言完成图2中的架构,并利用VCS工具进行功能和时序仿真．硬件实现基于SMIC 55 nm CMOS工艺库,利用Synopsys公司的Design Complier (DC) 工具进行综合,生成门级网表,并通过IC Compiler(ICC)工具实现布局布线,得到可重构架构的版图(见图9)．在300 MHz频率的约束下,本架构的面积为5.01×106gate．

图9　可重构架构版图

4.2性能分析与比较

由3.1节可知,层间互联可通过Crossbar结构和Benes网络2种方式实现．表1列出了这2种方式的面积开销与配置信息量．由表可知,Benes网络的实现面积较Crossbar结构减小了51.61%,但其需要的配置量为Crossbar结构的12倍．

表1　Crossbar结构与Benes网络的面积与配置对比

采用基于使用频度的配置信息组织形式后,切换子图时不需要对阵列进行全局配置,子图中冗余的配置信息不再更新,从而提升了配置的性能．采用基于使用频度的配置信息组织形式后,AES分组密码算法和DES分组密码算法的配置时间分别减少了80%和88%,相应地,AES分组密码算法和DES分组密码算法的配置时间占总时间的百分数分别下降了42%和39%．

表2列出了本文架构与类似架构的比较．由表可知道,RCPA架构[6]的面积小于本文架构,但是配置时间过长导致其算法的吞吐率不高;本文架构中采用了基于使用频度的配置存储和配置方案,缩短了执行时间,使得AES分组密码算法与DES分组密码算法实现的面积效率分别为RCPA架构的1.64与2.22倍．COBRA架构[12]中算法的吞吐率较高,但是消耗了大量的面积资源;本文架构采用Benes网络的方式实现层间互联,降低了面积消耗,AES分组密码算法在本文架构上实现的面积效率为COBRA架构的3.95倍．AsAP架构[1]具有较高的执行频率,但是需要众多的运算和互联资源,且其计算过程中仍需要取址和译码,AES分组密码算法在本文架构上实现的面积效率为AsAP架构的2.90倍．Cryptoraptor架构[13]在较高频率的基础上对AES分组密码算法进行了流水线技术优化,获得了较高的面积效率;然而,对于其他分组密码算法,该架构的面积效率并不理想．例如,DES分组密码算法在本文架构上实现的面积效率为Cryptoraptor架构的1.51倍．

5　结语

本文通过分析分组密码算法的特征,提出了一个面向分组密码算法的高面积效率可重构架构,通过进行架构层间互联优化以及配置信息层次化,提升了算法在架构上的性能,并降低了架构实现的面积．AES分组密码算法在本文架构上实现的面积效率为同类架构COBRA的3.95倍,DES分组密码算法在本文架构上实现的面积效率为同类架构Cryptoraptor的1.51倍．

表2　本文架构与类似架构的比较

References)

[1]Liu B, Baas B M. Parallel AES encryption engines for many-core processor arrays[J].IEEETransactionsonComputers, 2013, 62(3):536-547. DOI:10.1109/tc.2011.251.

[2]Mathew S K, Sheikh F, Kounavis M, et al. 53 Gbps native GF(24)2composite-field AES-encrypt/decrypt accelerator for content-protection in 45 nm high-performance microprocessors[J].IEEEJSolid-StateCircuits, 2011, 46(4):767-776. DOI:10.1109/jssc.2011.2108131.

[3]Hartenstein R. A decade of reconfigurable computing: A visionary retrospective[C]//ProceedingsoftheConferenceonDesign,AutomationandTestinEurope. Munich, Germany, 2001:642-649. DOI:10.1109/date.2001.915091.

[4]Liu Q, Xu Z, Yuan Y. A 66.1 Gbps single-pipeline AES on FPGA[C]//2013InternationalConferenceonField-ProgrammableTechnology. Kyoto,Japan, 2013: 378-381. DOI:10.1109/fpt.2013.6718392.

[5]Wang Y, Ha Y. FPGA-based 40.9-Gbits/s masked AES with area optimization for storage area network[J].IEEETransactionsonCircuitsandSystemsII:ExpressBriefs, 2013, 60(1):36-40. DOI:10.1109/tcsii.2012.2234891.

[6]Dai Z B, Yang X H, Ren Q, et al. The research and design of reconfigurable cipher processing architecture targeted at block cipher[C]//7thInternationalConferenceonASICASICON’07. Guilin, China, 2007:814-817.DOI:10.1109/icasic.2007.4415755.

[7]Yang X, Dai Z, Zhang Y, et al. The research and design of reconfigurable computing for block cipher[J].JournalofElectronics(China), 2008, 25(4):503-510. DOI:10.1007/s11767-006-0279-y.

[8]Garcia A, Berekovic M, Vander A T. Mapping of the AES cryptographic algorithm on a coarse-grain reconfigurable array processor[C]//InternationalConferenceonApplication-SpecificSystems,ArchitecturesandProcessors. Leuven,Belgium, 2008:245-250. DOI:10.1109/asap.2008.4580186.

[9]Wang M Y, Su C P, Horng C L, et al. Single- and multi-core configurable AES architectures for flexible security[J].IEEETransactionsonVeryLargeScaleIntegration(VLSI)Systems, 2010, 18(4):541-552. DOI:10.1109/tvlsi.2009.2013231.

[10]Elbirt A J, Paar C. An instruction-level distributed processor for symmetric-key cryptography[J].IEEETransactionsonParallelandDistributedSystems, 2005,16(5):468-480. DOI:10.1109/TPDS.2005.51.

[11]Park H W, Kim W, Yoo D, et al. A scalable scheduling algorithm for coarse-grained reconfigurable architecture[C]//IEEEInternationalConferenceonConsumerElectronics(ICCE). Las Vegas, Nevada,USA, 2013:542-543.

[12]Elbirt A J, Paar C. An instruction-level distributed processor for symmetric-key cryptography[J].IEEETransParallelDistribSyst, 2005, 16(5):468-480. DOI:10.1109/tpds.2005.51.

[13]Sayilar G, Chiou D. Cryptoraptor:High throughput reconfigurable cryptographic processor[C]//2014IEEE/ACMInternationalConferenceonComputer-AidedDesign. Los Angeles, CA,USA, 2014:154-161. DOI:10.1109/iccad.2014.7001346.

Reconfigurable architecture with high area efficiency for block cipher algorithms

Yang Jinjiang Cao Peng Yang Jun

(National ASIC System Engineering Technology Research Center, Southeast University, Nanjing 210096, China)

A coarse-grained reconfigurable architecture is proposed to improve the area efficiency of block cipher algorithms in the security applications. Two schemes are used to optimize the architecture. One is using the Benes network to optimize the connection between rows of the reconfigurable architecture, and the other is optimizing the context organization according to the use frequency. The experimental results show that the area cost is reduced by 51.61% after using the Benes network as the optimization of row connection. After using the hierarchical context organization based on the using frequency, the configuration time of the AES(advanced encryption standard) block cipher algorithm and that of the DES(data encryption standard) block cipher algorithm decrease by 80% and 88%, and the proportions of their configuration time in the total time decrease 42% and 39%, respectively. The area efficiencies of these two block cipher algorithms implemented on the proposed reconfigurable architecture are 3.95 and 1.51 times of the similar architectures, respectively. Therefore, the two proposed schemes can effectively decrease the area cost, improve the performance of the reconfigurable architecture and favor the efficient area implementation of block cipher algorithms.

block cipher algorithm;coarse-grained reconfigurable architecture;hierarchical configuration organization;area efficiency

10.3969/j.issn.1001-0505.2016.05.007

2016-04-28.作者简介: 杨锦江(1986—)，男，博士生；杨军(联系人),男,博士,教授,博士生导师，dragon@seu.edu.cn.

国家自然科学基金资助项目(61404028).

TN302

A

1001-0505(2016)05-0939-06

引用本文: 杨锦江,曹鹏,杨军.面向分组密码算法的高面积效率可重构架构[J].东南大学学报(自然科学版),2016,46(5):939-944. DOI:10.3969/j.issn.1001-0505.2016.05.007.