基于运算部件的可重构密码算法处理架构

杨壮林，郭宇波，赵梦恋

（浙江大学超大规模集成电路设计研究所，杭州310027）

基于运算部件的可重构密码算法处理架构

杨壮林，郭宇波，赵梦恋

（浙江大学超大规模集成电路设计研究所，杭州310027）

针对加解密运算中微处理器性能低、功耗高，以及专用电路灵活度受限的问题，提出基于运算部件粗粒度可重构的密码加速单元及其架构。给出密码运算的原子运算并实例化为运算部件，以原子运算部件为重构粒子，路由表负责配置运算部件互连网络以组合运算，参数表负责配置密码算法参数。通过生成路由表与参数表配置信息，对密码加速单元进行粗粒度重构。该架构在TSMC 0.13μm时可工作在350 MHz的时钟频率下。实验结果表明，提出的架构兼具微处理器与专用电路的优点，支持多种密码算法，所需的信息量和资源消耗少，并具有较好的性能面积比。

密码算法；粗粒度；可重构；运算部件阵列；路由器阵列；路由表

1 概述

信息技术的飞速发展对信息正确性和私密性的要求越来越高。为提高加密强度，一般采用两方面措施：（1）加长密钥长度；（2）增加算法复杂度。无论采用哪种措施，都会导致运算量急剧增加，并对密码加解密平台的运算能力提出极高要求。一种运算运行是通用微处理器，采用软件方式加解密，具有高度灵活性，但性能与能效表现不佳。另一种传统的加解密平台是专用集成电路（Application Specific Integrated Circuit，ASIC），能充分匹配应用特征并做优化处理，具有出色的性能与功耗表现，但缺乏灵活性。采用通用微处理器或ASIC平台进行加解密运算在现实应用中存在比较明显的劣势。

可重构方法兼具微处理器和ASIC密码处理灵活与高效的特点。文献［1］设计了4个功能可重构的处理单元组成流水线结构，运算并行度高但其只能支持RSA（Rivest-Sham ir-Adleman）与椭圆曲线（Elliptic Curve Cryptographic，ECC）2种密码算法。文献［2］提出了3级重构的密码算法处理结构，灵活度高，但大量配置信息需要从存储器动态加载，性能较差。文献［3］提出基于FPGA的细粒度可重构密码芯片，可支持数据加密标准（Data Encryption Standard，DES）算法，高级加密标准（Advanced Encryption Standard，AES）算法，RSA算法等多种典型密码算法，通用性高，但面积与功耗都很大。纵观上述设计方法，通常只能支持个别密码算法，或配置信息太多，功耗与性能表现不佳，在通用性、性能与功耗上存在缺陷。

本文提出一种通用的粗粒度可重构密码算法处理架构，核心思想是提取出密码算法的原子运算并实例化为运算部件，由路由表配置运算部件的互联网络，实现基于运算部件的粗粒度可重构。

2 密码算法分析

2.1 主流密码算法运算分析

密码算法的基本原理是以固定的算法循环迭代对数据依次进行加解密运算。对主流密码算法的研究发现，加解密运算可抽象为某些原子运算的组合，原子运算包括逻辑操作（主要为异或）、移位、加法、乘法、数据缓存等。表1归纳了一些主流密码算法的原子运算操作。不仅表1所示的密码算法，很多其他密码算法如数字签名算法（Digital Signature A lgorithm，DSA）、数论研究单元算法（Number Theory Research Unit，NTRU）等都可以分解为表1所归纳的原子运算。不同密码算法的数据操作宽度虽然各不相同，但都可采用32位的数据位宽循环迭代实现大位宽运算［4-7］。

表1 主流密码算法的原子运算bit

2.2 RSA密码算法的原子运算分解

以RSA密码算法为例，其加解密都是基于模幂运算。常用的模幂算法如二进制算法、滑动窗口法等都是依次扫描密钥每个比特位，根据扫描结果进行相应模乘运算。蒙哥马利模乘算法的一种实现方式［8］如下所示，将运算分解为数据位宽为k的原子运算。输入的被乘数和乘数为A=as-1as-2…a0和B=bs-1bs-2…b0，结果为C。

提取出蒙哥马利算法每一个步骤所对应的原子运算，有加法、乘法、移位和数据缓存，RSA密码算法的加解密运算即由这些原子运算组合而成。不仅RSA，其他大量密码算法的运算也可分解为表1所示的原子运算的组合。

3 可重构密码算法处理架构设计

3.1 整体架构

前文归纳了大量密码算法共有的原子运算，本文在实例化这些原子运算为运算部件的基础上提出基于运算部件粗粒度可重构的密码算法处理架构，辅以路由表与参数表重构运算功能，支持各种密码算法。架构主要包含接口模块、控制模块、运算部件阵列、路由器阵列、存储器以及可自定义的路由表和参数表，如图1所示。

图1 可重构的密码算法处理架构

接口负责与外部控制信息和数据的通信。存储器由4个部分组成，存储器0与1用于缓存运算部件计算所需的源数据，存储器2用于缓存运算结果，存储器3用于缓存与外部通信的密码算法参数。参数表定义了属性参数，如密钥、二元域控制位、加解密数据的长度、运算部件处理的数据位宽等。控制模块与参数表配合，负责整个架构的全局控制管理，如读取存放存储器数据、路由表项、参数、启动停止运算等。

运算部件阵列、路由器阵列以及路由表是架构的核心模块，这3个模块配合完成架构的重构。运算部件阵列包括加法器、乘法器、左移位器、右移位器、逻辑操作共5个原子运算单元以及数据缓存器。原子运算单元独立完成相应的运算操作。数据缓存器内部有5个独立的寄存器组，与5个运算单元一一对应，可通过配置寄存控制位与保持控制位对运算单元的结果进行寄存、保持或直接输出，如图2所示。寄存控制位用于决定运算结果是否寄存一级再输出。保持控制位用于决定是否保持原先的运算结果。数据缓存器配合寄存控制位可以灵活调整数据通路的逻辑路径延时，使电路能够满足多种频率需求，从而达到较高的工作频率。

图2 数据缓存器结构

运算结果经由数据缓存器处理后输入到路由器阵列。路由器阵列是运算部件以及存储器之间的互连网络。路由表由多个表项组成，是运算部件之间互联关系的映射，每个表项由路由器0～10的路由信息、寄存控制位与保持控制位组成，如图3所示。路由0～10每一项为3位，分别对应原子运算单元及存储器输入端数据的路由信息，其对应连接关系可参考图1。寄存控制位与保持控制位均有5位，分别对应5个原子运算部件。通过配置数据源的路由编码，定义数据通路，为运算部件和存储器3选择合适的数据来源。

图3 路由表项信息

每一个路由表项定义了一种数据通路，是一种运算组合的映射。不同密码算法或同一密码算法的不同运算阶段往往具有不同的运算内容，运算过程中通过不断读取并切换路由表项重构运算部件的互连关系，动态重构数据通路，完成动态变化的运算内容。

本设计采用以运算部件为重构粒子的粗粒度重构方式，只需对路由表以及参数表进行配置，即可完成对不同密码算法的支持，重构逻辑简单，重构信息较少，有利于用户实现。

3.2 RSA在架构中的映射实现

以典型密码算法RSA为例，阐述其在该架构的映射。首先初始化参数表，即初始化密钥，将二元域的控制位置零，设置好数据长度，运算位宽设为32位等。根据算法生成对应的路由表信息是一个关键步骤。加解密运算由多个原子运算组合完成，需将运算组合映射到路由表项。以t［j］+a［j］×b［j］为例，其先进行乘法再进行加法运算。乘法器输入数据a［j］与b［j］来自存储器0与1，结合图3的数据源编码，则路由器2与3的配置项为101与110。加法器输入数据来源分别为乘法器与存储器2，则路由器0与1的配置项为001和111。最终的运算结果来自于加法器并被存放到存储器2中，则路由器10配置项为000。在本次运算过程中没有用到的运算部件，输入源的路由配置项选择自身。如本次运算中没有用到的左移器，其输入端的路由配置项为010。路由表项的寄存控制位为10111，保持控制位为00111，即加法结果寄存一级再输出，乘法结果不寄存直接输出给加法器，没有用到的运算部件对应的保持控制位和寄存控制位为1，以保持原先结果。t［j］+a［j］×b［j］到路由表项的映射结果如表2所示。

