SM4算法CBC模式的并行化研究与实现

◆李 莉史国振杨 凤

（1.西安电子科技大学通信工程学院 西安 710071；2.北京电子科技学院 电子信息工程系 北京 100070）

SM4算法CBC模式的并行化研究与实现

◆李 莉1，2史国振2杨 凤2

（1.西安电子科技大学通信工程学院 西安 710071；2.北京电子科技学院 电子信息工程系 北京 100070）

本文通过对CBC模式下SM4算法结构的分析，根据密文输出前的反序变换，提出一种分组间部分并行的设计方案，改善了CBC模式只能串行执行的现状，并对方案在xc5vllx110t上进行了设计实现，测试结果表明，本方案能够提高单一多分组任务的CBC执行速度，同时不影响原设计方案对单个分组的执行速度。此方案可以在已有的SM4算法优化的基础上进行实现，充分发挥多核架构的优势。

CBC模式；SM4；并行设计

0 引言

信息安全是网络信息化环境下的必然需求，密码作为实现数据安全传输的基本手段，是信息安全领域不可或缺的环节。在数据密集型应用中，如何对数据进行快速的密码算法处理，而不影响用户的应用体验，始终是密码算法设计和实现领域关注的目标。随着单核系统在速度提升上的瓶颈，片上多核系统已成为事实上的芯片发展趋势，通过多核间的并行操作可以实现密码算法的快速运算，有效提升数据处理速度。在密码算法的工作模式中，CBC模式由于其可以隐藏相同明文的优势，较之其他密码工作模式更为安全，从而得到广泛应用。但是CBC模式内在的并行性又限制了其在多核上的并行执行。在多核架构已成为事实存在的当下，有必要进行cbc模式并行化的研究。

1 相关研究

随着2012年3月国家密码管理局发布的SM4算法，SM4算法作为国家密码管理局发布的密码算法，近年来对其研究越来越多，文献1根据应用需求，在8bit的智能卡上实现SM4算法；文献2对SM4进行的功耗分析研究表明SM4算法具有一定的抗差分功耗分析的能力，通过合理的算法设计可以获得高的侧信道安全性。对于SM4算法的优化研究也多集中在缩短关键路径和面积的优化上3,4，通过设计专用的指令集处理器，或者将密钥扩展通过嵌入式的cpu核实现，来提高算法的速度和灵活性。文献5通过对算法s盒置换和移位操作的优化，实现了895Mbps的吞吐率。

作为NIST推荐的分组密码工作模式，CBC密码模式由于具有隐藏长文件下的相同明文分组的特点，克服了ECB模式的缺陷，而得到广泛使用。若某业务的数据流包含n个分组数据， CBC密码模式如下所示：

其中Ci为第i个分组数据的加密结果。CBC密码模式在对明文进行加密时引入了初始向量IV，并将前一个分组数据的运算结果Ci-1作为后一个分组的IV，从而保证了即使明文分组Pi相同，但是由于分组加密算法加密的是XOR(Ci-1, Pi)，所以密文并不相同。CBC运算模式的这种迭代关系，决定了对于同一个数据文件其加密操作只能是串行的，从而限制了其在多核处理器上的并行执行。

因此对于密码算法的多核并行执行，多是采用ECB、CTR模式实现。例如文献6介绍了AES算法ECB模式和CTR模式的高速实现，通过采用全流水线，以及对s盒和乘法逆变器的优化，实现了ECB模式在644.33MHz下的82.4Gbps，CTR模式在508.104 MHz下的260.15 Gbps的吞吐率。目前已有的探讨CBC模式并行执行的文献大多是以任务分片的模式进行，没有深入进行密码算法在CBC密码模式下结构上的探讨。文献7研究了CBC模式下多SM4密码处理引擎的并行处理机制，提出了CBC模式下多引擎的任务分配机制。此方案通过控制单元将不同的任务送至不同的SM4处理单元上，从而形成了多个任务之间的并行处理，提高了系统的总的吞吐率。但是对于单一任务的处理仍是在一个核上采用串行的方式完成。因此单一任务的处理速度并未得到提高。文献8通过缩短设计中的关键路径，在算法级将AES算法的中的字节代替变换与列混合变换进行合并，从而实现了AES算法的高速实现，在密钥长度为128bit时，最高工作频率可以达到781MHz，从而实现了高达9.9Gbps的吞吐率。虽然实现了高的吞吐率，但是此文献在CBC模式的实现上仍然是采用串行的方式完成，即同一任务的不同分组之间仍然是采用串行方式完成。文献9通过采用GCM模式，实现了基于SM4算法的加密与认证功能，设计基于fpga采用全流水线架构实现了22.248Gbps的吞吐率。本论文通过分析CBC模式下SM4算法的特点，提出了同一任务不同分组间的部分并行设计方法，此方法可以在上述提到的SM4算法优化的基础上进行，测试表明此方法对系统最高工作频率，以及资源的占用情况影响不大。

