介绍

SM3与SHA-256

SHA安全加密标准是目前国际上使用最广泛的、较安全的杂凑系列算法,由美国国家标准与技术研究院（National Institute of Standards and Technology,NIST）和美国国家安全局（National Security Agency,NSA）两个单位共同开发。2004年,中国密码专家王小云教授研究小组宣布破解MD5、SHA-1等算法。考虑安全性问题,美国政府自2010年不再使用SHA-1算法,全面推广使用SHA-256、SHA-384和SHA-512等算法。2010年12月17日,中国国家密码管理局公布杂凑算法商用标准——SM3杂凑算法。

SM3与SHA系列算法的整体步骤相同,SM3算法包括消息填充、迭代压缩、得到杂凑值3个步骤。相较于SHA-256,SM3算法的压缩函数中增加了消息双字介入、P置换等设计,压缩函数更复杂,可抵抗强碰撞性的差分分析、弱碰撞性的线性分析等密码分析攻击。鉴于压缩函数设计的复杂性,可以认为SM3的安全性比SHA-256的安全性略高。

算法计算量

SM3与SHA-256的算法结构相似、步骤相同,主要区别在于核心的迭代压缩步骤,该步骤包含消息扩展和状态更新两个子步骤。

两种算法均采用移位运算、逻辑运算、模232算数加的混合运算方法,但运算量不同。对两种算法的总体运算量做具体统计分析,将比特移位运算记为SH,将字（32 bit）与、或、异或、非等逻辑运算统一记为LO,将字模232算数加运算记为MA,得到SM3与SHA-256的迭代压缩步骤计算量对比如表1所示。

表1 SM3与SHA-256的迭代压缩步骤计算量对比

杂凑算法 消息扩展 状态更新 合计
SM3 416SH+584LO 1024SH+1328LO+ 384MA 1440SH+1912LO+ 384MA
SHA-256 480SH+384LO+ 144MA 768SH+1152LO+ 256MA 1248SH+1536LO+ 400MA

由表1可知,SHA-256算法的模数运算相对较多,而SM3算法的移位、逻辑运算等简单运算较多,其中模数运算比移位或逻辑运算等简单运算更耗时。总体而言,SM3的总体计算量与SHA-256相近。

算法性能测试分析

算法性能对比

对A厂商SM3、OpenSSL SM3和SHA-256算法的C语言实现进行性能测试,循环次数N=5000,分别测试在12组不同输入长度情况下两种算法的运行时间比（以SHA-256为基准）,其中部分数据如表2所示。

表2 在不同输入长度下A厂商SM3、OpenSSL SM3与SHA-256的运行时间比

输入长度 A厂商SM3/SHA-256 OpenSSL SM3/SHA-256
8 B 1.3819 1.8048
64 B 1.2329 1.8392
256 B 1.1652 1.9581
1 KB 1.1295 2.0152
512 KB 1.1181 2.0292
1 MB 1.1160 2.0546

根据表2可知,A厂商SM3和OpenSSL SM3算法的耗时均略多于SHA-256算法,但两种SM3算法的软件性能相近,这与算法计算量分析结论相符。

优化对算法性能的影响

考虑在实际应用中,多数工具套件一般采用多种优化方法,使特定密码算法达到最优的运行效率。因此,对SM3和SHA-256算法分别进行优化后与优化前的性能对比测试。SM3与SHA-256算法的优化效果对比如图1所示,图1中每个点的值代表相应算法经优化后的系统吞吐量（Transactions Per Second,TPS）与优化前的系统吞吐量的比值,系统吞吐量由该输入长度下算法处理数据次数除以运行耗时计算得出。

图1
SM3与SHA-256算法的优化效果对比

由图1可以看出,SHA-256算法取得了良好的优化效果,优化后的性能约为优化前的两倍,SM3算法的性能则有所下降。

经分析发现,SHA-256算法在gcc编译器的O3级优化、宏定义等多种优化方法的作用下,取得了较好的优化效果,算法性能得到明显提升。以宏定义优化方法为例,将SHA-256算法的_asm块定义为C宏,在C代码中嵌入利用SIMD（Single Instruction Multiple Data,单指令多数据流）技术的汇编代码,进而实现算法优化。

结合算法性能对比的测试分析结果可知,SM3算法的性能应与SHA-256算法相近。由优化对算法性能的测试情况可知,优化后的SHA-256算法使其软件性能得到较大提升,但SM3算法的性能下降。由此可见,通过算法优化,SHA-256杂凑算法的性能明显高于SM3算法,SM3算法没有通过编译进行优化的能力,需要进一步进行分析。

参考资料