單向散列函數(shù)(HASH函數(shù))基本原理

　　Hash函數(shù)H(m)也名單向散列函數(shù)，它是現(xiàn)代密碼學的核心。散列函數(shù)一直在計算機科學中使用，散列函數(shù)就是把可變的輸入長度串轉換成固定長度輸出值(叫做散列值)的一種函數(shù)。而單向散列函數(shù)是在一個方向上工作的散列函數(shù)，從預映射的值很容易計算機其散列值，但要使其散列值等于一個特殊值卻很難。好的散列函數(shù)也是無沖突的：難于產生兩個預映射的值，使他們的散列值相同。

　　散列函數(shù)是公開的，對處理過程并不保密，單向散列函數(shù)的安全性是它的單向性，其輸出不依賴于輸入。平均而言，預映射值的單個位的改變，將引起散列值中一半位的改變。已知一個散列值，要找到預映射的值，使它的值等于已知的散列值在計算上是不可行的，可把單向散列函數(shù)看作是構成指紋文件的一種方法。如果你驗證某人持有一個特定的文件(你同時也持有該文件)，但你不想他將文件傳給你，那么，就要通知他將該文件的散列值傳給你，如果他傳送的散列值是正確的，那么可以肯定他持有那份文件。散列函數(shù)可用于數(shù)字簽名、消息的完整性檢測、消息起源的認證檢測等。常見的散列算法有MD5、SHA、Snefru和HVAL等。

　　Hash是作用于一任意長度的消息M，返回一固定長度的散列值h:h=H(m)。其中h的長度為m。Hash函數(shù)主要用于封裝或者數(shù)字簽名的過程當中，它必須具有如下幾個性質:

　　1.給定h，根據(jù)H(M)=h計算M在計算上是不可行的;

　　2.給定M，要找到另一消息M’。并滿足H(m)=H(m’)在計算上是不可行的。

　　上述特性中的任何弱點都有可能破壞使用Hash函數(shù)進行封裝或者簽名的各種協(xié)議的安全性，如生日攻擊。Hash函數(shù)的重要之處就是賦予M唯一的“指紋”。如果用戶A用數(shù)字簽名算法H(m)進行簽名，而B能產生滿足H(m)=H(m’)的另一消息M’，那么B就可以聲稱A對M進行了簽名。

　　Hash函數(shù)除了需要上述性質外還需要的性質有：

　　3.給定M，很容易計算h;

　　4.抗碰撞性。即隨機找到兩個消息M和M’，使H(m)=H(m’)在計算上不可行。

　　64位的Hash函數(shù)在生日攻擊面前顯得太小。大多數(shù)的Hash函數(shù)產生128位的散列值。這迫使試圖進行生日攻擊的攻擊者必須對264個隨機文件進行散列運算才能找到散列值相同的兩個文件，因此不足以維持散列函數(shù)的安全性。NIST則在其安全散列標準 (SHS)中用的是160位的散列值。這使生日攻擊更難進行，需要進行280次隨機散列運算。

　　不難分析得出，散列值越長則安全性越好。許多實際應用的單向散列函數(shù)產生128位的散列值，如我們將要使用的MD5算法，這就使得任何想要攻擊一次性函數(shù)的黑客們望而生畏，因此我們不妨考慮如何生成一個長的散列值。以下即為生成一個長散列值的法：

　　(1)運用單向散列函數(shù)生成一則消息的散列值。

　　(2)將該散列值附于消息之后。

　　(3)產生包含散列值和消息在內的一連串的數(shù)值的散列值。

　　(4)將第一步產生的散列值與第三步產生的散列值組合起來生成一個更大的散列值。

　　(5)重復(1)至(3)步若干次。