基于隨機(jī)化的混沌單分組散列函數(shù)的設(shè)計與實現(xiàn)

■尹滄濤，李永珍

（1.延邊職業(yè)技術(shù)學(xué)院，吉林 延吉 133000；2.延邊大學(xué)，吉林 延吉 133000）

隨著網(wǎng)絡(luò)技術(shù)和電子商務(wù)的迅速發(fā)展，保護(hù)數(shù)據(jù)的隱私和安全已經(jīng)成為了一項極其重要的任務(wù)。為了更好地保護(hù)數(shù)據(jù)的安全，密碼學(xué)研究不斷向前推進(jìn)，引入了許多新的技術(shù)和方法。其中，哈希函數(shù)就是密碼學(xué)領(lǐng)域中的一種重要技術(shù)。哈希函數(shù)是一種將任意長度的消息壓縮到固定長度的技術(shù)，它的輸出值稱為消息的哈希值或摘要。哈希函數(shù)是一種重要的不可逆加密算法，從而保護(hù)數(shù)據(jù)的完整性和安全性。本文對MD5 算法進(jìn)行改進(jìn)，意在進(jìn)一步保護(hù)短消息在傳輸和保存方面的安全性。

一、相關(guān)理論基礎(chǔ)

（一）哈希函數(shù)及MD 系列

哈希函數(shù)是一種將任意長度的輸入數(shù)據(jù)映射為固定長度輸出的函數(shù)，哈希函數(shù)具有以下特性：唯一性、一致性、不可逆性、抗碰撞性。哈希函數(shù)在計算機(jī)科學(xué)和密碼學(xué)中有廣泛應(yīng)用，例如，數(shù)字簽名、消息認(rèn)證、密碼學(xué)中的密鑰派生等領(lǐng)域。常見的哈希函數(shù)包括MD 系列、SHA 系列、RIPEMD等。MD系列是由美國密碼學(xué)家Ronald Rivest 發(fā)明的一系列哈希函數(shù)，包括MD2、MD4、MD5 三種算法。這些算法都是基于Merkle-Damg rd 結(jié)構(gòu)的迭代哈希函數(shù)，其核心思想是將消息分為若干個塊，對每個塊進(jìn)行一系列的變換操作，最終得到一個固定長度的哈希值。

（二）混沌理論

混沌理論是一種研究非線性系統(tǒng)的數(shù)學(xué)理論，它最初被提出描述混沌現(xiàn)象，即一種看似隨機(jī)無序、但實際上有規(guī)律的現(xiàn)象?；煦缋碚撚衫钐鞄r和Yorke J A 于1975 年提出[1]。現(xiàn)已成為一個廣泛研究的領(lǐng)域，涉及物理學(xué)、生物學(xué)、社會科學(xué)等多個領(lǐng)域，其具備下列特征：確定性、敏感性依賴、自相似性、穩(wěn)定的隨機(jī)性、非線性。

混沌系統(tǒng)的輸出是非線性的、無規(guī)律的，并且受初始條件的微小變化而產(chǎn)生不同的結(jié)果，這些特性使得混沌系統(tǒng)的輸出可以被用作密碼學(xué)中的加密和解密。

目前混沌系統(tǒng)在密碼學(xué)中的應(yīng)用主要體現(xiàn)在哈希函數(shù)的改造上。通過混沌系統(tǒng)的改造，可以使哈希函數(shù)的輸出更加隨機(jī)和無序，從而提高哈希函數(shù)的安全性和抗攻擊能力。

（三）隨機(jī)化結(jié)構(gòu)

