劉玉杰 劉建東 劉 博,2 鐘 鳴 李 博

1(北京石油化工學(xué)院信息工程學(xué)院 北京 102617) 2(北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院 北京 100029)

0 引 言

Hash函數(shù)最早由Knuth在1950年提出，它是一種單向函數(shù)，用于將大數(shù)據(jù)塊壓縮為該數(shù)據(jù)的較小的固定大小表示形式，稱為消息摘要或Hash值[1-2]。作為現(xiàn)代密碼學(xué)的重要研究內(nèi)容之一，Hash函數(shù)在信息安全領(lǐng)域中起著至關(guān)重要的作用，同時也是近幾年正興起的區(qū)塊鏈技術(shù)中的關(guān)鍵技術(shù)之一，密碼學(xué)家王小云因其所帶領(lǐng)的課題組成功碰撞了MD5等經(jīng)典加密算法獲得2019年未來科學(xué)大獎“數(shù)學(xué)與計算機科學(xué)獎”，Hash函數(shù)的研究再一次獲得了社會各界的關(guān)注。

安全是哈希函數(shù)的首要要求[3]，在MD5等傳統(tǒng)Hash算法被王小云教授課題組成功碰撞后，業(yè)界迫切需要尋找更加安全的Hash函數(shù)構(gòu)造方法。傳統(tǒng)的Hash函數(shù)構(gòu)造大多使用按位AND、OR、XOR和MOD等運算符來對數(shù)據(jù)進行雜湊處理，以增強其哈希輸出中的隨機性。文獻[4]提出了一種具有多項式函數(shù)的構(gòu)造方法，提升了部分性能，但是同樣避免不了使用上述運算符。2002年出現(xiàn)了一種利用混沌模型構(gòu)造Hash函數(shù)的方法，其利用較少的運算符就能充分使數(shù)據(jù)隨機性增強，成為一種新的研究思路，并且出現(xiàn)了較多的基于混沌映射的Hash算法?；煦缦到y(tǒng)具有良好的特征，與加密要求有很強的關(guān)聯(lián)性[5-6]。典型的混沌系統(tǒng)模型主要有連續(xù)系統(tǒng)模型和離散系統(tǒng)模型，帳篷映射就是一種經(jīng)典的離散混沌系統(tǒng)。將基于混沌的Hash函數(shù)構(gòu)造方法與傳統(tǒng)Hash函數(shù)構(gòu)造方法相結(jié)合，即將帳篷映射整數(shù)化，既能凸顯出基于混沌的Hash函數(shù)的優(yōu)良特性，又能避免出現(xiàn)因精度效應(yīng)導(dǎo)致的安全缺陷。同時通過添加動態(tài)參數(shù)，成立動態(tài)整數(shù)帳篷映射，這樣既可以避免整數(shù)帳篷映射的短周期行為，又保有其伸長與折疊的非線性本質(zhì)。最后利用耦合映象格子對動態(tài)整數(shù)帳篷映射進行耦合，極大地提高了系統(tǒng)的混亂與擴散性質(zhì)，進而使其在應(yīng)用中具有更高的安全性[7]。

除安全性問題外，效率是Hash函數(shù)的另一個重要問題。Rivest在Crypto2008上提出了MD6算法，MD6算法的數(shù)據(jù)塊大小為512字節(jié)，(而MD5的數(shù)據(jù)塊大小是512比特)，鏈值長度為1 024比特，可從其中摘出0～512比特的值作為最終Hash值，最重要的是MD6算法在其中增加了并行機制，非常適用于多核CPU，契合了時代的發(fā)展。另外SHA系列也是利用MD迭代結(jié)構(gòu)，其效率隨著文件大小的增加而迅速下降，所以目前研究方向是提出一種新穎的Hash函數(shù)，這種Hash函數(shù)在處理大量數(shù)據(jù)時可以保持較高的效率[8]。隨著信息時代的發(fā)展，產(chǎn)生巨大信息的同時，也要能夠快速地對大量數(shù)據(jù)進行處理，多核處理器技術(shù)(CMP)的發(fā)展提供了快速運算的可能?；谏鲜鲈?，本文采用MD6算法框架，利用多核處理器技術(shù)，設(shè)計出一種核心算法采用耦合動態(tài)整數(shù)帳篷映象格子模型的新型并行Hash函數(shù)算法。

1 耦合動態(tài)整數(shù)帳篷映象格子模型

1.1 動態(tài)整數(shù)帳篷映射

