簡介
Hash（哈隙淳停或散列）算法褂微，是密碼學(xué)中非常重要的一類算法果善，用于將任意長度的二進制串確定性地映射到較短的（通常是固定長度的）二進制串（哈希值）上，不同的二進制輸入串很難映射到相同的輸出嫡锌，這種特性使得其又被稱為指紋（fingerprint）或摘要（digest）算法。
一個優(yōu)秀的 Hash 算法琳钉，應(yīng)該具備以下特點：
- 正向快速：在給定原文后势木，能夠在有限時間和有限資源內(nèi)計算其Hash值；
- 逆向困難： 在給定Hash值后歌懒，在有限時間和有限資源內(nèi)無法逆推出原文啦桌；
- 輸入敏感：原文輸入信息的任何輕微改變，都將造成Hash值的巨大變化及皂；
- 避免碰撞：很難找到兩段內(nèi)容不同的明文甫男，使得它們的Hash值一致（即發(fā)生碰撞）；
常見算法
目前常見的 Hash 算法包括國際上的 Message Digest（MD）系列和 Secure Hash Algorithm（SHA）系列算法验烧，以及國內(nèi)的 SM3 算法板驳。
MD 系列主要包括 MD4 和 MD5 兩個算法。MD4（RFC 1320）是 MIT 的 Ronald L. Rivest 在 1990 年設(shè)計的碍拆，其輸出為 128 位若治。MD4 已證明不夠安全。Rivest在1991年對MD4進行改進發(fā)布MD5感混。MD5 比 MD4 更加安全端幼，但過程更加復(fù)雜，計算速度要慢一點浩习。MD5 已于 2004 年被成功碰撞静暂，其安全性已不足應(yīng)用于商業(yè)場景。
SHA 算法由美國國家標(biāo)準(zhǔn)與技術(shù)院（National Institute of Standards and Technology谱秽，NIST）征集制定洽蛀。首個實現(xiàn) SHA-0 算法于 1993 年問世，1998 年即遭破解疟赊。隨后的修訂版本 SHA-1 算法在 1995 年面世郊供，它的輸出為長度 160 位的 Hash 值，安全性更好近哟。SHA-1 已于 2005 年被成功碰撞驮审，意味著無法滿足商用需求。為了提高安全性，NIST 后來制定出更安全的 SHA-224疯淫、SHA-256地来、SHA-384，和 SHA-512 算法（統(tǒng)稱為 SHA-2 算法）熙掺。新一代的 SHA-3 相關(guān)算法也正在研究中未斑。
中國密碼管理局于 2010 年 12 月 17 日發(fā)布了GM/T 0004-2012 《SM3 密碼雜湊算法》，建立了國內(nèi)商用密碼體系中的公開 Hash 算法標(biāo)準(zhǔn)币绩，已經(jīng)被廣泛應(yīng)用在數(shù)字簽名和認(rèn)證等場景中蜡秽。
應(yīng)用
數(shù)字摘要
利用Hash算法的“抗碰撞性”，計算出數(shù)據(jù)的Hash值作為數(shù)字摘要缆镣。當(dāng)原始數(shù)據(jù)被改變時芽突，可以通過計算摘要進行比對從而檢測出數(shù)據(jù)被篡改。
最常見的用例便是文件下載董瞻，有些網(wǎng)站在提供下載文件的同時寞蚌，會提供文件相應(yīng)的數(shù)字摘要，用戶在下載完成后可以在本地計算文件的摘要力细，通過比對來檢測下載的文件是否被篡改睬澡。
數(shù)字簽名
數(shù)字簽名是對數(shù)據(jù)先使用Hash算法計算其數(shù)字摘要，然后使用加密算法對數(shù)字摘要進行加密眠蚂，最后將數(shù)字簽名附到原始數(shù)據(jù)后完成數(shù)據(jù)的簽名工作煞聪。此時該數(shù)據(jù)可以在不安全的信道中傳輸，接收方可以檢驗數(shù)據(jù)的真實性逝慧。接收方檢驗的流程如下：
- 從接收的數(shù)據(jù)中分離出數(shù)據(jù)和簽名
- 使用約定好的解密算法對簽名進行解密得到數(shù)字摘要
- 使用約定好的Hash算法對數(shù)據(jù)計算數(shù)字摘要
- 如果2與3中的數(shù)字摘要一致昔脯，就意味著數(shù)據(jù)是真實有效的、未被篡改過的笛臣。
這種真實性源于下面的兩個假設(shè)：
- 加密算法未被破解
- Hash算法的抗碰撞性
在加密算法未被破解的前提下云稚，Hash算法的抗碰撞性使得在有限的時間和資源內(nèi)難以找出一份篡改后的數(shù)據(jù)使得與原始數(shù)據(jù)摘要相同。加密算法未被破解沈堡，保證了對于偽造的簽名將解密出不一致的摘要静陈。
數(shù)據(jù)保護
在一些場景下不保存數(shù)據(jù)的原始信息，而保存其Hash值來減輕數(shù)據(jù)庫泄露造成的危害诞丽。例如鲸拥，后臺數(shù)據(jù)庫保存登錄口令的Hash值，每次通過Hash值比對即可判斷輸入口令是否正確僧免，此時即便數(shù)據(jù)庫發(fā)生泄露刑赶，攻擊者也無法知曉用戶的登錄口令。
字典攻擊就是攻擊者掌握了大量常見的登錄密碼懂衩，如password撞叨，123等等金踪，通過對其計算Hash值，編成 口令-Hash 字典牵敷，然后通過Hash值來快速反查找到原始口令胡岔。
對這類攻擊的防范可以使用加鹽（Salt）的方法。保存的不是原文的直接 Hash 值劣领，而是原文再加上一段隨機字符串（即“鹽”）之后的 Hash 值姐军。Hash 結(jié)果和“鹽”分別存放在不同的地方，這樣只要不是兩者同時泄露尖淘，攻擊者很難進行破解。這種思想的高級變種包括二次驗證技術(shù)著觉。
基于內(nèi)容的編址
由于Hash算法的特性村生，可以將任意內(nèi)容映射到一個固定長度的字符串，而且不同內(nèi)容映射到相同串的概率很低饼丘。因此趁桃，這就構(gòu)成了一個很好的“內(nèi)容 -> 索引”的生成關(guān)系。
假設(shè)肄鸽，給定一個數(shù)據(jù)和存儲系統(tǒng)卫病。將這個數(shù)據(jù)放到存儲系統(tǒng)中的什么位置，可以在查詢時快速確定該內(nèi)容是否存在于存儲系統(tǒng)中典徘？通過對內(nèi)容進行Hash計算蟀苛，然后將該哈希值作為在存儲系統(tǒng)中地址，這樣就可以實現(xiàn)高效的查找逮诲。
然而在物理世界中沒有無限長的紙帶帜平，當(dāng)存儲系統(tǒng)越小，Hash值映射的范圍越小梅鹦，Hash碰撞的概率就會越大裆甩。為了提供空間利用率， Burton Howard Bloom提出使用Bloom過濾器進行Hash編址齐唆。其基本思想是：在數(shù)據(jù)上應(yīng)用多個Hash函數(shù)計算多個Hash地址嗤栓，然后將這些Hash地址拼接起來形成最終的地址。這樣箍邮，不同數(shù)據(jù)發(fā)生地址碰撞當(dāng)且僅當(dāng)所有的Hash函數(shù)都碰撞茉帅，因此降低了地址碰撞的幾率。
使用
下面的示例以SHA-256為例媒殉，輸出的均為Hash值的十六進制字符串
bash
# 計算字符串的SHA-256值
$ echo "hello world!" |shasum -a 256
ecf701f727d9e2d77c4aa49ac6fbbcc997278aca010bddeeb961c10cf54d435a -
# 計算一個文件的的SHA-256數(shù)字摘要
$ echo "hello world!" > hello.txt && shasum -a 256 hello.txt
ecf701f727d9e2d77c4aa49ac6fbbcc997278aca010bddeeb961c10cf54d435a hello.txt
Go
package main
import (
"fmt"
"crypto/sha256"
"encoding/hex"
"os"
"io"
)
func sha256_file(path string) (string, error) {
f, err := os.Open(path)
if err != nil{
return "", err
}
defer f.Close()
h := sha256.New()
if _, err = io.Copy(h, f); err != nil{
return "", err
}
byte_hash := h.Sum(nil)
hex_hash := hex.EncodeToString(byte_hash)
return hex_hash, nil
}
func main(){
s := "hello world!"
// 從 `sha256.New()` 創(chuàng)建一個新的hash對象開始
h := sha256.New()
// `Write` 需要字節(jié)輸入担敌。所以要使用 `[]byte(s)` 將字符串 `s` 轉(zhuǎn)成字節(jié)切片
// 可以調(diào)用多次 `Write` 來寫入數(shù)據(jù)
h.Write([]byte(s))
// 獲得當(dāng)前已有數(shù)據(jù)的Hash值
// `Sum` 接受一個參數(shù)可以將獲得的Hash值附到一個存在的字節(jié)切片后：通常不是必需的
byte_hash := h.Sum(nil)
// 以十六進制字符串的格式進行編碼
hex_hash := hex.EncodeToString(byte_hash)
fmt.Printf("%s %s\n", hex_hash, s)
// 計算文件的SHA256值
path := os.Args[1]
file_hash, err := sha256_file(path)
if err != nil {
fmt.Println("this file not exists")
} else {
fmt.Printf("%s %s\n", file_hash, path)
}
}
python
# -*- coding: utf-8 -*-
import hashlib
import sys
def sha256_file(path):
buf_size = 64*1024
sha256 = hashlib.sha256()
try:
with open(path, "rb") as f:
while True:
data = f.read(buf_size)
if not data:
break
sha256.update(data)
return sha256.hexdigest()
except:
return None
if __name__ == "__main__":
s = "hello world!"
# 創(chuàng)建SHA256對象
sha256 = hashlib.sha256()
# 寫入要計算摘要的數(shù)據(jù)
sha256.update(s.encode())
# 計算當(dāng)前數(shù)據(jù)的摘要
hex_hash = sha256.hexdigest()
print("{0} {1}".format(hex_hash, s))
path = sys.argv[1]
hex_hash = sha256_file(path)
if hex_hash == None:
print("this file not exists")
else:
print("{0} {1}".format(hex_hash, path))
注意
各個編程語言的哈希算法對于相同的二進制數(shù)據(jù)會計算出相同的Hash摘要，但有時會出現(xiàn)意想不到的不一致廷蓉。這有可能是因為沒有考慮編碼的原因全封。例如马昙，python中的字符串在內(nèi)存中默認(rèn)以utf-8編碼，而bash根據(jù)每個人機器的不同配置會有不同的編碼刹悴，這樣表達意思相同的“你好”行楞，在兩者中將以不一致的二進制串出現(xiàn)，從而導(dǎo)致對“你好”出現(xiàn)不同的摘要信息土匀。
$ python
> s = "你好" // s以utf-8標(biāo)準(zhǔn)對“你好”進行編碼
$ echo "你好" // 根據(jù)機器配置對“你好”進行編碼子房，不一定是utf-8
