# Hash 算法與數字摘要

## 定義

Hash（哈希或散列）算法，又常被稱為指紋（fingerprint）或摘要（digest）算法，是非常基礎也非常重要的一類算法。可以將任意長度的二進制明文串映射為較短的（通常是固定長度的）二進制串（Hash 值），並且不同的明文很難映射為相同的 Hash 值。

例如計算 “hello blockchain world, this is yeasy\@github” 的 SHA-256 Hash 值。

```bash
$ echo "hello blockchain world, this is yeasy@github"|shasum -a 256
db8305d71a9f2f90a3e118a9b49a4c381d2b80cf7bcef81930f30ab1832a3c90
```

對於某個文件，無需查看其內容，只要其 SHA-256 Hash 計算後結果同樣為 `db8305d71a9f2f90a3e118a9b49a4c381d2b80cf7bcef81930f30ab1832a3c90`，則說明文件內容（極大的概率）就是 “hello blockchain world, this is yeasy\@github”。

除了快速對比內容外，Hash 思想也經常被應用到基於內容的編址或命名算法中。

一個優秀的 Hash 算法，將能滿足：

* 正向快速：給定原文和 Hash 算法，在有限時間和有限資源內能計算得到 Hash 值；
* 逆向困難：給定（若干）Hash 值，在有限時間內無法（基本不可能）逆推出原文；
* 輸入敏感：原始輸入信息發生任何改變，新產生的 Hash 值都應該發生很大變化；
* 碰撞避免：很難找到兩段內容不同的明文，使得它們的 Hash 值一致（即發生碰撞）。

碰撞避免有時候又被稱為“抗碰撞性”，可分為“弱抗碰撞性”和“強抗碰撞性”。給定原文前提下，無法找到與之碰撞的其它原文，則算法具有“弱抗碰撞性”；更一般地，如果無法找到任意兩個可碰撞的原文，則稱算法具有“強抗碰撞性”。

很多場景下，也往往要求算法對於任意長的輸入內容，輸出為定長的 Hash 結果。

## 常見算法

目前常見的 Hash 算法包括國際上的 Message Digest（MD）系列和 Secure Hash Algorithm（SHA）系列算法，以及國內的 SM3 算法。

MD 算法主要包括 MD4 和 MD5 兩個算法。MD4（RFC 1320）是 MIT 的 Ronald L. Rivest 在 1990 年設計的，其輸出為 128 位。MD4 已證明不夠安全。MD5（RFC 1321）是 Rivest 於 1991 年對 MD4 的改進版本。它對輸入仍以 512 位進行分組，其輸出是 128 位。MD5 比 MD4 更加安全，但過程更加複雜，計算速度要慢一點。MD5 已於 2004 年被成功碰撞，其安全性已不足應用於商業場景。。

SHA 算法由美國國家標準與技術院（National Institute of Standards and Technology，NIST）徵集制定。首個實現 SHA-0 算法於 1993 年問世，1998 年即遭破解。隨後的修訂版本 SHA-1 算法在 1995 年面世，它的輸出為長度 160 位的 Hash 值，安全性更好。SHA-1 設計採用了 MD4 算法類似原理。SHA-1 已於 2005 年被成功碰撞，意味著無法滿足商用需求。

為了提高安全性，NIST 後來制定出更安全的 SHA-224、SHA-256、SHA-384，和 SHA-512 算法（統稱為 SHA-2 算法）。新一代的 SHA-3 相關算法也正在研究中。

此外，中國密碼管理局於 2010 年 12 月 17 日發佈了GM/T 0004-2012 《SM3 密碼雜湊算法》，建立了國內商用密碼體系中的公開 Hash 算法標準，已經被廣泛應用在數字簽名和認證等場景中。

*注：MD5 和 SHA-1 算法的破解工作都是由清華大學教授、中國科學院院士王小云主導完成。*

## 性能

大多數 Hash 算法都是計算敏感型算法，在強大的計算芯片上完成的更快。因此要提升 Hash 計算的性能可以考慮硬件加速。例如採用普通 FPGA 來計算 SHA-256 值，可以輕易達到數 Gbps 的吞吐量，使用專用芯片甚至會更高。

也有一些 Hash 算法不是計算敏感型的。例如 scrypt算法，計算過程需要大量的內存資源，因此很難通過選用高性能芯片來加速 Hash 計算。這樣的算法可以有效防範採用專用芯片進行算力攻擊。

## 數字摘要

數字摘要是 Hash 算法重要用途之一。顧名思義，數字摘要是對原始的數字內容進行 Hash 運算，獲取唯一的摘要值。

利用 Hash 函數抗碰撞性特點，數字摘要可以檢測內容是否被篡改過。

細心的讀者可能會注意到，有些網站在提供文件下載時，會同時提供相應的數字摘要值。用戶下載原始文件後可以在本地自行計算摘要值，並與所提供摘要值進行比對，以確保文件內容沒有被篡改過。

## Hash 攻擊與防護

Hash 算法並不是一種加密算法，不能用於對信息的保護。

但 Hash 算法可被應用到對登錄口令的保存上。例如網站登錄時需要驗證用戶名和密碼，如果網站後臺直接保存用戶的口令原文，一旦發生數據庫洩露後果不堪設想（事實上，網站數據庫洩露事件在國內外都不少見）。

利用 Hash 的防碰撞特性，後臺數據庫可以僅保存用戶口令的 Hash 值，這樣每次通過 Hash 值比對，即可判斷輸入口令是否正確。即便數據庫洩露了，攻擊者也無法輕易從 Hash 值還原回口令。

然而，有時用戶設置口令的安全強度不夠，採用了一些常見的字符串，如 password、123456 等。有人專門蒐集了這些常見口令，計算對應的 Hash 值，製作成字典。這樣通過 Hash 值可以快速反查到原始口令。這一類型以空間換時間的攻擊方法包括字典攻擊和彩虹表攻擊（只保存一條 Hash 鏈的首尾值，相對字典攻擊可以節省存儲空間）等。

為了防範這一類攻擊，可以採用加鹽（Salt）的方法。保存的不是原文的直接 Hash 值，而是原文再加上一段隨機字符串（即“鹽”）之後的 Hash 值。Hash 結果和“鹽”分別存放在不同的地方，這樣只要不是兩者同時洩露，攻擊者很難進行破解。