集成消息填充的SM3算法硬件设计与实现

集成消息填充的SM3算法硬件设计与实现 Design of SM3 Hardware Implementation with Integrated Message Padding 1 first-author 武 迪，男，硕士生，主要从事信息网络安全方面的研究。 E⁃mail：wd5d000@163.com 武 迪，男，硕士生，主要从事信息网络安全方面的研究。 E⁃mail：wd5d000@163.com wd5d000@163.com 1 corresp E⁃mail：xutg@buaa.edu.cn E⁃mail：xutg@buaa.edu.cn xutg@buaa.edu.cn 1 2 1 北京航空航天大学 网络空间安全学院，北京 100191 北京航空航天大学 网络空间安全学院，北京 100191 School of Cyber Science and Technology, Beihang University, Beijing 100191, China School of Cyber Science and Technology, Beihang University, Beijing 100191, China 北京航空航天大学 高等理工学院，北京 100191 北京航空航天大学 高等理工学院，北京 100191 Shenyuan Honors College, Beihang University, Beijing 100191,China Shenyuan Honors College, Beihang University, Beijing 100191,China 分析了SM3的执行流程，基于现场可编程门阵列(field programmable gate array，FPGA)逻辑器件设计开发该算法的高性能硬件实现。针对目前SM3算法在FPGA上的消息填充实现不完整的问题，本文集成硬件消息填充模块，针对整字节输入进行了优化。实验结果表明，本文方案相比于其他SM3算法实现拥有较好的吞吐率和逻辑资源占用。 This article analyzes SM3（Chinese commercial Hash function） in details and develops a high performance hardware implementation based on field programmable gate array (FPGA). We tackled the incomplete message padding problem by integrating hardware style message padding and optimize the performance in the condition of byte input. Our results show that we improve the SM3 hardware implementation in message padding with better throughput and logical resource overhead. SM3 杂凑算法 现场可编程门阵列 SM3 Hash function FPGA(field programmable gate array) 0　 引 言 1 杂凑算法是加解密运算中重要的不可逆运算，受到各国密码管理机构的重视。这种算法的基本功能是针对长度任意的消息进行特定的运算，该运算最终将输出长度恒定的杂凑值。杂凑算法的运算过程不需要保密，且只要输入有任何细微的变化，其输出杂凑值的改变将是非常彻底的，这种“雪崩效应”使得不同输入产生相同杂凑值的几率极小。美国安全杂凑算法(secure Hash function, SHA)系列标准早已制定完成，而我国杂凑算法SM3也于2010年底由国家密码管理局正式颁布。在当前很多需要实时处理且数据量庞大的应用需求下，传统的软件杂凑算法操作越来越无法达到用户所需要的实现速度和效率。本文的核心目的是探索在高性能硬件平台现场可编程门阵列 (field programmable gate array，FPGA)上设计并实现完整功能的SM3杂凑算法。目前基于FPGA的SM3算法实现均没有集成消息填充的功能，需要依赖额外上层软件执行填充操作，并非完整的SM3算法硬件实现 [ 1 1 , 2 2 , 3 3 , 4 4 ] 。本文基于FPGA上使用Verilog语言实现了SM3算法，并设计了独立的消息填充模块，使SM3算法全部流程均由FPGA处理，避免了SM3算法的拆分，达到了算法完全集成于FPGA平台的目的，并进行了针对性优化。本文的SM3算法与其他无消息填充的算法实现相比，拥有较好的吞吐率和逻辑资源占用，能够满足商用杂凑算法的需要。 1　 SM3算法概述 1 SM3算法与美国SHA系列算法拥有类似的架构。SM3算法与SHA⁃256算法相比，杂凑值长度、处理块长度、最大输入消息长度、操作字长度和循环次数等参数的取值均相同，仅在操作字个数和压缩函数的设计上有部分区别，因此两者拥有相近的安全性能。 SM3算法关键步骤有两部分，分别为输入消息填充和杂凑中间量迭代压缩。SM3算法的总体流程如 图1 图1 所示。 1.1　消息填充 2 SM3算法规定 [ 1 1 ] ，输入消息 m 的长度 l 要小于2 64 比特，在进行消息填充时，首先在消息末尾添加1比特“1”，然后再添加 k 比特“0”，要求 k 是满足等式 <math id="M1"><mi>l</mi><mo>+</mo><mn mathvariant="normal">1</mn><mo>+</mo><mi>k</mi><mo>≡</mo><mn mathvariant="normal">448</mn><mi mathvariant="normal">m</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">d</mi><mn mathvariant="normal">512</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118027&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118021&type= 39.28533173 2.96333337 的最小非负整数。最后在输入消息后添加一个64位比特串，该比特串是输入消息长度 l 的二进制表示。因此，经过填充的消息 <math id="M2"><mi>m</mi><mi>'</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118040&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118033&type= 3.72533321 2.79399991 的比特长度应为512的整数倍。 1.2　迭代压缩 2 迭代压缩模块可分为消息扩展和压缩函数两部分。经过填充的消息 <math id="M3"><msup><mrow><mi>m</mi></mrow><mrow><mi>'</mi></mrow></msup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118051&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118046&type= 3.47133350 3.04799986 按512比特进行分组，得到 <math id="M4"><mi>m</mi><mi>'</mi><mo>=</mo><msup><mrow><mi>B</mi></mrow><mrow><mo stretchy="false">(</mo><mn mathvariant="normal">0</mn><mo stretchy="false">)</mo></mrow></msup><msup><mrow><mi>B</mi></mrow><mrow><mo stretchy="false">(</mo><mn mathvariant="normal">1</mn><mo stretchy="false">)</mo></mrow></msup><mo>⋯</mo><msup><mrow><mi>B</mi></mrow><mrow><mo stretchy="false">(</mo><mi>n</mi><mo>-</mo><mn mathvariant="normal">1</mn><mo stretchy="false">)</mo></mrow></msup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118064&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118058&type= 31.41133308 3.04799986 ，其中 <math id="M5"><mi>n</mi><mo>=</mo><mo stretchy="false">(</mo><mi>l</mi><mo>+</mo><mi>k</mi><mo>+</mo><mn mathvariant="normal">65</mn><mo stretchy="false">)</mo><mo>/</mo><mn mathvariant="normal">512</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118074&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118070&type= 33.61266708 3.72533321 。迭代压缩以分组 <math id="M6"><msup><mrow><mi>B</mi></mrow><mrow><mo stretchy="false">(</mo><mi>i</mi><mo stretchy="false">)</mo></mrow></msup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118088&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118083&type= 4.74133348 3.04799986 为单位进行处理。 消息扩展是对每一分组的 <math id="M7"><msup><mrow><mi>B</mi></mrow><mrow><mo stretchy="false">(</mo><mi>i</mi><mo stretchy="false">)</mo></mrow></msup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118100&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118094&type= 4.74133348 3.04799986 进行一定处理，具体过程为扩展到 <math id="M8"><msub><mrow><mi>W</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118111&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118105&type= 5.24933338 3.72533321 ， <math id="M9"><msub><mrow><mi>W</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118123&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118116&type= 5.24933338 3.72533321 ， <math id="M10"><mo>…</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118134&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118127&type= 3.97933340 2.79399991 ， <math id="M11"><msub><mrow><mi>W</mi></mrow><mrow><mn mathvariant="normal">67</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118143&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118137&type= 6.18066692 3.72533321 ， <math id="M12"><msub><mrow><mi>W</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub><mi mathvariant="normal">'</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118153&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118149&type= 6.18066692 4.23333359 ， <math id="M13"><msub><mrow><mi>W</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mi mathvariant="normal">'</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118161&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118158&type= 6.18066692 4.23333359 ，…， <math id="M14"><msub><mrow><mi>W</mi></mrow><mrow><mn mathvariant="normal">63</mn></mrow></msub><mi mathvariant="normal">'</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118173&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118166&type= 6.94266701 4.23333359 ，长度共132个字，每个字为32比特，以用于压缩函数。压缩函数共包含64轮，每轮进行12步运算，完成64轮循环运算后，将计算结果与执行本轮压缩函数前的初始数据进行异或运算。当所有分组处理完毕后，即可输出256比特的杂凑值。 2　 SM3算法的FPGA实现 1 本文SM3算法的FPGA实现包括对外封装接口及SM3算法的三个主要处理模块，即消息填充模块、消息扩展模块和压缩函数模块。 2.1　SM3算法接口封装 2 本文实现的SM3算法输入输出接口封装及功能说明如 表1 表1 所示。输入与输出数据信号位宽均为32比特；其他为时钟、复位等信号控制硬件逻辑。与其他实现方案相比，本文为解决最后一组输入数据可能不满32比特的情况，额外添加一组信号din_cnt表示输入数据的有效位数。 名称 类型 功能说明 clk input wire 时钟信号 rst input wire 复位信号 din input wire[31:0] 输入数据 din_vld input wire 输入数据有效 din_cnt input wire[5:0] 输入数据有效位数 din_end input wire 输入数据结束 rdy output wire 输入数据准备 dout output wire[31:0] 输出数据 dout_vld output wire 输出数据有效 2.2　消息填充模块 2 消息填充模块负责对输入数据进行填充，以满足杂凑运算的具体要求。当最后一组消息数据进入运算逻辑电路时，首先需要依据输入数据长度的不同，进行两步判断以决定填充的方式。具体判断流程如下： 1) 若输入消息 m 的总比特长度 l 满足 <math id="M15"><mn mathvariant="normal">32</mn><mo>|</mo><mi>l</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118193&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118187&type= 5.58799982 3.47133350 时，即最后一组32比特数据全部有效，在消息结尾填充一组32位长的比特串，该比特串第一位为“1”，其余位为“0”，则新消息比特总长度为 <math id="M16"><mi>l</mi><mi mathvariant="normal">'</mi><mo>=</mo><mi>l</mi><mo>+</mo><mn mathvariant="normal">32</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118201&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118196&type= 17.27199936 3.38666677 ；否则，即最后一组32比特数据并非全部有效，在最后一组数据的有效数据位末尾添加一位比特“1”，然后再添加 p 比特“0”，要求 p 是满足 <math id="M17"><mn mathvariant="normal">32</mn><mo>|</mo><mi>l</mi><mo>+</mo><mn mathvariant="normal">1</mn><mo>+</mo><mi>p</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118211&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118207&type= 18.96533394 3.72533321 的最小非负整数，则新消息比特总长度为 <math id="M18"><mi>l</mi><mi mathvariant="normal">'</mi><mo>=</mo><mi>l</mi><mo>+</mo><mn mathvariant="normal">1</mn><mo>+</mo><mi>p</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118218&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118214&type= 22.09799957 4.14866638 ，易知 <math id="M19"><mi>l</mi><mi mathvariant="normal">'</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118225&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118221&type= 2.70933342 3.30199981 为32的整数倍。例如，消息“01100001 01100010 01100011 00111000”，其长度 <math id="M20"><mi>l</mi><mo>=</mo><mn mathvariant="normal">32</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118232&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118228&type= 9.73666668 2.79399991 ，则填充“10000000 00000000 00000000 00000000”；消息“01100001 01100010 01100011”，其长度 <math id="M21"><mi>l</mi><mo>=</mo><mn mathvariant="normal">24</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118240&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118237&type= 9.73666668 2.79399991 ，则填充“10000000”。 2) 在消息数据位末尾继续填充 q 次32比特长度的全“0”比特串，要求 q 是满足 <math id="M22"><mi>l</mi><mi mathvariant="normal">'</mi><mo>+</mo><mi>q</mi><mo>×</mo><mn mathvariant="normal">32</mn><mo>≡</mo><mn mathvariant="normal">448</mn><mi mathvariant="normal">m</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">d</mi><mn mathvariant="normal">512</mn></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118248&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118245&type= 43.60333252 4.14866638 的最小非负整数。 3) 最后再在上述处理过程后添加一个64位比特串，该比特串是输入消息长度 l 的二进制表示。 至此，输入消息已经完成了填充步骤，填充后的消息比特长度应为512的整数倍，之后将消息按512比特进行分组，由迭代压缩模块进行处理。上述消息填充过程如 图2 图2 所示。 需要强调的是，在上述第一步判断中，当输入最后一组32比特数据的有效位数 n 不等于32时，表示该组数据并非全部有效。因此，需要对该数据先进行左移操作，将有效数据移至最高位，然后将有效数据的下一位修改为“1”。在实现过程中，仅考虑可综合的编程方式，可列举全部32种情况。例如，输入信号为din[31:0]，若有效位为10位，则 <math id="M23"><mo>{</mo><mi mathvariant="normal">d</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">n</mi><mo stretchy="false">[</mo><mn mathvariant="normal">9</mn><mo>:</mo><mn mathvariant="normal">0</mn><mo stretchy="false">]</mo><mo>,</mo><mn mathvariant="normal">1</mn><mi mathvariant="normal">'</mi><mi mathvariant="normal">b</mi><mn mathvariant="normal">1,21</mn><mi mathvariant="normal">'</mi><mi mathvariant="normal">b</mi><mn mathvariant="normal">0</mn><mo>}</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118270&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118264&type= 37.42266846 3.97933340 可表示移位与填充“1”的流程，以此类推可完成所有情况的处理。 由于输入有效位共有32种可能性，导致上述移位与填充流程是消息填充模块中资源消耗最多且速度影响最大的部分，因此可在已知数据部分特性的前提下进行优化。在电子计算设备的数据处理中，多数情况下数据均以字节为单位进行计算与存储，1字节可表示为8比特。因此，当输入数据已知以字节为单位，即数据的比特长度为8的整数倍时，上述移位与填充流程可以简化为仅列举有效位数为8、16、24、32的4种情况，从而有效节约资源消耗并提高运行效率。 2.3　消息扩展模块 2 依据SM3的算法规定 [ 1 1 ] ，消息扩展的计算流程如下： 1) 将 <math id="M24"><msup><mrow><mi>B</mi></mrow><mrow><mo stretchy="false">(</mo><mi>i</mi><mo stretchy="false">)</mo></mrow></msup></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118279&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118274&type= 4.74133348 3.04799986 划分为16个字 <math id="M25"><msub><mrow><mi>W</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub><mo>,</mo><msub><mrow><mi>W</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mrow><mi>W</mi></mrow><mrow><mn mathvariant="normal">15</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118287&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118282&type= 26.07733345 4.14866638 2) <math id="M26"><msub><mrow><mi>W</mi></mrow><mrow><mn mathvariant="normal">16</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118300&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118291&type= 6.77333355 3.72533321 到 <math id="M27"><msub><mrow><mi>W</mi></mrow><mrow><mn mathvariant="normal">67</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118308&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118304&type= 6.01133347 3.72533321 ，其生成表达式为 <math display="block" id="M28"><mtable columnalign="left"><mtr><mtd><msub><mrow><mi>W</mi></mrow><mrow><mi>j</mi></mrow></msub><mo>=</mo><msub><mrow><mi>P</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mo stretchy="false">(</mo><msub><mrow><mi>W</mi></mrow><mrow><mi>j</mi><mo>-</mo><mn mathvariant="normal">16</mn></mrow></msub><mo>⊕</mo><msub><mrow><mi>W</mi></mrow><mrow><mi>j</mi><mo>-</mo><mn mathvariant="normal">9</mn></mrow></msub><mo>⊕</mo><mo stretchy="false">(</mo><msub><mrow><mi>W</mi></mrow><mrow><mi>j</mi><mo>-</mo><mn mathvariant="normal">3</mn></mrow></msub><mo><</mo><mo><</mo><mo><</mo><mn mathvariant="normal">15</mn><mo stretchy="false">)</mo><mo stretchy="false">)</mo><mo>⊕</mo></mtd></mtr><mtr><mtd><mo stretchy="false">(</mo><msub><mrow><mi>W</mi></mrow><mrow><mi>j</mi><mo>-</mo><mn mathvariant="normal">13</mn></mrow></msub><mo><</mo><mo><</mo><mo><</mo><mn mathvariant="normal">7</mn><mo stretchy="false">)</mo><mo>⊕</mo><msub><mrow><mi>W</mi></mrow><mrow><mi>j</mi><mo>-</mo><mn mathvariant="normal">6</mn></mrow></msub></mtd></mtr></mtable></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118318&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118313&type= 74.16799927 10.24466705 3) <math id="M29"><msub><mrow><mi>W</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub><mi mathvariant="normal">'</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118330&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118324&type= 6.77333355 4.23333359 到 <math id="M30"><msub><mrow><mi>W</mi></mrow><mrow><mn mathvariant="normal">63</mn></mrow></msub><mi mathvariant="normal">'</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118341&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118335&type= 6.94266701 4.23333359 ，其生成表达式为 <math display="block" id="M31"><msub><mrow><mi>W</mi></mrow><mrow><mi>j</mi></mrow></msub><mi mathvariant="normal">'</mi><mo>=</mo><msub><mrow><mi>W</mi></mrow><mrow><mi>j</mi></mrow></msub><mo>⊕</mo><msub><mrow><mi>W</mi></mrow><mrow><mi>j</mi><mo>+</mo><mn mathvariant="normal">4</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118351&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118346&type= 27.00866890 4.57200003 依据上述流程，采用16个32比特的移位寄存器实现该功能，典型的消息扩展逻辑设计如 图3 图3 所示。 图3 图3 中函数 <math display="block" id="M32"><msub><mrow><mi>P</mi></mrow><mrow><mn mathvariant="normal">1</mn></mrow></msub><mo stretchy="false">(</mo><mi>X</mi><mo stretchy="false">)</mo><mo>=</mo><mi>X</mi><mo>⊕</mo><mo stretchy="false">(</mo><mi>X</mi><mo><</mo><mo><</mo><mo><</mo><mn mathvariant="normal">15</mn><mo stretchy="false">)</mo><mo>⊕</mo><mo stretchy="false">(</mo><mi>X</mi><mo><</mo><mo><</mo><mo><</mo><mn mathvariant="normal">23</mn><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118376&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118369&type= 72.47466278 4.65666676 需要强调的是，上述消息扩展逻辑需要全部16个寄存器填满，即从最后一组32比特数据进入后，压缩流程才会开始执行。而通过分析算法可知，当 j 小于等于15时， <math id="M33"><msub><mrow><mi>W</mi></mrow><mrow><mi>j</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118388&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118381&type= 4.57200003 3.72533321 不需要运算， <math id="M34"><msub><mrow><mi>W</mi></mrow><mrow><mi>j</mi></mrow></msub><mi mathvariant="normal">'</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118397&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118393&type= 5.58799982 4.23333359 仅需要 <math id="M35"><msub><mrow><mi>W</mi></mrow><mrow><mi>j</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118408&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118404&type= 4.57200003 3.72533321 和 <math id="M36"><msub><mrow><mi>W</mi></mrow><mrow><mi>j</mi><mo>+</mo><mn mathvariant="normal">4</mn></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118420&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118414&type= 8.12800026 3.72533321 进行与运算即可得到。因此，可以通过提前输出 <math id="M37"><msub><mrow><mi>W</mi></mrow><mrow><mi>j</mi></mrow></msub></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118430&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118425&type= 4.57200003 3.72533321 与 <math id="M38"><msub><mrow><mi>W</mi></mrow><mrow><mi>j</mi></mrow></msub><mi mathvariant="normal">'</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118440&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118435&type= 5.58799982 4.23333359 达到减少延时。经优化的消息扩展逻辑可以在第5个32比特数据输入的时钟周期时，开始向压缩函数提供数据输入。经优化的方案相比典型方案减小11个时钟周期延时。优化逻辑如 图4 图4 所示。 2.4　压缩函数模块 2 压缩函数是SM3算法的核心，是一个包含循环的运算过程。在执行循环过程之前，首先需要对 <math id="M39"><mi>A</mi><mo>,</mo><mi>B</mi><mo>,</mo><mi>C</mi><mo>,</mo><mi>D</mi><mo>,</mo><mi>E</mi><mo>,</mo><mi>F</mi><mo>,</mo><mi>G</mi><mo>,</mo><mi>H</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118464&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118461&type= 37.42266846 3.21733332 共8个32比特寄存器赋值，然后对一组运算执行64次循环。压缩函数的运算步骤如 图5 图5 所示，需要调用一些基于移位和加法操作的基本布尔函数与基本置换函数，定义如下： <math display="block" id="M40"><mi>F</mi><msub><mrow><mi>F</mi></mrow><mrow><mi>j</mi></mrow></msub><mo stretchy="false">(</mo><mi>X</mi><mo>,</mo><mi>Y</mi><mo>,</mo><mi>Z</mi><mo stretchy="false">)</mo><mo>=</mo><mfenced open="{" close="" separators="|"><mrow><mtable columnalign="left"><mtr><mtd><mi>X</mi><mo>⊕</mo><mi>Y</mi><mo>⊕</mo><mi>Z</mi><mo>,</mo><mi>j</mi><mo>∈</mo><mo stretchy="false">[</mo><mn mathvariant="normal">0,15</mn><mo stretchy="false">]</mo></mtd></mtr><mtr><mtd><mo stretchy="false">(</mo><mi>X</mi><mo>∧</mo><mi>Y</mi><mo stretchy="false">)</mo><mo>∨</mo><mo stretchy="false">(</mo><mi>X</mi><mo>∧</mo><mi>Z</mi><mo stretchy="false">)</mo><mo>∨</mo><mo stretchy="false">(</mo><mi>Y</mi><mo>∧</mo><mi>Z</mi><mo stretchy="false">)</mo><mo>,</mo><mi>j</mi><mo>∈</mo><mo stretchy="false">[</mo><mn mathvariant="normal">16,63</mn><mo stretchy="false">]</mo></mtd></mtr></mtable></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118473&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118468&type= 76.70800018 16.00200081 <math display="block" id="M41"><mi>G</mi><msub><mrow><mi>G</mi></mrow><mrow><mi>j</mi></mrow></msub><mo stretchy="false">(</mo><mi>X</mi><mo>,</mo><mi>Y</mi><mo>,</mo><mi>Z</mi><mo stretchy="false">)</mo><mo>=</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118482&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118477&type= 27.09333420 4.48733330 <math display="block" id="M42"><mfenced open="{" close="" separators="|"><mrow><mtable columnalign="left"><mtr><mtd><mi>X</mi><mo>⊕</mo><mi>Y</mi><mo>⊕</mo><mi>Z</mi><mo>,</mo><mi>j</mi><mo>∈</mo><mo stretchy="false">[</mo><mn mathvariant="normal">0,15</mn><mo stretchy="false">]</mo></mtd></mtr><mtr><mtd><mo stretchy="false">(</mo><mi>X</mi><mo>∧</mo><mi>Y</mi><mo stretchy="false">)</mo><mo>∨</mo><mo stretchy="false">(</mo><mo>¬</mo><mi>X</mi><mo>∧</mo><mi>Z</mi><mo stretchy="false">)</mo><mo>,</mo><mi>j</mi><mo>∈</mo><mo stretchy="false">[</mo><mn mathvariant="normal">16,63</mn><mo stretchy="false">]</mo></mtd></mtr></mtable></mrow></mfenced></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118509&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118502&type= 61.89133453 10.66799927 <math display="block" id="M43"><msub><mrow><mi>P</mi></mrow><mrow><mn mathvariant="normal">0</mn></mrow></msub><mo stretchy="false">(</mo><mi>X</mi><mo stretchy="false">)</mo><mo>=</mo><mi>X</mi><mo>⊕</mo><mo stretchy="false">(</mo><mi>X</mi><mo><</mo><mo><</mo><mo><</mo><mn mathvariant="normal">9</mn><mo stretchy="false">)</mo><mo>⊕</mo><mo stretchy="false">(</mo><mi>X</mi><mo><</mo><mo><</mo><mo><</mo><mn mathvariant="normal">17</mn><mo stretchy="false">)</mo></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118523&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118517&type= 69.84999847 4.65666676 在循环过程执行完毕后，逻辑电路将计算结果与执行本轮压缩函数前的初始数据进行异或运算，得到本次压缩函数的输出值。 压缩函数中包含大量移位、异或、加法等运算，因此可采用部分优化方法提升运行效率。如使用CSA结构对关键路径中多级加法器进行优化 [ 2 2 ] 。CSA结构可将多级加法器中的部分加法器简化为异或等延时较小的运算，以减小关键路径延时。此外，压缩函数中 <math id="M44"><msub><mrow><mi>T</mi></mrow><mrow><mi>j</mi></mrow></msub><mo><</mo><mo><</mo><mo><</mo><mi>j</mi></math> http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118535&type= http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=4118530&type= 17.61066628 4.57200003 运算步骤对每次循环的移位位数不同，会造成大量的资源浪费；因此可将其存入寄存器并在每次循环时将其循环左移1位，从而降低运算复杂度，节约资源并提高效率。 3　 性能评估 1 本文设计的SM3算法基于Altera公司的Cyclone V芯片，在Quartus平台上以Verilog HDL编程实现，在连续的数据输入条件下，可以在64时钟周期内完成512比特的数据处理。 由 表2 表2 可知，本文通过设计硬件电路处理的消息填充模块，使填充流程不需要借助上层的软件实现，开发了功能完全的SM3算法硬件，并且在不考虑硬件选型差异的前提下，资源消耗及吞吐率较其他参考文献的算法实现更优。此外，本文设计的两种消息填充模块，在有效位判断时有所区别，前者以比特为单位，对所有情况进行考虑与实现，而后者以字节为单位，仅对字节整数倍的数据输入情况进行分析，适用于大多应用场景，并且能够显著提高吞吐率，降低资源消耗。 算法来源 器件 填充方式 资源消耗 频率/MHz 吞吐率/Mb·s -1 文献[ 1 1 ] Virtex⁃Ⅱ 软件填充 1 035 (Slices) 105.7 795 文献[ 1 1 ] Virtex⁃Ⅱ Pro 软件填充 1 035 (Slices) 124.6 938 文献[ 1 1 ] Virtex⁃5 软件填充 328 (Slices) 197.2 1 483 文献[ 2 2 ] ZYNQ⁃7020 软件填充 1 743 (ALUTs) 167.8 1 342.28 文献[ 3 3 ] EP4CE22F17C8 软件填充 3 933 (LEs) 165 1 184.8 文献[ 4 4 ] EP1C20F324C6 软件填充 1 789 (LEs) 92.55 724.4 本文 5CEFA2F23C8 硬件填充 1 077 (ALMs) 230.84 1 846.72 本文（字节优化） 5CEFA2F23C8 硬件填充 992 (ALMs) 239.75 1 918 4　 结 论 1 本文在FPGA平台上设计并实现了SM3算法，通过设计消息填充模块，使填充流程不需要借助上层的软件实现，实现了完全功能的SM3算法硬件实现。实验结果表明，本文的实现具备较好的性能表现，能够满足不同应用场景下商用密码的要求。 □ 参考文献 刘宗斌 , 马原 , 荆继武 , 等 . SM3哈希算法的硬件实现与研究 [J]. 信息网络安全 , 2011 ( 9 ): 191 ⁃ 193+218 . DOI ： 10.3969/j.issn.1671⁃1122.2011.09.059 http://dx.doi.org/10.3969/j.issn.1671⁃1122.2011.09.059 . SM3哈希算法的硬件实现与研究 LIU Z B , MA Y , JING J W , et al . Implementation of SM3 Hash function on FPGA [J]. Netinfo Security , 2011 ( 9 ): 191 ⁃ 193+218 . DOI ：10.3969/j.issn.1671⁃1122.2011.09.059 (Ch) . Implementation of SM3 Hash function on FPGA 周威 , 王博 , 张卫东 . SM3算法硬件实现研究与应用 [J]. 电子测量技术 , 2015 , 38 ( 12 ): 67 ⁃ 71 . DOI： 10.19651/j.cnki.emt.2015.12.015 http://dx.doi.org/10.19651/j.cnki.emt.2015.12.015 . SM3算法硬件实现研究与应用 ZHOU W , WANG B , ZHANG W D , et al . Research and application of SM3 hardware implementation [J]. Electronic Measurement Technology , 2015 , 38 ( 12 ): 67 ⁃ 71 . DOI：10.19651/j.cnki.emt.2015.12.015 (Ch) . Research and application of SM3 hardware implementation 邵梦丽 , 殷新春 , 李艳梅 . SM3杂凑算法的SoPC组件实现 [J]. 网络与信息安全学报 , 2017 , 3 ( 5 ): 47 ⁃ 53 . DOI: 10.11959/j.issn.2096⁃109x.2017.00146 http://dx.doi.org/10.11959/j.issn.2096⁃109x.2017.00146 . SM3杂凑算法的SoPC组件实现 SHAO M L , YIN X C , LI Y M . Implementation of SM3 algorithm based on SoPC component [J]. Chinese Journal of Network and Information Security , 2017 , 3 ( 5 ): 47 ⁃ 53 . DOI: 10.11959/j.issn.2096⁃109x.2017.00146 (Ch) . Implementation of SM3 algorithm based on SoPC component 王晓燕 , 杨先文 . 基于FPGA的SM3算法优化设计与实现 [J]. 计算机工程 , 2012 , 38 ( 6 ): 244 ⁃ 246 . DOI: 10.3969/j.issn.1000⁃3428.2012.06.081 http://dx.doi.org/10.3969/j.issn.1000⁃3428.2012.06.081 . 基于FPGA的SM3算法优化设计与实现 WANG X Y , YANG X W . Optimization design and implementation of SM3 algorithm based on FPGA [J]. Computer Engineering , 2012 , 38 ( 6 ): 244 ⁃ 246 . DOI: 10.3969/j.issn.1000⁃3428.2012.06.081 (Ch) . Optimization design and implementation of SM3 algorithm based on FPGA 10.14188/j.1671-8836.2019.02.012 TN 918.4 A 1671-8836（2019）02-0218-05 武迪,徐同阁，王子钰,等.集成消息填充的SM3算法硬件设计与实现[J].武汉大学学报（理学版）,2019,65(2):218⁃222. 武迪,徐同阁，王子钰,等.集成消息填充的SM3算法硬件设计与实现[J].武汉大学学报（理学版）,2019,65(2):218⁃222. WU Di,XU Tongge, WANG Ziyu, et al .Design of SM3 Hardware Implementation with Integrated Message Padding [J]. J Wuhan Univ （ Nat Sci Ed ）,2019,65(2):218⁃222. DOI:10.14188/j.1671⁃8836.2019.02.012（Ch). WU Di,XU Tongge, WANG Ziyu,et al.Design of SM3 Hardware Implementation with Integrated Message Padding [J].J Wuhan Univ（Nat Sci Ed）,2019,65(2):218⁃222. DOI:10.14188/j.1671⁃8836.2019.02.012（Ch). 国家重点研发计划(2017YFB1400700) 2018-09-10 2019-04-24 2020-11-25 武汉大学学报（理学版） 2 65