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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　(4)將第一步產(chǎn)生的散列值與第三步產(chǎn)生的散列值組合起來(lái)生成一個(gè)更大的散列值。

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