數(shù)學(xué)表述為：h = H(M) ，其中H( )--單向散列函數(shù)，M--任意長度明文，h--固定長度散列值。

在信息安全領(lǐng)域中應(yīng)用的

第 一當(dāng)然是單向性(one-way)，從預(yù)映射，能夠簡單迅速的得到散列值，而在計(jì)算上不可能構(gòu)造一個(gè)預(yù)映射，使其散列結(jié)果等于某個(gè)特定的散列值，即構(gòu)造相 應(yīng)的M=H-1(h)不可行。這樣，散列值就能在統(tǒng)計(jì)上唯一的表征輸入值，因此，密碼學(xué)上的 Hash 又被稱為"消息摘要(message digest)"，就是要求能方便的將"消息"進(jìn)行"摘要"，但在"摘要"中無法得到比"摘要"本身更多的關(guān)于"消息"的信息。

第 二是抗沖突性(collision-resistant)，即在統(tǒng)計(jì)上無法產(chǎn)生2個(gè)散列值相同的預(yù)映射。給定M，計(jì)算上無法找到M ，滿足H(M)=H(M ) ，此謂弱抗沖突性；計(jì)算上也難以尋找一對任意的M和M ，使?jié)M足H(M)=H(M ) ，此謂強(qiáng)抗沖突性。要求"強(qiáng)抗沖突性"主要是為了防范所謂"生日攻擊(birthday attack)"，在一個(gè)10人的團(tuán)體中，你能找到和你生日相同的人的概率是2.4%，而在同一團(tuán)體中，有2人生日相同的概率是11.7%。類似的，當(dāng)預(yù) 映射的空間很大的情況下，算法必須有足夠的強(qiáng)度來保證不能輕易找到"相同生日"的人。

第 三是映射分布均勻性和差分分布均勻性，散列結(jié)果中，為 0 的 bit 和為 1 的 bit ，其總數(shù)應(yīng)該大致相等；輸入中一個(gè) bit 的變化，散列結(jié)果中將有一半以上的 bit 改變，這又叫做"雪崩效應(yīng)(avalanche effect)"；要實(shí)現(xiàn)使散列結(jié)果中出現(xiàn) 1bit 的變化，則輸入中至少有一半以上的 bit 必須發(fā)生變化。其實(shí)質(zhì)是必須使輸入中每一個(gè) bit 的信息，盡量均勻的反映到輸出的每一個(gè) bit 上去；輸出中的每一個(gè) bit，都是輸入中盡可能多 bit 的信息一起作用的結(jié)果。

Damgard 和 Merkle 定義了所謂“壓縮函數(shù)(compression function)”，就是將一個(gè)固定長度輸入，變換成較短的固定長度的輸出，這對密碼學(xué)實(shí)踐上 Hash 函數(shù)的設(shè)計(jì)產(chǎn)生了很大的影響。Hash函數(shù)就是被設(shè)計(jì)為基于通過特定壓縮函數(shù)的不斷重復(fù)“壓縮”輸入的分組和前一次壓縮處理的結(jié)果的過程，直到整個(gè)消息都 被壓縮完畢，最后的輸出作為整個(gè)消息的散列值。盡管還缺乏嚴(yán)格的證明，但絕大多數(shù)業(yè)界的研究者都同意，如果壓縮函數(shù)是安全的，那么以上述形式散列任意長度 的消息也將是安全的。這就是所謂 Damgard/Merkle 結(jié)構(gòu)：

在 下圖中，任意長度的消息被分拆成符合壓縮函數(shù)輸入要求的分組，最后一個(gè)分組可能需要在末尾添上特定的填充字節(jié)，這些分組將被順序處理，除了第一個(gè)消息分組 將與散列初始化值一起作為壓縮函數(shù)的輸入外，當(dāng)前分組將和前一個(gè)分組的壓縮函數(shù)輸出一起被作為這一次壓縮的輸入，而其輸出又將被作為下一個(gè)分組壓縮函數(shù)輸 入的一部分，直到最后一個(gè)壓縮函數(shù)的輸出，將被作為整個(gè)消息散列的結(jié)果。

MD5 和 SHA1 可以說是目前應(yīng)用最廣泛的Hash算法，而它們都是以 MD4 為基礎(chǔ)設(shè)計(jì)的。

1) MD4
MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年設(shè)計(jì)的，MD 是 Message Digest 的縮寫。它適用在32位字長的處理器上用高速軟件實(shí)現(xiàn)--它是基于 32 位操作數(shù)的位操作來實(shí)現(xiàn)的。它的安全性不像RSA那樣基于數(shù)學(xué)假設(shè)，盡管 Den Boer、Bosselaers 和 Dobbertin 很快就用分析和差分成功的攻擊了它3輪變換中的 2 輪，證明了它并不像期望的那樣安全，但它的整個(gè)算法并沒有真正被破解過，Rivest 也很快進(jìn)行了改進(jìn)。

