【OK思享匯】區塊鏈技術裡的密碼學：雜湊函式
在OK區塊鏈工程院技術交流活動上，我們邀請了清華大學密碼學研究中心吳彥冰博士前來討論，並整理了其中一些精彩觀點，以饗讀者。
Hash函式是密碼學的基本工具，hash函式可以用在數字簽名中，通過後面的介紹我們可以知道數字簽名使用的是橢圓曲線，計算複雜度十分高，在簽名之前，我們通常都將要簽名的檔案或者資訊經過hash函式壓縮之後再進行簽名。
雜湊函式還可以用在資料完整性的檢測當中，例如說我們經常會看到網站上下載軟體時會在旁邊給出hash值，這個hash值就是用來判斷檔案是否完整，是否在下載時被別人篡改了。我們從網站上下載了一個檔案，我們怎麼判斷我們下載的檔案是完整的呢？我們可以將檔案經過hash函式之後得到的值與網站上的進行對比，看是否相同，相同則代表檔案網站，不相同則代表不網站或者被篡改。
Hash函式還可以用於可證明安全密碼體制當中，這個之後我們會講到。其次hsah函式還可以檢測傳輸中訊息是否被篡改，防止偽造電子簽名和訊息認證碼，作為安全元件設計多種密碼體制和安全通訊協議，比特幣和區塊鏈的核心技術。
Hash函式又稱雜湊函式、雜湊函式、數字指紋等，將任意長的訊息壓縮為一個固定長度的摘要。如下圖，我們可以看到hash函式可以將任意大小的檔案壓縮成n位元的一個01串，n可以是128、160、192、256、384或512。
我們可以看到hash函式的數學表示式是Y=H(M) , {0,1}*®{0,1}n，H代表一個hash函式，M代表一個輸入資訊，Y是一個輸出，可以看到，hash函式的輸入可以是任意位數的，但是輸出是定長位數的，為n。計算機中使用的hash表主要用於儲存和查詢，是源於1953年IBM的歷史性討論所得到的。
密碼學中的hash函式與計算機中使用的hash函式略有不同，密碼學中使用的hash函式具有特定的安全屬性。之後我們會具體介紹它的安全屬性。
我們之前介紹的hash函式是不帶金鑰的，直接對訊息進行壓縮。我們可以在hash函式中引入金鑰，使它變成可以進行身份驗證的MAC演算法。我們可以看到下圖的表示，是把金鑰和訊息同時作為hash函式的輸入。MAC函式具有訊息完整性檢測和通訊雙方的身份認證功能。hash函式廣泛應用於各類Internet協議，如IPsec、SSL/TLS、SSH、SNMP等，還有金融安全：銀行，電子錢幣等。
再來說一下hash函式的5大安全特性。首先，hash函式具有抗原像攻擊的安全屬性。抗原像攻擊是指給定任意Hash值Y，恢復訊息M 是困難的。抗第二原像攻擊和抗碰撞性是相似的，抗第二原像攻擊指的是對於給定的訊息M1 ，計算另一個訊息M2 使H(M1)=H(M2)是困難的。
而抗碰撞性則是指找到不同的訊息(M1, M2) 有相同的指紋，即H(M1)=H(M2)是困難的。這兩個安全屬性的不同點在於一個是給定M1，一個是M1可以自己選擇。
抗長度擴充套件攻擊指的是給定訊息M的長度和H(M)，不知道M的情況下，計算H(M||M’)是困難的。抗二次碰撞攻擊：給定一對碰撞訊息M和M’，對於任意訊息N，訊息M||N和M’||N也形成碰撞。
Hash函式主要有6種，分別是MD5，SHA-1，SHA-2，SHA-3，Whirlpool，SHA-3，SM3。MD5已經是很傳統的hash函數了，是在1992年由Rivest設計提出的，輸出長度為128位元。Rivest也是公鑰加密演算法RSA的設計者之一，是其中的R，Rivest在2002年的時候得到了圖靈獎。
我的導師王小云教授在Crypto 2004上提出一種能成功攻破MD5的演算法。SHA-1是1995年由NIST（美國國家標準與技術研究院）提出，輸出長度160位元。SHA-2是2002年由NIST提出，輸出長度256，384，512位元。Whirlpool是2000年由Rijmen等設計，輸出長度512位元。KECCAK在SHA-3標準競賽中勝出，成為SHA-3標準演算法，是2007年由Daemen等設計，輸出長度256，384，512位元。Hash函式也有由中國人自己設計實現的演算法，SM3，是在2010年由我的導師王小云院士等設計，輸出長度256位元。
其次王老師還攻破過SHA-1，SHA-2。王老師最推薦看的一本密碼學入門書籍是《碼書》。我是通過看《欺騙的藝術》說到MD5時有標註，MD5已被中國科學家王小云破解了解到王老師的，之後對王老師十分敬佩，並且成為她的研究生。
Hash可以應用在登陸認證中。使用者提供使用者名稱和密碼，伺服器在資料庫中查詢使用者名稱，獲取salt值，計算Hash(salt password)與資料庫中比對，相同則通過認證。這樣可以防止密碼直接存在資料庫中，黑客/管理員可以直接檢視到使用者密碼。加salt的目的是防止兩個使用者密碼相同在伺服器中可以直接檢視到。
Hash可以用在金鑰衍生中。我們可以看到銀行使用的U盾所產生的隨機數就是通過hash函式產生的。其次hash函式也廣泛應用於RFID、衛星通訊等密碼系統中。
hash函式也在數字簽名中有應用。如果學習完下一節的知識之後，我們就會知道，數字簽名使用的是橢圓曲線簽名，在計算上十分慢，要籤的資料量越大簽名速度就會越慢，所以一般採用的辦法是，在簽名前先將要簽名的資訊進行Hash壓縮，得到一個很短的位元串，之後再進行簽名運算。我們看下圖是一個金融安全的模型。
hash函式還在比特幣以及區塊鏈中有很好的應用。比特幣挖礦，其實就是在找一個隨機數n，使得n拼接上交易資訊的hash值前m位為零。前m位為零，代表的是挖礦的計算複雜度，假設要尋找前60位元為0的hash值，那麼他的計算複雜度就是260次運算。電子貨幣：一種代替貨幣的電子簽名，通過使用者的公鑰（數字證書）可驗證貨幣的合法性。