聊到區(qū)塊鏈的時候也少不了會聽到“哈希”、“哈希函數(shù)”、“哈希算法”，是不是聽得一頭霧水？別急，這一講我們來講講什么是哈希算法。

1

哈希是一種加密算法

哈希函數(shù)（Hash Function），也稱為散列函數(shù)或雜湊函數(shù)。哈希函數(shù)是一個公開函數(shù)，可以將任意長度的消息M映射成為一個長度較短且長度固定的值H（M），稱H（M）為哈希值、散列值（Hash Value）、雜湊值或者消息摘要（Message Digest）。它是一種單向密碼體制，即一個從明文到密文的不可逆映射，只有加密過程，沒有解密過程。

它的函數(shù)表達式為：h=H（m）

無論輸入是什么數(shù)字格式、文件有多大，輸出都是固定長度的比特串。以比特幣使用的Sh256算法為例，無論輸入是什么數(shù)據(jù)文件，輸出就是256bit。

每個bit就是一位0或者1，256bit就是256個0或者1二進制數(shù)字串，用16進制數(shù)字表示的話，就是多少位呢？

16等于2的4次方，所以每一位16進制數(shù)字可以代表4位bit。那么，256位bit用16進制數(shù)字表示，當然是256除以4等于64位。

于是你通常看到的哈希值，就是這樣的了：

00740f40257a13bf03b40f54a9fe398c79a664bb21cfa2870ab07888b21eeba8。

這是從btc.com上隨便拷貝的一個哈希值，不放心的話你可以數(shù)一下，是不是64位~

2

Hash函數(shù)的特點

Hash函數(shù)具有如下特點。

易壓縮：對于任意大小的輸入x，Hash值的長度很小，在實際應(yīng)用中，函數(shù)H產(chǎn)生的Hash值其長度是固定的。

易計算：對于任意給定的消息，計算其Hash值比較容易。

單向性：對于給定的Hash值，要找到使得在計算上是不可行的，即求Hash的逆很困難。在給定某個哈希函數(shù)H和哈希值H（M）的情況下，得出M在計算上是不可行的。即從哈希輸出無法倒推輸入的原始數(shù)值。這是哈希函數(shù)安全性的基礎(chǔ)。

抗碰撞性：理想的Hash函數(shù)是無碰撞的，但在實際算法的設(shè)計中很難做到這一點。

有兩種抗碰撞性：一種是弱抗碰撞性，即對于給定的消息，要發(fā)現(xiàn)另一個消息，滿足在計算上是不可行的；另一種是強抗碰撞性，即對于任意一對不同的消息，使得在計算上也是不可行的。

高靈敏性：這是從比特位角度出發(fā)的，指的是1比特位的輸入變化會造成1/2的比特位發(fā)生變化。消息M的任何改變都會導(dǎo)致哈希值H（M）發(fā)生改變。即如果輸入有微小不同，哈希運算后的輸出一定不同。

3

哈希算法

把網(wǎng)址A，轉(zhuǎn)換成數(shù)字1。網(wǎng)址B，轉(zhuǎn)換成數(shù)字2。

一個網(wǎng)址X，轉(zhuǎn)換成數(shù)字N，根據(jù)數(shù)字N作為下標，就可以快速地查找出網(wǎng)址X的信息。這個轉(zhuǎn)換的過程就是哈希算法。

比如這里有一萬首歌，給你一首新的歌X，要求你確認這首歌是否在那一萬首歌之內(nèi)。

無疑，將一萬首歌一個一個比對非常慢。但如果存在一種方式，能將一萬首歌的每首數(shù)據(jù)濃縮到一個數(shù)字（稱為哈希碼）中，于是得到一萬個數(shù)字，那么用同樣的算法計算新的歌X的編碼，看看歌X的編碼是否在之前那一萬個數(shù)字中，就能知道歌X是否在那一萬首歌中。

作為例子，如果要你組織那一萬首歌，一個簡單的哈希算法就是讓歌曲所占硬盤的字節(jié)數(shù)作為哈希碼。這樣的話，你可以讓一萬首歌“按照大小排序”，然后遇到一首新的歌，只要看看新的歌的字節(jié)數(shù)是否和已有的一萬首歌中的某一首的字節(jié)數(shù)相同，就知道新的歌是否在那一萬首歌之內(nèi)了。

一個可靠的哈希算法，應(yīng)該滿足：

對于給定的數(shù)據(jù)M,很容易算出哈希值X=F(M);

根據(jù)X很難反算出M;

很難找到M和N使得F(N)=F(M)

前面提到哈希函數(shù)具有抗碰撞性，碰撞性就是指有人實現(xiàn)找出一奇一偶使得哈希結(jié)果一致，但這在計算上是不可行的。

首先，把大空間的消息壓縮到小空間上，碰撞肯定是存在的。假設(shè)哈希值長度固定為256位，如果順序取1，2，…2^256+1， 這2^256+1個輸入值，逐一計算其哈希值，肯定能找到兩個輸入值使得其哈希值相同。但不要高興的太早，因為你得有時間把它算出來，才是你的。

根據(jù)生日悖論，如果隨機挑選其中的2^128+1輸入，則有99.8%的概率發(fā)現(xiàn)至少一對碰撞輸入。那么對于哈希值長度為256位的哈希函數(shù)，平均需要完成2^128次哈希計算，才能找到碰撞對。如果計算機每秒進行10000次哈希計算，需要約10^27年才能完成2^128次哈希計算。在區(qū)塊鏈中，哈希函數(shù)的抗碰撞性用來做區(qū)塊和交易的完整性驗證，一有篡改就能被識別出來。

前面提到挖礦需要礦工通過隨機數(shù)不斷計算得到小于給定難度值的數(shù)值。難度值（difficulty）是礦工們挖礦時的重要參考指標，它決定了礦工大約需要經(jīng)過多少次哈希運算才能產(chǎn)生一個合法的區(qū)塊。比特幣的區(qū)塊大約每10分鐘生成一個，為了讓新區(qū)塊的產(chǎn)生基本保持這個速率，難度值必須根據(jù)全網(wǎng)算力的變化進行調(diào)整。

哈希函數(shù)通過調(diào)整難度值來確保每個區(qū)塊挖出的時間都大約在10分鐘，哈希函數(shù)計算的難度值對保證區(qū)塊鏈系統(tǒng)的安全意義重大。正如美國的幾位計算機科學(xué)家在共同所著的書中所寫的：“哈希密碼是密碼學(xué)中的瑞士軍刀，它們在眾多各具特色的應(yīng)用中找到了一席之地，為了保證安全，不同的應(yīng)用會要求不同的哈希函數(shù)特點。事實已經(jīng)證明，要確定一系列哈希函數(shù)以全面達成可證安全極度困難?！?/p>

工作量證明需要有一個目標值。比特幣工作量證明的目標值（target）的計算公式如下：

目標值＝最大目標值 / 難度值

其中，最大目標值為一個恒定值：

0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

目標值的大小與難度值成反比。比特幣工作量證明的達成就是礦工計算出來的區(qū)塊哈希值必須小于目標值。

我們也可以簡單理解成，比特幣工作量證明的過程，就是通過不停地變換區(qū)塊頭（即嘗試不同的隨機值）作為輸入進行SHA256哈希運算，找出一個特定格式哈希值的過程（即要求有一定數(shù)量的前導(dǎo)0）。而要求的前導(dǎo)0的個數(shù)越多，代表難度越大。

4

舉個栗子幫助理解

▌場景一、小星和阿呆在籃球場

小星：阿呆，你是不是口渴了，你要不要去買水喝，順便幫我買一瓶哈。

阿呆：呵呵，你的小心思我還不知道，你自己也口渴了吧，你去，我不去。

小星：哎哎，咱們不扯這些沒用的，來拋硬幣，好不好，正面你去，反面我去，公平吧，如何？

阿呆：好吧。

………

▌場景二、小星與阿呆即時聊天中

阿呆：小星，今天來我家玩，來的路上，有一家披薩店，很好吃，順便帶一點哈。

小星：哦，要不你來我家玩吧，你順便帶上披薩。

阿呆：小星，你竟然都這么說了，看來只能拋硬幣解決了。

小星：丫的，這個怎么拋，我怎么知道你有沒有搞鬼。

阿呆：嗯，那到也是，要不這樣。

1.考慮對結(jié)果加密

阿呆：我心中想一個數(shù)，假設(shè)為A，然后A在乘以一個數(shù)B，得到結(jié)果C。A是我的密鑰，我把結(jié)果C告訴你。你來猜A是奇數(shù)還是偶數(shù)，猜中了，算你贏。

小星：這不行，如果你告訴我C是12，我猜A是奇數(shù)，你可以說A是4，B是3。我猜A是偶數(shù)，你可以說A是3，B是4。要不你告訴我C是多少的時候，也告訴我B是多少。

阿呆：那這不行，告訴你C和B，不等于告訴你A是多少了，還猜個屁。不行得換個方式。

2.不可逆加密

阿呆：小星，你看這樣可以不，我想一個A，經(jīng)過下面的過程：

1.A+123=B2.B^2=C3.取C中第2~4位數(shù)，組成一個3位數(shù)D4.D/12的結(jié)果求余數(shù)，得到E

阿呆：我把E和上述計算方式都告訴你，你猜A是奇數(shù)還是偶數(shù)，然后我告訴你A是多少，你可以按上述的計算過程來驗證我是否有說謊。

小星：嗯，我想想，假如阿呆你想的A為5，那么：

5+123=128128^2=16384D=638 E=638mod12=53

(mod表示除法的求余數(shù))

小星：咦，厲害了，一個A值對應(yīng)一個唯一的E值，根據(jù)E還推算不出來A。你太賤了，好吧，這個算公平，誰撒謊都能被識別出來。

小星：阿呆，你出題吧 ……

這種丟掉一部分信息的加密方式稱為“單向加密”，也叫哈希算法。

5

常見的哈希算法

1、SHA-1算法

SHA-1的輸入是最大長度小于264位的消息，輸入消息以512位的分組為單位進行處理，輸出是160位的消息摘要。SHA-1具有實現(xiàn)速度高、容易實現(xiàn)、應(yīng)用范圍廣等優(yōu)點，其算法描述如下。

對輸入的消息進行填充：經(jīng)過填充后，消息的長度模512應(yīng)與448同余。填充的方式為第一位是1，余下各位都為0。再將消息被填充前的長度以big-endian的方式附加在上一步留下的最后64位中。該步驟是必須的，即使消息的長度已經(jīng)是所希望的長度。填充的長度范圍是1到512。

初始化緩沖區(qū)：可以用160位來存放Hash函數(shù)的初始變量、中間摘要及最終摘要，但首先必須進行初始化，對每個32位的初始變量賦值，即：

進入消息處理主循環(huán)，處理消息塊：一次處理512位的消息塊，總共進行4輪處理，每輪進行20次操作，如圖所示。這4輪處理具有類似的結(jié)構(gòu)，但每輪所使用的輔助函數(shù)和常數(shù)都各不相同。每輪的輸入均為當前處理的消息分組和緩沖區(qū)的當前值A(chǔ)、B、C、D、E，輸出仍放在緩沖區(qū)以替代舊的A、B、C、D、E的值。第四輪的輸出再與第一輪的輸入CVq相加，以產(chǎn)生CVq+1，其中加法是緩沖區(qū)5個字CVq中的每個字與中相應(yīng)的字模232相加。

圖 單個512位消息塊的處理流程

輸出：所有的消息分組都被處理完之后，最后一個分組的輸出即為得到的消息摘要值。

SHA-1的步函數(shù)如圖所示，它是SHA-1最為重要的函數(shù)，也是SHA-1中最關(guān)鍵的部件。

圖 SHA-1的步函數(shù)

SHA-1每運行一次步函數(shù)，A、B、C、D的值就會依次賦值給B、C、D、E這幾個寄存器。同時，A、B、C、D、E的輸入值、常數(shù)和子消息塊在經(jīng)過步函數(shù)運算后就會賦值給A。

其中，t是步數(shù)，0≤t≤79，Wt是由當前512位長的分組導(dǎo)出的一個32位的字，Kt是加法常量。

基本邏輯函數(shù)f的輸入是3個32位的字，輸出是一個32位的字，其函數(shù)表示如下。

對于每個輸入分組導(dǎo)出的消息分組wt，前16個消息字wt（0≤t≤15）即為消息輸入分組對應(yīng)的16個32位字，其余wt（0≤t≤79）可按如下公式得到：

其中，ROTLs表示左循環(huán)移位s位，如圖所示。

圖 SHA-1的80個消息字的產(chǎn)生過程

2、SHA-2算法

SHA-2系列Hash算法，其輸出長度可取SHA-2系列哈希算法的輸出長度可取224位、256位、384位、512位，分別對應(yīng)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位的長度塊，其值為填充前消息的長度。從而產(chǎn)生長度為512整數(shù)倍的消息分組，填充后消息的長度最多為264位。

（2）初始化鏈接變量

鏈接變量的中間結(jié)果和最終結(jié)果存儲于256位的緩沖區(qū)中，緩沖區(qū)用8個32位的寄存器A、B、C、D、E、F、G和H表示，輸出仍放在緩沖區(qū)以代替舊的A、B、C、D、E、F、G、H。首先要對鏈接變量進行初始化，初始鏈接變量存儲于8個寄存器A、B、C、D、E、F、G和H中：

初始鏈接變量是取自前8個素數(shù)（2、3、5、7、11、13、17、19）的平方根的小數(shù)部分其二進制表示的前32位。

（3）處理主循環(huán)模塊

消息塊是以512位分組為單位進行處理的，要進行64步循環(huán)操作（如圖所示）。每一輪的輸入均為當前處理的消息分組和得到的上一輪輸出的256位緩沖區(qū)A、B、C、D、E、F、G、H的值。每一步中均采用了不同的消息字和常數(shù)，下面將給出它們的獲取方法。

圖SHA-256的壓縮函數(shù)

（4）得出最終的Hash值

所有512位的消息塊分組都處理完以后，最后一個分組處理后得到的結(jié)果即為最終輸出的256位的消息摘要。

步函數(shù)是SHA-256中最為重要的函數(shù)，也是SHA-256中最關(guān)鍵的部件。其運算過程如圖所示。

圖SHA-256的步函數(shù)

根據(jù)T1、T2的值，對寄存器A、E進行更新。A、B、C、E、F、G的輸入值則依次賦值給B、C、D、F、G、H。

Kt的獲取方法是取前64個素數(shù)（2，3，5，7，……）立方根的小數(shù)部分，將其轉(zhuǎn)換為二進制，然后取這64個數(shù)的前64位作為Kt。其作用是提供了64位隨機串集合以消除輸入數(shù)據(jù)里的任何規(guī)則性。

對于每個輸入分組導(dǎo)出的消息分組Wt，前16個消息字Wt（0≤t≤15）直接按照消息輸入分組對應(yīng)的16個32位字，其他的則按照如下公式來計算得出：

圖SHA-256的64個消息字的生成過程

SHA-512算法

SHA-512是SHA-2中安全性能較高的算法，主要由明文填充、消息擴展函數(shù)變換和隨機數(shù)變換等部分組成，初始值和中間計算結(jié)果由8個64位的移位寄存器組成。該算法允許輸入的最大長度是2128位，并產(chǎn)生一個512位的消息摘要，輸入消息被分成若干個1024位的塊進行處理，具體參數(shù)為：消息摘要長度為512位；消息長度小于2128位；消息塊大小為1024位；消息字大小為64位；步驟數(shù)為80步。下圖顯示了處理消息、輸出消息摘要的整個過程，該過程的具體步驟如下。

圖SHA-512的整體結(jié)構(gòu)

消息填充：填充一個“1”和若干個“0”，使其長度模1024與896同余，填充位數(shù)為0-1023，填充前消息的長度以一個128位的字段附加到填充消息的后面，其值為填充前消息的長度。

鏈接變量初始化：鏈接變量的中間結(jié)果和最終結(jié)果都存儲于512位的緩沖區(qū)中，緩沖區(qū)用8個64位的寄存器A、B、C、D、E、F、G、H表示。初始鏈接變量也存儲于8個寄存器A、B、C、D、E、F、G、H中，其值為：

初始鏈接變量采用big-endian方式存儲，即字的最高有效字節(jié)存儲于低地址位置。初始鏈接變量取自前8個素數(shù)的平方根的小數(shù)部分其二進制表示的前64位。

主循環(huán)操作：以1024位的分組為單位對消息進行處理，要進行80步循環(huán)操作。每一次迭代都把512位緩沖區(qū)的值A(chǔ)、B、C、D、E、F、G、H作為輸入，其值取自上一次迭代壓縮的計算結(jié)果，每一步計算中均采用了不同的消息字和常數(shù)。

計算最終的Hash值：消息的所有N個1024位的分組都處理完畢之后，第N次迭代壓縮輸出的512位鏈接變量即為最終的Hash值。

步函數(shù)是SHA-512中最關(guān)鍵的部件，其運算過程類似SHA-256。每一步的計算方程如下所示，B、C、D、F、G、H的更新值分別是A、B、C、E、F、G的輸入狀態(tài)值，同時生成兩個臨時變量用于更新A、E寄存器。

對于80步操作中的每一步t，使用一個64位的消息字Wt，其值由當前被處理的1024位消息分組Mi導(dǎo)出，導(dǎo)出方法如圖所示。前16個消息字Wt（0≤t≤15）分別對應(yīng)消息輸入分組之后的16個32位字，其他的則按照如下公式來計算得出：

圖SHA-512的80個消息字生成的過程

其中，

式中，ROTRn（X）表示對64位的變量x循環(huán)右移n位，SHRn（X）表示對64位的變量x右移n位。

從圖可以看出，在前16步處理中，Wt的值等于消息分組中相對應(yīng)的64位字，而余下的64步操作中，其值是由前面的4個值計算得到的，4個值中的兩個要進行移位和循環(huán)移位操作。

Kt的獲取方法是取前80個素數(shù)（2，3，5，7，……）立方根的小數(shù)部分，將其轉(zhuǎn)換為二進制，然后取這80個數(shù)的前64位作為Kt，其作用是提供了64位隨機串集合以消除輸入數(shù)據(jù)里的任何規(guī)則性。

SHA-224與SHA-384

SHA-256和SHA-512是很新的Hash函數(shù)，前者定義一個字為32位，后者則定義一個字為64位。實際上二者的結(jié)構(gòu)是相同的，只是在循環(huán)運行的次數(shù)、使用常數(shù)上有所差異。SHA-224及SHA-384則是前述兩種Hash函數(shù)的截短型，它們利用不同的初始值做計算。

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個素數(shù)（23、29、31、37、41、43、47、53）的平方根的小數(shù)部分其二進制表示的第二個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個素數(shù)（23、29、31、37、41、43、47、53）的平方根的小數(shù)部分其二進制表示的前64位，SHA-384的初始鏈接變量如下：

SHA-384的詳細計算步驟與SHA-512的相同。

3、SHA-3算法

SHA-3算法整體采用Sponge結(jié)構(gòu)，分為吸收和榨取兩個階段。SHA-3的核心置換f作用在5×5×64的三維矩陣上。整個f共有24輪，每輪包括5個環(huán)節(jié)θ、ρ、π、χ、τ。算法的5個環(huán)節(jié)分別作用于三維矩陣的不同維度之上。θ環(huán)節(jié)是作用在列上的線性運算；ρ環(huán)節(jié)是作用在每一道上的線性運算，將每一道上的64比特進行循環(huán)移位操作；π環(huán)節(jié)是將每道上的元素整體移到另一道上的線性運算；χ環(huán)節(jié)是作用在每一行上的非線性運算，相當于將每一行上的5比特替換為另一個5比特；τ環(huán)節(jié)是加常數(shù)環(huán)節(jié)。

目前，公開文獻對SHA-3算法的安全性分析主要是從以下幾個方面來展開的。

對SHA-3算法的碰撞攻擊、原像攻擊和第二原像攻擊。

對SHA-3算法核心置換的分析，這類分析主要針對算法置換與隨機置換的區(qū)分來展開。

對SHA-3算法的差分特性進行展開，主要研究的是SHA-3置換的高概率差分鏈，并構(gòu)筑差分區(qū)分器。

Keccak算法的立體加密思想和海綿結(jié)構(gòu)，使SHA-3優(yōu)于SHA-2，甚至AES。Sponge函數(shù)可建立從任意長度輸入到任意長度輸出的映射。

4、RIPEMD160算法

RIPEMD（RACE Integrity Primitives Evaluation Message Digest），即RACE原始完整性校驗消息摘要。RIPEMD使用MD4的設(shè)計原理，并針對MD4的算法缺陷進行改進，1996年首次發(fā)布RIPEMD-128版本，它在性能上與SHA-1相類似。

RIPEMD-160是對RIPEMD-128的改進，并且是RIPEMD中最常見的版本。RIPEMD-160輸出160位的Hash值，對160位Hash函數(shù)的暴力碰撞搜索攻擊需要280次計算，其計算強度大大提高。RIPEMD-160的設(shè)計充分吸取了MD4、MD5、RIPEMD-128的一些性能，使其具有更好的抗強碰撞能力。它旨在替代128位Hash函數(shù)MD4、MD5和RIPEMD。

RIPEMD-160使用160位的緩存區(qū)來存放算法的中間結(jié)果和最終的Hash值。這個緩存區(qū)由5個32位的寄存器A、B、C、D、E構(gòu)成。寄存器的初始值如下所示：

數(shù)據(jù)存儲時采用低位字節(jié)存放在低地址上的形式。

處理算法的核心是一個有10個循環(huán)的壓縮函數(shù)模塊，其中每個循環(huán)由16個處理步驟組成。在每個循環(huán)中使用不同的原始邏輯函數(shù)，算法的處理分為兩種不同的情況，在這兩種情況下，分別以相反的順序使用5個原始邏輯函數(shù)。每一個循環(huán)都以當前分組的消息字和160位的緩存值A(chǔ)、B、C、D、E為輸入得到新的值。每個循環(huán)使用一個額外的常數(shù)，在最后一個循環(huán)結(jié)束后，兩種情況的計算結(jié)果A、B、C、D、E和A′、B′、C′、D′、E′及鏈接變量的初始值經(jīng)過一次相加運算產(chǎn)生最終的輸出。對所有的512位的分組處理完成之后，最終產(chǎn)生的160位輸出即為消息摘要。

除了128位和160位的版本之外，RIPEMD算法也存在256位和320位的版本，它們共同構(gòu)成RIPEMD家族的四個成員：RIPEMD-128、RIPEMD-160、RIPEMD-256、RIPEMD-320。其中128位版本的安全性已經(jīng)受到質(zhì)疑，256位和320位版本減少了意外碰撞的可能性，但是相比于RIPEMD-128和RIPEMD-160，它們不具有較高水平的安全性，因為他們只是在128位和160位的基礎(chǔ)上，修改了初始參數(shù)和s-box來達到輸出為256位和320位的目的。