第10卷第6期 智能系统学报 Vol.10 No.6 2015年12月 CAAI Transactions on Intelligent Systems Dee.2015 D0L:10.11992/is.201507036 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20151110.1354.004.html SM3杂凑算法的软件快速实现研究 杨先伟，康红娟2 (1.无锡职业技术学院基础部，江苏无锡214121：2.四川长虹电器股份有限公司，四川成都610041) 摘要：杂凑算法是密码学中最基本的模块之一，可广泛应用于密码协议、数字签名、消息鉴别等领域。我国国家密 码管理局在2010年发布了SM3密码杂凑算法，该算法适用于商用密码应用中的数字签名和验证、消息认证码的生 成与验证以及随机数的生成等。该文重点研究SM3密码杂凑算法的软件快速实现，根据算法本身的特点，尤其是压 缩函数的特点，给出一种更加适用于软件的快速实现方式。实验表明利用此方法可以将算法的效率提升60%左右。 关键词：SM3算法：杂凑函数：软件快速实现：数字签名：消息鉴别；完整性认证：数字指纹；压缩函数 中图分类号：TP309文献标志码：A文章编号：1673-4785(2015)06-0954-06 中文引用格式：杨先伟，康红娟.SM3杂凑算法的软件快速实现研究[J].智能系统学报，2015,10(6)：954-959. 英文引用格式：YANG Xianwei,KANG Hongjuan.Fast software implementation of SM3 Hash algorithm[J].CAAI Transactions on Intelligent Systems,2015,10(2):954-959. Fast software implementation of SM3 Hash algorithm YANG Xianwei',KANG Hongjuan? (1.Department of Fundamental Courses,Wuxi Prof Technology inst.,Wuxi 214121,China;2.Sichuan Changhong Electric Co., Ltd.,Chengdu 610041,China) Abstract:The hash algorithm is one of the most basic cryptography modules,and is widely used in cryptographic protocols,digital signatures,message authentication,and in other fields.The Chinese National Cryptography Ad- ministration released the SM3 hash algorithm in 2010.This algorithm is applied to digital signature and verification, the generation and verification of message authentication codes,and random number generation.This paper addres- ses the fast software implementation of the SM3 algorithm.Based on the SM3 features,and especially its compres- sion function characteristics,we propose a method that is highly suitable for fast software implementation.Experi- mental results show that this method can improve the implementation speed by 60%. Keywords:SM3 algorithm;hash function;fast software implementation;digital signature;message authentication; integrity authentication;digital fingerprint;compression function 哈希(Hash)函数，也叫杂凑函数，是密码学中 程软硬件均易于计算实现，但其逆向变换过程在计 最基本的模块之一，广泛应用于密码协议、数字签 算上不可行，即具有单向性。出于安全性的考虑，杂 名、消息鉴别、完整性认证等领域。因此，它在密码 凑函数还必须满足抗弱碰撞性和抗强碰撞性。1991 学中扮演着极其重要的角色。 年，Ron Rivest提出了MD5算法，这曾经是使用最为 杂凑函数的目的是产生数据块的“指纹”，它可 广泛的杂凑算法。从20世纪90年代年开始，美国 以对任意长度的信息产生定长的输出。这个变换过 国家标准与技术研究院(NST)陆续公布了SHA系 收稿日期：2015-07-23.网络出版日期：2015-11-10 列，并通过公开竞赛方式征集SHA-3。 基金项目：国家自然科学基金资助项目(11471144) 中国国家密码管理局在2010年发布了SM3密 通信作者：杨先伟.E-mail:yangxianwei2018@163.com
第 １０ 卷第 ６ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．６ ２０１５ 年 １２ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｄｅｃ． ２０１５ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１５０７０３６ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１５１１１０．１３５４．００４．ｈｔｍｌ ＳＭ３ 杂凑算法的软件快速实现研究 杨先伟１ ，康红娟２ （１． 无锡职业技术学院 基础部，江苏 无锡 ２１４１２１； ２． 四川长虹电器股份有限公司，四川 成都 ６１００４１） 摘 要：杂凑算法是密码学中最基本的模块之一，可广泛应用于密码协议、数字签名、消息鉴别等领域。 我国国家密 码管理局在 ２０１０ 年发布了 ＳＭ３ 密码杂凑算法，该算法适用于商用密码应用中的数字签名和验证、消息认证码的生 成与验证以及随机数的生成等。 该文重点研究 ＳＭ３ 密码杂凑算法的软件快速实现，根据算法本身的特点，尤其是压 缩函数的特点，给出一种更加适用于软件的快速实现方式。 实验表明利用此方法可以将算法的效率提升 ６０％左右。 关键词：ＳＭ３ 算法；杂凑函数；软件快速实现； 数字签名；消息鉴别；完整性认证；数字指纹； 压缩函数 中图分类号：ＴＰ３０９ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０６⁃０９５４⁃０６ 中文引用格式：杨先伟，康红娟． ＳＭ３ 杂凑算法的软件快速实现研究［Ｊ］． 智能系统学报， ２０１５， １０（６）： ９５４⁃９５９． 英文引用格式：ＹＡＮＧ Ｘｉａｎｗｅｉ， ＫＡＮＧ Ｈｏｎｇｊｕａｎ． Ｆａｓｔ ｓｏｆｔｗａｒｅ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ＳＭ３ Ｈａｓｈ ａｌｇｏｒｉｔｈｍ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（２）： ９５４⁃９５９． Ｆａｓｔ ｓｏｆｔｗａｒｅ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ＳＭ３ Ｈａｓｈ ａｌｇｏｒｉｔｈｍ ＹＡＮＧ Ｘｉａｎｗｅｉ １ ， ＫＡＮＧ Ｈｏｎｇｊｕａｎ ２ （１． Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｆｕｎｄａｍｅｎｔａｌ Ｃｏｕｒｓｅｓ， Ｗｕｘｉ Ｐｒｏｆ Ｔｅｃｈｎｏｌｏｇｙ ｉｎｓｔ．， Ｗｕｘｉ ２１４１２１， Ｃｈｉｎａ； ２． Ｓｉｃｈｕａｎ Ｃｈａｎｇｈｏｎｇ Ｅｌｅｃｔｒｉｃ Ｃｏ．， Ｌｔｄ．， Ｃｈｅｎｇｄｕ ６１００４１， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｈａｓｈ ａｌｇｏｒｉｔｈｍ ｉｓ ｏｎｅ ｏｆ ｔｈｅ ｍｏｓｔ ｂａｓｉｃ ｃｒｙｐｔｏｇｒａｐｈｙ ｍｏｄｕｌｅｓ， ａｎｄ ｉｓ ｗｉｄｅｌｙ ｕｓｅｄ ｉｎ ｃｒｙｐｔｏｇｒａｐｈｉｃ ｐｒｏｔｏｃｏｌｓ， ｄｉｇｉｔａｌ ｓｉｇｎａｔｕｒｅｓ， ｍｅｓｓａｇｅ ａｕｔｈｅｎｔｉｃａｔｉｏｎ， ａｎｄ ｉｎ ｏｔｈｅｒ ｆｉｅｌｄｓ． Ｔｈｅ Ｃｈｉｎｅｓｅ Ｎａｔｉｏｎａｌ Ｃｒｙｐｔｏｇｒａｐｈｙ Ａｄ⁃ ｍｉｎｉｓｔｒａｔｉｏｎ ｒｅｌｅａｓｅｄ ｔｈｅ ＳＭ３ ｈａｓｈ ａｌｇｏｒｉｔｈｍ ｉｎ ２０１０． Ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｉｓ ａｐｐｌｉｅｄ ｔｏ ｄｉｇｉｔａｌ ｓｉｇｎａｔｕｒｅ ａｎｄ ｖｅｒｉｆｉｃａｔｉｏｎ， ｔｈｅ ｇｅｎｅｒａｔｉｏｎ ａｎｄ ｖｅｒｉｆｉｃａｔｉｏｎ ｏｆ ｍｅｓｓａｇｅ ａｕｔｈｅｎｔｉｃａｔｉｏｎ ｃｏｄｅｓ， ａｎｄ ｒａｎｄｏｍ ｎｕｍｂｅｒ ｇｅｎｅｒａｔｉｏｎ． Ｔｈｉｓ ｐａｐｅｒ ａｄｄｒｅｓ⁃ ｓｅｓ ｔｈｅ ｆａｓｔ ｓｏｆｔｗａｒｅ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ｔｈｅ ＳＭ３ ａｌｇｏｒｉｔｈｍ． Ｂａｓｅｄ ｏｎ ｔｈｅ ＳＭ３ ｆｅａｔｕｒｅｓ， ａｎｄ ｅｓｐｅｃｉａｌｌｙ ｉｔｓ ｃｏｍｐｒｅｓ⁃ ｓｉｏｎ ｆｕｎｃｔｉｏｎ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ， ｗｅ ｐｒｏｐｏｓｅ ａ ｍｅｔｈｏｄ ｔｈａｔ ｉｓ ｈｉｇｈｌｙ ｓｕｉｔａｂｌｅ ｆｏｒ ｆａｓｔ ｓｏｆｔｗａｒｅ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ． Ｅｘｐｅｒｉ⁃ ｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｉｓ ｍｅｔｈｏｄ ｃａｎ ｉｍｐｒｏｖｅ ｔｈｅ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｓｐｅｅｄ ｂｙ ６０％． Ｋｅｙｗｏｒｄｓ： ＳＭ３ ａｌｇｏｒｉｔｈｍ； ｈａｓｈ ｆｕｎｃｔｉｏｎ； ｆａｓｔ ｓｏｆｔｗａｒｅ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ； ｄｉｇｉｔａｌ ｓｉｇｎａｔｕｒｅ； ｍｅｓｓａｇｅ ａｕｔｈｅｎｔｉｃａｔｉｏｎ； ｉｎｔｅｇｒｉｔｙ ａｕｔｈｅｎｔｉｃａｔｉｏｎ； ｄｉｇｉｔａｌ ｆｉｎｇｅｒｐｒｉｎｔ； ｃｏｍｐｒｅｓｓｉｏｎ ｆｕｎｃｔｉｏｎ 收稿日期：２０１５⁃０７⁃２３． 网络出版日期：２０１５⁃１１⁃１０． 基金项目：国家自然科学基金资助项目（１１４７１１４４）． 通信作者：杨先伟． Ｅ⁃ｍａｉｌ：ｙａｎｇｘｉａｎｗｅｉ２０１８＠ １６３．ｃｏｍ． 哈希（Ｈａｓｈ）函数，也叫杂凑函数，是密码学中 最基本的模块之一，广泛应用于密码协议、数字签 名、消息鉴别、完整性认证等领域。 因此，它在密码 学中扮演着极其重要的角色。 杂凑函数的目的是产生数据块的“指纹”，它可 以对任意长度的信息产生定长的输出。 这个变换过 程软硬件均易于计算实现，但其逆向变换过程在计 算上不可行，即具有单向性。 出于安全性的考虑，杂 凑函数还必须满足抗弱碰撞性和抗强碰撞性。 １９９１ 年，Ｒｏｎ Ｒｉｖｅｓｔ 提出了 ＭＤ５ 算法，这曾经是使用最为 广泛的杂凑算法。 从 ２０ 世纪 ９０ 年代年开始，美国 国家标准与技术研究院（ＮＩＳＴ）陆续公布了 ＳＨＡ 系 列［１］ ，并通过公开竞赛方式征集 ＳＨＡ⁃３ ［２］ 。 中国国家密码管理局在 ２０１０ 年发布了 ＳＭ３ 密
第6期 杨先伟，等：SM3杂凑算法的软件快速实现研究 ·955· 码杂凑算法)，该算法适用于商用密码中的多种应 1.1函数 用，满足多种密码应用的安全需求：1)数字签名和验 布尔函数FF(X,Y,Z)、GG(X,Y,Z), 证，如作为SM2算法中数字签名所需的杂凑函数；2) 0≤i≤63的定义如下： 消息认证码的生成与验证，消息认证码不仅可以使用 FF (X,Y,Z)= 分组密码算法基于特定的工作模式生成，也可以使用 (X①Y①Z,0≤i≤15 SM3等杂凑函数生成：3)随机数的生成。 l(XA)V(X∧Z)V(Y∧Z),16≤i≤63 哈希函数在各种平台和环境下的执行效率 GG(X,Y,Z)= 是非常重要的考量指标之一，比如服务器端常需 X⊕Y①Z,0≤i≤15 执行的SSL/TLS协议就使用了哈希函数进行认 (X∧Y)V(XΛZ),16≤i≤63 证。目前已有大量文章对SHA系列算法的软件 置换函数P。(X)和P,(X)的定义如下： 快速实现进行研究，比如Aciicmez)提出基于 P(X)=X⊕(X<<<9)⊕(X<<<17) SIMD技术快速实现哈希算法，Gueron等[s-6]对并 P(X)=X⊕(X<<<15)⊕(X<<<23) 行处理多个消息的情况进行了研究。同样也有 1.2填充 大量文章对SM3算法的软硬件快速实现进行研 设消息的长度为（比特。填充方式为：首先将 究。张倩等)提出了一种ASIC高效实现架构： 比特“1”添加到消息的末尾；然后添加k个“0”，k 王晓燕等[劉基于FPGA设计SM3算法P核的整 是满足l+1+k=448mod512的最小的非负整数； 体架构，对关键逻辑进行优化设计：伍娟[町以同 最后再将消息长度1的64位二进制表示添加在最 方公司THD86智能卡芯片为硬件平台实现了 末。填充后的消息比特长度为512的倍数。 SM3算法：曾小波等[1o1分析了基于8051软核的 1.3迭代压缩 SM3算法P原理、设计流程及实现方案，该方案 填充后的消息m'按512比特进行分组：m'= 在时序和面积上均做到相当程度的优化，并提高 B)I…‖Ba-.对每个分组利用压缩函数CF进 了算法的效率：沈一公等[基于Android平台研 行迭代： 究了SM3算法的快速实现，并以此为基础研究文 FORi=0TOn-1 件防篡改以便检查手机软件的安装；易叔贤 i+I)←-CF(o,B0) 等[2]结合已经将SM系列算法纳入其中的PBOC END FOR 3.0新规范，分析考虑SM2、SM3、SM4算法在金 1.4压缩函数 融IC卡领域的实现和应用。 压缩函数CF的计算过程如下： 与这些研究相比，文本研究的侧重点是SM3算 首先，计算消息扩展字W:,0≤i≤67和W:', 法在普通软件平台下的快速实现方式。文本根据算 0≤i≤63，步骤如下： 法以及压缩函数的特点，给出一种更加适用于软件 Wo‖…‖Ws=B) 快速实现的算法描述方式和实现方法，本文提出的 F0Ri=16T067 实现方法具有以下优点：首先，此方法避免了普通实 W:←-P,(W-6①W-g①(W-3<<<15)① 现中可能采用的效率较低的实现架构和运算方式， (W-3<<<7)⊕W-6 可较大地提高算法的软件效率，经多个软件平台对 END FOR 比测试，本文的实现方法可将算法效率提升60%左 F0Ri=0T063 右；其次，此方式不基于特定的软件平台、架构、指令 W:←-W,⊕W+4 等，具有很强的跨平台性和兼容性。 END FOR 然后，进行包含64轮迭代的压缩，步骤如下： 1SM3算法简介 A‖BIC IDI EI F I GIH←-) SM3杂凑算法可将长度小于24比特的消息 F0Ri=0T063 经过填充、反复的消息扩展和压缩，生成长度为 SS,←-((A<<<12)+E+(T<<<j)) 256比特的杂凑值。在SM3算法中，字表示长度 <<<7 为32的比特串。 SS2←SS1④(A<<<12)
码杂凑算法［３］ ，该算法适用于商用密码中的多种应 用，满足多种密码应用的安全需求：１）数字签名和验 证，如作为 ＳＭ２ 算法中数字签名所需的杂凑函数；２） 消息认证码的生成与验证，消息认证码不仅可以使用 分组密码算法基于特定的工作模式生成，也可以使用 ＳＭ３ 等杂凑函数生成；３）随机数的生成。 哈希函数在各种平台和环境下的执行效率 是非常重要的考量指标之一，比如服务器端常需 执行的 ＳＳＬ ／ ＴＬＳ 协议就使用了哈希函数进行认 证。 目前已有大量文章对 ＳＨＡ 系列算法的软件 快速 实 现 进 行 研 究， 比 如 Ａｃｉｉçｍｅｚ ［ ４］ 提 出 基 于 ＳＩＭＤ 技术快速实现哈希算法，Ｇｕｅｒｏｎ 等［ ５⁃６］ 对并 行处理多个消息的情况进行了研究。 同样也有 大量文章对 ＳＭ３ 算法的软硬件快速实现进行研 究。 张倩等［ ７］ 提出了一种 ＡＳＩＣ 高效实现架构； 王晓燕等［ ８］ 基于 ＦＰＧＡ 设计 ＳＭ３ 算法 ＩＰ 核的整 体架构，对关键逻辑进行优化设计；伍娟［ ９］ 以同 方公司 ＴＨＤ８６ 智 能 卡 芯 片 为 硬 件 平 台 实 现 了 ＳＭ３ 算法；曾小波等［ １０］ 分析了基于 ８０５１ 软核的 ＳＭ３ 算法 ＩＰ 原理、设计流程及实现方案，该方案 在时序和面积上均做到相当程度的优化，并提高 了算法的效率；沈一公等［ １１］ 基于 Ａｎｄｒｏｉｄ 平台研 究了 ＳＭ３ 算法的快速实现，并以此为基础研究文 件防 篡 改 以 便 检 查 手 机 软 件 的 安 装； 易 叔 贤 等［ １２］ 结合已经将 ＳＭ 系列算法纳入其中的 ＰＢＯＣ ３．０ 新规范，分析考虑 ＳＭ２、 ＳＭ３、 ＳＭ４ 算法在金 融 ＩＣ 卡领域的实现和应用。 与这些研究相比，文本研究的侧重点是 ＳＭ３ 算 法在普通软件平台下的快速实现方式。 文本根据算 法以及压缩函数的特点，给出一种更加适用于软件 快速实现的算法描述方式和实现方法，本文提出的 实现方法具有以下优点：首先，此方法避免了普通实 现中可能采用的效率较低的实现架构和运算方式， 可较大地提高算法的软件效率，经多个软件平台对 比测试，本文的实现方法可将算法效率提升 ６０％左 右；其次，此方式不基于特定的软件平台、架构、指令 等，具有很强的跨平台性和兼容性。 １ ＳＭ３ 算法简介 ＳＭ３ 杂凑算法可将长度小于 ２ ６４ 比特的消息 经过填充、反复的消息扩展和压缩，生成长度为 ２５６ 比特的杂凑值。 在 ＳＭ３ 算法中，字表示长度 为 ３２ 的比特串。 １．１ 函数 布 尔 函 数 ＦＦｉ（Ｘ，Ｙ，Ｚ） 、 ＧＧｉ（Ｘ，Ｙ，Ｚ） ， ０ ≤ ｉ ≤６３ 的定义如下： ＦＦｉ（Ｘ，Ｙ，Ｚ） ＝ Ｘ Ｙ Ｚ，０ ≤ ｉ ≤ １５ （Ｘ ∧ Ｙ） ∨ （Ｘ ∧ Ｚ） ∨ （Ｙ ∧ Ｚ），１６ ≤ ｉ ≤ ６３ { ＧＧｉ（Ｘ，Ｙ，Ｚ） ＝ Ｘ Ｙ Ｚ，０ ≤ ｉ ≤ １５ （Ｘ ∧ Ｙ） ∨ （¬ Ｘ ∧ Ｚ），１６ ≤ ｉ ≤ ６３ { 置换函数 Ｐ０（Ｘ） 和 Ｐ１（Ｘ） 的定义如下： Ｐ０（Ｘ） ＝ Ｘ （Ｘ ＜ ＜ ＜ ９） （Ｘ ＜ ＜ ＜ １７） Ｐ１（Ｘ） ＝ Ｘ （Ｘ ＜ ＜ ＜ １５） （Ｘ ＜ ＜ ＜ ２３） １．２ 填充 设消息的长度为 ｌ 比特。 填充方式为：首先将 比特“１”添加到消息的末尾；然后添加 ｋ 个“０”， ｋ 是满足 ｌ ＋ １ ＋ ｋ ＝ ４４８ ｍｏｄ ５１２ 的最小的非负整数； 最后再将消息长度 ｌ 的 ６４ 位二进制表示添加在最 末。 填充后的消息比特长度为 ５１２ 的倍数。 １．３ 迭代压缩 填充后的消息 ｍ′ 按 ５１２ 比特进行分组： ｍ′ ＝ Ｂ （０）‖…‖Ｂ （ｎ－１） ．对每个分组利用压缩函数 ＣＦ 进 行迭代： ＦＯＲ ｉ ＝ ０ ＴＯ ｎ － １ Ｖ （ｉ＋１） ← ＣＦ（Ｖ （ｉ） ，Ｂ （ｉ） ） ＥＮＤ ＦＯＲ １．４ 压缩函数 压缩函数 ＣＦ 的计算过程如下： 首先，计算消息扩展字 Ｗｉ，０ ≤ ｉ ≤ ６７ 和 Ｗｉ ′， ０ ≤ｉ ≤ ６３，步骤如下： Ｗ０‖…‖Ｗ１５ ＝ Ｂ （ｉ） ＦＯＲ ｉ ＝ １６ ＴＯ ６７ Ｗｉ ← Ｐ１（Ｗｉ－１６ Ｗｉ－９ （Ｗｉ－３ ＜ ＜ ＜ １５）） （Ｗｉ－１３ ＜ ＜ ＜ ７） Ｗｉ－６ ＥＮＤ ＦＯＲ ＦＯＲ ｉ ＝ ０ ＴＯ ６３ Ｗ′ｉ ← Ｗｉ Ｗｉ＋４ ＥＮＤ ＦＯＲ 然后，进行包含 ６４ 轮迭代的压缩，步骤如下： Ａ‖Ｂ‖Ｃ‖Ｄ‖Ｅ‖Ｆ‖Ｇ‖Ｈ ← Ｖ （ｉ） ＦＯＲ ｉ ＝ ０ ＴＯ ６３ ＳＳ１ ← （（Ａ ＜ ＜ ＜ １２） ＋ Ｅ ＋ （Ｔｊ ＜ ＜ ＜ ｊ）） ＜ ＜ ＜ ７ ＳＳ２ ← ＳＳ１ （Ａ ＜ ＜ ＜ １２） 第 ６ 期 杨先伟，等：ＳＭ３ 杂凑算法的软件快速实现研究 ·９５５·
·956· 智能系统学报 第10卷 TT-FF (A,B,C)+D SS2 +W' 了字W。,…,W。和W。,…,W的加载和存储次 TT2+GG(E,F,G)+H SS W 数，提高了消息扩展的速度。 D←-C 2.2压缩函数的快速实现 C←-B>>32, F←E EIF‖GIH←-(EIFIGIH)>>>32。为了减 E←-P(TT2) 少循环移位导致的不必要的赋值运算，可以将字的 END FOR 循环右移变更每轮输入字顺序的变动，且这个顺序 +)←V⊕(AIBICID‖EIFIGIH) 变动会在4轮后还原，具体情况如下（以下用 1.5输出杂凑值 OneRound(·)表示一轮压缩)： 256比特杂凑值y的计算方式为 OneRound(i+0,A,B,C,D,E,F,G,H,W) y←(AIBICIDIEIFIGIH)←O OneRound(i +1,D,A,B,C,H,E,F,G,W) 2软件快速实现 OneRound(i +2,C,D,A,B,G,H,E,F,W) OneRound(i+3,B,C,D,A,F,G,H,E,W) 从理论上讲，SM3算法中使用最多且最耗时的 2)可以优化压缩函数的中间变量的生成流程。 是64轮压缩函数和消息扩展。利用Intel VTune 此优化生成流程可以去除不必要的赋值，减少中间 Amplifier XE分析算法热点，得出信息如下表。 变量个数。优化后的执行步骤如下（其中t:=T: 表1普通实现时的热点 <<<i为常数)： Table 1 The hot spots of general implementation TT2←-A<<<12 参数 耗时/s 百分比/% TT1←-TT2+E+ 整体 21.795 100 TT,←TT,<<<7 压缩函数 14.355 65.9 TT2←TT,⊕TT 消息扩展 5.287 24.3 3)利用上述调整以及消息扩展部分的调整可 其他 2.153 9.8 以将原来计算TT1、TT2、D和H的过程进行如下的 热点信息显示，压缩函数和消息扩展的确是最 进一步简化。 耗时的2个部分，其耗时分别占总耗时的65.9%和 D←-D+FF(A,B,C)+TT2+(W:①W+a) 24.3%。因此，快速实现的关键在怎样快速实现压 H←H+GG(A,B,C)+TT,+W 缩函数和消息扩展。 4)预先计算并存储常数t:=T:<<<i。这可 2.1消息扩展的快速实现 以避免每个消息分组都去计算常数，且占用的存储 消息扩展的目的是利用512比特的消息分组B 空间也很少，仅256Byte。 扩展得到68个字W。,…,W,和64个字W。,…, 2.3调整后的算法描述 W'6 优化后的算法将消息扩展和压缩函数结合在一 快速实现时，为了尽可能减少不必要的数据加 起。下面先描述调整后的消息处理算法，该算法完 载和存储，W。,…,W和W'。,…,W6a的计算可以 成消息扩展和64轮压缩迭代：再描述调整后的一轮 调整到压缩函数里执行，具体实施过程是： 算法，该算法完成一轮压缩迭代，包括计算必需的消 1)首先在执行64轮压缩函数前只计算初始的 息扩展字W+4。调整后的消息处理算法描述如下。 4个字Wo,…,W3 算法1调整后的消息处理算法 2)然后在压缩函数的第i轮生成W:+4,而W': ProcessBlock(V,M) 则使用W:=W①W4代替。 输入：上轮迭代结果V,一个消息分组B 经过这样的调整，去掉了字W。,…,W6品，减少 输出：本轮迭代结果V
ＴＴ１ ← ＦＦｉ（Ａ，Ｂ，Ｃ） ＋ Ｄ ＋ ＳＳ２ ＋ Ｗｉ ′ ＴＴ２ ← ＧＧｉ（Ｅ，Ｆ，Ｇ） ＋ Ｈ ＋ ＳＳ１ ＋ Ｗｉ Ｄ ← Ｃ Ｃ ← Ｂ ＜ ＜ ＜ ９ Ｂ ← Ａ Ａ ← ＴＴ１ Ｈ ← Ｇ Ｇ ← Ｆ ＜ ＜ ＜ １９ Ｆ ← Ｅ Ｅ ← Ｐ０（ＴＴ２ ） ＥＮＤ ＦＯＲ Ｖ （ｉ＋１） ← Ｖ （ｉ） （Ａ‖Ｂ‖Ｃ‖Ｄ‖Ｅ‖Ｆ‖Ｇ‖Ｈ） １．５ 输出杂凑值 ２５６ 比特杂凑值 ｙ 的计算方式为 ｙ ← （Ａ‖Ｂ‖Ｃ‖Ｄ‖Ｅ‖Ｆ‖Ｇ‖Ｈ） ← Ｖ （ｎ） ２ 软件快速实现 从理论上讲，ＳＭ３ 算法中使用最多且最耗时的 是 ６４ 轮压缩函数和消息扩展。 利用 Ｉｎｔｅｌ ＶＴｕｎｅ Ａｍｐｌｉｆｉｅｒ ＸＥ 分析算法热点，得出信息如下表。 表 １ 普通实现时的热点 Ｔａｂｌｅ １ Ｔｈｅ ｈｏｔ ｓｐｏｔｓ ｏｆ ｇｅｎｅｒａｌ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ 参数 耗时／ ｓ 百分比／ ％ 整体 ２１．７９５ １００ 压缩函数 １４．３５５ ６５．９ 消息扩展 ５．２８７ ２４．３ 其他 ２．１５３ ９．８ 热点信息显示，压缩函数和消息扩展的确是最 耗时的 ２ 个部分，其耗时分别占总耗时的 ６５．９％和 ２４．３％。 因此，快速实现的关键在怎样快速实现压 缩函数和消息扩展。 ２．１ 消息扩展的快速实现 消息扩展的目的是利用 ５１２ 比特的消息分组 Ｂ 扩展得到 ６８ 个字 Ｗ０ ，…，Ｗ６７ 和 ６４ 个字 Ｗ′０ ，…， Ｗ′６３ 。 快速实现时，为了尽可能减少不必要的数据加 载和存储， Ｗ０ ，…，Ｗ６７ 和 Ｗ′０ ，…，Ｗ′６３ 的计算可以 调整到压缩函数里执行，具体实施过程是： １）首先在执行 ６４ 轮压缩函数前只计算初始的 ４ 个字 Ｗ０ ，…，Ｗ３ ； ２）然后在压缩函数的第 ｉ 轮生成 Ｗｉ＋４ ，而 Ｗ′ｉ 则使用 Ｗ′ｉ ＝ Ｗｉ Ｗｉ＋４ 代替。 经过这样的调整，去掉了字 Ｗ′０ ，…，Ｗ′６３ ，减少 了字 Ｗ０ ，…，Ｗ６７ 和 Ｗ′０ ，…，Ｗ′６３ 的加载和存储次 数，提高了消息扩展的速度。 ２．２ 压缩函数的快速实现 压缩函数的快速实现可以从结构调整、流程变 更、常数计算等方面着手。 １）压缩函数的结构可以做适当的调整。 压缩 函数每一轮的最末会执行如下所示的循环右移， Ａ‖Ｂ‖Ｃ‖Ｄ ← （Ａ‖Ｂ‖Ｃ‖Ｄ） ＞ ＞ ＞ ３２， Ｅ‖Ｆ‖Ｇ‖Ｈ ← （Ｅ‖Ｆ‖Ｇ‖Ｈ） ＞ ＞ ＞ ３２。 为了减 少循环移位导致的不必要的赋值运算，可以将字的 循环右移变更每轮输入字顺序的变动，且这个顺序 变动 会 在 ４ 轮 后 还 原， 具 体 情 况 如 下 （ 以 下 用 ＯｎｅＲｏｕｎｄ（·） 表示一轮压缩）： ＯｎｅＲｏｕｎｄ（ｉ ＋ ０，Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ，Ｗ） ＯｎｅＲｏｕｎｄ（ｉ ＋ １，Ｄ，Ａ，Ｂ，Ｃ，Ｈ，Ｅ，Ｆ，Ｇ，Ｗ） ＯｎｅＲｏｕｎｄ（ｉ ＋ ２，Ｃ，Ｄ，Ａ，Ｂ，Ｇ，Ｈ，Ｅ，Ｆ，Ｗ） ＯｎｅＲｏｕｎｄ（ｉ ＋ ３，Ｂ，Ｃ，Ｄ，Ａ，Ｆ，Ｇ，Ｈ，Ｅ，Ｗ） ２）可以优化压缩函数的中间变量的生成流程。 此优化生成流程可以去除不必要的赋值，减少中间 变量个数。 优化后的执行步骤如下（其中 ｔ ｉ ＝ Ｔｉ ＜ ＜ ＜ ｉ 为常数）： ＴＴ２ ← Ａ ＜ ＜ ＜ １２ ＴＴ１ ← ＴＴ２ ＋ Ｅ ＋ ｔ ｉ ＴＴ１ ← ＴＴ１ ＜ ＜ ＜ ７ ＴＴ２ ← ＴＴ２ ＴＴ１ ３）利用上述调整以及消息扩展部分的调整可 以将原来计算 ＴＴ１ 、 ＴＴ２ 、 Ｄ 和 Ｈ 的过程进行如下的 进一步简化。 Ｄ ← Ｄ ＋ ＦＦｉ（Ａ，Ｂ，Ｃ） ＋ ＴＴ２ ＋ （Ｗｉ Ｗｉ＋４ ） Ｈ ← Ｈ ＋ ＧＧｉ（Ａ，Ｂ，Ｃ） ＋ ＴＴ１ ＋ Ｗｉ ４）预先计算并存储常数 ｔ ｉ ＝ Ｔｉ ＜ ＜ ＜ ｉ 。 这可 以避免每个消息分组都去计算常数，且占用的存储 空间也很少，仅 ２５６ Ｂｙｔｅ。 ２．３ 调整后的算法描述 优化后的算法将消息扩展和压缩函数结合在一 起。 下面先描述调整后的消息处理算法，该算法完 成消息扩展和 ６４ 轮压缩迭代；再描述调整后的一轮 算法，该算法完成一轮压缩迭代，包括计算必需的消 息扩展字 Ｗｉ＋４ 。 调整后的消息处理算法描述如下。 算法 １ 调整后的消息处理算法 ＰｒｏｃｅｓｓＢｌｏｃｋ（ Ｖ，Ｍ ） 输入：上轮迭代结果 Ｖ ，一个消息分组 Ｂ 输出：本轮迭代结果 Ｖ ·９５６· 智 能 系 统 学 报 第 １０ 卷
第6期 杨先伟，等：SM3杂凑算法的软件快速实现研究 ·957. 中间变量：字寄存器A一H, 已经求出，执行完毕后W+4也被计算出来：步骤2 步骤： 中的t:为常量T:<<<i,应预先计算并存储，使用 1)W。‖W,IW2‖W3←-B。IB,‖B2lB3, 时只需查表：由于W,、FF,、GG:的计算方式在i< 2)AIBI C IDI E I F I GIH-V, 16时和i≥16时不同，因此可以考虑将0 neRound 3)F0R(i=0,4,8,…,60), 函数分为0≤i<12、12≤i<16、16≤i<643种 OneRound(i +0,A,B,C,D,E,F,G,H,W), 情况分别实现。 OneRound(i 1,D,A,B,C,H,E,F,G,W), OneRound(i +2,C,D,A,B,G,H,E,F,W), 32种实现方式的计算量分析评估 OneRound(i +3,B,C,D,A,F,G,H,E,W), 为了从理论上评估新方法的效率，本节对2种 END FOR 方法的计算量进行详细对比。由于算法的操作主要 4)V←V⊕(A IB I C‖DIEIFIGIH), 集中在压缩函数中，因此以下对压缩函数的计算量 5)返回V。 进行统计、分析和对比。优化前的方法严格按照标 对算法1做以下儿点说明：这里的 准文档，先计算消息扩展字，再进行64轮迭代，优化 B。‖B,…‖Bs=B分别代表消息的16个字：前4 后的方法则按照上一节描述的算法1和算法2进行 个消息扩展字W。、W,、W2、W3需在循环前计算出来， 实现。以下用LOAD和STORE表示数据加载和存 进入后面的循环后，每次执行OneRound(i,*)将 储，XOR表示异或运算，ROT表示移位运算，ADD 计算W:+4。 表示加法运算，AND表示与运算，OR表示或运算， 调整后的一轮压缩算法如下。 NOT表示非运算。 算法2调整后的一轮压缩算法 优化前的算法中，消息扩展的计算量为： OneRound(i,A,B,C,D,E,F,G,H,W) 1)计算前16个W,时每个需执行1次L0AD和 输入：字寄存器A一H,轮序号i,消息扩展字数 1次STORE,计算后52个W时每个需执行5次 组W=(Wo,…,W6) LOAD、1次STORE,6次XOR、4次ROT; 输出：更新后的A一H和W=(W。,…,W6) 2)计算64个W',每个需执行2次L0AD、1次 步骤： STORE、1次ROT: 1)计算消息扩展字W+4 3)计算压缩函数的一次迭代需要执行3次 F(i<12)W:+4←-B+d LOAD、12次STORE、8次ADD、3次XOR、8次 ELSE W44←-P,(W-2①W-s⊕(W+1<<< ROT、1次FFi函数和1次GGi函数， 15))④(W-9<<<7)⊕W-2 4)F℉i函数和GGi函数的计算量是，前16次 END IF FFi函数需执行2次XOR和2次ROT,前16次GGi 2)计算中间变量TT,和TT, 函数需执行2次XOR和2次ROT,后48次FFi函 TT2←-A<<<12 数需执行3次AND和2次OR,后48次GGi函数需 TT,←-TT2+E+t 执行2次AND、1次OR、1次NOT。 TT,←TT,<<<7 根据以上统计分析，表2列出了优化前的算法 TT2←TT,①TT1 中对一个512比特的消息块执行一次完整的压缩所 3)仅更新字寄存器B、D、F、H。 需的计算量。 D←-D+FF,(A,B,C)+TT2+(W:①W+a) 优化后的算法中，消息扩展的计算量为： H-H+GG(E,F,G)TT +Wi 1)计算前12个W+4时每个需执行1次L0AD B-B<<<9 和1次STORE,计算后52个W+4时每个需执行5 F←-F<<<19 次LOAD、1次STORE、6次XOR、4次ROT; H←-P。(H) 2)计算中间变量TT,和TT,需要执行1次 4)返回更新后的A一H和W=(W。,…,W）。 LOAD、2次STORE、2次ADD、1次XOR、2次ROT; 对算法2做以下几点说明：进入第i轮的算法2 3)更新字寄存器B、D、F、H需要执行：1次 之时，消息扩展字只有{W|k<i+4}这部分信息 LOAD、1次STORE、6次ADD、3次XOR、4次ROT
中间变量：字寄存器 Ａ—Ｈ ， 步骤： １） Ｗ０‖Ｗ１‖Ｗ２‖Ｗ３ ← Ｂ０‖Ｂ１‖Ｂ２‖Ｂ３ ， ２） Ａ‖Ｂ‖Ｃ‖Ｄ‖Ｅ‖Ｆ‖Ｇ‖Ｈ ← Ｖ ， ３）ＦＯＲ （ ｉ ＝ ０，４，８，…，６０）， ＯｎｅＲｏｕｎｄ（ｉ ＋ ０，Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ，Ｗ） ， ＯｎｅＲｏｕｎｄ（ｉ ＋ １，Ｄ，Ａ，Ｂ，Ｃ，Ｈ，Ｅ，Ｆ，Ｇ，Ｗ） ， ＯｎｅＲｏｕｎｄ（ｉ ＋ ２，Ｃ，Ｄ，Ａ，Ｂ，Ｇ，Ｈ，Ｅ，Ｆ，Ｗ） ， ＯｎｅＲｏｕｎｄ（ｉ ＋ ３，Ｂ，Ｃ，Ｄ，Ａ，Ｆ，Ｇ，Ｈ，Ｅ，Ｗ） ， ＥＮＤ ＦＯＲ ４） Ｖ ← Ｖ （Ａ‖Ｂ‖Ｃ‖Ｄ‖Ｅ‖Ｆ‖Ｇ‖Ｈ） ， ５）返回 Ｖ 。 对 算 法 １ 做 以 下 几 点 说 明： 这 里 的 Ｂ０‖Ｂ１‖…‖Ｂ１５ ＝ Ｂ 分别代表消息的 １６ 个字；前 ４ 个消息扩展字 Ｗ０ 、Ｗ１ 、Ｗ２ 、Ｗ３ 需在循环前计算出来， 进入后面的循环后，每次执行 ＯｎｅＲｏｕｎｄ（ｉ，∗） 将 计算 Ｗｉ＋４ 。 调整后的一轮压缩算法如下。 算法 ２ 调整后的一轮压缩算法 ＯｎｅＲｏｕｎｄ（ ｉ，Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ，Ｗ ） 输入：字寄存器 Ａ—Ｈ， 轮序号 ｉ ，消息扩展字数 组 Ｗ ＝ （Ｗ０ ，…，Ｗ６７ ） 输出：更新后的 Ａ—Ｈ 和 Ｗ ＝ （Ｗ０ ，…，Ｗ６７ ） 步骤： １）计算消息扩展字 Ｗｉ＋４ ＩＦ（ ｉ ＜ １２） Ｗｉ＋４ ← Ｂｉ＋４ ＥＬＳＥ Ｗｉ＋４ ← Ｐ１（Ｗｉ－１２ Ｗｉ－５ （Ｗｉ＋１ ＜ ＜ ＜ １５）） （Ｗｉ－９ ＜ ＜ ＜ ７） Ｗｉ－２ ＥＮＤ ＩＦ ２）计算中间变量 ＴＴ１ 和 ＴＴ２ ＴＴ２ ← Ａ ＜ ＜ ＜ １２ ＴＴ１ ← ＴＴ２ ＋ Ｅ ＋ ｔ ｉ ＴＴ１ ← ＴＴ１ ＜ ＜ ＜ ７ ＴＴ２ ← ＴＴ２ ＴＴ１ ３）仅更新字寄存器 Ｂ、Ｄ、Ｆ、Ｈ。 Ｄ ← Ｄ ＋ ＦＦｉ（Ａ，Ｂ，Ｃ） ＋ ＴＴ２ ＋ （Ｗｉ Ｗｉ＋４ ） Ｈ ← Ｈ ＋ ＧＧｉ（Ｅ，Ｆ，Ｇ） ＋ ＴＴ１ ＋ Ｗｉ Ｂ ← Ｂ ＜ ＜ ＜ ９ Ｆ ← Ｆ ＜ ＜ ＜ １９ Ｈ ← Ｐ０（Ｈ） ４）返回更新后的 Ａ—Ｈ 和 Ｗ ＝ （Ｗ０ ，…，Ｗ６７ ） 。 对算法 ２ 做以下几点说明：进入第 ｉ 轮的算法 ２ 之时，消息扩展字只有 ｛Ｗｋ ｜ ｋ ＜ ｉ ＋ ４｝ 这部分信息 已经求出，执行完毕后 Ｗｉ＋４ 也被计算出来；步骤 ２ 中的 ｔ ｉ 为常量 Ｔｉ ＜ ＜ ＜ ｉ ，应预先计算并存储，使用 时只需查表；由于 Ｗｉ 、 ＦＦｉ 、 ＧＧｉ 的计算方式在 ｉ ＜ １６ 时和 ｉ ≥ １６ 时不同，因此可以考虑将 ＯｎｅＲｏｕｎｄ 函数分为 ０ ≤ ｉ ＜ １２、 １２ ≤ ｉ ＜ １６、 １６ ≤ ｉ ＜ ６４３ 种 情况分别实现。 ３ ２ 种实现方式的计算量分析评估 为了从理论上评估新方法的效率，本节对 ２ 种 方法的计算量进行详细对比。 由于算法的操作主要 集中在压缩函数中，因此以下对压缩函数的计算量 进行统计、分析和对比。 优化前的方法严格按照标 准文档，先计算消息扩展字，再进行 ６４ 轮迭代，优化 后的方法则按照上一节描述的算法 １ 和算法 ２ 进行 实现。 以下用 ＬＯＡＤ 和 ＳＴＯＲＥ 表示数据加载和存 储，ＸＯＲ 表示异或运算，ＲＯＴ 表示移位运算，ＡＤＤ 表示加法运算，ＡＮＤ 表示与运算，ＯＲ 表示或运算， ＮＯＴ 表示非运算。 优化前的算法中，消息扩展的计算量为： １）计算前 １６ 个 Ｗｉ 时每个需执行 １ 次 ＬＯＡＤ 和 １ 次 ＳＴＯＲＥ，计算后 ５２ 个 Ｗｉ 时每个需执行 ５ 次 ＬＯＡＤ、１ 次 ＳＴＯＲＥ、６ 次 ＸＯＲ、４ 次 ＲＯＴ； ２）计算 ６４ 个 Ｗ′ｉ 每个需执行 ２ 次 ＬＯＡＤ、１ 次 ＳＴＯＲＥ、１ 次 ＲＯＴ； ３）计算压缩函数的一次迭代需要执行 ３ 次 ＬＯＡＤ、１２ 次 ＳＴＯＲＥ、 ８ 次 ＡＤＤ、 ３ 次 ＸＯＲ、 ８ 次 ＲＯＴ、１ 次 ＦＦｉ 函数和 １ 次 ＧＧｉ 函数， ４） ＦＦｉ 函数和 ＧＧｉ 函数的计算量是，前 １６ 次 ＦＦｉ 函数需执行 ２ 次 ＸＯＲ 和 ２ 次 ＲＯＴ，前 １６ 次 ＧＧｉ 函数需执行 ２ 次 ＸＯＲ 和 ２ 次 ＲＯＴ，后 ４８ 次 ＦＦｉ 函 数需执行 ３ 次 ＡＮＤ 和 ２ 次 ＯＲ，后 ４８ 次 ＧＧｉ 函数需 执行 ２ 次 ＡＮＤ、１ 次 ＯＲ、１ 次 ＮＯＴ。 根据以上统计分析，表 ２ 列出了优化前的算法 中对一个 ５１２ 比特的消息块执行一次完整的压缩所 需的计算量。 优化后的算法中，消息扩展的计算量为： １）计算前 １２ 个 Ｗｉ＋４ 时每个需执行 １ 次 ＬＯＡＤ 和 １ 次 ＳＴＯＲＥ，计算后 ５２ 个 Ｗｉ＋４ 时每个需执行 ５ 次 ＬＯＡＤ、１ 次 ＳＴＯＲＥ、６ 次 ＸＯＲ、４ 次 ＲＯＴ； ２）计算中间变量 ＴＴ１ 和 ＴＴ２ 需要执行 １ 次 ＬＯＡＤ、２ 次 ＳＴＯＲＥ、２ 次 ＡＤＤ、１ 次 ＸＯＲ、２ 次 ＲＯＴ； ３） 更 新 字 寄 存 器 Ｂ、Ｄ、Ｆ、Ｈ 需 要 执 行： １ 次 ＬＯＡＤ、１ 次 ＳＴＯＲＥ、６ 次 ＡＤＤ、３ 次 ＸＯＲ、４ 次 ＲＯＴ、 第 ６ 期 杨先伟，等：ＳＭ３ 杂凑算法的软件快速实现研究 ·９５７·
·958· 智能系统学报 第10卷 1次FFi函数和1次GGi函数； 根据以上统计分析，表2列出了优化后的算法 4)FFi函数和GGi函数的计算量同优化前的计 中对一个512比特的消息块执行一次完整的压缩所 算量。 需的计算量。 表2优化前后一次压缩函数的计算量 Table 2 The computation of the compression function of the before and after optimization LOAD STORE ADD XOR ROT AND OR NOT 合计 优化前 596 900 512 632 720 240 144 48 3792 优化后 400 256 512 632 592 240 144 好 2824 从表2可知，优化后的压缩函数通过轮函数的 情况说明。 调整和消息扩展函数的优化，大大减少了LOAD和 1)第1组测试中测试1个数据包，该数据包为 STORE的次数，同时中间变量TT,和TT,的优化实 256×10个字节，此测试用以模拟大量数据杂凑的 现又进一步减少了ROT的次数，其余运算的计算量 情况，如大型文件杂凑； 无变化。 2)第2组测试中杂凑200个数据包，每个数据 如果从操作总数的角度考虑，优化后算法的速 包1.28×10个字节，此测试用以模拟中型数据包杂 度可提升(3792-2824)/2824=34.3%。但实际 凑的情况，如图片等： 上CPU执行这些操作指令时，不同的操作具有不同 3)第3组测试中杂凑40000个数据包，每个数 的指令执行周期(eycle),甚至不同的CPU执行相同 据包6.4×103个字节，此测试用以模拟普通网络数 的运算所需的指令周期也各不相同。大部分CPU 据包杂凑的情况； 执行整数的算数运算和逻辑运算需1个时钟周期， 4)第4组测试中杂凑8×10个数据包，每个数 而执行LOAD和STORE则需要多个时钟周期，且各 据包32个字节，此测试用以模拟频繁的微小型数据 CPU的执行时间也有较大差异。以下假设执行每个 包杂凑的情况。 算数逻辑运算需1个时钟周期。如果执行LOAD需 为了统计每种测试的准确耗时值，每组测试都 1个时钟周期，执行STORE需2个时钟周期，则优化 反复进行21次并记录各次的时间，最后从大到小排 后算法的速度可提升52.3%。：如果假设执行LOAD 列后取最中间的值作为统计耗时值。 需1.5个时钟周期，执行ST0RE需2.5个时钟周期， 测试使用的软件平台详情如下：Windows XP 则优化后算法的速度可提升59.6%：如果假设执行 SP332比特、Intel Core i3@3400MHz、4 GB DDR3- LOAD需2个时钟周期，执行STORE需3个时钟周 1600 SDRAM、Microsoft Visual Studio8.0。速度单位 期，则优化后算法的速度可提升65.6%。不同假设 为Mbi/s。其中处理器的缓存情况为[)：一级缓存 下的速度提升情况见下表3。 为每个核心32KB,2级缓存为每个核心64KB,3级 表3不同情况下的优化前后速度提升估计值 缓存为多核共享3MB。 Table 3 The speed of the before and after optimization 表42种实现方式的性能比较 算数逻辑 LOAD STORE 速度 Table 4 The performance comparison of two implementa- 运算(cycle) (cycle) (cycle) 提升/% tion methods 1 1.0 1.0 34.3 测试 速度/(Mh·s1) 速度 1 1.0 2.0 52.3 类别 优化前 优化后 提升/% 1 1.5 2.5 59.6 第1组测试 739 1203 62.8 1 2.0 3.0 65.6 第2组测试 733 1191 62.5 第3组测试 701 1074 53.2 4 模拟实验与对比测试 第4组测试 642 973 51.6 为了模拟真实环境中对SM3算法软件实现的 平均 704 1110 57.7 需求，下面的实验中进行了4组测试，每组测试方法 上表列出的测试结果表明：1)数据包越大，执行 对多个数据包进行杂凑，每个数据包为特定长度字 效率越高，这是因为大型数据包减少了一头一尾的 节，然后统计耗时和速度。以下为4组测试的详细 初始化、消息填充和反初始化等工作：2)优化调整后
１ 次 ＦＦｉ 函数和 １ 次 ＧＧｉ 函数； ４）ＦＦｉ 函数和 ＧＧｉ 函数的计算量同优化前的计 算量。 根据以上统计分析，表 ２ 列出了优化后的算法 中对一个 ５１２ 比特的消息块执行一次完整的压缩所 需的计算量。 表 ２ 优化前后一次压缩函数的计算量 Ｔａｂｌｅ ２ Ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎ ｏｆ ｔｈｅ ｃｏｍｐｒｅｓｓｉｏｎ ｆｕｎｃｔｉｏｎ ｏｆ ｔｈｅ ｂｅｆｏｒｅ ａｎｄ ａｆｔｅｒ ｏｐｔｉｍｉｚａｔｉｏｎ ＬＯＡＤ ＳＴＯＲＥ ＡＤＤ ＸＯＲ ＲＯＴ ＡＮＤ ＯＲ ＮＯＴ 合计 优化前 ５９６ ９００ ５１２ ６３２ ７２０ ２４０ １４４ ４８ ３ ７９２ 优化后 ４００ ２５６ ５１２ ６３２ ５９２ ２４０ １４４ ４８ ２ ８２４ 从表 ２ 可知，优化后的压缩函数通过轮函数的 调整和消息扩展函数的优化，大大减少了 ＬＯＡＤ 和 ＳＴＯＲＥ 的次数，同时中间变量 ＴＴ１ 和 ＴＴ２ 的优化实 现又进一步减少了 ＲＯＴ 的次数，其余运算的计算量 无变化。 如果从操作总数的角度考虑，优化后算法的速 度可提升 （３ ７９２ － ２ ８２４） ／ ２ ８２４ ＝ ３４．３％ 。 但实际 上 ＣＰＵ 执行这些操作指令时，不同的操作具有不同 的指令执行周期（ｃｙｃｌｅ），甚至不同的 ＣＰＵ 执行相同 的运算所需的指令周期也各不相同。 大部分 ＣＰＵ 执行整数的算数运算和逻辑运算需 １ 个时钟周期， 而执行 ＬＯＡＤ 和 ＳＴＯＲＥ 则需要多个时钟周期，且各 ＣＰＵ 的执行时间也有较大差异。 以下假设执行每个 算数逻辑运算需 １ 个时钟周期。 如果执行 ＬＯＡＤ 需 １ 个时钟周期，执行 ＳＴＯＲＥ 需 ２ 个时钟周期，则优化 后算法的速度可提升 ５２．３％。；如果假设执行 ＬＯＡＤ 需 １．５ 个时钟周期，执行 ＳＴＯＲＥ 需 ２．５ 个时钟周期， 则优化后算法的速度可提升 ５９．６％；如果假设执行 ＬＯＡＤ 需 ２ 个时钟周期，执行 ＳＴＯＲＥ 需 ３ 个时钟周 期，则优化后算法的速度可提升 ６５．６％。 不同假设 下的速度提升情况见下表 ３。 表 ３ 不同情况下的优化前后速度提升估计值 Ｔａｂｌｅ ３ Ｔｈｅ ｓｐｅｅｄ ｏｆ ｔｈｅ ｂｅｆｏｒｅ ａｎｄ ａｆｔｅｒ ｏｐｔｉｍｉｚａｔｉｏｎ 算数逻辑 运算（ｃｙｃｌｅ） ＬＯＡＤ （ｃｙｃｌｅ） ＳＴＯＲＥ （ｃｙｃｌｅ） 速度 提升／ ％ １ １．０ １．０ ３４．３ １ １．０ ２．０ ５２．３ １ １．５ ２．５ ５９．６ １ ２．０ ３．０ ６５．６ ４ 模拟实验与对比测试 为了模拟真实环境中对 ＳＭ３ 算法软件实现的 需求，下面的实验中进行了 ４ 组测试，每组测试方法 对多个数据包进行杂凑，每个数据包为特定长度字 节，然后统计耗时和速度。 以下为 ４ 组测试的详细 情况说明。 １）第 １ 组测试中测试 １ 个数据包，该数据包为 ２５６ × １０ ６ 个字节，此测试用以模拟大量数据杂凑的 情况，如大型文件杂凑； ２）第 ２ 组测试中杂凑 ２００ 个数据包，每个数据 包 １．２８ × １０ ６ 个字节，此测试用以模拟中型数据包杂 凑的情况，如图片等； ３）第 ３ 组测试中杂凑 ４０ ０００ 个数据包，每个数 据包 ６．４ × １０ ３ 个字节，此测试用以模拟普通网络数 据包杂凑的情况； ４）第 ４ 组测试中杂凑 ８ × １０ ６ 个数据包，每个数 据包 ３２ 个字节，此测试用以模拟频繁的微小型数据 包杂凑的情况。 为了统计每种测试的准确耗时值，每组测试都 反复进行 ２１ 次并记录各次的时间，最后从大到小排 列后取最中间的值作为统计耗时值。 测试使用的软件平台详情如下： Ｗｉｎｄｏｗｓ ＸＰ ＳＰ３ ３２ 比特、Ｉｎｔｅｌ Ｃｏｒｅ ｉ３＠ ３４００ ＭＨｚ、４ ＧＢ ＤＤＲ３⁃ １６００ ＳＤＲＡＭ、Ｍｉｃｒｏｓｏｆｔ Ｖｉｓｕａｌ Ｓｔｕｄｉｏ ８．０。 速度单位 为 Ｍｂｉｔ ／ ｓ。 其中处理器的缓存情况为［１３］ ：一级缓存 为每个核心 ３２ ＫＢ，２ 级缓存为每个核心 ６４ ＫＢ，３ 级 缓存为多核共享 ３ ＭＢ。 表 ４ ２ 种实现方式的性能比较 Ｔａｂｌｅ ４ Ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｗｏ ｉｍｐｌｅｍｅｎｔａ⁃ ｔｉｏｎ ｍｅｔｈｏｄｓ 测试 类别 速度／ （Ｍｂ·ｓ －１ ） 优化前 优化后 速度 提升／ ％ 第 １ 组测试 ７３９ １ ２０３ ６２．８ 第 ２ 组测试 ７３３ １ １９１ ６２．５ 第 ３ 组测试 ７０１ １ ０７４ ５３．２ 第 ４ 组测试 ６４２ ９７３ ５１．６ 平均 ７０４ １ １１０ ５７．７ 上表列出的测试结果表明：１）数据包越大，执行 效率越高，这是因为大型数据包减少了一头一尾的 初始化、消息填充和反初始化等工作：２）优化调整后 ·９５８· 智 能 系 统 学 报 第 １０ 卷
第6期 杨先伟，等：SM3杂凑算法的软件快速实现研究 .959. 的算法效率提升显著，可以提升60%左右，在杂凑大 [8]王晓燕，杨先文.基于FPGA的SM3算法优化设计与实 中型数据包时速度提升60%以上，即使在杂凑微小 现[J].计算机工程，2012,38(6)：244-246. 型数据包时效率也能提升50%以上。 WANG Xiaoyan,YANG Xianwen.Optimization design and implementation of SM3 algorithm based on FPGA[J].Com- 4结束语 puter Engineering,2012,38(6):244-246. [9]伍娟.国密SM3算法在C0S上的研究与实现[J刀].科技 本文对我国国家密码管理局发布的SM3密码杂 信息，2013，(2)：294-295. 凑算的软件快速实现进行研究，根据算法自身的特 WU Juan.Research and implementation of SM3 algorithm on 点，尤其是压缩函数的特点，给出一种更加适用于软 COS[J].Science Technology Information,2013,(2): 件快速实现的算法描述方式和实现方法。理论分析 294-295. 得出的算法计算量以及模拟实验结果均表明，利用此 [10]曾小波，唐忠彪，焦歆.基于单片机的SM3算法优化及 软件快速实现方法可以将算法的效率提升60%左右。 Verilog模型验证[J].电子科技，2015,28(2)：38-40. 另外，此软件快速实现方式不基于特定的平台、架构、 ZENG Xiaobo,TANG Zhongbiao,JIAO Xin.Optimization 指令等，因此具有很强的跨平台性和兼容性。 of SM3 algorithm and Verilog model validation based on SCM[J].Electronic Science and Technology,2015,28 参考文献： (2):38-40. [1l]沈一公，苏厚勤.基于Android的SM3密码杂凑算法研 [1]NIST.Federal information processing standards publication 180-3,secure hash standards (SHS)[S].Gaithersburg, 究与实现[J].电子技术与软件工程，2013(18)：69-70. SHEN Yigong,SU Houqin.Research and implementation MD,USA:Information Technology Laboratory of National of SM3 algorithm based on android[J].Electronic Technol- Institute of Standards and Technology,2008.http://csre. ogy Software Engineering,2013(18):69-70. nist.gov/publications. [12]易叔贤，张非凡.SM系列算法在金融IC卡领域的应用 [2]NIST.Cryptographic hash algorithm competition [EB/OL]. (2005-04-15)[2015-08-05].htp:/csrc.nist.gov/groups/, [J].金融电子化.2013(7)：49-52. YI Shuxian,ZHANG Feifan.Application of SM series algo- ST/hash/sha-3/index.html. [3]国家密码管理局.SM3密码杂凑算法[S].北京：国家密 rithm in the field of financial IC card[J].Financial Com- 码管理局，2010. puterizing,2013(7):49-52. [13]ntel.2nd generation intel coreTM processor family desktop National Cryptography Administration.SM3 cryptographic datasheet[EB/0L].(2011-01-04)[2013-07-08].htp:/ hash algorithm[S].Beijing:National Cryptography Admin- www.intel.com/content/www/us/en/processors/core/2nd- istration,2010. [4]ACIICMEZ O.Fast hashing on pentium SIMD architecture gen-core-desktop-vol-1-datasheet.html. 作者简介： [D].Corvallis,Oregon:Oregon State University,2004. 杨先伟，男，1980年生，讲师，主要 [5]GUERON S,KRASNOV V.Parallelizing message schedules 研究方向为通信与系统工程。 to accelerate the computations of hash functions[R].2012. http://eprint.iacr.org/2012/067.pdf [6]GUERON S,KRASNOV V.Simultaneous hashing of multi- ple messages[J].Journal of Information Security,2012,3 (4):319-325. [7]张倩，李树国.SM3杂凑算法的ASIC设计和实现[J].微 康红娟，女，1983年生，工程师，主 电子学与计算机，2014,31(9)：143-146,152 要研究方向为保密通信。 ZHANG Qian,LI Shuguo.Design and implementation of SM3 algorithm in ASIC[J].Microelectronics Computer. 2014,31(9)：143-146,152
的算法效率提升显著，可以提升 ６０％左右，在杂凑大 中型数据包时速度提升 ６０％以上，即使在杂凑微小 型数据包时效率也能提升 ５０％以上。 ４ 结束语 本文对我国国家密码管理局发布的 ＳＭ３ 密码杂 凑算的软件快速实现进行研究，根据算法自身的特 点，尤其是压缩函数的特点，给出一种更加适用于软 件快速实现的算法描述方式和实现方法。 理论分析 得出的算法计算量以及模拟实验结果均表明，利用此 软件快速实现方法可以将算法的效率提升 ６０％左右。 另外，此软件快速实现方式不基于特定的平台、架构、 指令等，因此具有很强的跨平台性和兼容性。 参考文献： ［１］ ＮＩＳＴ． Ｆｅｄｅｒａｌ ｉｎｆｏｒｍａｔｉｏｎ ｐｒｏｃｅｓｓｉｎｇ ｓｔａｎｄａｒｄｓ ｐｕｂｌｉｃａｔｉｏｎ １８０⁃３， ｓｅｃｕｒｅ ｈａｓｈ ｓｔａｎｄａｒｄｓ （ ＳＨＳ） ［ Ｓ］． Ｇａｉｔｈｅｒｓｂｕｒｇ， ＭＤ， ＵＳＡ： Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｎａｔｉｏｎａｌ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｓｔａｎｄａｒｄｓ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， ２００８． ｈｔｔｐ： ／ ／ ｃｓｒｃ． ｎｉｓｔ．ｇｏｖ ／ ｐｕｂｌｉｃａｔｉｏｎｓ． ［２］ＮＩＳＴ． Ｃｒｙｐｔｏｇｒａｐｈｉｃ ｈａｓｈ ａｌｇｏｒｉｔｈｍ ｃｏｍｐｅｔｉｔｉｏｎ ［ＥＢ／ ＯＬ］． （２００５⁃０４⁃１５） ［ ２０１５⁃０８⁃０５］． ｈｔｔｐ： ／ ／ ｃｓｒｃ． ｎｉｓｔ． ｇｏｖ ／ ｇｒｏｕｐｓ／ ＳＴ／ ｈａｓｈ ／ ｓｈａ⁃３／ ｉｎｄｅｘ．ｈｔｍｌ． ［３］国家密码管理局． ＳＭ３ 密码杂凑算法［ Ｓ］． 北京： 国家密 码管理局， ２０１０． Ｎａｔｉｏｎａｌ Ｃｒｙｐｔｏｇｒａｐｈｙ Ａｄｍｉｎｉｓｔｒａｔｉｏｎ． ＳＭ３ ｃｒｙｐｔｏｇｒａｐｈｉｃ ｈａｓｈ ａｌｇｏｒｉｔｈｍ［ Ｓ］． Ｂｅｉｊｉｎｇ： Ｎａｔｉｏｎａｌ Ｃｒｙｐｔｏｇｒａｐｈｙ Ａｄｍｉｎ⁃ ｉｓｔｒａｔｉｏｎ， ２０１０． ［４］ ＡＣＩＩＣＭＥＺ Ｏ． Ｆａｓｔ ｈａｓｈｉｎｇ ｏｎ ｐｅｎｔｉｕｍ ＳＩＭＤ ａｒｃｈｉｔｅｃｔｕｒｅ ［Ｄ］． Ｃｏｒｖａｌｌｉｓ， Ｏｒｅｇｏｎ： Ｏｒｅｇｏｎ Ｓｔａｔｅ Ｕｎｉｖｅｒｓｉｔｙ， ２００４． ［５］ＧＵＥＲＯＮ Ｓ， ＫＲＡＳＮＯＶ Ｖ． Ｐａｒａｌｌｅｌｉｚｉｎｇ ｍｅｓｓａｇｅ ｓｃｈｅｄｕｌｅｓ ｔｏ ａｃｃｅｌｅｒａｔｅ ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎｓ ｏｆ ｈａｓｈ ｆｕｎｃｔｉｏｎｓ［Ｒ］． ２０１２． ｈｔｔｐ： ／ ／ ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ ／ ２０１２ ／ ０６７．ｐｄｆ ［６］ＧＵＥＲＯＮ Ｓ， ＫＲＡＳＮＯＶ Ｖ． Ｓｉｍｕｌｔａｎｅｏｕｓ ｈａｓｈｉｎｇ ｏｆ ｍｕｌｔｉ⁃ ｐｌｅ ｍｅｓｓａｇｅｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｅｃｕｒｉｔｙ， ２０１２， ３ （４）： ３１９⁃３２５． ［７］张倩， 李树国． ＳＭ３ 杂凑算法的 ＡＳＩＣ 设计和实现［Ｊ］． 微 电子学与计算机， ２０１４， ３１（９）： １４３⁃１４６， １５２． ＺＨＡＮＧ Ｑｉａｎ， ＬＩ Ｓｈｕｇｕｏ． Ｄｅｓｉｇｎ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ＳＭ３ ａｌｇｏｒｉｔｈｍ ｉｎ ＡＳＩＣ［ Ｊ］． Ｍｉｃｒｏｅｌｅｃｔｒｏｎｉｃｓ ＆ Ｃｏｍｐｕｔｅｒ， ２０１４， ３１（９）： １４３⁃１４６， １５２． ［８］王晓燕， 杨先文． 基于 ＦＰＧＡ 的 ＳＭ３ 算法优化设计与实 现［Ｊ］． 计算机工程， ２０１２， ３８（６）： ２４４⁃２４６． ＷＡＮＧ Ｘｉａｏｙａｎ， ＹＡＮＧ Ｘｉａｎｗｅｎ． Ｏｐｔｉｍｉｚａｔｉｏｎ ｄｅｓｉｇｎ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ＳＭ３ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ＦＰＧＡ［ Ｊ］． Ｃｏｍ⁃ ｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ， ２０１２， ３８（６）： ２４４⁃２４６． ［９］伍娟． 国密 ＳＭ３ 算法在 ＣＯＳ 上的研究与实现［ Ｊ］． 科技 信息， ２０１３， （２）： ２９４⁃２９５． ＷＵ Ｊｕａｎ． Ｒｅｓｅａｒｃｈ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ＳＭ３ ａｌｇｏｒｉｔｈｍ ｏｎ ＣＯＳ［Ｊ］． Ｓｃｉｅｎｃｅ ＆ Ｔｅｃｈｎｏｌｏｇｙ Ｉｎｆｏｒｍａｔｉｏｎ， ２０１３， （ ２）： ２９４⁃２９５． ［１０］曾小波， 唐忠彪， 焦歆． 基于单片机的 ＳＭ３ 算法优化及 Ｖｅｒｉｌｏｇ 模型验证［Ｊ］． 电子科技， ２０１５， ２８（２）： ３８⁃４０． ＺＥＮＧ Ｘｉａｏｂｏ， ＴＡＮＧ Ｚｈｏｎｇｂｉａｏ， ＪＩＡＯ Ｘｉｎ． Ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ＳＭ３ ａｌｇｏｒｉｔｈｍ ａｎｄ Ｖｅｒｉｌｏｇ ｍｏｄｅｌ ｖａｌｉｄａｔｉｏｎ ｂａｓｅｄ ｏｎ ＳＣＭ［ Ｊ］． Ｅｌｅｃｔｒｏｎｉｃ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， ２０１５， ２８ （２）： ３８⁃４０． ［１１］沈一公， 苏厚勤． 基于 Ａｎｄｒｏｉｄ 的 ＳＭ３ 密码杂凑算法研 究与实现［Ｊ］． 电子技术与软件工程， ２０１３（１８）： ６９⁃７０． ＳＨＥＮ Ｙｉｇｏｎｇ， ＳＵ Ｈｏｕｑｉｎ． Ｒｅｓｅａｒｃｈ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ＳＭ３ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ａｎｄｒｏｉｄ［Ｊ］． Ｅｌｅｃｔｒｏｎｉｃ Ｔｅｃｈｎｏｌ⁃ ｏｇｙ ＆ Ｓｏｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ， ２０１３（１８）： ６９⁃７０． ［１２］易叔贤， 张非凡． ＳＭ 系列算法在金融 ＩＣ 卡领域的应用 ［Ｊ］． 金融电子化， ２０１３（７）： ４９⁃５２． ＹＩ Ｓｈｕｘｉａｎ， ＺＨＡＮＧ Ｆｅｉｆａｎ． Ａｐｐｌｉｃａｔｉｏｎ ｏｆ ＳＭ ｓｅｒｉｅｓ ａｌｇｏ⁃ ｒｉｔｈｍ ｉｎ ｔｈｅ ｆｉｅｌｄ ｏｆ ｆｉｎａｎｃｉａｌ ＩＣ ｃａｒｄ［ Ｊ］． Ｆｉｎａｎｃｉａｌ Ｃｏｍ⁃ ｐｕｔｅｒｉｚｉｎｇ， ２０１３（７）： ４９⁃５２． ［１３］ｎｔｅｌ． ２ｎｄ ｇｅｎｅｒａｔｉｏｎ ｉｎｔｅｌ ® ｃｏｒｅＴＭ ｐｒｏｃｅｓｓｏｒ ｆａｍｉｌｙ ｄｅｓｋｔｏｐ ｄａｔａｓｈｅｅｔ［ＥＢ／ ＯＬ］． （２０１１⁃０１⁃０４） ［２０１３⁃０７⁃０８］． ｈｔｔｐ： ／ ／ ｗｗｗ． ｉｎｔｅｌ． ｃｏｍ／ ｃｏｎｔｅｎｔ ／ ｗｗｗ／ ｕｓ／ ｅｎ ／ ｐｒｏｃｅｓｓｏｒｓ／ ｃｏｒｅ ／ ２ｎｄ⁃ ｇｅｎ⁃ｃｏｒｅ⁃ｄｅｓｋｔｏｐ⁃ｖｏｌ⁃１⁃ｄａｔａｓｈｅｅｔ．ｈｔｍｌ． 作者简介： 杨先伟，男，１９８０ 年生，讲师，主要 研究方向为通信与系统工程。 康红娟，女，１９８３ 年生，工程师，主 要研究方向为保密通信。 第 ６ 期 杨先伟，等：ＳＭ３ 杂凑算法的软件快速实现研究 ·９５９·
