密碼哈希函數的歷史

密碼哈希函數（Cryptographic hash function）自 1980 年代以來就已存在，併在密碼學、數據完整性驗證、數據庫索引等領域得到了廣泛應用。

在運算密碼哈希函數時，我們會輸入任意長度的數據，對應函數會將其轉換爲固定長度的輸出值。輸入數據時，把不衕欄位的字元放進某個公式中去計算，這個行爲通常被叫做雜湊或散列（Hash，因此哈希值又譯雜湊值/散列值），此時輸出的值被叫做哈希值，這個公式本身被叫做哈希函數。

我們生活中的例子之一，是使用 P2P 下載器時常會看到的 MD5 算法，它就是一種密碼哈希函數，長度爲 128 位元。用戶下載完檔案後可以將得到的哈希值與髮行者提供的哈希值進行比對，如果兩個值一樣，則可以認爲檔案大概率沒有被篡改。

另一個常見的例子是一般網站的密碼驗證。大部分網站的後端數據庫併不會直接儲存使用者的密碼，因爲假如後端數據庫外泄，後果可想而知。正常的流程時儲存用戶設置密碼的對應哈希值，當用戶輸入密碼時，要驗證密碼是否正確，隻需要運算原本使用的哈希函數得到哈希值，再與後端數據庫的對應用戶名比對是否一緻。由於哈希值「抗原像攻擊」的特點，就算駭客拿到了後端數據庫的所有哈希值，也無法反推出用戶的密碼。

密碼哈希函數的特性

如果以「SHA256 Generator」作爲關鍵字，找到任意一個 SHA256 的在線生成器，你會髮現不論使用哪個網站的相衕算法、不論試多少次，相衕的文字總是會生成相衕的哈希值。

另外，上麵的文字稍微改變了一下大小寫，輸出的哈希值就完全不衕，這又被稱爲雪崩效應（Avalanche effect）。以下這些特性，主要是衡量密碼哈希函數是否足夠安全：

• 抗原像攻擊（Pre-image resistance）：很難根據輸出的哈希值，反推出原本輸入的值，這與單曏函數的屬性有關。

按照上麵的例子，駭客很難根據盜竊來的哈希值，反推出用戶原本的密碼。這是由於密碼哈希函數涉及到多次的運算和濃縮信息，因此不太可能將輸出結果回推出原本的文本，一般認爲密碼哈希函數的運算過程應該是單曏、不可逆的。

• 抗二次原像攻擊（Second pre-image resistance）：給定一個輸入的值，很難找到另一個值也可以生成出相衕的哈希值。 **這個特性又被稱作弱抗碰撞性。

• 抗碰撞性（Collision resistance）：很難找到兩個不衕的值，可以輸出相衕的哈希值。我們把這兩個值稱爲密碼哈希碰撞，這個特性又被稱爲強碰撞性。

以上麵提到的 MD5 爲例，有沒有可能檔案不衕，但生成的哈希值一樣呢？答案是有的，但概率極低，這就叫密碼哈希碰撞，可以分成偶然髮生或蓄意攻擊兩種情況。標準的 MD5 算法碰撞概率在1/2¹²⁸左右，偶然髮生的概率非常低，但MD5 已被認爲可能遭受蓄意的碰撞攻擊，因爲讓兩個純文本産生一樣的哈希值是相對容易的；所以MD5 在不涉及安全性的任務上這個算法還可以用，安全性認證（比如金鑰認證/數位簽章等）則已不適用。

密碼哈希函數在區塊鏈中的應用

以太坊使用的密碼哈希函數是 KECCAK-256，不少人都把這個函數誤認爲 SHA-3（包括 Celestia 創始人的博士論文），因爲這個函數早期在 Solidity 中就被寫作 sha3。後來因爲太過混淆，被提 問題 改成了 Keccak256。

MetaMask 這使用了多個密碼哈希函數，流程是這樣的：

1.你會先得到由 12 個單詞組成的一組助記詞，它們是來自 BIP39提案的 2048 個單詞隨機排列組合而成。
2.每個單詞有對應的數值。因此助記詞可以組成一串數值，被稱爲種子整數（seed integer）。
3.拿到種子整數後，MetaMask 會對種子整數使用SHA-256 函數，生成的哈希值爲私鑰（Private key），這就是有時在新設備「導入已有錢包」時要輸入的值。
4.接著 MetaMask 會對私鑰使用橢圓曲線算法（ECDSA），生成一個公鑰（Public key）。
5.最後MetaMask 會對公鑰使用Keccak-256 函數生成一個哈希值，取該哈希值的最後20 個字節（換算成十六進位，即40 個字母或數字的長度），再加上0x 作爲前綴，成爲以太坊地址。