目前，對哈希函數(shù)的傳統(tǒng)攻擊手段，如長度擴(kuò)展攻擊，第二原像攻擊，中間相遇攻擊等，都是以明確函數(shù)內(nèi)部結(jié)構(gòu)為前提。2004 年王小云教授等人提出了差分攻擊，成功地對具有MD 結(jié)構(gòu)的算法進(jìn)行了有效的碰撞，這進(jìn)一步增加了哈希函數(shù)的安全隱患。差分攻擊是通過尋找哈希函數(shù)內(nèi)部不同輸入值之間的差異，破解函數(shù)的攻擊方法。它利用哈希函數(shù)的差分特性，找出一些輸入的差異，從而推導(dǎo)出哈希函數(shù)的輸出差異。然后，通過這些輸出差異，可以生成兩個不同的輸入，使它們在哈希函數(shù)中產(chǎn)生相同的輸出，即碰撞攻擊。但當(dāng)哈希函數(shù)的算法是不確定的時候，密碼分析將很難著手。對于一個固定的函數(shù)，要保證單向性是比較困難的，因為原則上可以根據(jù)哈希函數(shù)的結(jié)構(gòu)進(jìn)行逆推[2]。但是，在引入隨機(jī)函數(shù)的情況下，哈希函數(shù)的表達(dá)式、結(jié)構(gòu)和形式可能是隨機(jī)的不確定的，因此，逆推哈希函數(shù)變得非常困難。

二、算法的設(shè)計與實現(xiàn)

（一）預(yù)處理階段

本設(shè)計所提出的哈希函數(shù)為更好的適應(yīng)短消息加密，將輸入長度限制為1 bit 至128 bits。若不足128 bits，則填充1 個1 和多個0。將處理好的消息，分成A、B、C、D，4 組每組32 bits（見圖1）。

圖1 算法的初始化過程

對于安全的哈希函數(shù)，在已知哈希值和算法的時候，明文（消息）m 本質(zhì)上是可以推導(dǎo)的，但是通過哈希值計算明文的困難讓我們通常地認(rèn)為它是未知的，所以，如果哈希函數(shù)的具體形式由明文確定，即i=S(m)，哈希值H=fi(m)，則剛好滿足上面提到的“已知明文可以很容易確定函數(shù)的具體形式，已知哈希值很難確定函數(shù)的具體形式”的要求。為減少計算量，存儲量和復(fù)雜度，本設(shè)計在預(yù)處理階段確定哈希函數(shù)的具體形式。將預(yù)處理后的128 bits 內(nèi)容，分為兩組M1 和M2，各64 bits。為消除預(yù)處理階段M2 填充1 和大量0 后可能產(chǎn)生的規(guī)律性。將M1 左循環(huán)移6 bits，M2 右循環(huán)移8 bits 后異或，并對1024 取模，結(jié)果為10 bits 的2 進(jìn)制數(shù)。前8 bits 中，每2 bits 控制第2 節(jié)主循環(huán)中一個邏輯函數(shù)的具體形式。后2 bits 將被保存，并用于第3 節(jié)中混沌加密算法及其分形參數(shù)的確定。

（二）主循環(huán)邏輯

算法的主循環(huán)共經(jīng)過4 輪，每輪4 步的邏輯運算，一共經(jīng)過16 步運算，最終生成長度為128 bits 的輸出結(jié)果。將4 組待操作內(nèi)容，分別與A，B，C，D 四個寄存器中的常量，按位與運算，在本步循環(huán)結(jié)束時獲得的運算變量替換循環(huán)前所保存的寄存器變量，用來更新寄存器內(nèi)容[3]。圖2 描述了該算法主循環(huán)的整體邏輯。

圖2 整體邏輯圖

其中，T 為128 bits 常數(shù)，其作用為對操作內(nèi)容進(jìn)行混淆，消除短消息內(nèi)容上的規(guī)律性。F,G,H,I 為四個函數(shù)列表，內(nèi)部各含有4 個不同的邏輯函數(shù)F=[f1,f2,f3,f4],G=[g1,g2,g3,g4],H=[h1,h2,h3,h4],I=[i1,i2,i3,i4]，每輪將選取列表中的一個函數(shù)參與4 步運算。

附表1 為隨機(jī)函數(shù)的定義，新設(shè)計的邏輯函數(shù)保證了結(jié)果滿足均勻分布的規(guī)律，從而確保循環(huán)后輸出結(jié)果具有統(tǒng)一分布。X[p（i）]為不同輪中分組的使用順序，p（i）函數(shù)具體形式如下：

附表1 隨機(jī)函數(shù)定義表

第一輪中：p（i）=i；

第二輪中：p(i)=(1+5i)mod 4；

第三輪中：p(i)=(5+3i)mod 4；

第四輪中：p(i)=7i mod 4；

（三）混沌加密算法

由于混沌映射具有良好的隨機(jī)性、初始值敏感性，與哈希函數(shù)設(shè)計原則極為貼切。因此，在過去幾十年中，有學(xué)者曾提出過具有混沌映射構(gòu)建哈希函數(shù)的方案[4-6]，本設(shè)計將利用多種參數(shù)可變的混沌加密算法，對循環(huán)后的結(jié)果通過迭代處理的方式產(chǎn)生新的輸出值，以提高哈希函數(shù)的擴(kuò)散性，整個混沌映射流程，見圖3。

圖3 混沌映射算法流程圖

由圖3 可知，為了將得到的A,B,C,D 四個寄存器的值轉(zhuǎn)換為16 個混沌映射的初始值，并落在(0,1)的值域上，首先需做如下線性變換：

βi為消息分塊后的ASCII 值。

定義可變參數(shù)的混沌映射算法如附表2 所示。

附表2 混沌映射定義表

這里將通過第2 節(jié)保存參數(shù)s，確定混沌映射的使用編號。本設(shè)計將μ 設(shè)為固定范圍的可變參數(shù)，為克服周期窗口對混沌映射的影響，其確定方式如下：

隨機(jī)參數(shù)μ 由線性同余隨機(jī)數(shù)發(fā)生器（LCG）產(chǎn)生，選取的混沌變換將進(jìn)行36 次迭代。其中K1,K2,K3,K4 為上一輪輸出結(jié)果的分組，各32 bits。式（2）中233-1，根據(jù)文獻(xiàn)建議進(jìn)行取值，其為一個較大的奇素數(shù)，產(chǎn)生的隨機(jī)數(shù)具有較大周期，保證了參數(shù)μ 的取值空間和隨機(jī)性。

經(jīng)過36 輪迭代計算，得到的混沌序列為：

對迭代結(jié)果x36（1），x36（2），…，x36(16)通過公式進(jìn)行逆變換。

其中floor（x）為向下取整操作，舍去小數(shù)點后的值，以提高哈希函數(shù)的單向性。根據(jù)式（4）可得到16 個0 至255 之間的整數(shù)，每個整數(shù)用8 bits 的2 進(jìn)制數(shù)表示，最終將輸出128 bits 的結(jié)果。

三、實驗測試與分析

本節(jié)首先進(jìn)行混沌的判別分析，驗證設(shè)計中的系統(tǒng)具備混沌狀態(tài)；再通過統(tǒng)計分析、雪崩效應(yīng)以及算法效率三個方面，進(jìn)行對比試驗，驗證設(shè)計的安全性以及效率。

（一）混沌的判別原則

混沌運動是非線性系統(tǒng)特定的運動形式，但是系統(tǒng)的非線性僅是出現(xiàn)混沌運動的必要條件而非充分條件[7]。其判別多先用數(shù)值實驗識別，再通過工程試驗驗證，實驗將采用以下兩種方式驗證系統(tǒng)具備混沌狀態(tài)，即李雅普諾夫指數(shù)法和分岔圖法。