下面是一些MD4散列結(jié)果的例子：

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的改進(jìn)版本。它對輸入仍以512位分組，其輸出是4個(gè)32位字的級(jí)聯(lián)，與 MD4 相同。它較MD4所做的改進(jìn)是：

1) 加入了第四輪
2) 每一步都有唯一的加法常數(shù)；
3) 第二輪中的G函數(shù)從((X ∧ Y) ∨ (X ∧ Z) ∨ (Y ∧ Z)) 變?yōu)?((X ∧ Z) ∨ (Y ∧ ～Z))以減小其對稱性；
4) 每一步都加入了前一步的結(jié)果，以加快"雪崩效應(yīng)"；
5) 改變了第2輪和第3輪中訪問輸入子分組的順序，減小了形式的相似程度；
6) 近似優(yōu)化了每輪的循環(huán)左移位移量，以期加快"雪崩效應(yīng)"，各輪的循環(huán)左移都不同。
盡管MD5比MD4來得復(fù)雜，并且速度較之要慢一點(diǎn)，但更安全，在抗分析和抗差分方面表現(xiàn)更好。

消 息首先被拆成若干個(gè)512位的分組，其中最后512位一個(gè)分組是“消息尾+填充字節(jié)(100…0)+64 位消息長度”，以確保對于不同長度的消息，該分組不相同。64位消息長度的限制導(dǎo)致了MD5安全的輸入長度必須小于264bit，因?yàn)榇笥?4位的長度信 息將被忽略。而4個(gè)32位寄存器字初始化為A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210， 它們將始終參與運(yùn)算并形成最終的散列結(jié)果。

接著各個(gè)512位消息分組以16個(gè)32位字的形式進(jìn)入算法的主循環(huán)，512位消息分組的個(gè)數(shù)據(jù)決定了循環(huán)的次數(shù)。主循環(huán)有4輪，每輪分別用到了非線性函數(shù)

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輪變換是對進(jìn)入主循環(huán)的512位消息分組的16個(gè)32位字分別進(jìn)行如下操作：將A、B、C、D的副本a、b、c、d中的3個(gè)經(jīng)F、G、H、I運(yùn)算后的結(jié) 果與第4個(gè)相加，再加上32位字和一個(gè)32位字的加法常數(shù)，并將所得之值循環(huán)左移若干位，最后將所得結(jié)果加上a、b、c、d之一，并回送至ABCD，由此 完成一次循環(huán)。

所用的加法常數(shù)由這樣一張表T[i]來定義，其中i為1…64，T[i]是i的正弦絕對值之4294967296次方的整數(shù)部分，這樣做是為了通過正弦函數(shù)和冪函數(shù)來進(jìn)一步消除變換中的線性性。

當(dāng)所有512位分組都運(yùn)算完畢后，ABCD的級(jí)聯(lián)將被輸出為MD5散列的結(jié)果。下面是一些MD5散列結(jié)果的例子：

MD5 ("") = d41d8cd98f00b204e9800998ecf8427e
MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661
MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72
MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0
MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = d174ab98d277d9f5a5611c2c9f419d9f
MD5 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = 57edf4a22be3c955ac49da2e2107b67a
參考相應(yīng)RFC文檔可以得到MD4、MD5算法的詳細(xì)描述和算法的C源代碼。

3) SHA1 及其他
SHA1 是由NIST NSA設(shè)計(jì)為同DSA一起使用的，訪問http://www.itl.nist.gov/fipspubs可以得到它的詳細(xì)規(guī)范 --[/url]"FIPS PUB 180-1 SECURE HASH STANDARD"。它對長度小于264的輸入，產(chǎn)生長度為160bit的散列值，因此抗窮舉(brute-force)性更好。SHA-1 設(shè)計(jì)時(shí)基于和MD4相同原理,并且模仿了該算法。因?yàn)樗鼘a(chǎn)生160bit的散列值，因此它有5個(gè)參與運(yùn)算的32位寄存器字，消息分組和填充方式與MD5 相同，主循環(huán)也同樣是4輪，但每輪進(jìn)行20次操作，非線性運(yùn)算、移位和加法運(yùn)算也與MD5類似，但非線性函數(shù)、加法常數(shù)和循環(huán)左移操作的設(shè)計(jì)有一些區(qū)別， 可以參考上面提到的規(guī)范來了解這些細(xì)節(jié)。下面是一些SHA1散列結(jié)果的例子：

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算法，另外還有經(jīng)IDEA改進(jìn)的Davies- Meyer算法，它們兩者目前都被認(rèn)為是安全的算法。另一類是基于模運(yùn)算/離散對數(shù)的，也就是基于公開密鑰算法的，但因?yàn)槠溥\(yùn)算開銷太大，而缺乏很好的應(yīng) 用前景。

