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

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

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

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

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

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

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

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

　　3.給定M，很容易計(jì)算h;

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

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

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

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

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

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

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

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