基于糾錯碼的SM3改進算法

鄭明輝，喬譯萱，朱小強，陳 珩

(1.湖北民族大學 智能科學與工程學院，湖北 恩施 445000；2.四川大學 網(wǎng)絡空間安全學院，四川 成都 610065)

在實際的通信過程中，數(shù)據(jù)保密性和數(shù)據(jù)完整性是傳輸數(shù)據(jù)的基本安全需求。密碼雜湊算法作為基礎的密碼算法之一，主要功能是提供數(shù)據(jù)的完整性檢驗，即數(shù)據(jù)經(jīng)過信道傳輸和存儲過程未被未授權(quán)方修改。密碼雜湊算法的實質(zhì)是將任意長度的消息序列映射成固定長度的輸出值（也稱為雜湊值）。并且無法從雜湊值反推出原本的消息序列，稱為雜湊函數(shù)的單向性?；谠撎匦?，雜湊值可以構(gòu)造“數(shù)據(jù)指紋”來進行數(shù)據(jù)的完整性檢驗，應用于身份認證、密鑰推導、消息認證碼、區(qū)塊鏈等場景。典型的密碼雜湊算法包括MD5、SHA1、SHA2、SM3等。其中，SM3算法[1]是由國家商用密碼管理辦公室于2010年公布的商用密碼標準，2012年成為行業(yè)標準，并于2016年成為國家標準，2018年正式成為ISO/IEC國際標準[2]。北京大學密碼學研究組開發(fā)維護的密碼算法工具包OpenSSL分支GmSSL支持SM3算法[3]，并在之后的正式版本中添加了SM3算法的實現(xiàn)[4]。

Merkle-Damgard（記作MD）結(jié)構(gòu)[5-6]是密碼雜湊算法的經(jīng)典迭代結(jié)構(gòu)，基于該結(jié)構(gòu)所構(gòu)造的雜湊函數(shù)，如果壓縮函數(shù)具有抗碰撞性，則該函數(shù)也具有抗碰撞性。SM3算法作為MD結(jié)構(gòu)的典型代表，將任意長度的數(shù)據(jù)輸入壓縮成256 bit的輸出，能夠有效抵御窮舉攻擊，同時采用消息雙字介入、P置換等方法構(gòu)造具有更高復雜性的輪函數(shù)，使得對SM3算法構(gòu)造原像攻擊是比較困難的[7]。安全性方面，目前針對MD5、SHA-1、RIPEMD、HAVAL等雜湊函數(shù)已找到快速碰撞的方法[8]，同時在碰撞攻擊、區(qū)分器攻擊、原像攻擊方式下，對SM3 算法的攻擊難度相比其他傳統(tǒng)算法更高[9]，能夠在具有高安全性需求的應用場景下進行數(shù)據(jù)傳遞。

然而，由于MD結(jié)構(gòu)是串行結(jié)構(gòu)，在效率上很難突破，同時易遭受消息擴展攻擊及二次碰撞攻擊[10]，所以研究人員開始將目光投向雜湊算法的迭代結(jié)構(gòu)。徐勁松等[11]提出基于并行擴展算法的雜湊函數(shù)，提升了算法安全強度，但不適合短消息的處理。Yang等[12]針對雜湊函數(shù)并行迭代結(jié)構(gòu)的局部碰撞問題提出基于混沌映射的壓縮函數(shù)，增強了算法的抗碰撞能力和運算效率，但由于基于格的并行迭代結(jié)構(gòu)，導致運算開銷沒有顯著降低。Halder等[13]利用2D-CA技術(shù)構(gòu)建雜湊函數(shù)的迭代結(jié)構(gòu)，使算法的隨機性和擴散性有所提升，但算法的輪函數(shù)定義為35輪，運算復雜性不高。Liu等[14]構(gòu)造具有更高隨機性的3D-ECM來充當海綿函數(shù)，同時輸出指定長度的雜湊值，減輕了側(cè)信道攻擊的威脅，但由于構(gòu)造過程中增加字符轉(zhuǎn)換操作，無法保證運算效率的提升。Todorova等[15]提出基于Zaslavsky混沌映射的雜湊算法，該算法具有更強的抗碰撞性，但由于迭代過程中使用較多異或操作，導致算法復雜性不高。王鎮(zhèn)道等[16]將MD5算法迭代過程的64步運算設計為32級的流水線，在保持串行運算的前提下提高了算法的運算速度，但未曾考慮算法安全性。巫光福等[17]以MD5算法為例構(gòu)造基于線性分組碼的密碼雜湊算法，提高了密碼雜湊算法輸出值的隨機性，但產(chǎn)生的雜湊值為128 bit，抗窮舉攻擊能力較弱。