將帳篷映射進行整數(shù)化，并引入動態(tài)參量，即得到動態(tài)整數(shù)帳篷映射。它不僅解決了整數(shù)帳篷映射的短周期問題，還具備帳篷映射均勻分布的特性，性能優(yōu)良[7]。其數(shù)學(xué)描述如下：

(1)

gi=(xi+ki)mod 2n

(2)

F映射中(圖1)，ki為動態(tài)變量，表示“帳篷”橫坐標移動的距離，控制其水平移動。xi表示第i步迭代結(jié)果；2n為x(i)取值的整數(shù)集上界。迭代運算中，隨著i值的變化，ki取不同的值，即ki的值與算法迭代步數(shù)有關(guān)，既保證了動態(tài)性又保證了的算法的穩(wěn)定性，不會使得因動態(tài)參數(shù)改變而使最終值改變。

圖1 動態(tài)整數(shù)帳篷映射

1.2 耦合動態(tài)整數(shù)帳篷映象格子模型

利用耦合映像格子模型(CML)將動態(tài)整數(shù)帳篷映射進行耦合，進而獲得性能更好的密碼序列。CML所生成序列的復(fù)雜性直接影響其構(gòu)造出的密碼系統(tǒng)的安全性，而其又受到所選用的非線性函數(shù)、系統(tǒng)格子規(guī)模大小、耦合系數(shù)及非線性函數(shù)參數(shù)的取值等的影響[9]，將耦合映象格子系統(tǒng)的非線性函數(shù)選為動態(tài)整數(shù)帳篷映射，耦合方式如下：

xi(n+1)=

(f[xi(n)]+f[xi-1(n)]+f[xi+1(n)])mod 2k

(3)

式中：xi(n+1)表示第i個格點的第n+1步迭代所得狀態(tài)值；f(·)表示格點的非線性函數(shù))；2k為格點取值的狀態(tài)數(shù)目。每一個格點既由上一步迭代的三個格點值所影響，又能對下一步迭代的三個格點產(chǎn)生影響，其過程如圖2所示。圖2中，實心點表示格點，空心點表示虛擬格點，虛擬格點為迭代計算提供邊界條件[9]。

圖2 模型耦合方式

2 多核并行計算技術(shù)

多核處理技術(shù)(CMP)是在一塊芯片上集成兩個及以上的處理器核，通過這種方式來增強芯片計算性能。CMP通過在兩個及以上的CPU核上分配工作負荷，并且依靠內(nèi)存和輸入輸出的高速片上互聯(lián)和高帶寬管道對系統(tǒng)性能進行提升。較之當前的單核處理器，多核處理器能帶來更多的性能和生產(chǎn)力能效。因此針對多核處理器設(shè)計對應(yīng)的加密算法能夠使得雜湊算法更加快捷。

同時利用英特爾的超線程技術(shù)，把多線程處理器內(nèi)部的兩個邏輯內(nèi)核模擬成兩個物理芯片，舉例來說就是單個處理器就能夠模擬出兩個線程來實現(xiàn)并行，進而兼容多線程操作系統(tǒng)和軟件。超線程技術(shù)充分利用空閑CPU資源，在相同時間內(nèi)完成更多的工作。通過超線程技術(shù)，可以將雙核心的處理器，模擬出4個線程處理器的效果。本文所有測試都是在Intel(R) Core(TM) i5- 6200U@2.30 GHz 2.40 GHz雙核處理器，利用超線程技術(shù)模擬出四個線程實現(xiàn)。

各種并行計算平臺的存在允許各種算法和操作的并行實現(xiàn)。一種流行的并行平臺是共享內(nèi)存并行機(SMPM)，它是一種多核共享內(nèi)存計算機，通常使用OpenMP(開放式多處理)API[10-11]。OpenMP采用Fork-Join模型，如圖3所示。

圖3 Fork-Join模型

OpenMP由Compiler Directives(編譯指導(dǎo)語句)、Run-time Library Functions(庫函數(shù))等組成，使用方式比較容易，很多研究人員做并行算法都會首先選擇使用。本文算法也是使用了openMP中的sections-section實現(xiàn)了并行。

3 并行Hash函數(shù)構(gòu)造

3.1 運算模式

執(zhí)行模式的確定。參數(shù)L確定如圖4的Merkle樹的執(zhí)行模式。MD6中L默認值為64，此時為一顆完整的Merkle樹，執(zhí)行模式為并行模式；如果L值等于0，則為串行模式，按順序串行執(zhí)行；如果L的值介于0和64之間，則進行混合模式，首先從層次0到層次L，然后在每個層次內(nèi)按順序壓縮函數(shù)。本文中取L=64，以實現(xiàn)并行化。