沒有通過分析和差分攻擊考驗(yàn)的算法，大多都已經(jīng)夭折在實(shí)驗(yàn)室里了，因此，如果目前流行的Hash算法能 完全符合密碼學(xué)意義上的單向性和抗沖突性，就保證了只有窮舉，才是破壞Hash運(yùn)算安全特性的唯一方法。為了對抗弱抗沖突性，我們可能要窮舉個(gè)數(shù)和散列值 空間長度一樣大的輸入，即嘗試2^128或2^160個(gè)不同的輸入，目前一臺(tái)高檔個(gè)人電腦可能需要10^25年才能完成這一艱巨的工作，即使是最高端的并 行系統(tǒng)，這也不是在幾千年里的干得完的事。而因?yàn)?生日攻擊"有效的降低了需要窮舉的空間，將其降低為大約1.2*2^64或1.2*2^80，所以，強(qiáng) 抗沖突性是決定Hash算法安全性的關(guān)鍵。

在NIST新的 Advanced Encryption Standard (AES)中，使用了長度為128、192、256bit 的密鑰，因此相應(yīng)的設(shè)計(jì)了 SHA256、SHA384、SHA512，它們將提供更好的安全性。

Hash算法在信息安全方面的應(yīng)用主要體現(xiàn)在以下的3個(gè)方面：

1) 文件校驗(yàn)
我們比較熟悉的校驗(yàn)算法有奇偶校驗(yàn)和CRC校驗(yàn)，這2種校驗(yàn)并沒有抗數(shù)據(jù)篡改的能力，它們一定程度上能檢測并糾正數(shù)據(jù)傳輸中的信道誤碼，但卻不能防止對數(shù)據(jù)的惡意破壞。

MD5 Hash算法的"數(shù)字指紋"特性，使它成為目前應(yīng)用最廣泛的一種文件完整性校驗(yàn)和(Checksum)算法，不少Unix系統(tǒng)有提供計(jì)算md5 checksum的命令。它常被用在下面的2種情況下：

第 一是文件傳送后的校驗(yàn)，將得到的目標(biāo)文件計(jì)算 md5 checksum，與源文件的md5 checksum 比對，由兩者 md5 checksum 的一致性，可以從統(tǒng)計(jì)上保證2個(gè)文件的每一個(gè)碼元也是完全相同的。這可以檢驗(yàn)文件傳輸過程中是否出現(xiàn)錯(cuò)誤，更重要的是可以保證文件在傳輸過程中未被惡意篡 改。一個(gè)很典型的應(yīng)用是ftp服務(wù)，用戶可以用來保證多次斷點(diǎn)續(xù)傳，特別是從鏡像站點(diǎn)下載的文件的正確性。

更 出色的解決方法是所謂的代碼簽名，文件的提供者在提供文件的同時(shí)，提供對文件Hash值用自己的代碼簽名密鑰進(jìn)行數(shù)字簽名的值，及自己的代碼簽名證書。文 件的接受者不僅能驗(yàn)證文件的完整性，還可以依據(jù)自己對證書簽發(fā)者和證書擁有者的信任程度，決定是否接受該文件。瀏覽器在下載運(yùn)行插件和java小程序時(shí)， 使用的就是這樣的模式。

第二是用作保存二進(jìn)制文件系統(tǒng)的數(shù)字指紋，以便檢 測文件系統(tǒng)是否未經(jīng)允許的被修改。不少系統(tǒng)管理/系統(tǒng)安全軟件都提供這一文件系統(tǒng)完整性評(píng)估的功能，在系統(tǒng)初始安裝完畢后，建立對文件系統(tǒng)的基礎(chǔ)校驗(yàn)和數(shù) 據(jù)庫，因?yàn)樯⒘行ｒ?yàn)和的長度很小，它們可以方便的被存放在容量很小的存儲(chǔ)介質(zhì)上。此后，可以定期或根據(jù)需要，再次計(jì)算文件系統(tǒng)的校驗(yàn)和，一旦發(fā)現(xiàn)與原來保 存的值有不匹配，說明該文件已經(jīng)被非法修改，或者是被病毒感染，或者被木馬程序替代。TripWire就提供了一個(gè)此類應(yīng)用的典型例子。