綜上所述，目前針對密碼雜湊算法迭代結(jié)構(gòu)的研究方法主要包含并行計算和混沌映射。其中：并行計算達到了提高數(shù)據(jù)運算效率，但與串行結(jié)構(gòu)相比增大了計算復雜度；混沌映射則是通過提升初值敏感度來增強雜湊算法的抗碰撞性，但未考慮優(yōu)化雜湊值的比特混亂度，雜湊值混亂度的提升也是算法安全性的重要評估條件之一。針對構(gòu)建具有更高隨機性的密碼雜湊算法，本文提出基于糾錯碼的SM3改進算法的設計方案，選用糾錯能力更強的線性分組碼并計算對應的生成矩陣；在生成的有效碼字中選擇8個最優(yōu)碼字串聯(lián)賦值給初始寄存器，同時與每個512 bit消息分組進行迭代壓縮運算，所產(chǎn)生的雜湊值為256 bit，若采用蠻力攻擊，則需要執(zhí)行2256數(shù)量級的操作，保證算法的安全性。實驗結(jié)果表明，本文算法滿足雪崩效應，并在運算效率相近的情況下，產(chǎn)生的雜湊值隨機性更高，同時算法內(nèi)存消耗更少。

1 準備知識

在數(shù)字通信過程中不可避免發(fā)生差錯，對于接收到的數(shù)據(jù)序列，糾錯碼的主要作用是在存儲設備及通信中進行糾錯和檢錯，被廣泛用于密碼學和通信系統(tǒng)中。糾錯碼主要分為分組碼和卷積碼。下面重點介紹分組碼[18]及其相關(guān)知識[19-21]。

定義1（線性分組碼）有限域GFq上 的一個(n,k)線性分組碼C是GFqn上的k維線性子空間，其中，n為分組碼的碼長，碼C中向量稱作碼字，k為信息碼元長度，k/n為 碼的信息率，n-k為 碼C的校驗位或者監(jiān)督位。

定義2（漢明距離）兩個不同碼字之間的漢明距離定義為兩個序列之間對應不同的位數(shù)，記作d。

式中，⊕為異或運算。

碼字間的距離表示碼字之間差異程度的大小。當存在干擾時，距離越大，一個碼字變成另一個碼字的可能性越小。

定義3（最小漢明距離）碼C的最小漢明距離dmin定義為所有任意兩個碼字漢明距離的最小值。對于線性分組碼，記為(n,k,dmin)。

定義4（生成矩陣）對于(n,k,d)線性分組碼，有下列關(guān)系式：

式中：m為k維矢量；k×n的矩陣G稱為線性分組碼C的生成矩陣，G的行向量構(gòu)成碼C的一組基。

對于給定信息碼元長度k、碼長n的 線性分組碼C，其生成矩陣不唯一，并且可以通過初等行變換相互進行轉(zhuǎn)換。其中，無論生成矩陣如何初等變換，碼字都是唯一確定的，任意生成矩陣可產(chǎn)生相同的 2k個碼字。

2 基于糾錯碼的SM3算法構(gòu)造

SM3算法是基于分組迭代的國際密碼雜湊算法，該算法比其他國際雜湊算法標準設計更復雜，具體表現(xiàn)在Merkle Damgard迭代結(jié)構(gòu)中每一輪壓縮都使用2個消息字，以及消息拓展過程中每一輪都使用5個消息字，并且將不同群運算結(jié)合，使明文消息非線性迅速擴散。下面給出基于糾錯碼的SM3改進算法具體構(gòu)造過程。

單個消息分組處理過程主要利用糾錯碼構(gòu)建初始常量并將其嵌入到初始緩存器中，再進行64步迭代操作。具體分為初始常量構(gòu)造、消息預處理、消息擴展、迭代壓縮、雜湊值輸出5個步驟。其中，輸入是最大長度為264-1 bit的消息，輸出是長度為256 bit的消息雜湊值，處理單元是512 bit消息分組。

2.1 初始常量構(gòu)造

在構(gòu)造基于糾錯碼的SM3算法過程中，需要選擇合適的線性分組碼C，一個最優(yōu) (n,k,dmin)分 組碼C必須滿足以下條件。

1）確定n和k，使dmin盡量最大化，則構(gòu)造出的碼C可以提高糾錯能力。

2）確定n和dmin，使k盡量最大化，則構(gòu)造出的碼C可以提高傳輸速率。

