一種MDx變種Hash函數(shù)——GIN.pdf

1、密碼學(xué)上的Hash函數(shù)(雜湊函數(shù))是指一種將任意長度的消息壓縮到某一固定長度的消息摘要(Message Digest)的函數(shù)。Hash函數(shù)可用于數(shù)據(jù)壓縮、數(shù)據(jù)完整性檢驗，可作偽隨機(jī)數(shù)生成器，可以用于設(shè)計知識證明方案，還是數(shù)字簽名安全有效的充要條件。 Hash函數(shù)h作用于任意長度消息M，返回固定長度的散列值h： h=h(M) 根據(jù)Hash函數(shù)的安全水平，Hash函數(shù)可以分為兩大類： ■強(qiáng)碰撞自由的Hash函

2、數(shù) ■弱碰撞自由的Hash函數(shù)如果函數(shù)h滿足以下條件，則h就是一個強(qiáng)碰撞自由的函數(shù)： 1)h的輸入為任意長度： 2)h的輸出為固定長度(為了抵抗生日攻擊，根據(jù)目前計算能力，輸出至少為128bit)： 3)給定h和M，計算h(M)是容易的； 4)給定h，尋找不同的M1和M2，使得h(M1)=h(M2)是計算上不可行的。 弱碰撞自由的Hash函數(shù)與強(qiáng)碰撞自由的Hash函數(shù)的前三個條件相同，第四

3、個條件為：給定h和一個隨機(jī)選擇的消息M1，找另一個消息M2(與M不同)，使得h(M1)=h(M2)是計算上不可行的。 顯然強(qiáng)碰撞自由的Hash函數(shù)比若碰撞自由的Hash函數(shù)安全性強(qiáng)，因為一個弱自由Hash函數(shù)無法保證找不到一對不同的消息M1，M2，使得h(M1)≠h(M2)。 Hash函數(shù)不僅在安全通信中起著重要的作用，而且是許多密碼算法與密碼協(xié)議安全的基本前提條件，應(yīng)用較為普遍的Hash函數(shù)算法有MD5，RIPEMD，

4、HAVAL，SHA-1等。 由于模差分方法和比特跟蹤方法([25]，[28]，[29])對MD4，MD5，RIPEMD，HAVAL，SHA-0甚至SHA-1等Hash函數(shù)尋找碰撞十分有效，所以研究設(shè)計使得模差分方法和明文修改技術(shù)應(yīng)用較為困難的Hash函數(shù)就變得有實際意義。本文對這一問題進(jìn)行了探索，設(shè)計了一種MDx變種Hash函數(shù)--GIN。 GIN算法采用5個鏈變量，對任意長度的明文生成160bit的雜湊值。GIN采用了

5、較SHA-1復(fù)雜的明文擴(kuò)展算法。在輪函數(shù)中使用了模232加法，采用了線性和非線性結(jié)合的設(shè)計方法。在鏈變量處理過程中，使用了較MD5更為復(fù)雜的鏈變量處理方法。文中對GIN算法進(jìn)行了隨機(jī)性檢測，及軟件實現(xiàn)效率分析。 同時針對GIN算法擴(kuò)展明文處理方法速度較慢的情況，提出了GIN算法的變種算法--GIN2算法，算法速度大幅度提高，并且進(jìn)行了軟件實現(xiàn)效率比較和隨機(jī)性檢測。 然后對GIN算法進(jìn)行了簡要的分析，重點針對模差分和明文修