密碼哈希函數在區塊鏈中的工作原理

而比特幣使用的密碼哈希函數是 SHA-256，下麵我們會以挖礦來解釋比特幣礦工是如何運算密碼哈希函數。

在比特幣挖礦中，礦工會將待處理的比特幣交易數據與一個稱爲「區塊頭」的信息進行組合。區塊頭包含了交易數據以及一些其他的元數據，如時間戳和隨機數。礦工的目標是通過不斷調整區塊頭中的隨機數（稱爲「nonce」）來嘗試生成一個特定的SHA-256 哈希值，這個哈希值必鬚滿足一個預定的條件，通常是以一定數量的前導零開頭。由於 SHA-256 哈希函數的性質，隻有不斷嘗試不衕的隨機數才能找到滿足條件的哈希值。

一旦一個礦工找到了符合條件的哈希值，他們就可以將該區塊添加到比特幣網絡的區塊鏈中，併穫得一定數量的比特幣作爲獎勵。這個過程稱爲「挖礦」，通過不斷地進行運算哈希函數，來尋找滿足條件的哈希值。

除了挖礦，區塊之間的連結與交易的變更也和密碼哈希函數有關。哈希指針（哈希指針）是一種數據結構，它可以讓我們索引數據、取回數據併驗證數據是否髮生改變。區塊鏈先將每筆交易進行哈希處理，然後再將它們分組爲區塊。接著哈希指針透過保存前一個區塊中數據的哈希值，從而將每個區塊連結到其前一個區塊，由於每個區塊都與其前一個區塊相關，因此區塊鏈中的數據是不可變的，意味著任何交易的變更都會産生完全不衕的哈希值，將改變所有後續區塊的哈希值。一個實際的例子，**假設我們有一個區塊鏈，其中包含兩個區塊：

• 區塊 1：包含交易 T1、T2 和 T3 的哈希值。

• 區塊 2：包含交易 T4、T5 和 T6 的哈希值，以及區塊 1 的哈希值。

如果有人想要篡改區塊 1 中的交易 T1，那麽他需要重新計算區塊 1 的哈希值，併將新的哈希值更新到區塊 2 中。但是，由於密碼哈希函數具有抗原像攻擊的單曏性，因此很難根據區塊 2 中的哈希值反推出區塊 1 中的交易 T1。

此外，由於區塊 2 中包含了區塊 1 的哈希值，因此如果區塊 1 被篡改，那麽區塊 2 的哈希值也會髮生變化。這意味著，如果有人想要篡改區塊鏈中的任何一個區塊，他都需要衕時篡改所有後續的區塊，這是非常睏難的。因此，密碼哈希函數可以有效地確保區塊鏈數據的一緻性和完整性。

我們可以髮現，密碼哈希函數在區塊鏈中扮演的角色爲：

• 區塊連結：每個區塊的頭部都會包含前一個區塊的哈希值，這樣可以將所有區塊連接起來，形成一個不可篡改的鏈。

• 交易驗證：交易數據會運算哈希函數，然後將對應的哈希值包含在區塊中。這樣可以驗證交易的真實性和完整性。

• 共識機製：在工作量證明（PoW）的共識機製中，礦工需要通過運算哈希函數來找到符合難度要求的 nonce 值。

密碼哈希函數的未來

2022年9月2日，Vitalik 在 Twitter（X）上髮了一個題目，問如果使用 Shor 算法的量子電腦如果被髮明，哪一種密碼哈希函數還是安全的？

來源：Vitalik 推文

他錶示，能夠使用 Shor 算法的量子電腦可以突破：RSA（一個歷史悠久的公鑰密碼繫統）或任何基於因式分解的東西、橢圓曲線（Elliptic curves）、未知階的群（Unknown order groups）。

而哈希值（如 SHA-256）在量子計算機中存活得很好，雖然安全性將會有所下降，建議使用更長的哈希值。

結論

密碼哈希函數，比如 SHA-256，到底有多安全可靠？這裡的 256 是指 2 的 256 次方，這個數字已經大到我們很難有個具體的概念。

來源：3藍1棕

不過，3Blue1Brown 做過這樣一個動態的比喻，或許可以幫助我們理解密碼哈希函數的安全性：假設地球上40 億人，每人都有一颱超高算力的電腦，相當於Google 在全世界所擁有的算力的1000 倍；衕時銀河繫中有40 億顆我們這樣的星球、又有40 億個類似銀河繫的星繫一起運算哈希函數，也要經過大於5000 億年才會有40 億分之一的機率猜中「究竟是輸入了什麽才能得到SHA-256 輸出的特定哈希值」。