什麼是Hash函數？

首先介紹下Hash函數

> Hash函數（也稱散列函數或散列演算法）的輸入為任意長度的消息，而輸出為某一固定長度的消息，即Hash函數是一種將任意長度的消息串M映射成為一個定長消息的函數，記為H。稱h=H(M)為消息M的Hash值或消息摘要，有時也稱為消息的指紋。通常Hash函數應用於數字簽名、消息完整性檢查等方面。

設H是一個Hash函數，x是任意長度的二元串，相應的消息摘要為y=H(x)，通常消息摘要是一個相對較短的二元串。假設我們已經計算出了y的值，那麼如果有人改變了x的值為xˊ，則通過計算消息摘要yˊ=H(xˊ)，驗證yˊ與y不相等就可以知道原來的消息x已被改變。

通常，Hash函數可以分為兩類：不帶密鑰的Hash函數和帶密鑰的Hash函數。不帶密鑰的Hash函數只需要有一個消息輸入；帶密鑰的Hash函數規定要有兩個不同的輸入，即一個消息和一個密鑰。


Hash函數的目的是為指定的消息產生一個消息「指紋」，Hash函數通常具有以下這些性質：

- 壓縮性。Hash函數將一個任意比特長度的輸入x，映射成為固定長度為n的輸出H(x)。

- 正向計算簡單性。給定Hash函數H和任意的消息輸入x，計算H(x)是簡單的。

- 逆向計算困難性。對所有預先給定的輸出值，找到一個消息輸入使得它的Hash值等於這個輸出，在計算上是不可行的。即對給定的任意值y，求使得H(x)=y的x在計算上是不可行的。這一性質也稱為單向性。

- 弱無碰撞性。對於任何輸入，找到一個與它有相同輸出的第二個輸入，在計算上是不可行的，即給定一個輸入x，找到一個xˊ，使得H(x)= H(xˊ)成立在計算上是不可行的。

- 強無碰撞性。找出任意兩個不同的輸入x與xˊ，使得H(x)= H(xˊ)成立在計算上是不可行的。

**攻擊者可以對Hash函數發起兩種攻擊。第一種是找出一個xˊ，使得H(x)= H(xˊ)**。例如，在一個使用Hash函數的簽名方案中，假設s是簽名者對消息x的一個有效簽名，s=sig(H(x))。攻擊者可能會尋找一個與x不同的消息xˊ，使得H(x)= H(xˊ)。如果找得到，則攻擊者就可以偽造對消息xˊ的簽名，這事因為s也是對消息xˊ的有效簽名。Hash函數的弱無碰撞性可以抵抗這種攻擊。

**攻擊者還可以發起另一種攻擊，同樣一個應用Hash函數的簽名方案中，對手可能會尋找兩個不同的消息x和xˊ**，使得H(x)= H(xˊ)，然後說服簽名者對消息x簽名，得到s=sig(H(x))。由於s=sig(H(xˊ))，所以攻擊者得到了一個對消息xˊ的有效簽名。Hash函數的強無碰撞性可以抵抗這種攻擊。

Hash函數的另一種常見的攻擊方法是生日攻擊，感興趣的讀者可以參閱參考文獻中生日攻擊的的相關資料。為防止生日攻擊，通常的方法就是增加Hash值的比特長度，一般最小的可接受長度為128位。常見的Hash函數，如MD5和SHA分別具有128比特和160比特的消息摘要。

---

推薦閱讀：