3）確定k和dmin，使n盡 量最小化，則構(gòu)造出的碼C可以提高傳輸速率。

綜上所述，構(gòu)造性能良好的糾錯碼，需要考慮信息k、碼長n、最小漢明距離dmin這3個參數(shù)的相互制約問題，達到傳輸效率及糾錯能力的平衡。

根據(jù)可變擬陣搜索算法和擬陣聯(lián)接度的定義[22]，可以構(gòu)建一類最優(yōu)的二進制線性 (n,k,dmin)碼及它的生成矩陣Ga×b[23]。因為本文所構(gòu)建的加法常數(shù)表需8個32 bit串聯(lián)而成，所以選擇構(gòu)建SM3的線性分組碼為(32,6,16)，并求得該線性分組碼的生成矩陣G6×32。為了使加法常數(shù)能達到隨機化和無規(guī)律性最大化的效果，需要有效降低比特之間的規(guī)律性，經(jīng)過測試，選擇將生成矩陣G6×32進行循環(huán)左移6位，最終產(chǎn)生的雜湊值的熵值達到預期設計要求，即雜湊算法的隨機性更高。生成碼字集合U={u1,u2,···,u2k}，k=6。

基于SM3算法的初始常量及迭代過程的特征，應選擇8個碼字串聯(lián)來構(gòu)建本文算法的初始常量，其中初始常量集合B0以下列方式選?。?/p>

重新構(gòu)造的初始常量應滿足兩個要求：

1）初始常量二進制表示中，1、0的數(shù)量比趨近于1。

2）初始常量二進制表示中，最長1游程小于10，最長0游程小于8。

2.2 消息預處理

假設輸入消息m的 長度為lbit，首先，在消息的末尾先添加比特“1”；再在后面添加k個“0”，k滿足l+1+k≡488 mod 512；再添加64 bit的比特串來表示輸入消息的長度l，得到填充后的消息m′，長度為512×nbit；最后，將消息m′按512 bit進行分組：

式中，n=(l+k+65)/512。

2.3 消息擴展

1）將m′i分為16個32 bit的比特串W0,W1,···,W15。

2）W16,W17,···,W67以下列規(guī)則進行擴展：

式中，Wj為 消息擴展的第j個字，＜ ＜＜k表示循環(huán)左移k比特運算，固定公式P1(·)定義為：

3）W16,W17,···,W67以下列規(guī)則進行擴展：

式中，W′j為消息擴展的第j+69個字。

2.4 迭代壓縮

將初始常量集合B0中8個碼字分別賦值于寄存器A、B、C、D、E、F、G、H中，對第i個消息分組m′i以下列方式迭代：

式中，CF壓縮函數(shù)由64步迭代運算組成，Bi為第i次迭代輸入的集合。將Bi賦值于A、B、C、D、E、F、G、H作為初始寄存器，同時添加中間變量S S1、S S2、TT1、TT2進行左向賦值操作，具體過程描述如式（9）～（12）：

式中，←表示左向賦值運算符，Tj為 32 bit常量，F(xiàn)Fj(·)、GGj(·)為 定義好的布爾函數(shù)[1]，0 ≤j≤63。

將更新后的中間變量TT1、TT2 與寄存器A、B、C、D、E、F、G、H進行狀態(tài)更新，過程描述如下：

1）將初始寄存器A、C、E、G分別賦值于寄存器B、D、F、H，然后將中間變量TT1賦 值于寄存器A。

2）對中間變量TT2 進行公式運算后賦值于E，具體運算過程如下：

式中，固定公式P0(·)定義為：

3）將更新后的寄存器B、F進行循環(huán)左移操作后賦值于寄存器C、G，描述如下：

每輪迭代的輸入都是上一輪迭代的輸出再與512 bit的分組消息進行運算的結(jié)果。

2.5 輸出雜湊值

最終所有消息分組處理完畢之后，最后一個512 bit的輸出即為算法雜湊值。

密碼雜湊算法的安全水平是由它的輸出長度決定的[24]，本文所構(gòu)造的雜湊函數(shù)輸出長度為512 bit，與128 bit的輸出相比更能抵抗原像攻擊、第二原像攻擊和碰撞攻擊。

3 實驗分析與對比

第2節(jié)所構(gòu)造的密碼雜湊函數(shù)是針對SM3算法的改進算法，下面從雪崩效應、信息熵方面進行本文算法的安全性分析，同時通過仿真實驗進行算法運算效率和內(nèi)存損耗性能分析與討論。

3.1 安全性分析

3.1.1 雪崩效應分析