更 完美的方法是使用"MAC"。"MAC" 是一個(gè)與Hash密切相關(guān)的名詞，即信息鑒權(quán)碼(Message Authority Code)。它是與密鑰相關(guān)的Hash值，必須擁有該密鑰才能檢驗(yàn)該Hash值。文件系統(tǒng)的數(shù)字指紋也許會(huì)被保存在不可信任的介質(zhì)上，只對擁有該密鑰者提 供可鑒別性。并且在文件的數(shù)字指紋有可能需要被修改的情況下，只有密鑰的擁有者可以計(jì)算出新的散列值，而企圖破壞文件完整性者卻不能得逞。

2) 數(shù)字簽名
Hash 算法也是現(xiàn)代密碼體系中的一個(gè)重要組成部分。由于非對稱算法的運(yùn)算速度較慢，所以在數(shù)字簽名協(xié)議中，單向散列函數(shù)扮演了一個(gè)重要的角色。

在這種簽名協(xié)議中，雙方必須事先協(xié)商好雙方都支持的Hash函數(shù)和簽名算法。

簽名方先對該數(shù)據(jù)文件進(jìn)行計(jì)算其散列值，然后再對很短的散列值結(jié)果--如Md5是16個(gè)字節(jié)，SHA1是20字節(jié)，用非對稱算法進(jìn)行數(shù)字簽名操作。對方在驗(yàn)證簽名時(shí)，也是先對該數(shù)據(jù)文件進(jìn)行計(jì)算其散列值，然后再用非對稱算法驗(yàn)證數(shù)字簽名。

對 Hash 值，又稱"數(shù)字摘要"進(jìn)行數(shù)字簽名，在統(tǒng)計(jì)上可以認(rèn)為與對文件本身進(jìn)行數(shù)字簽名是等效的。而且這樣的協(xié)議還有其他的優(yōu)點(diǎn)：

首先，數(shù)據(jù)文件本身可以同它的散列值分開保存，簽名驗(yàn)證也可以脫離數(shù)據(jù)文件本身的存在而進(jìn)行。

再 者，有些情況下簽名密鑰可能與解密密鑰是同一個(gè)，也就是說，如果對一個(gè)數(shù)據(jù)文件簽名，與對其進(jìn)行非對稱的解密操作是相同的操作，這是相當(dāng)危險(xiǎn)的，惡意的破 壞者可能將一個(gè)試圖騙你將其解密的文件，充當(dāng)一個(gè)要求你簽名的文件發(fā)送給你。因此，在對任何數(shù)據(jù)文件進(jìn)行數(shù)字簽名時(shí)，只有對其Hash值進(jìn)行簽名才是安全 的。

3) 鑒權(quán)協(xié)議
如下的鑒權(quán)協(xié)議又被稱作"挑戰(zhàn)--認(rèn)證模式：在傳輸信道是可被偵聽，但不可被篡改的情況下，這是一種簡單而安全的方法。

需 要鑒權(quán)的一方，向?qū)⒈昏b權(quán)的一方發(fā)送隨機(jī)串（“挑戰(zhàn)”），被鑒權(quán)方將該隨機(jī)串和自己的鑒權(quán)口令字一起進(jìn)行 Hash 運(yùn)算后，返還鑒權(quán)方，鑒權(quán)方將收到的Hash值與在己端用該隨機(jī)串和對方的鑒權(quán)口令字進(jìn)行 Hash 運(yùn)算的結(jié)果相比較（“認(rèn)證”），如相同，則可在統(tǒng)計(jì)上認(rèn)為對方擁有該口令字，即通過鑒權(quán)。

POP3協(xié)議中就有這一應(yīng)用的典型例子：

S: +OK POP3 server ready <1896.697170952@dbc.mtview.ca.us>
C: APOP mrose c4c9334bac560ecc979e58001b3e22fb
S: +OK maildrop has 1 message (369 octets)
在 上面的一段POP3協(xié)議會(huì)話中，雙方都共享的對稱密鑰（鑒權(quán)口令字）是tanstaaf，服務(wù)器發(fā)出的挑戰(zhàn) 是<1896.697170952@dbc.mtview.ca.us>，客戶端對挑戰(zhàn)的應(yīng)答是 MD5("<1896.697170952@dbc.mtview.ca.us>tanstaaf") = c4c9334bac560ecc979e58001b3e22fb，這個(gè)正確的應(yīng)答使其通過了認(rèn)證。

散列算法長期以來一直在計(jì)算機(jī)科學(xué)中大量應(yīng)用，隨著現(xiàn)代密碼學(xué)的發(fā)展，單向散列函數(shù)已經(jīng)成為信息安全領(lǐng)域中一個(gè)重要的結(jié)構(gòu)模塊，我們有理由深入研究其設(shè)計(jì)理論和應(yīng)用方法。