表2 t［j］+a［j］×b［j］到路由表项的映射

按照该方式可完成蒙哥马利算法所有运算步骤到路由表的映射，即完成RSA密码算法到路由表的映射。对于其他密码算法，类似的只需要匹配好目标算法，提取出原子运算及组合，并生成对应的参数表与路由表信息，即可粗粒度重构处理架构的功能，从而支持各种密码算法运算。

4 实验结果与分析

本文提出的处理架构采用的乘法器需2个时钟周期完成运算，并配置路由表使数据都先寄存一次再输出。采用Synopsys公司的Design Com p lier工具，TSMC 130 nm RVT工艺库对电路进行综合，延时为2.8 ns，路由器输入端到乘法器中间结果的逻辑路径为关键路径，电路最高工作频率为350 MHz。

以典型密码算法RSA，ECC与RC6为例，设计实验对提出的处理架构进行功能验证，并与处理器和专用电路平台作对比，对结果进行分析评估。分别采用CK810处理器与本文提出的处理架构，对相同的密钥与明文数据进行密码运算，对比实验结果如表3所示。

表3 本文架构与CK 810的RSA性能对比

尽管CK810是高频率、指令双发射并乱序执行的高性能处理器［9］，但其软件加解密方式在性能与功耗上表现都较差。本文的架构针对RSA进行粗粒度重构，能更好地匹配算法特点，性能更高且功耗更低。

表4对比了本文架构与其他专用电路进行RSA密码运算的性能。文献［10］采用大位宽乘法器与加法器以提高运算效率，但工作频率低，资源消耗大，性能仅为本文架构的45.5%。文献［11］采用总共34个加法器在高时钟频率条件下流水完成运算，性能比本文架构高7%，但资源消耗远大于本文架构。此外，文献［10-11］均只能支持RSA密码算法，灵活性较差。

表4 RSA算法性能对比

表5对比了本文与其他电路的ECC密码运算性能。文献［12］设计了4个运算单元并行计算，性能比本文架构略优，但运算资源是本文架构的近4倍。文献［13］设计了基于FPGA细粒度重构的ECC密码加速系统，不仅资源消耗大，而且性能较低。

表6对比了本文架构与文献［4］的RC6密码运算性能。文献［4］的性能比本文架构高21%，但运算资源是本文架构的4倍，运算部件采用部分串联连接，路径延时较大且不能很好匹配算法特点，运算资源得不到充分利用。

表6 RC6算法性能对比

受限于篇幅，本文设计所支持的其他密码算法对比实验结果不再列出。已有的对比实验结果表明，相比软件方式加解密，本文提出的密码处理架构性能更高，功耗更低。相比专用电路或其他可重构电路，本文的设计重构逻辑简单，重构所需信息量少，资源消耗少，性能良好，具有更好的性能面积比。

5 结束语

本文提出一个密码算法处理架构，设计运算部件阵列、路由器阵列以及路由表与参数表等关键模块，可对处理架构进行粗粒度重构，从而灵活支持各种密码算法，重构信息少、重构便捷。实验结果表明，与微处理器、专用电路或其他可重构电路相比，该架构在保证灵活性的基础上，功耗较低，性能优良，具有良好的性能面积比，在多样的密码加解密应用中有充分的竞争力。为进一步优化设计方案，后续工作将增加原子运算单元，提高通用性与并行性；研究原子运算单元以及运算部件阵列之间的路由网络，更好地匹配密码算法的特点，提高加解密运算性能。

［1］ 黎 明，吴 丹，戴 葵，等.高性能可扩展公钥密码协处理器研究与设计［J］.电子学报，2011，39（3）：665-670.

［2］ 王玉良.面向密码算法的粗粒度可重构结构研究与设计［D］.郑州：解放军信息工程大学，2010.

［3］ 李可长.基于FPGA可重构快速密码芯片设计［J］.计算机测量与控制，2011，19（7）：1665-1667.

