謝宗曉 甄杰 董坤祥

SM3密碼雜湊算法發(fā)布于2010年12月17日1）。密碼雜湊算法也被稱作“雜湊算法”“散列算法”或“哈希算法”。在GM/Z 0001—2013《密碼術語》中，上述幾個術語對應的英文都是hash algorithm。

1 密碼雜湊算法

密碼雜湊算法的主要功能是將一個任意長的比特串映射到一個固定長的比特串。

假設任意長度的消息M，經過函數(shù)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），實際就是單向函數(shù)的要求，對于（3）而言，這個特性指的是抗碰撞性（collision resistance），即防止不同的輸入產生相同的輸出。在實踐中使用的密碼雜湊函數(shù)必須具備強抗碰撞性，例如，MD4、MD5和SHA-1都是因為碰撞攻擊算法而被攻破。通俗而言，就是這些算法H（M），已經能夠產生具備相同散列值h的兩條不同消息M和M′。

由于密碼雜湊算法這個特性，散列值h，就像是消息的“指紋”。顯然，密碼雜湊算法可以用于驗證消息的完整性（integrity），也可以更廣泛地應用于數(shù)字簽名和驗證、消息鑒別碼（message authentication code，MAC）的生成和驗證，以及隨機數(shù)的生成等。

2 SM3密碼雜湊算法

SM3是一種密碼雜湊算法。2012年，SM3被采納為GM/T 0004—2012行業(yè)標準，2016年轉化為GB/T 32905—2016國家標準。具體信息如表1所示。

SM3的將輸入的消息經過填充和迭代壓縮等步驟，生成256比特雜湊值（散列值h）。

GB/T 32905—2016中舉了一個通俗易懂的例子，消息01100001 01100010 01100011，長度l為24，首先①，在末尾加“1”，然后②，添加k個“0”湊成512的倍數(shù)，最后③，添加一個64位比特串，該比特串是輸入消息長度l的二進制表示。

經過填充后的消息，如圖1所示。

SM3中填充后的消息長度是512的倍數(shù)，因為SM3的消息分組長度為512比特。就是說，將填充后的消息m′按512比特進行分組：m′=B（0）B（1）…B（n-1），其中：

（2）

在上述示例中，k=423，因此，n=1。

迭代的過程如下：

其中，CF為壓縮函數(shù)，V（0）在GB/T 32905—2016中已經被賦了一個為256比特的初始值。B（i）為填充后的消息分組。在GB/T 32905—2016附錄A中，m′為16個字，即512比特2）。用于壓縮函數(shù)CF輸入的B（i）需要先進行擴展，擴展后的格式一組68個字，另一組64個字，共132個字。

擴展之后的消息分組B（i）與V（i）作為壓縮函數(shù)的輸入，進行迭代，經過一系列復雜的壓縮運算，最后輸出固定長度256比特的雜湊值，具體示例可以參考GB/T 32905—2016附錄A。

3 基于M-D結構的算法

MD5和SHA-1都已經被證明不安全，SHA-2雖然沒有發(fā)現(xiàn)有效攻擊，由于SHA-1和SHA-2結構過于類似，NIST3）在2012年就已經宣布其不安全。上述幾個算法，都采用了Merkle-Damgard結構（簡稱M-D結構）。

M-D結構是Ralph C. Merkle和Ivan Bjerre Damgard在1989年各自獨立發(fā)表的[1，2]，其基本原理是先將填充后的消息均勻分組，指定一個初始向量，然后將消息分組和向量順序輸入至壓縮函數(shù)，過程如圖2所示，最后輸出的就是雜湊值。顯然，SM3密碼雜湊算法也采用了M-D結構。

諸多研究表明，如果壓縮函數(shù)是安全的，那么以此為基礎的雜湊算法也是安全的[3]，也就是說，基于M-D結構的雜湊算法安全性取決于壓縮函數(shù)的安全性，尤其是在抗碰撞性方面。但是，M-D結構也存在弱點，可能難以對抗長度擴展攻擊（length extension attacks）[4]，因此SHA-3已經改用海綿函數(shù)（sponge function）。

4 其他幾個算法介紹

其他常用的密碼雜湊算法還有MD4、MD5以及SHA（Secure Hash Algorithm，安全雜湊算法）。

MD4（Message Digest）是Ronald L. Rivest在1990年設計的，已經被成功攻擊，因此改進為MD5。MD4和MD5的雜湊值長度都是128位。再之前，1989年曾經發(fā)布過MD2，與之不同的是，MD2的安全性依賴于字節(jié)間的隨機置換[5]。

SHA系列算法是NSA4）和NIST共同發(fā)布的安全雜湊算法標準（SHS，Secure Hash Standard），其中SHA-1和SHA-2的對比如表2所示5）。

SHA-3發(fā)布于2012年，發(fā)布為FIPS6） 202， SHA-3 Standard：? Permutation-Based Hash and Extendable-Output Functions7）。SHA-3發(fā)布并不是說SHA-2就不安全了，在一段時間內，兩者可以并存。SHA-3之前的名稱為Keccak。Keccak采用了海綿結構，可以生成任意長度的雜湊值，為了與SHA-2兼容，SHA-3中規(guī)定了表2中的各種版本。SHA-3從根本上解決了M-D結構設計中的弱點。Keccak算法比較復雜，在國內也不會大面積應用，本文不再贅述。

5 小結

SM3是密碼雜湊算法的一種，其壓縮函數(shù)與SHA-256的壓縮函數(shù)結構相似8），在消息分組大小、迭代輪數(shù)和輸出長度等方面也基本接近。但與SHA-256相比，SM3設計更復雜一些，在安全性和效率上也更高。如本文所述，雖然SM3與SHA-256（SHA-2的一種）安全強度接近，且同為M-D結構的算法，但目前并沒有發(fā)現(xiàn)對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]. 北京：中國工信出版社/電子工業(yè)出版社，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. 應用密碼學：協(xié)議、算法與C源程序[M]. 北京：機械工業(yè)出版社，2013.