---------------
什么是 Hash
Hash 的重要特性
Hash 函數的實現
主要的 Hash 算法
Hash 算法的安全問題
Hash 算法的應用
結 論
---------------
Hash，一般翻譯做“散列”，也有直接音譯為"哈希"的，就是把任意長度的輸入（又叫做預映射， pre-image），通過散列算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。
數學表述為：h = H(M) ，其中H( )--單向散列函數，M--任意長度明文，h--固定長度散列值。
在信息安全領域中應用的Hash算法，還需要滿足其他關鍵特性：
第一當然是單向性(one-way)，從預映射，能夠簡單迅速的得到散列值，而在計算上不可能構造一個預映射，使其散列結果等于某個特定的散列值，即構造相應的M=H-1(h)不可行。這樣，散列值就能在統計上唯一的表征輸入值，因此，密碼學上的 Hash 又被稱為"消息摘要(message digest)"，就是要求能方便的將"消息"進行"摘要"，但在"摘要"中無法得到比"摘要"本身更多的關于"消息"的信息。
第二是抗沖突性(collision-resistant)，即在統計上無法產生2個散列值相同的預映射。給定M，計算上無法找到M'，滿足H(M)=H(M') ，此謂弱抗沖突性；計算上也難以尋找一對任意的M和M'，使滿足H(M)=H(M') ，此謂強抗沖突性。要求"強抗沖突性"主要是為了防范所謂"生日攻擊(birthday attack)"，在一個10人的團體中，你能找到和你生日相同的人的概率是2.4%，而在同一團體中，有2人生日相同的概率是11.7%。類似的，當預映射的空間很大的情況下，算法必須有足夠的強度來保證不能輕易找到"相同生日"的人。
第三是映射分布均勻性和差分分布均勻性，散列結果中，為 0 的 bit 和為 1 的 bit ，其總數應該大致相等；輸入中一個 bit 的變化，散列結果中將有一半以上的 bit 改變，這又叫做"雪崩效應(avalanche effect)"；要實現使散列結果中出現 1bit 的變化，則輸入中至少有一半以上的 bit 必須發生變化。其實質是必須使輸入中每一個 bit 的信息，盡量均勻的反映到輸出的每一個 bit 上去；輸出中的每一個 bit，都是輸入中盡可能多 bit 的信息一起作用的結果。
Damgard 和 Merkle 定義了所謂“壓縮函數(compression function)”，就是將一個固定長度輸入，變換成較短的固定長度的輸出，這對密碼學實踐上 Hash 函數的設計產生了很大的影響。Hash函數就是被設計為基于通過特定壓縮函數的不斷重復“壓縮”輸入的分組和前一次壓縮處理的結果的過程，直到整個消息都被壓縮完畢，最后的輸出作為整個消息的散列值。盡管還缺乏嚴格的證明，但絕大多數業界的研究者都同意，如果壓縮函數是安全的，那么以上述形式散列任意長度的消息也將是安全的。這就是所謂 Damgard/Merkle 結構：
在下圖中，任意長度的消息被分拆成符合壓縮函數輸入要求的分組，最后一個分組可能需要在末尾添上特定的填充字節，這些分組將被順序處理，除了第一個消息分組將與散列初始化值一起作為壓縮函數的輸入外，當前分組將和前一個分組的壓縮函數輸出一起被作為這一次壓縮的輸入，而其輸出又將被作為下一個分組壓縮函數輸入的一部分，直到最后一個壓縮函數的輸出，將被作為整個消息散列的結果。
MD5 和 SHA1 可以說是目前應用最廣泛的Hash算法，而它們都是以 MD4 為基礎設計的。
1) MD4
MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年設計的，MD 是 Message Digest 的縮寫。它適用在32位字長的處理器上用高速軟件實現--它是基于 32 位操作數的位操作來實現的。它的安全性不像RSA那樣基于數學假設，盡管 Den Boer、Bosselaers 和 Dobbertin 很快就用分析和差分成功的攻擊了它3輪變換中的 2 輪，證明了它并不像期望的那樣安全，但它的整個算法并沒有真正被破解過，Rivest 也很快進行了改進。
下面是一些MD4散列結果的例子：
MD4 ("") = 31d6cfe0d16ae931b73c59d7e0c089c0
MD4 ("a") = bde52cb31de33e46245e05fbdbd6fb24
MD4 ("abc") = a448017aaf21d8525fc10ae87aa6729d
MD4 ("message digest") = d9130a8164549fe818874806e1c7014b
MD4 ("abcdefghijklmnopqrstuvwxyz") = d79e1c308aa5bbcdeea8ed63df412da9
MD4 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = 043f8582f241db351ce627e153e7f0e4
MD4 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = e33b4ddc9c38f2199c3e7b164fcc0536
2) MD5
MD5(RFC 1321)是 Rivest 于1991年對MD4的改進版本。它對輸入仍以512位分組，其輸出是4個32位字的級聯，與 MD4 相同。它較MD4所做的改進是：
1) 加入了第四輪
2) 每一步都有唯一的加法常數；
3) 第二輪中的G函數從((X ∧ Y) ∨ (X ∧ Z) ∨ (Y ∧ Z)) 變為 ((X ∧ Z) ∨ (Y ∧ ～Z))以減小其對稱性；
4) 每一步都加入了前一步的結果，以加快"雪崩效應"；
5) 改變了第2輪和第3輪中訪問輸入子分組的順序，減小了形式的相似程度；
6) 近似優化了每輪的循環左移位移量，以期加快"雪崩效應"，各輪的循環左移都不同。
盡管MD5比MD4來得復雜，并且速度較之要慢一點，但更安全，在抗分析和抗差分方面表現更好。
消息首先被拆成若干個512位的分組，其中最后512位一個分組是“消息尾+填充字節(100…0)+64 位消息長度”，以確保對于不同長度的消息，該分組不相同。64位消息長度的限制導致了MD5安全的輸入長度必須小于264bit，因為大于64位的長度信息將被忽略。而4個32位寄存器字初始化為A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210，它們將始終參與運算并形成最終的散列結果。
接著各個512位消息分組以16個32位字的形式進入算法的主循環，512位消息分組的個數據決定了循環的次數。主循環有4輪，每輪分別用到了非線性函數
F(X, Y, Z) = (X ∧ Y) ∨ (～X ∧ Z)
G(X, Y, Z) = (X ∧ Z) ∨ (Y ∧ ～Z)
H(X, Y, Z) =X ⊕ Y ⊕ Z
I(X, Y, Z) = X ⊕ (Y ∨ ～Z)
這4輪變換是對進入主循環的512位消息分組的16個32位字分別進行如下操作：將A、B、C、D的副本a、b、c、d中的3個經F、G、H、I運算后的結果與第4個相加，再加上32位字和一個32位字的加法常數，并將所得之值循環左移若干位，最后將所得結果加上a、b、c、d之一，并回送至ABCD，由此完成一次循環。
所用的加法常數由這樣一張表T[i]來定義，其中i為1…64，T[i]是i的正弦絕對值之4294967296次方的整數部分，這樣做是為了通過正弦函數和冪函數來進一步消除變換中的線性性。
當所有512位分組都運算完畢后，ABCD的級聯將被輸出為MD5散列的結果。下面是一些MD5散列結果的例子：
MD5 ("") = d41d8cd98f00b204e9800998ecf8427e
MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661
MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72
MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0
MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = d174ab98d277d9f5a5611c2c9f419d9f
MD5 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = 57edf4a22be3c955ac49da2e2107b67a
參考相應RFC文檔可以得到MD4、MD5算法的詳細描述和算法的C源代碼。
3) SHA1 及其他
SHA1是由NIST NSA設計為同DSA一起使用的，訪問http://www.itl.nist.gov/fipspubs可以得到它的詳細規范--[/url]"FIPS PUB 180-1 SECURE HASH STANDARD"。它對長度小于264的輸入，產生長度為160bit的散列值，因此抗窮舉(brute-force)性更好。SHA-1 設計時基于和MD4相同原理,并且模仿了該算法。因為它將產生160bit的散列值，因此它有5個參與運算的32位寄存器字，消息分組和填充方式與MD5相同，主循環也同樣是4輪，但每輪進行20次操作，非線性運算、移位和加法運算也與MD5類似，但非線性函數、加法常數和循環左移操作的設計有一些區別，可以參考上面提到的規范來了解這些細節。下面是一些SHA1散列結果的例子：
SHA1 ("abc") = a9993e36 4706816a ba3e2571 7850c26c 9cd0d89d
SHA1 ("abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq") = 84983e44 1c3bd26e baae4aa1 f95129e5 e54670f1
其他一些知名的Hash算法還有MD2、N-Hash、RIPE-MD、HAVAL等等。上面提到的這些都屬于"純"Hash算法。還有另2類Hash算法，一類就是基于對稱分組算法的單向散列算法，典型的例子是基于DES的所謂Davies-Meyer算法，另外還有經IDEA改進的Davies-Meyer算法，它們兩者目前都被認為是安全的算法。另一類是基于模運算/離散對數的，也就是基于公開密鑰算法的，但因為其運算開銷太大，而缺乏很好的應用前景。
沒有通過分析和差分攻擊考驗的算法，大多都已經夭折在實驗室里了，因此，如果目前流行的Hash算法能完全符合密碼學意義上的單向性和抗沖突性，就保證了只有窮舉，才是破壞Hash運算安全特性的唯一方法。為了對抗弱抗沖突性，我們可能要窮舉個數和散列值空間長度一樣大的輸入，即嘗試2^128或2^160個不同的輸入，目前一臺高檔個人電腦可能需要10^25年才能完成這一艱巨的工作，即使是最高端的并行系統，這也不是在幾千年里的干得完的事。而因為"生日攻擊"有效的降低了需要窮舉的空間，將其降低為大約1.2*2^64或1.2*2^80，所以，強抗沖突性是決定Hash算法安全性的關鍵。
在NIST新的 Advanced Encryption Standard (AES)中，使用了長度為128、192、256bit 的密鑰，因此相應的設計了 SHA256、SHA384、SHA512，它們將提供更好的安全性。
Hash算法在信息安全方面的應用主要體現在以下的3個方面：
1) 文件校驗
我們比較熟悉的校驗算法有奇偶校驗和CRC校驗，這2種校驗并沒有抗數據篡改的能力，它們一定程度上能檢測并糾正數據傳輸中的信道誤碼，但卻不能防止對數據的惡意破壞。
MD5 Hash算法的"數字指紋"特性，使它成為目前應用最廣泛的一種文件完整性校驗和(Checksum)算法，不少Unix系統有提供計算md5 checksum的命令。它常被用在下面的2種情況下：
第一是文件傳送后的校驗，將得到的目標文件計算 md5 checksum，與源文件的md5 checksum 比對，由兩者 md5 checksum 的一致性，可以從統計上保證2個文件的每一個碼元也是完全相同的。這可以檢驗文件傳輸過程中是否出現錯誤，更重要的是可以保證文件在傳輸過程中未被惡意篡改。一個很典型的應用是ftp服務，用戶可以用來保證多次斷點續傳，特別是從鏡像站點下載的文件的正確性。
更出色的解決方法是所謂的代碼簽名，文件的提供者在提供文件的同時，提供對文件Hash值用自己的代碼簽名密鑰進行數字簽名的值，及自己的代碼簽名證書。文件的接受者不僅能驗證文件的完整性，還可以依據自己對證書簽發者和證書擁有者的信任程度，決定是否接受該文件。瀏覽器在下載運行插件和java小程序時，使用的就是這樣的模式。
第二是用作保存二進制文件系統的數字指紋，以便檢測文件系統是否未經允許的被修改。不少系統管理/系統安全軟件都提供這一文件系統完整性評估的功能，在系統初始安裝完畢后，建立對文件系統的基礎校驗和數據庫，因為散列校驗和的長度很小，它們可以方便的被存放在容量很小的存儲介質上。此后，可以定期或根據需要，再次計算文件系統的校驗和，一旦發現與原來保存的值有不匹配，說明該文件已經被非法修改，或者是被病毒感染，或者被木馬程序替代。TripWire就提供了一個此類應用的典型例子。
更完美的方法是使用"MAC"。"MAC" 是一個與Hash密切相關的名詞，即信息鑒權碼(Message Authority Code)。它是與密鑰相關的Hash值，必須擁有該密鑰才能檢驗該Hash值。文件系統的數字指紋也許會被保存在不可信任的介質上，只對擁有該密鑰者提供可鑒別性。并且在文件的數字指紋有可能需要被修改的情況下，只有密鑰的擁有者可以計算出新的散列值，而企圖破壞文件完整性者卻不能得逞。
2) 數字簽名
Hash 算法也是現代密碼體系中的一個重要組成部分。由于非對稱算法的運算速度較慢，所以在數字簽名協議中，單向散列函數扮演了一個重要的角色。
在這種簽名協議中，雙方必須事先協商好雙方都支持的Hash函數和簽名算法。
簽名方先對該數據文件進行計算其散列值，然后再對很短的散列值結果--如Md5是16個字節，SHA1是20字節，用非對稱算法進行數字簽名操作。對方在驗證簽名時，也是先對該數據文件進行計算其散列值，然后再用非對稱算法驗證數字簽名。
對 Hash 值，又稱"數字摘要"進行數字簽名，在統計上可以認為與對文件本身進行數字簽名是等效的。而且這樣的協議還有其他的優點：
首先，數據文件本身可以同它的散列值分開保存，簽名驗證也可以脫離數據文件本身的存在而進行。
再者，有些情況下簽名密鑰可能與解密密鑰是同一個，也就是說，如果對一個數據文件簽名，與對其進行非對稱的解密操作是相同的操作，這是相當危險的，惡意的破壞者可能將一個試圖騙你將其解密的文件，充當一個要求你簽名的文件發送給你。因此，在對任何數據文件進行數字簽名時，只有對其Hash值進行簽名才是安全的。
3) 鑒權協議
如下的鑒權協議又被稱作"挑戰--認證模式：在傳輸信道是可被偵聽，但不可被篡改的情況下，這是一種簡單而安全的方法。
需要鑒權的一方，向將被鑒權的一方發送隨機串（“挑戰”），被鑒權方將該隨機串和自己的鑒權口令字一起進行 Hash 運算后，返還鑒權方，鑒權方將收到的Hash值與在己端用該隨機串和對方的鑒權口令字進行 Hash 運算的結果相比較（“認證”），如相同，則可在統計上認為對方擁有該口令字，即通過鑒權。
POP3協議中就有這一應用的典型例子：
S: +OK POP3 server ready <1896.697170952@dbc.mtview.ca.us>
C: APOP mrose c4c9334bac560ecc979e58001b3e22fb
S: +OK maildrop has 1 message (369 octets)
在上面的一段POP3協議會話中，雙方都共享的對稱密鑰（鑒權口令字）是tanstaaf，服務器發出的挑戰是<1896.697170952@dbc.mtview.ca.us>，客戶端對挑戰的應答是MD5("<1896.697170952@dbc.mtview.ca.us>tanstaaf") = c4c9334bac560ecc979e58001b3e22fb，這個正確的應答使其通過了認證。
散列算法長期以來一直在計算機科學中大量應用，隨著現代密碼學的發展，單向散列函數已經成為信息安全領域中一個重要的結構模塊，我們有理由深入研究其設計理論和應用方法。