密碼學中約定密碼雜湊算法應滿足雪崩效應，即輸入消息微小的改變會引起雜湊值至少一半以上的位數(shù)發(fā)生變化，以達到更好的混淆效果，利用式（17）～（19）對本文改進算法的雪崩效應進行穩(wěn)定性評估。

式（17）～（19）中，Bi為第i次測試的雜湊值改變的比特數(shù)，P為平均雪崩系數(shù)，N為測試的總次數(shù)，n為雜湊值比特數(shù)，B為平均變化比特數(shù)。理想狀態(tài)下P為50%，表明密碼雜湊算法具有良好的雪崩效應，均方差 ΔP數(shù)值越小，則密碼雜湊算法的穩(wěn)定性越好[25]。

為了進一步驗證改進算法性能，選擇傳統(tǒng)SHA-256算法和SM3算法，以及改進的MD5算法[17]（記為Wu-MD5算法）進行雪崩效應測試。隨機選擇明文消息并計算生成的雜湊值，任意改變消息中的1 bit，同時計算新生成的雜湊值。由于雜湊值長度不同，所以僅針對雪崩系數(shù)P及均方差 ΔP進行數(shù)值比較，結(jié)果如表1所示。值得說明的是，雪崩效應僅是雜湊算法擴散效應的指標之一，其結(jié)果無法直觀地進行4種算法混淆性的優(yōu)劣比較，僅能夠進行雪崩效應的穩(wěn)定性評估。

表1 不同測試次數(shù)下4種算法的雪崩特性統(tǒng)計Tab.1 Avalanche characteristics statistics of four algorithms under different test times

表1結(jié)果表明：在測試總次數(shù)N分別為1 000、5 000、10 000和50 000的情況下，本文算法與其他3種算法的雪崩系數(shù)P均接近50%，達到了雜湊函數(shù)雪崩效應的理想狀態(tài)，說明本文算法擁有良好的混淆和擴散性；同時，本文算法的均方差 ΔP的數(shù)值偏小，充分說明本文算法具有穩(wěn)定的雪崩效應。

3.1.2 信息熵分析

熵反映了信息源的平均不確定性，在密碼學領域內(nèi)，信息熵也是用于衡量信息序列隨機性的一項重要指標。信息序列的隨機性越大，熵值越大；信息序列的隨機性越小，熵值越小[26]。一般熵值的大小也與攻擊者分析雜湊算法的規(guī)律性所需要的時間成正比。利用熵值的大小來度量糾錯碼構(gòu)建的改進密碼雜湊算法的安全性。熵的計算公式為：

式中，H(x)為 消息x的 信息熵，p(xi)為 消息中xi出現(xiàn)的概率。

針對第2節(jié)中生成矩陣G6×32分別進行循環(huán)左移5、6、7位操作，輸入長度為20～500 byte的樣本數(shù)據(jù)，計算在輸入數(shù)據(jù)相同時的雜湊值信息熵，如圖1所示。由圖1可以看出，循環(huán)左移6位時信息熵數(shù)值更高，相對于循環(huán)左移5、7位穩(wěn)定性更好，而循環(huán)左移操作的目的是增大比特之間的無規(guī)律性，說明構(gòu)造的加法常數(shù)值符合算法設計最初指標，即達到隨機性和無規(guī)律性最大化，提升了雜湊值隨機性。

圖1 本文算法中不同循環(huán)左移位數(shù)的信息熵比較Fig.1 Information entropy comparison of different cyclic left shift numbers in the proposed algorithm

為了評估本文算法的雜湊值隨機性，在明文樣本相同的情況下，選擇典型的密碼雜湊算法進行雜湊值的信息熵對比實驗，具體標準為：1）本文算法是基于SM3算法的改進雜湊算法，所以選擇SM3算法進行對比；2）在雜湊值長度都為256 bit的情況下，選擇SHA-256算法進行對比。不同算法的雜湊值信息熵對比實驗結(jié)果如表2所示。

表2 本文算法、SM3算法及SHA-256算法的雜湊值信息熵比較Tab.2 Comparison of information entropy between the proposed algorithm, SM3 algorithm and SHA-256 algorithm

表2表明：在迭代結(jié)構(gòu)相似的情況下，本文算法因為選擇糾錯更強的最優(yōu)碼 (n,k,dmin)來構(gòu)建加法常數(shù)表，雜湊值的熵值相對于 SM3算法有所增加；在雜湊值長度相同的情況下，由于本文算法迭代結(jié)構(gòu)包含消息雙字介入等方法，使得輪函數(shù)復雜性提升，消息能夠快速擴散，從而導致最終生成雜湊值的信息熵值更高，隨機性更強。以上結(jié)果表明，本文所構(gòu)造的SM3改進算法利用糾錯碼技術(shù)有效平衡了雜湊值長度和迭代結(jié)構(gòu)兩個方面，使得算法雜湊值隨機性有所提升，能夠更好地隱藏明文消息和雜湊值之間的關(guān)聯(lián)性。