證明一動力系統(tǒng)或自治微分方程穩(wěn)定性的函數(shù)被稱為稱李雅普諾夫指數(shù)(Lyapunov Exponent)，簡稱LE。它沿某一個方向取值的大小與正負(fù)可用來描述動力學(xué)系統(tǒng)的相鄰軌道沿該方向的平均發(fā)散或收斂的快慢程度。正的李雅普諾夫指數(shù)越大，表示運行軌道越發(fā)散，使系統(tǒng)呈現(xiàn)出“既不收斂，也不發(fā)散，也不周期”的混沌態(tài)。一維李雅普諾夫指數(shù)計算公式如下：

其中λ 為李雅普諾夫指數(shù)，f(xi)為一維混沌映射函數(shù)。

分岔圖法中“分叉”指的是當(dāng)系統(tǒng)中的控制參數(shù)略有變化時，如果整個動力系統(tǒng)的結(jié)構(gòu)不穩(wěn)定，系統(tǒng)的拓?fù)浣Y(jié)構(gòu)會突然改變。對于某個特定的參數(shù)，狀態(tài)變量在分叉圖上呈現(xiàn)為一個點或與系統(tǒng)等周期的點，這表明系統(tǒng)處于周期狀態(tài)；如果對于某個控制參數(shù)，分叉圖上有無數(shù)個點，并且每次狀態(tài)都不落在同一個點，則系統(tǒng)處于混沌狀態(tài)。

1.Logistic 映射

圖4 給出了Logistic 映射隨分形參數(shù)μ 變化的李雅普諾夫指數(shù)圖譜。從其圖譜可見，當(dāng)參數(shù)μ∈[3.57,4]時，該映射的李雅普諾夫指數(shù)大于0，進(jìn)入混沌狀態(tài)。圖5 給出了Logistic 映射的分岔圖，當(dāng)參數(shù)μ 大于3.57 時映射取值范圍逐漸增大，符合混沌特點。

圖4 Logistic 映射李雅普諾夫指數(shù)圖譜

圖5 Logistic 映射的分岔圖

2.Tent 映射

Tent 映射常用于圖像加密系統(tǒng)，由圖6 可知，當(dāng)參數(shù)μ 大于1 時，系統(tǒng)的李雅普諾夫指數(shù)皆大于0; 由分岔圖（見圖7）可知，當(dāng)μ 大大于1.75 時，其取值范圍接近滿射。

圖6 Tent 映射下μ 的李雅普諾夫指數(shù)圖譜

圖7 Tent 映射下分岔圖

3.Tent 映射

從圖8,9 中可見Chebyshev 映射的參數(shù)區(qū)間更大，李雅普諾夫指數(shù)也更大，說明其混沌性優(yōu)于前兩者。當(dāng)分形參數(shù)μ 大于1 時進(jìn)入混沌狀態(tài)，大于2 時即可遍歷該區(qū)域所有狀態(tài)點。

圖8 Chebyshev 映射李雅普諾夫指數(shù)圖譜

圖9 Chebyshev 映射分岔圖

4.Sine 映射

Sine 映射是混沌映射的典型代表，它的數(shù)學(xué)形式極為簡單，由圖10、圖11 可知當(dāng)分形參數(shù)μ 大于0.87 時，其進(jìn)入混沌狀態(tài)。

圖10 Sine 映射李雅普諾夫指數(shù)圖譜

圖11 Sine 映射分岔圖

由上述實驗可知，本設(shè)計中可變參數(shù)μ 的取值范圍皆符合混沌要求，可通過迭代計算的方式，將消息通過處理得到的哈希值擴(kuò)展到整個向量空間。

（二）統(tǒng)計分析

為確保哈希函數(shù)的安全性，要求其值域是均勻分布的，否則，攻擊者就能夠以低于暴力破解的代價找到哈希函數(shù)的碰撞[8]。本設(shè)計選取以下六個指標(biāo)對哈希算法進(jìn)行統(tǒng)計分析。

（1）最大變化比特數(shù)Bmax；

（2）最小變化比特數(shù)Bmin；

