哈希函數的原理及應用

    哈希（Hash）函數又稱為散列函數、雜湊函數。它是一種單向密碼體制，即一個從明文到密文的不可逆映射，只有加密過程，沒有解密過程。

    哈希函數可以將滿足要求的任意長度的輸入經過變換后得到固定長度的輸出。這個固定長度的輸出稱為原消息的散列或消息摘要（Message Digest）。哈希函數的數學表述為：

                                    h=H(m)

    其中，H是哈希函數，m是任意長度明文，h是固定長度的哈希值。

    理想的哈希函數對于不同的輸入可以獲得不同的哈希值。如果x、x' 是兩個不同的消息，存在H(x)=H(x'),則稱x和x'是哈希函數H的一個碰撞。

    由于哈希函數的這種單向的特征以及長度固定的特征使得它可以生成消息或者數據塊的消息摘要（也稱為散列值、哈希值），因此在數據完整性和數字簽名領域有著廣泛的應用。

    典型的哈希函數有兩類：消息摘要算法（MD5）和安全散列算法（SHA）。

    1.哈希函數的性質

    哈希函數有以下特點：

    ①壓縮。對于任意大小的輸入x，哈希值H（x）的長度很小，實際應用中哈希函數H產生的哈希值是固定長度。

    ②易計算。對于任意給定的消息，容易技術其哈希值。

    ③單向性。對于給定的哈希值h，要找到m'使得H(m')=h在計算上是不可行的，即求哈希的逆很困難。

    ④抗碰撞性。理想的哈希函數是無碰撞的，但實際算法設計中很難做到。有兩種抗碰撞性：一種是弱抗碰撞性，即對于給定的消息x，要發現另一個消息y，滿足H(x)=H(y)在計算上不可行；另一種是強抗碰撞性，即對于任意一對不同的消息（x,y），使得H(x)=H(y)在計算上不可行。

    ⑤高靈敏性。當一個輸入位發生變化時，輸出位將有一半以上會發生變化。

    2.哈希函數的應用

    （1）消息認證

    在一個開放通信網絡的環境中，信息面臨的***包括竊聽、偽造、修改、插入、刪除、否認等。因此，需要提供用來驗證消息完整性的機制或服務，即消息認證。這種服務的主要功能是確保收到的消息確實與發送的一樣和確保消息的來源真實有效。用于消息認證的最常見的密碼技術是基于哈希函數的消息認證碼。

    （2）數字簽名

    因為非對稱算法的運算速度較慢，所以在數字簽名協議中，哈希函數扮演了一個重要的角色。對消息摘要進行數字簽名，在統計上可以認為與對文件本身進行數字簽名是等效的。

    （3）口令的安全性

    由于哈希函數具有單向性的特征，因此在口令保護中應用非常廣泛。通常，僅將口令的哈希值進行保存，進行口令校驗的時候對比哈希值即可。即使***者獲得了保存的哈希值，也無法計算出口令。

    （4）數據完整性

    比較熟悉的校驗算法有奇偶檢驗和循環冗余校驗碼CRC。這兩種校驗并沒有抗數據篡改的能力，它們一定程度上能檢測并糾正數據傳輸中的信息誤碼，但卻不能防止對數據的惡意破壞。哈希算法消息摘要的特征使它成為目前應用最廣泛的一種數據完整性校驗的算法。

    3.消息摘要算法

    消息摘要算法MD5可以對任意長度的明文產生128位的消息摘要。

    MD5算法是按512位進行處理的，對于任意長度的消息將首先通過填充的方法使其成為512的倍數。首先，要對任意長度的信息進行填充，使信息的長度等于L*512+448，即長度≡448 mod 512 .填充的方法為：首先在消息后面先添加一個位“1”，再依次添加位“0”，直到長度滿足條件；然后，將原始消息的長度以64位表示，添加在最后面，使得信息長度恰好達到512位的倍數。

    MD5將填充后的消息以512為單元分為L個分組，然后對每個分組進行處理。對每個分組處理的時候，都執行4輪非常相似的運算，每一輪包括了16個類似的步驟。

    每一個步驟的數據處理都是針對4個32位記錄單元數據進行的，這4個記錄單元的初始值以十六進制數表示如下：A=0123 4567 ,B =89AB CDEF ,C =FEDC BA98 ,D =7654 3210。進行4輪，共64個步驟運算之后，記錄單元A、B、C、D中的128位即為中間處理的輸出結果，它將作為下個512位分組處理的輸入初始值。這樣，對L個分組都處理完畢后，最后輸出一個128位的哈希結果。

    當第一輪的第一步驟開始處理時，A、B、C、D記錄單元中的值先復制到另外4個記錄單元AA BB CC DD 中。這4個值將在第4輪的最后一個步驟與相關的A B C D相加。在每一個步驟的操作中都是將A B C D中的3個記錄單元中的數據以非線性的操作方式處理，此結果再與512位明文分組中的一個32位子明文分組M[K]及一固定數T[i]相加。相加的結果向左循環移動S位（以<<S表示），再與剩下的第四記錄單元中數據相加。最后的32位結果將重新存入A B C D 中的一個記錄單元中。

    在每一輪的操作中，MD5都使用不同的邏輯運算將3個記錄單元中的數據以非線性方式處理，可以用下面的方式來表示在4個不同輪中，每個步驟的操作程序：

    第一輪：FF（A.B,C,D,M[K],S,T[i]）表示a←b+((F(B,C,D)+M[k]+T[i])<<s)

    第二輪：GG（A.B,C,D,M[K],S,T[i]）表示a←b+((G(B,C,D)+M[k]+T[i])<<s)

    第三輪：HH（A.B,C,D,M[K],S,T[i]）表示a←b+((H(B,C,D)+M[k]+T[i])<<s)

    第四輪：II（A.B,C,D,M[K],S,T[i]）表示a←b+((I(B,C,D)+M[k]+T[i])<<s)

    第四輪最后一個步驟的A B C D輸出，將分別與 AA BB CC DD記錄單元中的數值相加，其結果將成為下一個512位明文分組處理時 A B C D 的初始值。當完成了最后一個分組運算時，A B C D中的設置就是最后哈希值。

    值得一提的是 ，2004年 我國密碼學家王小云所提的雜湊沖撞算法只需少于2的69次方步驟