2 SM4算法

2.1 轮函数F

SM4算法以128bit为一个分组，采用非线性迭代结构，以字为单位进行加密运算，共进行32次轮变换。设明文输入为：，密文输出为：子密钥为，则：

为了保证加解密的一致性，在32轮变换之后，进行了一次以32bit为单位的反序变换，即：

2.2 轮密钥

SM4算法中加密算法的轮密钥由128bit的加密密钥通过密钥扩展算法生成。若加密密钥为：，则轮密钥的生成过程如下：

3 部分并行

图1 CBC模式部分并行

4 设计实现

4.1 数据帧格式说明

为了简化控制时序，实现对数据的正确处理，设计如表1所示的数据帧格式，其中ID表示具体的任务，不同的任务ID号不同；MODE表示运算需求，当MODE=0x1时，表示工作模式为ECB加密，当MODE=0x2时，表示工作模式为ECB解密，当MODE=0x3时，表示工作模式为CBC加密，当MODE=0x4时，表示工作模式为CBC解密；length表示任务包含数据的长度，单位为字节。后面紧跟算法运算的密钥和初始向量IV，然后是进行运算的数据DATA。

表1 输入数据结构

4.2 系统架构

本系统采用对称的SM4 IP核架构设计，整个系统包括输入解析模块、密钥扩展模块、反馈控制模块、SM4算法核和输出模块。反馈控制模块通过对数据运行状态的监控，实现数据在两个对称的IP核间的切换，通过两个IP核间的交叉运行，实现数据的加解密需求的并行处理。本系统支持命令和数据的连续输入，即只要两个算法核输入队列的fifo_afull信号无效，命令帧可以连续不断地输入。系统架构如图所示：

图2 CBC并行处理系统架构图

（1）输入解析模块。输入解析模块通过对命令帧的解析，实现对密钥、初始向量IV和运算数据data的提取。将密钥送入密钥扩展模块，实现密钥的扩展；将IV送入IV寄存器，等待与第一分组数据的异或操作；将同一任务下的数据data分为多个128bit的数据分组，并交叉送入两个SM4 IP核的入口队列中。若任务的长度length不足128bit的整数倍，则自动添零补齐，拆分后的分组个数送入任务长度寄存器NUM存储。通过对MODE的解析，决定输入SM4算法核的数据来源，在ECB模式下，mode1=0时，SM4入口队列的数据直接控制输入SM4算法核；在CBC模式下，mode1=1，SM4入口队列的数据通过与SM4反馈数据异或后输入SM4算法核。并产生对应的加/解密控制信号至SM4算法核，其中mode0=1时，表示加密操作，mode0=0时，表示解密操作。

（2）SM4算法核

SM4算法核采用轮迭代的数据结构，图3所示，为其中一个算法核的内部结构，由异或、非线性变换S、线性移位变换L和反序变换R构成。其中input1来自于反馈控制模块的输出，rki为密钥扩展后产生的轮密钥，cipherout1为分组数据的运算结果，rdy311、rdy321分别标识第31轮和32轮的运算状态，当其值为1时，表示此轮运算完成。F_cnt为轮计数器。

图3 SM4算法核结构图

加密模块由8个状态构成，各状态下的操作如表2所示：

表2 SM4算法核状态

本算法核的设计与传统设计的不同体现在s4状态和s6状态上。s4状态下，不同分组数据在第一轮运算时异或操作的数据不同：

当轮数f_cnt=0时，迭代结果来自于上一分组的运算结果和本次分组运算线性移位结果的异或：，否则来自于自身上一轮的轮运算结果cipherout[127：96]

S6状态将判断是否启动下一个分组和本次分组的下一轮运算并行执行。当轮数f_cnt=30时，rdy31=1，通知反馈控制模块启动另一个SM4算法核，并输出加密完成的96bit数据，供下一分组的第一轮运算。当count=31时，rdy32=1，输出反序变换后的密文。

（3）反馈控制模块

反馈控制模块用于实现数据流入和流出的控制，其内部逻辑结构如图4所示。其中cipher1、cipher2为两个算法IP核的输出，input1和input2为两个算法IP核的输入，datain为分组数据输入端，rdy311、rdy321和rdy312、rdy322分别为两个算法IP核的第31轮和32轮的运算完成状态标识。分组计数器P_cnt用于对同一任务的不同分组进行计数，用于决定进入到SM4算法核的数据以及判断同一任务是否执行完成。当P_cnt=0时，表示128bit的分组数据为任务的第一个分组，在CBC模式下，需要将分组数据datain与IV异或后，送SM4加密模块；否则，若0＜P_cnt＜num，则分组数据datain需要与前一分组的第31轮或第32轮的运算结果进行异或后送SM4加密模块进行SM4算法的第一轮和第二轮运算。

