Hash 是密碼學(xué)安全性的基石，它引入了單向函數(shù)（one-way function）和指紋（fingerprint）的概念。即：

對于任意輸入，都可以產(chǎn)生相同的、唯一的輸出值 輸出值中不包含輸入值的任何線索

一、保密性（confidentiality）與完整性（integrity）

簡單來說，信息的保密性確保除授權(quán)人員以外的任何人都無法讀取該消息，信息的完整性則確保除授權(quán)人員以外的任何人都無法修改該消息。很多時候一段加密的消息無法被他人讀取和理解（保密性），并不意味著該密文不會在傳播過程中被截取和惡意修改（完整性）。

信息摘要（message digest）或指紋（fingerprint）技術(shù)即用于驗證信息的完整性。

信息摘要需滿足的基本條件為：

相同的文檔永遠(yuǎn)會生成相同的摘要（能夠作為身份線索） 生成的摘要“感覺”是隨機(jī)的，即摘要中不包含原始文檔的任何信息（無法被破解）

信息摘要也被稱作指紋，即可以代表某份文檔“身份”的一小段數(shù)據(jù)，類似于人類的指紋。每個人都可以通過指紋驗證其身份，但該指紋并不包含其身體的所有信息。文檔的指紋也是如此，可以很方便快速的通過文檔內(nèi)容計算得出一小段唯一的指紋數(shù)據(jù)作為其身份證明，但是只有指紋數(shù)據(jù)就幾乎不可能得出原始文檔的內(nèi)容。

對于兩份文檔，只需要比對其信息摘要（指紋）是否一致，就可以確保其內(nèi)容是否相同，在傳播過程中是否被人惡意修改。同時該指紋信息也不會造成原始文檔本內(nèi)容的泄露。

二、MD5

MD5 是一種比較古老的哈希算法，其名字中的 MD 即代表 message digest。它可以從任意大小的文檔計算出一個唯一的 16 字節(jié)長度的摘要數(shù)據(jù)。

PS：鑒于 MD5 較悠久的歷史和不夠長的摘要長度，不推薦在安全性很敏感的場景中使用該算法。

>>> from hashlib import md5>>> md5(b’alice’).hexdigest()’6384e2b2184bcbf58eccf10ca7a6563c’>>> md5(b’bob’).hexdigest()’9f9d51bc70ef21ca5c14f307980a29d8’>>> md5(b’balice’).hexdigest()’6760742ebf884c998752b4e082b78224’>>> md5(b’cob’).hexdigest()’386685f06beecb9f35db2e22da429ec9’>>> md5(b’a’).hexdigest()’0cc175b9c0f1b6a831c399e269772661’>>> md5(b’aa’).hexdigest()’4124bc0a9335c27f086f24ba207a4912’>>> md5(b’aa’ * 100000).hexdigest()’561b1994f6baacd6e5eaf4baaa12849f’>>> md5(b’alice’).hexdigest()’6384e2b2184bcbf58eccf10ca7a6563c’

從輸出中可以看出，針對不同的輸入內(nèi)容（即便相似度很高，比如 bob 和 cob），摘要算法生成的輸出是發(fā)散的，彼此之間沒有相似性，像是隨機(jī)生成的結(jié)果。但是對于任意相同的輸入，生成的摘要數(shù)據(jù)則都是確定的、唯一的。

三、哈希算法的規(guī)則

一般我們提到哈希算法，都會關(guān)聯(lián)到密碼學(xué)、安全性等場景中，實際上我們很早就接觸了一種完全“非密碼學(xué)”的哈希場景。比如小時候跟老師學(xué)習(xí)判斷一個數(shù)是奇數(shù)還是偶數(shù)。。。從本質(zhì)上看，哈希函數(shù)的目的是將巨大（甚至無窮大）數(shù)量的事物映射到一個相對較小的數(shù)據(jù)集中。比如 MD5，不管輸入的文檔有多大，最終都會生成一個固定長度（16 字節(jié)）的十六進(jìn)制數(shù)字作為指紋。這就意味著 MD5 的輸入集合，實際上是大于其輸出集合的。即只要輸入文檔的集合足夠大（很大很大），就有可能出現(xiàn)重復(fù)的指紋信息。

這和判斷數(shù)字奇偶是相通的。不管某個數(shù)字有多大多奇特，我們永遠(yuǎn)可以將它“壓縮”成奇數(shù)或偶數(shù)，用 1 bit 的 1 或 0 表示就可以。但是只說明某個未知數(shù)字是奇數(shù)（或偶數(shù)），我們就無法猜出該數(shù)字的準(zhǔn)確值。

上面的邏輯驗證了哈希函數(shù)共有的 3 個特性：

