區塊鏈兄弟社區，區塊鏈技術專業問答先行者，中國區塊鏈技術愛好者聚集地
華章圖書：《鏈接未來：迎接區塊鏈與數字資產的新時代》《區塊鏈開發指南》
本文約9000字+，閱讀（觀看）需要52分鐘
聊到區塊鏈的時候也少不了會聽到“哈希”、“哈希函數”、“哈希算法”，是不是聽得一頭霧水？別急，這一講我們來講講什麼是哈希算法。
哈希是一種加密算法
哈希函數（Hash Function），也稱為散列函數或雜湊函數。哈希函數是一個公開函數，可以將任意長度的消息M映射成為一個長度較短且長度固定的值H（M），稱H（M）為哈希值、散列值（Hash Value）、雜湊值或者消息摘要（Message Digest）。它是一種單向密碼體制，即一個從明文到密文的不可逆映射，只有加密過程，沒有解密過程。
它的函數表達式為：h=H（m）
無論輸入是什麼數字格式、文件有多大，輸出都是固定長度的比特串。以比特幣使用的Sh256算法為例，無論輸入是什麼數據文件，輸出就是256bit。
每個bit就是一位0或者1，256bit就是256個0或者1二進制數字串，用16進制數字表示的話，就是多少位呢？
16等於2的4次方，所以每一位16進制數字可以代表4位bit。那麼，256位bit用16進制數字表示，當然是256除以4等於64位。
於是你通常看到的哈希值，就是這樣的了：
00740f40257a13bf03b40f54a9fe398c79a664bb21cfa2870ab07888b21eeba8。
這是從btc.com上隨便拷貝的一個哈希值，不放心的話你可以數一下，是不是64位~
Hash函數的特點
Hash函數具有如下特點。
- 易壓縮：對於任意大小的輸入x，Hash值的長度很小，在實際應用中，函數H產生的Hash值其長度是固定的。
- 易計算：對於任意給定的消息，計算其Hash值比較容易。
- 單向性：對於給定的Hash值，要找到使得在計算上是不可行的，即求Hash的逆很困難。在給定某個哈希函數H和哈希值H（M）的情況下，得出M在計算上是不可行的。即從哈希輸出無法倒推輸入的原始數值。這是哈希函數安全性的基礎。
- 抗碰撞性：理想的Hash函數是無碰撞的，但在實際算法的設計中很難做到這一點。
- 有兩種抗碰撞性：一種是弱抗碰撞性，即對於給定的消息，要發現另一個消息，滿足在計算上是不可行的；另一種是強抗碰撞性，即對於任意一對不同的消息，使得在計算上也是不可行的。
- 高靈敏性：這是從比特位角度出發的，指的是1比特位的輸入變化會造成1/2的比特位發生變化。消息M的任何改變都會導致哈希值H（M）發生改變。即如果輸入有微小不同，哈希運算後的輸出一定不同。
哈希算法
把網址A，轉換成數字1。網址B，轉換成數字2。
一個網址X，轉換成數字N，根據數字N作為下標，就可以快速地查找出網址X的信息。這個轉換的過程就是哈希算法。
比如這裡有一萬首歌，給你一首新的歌X，要求你確認這首歌是否在那一萬首歌之內。
無疑，將一萬首歌一個一個比對非常慢。但如果存在一種方式，能將一萬首歌的每首數據濃縮到一個數字（稱為哈希碼）中，於是得到一萬個數字，那麼用同樣的算法計算新的歌X的編碼，看看歌X的編碼是否在之前那一萬個數字中，就能知道歌X是否在那一萬首歌中。
作為例子，如果要你組織那一萬首歌，一個簡單的哈希算法就是讓歌曲所佔硬盤的字節數作為哈希碼。這樣的話，你可以讓一萬首歌“按照大小排序”，然後遇到一首新的歌，只要看看新的歌的字節數是否和已有的一萬首歌中的某一首的字節數相同，就知道新的歌是否在那一萬首歌之內了。
一個可靠的哈希算法，應該滿足：
- 對於給定的數據M,很容易算出哈希值X=F(M);
- 根據X很難反算出M;
- 很難找到M和N使得F(N)=F(M)
前面提到哈希函數具有抗碰撞性，碰撞性就是指有人實現找出一奇一偶使得哈希結果一致，但這在計算上是不可行的。
首先，把大空間的消息壓縮到小空間上，碰撞肯定是存在的。假設哈希值長度固定為256位，如果順序取1，2，…2^256+1， 這2^256+1個輸入值，逐一計算其哈希值，肯定能找到兩個輸入值使得其哈希值相同。但不要高興的太早，因為你得有時間把它算出來，才是你的。
根據生日悖論，如果隨機挑選其中的2^128+1輸入，則有99.8%的概率發現至少一對碰撞輸入。那麼對於哈希值長度為256位的哈希函數，平均需要完成2^128次哈希計算，才能找到碰撞對。如果計算機每秒進行10000次哈希計算，需要約10^27年才能完成2^128次哈希計算。在區塊鏈中，哈希函數的抗碰撞性用來做區塊和交易的完整性驗證，一有篡改就能被識別出來。
前面提到挖礦需要礦工通過隨機數不斷計算得到小於給定難度值的數值。難度值（difficulty）是礦工們挖礦時的重要參考指標，它決定了礦工大約需要經過多少次哈希運算才能產生一個合法的區塊。比特幣的區塊大約每10分鐘生成一個，為了讓新區塊的產生基本保持這個速率，難度值必須根據全網算力的變化進行調整。
哈希函數通過調整難度值來確保每個區塊挖出的時間都大約在10分鐘，哈希函數計算的難度值對保證區塊鏈系統的安全意義重大。正如美國的幾位計算機科學家在共同所著的書中所寫的：“哈希密碼是密碼學中的瑞士軍刀，它們在眾多各具特色的應用中找到了一席之地，為了保證安全，不同的應用會要求不同的哈希函數特點。事實已經證明，要確定一系列哈希函數以全面達成可證安全極度困難。”
工作量證明需要有一個目標值。比特幣工作量證明的目標值（target）的計算公式如下：
目標值＝最大目標值 / 難度值
其中，最大目標值為一個恆定值：
0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
目標值的大小與難度值成反比。比特幣工作量證明的達成就是礦工計算出來的區塊哈希值必須小於目標值。
我們也可以簡單理解成，比特幣工作量證明的過程，就是通過不停地變換區塊頭（即嘗試不同的隨機值）作為輸入進行SHA256哈希運算，找出一個特定格式哈希值的過程（即要求有一定數量的前導0）。而要求的前導0的個數越多，代表難度越大。
舉個栗子幫助理解
▌場景一、小星和阿呆在籃球場
小星：阿呆，你是不是口渴了，你要不要去買水喝，順便幫我買一瓶哈。
阿呆：呵呵，你的小心思我還不知道，你自己也口渴了吧，你去，我不去。
小星：哎哎，咱們不扯這些沒用的，來拋硬幣，好不好，正面你去，反面我去，公平吧，如何？
阿呆：好吧。
………
▌場景二、小星與阿呆即時聊天中
阿呆：小星，今天來我家玩，來的路上，有一家披薩店，很好吃，順便帶一點哈。
小星：哦，要不你來我家玩吧，你順便帶上披薩。
阿呆：小星，你竟然都這麼說了，看來只能拋硬幣解決了。
小星：丫的，這個怎麼拋，我怎麼知道你有沒有搞鬼。
阿呆：嗯，那到也是，要不這樣。
1
考慮對結果加密
阿呆：我心中想一個數，假設為A，然後A在乘以一個數B，得到結果C。A是我的密鑰，我把結果C告訴你。你來猜A是奇數還是偶數，猜中了，算你贏。
小星：這不行，如果你告訴我C是12，我猜A是奇數，你可以說A是4，B是3。我猜A是偶數，你可以說A是3，B是4。要不你告訴我C是多少的時候，也告訴我B是多少。
阿呆：那這不行，告訴你C和B，不等於告訴你A是多少了，還猜個屁。不行得換個方式。
2
不可逆加密
阿呆：小星，你看這樣可以不，我想一個A，經過下面的過程：
1.A+123=B
2.B^2=C
3.取C中第2~4位數，組成一個3位數D
4.D/12的結果求餘數，得到E
阿呆：我把E和上述計算方式都告訴你，你猜A是奇數還是偶數，然後我告訴你A是多少，你可以按上述的計算過程來驗證我是否有說謊。
小星：嗯，我想想，假如阿呆你想的A為5，那麼：
5+123=128
128^2=16384
D=638 E=638mod12=53
(mod表示除法的求餘數)
小星：咦，厲害了，一個A值對應一個唯一的E值，根據E還推算不出來A。你太賤了，好吧，這個算公平，誰撒謊都能被識別出來。
小星：阿呆，你出題吧 ……
這種丟掉一部分信息的加密方式稱為“單向加密”，也叫哈希算法。
常見的哈希算法
1
SHA-1算法
SHA-1的輸入是最大長度小於264位的消息，輸入消息以512位的分組為單位進行處理，輸出是160位的消息摘要。SHA-1具有實現速度高、容易實現、應用範圍廣等優點，其算法描述如下。
- 對輸入的消息進行填充：經過填充後，消息的長度模512應與448同餘。填充的方式為第一位是1，餘下各位都為0。再將消息被填充前的長度以big-endian的方式附加在上一步留下的最後64位中。該步驟是必須的，即使消息的長度已經是所希望的長度。填充的長度範圍是1到512。
- 初始化緩衝區：可以用160位來存放Hash函數的初始變量、中間摘要及最終摘要，但首先必須進行初始化，對每個32位的初始變量賦值，即：
- 進入消息處理主循環，處理消息塊：一次處理512位的消息塊，總共進行4輪處理，每輪進行20次操作，如圖所示。這4輪處理具有類似的結構，但每輪所使用的輔助函數和常數都各不相同。每輪的輸入均為當前處理的消息分組和緩衝區的當前值A、B、C、D、E，輸出仍放在緩衝區以替代舊的A、B、C、D、E的值。第四輪的輸出再與第一輪的輸入CVq相加，以產生CVq+1，其中加法是緩衝區5個字CVq中的每個字與中相應的字模232相加。
圖 單個512位消息塊的處理流程
- 輸出：所有的消息分組都被處理完之後，最後一個分組的輸出即為得到的消息摘要值。
SHA-1的步函數如圖所示，它是SHA-1最為重要的函數，也是SHA-1中最關鍵的部件。
圖 SHA-1的步函數
SHA-1每運行一次步函數，A、B、C、D的值就會依次賦值給B、C、D、E這幾個寄存器。同時，A、B、C、D、E的輸入值、常數和子消息塊在經過步函數運算後就會賦值給A。
其中，t是步數，0≤t≤79，Wt是由當前512位長的分組導出的一個32位的字，Kt是加法常量。
基本邏輯函數f的輸入是3個32位的字，輸出是一個32位的字，其函數表示如下。
對於每個輸入分組導出的消息分組wt，前16個消息字wt（0≤t≤15）即為消息輸入分組對應的16個32位字，其餘wt（0≤t≤79）可按如下公式得到：
其中，ROTLs表示左循環移位s位，如圖所示。
圖 SHA-1的80個消息字的產生過程
2
SHA-2算法
SHA-2系列Hash算法，其輸出長度可取SHA-2系列哈希算法的輸出長度可取224位、256位、384位、512位，分別對應SHA-224、SHA-256、SHA-384、SHA-512。它還包含另外兩個算法：SHA-512/224、SHA-512/256。比之前的Hash算法具有更強的安全強度和更靈活的輸出長度，其中SHA-256是常用的算法。下面將對前四種算法進行簡單描述。
SHA-256算法
SHA-256算法的輸入是最大長度小於264位的消息，輸出是256位的消息摘要，輸入消息以512位的分組為單位進行處理。算法描述如下。
（1）消息的填充
添加一個“1”和若干個“0”使其長度模512與448同餘。在消息後附加64位的長度塊，其值為填充前消息的長度。從而產生長度為512整數倍的消息分組，填充後消息的長度最多為264位。
（2）初始化鏈接變量
鏈接變量的中間結果和最終結果存儲於256位的緩衝區中，緩衝區用8個32位的寄存器A、B、C、D、E、F、G和H表示，輸出仍放在緩衝區以代替舊的A、B、C、D、E、F、G、H。首先要對鏈接變量進行初始化，初始鏈接變量存儲於8個寄存器A、B、C、D、E、F、G和H中：
初始鏈接變量是取自前8個素數（2、3、5、7、11、13、17、19）的平方根的小數部分其二進制表示的前32位。
（3）處理主循環模塊
消息塊是以512位分組為單位進行處理的，要進行64步循環操作（如圖所示）。每一輪的輸入均為當前處理的消息分組和得到的上一輪輸出的256位緩衝區A、B、C、D、E、F、G、H的值。每一步中均採用了不同的消息字和常數，下面將給出它們的獲取方法。
圖 SHA-256的壓縮函數
（4）得出最終的Hash值
所有512位的消息塊分組都處理完以後，最後一個分組處理後得到的結果即為最終輸出的256位的消息摘要。
步函數是SHA-256中最為重要的函數，也是SHA-256中最關鍵的部件。其運算過程如圖所示。
圖 SHA-256的步函數
根據T1、T2的值，對寄存器A、E進行更新。A、B、C、E、F、G的輸入值則依次賦值給B、C、D、F、G、H。
Kt的獲取方法是取前64個素數（2，3，5，7，……）立方根的小數部分，將其轉換為二進制，然後取這64個數的前64位作為Kt。其作用是提供了64位隨機串集合以消除輸入數據裡的任何規則性。
對於每個輸入分組導出的消息分組Wt，前16個消息字Wt（0≤t≤15）直接按照消息輸入分組對應的16個32位字，其他的則按照如下公式來計算得出：
圖 SHA-256的64個消息字的生成過程
SHA-512算法
SHA-512是SHA-2中安全性能較高的算法，主要由明文填充、消息擴展函數變換和隨機數變換等部分組成，初始值和中間計算結果由8個64位的移位寄存器組成。該算法允許輸入的最大長度是2128位，併產生一個512位的消息摘要，輸入消息被分成若干個1024位的塊進行處理，具體參數為：消息摘要長度為512位；消息長度小於2128位；消息塊大小為1024位；消息字大小為64位；步驟數為80步。下圖顯示了處理消息、輸出消息摘要的整個過程，該過程的具體步驟如下。
圖 SHA-512的整體結構
- 消息填充：填充一個“1”和若干個“0”，使其長度模1024與896同餘，填充位數為0-1023，填充前消息的長度以一個128位的字段附加到填充消息的後面，其值為填充前消息的長度。
- 鏈接變量初始化：鏈接變量的中間結果和最終結果都存儲於512位的緩衝區中，緩衝區用8個64位的寄存器A、B、C、D、E、F、G、H表示。初始鏈接變量也存儲於8個寄存器A、B、C、D、E、F、G、H中，其值為：
初始鏈接變量採用big-endian方式存儲，即字的最高有效字節存儲於低地址位置。初始鏈接變量取自前8個素數的平方根的小數部分其二進制表示的前64位。
- 主循環操作：以1024位的分組為單位對消息進行處理，要進行80步循環操作。每一次迭代都把512位緩衝區的值A、B、C、D、E、F、G、H作為輸入，其值取自上一次迭代壓縮的計算結果，每一步計算中均採用了不同的消息字和常數。
- 計算最終的Hash值：消息的所有N個1024位的分組都處理完畢之後，第N次迭代壓縮輸出的512位鏈接變量即為最終的Hash值。
步函數是SHA-512中最關鍵的部件，其運算過程類似SHA-256。每一步的計算方程如下所示，B、C、D、F、G、H的更新值分別是A、B、C、E、F、G的輸入狀態值，同時生成兩個臨時變量用於更新A、E寄存器。
對於80步操作中的每一步t，使用一個64位的消息字Wt，其值由當前被處理的1024位消息分組Mi導出，導出方法如圖所示。前16個消息字Wt（0≤t≤15）分別對應消息輸入分組之後的16個32位字，其他的則按照如下公式來計算得出：
圖 SHA-512的80個消息字生成的過程
其中，
式中，ROTRn（X）表示對64位的變量x循環右移n位，SHRn（X）表示對64位的變量x右移n位。
從圖可以看出，在前16步處理中，Wt的值等於消息分組中相對應的64位字，而餘下的64步操作中，其值是由前面的4個值計算得到的，4個值中的兩個要進行移位和循環移位操作。
Kt的獲取方法是取前80個素數（2，3，5，7，……）立方根的小數部分，將其轉換為二進制，然後取這80個數的前64位作為Kt，其作用是提供了64位隨機串集合以消除輸入數據裡的任何規則性。
SHA-224與SHA-384
SHA-256和SHA-512是很新的Hash函數，前者定義一個字為32位，後者則定義一個字為64位。實際上二者的結構是相同的，只是在循環運行的次數、使用常數上有所差異。SHA-224及SHA-384則是前述兩種Hash函數的截短型，它們利用不同的初始值做計算。
SHA-224的輸入消息長度跟SHA-256的也相同，也是小於264位，其分組的大小也是512位，其處理流程跟SHA-256也基本一致，但是存在如下兩個不同的地方。
- SHA-224的消息摘要取自A、B、C、D、E、F、G共7個寄存器的比特字，而SHA-256的消息摘要取自A、B、C、D、E、F、G、H共8個寄存器的32比特字。
- SHA-224的初始鏈接變量與SHA-256的初始鏈接變量不同，它採用高端格式存儲，但其初始鏈接變量的獲取方法是取前第9至16個素數（23、29、31、37、41、43、47、53）的平方根的小數部分其二進制表示的第二個32位，SHA-224的初始鏈接變量如下：
SHA-224的詳細計算步驟與SHA-256一致。
SHA-384的輸入消息長度跟SHA-512相同，也是小於2128位，而且其分組的大小也是1024位，處理流程跟SHA-512也基本一致，但是也有如下兩處不同的地方。
- SHA-384的384位的消息摘要取自A、B、C、D、E、F共6個64比特字，而SHA-512的消息摘要取自A、B、C、D、E、F、G、H共8個64比特字。
- SHA-384的初始鏈接變量與SHA-512的初始鏈接變量不同，它也採用高端格式存儲，但其初始鏈接變量的獲取方法是取前9至16個素數（23、29、31、37、41、43、47、53）的平方根的小數部分其二進制表示的前64位，SHA-384的初始鏈接變量如下：
SHA-384的詳細計算步驟與SHA-512的相同。
3
SHA-3算法
SHA-3算法整體採用Sponge結構，分為吸收和榨取兩個階段。SHA-3的核心置換f作用在5×5×64的三維矩陣上。整個f共有24輪，每輪包括5個環節θ、ρ、π、χ、τ。算法的5個環節分別作用於三維矩陣的不同維度之上。θ環節是作用在列上的線性運算；ρ環節是作用在每一道上的線性運算，將每一道上的64比特進行循環移位操作；π環節是將每道上的元素整體移到另一道上的線性運算；χ環節是作用在每一行上的非線性運算，相當於將每一行上的5比特替換為另一個5比特；τ環節是加常數環節。
目前，公開文獻對SHA-3算法的安全性分析主要是從以下幾個方面來展開的。
- 對SHA-3算法的碰撞攻擊、原像攻擊和第二原像攻擊。
- 對SHA-3算法核心置換的分析，這類分析主要針對算法置換與隨機置換的區分來展開。
- 對SHA-3算法的差分特性進行展開，主要研究的是SHA-3置換的高概率差分鏈，並構築差分區分器。
Keccak算法的立體加密思想和海綿結構，使SHA-3優於SHA-2，甚至AES。Sponge函數可建立從任意長度輸入到任意長度輸出的映射。
4
RIPEMD160算法
RIPEMD（RACE Integrity Primitives Evaluation Message Digest），即RACE原始完整性校驗消息摘要。RIPEMD使用MD4的設計原理，並針對MD4的算法缺陷進行改進，1996年首次發佈RIPEMD-128版本，它在性能上與SHA-1相類似。
RIPEMD-160是對RIPEMD-128的改進，並且是RIPEMD中最常見的版本。RIPEMD-160輸出160位的Hash值，對160位Hash函數的暴力碰撞搜索攻擊需要280次計算，其計算強度大大提高。RIPEMD-160的設計充分吸取了MD4、MD5、RIPEMD-128的一些性能，使其具有更好的抗強碰撞能力。它旨在替代128位Hash函數MD4、MD5和RIPEMD。
RIPEMD-160使用160位的緩存區來存放算法的中間結果和最終的Hash值。這個緩存區由5個32位的寄存器A、B、C、D、E構成。寄存器的初始值如下所示：
數據存儲時採用低位字節存放在低地址上的形式。
處理算法的核心是一個有10個循環的壓縮函數模塊，其中每個循環由16個處理步驟組成。在每個循環中使用不同的原始邏輯函數，算法的處理分為兩種不同的情況，在這兩種情況下，分別以相反的順序使用5個原始邏輯函數。每一個循環都以當前分組的消息字和160位的緩存值A、B、C、D、E為輸入得到新的值。每個循環使用一個額外的常數，在最後一個循環結束後，兩種情況的計算結果A、B、C、D、E和A′、B′、C′、D′、E′及鏈接變量的初始值經過一次相加運算產生最終的輸出。對所有的512位的分組處理完成之後，最終產生的160位輸出即為消息摘要。
除了128位和160位的版本之外，RIPEMD算法也存在256位和320位的版本，它們共同構成RIPEMD家族的四個成員：RIPEMD-128、RIPEMD-160、RIPEMD-256、RIPEMD-320。其中128位版本的安全性已經受到質疑，256位和320位版本減少了意外碰撞的可能性，但是相比於RIPEMD-128和RIPEMD-160，它們不具有較高水平的安全性，因為他們只是在128位和160位的基礎上，修改了初始參數和s-box來達到輸出為256位和320位的目的。
閱讀更多 區塊鏈兄弟 的文章