图4 反馈控制模块逻辑图

（4）输出模块

当任一个SM4算法核的rdy32为1时，表示一个分组运算完成，密文即可输出。

if rdy321='1' then cipher＜=cipher1;

elsif rdy322='1' then cipher＜=cipher2;

end if;

5 测试

为了验证设计的正确性，本文在xilinx公司的xc5vllx110t上进行了原型设计，并与已有的SM4实现方案进行了对比。

为了验证单一业务处理的速度，我们分别对1Kb、10Kb、100Kb、1000Kb的文件在CBC串行和部分并行的方式下，进行了对比测试，在相同的时钟频率下，各文件消耗的时钟数如表3所示，单个任务的平均速度提升为3%。

表3 文件运行时间对比

逻辑资源占用、系统的最高频率、吞吐率及功耗测试如表4所示。通过对比改进后的部分并行CBC模式，可以发现，改动后的程序的资源占用情况有所减少，功耗影响很小，且系统的最高工作频率没有改变。

表4 设计性能对比

?

6 结论

本文提出的分组间部分并行的设计方案，改善了CBC模式只能串行执行的不足，通过部分并行确实能提高数据的处理速度，本方案对算法原先的实现方案改动不大，可以在已有的算法优化的基础上进行，实现优化后算法核间的并行操作，且适合于多任务数据的处理，即不仅能够进行单任务SM4-CBC并行处理，也能够进行多任务SM4-CBC并行处理。但是这种并行设计方式对速度的提升有限，且只针对SM4算法，如何获得更优的改进方案是以后研究的目标。

[1]Dawei Zhang; Wenrui Ding; Ding Ding, "Fast Implementation of SMS4 Cryptographic Algorithms on Smart Card," in Intelligent Information Hiding and Multimedia Signal Processing, 2008. IIHMSP '08 International Conference on , vol., no., pp.287-290, 15-17 Aug. 2008.

[2]Shuang Qiu; Guoqiang Bai, "Power analysis of a FPGA implementation of SM4," in Computing, Communication and Networking Technologies (ICCCNT), 2014 International Conference on , vol., no., pp.1-6, 11-13 July 2014.

[3]Zhenzhou Li; Feng Li; Zhiping Jia; Lei Ju; Renhai Chen, "The Research and Application of a Specific Instruction Processor for SMS4," in Trust, Security and Privacy in Computing and Communications (TrustCom), 2012 IEEE 11th International Conference on , vol., no., pp.1883-1888, 25-27 June 2012.

[4]Zhang Lei; Li Li; Xianwei Gao; Wang Jianxin, "Design and realization of SMS4 algorithm based on MicroBlaze," in Electronic Measurement & Instruments (ICEMI), 2011 10th International Conference on , vol.1, no., pp.106-109, 16-19 Aug. 2011.

[5]Sklavos, N.; Kitsos, P., "Architectural Optimizations & Hardware Implementations of WLANs Encryption Standard," in New Technologies, Mobility and Security (NTMS), 2012 5th International Conference on , vol., no., pp.1-5, 7-10 May 2012.

[6]An ultra-high throughput and fully pipelined implementation of AES algorithm on FPGA，2015.

[7]李校南,徐岩,戴紫彬. CBC模式下SMS4算法并行化研究[J]. 计算机工程与设计,2013.

[8]刘楠,陈迅,李军伟. 面向CBC模式的AES高速芯片设计与实现[J]. 电子技术应用,2014.

[9]Meng Zhao; Guochu Shou; Yihong Hu; Zhigang Guo, "High-Speed Architecture Design and Implementation for SMS4-GCM," in Communications and Mobile Computing (CMC), 2011 Third International Conference on , vol., no., pp.15-18, 18-20 April 2011.

[10]王晨光,乔树山,黑勇. 分组密码算法SM4的低复杂度实现[J]. 计算机工程,2013.

[11]Yier Jin;Haibin Shen; Rongquan You, "Implementation of SMS4 Block Cipher on FPGA," in Communications and Networking in China, 2006. ChinaCom '06. First International Conference on , vol., no., pp.1-4, 25-27 Oct. 2006.

[12]Sklavos, N.; Kitsos, P., "Architectural Optimizations & Hardware Implementations of WLANs Encryption Standard," in New Technologies, Mobility and Security (NTMS), 2012 5th International Conference on , vol., no., pp.1-5, 7-10 May 2012.