论文部分内容阅读
SM3密码杂凑算法发布于2010年12月17日1）。密码杂凑算法也被称作“杂凑算法”“散列算法”或“哈希算法”。在GM/Z 0001—2013《密码术语》中，上述几个术语对应的英文都是hash algorithm。
1 密码杂凑算法
密码杂凑算法的主要功能是将一个任意长的比特串映射到一个固定长的比特串。
假设任意长度的消息M，经过函数H（M）运算后，得到一个固定长度为m的散列值h，如公式（1）所示。
h=H（M） （1）
如果上述运算满足下面3个条件：
（1） 给定任意长度的消息M，容易固定长度的h;
（2）给定h，计算M非常困难;
（3）给定任意长度的消息M，要找到另一个任意长度的消息M′，能够满足H（M）= H（M′），非常困难。
观察（1）和（2），实际就是单向函数的要求，对于（3）而言，这个特性指的是抗碰撞性（collision resistance），即防止不同的输入产生相同的输出。在实践中使用的密码杂凑函数必须具备强抗碰撞性，例如，MD4、MD5和SHA-1都是因为碰撞攻击算法而被攻破。通俗而言，就是这些算法H（M），已经能够产生具备相同散列值h的两条不同消息M和M′。
由于密码杂凑算法这个特性，散列值h，就像是消息的“指纹”。显然，密码杂凑算法可以用于验证消息的完整性（integrity），也可以更广泛地应用于数字签名和验证、消息鉴别码（message authentication code，MAC）的生成和验证，以及随机数的生成等。
2 SM3密码杂凑算法
SM3是一种密码杂凑算法。2012年，SM3被采纳为GM/T 0004—2012行业标准，2016年转化为GB/T 32905—2016国家标准。具体信息如表1所示。
SM3的将输入的消息经过填充和迭代压缩等步骤，生成256比特杂凑值（散列值h）。
GB/T 32905—2016中举了一个通俗易懂的例子，消息01100001 01100010 01100011，长度l为24，首先①，在末尾加“1”，然后②，添加k个“0”凑成512的倍数，最后③，添加一个64位比特串，该比特串是输入消息长度l的二进制表示。
经过填充后的消息，如图1所示。
SM3中填充后的消息长度是512的倍数，因为SM3的消息分组长度为512比特。就是说，将填充后的消息m′按512比特进行分组：m′=B（0）B（1）…B（n-1），其中：
（2）
在上述示例中，k=423，因此，n=1。
迭代的过程如下：
其中，CF为压缩函数，V（0）在GB/T 32905—2016中已经被赋了一个为256比特的初始值。B（i）为填充后的消息分组。在GB/T 32905—2016附录A中，m′为16个字，即512比特2）。用于压缩函数CF输入的B（i）需要先进行扩展，扩展后的格式一组68个字，另一组64个字，共132个字。
扩展之后的消息分组B（i）与V（i）作为压缩函数的输入，进行迭代，经过一系列复杂的压缩运算，最后输出固定长度256比特的杂凑值，具体示例可以参考GB/T 32905—2016附录A。
3 基于M-D结构的算法
MD5和SHA-1都已经被证明不安全，SHA-2虽然没有发现有效攻击，由于SHA-1和SHA-2结构过于类似，NIST3）在2012年就已经宣布其不安全。上述几个算法，都采用了Merkle-Damgard结构（简称M-D结构）。
M-D结构是Ralph C. Merkle和Ivan Bjerre Damgard在1989年各自独立发表的[1，2]，其基本原理是先将填充后的消息均匀分组，指定一个初始向量，然后将消息分组和向量顺序输入至压缩函数，过程如图2所示，最后输出的就是杂凑值。显然，SM3密码杂凑算法也采用了M-D结构。
诸多研究表明，如果压缩函数是安全的，那么以此为基础的杂凑算法也是安全的[3]，也就是说，基于M-D结构的杂凑算法安全性取决于压缩函数的安全性，尤其是在抗碰撞性方面。但是，M-D结构也存在弱点，可能难以对抗长度扩展攻击（length extension attacks）[4]，因此SHA-3已经改用海绵函数（sponge function）。
4 其他几个算法介绍
其他常用的密码杂凑算法还有MD4、MD5以及SHA（Secure Hash Algorithm，安全杂凑算法）。
MD4（Message Digest）是Ronald L. Rivest在1990年设计的，已经被成功攻击，因此改进为MD5。MD4和MD5的杂凑值长度都是128位。再之前，1989年曾经发布过MD2，与之不同的是，MD2的安全性依赖于字节间的随机置换[5]。
SHA系列算法是NSA4）和NIST共同发布的安全杂凑算法标准（SHS，Secure Hash Standard），其中SHA-1和SHA-2的对比如表2所示5）。
SHA-3发布于2012年，发布為FIPS6） 202， SHA-3 Standard： Permutation-Based Hash and Extendable-Output Functions7）。SHA-3发布并不是说SHA-2就不安全了，在一段时间内，两者可以并存。SHA-3之前的名称为Keccak。Keccak采用了海绵结构，可以生成任意长度的杂凑值，为了与SHA-2兼容，SHA-3中规定了表2中的各种版本。SHA-3从根本上解决了M-D结构设计中的弱点。Keccak算法比较复杂，在国内也不会大面积应用，本文不再赘述。
5 小结
SM3是密码杂凑算法的一种，其压缩函数与SHA-256的压缩函数结构相似8），在消息分组大小、迭代轮数和输出长度等方面也基本接近。但与SHA-256相比，SM3设计更复杂一些，在安全性和效率上也更高。如本文所述，虽然SM3与SHA-256（SHA-2的一种）安全强度接近，且同为M-D结构的算法，但目前并没有发现对SM3或SHA-2的有效攻击途径。
（注：本文仅做学术探讨，与作者所在单位观点无关）
参考文献
[1] Merkle R C. One Way Hash Functions and DES [C]. In： Brassard G. （eds） Advances in Cryptology — CRYPTO’ 89 Proceedings. CRYPTO 1989.
[2] Damgard I B. A Design Principle for Hash Functions[C]. In： Brassard G. （eds） Advances in Cryptology — CRYPTO’ 89 Proceedings. CRYPTO 1989.
[3] 霍炜，郭启全，马原.商用密码应用与安全性评估[M]. 北京：中国工信出版社/电子工业出版社，2020.
[4] Tiwari， Harshvardhan. Merkle-Damgard Construction Method and Alternatives： A Review [J]. Journal of Information and Organizational Sciences， 2017 （41）：283-304.
[5] Bruce Schneier. 应用密码学：协议、算法与C源程序[M]. 北京：机械工业出版社，2013.
1 密码杂凑算法
密码杂凑算法的主要功能是将一个任意长的比特串映射到一个固定长的比特串。
假设任意长度的消息M，经过函数H（M）运算后，得到一个固定长度为m的散列值h，如公式（1）所示。
h=H（M） （1）
如果上述运算满足下面3个条件：
（1） 给定任意长度的消息M，容易固定长度的h;
（2）给定h，计算M非常困难;
（3）给定任意长度的消息M，要找到另一个任意长度的消息M′，能够满足H（M）= H（M′），非常困难。
观察（1）和（2），实际就是单向函数的要求，对于（3）而言，这个特性指的是抗碰撞性（collision resistance），即防止不同的输入产生相同的输出。在实践中使用的密码杂凑函数必须具备强抗碰撞性，例如，MD4、MD5和SHA-1都是因为碰撞攻击算法而被攻破。通俗而言，就是这些算法H（M），已经能够产生具备相同散列值h的两条不同消息M和M′。
由于密码杂凑算法这个特性，散列值h，就像是消息的“指纹”。显然，密码杂凑算法可以用于验证消息的完整性（integrity），也可以更广泛地应用于数字签名和验证、消息鉴别码（message authentication code，MAC）的生成和验证，以及随机数的生成等。
2 SM3密码杂凑算法
SM3是一种密码杂凑算法。2012年，SM3被采纳为GM/T 0004—2012行业标准，2016年转化为GB/T 32905—2016国家标准。具体信息如表1所示。
SM3的将输入的消息经过填充和迭代压缩等步骤，生成256比特杂凑值（散列值h）。
GB/T 32905—2016中举了一个通俗易懂的例子，消息01100001 01100010 01100011，长度l为24，首先①，在末尾加“1”，然后②，添加k个“0”凑成512的倍数，最后③，添加一个64位比特串，该比特串是输入消息长度l的二进制表示。
经过填充后的消息，如图1所示。
SM3中填充后的消息长度是512的倍数，因为SM3的消息分组长度为512比特。就是说，将填充后的消息m′按512比特进行分组：m′=B（0）B（1）…B（n-1），其中：
（2）
在上述示例中，k=423，因此，n=1。
迭代的过程如下：
其中，CF为压缩函数，V（0）在GB/T 32905—2016中已经被赋了一个为256比特的初始值。B（i）为填充后的消息分组。在GB/T 32905—2016附录A中，m′为16个字，即512比特2）。用于压缩函数CF输入的B（i）需要先进行扩展，扩展后的格式一组68个字，另一组64个字，共132个字。
扩展之后的消息分组B（i）与V（i）作为压缩函数的输入，进行迭代，经过一系列复杂的压缩运算，最后输出固定长度256比特的杂凑值，具体示例可以参考GB/T 32905—2016附录A。
3 基于M-D结构的算法
MD5和SHA-1都已经被证明不安全，SHA-2虽然没有发现有效攻击，由于SHA-1和SHA-2结构过于类似，NIST3）在2012年就已经宣布其不安全。上述几个算法，都采用了Merkle-Damgard结构（简称M-D结构）。
M-D结构是Ralph C. Merkle和Ivan Bjerre Damgard在1989年各自独立发表的[1，2]，其基本原理是先将填充后的消息均匀分组，指定一个初始向量，然后将消息分组和向量顺序输入至压缩函数，过程如图2所示，最后输出的就是杂凑值。显然，SM3密码杂凑算法也采用了M-D结构。
诸多研究表明，如果压缩函数是安全的，那么以此为基础的杂凑算法也是安全的[3]，也就是说，基于M-D结构的杂凑算法安全性取决于压缩函数的安全性，尤其是在抗碰撞性方面。但是，M-D结构也存在弱点，可能难以对抗长度扩展攻击（length extension attacks）[4]，因此SHA-3已经改用海绵函数（sponge function）。
4 其他几个算法介绍
其他常用的密码杂凑算法还有MD4、MD5以及SHA（Secure Hash Algorithm，安全杂凑算法）。
MD4（Message Digest）是Ronald L. Rivest在1990年设计的，已经被成功攻击，因此改进为MD5。MD4和MD5的杂凑值长度都是128位。再之前，1989年曾经发布过MD2，与之不同的是，MD2的安全性依赖于字节间的随机置换[5]。
SHA系列算法是NSA4）和NIST共同发布的安全杂凑算法标准（SHS，Secure Hash Standard），其中SHA-1和SHA-2的对比如表2所示5）。
SHA-3发布于2012年，发布為FIPS6） 202， SHA-3 Standard： Permutation-Based Hash and Extendable-Output Functions7）。SHA-3发布并不是说SHA-2就不安全了，在一段时间内，两者可以并存。SHA-3之前的名称为Keccak。Keccak采用了海绵结构，可以生成任意长度的杂凑值，为了与SHA-2兼容，SHA-3中规定了表2中的各种版本。SHA-3从根本上解决了M-D结构设计中的弱点。Keccak算法比较复杂，在国内也不会大面积应用，本文不再赘述。
5 小结
SM3是密码杂凑算法的一种，其压缩函数与SHA-256的压缩函数结构相似8），在消息分组大小、迭代轮数和输出长度等方面也基本接近。但与SHA-256相比，SM3设计更复杂一些，在安全性和效率上也更高。如本文所述，虽然SM3与SHA-256（SHA-2的一种）安全强度接近，且同为M-D结构的算法，但目前并没有发现对SM3或SHA-2的有效攻击途径。
（注：本文仅做学术探讨，与作者所在单位观点无关）
参考文献
[1] Merkle R C. One Way Hash Functions and DES [C]. In： Brassard G. （eds） Advances in Cryptology — CRYPTO’ 89 Proceedings. CRYPTO 1989.
[2] Damgard I B. A Design Principle for Hash Functions[C]. In： Brassard G. （eds） Advances in Cryptology — CRYPTO’ 89 Proceedings. CRYPTO 1989.
[3] 霍炜，郭启全，马原.商用密码应用与安全性评估[M]. 北京：中国工信出版社/电子工业出版社，2020.
[4] Tiwari， Harshvardhan. Merkle-Damgard Construction Method and Alternatives： A Review [J]. Journal of Information and Organizational Sciences， 2017 （41）：283-304.
[5] Bruce Schneier. 应用密码学：协议、算法与C源程序[M]. 北京：机械工业出版社，2013.