數(shù)據(jù)填充。算法的輸入?yún)⒘繛殚L度小于264比特的消息，算法中的計量單位是“字”，一個“字”等于8字節(jié)，圖4中每個節(jié)點的大小為16個“字”，所以進行一次壓縮函數(shù)運行需要64個“字”的初始輸入。要實現(xiàn)4個線程并行處理數(shù)據(jù)，進行運算的數(shù)據(jù)應(yīng)滿足其形成的節(jié)點數(shù)為4的次冪，即總字節(jié)數(shù)除以128后為4的次冪。所以算法先對初始數(shù)據(jù)進行判斷，如果不能滿足上述情況，則用“0”進行填充，以滿足條件。

算法運算模式如圖4所示?？梢钥闯?，整棵樹被分成四個部分，每一個部分由一個線程執(zhí)行，最后將四個線程的結(jié)果匯總到一起進行最后一次Hash計算并從中得到摘要值。利用openMP的fork-join模式，先劃分再匯總，以實現(xiàn)并行化提升效率。每個線程中的運行方式相同，收到足夠的消息塊即512字節(jié)的數(shù)據(jù)即調(diào)用壓縮函數(shù)，逐級深入，整個過程只需要開辟一個很小的結(jié)構(gòu)體空間，存儲各級數(shù)和當前需處理的數(shù)據(jù)等信息[13]。

圖4 Merkle樹

3.2 壓縮函數(shù)

壓縮函數(shù)的輸入是大小為80個“字”的數(shù)據(jù)塊，其具體表示如圖5所示。Q為一個15個“字”的向量，這一部分可以修改。U為節(jié)點ID號，其大小為1個“字”，指示分塊的位置，包括節(jié)點所在層次和在層次內(nèi)具體位置，大小分別為1個字節(jié)和7個字節(jié)。B是大小為64個“字”的數(shù)據(jù)塊，與4個16的“字”的節(jié)點相對應(yīng)。

圖5 壓縮函數(shù)的輸入

取系統(tǒng)格子規(guī)模L=16，對應(yīng)最終節(jié)點大小16個“字”。壓縮函數(shù)核心步驟如下[14]：

1) 將每個壓縮函數(shù)的輸入劃分成20×32字節(jié)的消息字m0，…，mp，…，m19。

2) 每個消息字按從高到低位劃分為4×8個字節(jié)：C1、C2、C3、C4。

3) 嵌入消息塊Mn。具體嵌入過程如下所示?？偣残枰M行兩輪操作，每一輪操作執(zhí)行4次迭代過程。兩輪操作過后，每個消息字都被使用了4次，在每一輪中將消息塊與格點變量進行混合。

第一輪：

第8×n次迭代：

xj,8×n=xj,8×n+mpj=0,…,4;p=0,…,4

第8×n+1次迭代：

xj,8×n=xj,8×n+1+mpj=0,…,4;p=5,…,9

第8×n+2次迭代：

xj,8×n=xj,8×n+2+mpj=0,…,4;p=10,…,14

第8×n+3次迭代：

xj,8×n=xj,8×n+3+mpj=0,…,4;p=15,…,19

第二輪：

第8×n+4次迭代：

第8×n+5次迭代：

第8×n+6次迭代：

第8×n+7次迭代：

4) 在對所有的消息塊進行如上操作之后,接著對式(4)進行r次迭代，取出最后一次迭代結(jié)果，即得到最后的16個“字”的輸出，然后在從中截取長度為d的最終Hash值。

4 實驗結(jié)果與分析

4.1 數(shù)據(jù)敏感性分析

首先分別對以下幾種情況的消息文本進行仿真實驗：

T1:2.5Mbytes大小的消息文本。
T2：第一個大寫字母變?yōu)樾憽?br/>T3：中間一個句號變?yōu)槎禾枴?br/>T4：刪除末尾的一個字符。
T5：將中間的‘a(chǎn)’變?yōu)椤産’。

通過實驗得到的各種情況十六進制Hash值分別為：

T1:9c4b00e85d2d12a6e45d4cc43beccfa2。
T2：5d6d72613c163a7697b6eb8ec05579ee。
T3：a63b3d85950c8d42a87a931ac36eaef2。
T4：b050eadf93061e6a799470e9abaccd0e。
T5：f4841a6b5b442b169d8f81d42bb71e2e。

如果采用0，1序列來表示Hash值，上述各種情況對應(yīng)的結(jié)果如圖6所示。從仿真結(jié)果可以看出，明文消息文本的微小改變一定會對Hash值的生成產(chǎn)生極大的影響。

