TokenPocket錢包下載|五分鐘了解哈希函數的特性、分類與應用
哈希函數具有單向性和抗碰撞性，被廣泛應用于區塊鏈、口令保護及軟件保護。
原文標題：《【圖學院】這里有哈希函數「家族」的秘密 ......》
撰文：PlatON
哈希函數是現代密碼體系中的一個重要組成部分，被普遍應用在社會生產生活當中。平時大家比較感興趣的數字貨幣，就使用了哈希函數。
從理論角度來看，哈希函數是以任意長度的數據為輸入，輸出相應固定長度的值（比如，32byte）。這個值為哈希值，又稱摘要、散列、雜湊、指紋。這可能看起來很難理解，其實就是一種數學函數，輸入的長度可以是任意的，但輸出的長度是固定的。
密碼學的很多概念是從現實世界的概念遷徙而來，比如哈希是模擬人類的指紋。因為人類的指紋始終不變，不可能跟隨人的胖瘦而更改，也不可能同時代表兩個人。
在網絡安全協議中，哈希函數可以用來處理電子簽名，將冗長的簽名文件壓縮為一段獨特的數字信息，像指紋鑒別身份一樣保證原來數字簽名文件的合法性和安全性。
哈希函數的特性哈希函數具有兩大基本屬性（敲黑板，這是重點）：單向性和抗碰撞性。單向性決定了哈希函數的正向計算效率高，反向計算難度非常大，幾乎不可能；而抗碰撞性決定了無法找到兩個不同的輸入，使得其輸出（即哈希值）是一致的。
接下來，讓我們依次進行闡述。
單向性哈希函數的單向性意味著，給定一個哈希值，我們無法（很難）逆向計算出其原像輸入。即給定一個哈希值 y，我們無法計算出 x，使得 y=H （x）。簡單來說，是無法逆向推理。
對于無法逆向推理，你可能會產生疑問：難道就不能通過不斷試錯的方法，碰碰運氣，得到最終的 x 值嗎？也就是說，嘗試不同的 x 值，總有一個經過哈希后能得到正確的 y 值吧？這只能說，實踐出真知。
以哈希函數 SHAI （輸出為 160-bit）為例，假設計算機具備的算力為 73TH/s （即每秒可執行 73×1012 次哈希），Bitman 算力最高礦機 AntminerS17+），那么其一年可執行的哈希運算為 2×1022 次，要搜索出每一個原像大概需要 282 年，超過 100 萬億億年。
以下是計算過程：
73TH/s=73×1012/s≈2×1022/year≈278/year
2160÷278=282year>1024year
所以，反向計算出哈希函數原像的難度太大，幾乎不可能。
抗碰撞性碰撞指的是在輸入區間 D 中的任意兩個不同輸入 x、y，兩者的哈希值是相同的。那么哈希函數的抗碰撞性意味著，找出任意兩個不同的輸入值 x、y，使得 H （x）= H （y）是困難的。（這里稱為「困難」的原因，是消息空間是無窮的，而哈希值空間是有限的，因此一定會存在碰撞，只是對尋找碰撞的算力需要有難度上的約束）。
以哈希函數 SHAI （輸出為 160-bit）為例：其輸出空間為（0，2160），假設有一萬億個哈希值，發生碰撞的概率僅為 3×10-25。被碰撞的概率太低，幾乎不可能。
因此，哈希函數的碰撞雖很難，但產生碰撞的幾率并不為零。比如，我們將十只鴿子放到五個箱子里面，一定會有兩只鴿子是在同一個箱子里面。
再比如下圖的生日攻擊問題，考慮所有人的生日都是獨立均勻隨機分布在 365 天內，因為第二個人不能跟第一個人有相同的生日 (概率是 364/365)，第三個人不能跟前兩個人生日相同 (概率為 363/365)，依此類推，用階乘方法計算。最終得知，當 n=23 時，概率趨于 50%，而人的出生率并不是均勻隨機的，因此 23 人實際概率應該大于 50%。
因此，哈希函數的抗碰撞性依據其內部構造而定，不同的哈希函數被攻擊的幾率不同。
哈希函數算法「家族」從哈希（Hash）函數這一概念誕生至今，已經提出了幾十種哈希算法，每類算法對應不同的參數又會形成不同的算法實現。眾多的哈希函數如同一個江湖，其中 MD 家族和 SHA 家族是「哈希江湖」中最具聲望的兩大家族。
國際： MD4、MD5、SHA-1、SHA-256、SHA-3。（MD 系列、SHA-1 已被破解）
國內：國產自主研發的商用密碼哈希算法，即 SM3。
MD5 由美國密碼學家羅納德·李維斯特（Ronald Linn Rivest）設計，經 MD2、MD3 和 MD4 發展而來，輸出的是 128 位固定長度的字符串。主要用于增強算法復雜度和不可逆性，因其普遍、穩定、快速的特點，仍廣泛應用于普通數據的加密保護領域。
SHA-1 由美國國家安全局（NSA）提出，輸出的是 160 位固定長度的字符串，在 MD5 的基礎上提高輸出的長度，單向操作的數量以及單向操作的復雜性，但未做任何根本改進來使其能夠抵御更強大的機器。
SHA-3 是由美國國家標準與技術研究所（NIST）發布的，采用了不同于 MD 算法 (如 MD5) 結構的海綿結構，是目前較為安全的哈希函數。
國內的哈希算法有國產自主研發的商用密碼算法 SM3，由國家密碼管理局于 2010 年發布，主要用于數字簽名及驗證、消息認證碼生成及驗證、隨機數生成等，其算法是公開的。據國家密碼管理局表示，其安全性及效率與 SHA-256 相當。
每個算法都是有生命周期，不可能永遠被使用。比如曾在商業市場廣泛運用的 MD5 算法，被中國科學院院士、清華大學王小云教授攻破，造成密碼學界的轟動。
王小云教授給出了首個在 MD5 算法上的碰撞例子，并且該碰撞案例是通過 IBM P690 計算機約 1 小時左右即可尋找到，從而證實了 MD5 算法無法防止碰撞，不適用于安全性認證。
王小云教授對 MD5 防碰撞性的攻擊表現在：
能夠在較短時間內計算找到消息 M1 和 M2，使得 M2 產生的哈希值與 M1 產生的哈希值相同。如此，MD5 的抗碰撞性就已不滿足，使得 MD5 不再是安全的哈希算法。
因此，某個單一的哈希算法可能在十年甚至三十年內保證是安全的，能被大家放心地使用。一旦被攻破，大家只能開始換用另一種算法。當然，這個過程是非常漫長的。
哈希函數的應用哈希函數具有單向性和抗碰撞性，即使僅僅改變輸入信息的一個字符也會產生一個完全不同的哈希值，該特性幫助我們防止數據被篡改。
我們可以將原始數據和經過哈希算法得到的數據一塊發送給對方，對方收到數據之后，對數據使用相同的哈希算法進行計算，如果得到的哈希值和對方發過來的相同，那么就說明數據沒有經過篡改。
哈希函數的應用非常廣泛，例如以下幾種：
口令保護：在現代 web 應用中，賬戶系統的口令通過哈希函數處理后，再存儲于服務器上，使得口令只對用戶自己可知；軟件保護：對外發布軟件時，同時使用哈希函數計算出軟件的哈希值，與軟件一起發布，防止用戶下載假冒軟件；區塊鏈：在區塊鏈中，賬戶與交易都涉及哈希函數的使用。在區塊鏈中，哈希函數的主要價值是防篡改。每一個區塊都存有前一個區塊的哈希值，前一個區塊叫做當前區塊的父區塊。當修改當前區塊的任意值，都會對父區塊產生影響。
前面我們提到，每個算法都是有生命周期，不可能永遠被使用。如果 SHA-256 算法被攻破，是不是意味著區塊鏈就掛了？是的，除非全網升級新的哈希算法。SHA-256 算法可能被使用 30 多年或者更長時間，這都很難被確定。
值得一提的是，比特幣使用 SHA-256 來轉換數據的方式非常有趣，它將算法在協議中連續執行了兩次。注意，這并不是為了抵御生日攻擊。顯然如果 Hash(x) = Hash(y)，那么也有 Hash(Hash(x)) = Hash(Hash(y))，為了緩解長度擴展攻擊。
從本質上說，這種攻擊需要惡意攻擊者知道哈希輸入值的長度，在這個已知的長度上再加上一個秘密的字符串，就可以發動哈希函數內部的一部分，從而擾亂哈希函數。由于 SHA-256 是 SHA-2 算法家族的成員，它有這一類的短板，而比特幣通過將哈希函數連續運行兩次來緩解這個缺陷。
總的來說，哈希函數在生活當中無處不在，包括我們平常在網絡上輸入的口令，背后都是哈希函數在起作用。不僅如此，它在區塊鏈中的應用和價值也是顯而易見的，通過提高其內部操作的復雜性或輸出長度，使得被運用的哈希函數在一定時間內足夠安全。
如同哈希函數的發展史，當有舊的算法被攻破，就有新的算法被發明。我們一直在盡全力探尋一個計算更高效的未來，不斷挑選最好的工具，經得起時間的考驗！
來源鏈接：mp.weixin.qq.com
標簽: