1.1　加密散列函數

在實際應用中，加密散列函數將變長的位字符串輸入固定地映射為定長的位字符串輸出。

如前所述，散列碰撞是不可避免的，但是一個安全的散列函數需要具備抗碰撞性，也就是應該很難發現碰撞。當然，一次碰撞是可以被意外發現或者提前計算的。這就是為什么這類函數始終需要數學證明。

加密散列函數在密碼學中非常重要，并且在數字簽名、模式驗證和消息完整性等許多實際場景中有著廣泛應用。

加密散列需要滿足以下三個主要要求：

·工作因數——為使暴力破解變得困難，加密散列在計算上應該是高代價的。

·黏性狀態——加密散列的狀態不應依賴于合理輸入模式。

·擴散——加密散列的每個輸出比特都應該是與每個輸入比特同樣復雜的函數。

理論上，加密散列函數可以進一步分為使用密鑰的鍵控散列函數和不使用密鑰的非鍵控散列函數。概率數據結構僅僅使用非鍵控散列函數，包括單向散列函數、抗碰撞性散列函數和全域單向散列函數。這些函數僅僅在一些額外屬性上有所差異。

單向散列函數滿足如下要求：

·可以應用于任意長度的數據塊（當然，在實際應用中數據塊的長度不會超過一個很大的值）。

·散列的輸出是定長的。

·它們應該具備抗原像性（單向特性），即給定特定的散列結果，找到該結果對應的輸入在計算上是不可行的。

此外，對于抗碰撞性散列函數來說，給定兩個不同的輸入，它們產生相同散列值的概率應該是非常小的。

如果不具備抗碰撞性，全域單向散列函數需要具備目標耐碰撞性或抗第二原像性，即在計算上找到與指定輸入相同的輸出的第二個不同輸入是不可行的。

需要注意的是，具有抗碰撞性意味著這個函數同時具有抗第二原像性，但是找到抗第二原像性的一般復雜度要比找到碰撞對高得多。

由于它們的設計（特別是工作因數要求），加密散列函數的效率要遠低于非加密散列函數。例如，接下來將要討論的SHA-1函數的速度是540MiB/s[1]，而當下流行的非加密散列函數速度為2500MiB/s，甚至更快。

（1）消息-摘要算法

1991年，Ron Rivest發明了著名的消息-摘要算法（Message-Digest Algorithm，又稱MD5），以替代舊的MD4標準。MD5是一個定義在IETF RFC 1321中的加密散列算法，它以任意大小的消息作為輸入，并生成長度為128比特的散列值作為輸出。

MD5算法基于Merkle-Damg?rd模式。在第一個階段，MD5算法使用符合MD模式的填充函數將任意長度的輸入轉換為一系列固定長度的數據塊（大小為512比特的數據塊或16個大小為32比特的字）。之后，這些數據塊被一個特殊的壓縮函數逐一處理，每一個數據塊都會使用前一個輸出的結果。為了保證壓縮的安全性，MD5算法使用Merkle-Damg?rd增強，然后填充函數使用原始消息的編碼長度。最終的MD5散列摘要（大小為128比特）在處理完最后一個數據塊后生成。

MD5算法通常被用來驗證文件的完整性。相較于通過檢查原始數據來驗證文件是否被更改的方式，比較MD5的散列值已經足夠。

如漏洞說明VU#836068[2]所稱，MD5算法容易遭受碰撞攻擊。算法中發現的缺陷使得使用相同的MD5散列構建不同的消息成為可能。結果是，攻擊者可以生成密碼令牌或其他非法顯示為真實的數據。不再建議將MD5用作安全的加密算法。但是，這種漏洞對概率數據結構影響不大，仍然可以使用。

（2）安全散列算法

安全散列算法由美國國家安全局（NSA）開發，并由美國國家標準技術研究院（NIST）發布。該系列中的第一個算法SHA-0于1993年發布，并很快被其后繼SHA-1所取代，SHA-1已在全球范圍內被廣泛接受。SHA-1產生了更長的160比特（20B）散列值，同時通過修復SHA-0的弱點提高了它的安全性。

SHA-1已在各種應用程序中被廣泛使用了多年，大多數網站都使用基于SHA-1的算法進行簽名。然而，在2005年，SHA-1的一個弱點被發現。因此，在2010年，NIST不贊成將其用于政府用途。而且，從2011年起，它在互聯網上遭到了棄用。與MD5一樣，SHA-1所發現的弱點并沒有影響其用作概率數據結構的散列函數。

SHA-2在2001年發布，其中包括6個具有不同摘要大小的散列函數：SHA-224、SHA-256、SHA-384、SHA-512等。SHA-2比SHA-1更強大，在當前的計算能力下，對SHA-2的攻擊不太可能發生。

（3）RadioGatún

RadioGatún加密散列函數族于2006年在第二屆加密散列研討會上被提出［Be06］。RadioGatún的設計改進了已知的巴拿馬散列函數。

與其他常用的散列函數類似，RadioGatún加密散列函數的輸入被分成一系列數據塊。這些數據塊使用一個特殊函數注入算法的內部狀態，然后迭代應用單個非加密輪函數（稱為belt-and-mill round函數）。在每一輪中，狀態被表示為兩個部分，皮帶和磨機，這兩個部分由輪函數進行不同的處理。輪函數的應用包括四個并行操作：1）應用于磨機的非線性函數，2）應用于皮帶的簡單線性函數，3）以線性方式將磨機的一些位前饋給皮帶，4）以線性方式將皮帶的一些位前饋給磨機。注入所有輸入塊后，該算法將執行多輪，而無須輸入或輸出（空白輪），然后將部分狀態作為最終的散列值返回。

在該系列中，帶有64位字的RadioGatún64是默認選擇，并且是64位平臺的最佳選擇。為了在32位平臺上獲得最佳性能，還可以使用帶有32位字的RadioGatún32。

在相同的時鐘頻率下，據稱RadioGatún32對于長輸入而言，其速度比SHA-256快12倍；對于短輸入而言，其速度比SHA-256快3.2倍，同時門數更少。對于長輸入，RadioGatún64甚至比SHA-256快24倍，但邏輯門卻多出約50％。

[1] Crypto++6.0.0 Benchmarks https://www.cryptopp.com/benchmarks.html

[2] VU#836068 http://www.kb.cert.org/vuls/id/836068