consistency（一致性）：相同的輸入只會生成相同的輸出信息 compression（壓縮）：可以將體量很大的輸入壓縮成一個固定大小的輸出 lossiness（有損的）：只通過檢查輸出無法反向計算出輸入值

但是對于一個滿足密碼學(xué)安全的哈希函數(shù)而言，除以上三點(diǎn)以外還需要具有如下屬性：

Preimage resistance Second-preimage resistance Collision resistance

Preimage Resistance

哈希函數(shù)的 preimage 是指能夠生成同一個特定指紋的所有輸入的合集。即對于某個哈希函數(shù) H 與摘要 k，所有能夠生成 k 的輸入值 x （滿足 H(x) = k）共同組成了 H 與 k 的 preimage。

preimage resistance 的意義即為，在僅僅只是知曉某個摘要的前提下，通過有限的計算無法獲取其 preimage 中的任何一個元素。即只通過結(jié)果無法知曉輸入。摘要中不包含原始文檔的任何信息（lossiness），無法通過逆向運(yùn)算的方式由摘要反推出原始輸入。只能隨機(jī)地嘗試任意輸入，以期碰巧得到同樣的摘要信息（暴力破解）。

因此前面提到的奇偶函數(shù)就不能作為一個安全的哈希函數(shù)使用。假設(shè)使用奇偶作為哈希函數(shù)（奇數(shù)輸出 1，偶數(shù)輸出 0），則對于摘要 1，總可以很輕易的在 preimage（此處是全體奇數(shù)）中找到任意多個摘要同為 1 的元素。這意味著原始輸入可以輕易被修改而不影響指紋數(shù)據(jù)，則該指紋作為信息完整性的驗證條件就失去了意義。

但是對于較安全的哈希算法如 MD5，由 MD5(x) = ca8a0fb205782051bd49f02eae17c9ee 就無法在有限的計算內(nèi)找到確定的 x 的值。MD5 生成 16 字節(jié)（16 * 8 = 128bit）長度的摘要，其中可以包含 2^128 種不同的數(shù)字組合。因此使用暴力破解的話，最多需要嘗試 2^128 = 340282366920938463463374607431768211456 次！假設(shè)每秒鐘可以嘗試一百萬條輸入，仍需要 10^26 年完成所有驗證操作！

Second-Preimage Resistance 與 Collision Resistance

second-primage resistance 是指即便知曉某個原始文檔以及由該文檔生成的摘要數(shù)據(jù)，仍很難計算可以出生成同樣摘要的另一個不同的文檔。即在已知 MD5(alice) = 384e2b2184bcbf58eccf10ca7a6563c 的情況下，仍無法找出除 alice 以外的另一個輸入生成同樣的摘要。為了尋求可以替換掉 alice 的另一個值，同時不影響摘要認(rèn)證，達(dá)到混淆的目的，最終仍需使用暴力破解的方式。

collision resistance 是指很難找出任意兩個生成相同摘要（相同而非特定）的輸入值。可以參考“生日問題”，即在一個班級中，存在兩個生日為同一天的學(xué)生的概率遠(yuǎn)比存在一個生日為特定日期的學(xué)生的概率大得多。

collision resistance 的意義在于，無法故意找出兩套符合同一指紋的輸入以達(dá)到混淆的目的。比如 MD5 算法：

>>> from hashlib import md5>>> md5(’bob’).hexdigest()’9f9d51bc70ef21ca5c14f307980a29d8’>>> md5(’cob’).hexdigest()’386685f06beecb9f35db2e22da429ec9’

對于很相似的輸入 bob 和 cob，其指紋信息的差異卻非常大，沒有任何可供預(yù)測的規(guī)律。這得益于一種稱為 avalanche property 的特性：輸入的微小變化總可以在輸出中產(chǎn)生巨大的無法預(yù)測的差異。

由前面提到的生日問題可知，找出兩個生成相同指紋的元素遠(yuǎn)比找出某個可以生成特定指紋的元素要容易的多。以 MD5 算法的暴力破解為例，后者往往需要做 2^128 次嘗試，而前者只需要 2^64 次嘗試。現(xiàn)實中 MD5 的 collision resistance 遠(yuǎn)非想象中那么優(yōu)異，甚至存在一種非暴力破解的方式 能夠在一小時以內(nèi)攻破 MD5 的 collision resistance。所以盡量不要使用 MD5 這個已經(jīng)不再維護(hù)超過 10 年、安全漏洞存在 20 年的古老算法。

參考資料

Practical Cryptography in Python: Learning Correct Cryptography by Example

以上就是python密碼學(xué)示例——理解哈希（Hash）算法的詳細(xì)內(nèi)容，更多關(guān)于python 哈希（Hash）算法的資料請關(guān)注好吧啦網(wǎng)其它相關(guān)文章！