基于FPGA的SM3算法优化设计与实现

基于FPGA的SM3算法优化设计与实现王晓燕1，杨先文2(1.河南中医学院学生工作部(处)，河南郑州450008；2.解放军信息工程大学电子技术学院，河南郑州450004)摘要：针对国家密码管理局发布的SM3密码杂凑算法，文章对其基本流程进行了概括。基于FPGA实现平台，提出了SM3算法IP核设计的整体架构，并讨论了其关键逻辑的优化设计。选用Altera公司Cyclone系列器件作为目标器件，与已有研究成果进行了实现比较。结果显示SM3算法的IP核实现性能优越，可为密码SoC产品的开发提供算法引擎支持。关键词：密码杂凑算法；片上系统(SoC)；关键路径；优化设计；IP核；现场可编程门阵列(FPGA)OptimizationDesignandImplementationofSM3AlgorithmBasedonFPGAWANGXiao-yan1,YANGXian-wen2(1.HenanUniversityofTraditionalChineseMedicine,Zhengzhou450008,China;2.InstituteofElectronicTechnology,PLAInformationEngineeringUniversity,Zhengzhou450004,China;)【Abstract】AimingatSM3cryptographichashalgorithmreleasedbyStateCryptographyAdministration,thegeneralworkingflowofthealgorithmissummarizedinthispaper.BasedonFPGAplatform,theIParchitectureoftheSM3isproposed,andtheoptimizationdesignofitsrelevantcrucialpathisdiscussed.ChoosingthreeCycloneFPGAsofAlteracorporationasthetargetdevices,thefastimplementationoftheSM3isachievedandiscomparedwithsomeotherexistingresearchfruits.ComparisonresultsindicatethattheIPimplementationoftheSM3hasasuperiorperformance,anditcanprovidethealgorithmengineforthedevelopmentofcryptographySoCproductsinpractice.【Keywords】Cryptographichashalgorithm;SystemonChip(SoC);Crucialpath;Optimizationdesign;IPcore;FieldProgrammableGateArray(FPGA)DOI:10.3969/j.issn.1000-3428.2011.19.000计算机工程ComputerEngineering第37卷第19期Vol.37No.192011年10月October2011文章编号：1000—3428(2011)19—00—0文献标识码：A中图分类号：TP309.11概述杂凑算法又称为Hash函数、散列函数，它是能够将任意有限长的输入消息映射为固定长度的输出值并且计算容易的一类函数[1]。杂凑函数是现代密码学中一类重要的基础算法，在构建信息安全系统的过程中，提供了数据完整性认证和对消息源进行认证的支撑功能。杂凑函数一般采用分组迭代的设计方法，如国际上已有的典型杂凑算法均采用MD类型分组迭代结构，其中以SHA-1算法和SHA-256/384/512算法为代表。该类算法具有压缩函数非线性度高、消息填充和分组强等优点，但也存在威胁安全性的缺点[2]。为此，研究人员致力于并行模式杂凑算法的设计、分析和构造，并由国家密码管理局于2010年12月22日最终发布了适用于商用密码应用的SM3密码杂凑算法[3]。本文基于现场可编程门阵列(FieldProgrammableGateArray,FPGA)器件完成了SM3算法的优化设计与快速实现，并以IP软核的形式为实际密码SoC产品的开发提供SM3算法引擎支持。2SM3算法介绍SM3密码杂凑算法是一种基于分组迭代结构的杂凑算法，该算法采用消息双字结合的消息字处理方式，使用来自不同群运算的混合，实现了消息在局部范围内快速扩散和混乱，有效防止了比特追踪及其它已知分析方法的攻击。SM3算法安全性好、结构新颖，适合软硬件和智能卡实现。针对长度为l(l264)比特的报文消息，SM3杂凑算法经过填充和迭代压缩，生成杂凑值，杂凑值长度为256比特，其具体处理过程可概括为以下四个步骤[3]：步骤1：消息填充。假设报文消息m的长度为l比特，首先将比特“1”添加到消息的末尾，再添加k个“0”，其中k是满足l+1+k=448mod512的最小的非负整数；然后再添加一个64位比特串，该比特串是长度l的二进制表示。填充后的报文消息m'的比特长度为512的倍数。步骤2：初始化缓冲区。SM3函数的中间结果和最终结果保存于256比特的缓冲区中，缓冲区用8个32位的寄存器A、B、C、D、E、F、G、H表示，并将寄存器初始化为下列32比特的整数：A=7380166f，B=4914b2b9，C=172442d7，D=da8a0600，E=a96f30bc，F=163138aa，G=e38dee4d，H=b0fb0e4e。步骤3：消息迭代压缩。将填充后的消息m'按512比特进行分组：m'=B(0)B(1)...B(n−1)。对m'按下列方式迭代：V(i+1)=CF(V(i),B(i))。其中，CF是由64步迭代运算组成，每步都以寄存器A、B、C、D、E、F、G、H为输入，然后更新缓存内容。每步使用32位常数Wj和Wj'，它们是由消息分组B(i)按消息扩展规则迭代产生。压缩函数主要涉及到的运算包括：基金项目：现代通信国家重点实验室基金(9140C1106021006)，郑州市科技创新型科技人才队伍建设工程(096SYJH21099)作者简介：王晓燕(1978－)，女，讲师，硕士研究生，主研方向：信息安全和图像处理；杨先文，博士研究生收稿日期：2010-0-0E-mail：[e-mail]2011-08-1209:40:40计算机工程2011年10月5日1((12)())721(12)1(,,)2'2(,,)1jjjjjSSAETjSSSSATTFFABCDSSWTTGGEFGHSSW!其中FFj(·)和GGj(·)是两个布尔函数运算，Tj是常量。同时为提高扩散速率，引入了P0/P1扩散技术，达到了扩散速度快效果好的优点。步骤4：杂凑值输出。所有512比特的分组处理完毕后，最后一个512比特分组的输出即是消息摘要值。3整体架构设计在SM3算法的电路设计中采用计算机辅助设计技术(CAD)，借助自上至下的设计方法可完成算法IP核整体设计。从系统的总体要求出发，自上至下地逐步将设计内容细化，最终得到的SM3算法模块化架构设计如图1所示，主要包括消息扩展逻辑、压缩函数逻辑、压缩函数寄存器，以及控制电路组成。其中，压缩函数逻辑又包括运算电路、常量Tj生成电路等逻辑组成，控制电路中的核心部件为一个满64归零的迭代计数器。需要说明的是，对应SM3杂凑算法描述中的消息填充，本文是将其以上层软件控制的形式实现，因此节约了硬件开销。图1SM3算法整体架构设计该IP核的工作原理是：报文消息经过填充模块填充为512的整数倍长度后，按512比特进行分组，并将分组消息输入到IP核消息扩展逻辑，同时时钟信号、复位信号、使能信号进入到控制电路；依据消息扩展原理，消息扩展逻辑输出Wj和Wj'至压缩函数逻辑，在控制电路的控制下，各压缩函数逻辑子电路协调工作，经过64个时钟周期迭代，最终将256比特缓冲区数据存储于压缩函数寄存器，同时置分组完成信号有效，置使能输入无效；当调度程序检测到分组完成信号有效时，判断所有分组消息是否已经处理完毕，若没有处理完则将下一分组消息输入至IP核，然后置使能信号有效，并等待分组完成信号有效，否则压缩函数寄存器中的数据即为摘要值，依次将其输出即可。4关键逻辑优化设计4.1控制电路控制电路主要包括三个功能：1)接收外界时钟信号、复位信号、使能信号，为各功能模块配置时钟驱动信号和相应的控制信号；2)满64归零计数迭代次数，为消息扩展逻辑和压缩函数逻辑配置正确的迭代轮数；3)当迭代计数器满64归零的同时配置分组完成信号，并将其输出至调度程序。4.2消息扩展逻辑根据算法，消息扩展的具体过程是：1)将消息分组B(i)划分为16个字W0,W1,…,W15。2)FORj=16TO6711693136((15))(7)jjjjjjWP∀∀∀∀∀!!!!ENDFOR3)FORj=0TO634'jjj!ENDFOR图2消息扩展逻辑设计对应上述原理，消息扩展逻辑的具体设计如图2所示，其中采用了16级字移位寄存器作为生成132个字的缓存区。首先将消息分组B(i)划分为16个字后依次作为16级字移存器的初始值，然后每个时钟周期移存器左移一个字，同时按图示位置抽取寄存器的值参与逻辑运算，并将结果作为W15的更新值。抽取W0作为本轮Wj的输出，抽取W0和W4异或后作为本轮Wj'的输出。4.3压缩函数逻辑依据压缩函数计算过程，压缩函数逻辑设计如图3所示，其关键逻辑可分为常量Tj生成电路、FFj函数电路、GGj函数电路、256比特缓存区、以及运算电路。常量Tj生成电路主要包括两个常量寄存器，根据迭代计数器的输出选择不同轮数对应的常量Tj，同时为了减少压缩函数计算过程中(Tjj)的复杂性，每个时钟周期中常量寄存器左移一位。FFj函数电路和GGj函数电路分别是根据如下布尔函数搭建的组合逻辑。(,,)()()()jABCFFABCABACBC!!#∃%&∋&∋&(0151663jj≤≤≤≤(,,)()()jEFGFFEFGEFEG!!#∃%&∋)&(0151663jj≤≤≤≤256比特缓存区对应计算过程描述中的A、B、C、D、E、F、G、H表示，用以接收迭代处理结果值。运算电路对应计算过程描述中组件调用、移位操作、逻辑运算和算术运算的集合，它的优化设计决定了压缩函数逻辑设计的整体性能。图3压缩函数逻辑设计运算电路中组件调用、移位操作只是简单的布线，逻辑运算也是简单的门级电路，它们占用关键路径的时间延迟相对32位全加器而言可忽略不计。由于运算电路最长关键路径是计算P0(TT2)，在这一过程中，影响效率主要是多次加法运算带来的时间延迟。因此，主要是对加法电路设计进行了优化。第37卷第19期3王晓燕，杨先文：基于FPGA的SM3算法优化设计与实现由于最长关键路径的计算过程为：1((12)())7jSSAETj，2(,,)1jjTTGGEFGHSSW，0(2)EPTT。因此关键运算延迟主要是由计算SS1和TT2两级加法引起的。虽然描述中计算SS1和TT2是顺序执行的，但是硬件实现时由于进程间并行执行的可操作性强，计算SS1和计算(,,)jjGGEFGHW可同时执行。此外，由于传统进位加法电路(CPA)会产生进位延迟，因此应尽量对其进行优化。借助2个进位保存加法器(CSA)[4]和3个超前进位加法器(CLA)[4,5]，计算TT2加法电路实现原理如图4(b)所示，在牺牲不多硬件资源的前提下，加法电路的关键路径延迟较传统进位加法电路要小很多。$12+:MCPACP