一种基于流处理框架的可重构分簇式分组密码处理结构模型

陈 韬 罗兴国 李校南 李 伟



一种基于流处理框架的可重构分簇式分组密码处理结构模型

陈 韬*罗兴国 李校南 李 伟

(解放军信息工程大学 郑州 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)资助课题