圖6 Hash值對明文消息敏感度的測試

4.2 混亂與擴散性質(zhì)統(tǒng)計分析

一般用以下4個統(tǒng)計量來檢測算法的混亂與擴散性質(zhì)：

(1) 平均比特變化數(shù)：

(4)

(2) 平均比特變化率：

(5)

(3) 比特變化數(shù)的均方差：

(6)

(4) 比特變化率的均方差：

(7)

表1 混亂與擴散性質(zhì)統(tǒng)計結(jié)果

4.3 抗碰撞性分析

Hash函數(shù)的抗碰撞性是檢驗其安全性的一個重要測試，如果能夠找到兩個不同的明文消息，其經(jīng)過算法處理后產(chǎn)生的Hash值相同，則稱為碰撞攻擊。方法如下：首先選取一段明文消息求出其Hash值，以ASCII字符來表示；然后改變明文中1 bit的值，得經(jīng)過計算得到一個新的Hash值。對兩個Hash值進行比對，若兩個Hash值在相同位置上的ASCⅡ字符相同，則稱被擊中1次。測試結(jié)果如圖7所示，1 024次測試中有83次測試擊中1次，2次測試擊中2次，5次及以上是16次，碰撞率約為0.098 633。

圖7 相同位置上ASCII字符相同的數(shù)目分布

4.4 字符距離測試

字符距離是一種用來檢驗兩個不同明文消息產(chǎn)生的Hash值是否相互獨立的統(tǒng)計量，定義如下：

(8)

式中：d為字符距離；H1[i]和H2[i]分別為用十進制數(shù)來表示的兩個不同Hash值的第i個字節(jié)的值；s為所得的Hash值的字節(jié)長度。如果兩個被檢驗的Hash值獨立并且各字節(jié)取值服從均勻分布，所求得的平均字符距離值理論上應(yīng)為85.33。測試方法同抗碰撞檢驗類似，在求得一段明文消息的Hash值后，隨機改變1比特明文，求得一個新的Hash值，比較兩個Hash值的字符距離。共進行1 024次測試，得平均字符距離為85.89，同時通過表2與其他算法進行對比，本算法的平均字符距離非常接近理論值，可以認為更改原明文消息1 bit后，新的Hash值與原Hash值是相互獨立的。

表2 算法的平均字符距離

4.5 NIST隨機性測試

NIST測試套件是由15個測試組成的統(tǒng)計軟件包，這些是為了測試隨機(任意長度)由基于硬件或軟件的密碼隨機或偽隨機數(shù)生成器產(chǎn)生的二進制序列。測試關(guān)注于各種不同類型的已存在的非隨機序列。有些測試可以分成各種子測試。NIST測試主要檢測P_value的值與設(shè)定值α的大小比來判斷是否通過測試，α取值為0.01。若P_value≥α，則通過該項測試。測試結(jié)果如表3所示。本文提出的Hash函數(shù)算法生成的序列通過了其中13項測試，可以認為生成的序列是一個比較理想的隨機序列。

表3 NIST隨機性測試結(jié)果

4.6 執(zhí)行效率測試

當初始消息塊的長度不能滿足被分成四塊后每塊形成的數(shù)據(jù)塊個數(shù)為4的次冪時，需要進行數(shù)據(jù)填充，經(jīng)檢測此部分占用了大量時間去處理，這也是下一步需要改進的地方。圖8顯示的是初始數(shù)據(jù)滿足條件時各線程運行時間的對比?？梢钥闯鲈陂_啟1、2/3、4線程算法運行時間是遞減的；在開啟2/3線程運行時間相近是因為都為將4塊數(shù)據(jù)分為兩步處理，因此執(zhí)行速度差別較小。

圖8 算法運行時間

5 結(jié) 語

本文采用MD6架構(gòu)，利用merkle樹來實現(xiàn)并行化，壓縮函數(shù)核心為耦合動態(tài)整數(shù)帳篷映射，結(jié)合傳統(tǒng)邏輯函數(shù)，使得帳篷映射整數(shù)化，并加入動態(tài)參量，最后使用耦合映象格子模型，充分發(fā)揮了混沌系統(tǒng)的隨機性。同時利用merkle樹的結(jié)構(gòu)，并行化處理數(shù)據(jù)，使得雜湊速度在開啟多核情況時倍速增長。對比文獻[9]可以用在對數(shù)據(jù)量較大的信息進行雜湊處理。雖然由于數(shù)據(jù)填充部分使得在填充數(shù)據(jù)時可能會占用大量時間，但是算法通過了各項測試，可以說是有價值的，值得在未來信息安全中使用。