［4］ 杨晓辉.面向分组密码处理的可重构设计技术研究［D］.郑州：解放军信息工程大学，2007.

［5］ Elbirt A J.Reconfigurable Computing for Symmetric-key Algorithms［D］.Worcester，USA：Worcester Polytechnic Institute，2002.

［6］ Ravikumar K，Udhayakumar A.A Detailed Study of Elliptic Curve Cryptography Algorithm and Its Performance［J］. International Journal of Engineering Science&Research Technology，2013，2（10）：2960-2964.

［7］ Bluhm M，Gueron S.Fast Software Implementation of Binary Elliptic Curve Cryptography［EB/OL］.（2014-10-15）.http：//eprint.iacr.org/2013/741.pdf.

［8］ KoçÇK，Acar T，Kaliski B S.Analyzing and Comparing Montgomery Multiplication Algorithms［J］.IEEE Micro，1996，16（3）：26-33.

［9］ C-Sky Microsystems.Co.，Ltd..C-Sky CK810 User's Manual［EB/OL］.（2014-10-20）.http：//www.c-sky.com.

［10］ Moon S.Design of a Scalable RSA Cryptoprocessor Em bedded with an Efficient MAC Unit［C］// Proceedings of the 2nd International Conference on Future Generation Communication and Networking. Washington D.C.，USA：IEEE Press，2008：74-77.

［11］ Chen Yunlu，Tseng Chih-Yeh，Chang Hsie-Chia.Design and Implementation of Reconfigurable RSA Cryptosystem［C］//Proceedings of International Symposium on VLSI Design，Automation and Test.Washington D.C.，USA：IEEE Press，2007：1-4.

［12］ Zhao Xuem i，Wang Zhiying，Yue Hong，et al.TTA-EC：A W hole Algorithm Processor for ECC Based on Transport Triggered Architecture［J］.Chinese Journal of Computings，2007，30（2）：225-233.

［13］ Liu Sining，Francis B，Brian K，et al.Elliptic Curves Cryptosystem Implementation Based on a Look-up Table Sharing Scheme［C］//Proceedings of International Symposium on Circuits and System s.Washington D.C.，USA：IEEE Press，2006：2921-2924.

编辑顾逸斐

Reconfigurable Cryptographic Algorithm Processing Architecture Based on Operating Element

YANG Zhuanglin，GUO Yubo，ZHAO Menglian
（Institute of VLSI Design，Zhejiang University，Hangzhou 310027，China）

Facing with the poor performance and high power consumption of microprocessor and inflexibility of ASIC in encryption and decryption computation，coarse-grain reconfigurable cryptographic algorithm processing architecture based on operating elements is proposed.This paper extracts atomic operations and instantiates them as processing elements.Operating elements are taken as reconfigurable gains，coupled with routing table and parameter table.Routing table is in charge of configuring interconnection network of operating elements while parameter table is responsible for configuring cryptographic algorithm parameters.By generating routing table and parameter table information according to different cryptographic algorithms，cryptographic accelerator is coarse-grain reconfigured to support various cryptographic algorithms.The circuit reaches clock frequency of 350 MHz using TSMC 0.13μm cell library.Experimental results show that the architecture has both the advantages of microprocessor and ASIC and it flexibly supports various cryptographic algorithms.The required amount of information and resource consumption is less，and has better performance area ratio.【Key words】cryptographic algorithm；coarse-grain；reconfigurable；operating element array；router array；routing table

10.3969/j.issn.1000-3428.2015.11.016

杨壮林，郭宇波，赵梦恋.基于运算部件的可重构密码算法处理架构［J］.计算机工程，2015，41（11）：89-93.

英文引用格式：Yang Zhuanglin，Guo Yubo，Zhao Menglian.Reconfigurable Cryptographic Algorithm Processing Architecture Based on Operating Element［J］.Computing Engineering，2015，41（11）：89-93.

1000-3428（2015）11-0089-05

A

TP301.6

杨壮林（1988-），男，硕士研究生，主研方向：计算机体系结构；郭宇波，工程师、硕士；赵梦恋，副教授。

2014-11-21

2014-12-19 E-m ail：edians@163.com