并行耦合動態整數帳篷Hash函數設計

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

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

0 引 言

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

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

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

1 耦合動態整數帳篷映象格子模型

1.1 動態整數帳篷映射

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

(1)

gi=(xi+ki)mod 2n

(2)

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

圖1 動態整數帳篷映射

1.2 耦合動態整數帳篷映象格子模型

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

xi(n+1)=

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

(3)

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

圖2 模型耦合方式

2 多核并行計算技術

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

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

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

圖3 Fork-Join模型

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

3 并行Hash函數構造

3.1 運算模式

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

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

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

圖4 Merkle樹

3.2 壓縮函數

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

圖5 壓縮函數的輸入

取系統格子規模L=16，對應最終節點大小16個“字”。壓縮函數核心步驟如下[14]：

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

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

3) 嵌入消息塊Mn。具體嵌入過程如下所示。總共需要進行兩輪操作，每一輪操作執行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次迭代，取出最后一次迭代結果，即得到最后的16個“字”的輸出，然后在從中截取長度為d的最終Hash值。

4 實驗結果與分析

4.1 數據敏感性分析

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

T1:2.5Mbytes大小的消息文本。
T2：第一個大寫字母變為小寫。
T3：中間一個句號變為逗號。
T4：刪除末尾的一個字符。
T5：將中間的‘a’變為‘b’。

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

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

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

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

4.2 混亂與擴散性質統計分析

一般用以下4個統計量來檢測算法的混亂與擴散性質：

(1) 平均比特變化數：

(4)

(2) 平均比特變化率：

(5)

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

(6)

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

(7)

表1 混亂與擴散性質統計結果

4.3 抗碰撞性分析

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

圖7 相同位置上ASCII字符相同的數目分布

4.4 字符距離測試

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

(8)

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

表2 算法的平均字符距離

4.5 NIST隨機性測試

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

表3 NIST隨機性測試結果

4.6 執行效率測試

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

圖8 算法運行時間

5 結 語

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