3.2 性能分析

一般來說，密碼雜湊算法的運算效率及內(nèi)存損耗是需要研究人員考慮的重要方面，在配置為Intel Core i5-9400 2.90 GHz、16 GB RAM的計算機上，進行改進算法與傳統(tǒng)SM3算法的時間效率及內(nèi)存損耗的對比實驗，并進行分析。

3.2.1 運算效率分析

利用 Java 1.8.0_291進行算法運算效率測試。針對不同明文消息長度的輸入，分別選擇本文算法與SM3算法進行效率分析，如圖2所示。

圖2 本文算法與SM3算法時間復雜度比較Fig.2 Comparison of time complexity between the proposed algorithm and SM3 algorithm

由于迭代結(jié)構(gòu)的串行特性，明文消息長度和運行時間成正比，圖2結(jié)果表明，本文算法可以支持算法快速運算，在輸入明文消息長度為40～1 080 byte的條件下，1 s內(nèi)可以進行450～2 000次運算，與SM3算法的運算效率基本一致。

3.2.2 內(nèi)存消耗分析

JProfiler作為商業(yè)授權(quán)的Java性能剖析工具，具有對被分析對象影響較小、針對內(nèi)存（memory）分析功能強大等特點，專用于分析Java SE、Java EE應用程序。利用JProfiler分析工具，針對不同長度的明文輸入，選用30個明文樣本集，對本文改進算法及SM3算法分別進行相同明文輸入的內(nèi)存損耗測試對比，結(jié)果如圖3所示。

圖3 本文算法與SM3算法內(nèi)存損耗比較Fig.3 Comparison of memory loss between the proposed algorithm and SM3 algorithm

由圖3可知：本文算法的內(nèi)存損耗并不高，在明文輸入長度為100～3 000 byte的條件下，隨著消息長度的增加，計算量增大，導致內(nèi)存損耗呈線性增長趨勢；同時，由于本文利用糾錯碼來構(gòu)造加法常數(shù)表，導致在消息長度相同的情況下，本文算法相比于SM3算法內(nèi)存損耗降低0.01～0.07 MB，實現(xiàn)了性能優(yōu)化。

基于糾錯碼的SM3算法是在傳統(tǒng)SM3算法的基礎上進行的改進。改進后的SM3算法不僅具有較強的雪崩效應，且具有更強的隨機性，使攻擊者更難找到其中規(guī)律。上述算法效率及內(nèi)存損耗實驗表明，本文改進算法在效率相同的情況下內(nèi)存損耗有所下降，為高效率、低內(nèi)存需求的應用場景提供技術(shù)參考。

4 結(jié) 論

為了提高雜湊值的隨機性，本文利用糾錯碼可以在數(shù)字通信過程中提高可靠度的特性，提出一種對SM3算法的改進方案。該方案選擇擬陣理論構(gòu)建的線性分組碼(32,6,16)，通過生成矩陣G6×32計算有效碼字，同時利用周期性原則選擇8個碼字構(gòu)建初始常量值，并嵌入到迭代結(jié)構(gòu)中進行64輪運算；從信息熵值和雪崩效應兩個角度進行雜湊值穩(wěn)定性和隨機性評估，同時測試本文算法在運算效率和內(nèi)存損耗的全局性能并進行分析。實驗結(jié)果表明，本文算法具有理想雪崩效應的特性，生成的雜湊值相比其他密碼雜湊算法混亂度有明顯提高，使攻擊者更難逆推出明文消息，具備更高的算法安全性。另外，本文算法在保留傳統(tǒng)密碼雜湊算法的串行迭代結(jié)構(gòu)的前提下，能夠在1 s內(nèi)進行450～2 000次高速運算，且內(nèi)存損耗與SM3算法相比降低0.01～0.07 MB，為信息安全領域的應用開發(fā)提供理論參考。在未來的研究工作中，將重點研究密碼雜湊算法的迭代結(jié)構(gòu)，嘗試采用并行結(jié)構(gòu)進行數(shù)據(jù)運算效率的優(yōu)化，并且在區(qū)塊鏈技術(shù)的底層架構(gòu)來驗證優(yōu)化后算法的適用性。