測試方法如下：首先選取1000 個長度介于1 bit 至128 bits 的短消息，計算輸出結(jié)果，再翻轉(zhuǎn)消息中任意1bit，計算改變后的輸出結(jié)果，將兩者對比得到結(jié)果，如附表3 所示。

附表3 統(tǒng)計分析結(jié)果

由統(tǒng)計測試結(jié)果可以看出，本設(shè)計提出的哈希函數(shù)平均變化比特數(shù)比傳統(tǒng)算法更接近于理想值，平均變化概率P 也非常接近于50%，平均變化比特數(shù)的均方差△B 和平均變化概率的均方差，P 均比傳統(tǒng)算法小，說明其變化幅度很小且非常穩(wěn)定，同時Bmax和Bmin也較小。統(tǒng)計分析結(jié)果表明，本設(shè)計具有良好的抗統(tǒng)計攻擊能力。

（三）雪崩效應(yīng)

哈希函數(shù)不同部件的數(shù)據(jù)關(guān)系越獨立，則越容易在密碼分析的過程中被逐個擊破。因此，良好的雪崩效應(yīng)是一個優(yōu)秀的哈希算法所應(yīng)該具備的。實驗按照雪崩效應(yīng)的原理來設(shè)計實驗，使用1000 對明文對，這些明文對每個都只有一位不同，通過比較兩個明文經(jīng)過算法得到的結(jié)果中不相同的位數(shù)，來作為評判標(biāo)準(zhǔn)[9]。按照雪崩效應(yīng)所描述的，其理想值應(yīng)接近輸出結(jié)果位數(shù)的50%。

圖12—圖14 為本設(shè)計提出的算法與傳統(tǒng)算法的雪崩效應(yīng)實驗結(jié)果，這里規(guī)定百分比大于60%的點和小于40%的點為壞點。經(jīng)過統(tǒng)計發(fā)現(xiàn)各個算法壞點出現(xiàn)的概率如下。MD5：3.2%；單分組哈希函數(shù)SBH：2.25%；本設(shè)計提出算法：1.82%，從統(tǒng)計結(jié)果可以看出，添加具有隨機(jī)化參數(shù)的混沌映射使結(jié)果行成高度關(guān)聯(lián)、廣泛擴(kuò)散的狀態(tài)，有效的提高了哈希函數(shù)的雪崩性和擴(kuò)散效果。

圖12 SBH 雪崩測試結(jié)果

圖13 MD5 雪崩測試結(jié)果

圖14 Ours 雪崩測試結(jié)果

（四）效率分析

為通過累加每次運算的時間，將時間尺度拉大，使結(jié)果便于觀察，在算法效率測試中，每個算法都需要運行10000000 次，在實驗過程中，每次輸入長度為128 bits且各不相同的消息，圖15 為效率對比結(jié)果。

圖15 算法效率對比結(jié)果

從實驗結(jié)果可以看出，本設(shè)計提出的算法與SBH算法相比運行時間增加到了169%，與MD5 相比運行時間減少到了86.9%。由于本設(shè)計在迭代過程中引入36 步混沌映射，所以運算效率低于SBH 算法，但從結(jié)果可以看出，其依舊保留良好的密碼學(xué)算法所需的線性特性。

四、結(jié)語

本設(shè)計提出了一個針對處理短消息的哈希函數(shù)，通過引入隨機(jī)化的思想，使攻擊者在僅知到輸出結(jié)果的情況下，無法確定哈希函數(shù)的具體形式，提高了哈希函數(shù)的單向性，從而加大了攻擊難度。同時，通過多種可變參數(shù)的混沌映射，有效的解決了SBH 算法由于迭代次數(shù)過少，無法進(jìn)行有效擴(kuò)展的問題。由于其屬于線性運算，有效的保證了算法的運行效率。綜上所述，本設(shè)計在保證算法效率的前提下，可以有效地保障短消息在處理過程中的完整性以及安全性。