哈希函數(shù)

一、概念

哈希函數(shù)是一公開函數(shù)。用于將任意長的消息M映射為較短的、固定長度的值H（M），又稱為散列函數(shù)、雜湊函數(shù)。我們稱函數(shù)值H（M）為哈希值、雜湊值、雜湊碼、信息摘要。

雜湊值是信息中所有比特的函數(shù)，因此提供了一種錯誤檢測能力，即改變信息中任何一個比特或幾個比特都會使雜湊值改變。

?

二、性質(zhì)

實用性要求（本身特性，用于消息認證的基本要求）：

①輸入任意性：函數(shù)的輸入可以是任意大小的數(shù)據(jù)

（實際上不是任意的，如SHA-1要求不超過2^64）

②輸出固定性：函數(shù)的輸出是一個固定大小的數(shù)據(jù)；

（如SHA-1的輸出是160比特，SHA-256的輸出是256比特）

③對任意給定的x，H（x）計算相對容易，無論是軟件還是硬件實現(xiàn)。

?

安全性要求：對于區(qū)塊鏈技術(shù)以及加密數(shù)字貨幣而言，要使得哈希函數(shù)達到密碼安全：

①collision?resistance抗碰撞；對任意x≠y，使H(x)=H(y)是不可能的。

作用：檢測信息是否被篡改

注意：哈希碰撞不可避免，因為輸入空間大于輸出空間。

②hiding單向不可逆；知道H(x)無法推導x。

前提：輸入的空間要足夠大，使得暴力破解的方法不可行，而且輸入的分布要比較均勻，各種取值的可能性都差不多。

③puzzle?friendly；哈希值的計算是不可預(yù)測的，只根據(jù)輸入很難預(yù)測出輸出。

如果需要找出一個哈希值存在某個范圍內(nèi)，只能通過一個一個運算才能找出。

一個好的“Puzzle friendly”算法不會顯式輸入x和輸出H(x)之間的任何可預(yù)先確定的相關(guān)性。

該性質(zhì)保證了比特幣系統(tǒng)中，只能通過挖礦獲得比特幣。

?

三、哈希函數(shù)的一般結(jié)構(gòu)

四、哈希的實際用途

Hash能把一個大范圍映射到一個小范圍，能對輸入數(shù)據(jù)或文件進行校驗，還可用于查找等。具體的：

①唯一標識或數(shù)據(jù)檢驗：

能夠?qū)斎霐?shù)據(jù)或文件進行校驗，判斷是否相同或是否被修改。 如圖片識別，可針對圖像二進制流進行摘要后MD5，得到的哈希值作為圖片唯一標識； 如文件識別，服務(wù)器在接受文件上傳時，對比兩次傳送文件的哈希值，若相同則無須再次上傳（傳統(tǒng)的奇偶校驗和CRC校驗一定程度上能檢測并糾正數(shù)據(jù)傳輸中的信道誤碼，但沒有抗數(shù)據(jù)篡改的能力）。

②安全加密：

最常用于加密的哈希算法是 MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法）和SHA（Secure Hash Algorithm，安全散列算法）。對于敏感數(shù)據(jù)進行MD5或SHA加密傳輸。哈希算法還可以檢驗信息的擁有者是否真實。如，用保存密碼的哈希值代替保存密碼，基本可以杜絕泄密風險。

③數(shù)字簽名：對Hash值，又稱“數(shù)字摘要”進行數(shù)字簽名。

④散列函數(shù)：是構(gòu)造散列表的關(guān)鍵。它直接決定了散列沖突的概率和散列表的性質(zhì)。

⑤*負載均衡：

負載均衡算法有很多，比如輪詢、隨機、加權(quán)輪詢等。那如何才能實現(xiàn)一個會話粘滯（session sticky）的負載均衡算法呢？也就是說，需要在同一個客戶端上，將一次會話中的所有請求都路由到同一個服務(wù)器上。

直接的方法就是，維護一張映射關(guān)系表，這張表的內(nèi)容是客戶端IP地址或者會話ID與 服務(wù)器編號的映射關(guān)系?？蛻舳税l(fā)出的每次請求，都要先在映射表中查找應(yīng)該路由到的服務(wù)器編號，然后再請求編號對應(yīng)的服務(wù)器。這種方法簡單直觀，但也有幾個弊端：

A.如果客戶端很多，映射表可能會很大，比較浪費內(nèi)存空間；

B.客戶端下線、上線，服務(wù)器擴容、縮容都會導致映射失效，維護映射表的成本就會很大；

還可以通過哈希算法，對客戶端IP地址或者會話ID計算哈希值，將取得的哈希值與服務(wù)器列表的大小進行取模運算，最終得到的值就是應(yīng)該被路由到的服務(wù)器編號。

A.哈希算法可以保證每個客戶端的哈希值不同，達到負載均衡效果

B.取?？梢园淹粋€ IP 過來的所有請求，都路由到同一個后端服務(wù)器上

⑥*數(shù)據(jù)分片：

比如圖庫中有大量圖片，可以使用分片思想，準備n臺機器，每臺機器負責散列表的一部分數(shù)據(jù)。每次從圖庫取一個圖片，計算唯一標識，然后與機器個數(shù)n求余取模，得到的值就是被分配到的機器編號，然后將這個唯一標識和圖片路徑發(fā)往對應(yīng)機器構(gòu)建散列表。 當進行圖片查找時，使用相同的哈希函數(shù)對圖片摘要信息取唯一標識并對n求余取模操作后，得到的值k，就是當前圖片所存儲的機器編號，在該機器的散列表中查找該圖片即可。海量數(shù)據(jù)的處理問題，都可以借助這種數(shù)據(jù)分片思想，突破單機內(nèi)存、CPU等資源限制。

⑦*分布式存儲：

一致性哈希：對于K個關(guān)鍵字和n個槽位（分布式系統(tǒng)中的節(jié)點）的哈希表，增減槽位后，平均只需對K/n個關(guān)鍵字重新映射。

解決緩存等分布式系統(tǒng)的擴容、縮容導致大量數(shù)據(jù)搬移難題。

?

問題：在分布式緩存的情景下，若其中一臺服務(wù)器宕機，或者整體要縮容擴容。雖然hash值不變，但取模的服務(wù)器數(shù)改變了，因此計算出的對應(yīng)服務(wù)器已經(jīng)錯誤了。導致所有的數(shù)據(jù)請求都會穿透緩存，直接去請求數(shù)據(jù)庫。很可能發(fā)生雪崩效應(yīng)，壓垮數(shù)據(jù)庫。

?

假設(shè)有k個機器，數(shù)據(jù)的哈希值的范圍是[0, MAX]：

==》將整個范圍劃分成m個小區(qū)間（m 遠大于k）去直接管理每個客戶端

==》每個機器負責 m/k個小區(qū)間

==》若集群變動只用遷移少量區(qū)間即可

?

服務(wù)器定位：確定每個管理哪些區(qū)間，原來的分片算法并無此步。注：這里的2^32是因為IPV4，32位的IP斷，相當于根據(jù)IP斷進行分區(qū)管理。

客戶端定位：定位不依賴于服務(wù)器數(shù)量，而是看其處于哪個小區(qū)間。

區(qū)間遷移：若有新機器加入，就將某幾個小區(qū)間的數(shù)據(jù)，從原來的機器中搬移到新的機器中。這樣，既不用全部重新哈希、搬移數(shù)據(jù)，也保持了各個機器上數(shù)據(jù)數(shù)量的均衡。

1.硬哈希

分布式系統(tǒng)中，假設(shè)有n個節(jié)點，傳統(tǒng)方案使用mod(key, n)映射數(shù)據(jù)和節(jié)點。當擴容或縮容時(哪怕增減1個節(jié)點)，映射關(guān)系變?yōu)?mod(key, n+1) / mod(key, n-1)，絕大多數(shù)數(shù)據(jù)的映射關(guān)系都會失效。

2.特性

均衡性(Balance)：將關(guān)鍵字的哈希地址均勻地分布在地址空間中，使地址空間充分利用。

?

單調(diào)性(Monotonicity)：當?shù)刂房臻g增大（減少）時，通過哈希函數(shù)所得到的關(guān)鍵字的哈希地址也能映射的新的地址空間，而不是僅限于原先的地址空間。簡單的哈希函數(shù)往往不能滿足此性質(zhì)。

?

分散性(Spread)：哈希經(jīng)常用在分布式環(huán)境中，終端用戶通過哈希函數(shù)將自己的內(nèi)容存到不同的緩沖區(qū)。此時，終端有可能看不到所有的緩沖，只能看到其中的一部分。當終端希望通過哈希過程將內(nèi)容映射到緩沖上時，由于不同終端所見的緩沖范圍有可能不同，從而導致哈希的結(jié)果不一致，最終的結(jié)果是相同的內(nèi)容被不同的終端映射到不同的緩沖區(qū)中，降低了系統(tǒng)存儲的效率。好的哈希算法應(yīng)能夠盡量避免不一致的情況發(fā)生，盡量降低分散性。

?

負載(Load)：對于一個特定的緩沖區(qū)而言，也可能被不同的用戶映射為不同的內(nèi)容。這種情況也是應(yīng)當避免的，因此好的哈希算法應(yīng)能夠盡量降低緩沖的負荷。

?

3.映射思想描述

把數(shù)據(jù)用hash函數(shù)（如MD5），映射到一個很大的空間里，如圖所示。數(shù)據(jù)的存儲時，先得到一個hash值，對應(yīng)到這個環(huán)中的每個位置，如k1對應(yīng)到了圖中所示的位置，然后沿順時針找到一個機器節(jié)點B，將k1存儲到B這個節(jié)點中。

如果B節(jié)點宕機了，則B上的數(shù)據(jù)就會落到C節(jié)點上：

只會影響C節(jié)點，對其他的節(jié)點A，D的數(shù)據(jù)不會造成影響。然而，這又會造成一個“雪崩”的情況，即C節(jié)點由于承擔了B節(jié)點的數(shù)據(jù)，C節(jié)點的負載會變高，很容易也宕機，依次下去，造成整個集群都掛了。

為此，引入了“虛擬節(jié)點”的概念：想象在這個環(huán)上有很多“虛擬節(jié)點”，數(shù)據(jù)的存儲是沿著環(huán)的順時針方向找一個虛擬節(jié)點，每個虛擬節(jié)點都會關(guān)聯(lián)到一個真實節(jié)點：

圖中的A1、A2、B1、B2、C1、C2、D1、D2都是虛擬節(jié)點，機器A負載存儲A1、A2的數(shù)據(jù)，機器B負載存儲B1、B2的數(shù)據(jù)，機器C負載存儲C1、C2的數(shù)據(jù)。由于這些虛擬節(jié)點數(shù)量很多，均勻分布，因此不會造成“雪崩”現(xiàn)象。

?

?

密碼學Hash函數(shù)的應(yīng)用

1.消息認證：

1.是確保數(shù)據(jù)正確，2是確保發(fā)送方的身份真實

當提供消息認證功能時，Hash值通常稱為信息摘要

操作過程：發(fā)送者先將信息M進行Hash，然后將【M+Hash】一起發(fā)送給B，B再做一次Hash運算將結(jié)果與Hash值比較，相同則沒有篡改。

注意：此種情況下必須保證Hash的安全傳輸，因為中間人攻擊完全可以改完信息之后再算一個新的Hash值，接收者并不會發(fā)現(xiàn)。

?

使用不同方法提供消息認證服務(wù)：

①使用對稱密碼一起加密M和Hash：認證功能+保密性

②使用對稱密碼只加密Hash：認證功能

③不使用加密算法，使用一個雙方都知道的秘密值S和M一起計算Hash值：認證功能

④在③的基礎(chǔ)上再將整個消息和Hash一起加密：認證功能+保密性

?

人們不希望使用加密函數(shù)的理由：

①加密軟件速度慢

②加密硬件成本不容忽視

③硬件的優(yōu)化通常是針對大數(shù)據(jù)塊

④加密算法可能受專利保護，會增加成本

更一般的，消息認證通過使用消息認證碼（MAC）實現(xiàn)，即帶密鑰的哈希函數(shù)。同③不使用加密算法，此時的秘密值就是密鑰

?

2.數(shù)字簽名

過程：

使用發(fā)送方的私鑰，利用公鑰算法對Hash進行加密。

如果希望保密整個信息，則發(fā)送方可以先使用私鑰對Hash進行加密，再使用對稱密碼加密消息和公鑰算法結(jié)果，這是比較常用的做法。

?

五、常用哈希函數(shù)及其生命周期

常見Hash算法有：

MD5（MD5 Message-Digest Algorithm，MD5消息摘要算法）

SHA（Secure Hash Algorithm，安全散列算法）

DES（Data Encryption Standard，數(shù)據(jù)加密標準）

AES（Advanced Encryption Standard，高級加密標準）

目前MD5和SHA1已經(jīng)被破解，一般推薦至少使用SHA2-256算法。

?

（一）MD5：Message-Digest Algorithm消息摘要算法

MD5輸入任意長度的信息，在處理過程中以512位輸入數(shù)據(jù)塊為單位，輸出為128位的信息（數(shù)字指紋）。

?

常用場景：

1、一致性驗證，防篡改：如發(fā)送一個電子文檔，發(fā)送前，得到MD5的輸出結(jié)果a。對方接收后，也得到一個MD5的輸出結(jié)果b。如果a與b一樣就代表中途未被篡改。

2、安全訪問認證，增強密碼保存的安全性：例如網(wǎng)站將用戶密碼的MD5值保存，而不是存儲用戶密碼。當用戶登錄的時候，系統(tǒng)把用戶輸入的密碼進行MD5 Hash運算，然后再去和保存在文件系統(tǒng)中的MD5值進行比較，進而確定輸入的密碼是否正確。

3、防抵賴，數(shù)字簽名：這需要一個第三方認證機構(gòu)。例如A寫了一個文件，認證機構(gòu)對此文件用MD5算法產(chǎn)生摘要信息并做好記錄。若以后A說這文件不是他寫的，權(quán)威機構(gòu)只需對此文件重新產(chǎn)生摘要信息，然后跟記錄在冊的摘要信息進行比對，相同的話，就證明是A寫的了。這就是所謂的“數(shù)字簽名”。

?

算法實現(xiàn)過程：

①消息填充，補長到512的倍數(shù)。最后64位為消息長度（填充前的長度）的低64位，在消息后面進行填充，填充第一位為1，其余為0。直到使其字節(jié)長度對512求余數(shù)的結(jié)果等于448，即（n*512) + 448。

為什么余數(shù)為448呢，因為剩下的512-448 等于64位，是用于表示填充前的信息長度。信息長度就變?yōu)镹*512 + 448 + 64 = (N+1)*512，剛好是512的整數(shù)倍數(shù)。

?

②分割：把輸入消息分割為512位的分組，每一塊又被劃分為16個32位子分組。

?

③計算：每一個分組（512位）進行64次計算后（4輪F\G\H\I，每輪16個子塊M0~M15），將A，B，C，D分別加上計算得到的a，b，c，d。當做新的A，B，C，D，并將這4個變量賦值給a，b，c，d再進行下一分組的運算。

由于填充后的消息長度為(N+1)*512，則共需計算N+1個分組。計算所有數(shù)據(jù)分組后，這4個變量為最后的結(jié)果，即MD5值。每次一個輸入128位（A\B\C\D），另一個輸入512位，結(jié)果輸出128位，用于下一輪輸入。

?

首先需要用到4個常數(shù)：

四個32位變量初始化(經(jīng)過研究所得，為固定值)，稱為鏈接變量（chaining variable）

A = 0×01234567 ；B = 0×89ABCDEF ；C = 0xFEDCBA98 ；D = 0×76543210 ?

以上為標準的幻數(shù)的（物理順序），在程序中(小端模式)定義是：

A = 0x67452301?；B = 0xEFCDAB89?；C = 0x98BADCFE?；D = 0x10325476

?

4個非線性函數(shù)：

F(X,Y,Z)=(X & Y) | ((~X) & Z);

G(X,Y,Z)=(X & Z) | (Y & (~Z));

H(X,Y,Z)=X ^ Y ^ Z;

I(X,Y,Z)=Y ^ (X | (~Z));

(&是與, |是或, ~是非, ^是異或)

4種操作：

FF(a,b,c,d,Mi,s,tj) ?表示a=b+((a+(F(b,c,d)+Mi+tj)<<< s)

GG(a,b,c,d,Mi,s,tj) 表示 a=b+((a+(G(b,c,d)+Mi+tj)<<< s)

HH(a,b,c,d,Mi,s,tj) 表示 a=b+((a+(H(b,c,d)+Mi+tj)<<< s)

II(a,b,c,d,Mi,s,tj) ??表示a=b+((a+(I(b,c,d)+Mi+tj)<<< s)

?

Mi表示消息的第i個子分組（從0到15，共16個）

<<< s表示循環(huán)左移s位

常數(shù)tj：在第j步中，tj是4294967296*abs(sin(j))的整數(shù)部分，i的單位是弧度。

(4294967296是2的32次方)，亦可用 0x100000000UL * abs(sin((double)j)) 計算。

x循環(huán)左移s位:( s << x ) | ( s >> (32 - x) )

④輸出：輸出由4個32位分組組成，級聯(lián)后將生成一個128位散列值。

?

MD5性質(zhì)：

①壓縮性：任意長度的數(shù)據(jù)，算出的MD5值長度都是固定的(相當于超損壓縮)。

②容易計算

③抗修改性：哪怕只修改1個字節(jié)，所得到的MD5值都有很大區(qū)別。

④弱抗碰撞：已知原數(shù)據(jù)和其MD5值，想找到一個具有相同MD5值的數(shù)據(jù)（即偽造數(shù)據(jù)）是非常困難的。

⑤強抗碰撞：想找到兩個不同的數(shù)據(jù)，使它們具有相同的MD5值，是非常困難的。

?

MD5不是加密算法：

使用加密算法加密后的消息是完整的，并且基于解密算法后，可以恢復(fù)原始數(shù)據(jù)。

而MD5算法得到的消息是不完整的，并且無法通過摘要的數(shù)據(jù)也無法得到原始數(shù)據(jù)。

MD5算法對比加密算法缺少了解密過程，因此，MD5算法不是加密算法。

MD5已經(jīng)較老，散列長度通常為128位，隨著計算機運算能力提高，找到“碰撞”是可能的。因此，在安全要求高的場合不使用MD5。

?

MD2、MD4和MD5：

MD2、MD4和MD5是Rivest開發(fā)的信息摘要算法。它們是針對數(shù)字簽名應(yīng)用而言的，在一個大的消息被用私鑰簽名之前，必須以安全的方式‘壓縮’。這三種算法都接收任意長度的消息，并生成128位消息摘要。雖然這些算法的結(jié)構(gòu)有些相似，但MD2的設(shè)計與MD4和MD5完全不同，MD2是為8位機器做過設(shè)計優(yōu)化的，而MD4和MD5卻是面向32位的電腦。

MD2由Rivest于1989年開發(fā)。信息首先被填充(數(shù)據(jù)部位)，使其字節(jié)長度是16的倍數(shù)。然后在信息末尾追加一個16字節(jié)的校驗和，并在這個新產(chǎn)生的信息上計算哈希值。Rogier和Chauvaud發(fā)現(xiàn)，如果省略校驗和的計算，MD2的碰撞可以被構(gòu)造出來。這是MD2已知的唯一的密碼分析結(jié)果。

MD4是Rivest于1990年開發(fā)的。對信息進行填充，保證信息在加上448后的長度可以被512整除。然后將信息原始長度的64位二進制表示添加到信息中。該消息以512位塊進行處理，每個塊以三個不同的步驟進行處理。Den Boer和Bosselaers等人非常迅速地開發(fā)了對MD4版本的攻擊，其中第一輪或最后一輪丟失。Dobbertin 已經(jīng)在一個典型的PC機上顯示了如何在一分鐘內(nèi)就能發(fā)現(xiàn)MD4全版本的碰撞。顯然，現(xiàn)在MD4被認為是被打破了。

MD5由Rivest于1991年開發(fā)。它在md4的基礎(chǔ)上增加了"安全-帶子"（safety-belts）的概念，雖然比MD4稍慢，但更安全。該算法由4個截然不同的步驟組成，其設(shè)計與MD4略有不同。信息摘要大小以及填充要求保持不變。Den Boer和Bosselaers 發(fā)現(xiàn)了MD5的偽碰撞，但沒有其他已知的密碼分析結(jié)果。

Van Oorschot 和 Wiener在哈希函數(shù)中考慮了對碰撞的粗暴力搜索，他們估計專門為MD5設(shè)計的碰撞搜索機(1994年耗資 1000萬美元)可以在平均每24天內(nèi)找到一個MD5的碰撞。一般的技術(shù)可以應(yīng)用于其他哈希函數(shù)。

?（二）SHA-1：Secure Hash Algorithm安全哈希算法

主要適用于數(shù)字簽名標準（Digital Signature Standard DSS）里面定義的數(shù)字簽名算法（Digital Signature Algorithm DSA）。對于長度小于2^64b的消息，SHA-1將輸入流按照每塊512b（64B）進行分塊，并產(chǎn)生20B或160b的信息摘要。

每個明文分組的摘要生成過程如下：

1、將512位的明文分組劃分為16個子明文分組（32位）。

2、申請5個32位的鏈接變量，記為A、B、C、D、E。

3、16份子明文分組擴展為80份（32位）。

4、80份子明文分組進行4輪運算。

5、鏈接變量與初始鏈接變量進行求和運算。

6、鏈接變量作為下一個明文分組的輸入重復(fù)進行以上操作。

7、最后，5個鏈接變量里面的數(shù)據(jù)就是SHA1摘要。

?

具體算法實現(xiàn)過程：

①補位：（同MD5）消息補位使其長度在對512取模以后的余數(shù)是448。先補一個1，然后再補0，直到長度滿足對512取模后余數(shù)是448。補位是至少補一位，最多補512位。即使長度已經(jīng)滿足對512取模后余數(shù)是448，補位也必須要進行。

原始信息： ?011000010110001001100011

補位第一步：0110000101100010011000111，首先補一個“1”

補位第二步：01100001011000100110001110…..0，然后補423個“0”

可以把最后補位完成后的數(shù)據(jù)用16進制寫成下面的樣子，確保是448b：

61626380000000000000000000000000

00000000000000000000000000000000

00000000000000000000000000000000

0000000000000000

?

②補長度：將原始數(shù)據(jù)的長度補到已經(jīng)進行了補位操作的消息后面。通常用一個64位的數(shù)據(jù)來表示原始消息的長度。如果消息長度不大于2^64，那么第一個字就是0。

在進行了補長度的操作以后，整個消息就變成下面這樣了（16進制格式）：

61626380000000000000000000000000

00000000000000000000000000000000

00000000000000000000000000000000

00000000000000000000000000000018（16進制，一個數(shù)4位）

如果原始的消息長度超過了512，我們需要將它補成512的倍數(shù)。然后我們把整個消息分成一個個512位的數(shù)據(jù)塊。分別處理每一個數(shù)據(jù)塊，從而得到消息摘要。

?

③壓縮函數(shù)處理：每個消息塊都將進行四輪操作，每輪操作又將進行20步運算。

鏈接變量：函數(shù)的初始鏈接變量值、中間鏈接變量值和最終的輸出值都保存在5個32比特的寄存器A，B，C，D，E中，其中初始鏈接變量的值為：

A=H0=0x67452301

B=H1=0xEFCDAB89

C=H2=0x98BADCFE

D=H3=0x10325476

E=H4=0xC3D2E1F0

?

常量字K(0),K(1),...,K(79)，如果以16進制給出：

Kt=0x5A827999(0<=t<=19)?；

Kt=0x6ED9EBA1(20<=t<=39)?；

Kt=0x8F1BBCDC(40<=t<=59)?；

Kt=0xCA62C1D6(60<=t<=79)

?

函數(shù)：每個函數(shù)ft(0<=t<=79)都操作32位的字B，C，D并且產(chǎn)生32位的字作為輸出。ft(B,C,D)可以如下定義：

ft(B,C,D)=(B AND C)or( (NOT B)AND D ) ?????(0<=t<=19)

ft(B,C,D)=B XOR C XOR D ?????????????????(20<=t<=39)

ft(B,C,D)=(B AND C)or(B AND D)or(C AND D) ?(40<=t<=59)

ft(B,C,D)=B XOR C XOR D ?????????????????(60<=t<=79)

計算消息摘要：計算需要

A.?兩個緩沖區(qū)，每個由5個32位的字組成（A，B，C，D，E；H0，H1，H2，H3，H4）；

B.?一個“80個32位”的緩沖區(qū)（W0，W1，...，W79）；

C.?一個一個字的TEMP緩沖區(qū)。

開始處理Mi。（每個Mi包含80個步驟）

Mi：512b（64B），512位（512比特，64字）

在每一次步函數(shù)運算中，A、B、C、D中的值將依次賦值給B、C、D、E寄存器。同時，將A、B、C、D、E的當前的輸入值與加法常數(shù)和由消息塊生成的消息字的值通過步函數(shù)運算，將得出的值賦值給寄存器A，其表達式為：

每一個消息塊經(jīng)過運算后，將得到的值賦值給寄存器A、B、C、D、E，當前寄存器中的值與此次運算的輸入值進行模加運算，則得到當前的中間鏈接變量值。當依次計算出最后一個消息塊的值時，所得到的值即為最終的消息摘要。

處理完所有Mi后，消息摘要是一個160位的字符串，以下面的順序標識H0H1H2H3H4。

?

?

（三）SHA-2系列

SHA-2是六個不同算法的合稱，包括：SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。除了生成摘要的長度、循環(huán)運行的次數(shù)等一些微小差異外，這些算法的基本結(jié)構(gòu)是一致的。對于任意長度的消息，SHA256都會產(chǎn)生一個256bit長的消息摘要。

?

SHA-256算法

SHA-256算法的輸入是最大長度小于2^64位的消息，輸出是256位的消息摘要，輸入消息以512位的分組為單位進行處理。

?

①消息充填：（同MD5）添加一個“1”或者N個“0”，使其長度模512與448同余。在消息后附加64位的長度塊，其值為充填前消息的長度。從而產(chǎn)生長度為512整數(shù)倍的消息分組，充填后消息的長度最多為2^64位。

?

②初始化鏈接變量：鏈接變量的中間結(jié)果和最終結(jié)果存儲于256位的緩沖區(qū)中，緩沖區(qū)用8個32位的寄存器可用A-H，h0-h7表示，輸出仍然放在緩沖區(qū)以代替舊的8個寄存器。

h0 := 0x6a09e667

h1 := 0xbb67ae85

h2 := 0x3c6ef372

h3 := 0xa54ff53a

h4 := 0x510e527f

h5 := 0x9b05688c

h6 := 0x1f83d9ab

h7 := 0x5be0cd19

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

?

③初始化Kt（第t個密鑰）：Kt是取前64個素數(shù)(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,?61,67,71,73,79,83,89,97…)的立方根的小數(shù)部分二進制的前64位。提供了64位隨機串集合以消除輸入數(shù)據(jù)里的任何規(guī)則性。

④處理主循環(huán)模塊：消息塊是以512位分組為單位進行處理的，需要進行64步循環(huán)操作。每一輪的輸入均為當前處理的消息分組和上一輪輸出的256位緩沖區(qū)A-H的值。每一步中均采用了不同的消息字和常數(shù)。

?⑤消息拓展：

對一個消息分組M(t)迭代壓縮之前，首先進行消息擴展：

①將16個字的消息分組Mt擴展生成如下的64個字，供壓縮函數(shù)使用 W0，…，W63；

? ②消息擴展把原消息位打亂，隱蔽原消息位之間的關(guān)聯(lián)，增強了安全性；

SHA256算法中的最小運算單元稱為“字”（Word），一個字是32位。

?⑥壓縮：初始化變量A,B,C,E,F,G分別等于前面設(shè)置的哈希值 h0, h1, h2, h3, h4,h5, h6, h7。每一步都會生成兩個臨時的變量，T1、T2：根據(jù)T1、T2的值，對寄存器A、E進行更新。ABCEFG的輸入值則一次賦值給BCDFGH。

?

?

?⑦得出最終的Hash值：

在壓縮循環(huán)之后，在每一個塊循環(huán)內(nèi)，通過加上相應(yīng)的變量a-h來改變哈希值。加法都對2^23取模。

級聯(lián)最終的哈希值。

?

SHA-256工作全過程：

至今尚未出現(xiàn)對SHA-2有效的攻擊，SHA-2和SHA-1并沒有接受公眾密碼社區(qū)的詳細檢驗，所以它們的密碼安全性還不被廣泛信任。

總體上，HAS-256與MD4、MD5以及HSA-1等哈希函數(shù)的操作流程類似，在哈希計算之前首先要進行以下兩個步驟：

①對消息進行補位處理，最終的長度是512位的倍數(shù)；

②以512位為單位對消息進行分塊為M1,M2,…,Mn

③處理消息塊：從一個初始哈希H0開始，迭代計算：Hi = Hi-1 + CMi(Hi-1)

其中C是SHA256的壓縮函數(shù)，+是mod 2^32加法，Hn是消息區(qū)塊的哈希值。

?

?

?

（四）Keccak算法

SHA-3成為NIST的新哈希函數(shù)標準算法(FIPS PUB 180--5)。SHA-3的結(jié)構(gòu)仍屬于Merkle提出的迭代型哈希函數(shù)結(jié)構(gòu)。最大的創(chuàng)新點是采用了一種被稱為海綿結(jié)構(gòu)的新的迭代結(jié)構(gòu)。海綿結(jié)構(gòu)又稱為海綿函數(shù)。

在海綿函數(shù)中，輸入數(shù)據(jù)被分為固定長度的數(shù)據(jù)分組。每個分組逐次作為迭代的輸入，同時，上輪迭代的輸出也反饋至下輪的迭代中，最終產(chǎn)生輸出哈希值。海綿函數(shù)允許輸入長度和輸出長度都可變，具有靈活的性。海綿函數(shù)能夠用于設(shè)計哈希函數(shù)（固定輸出長度）、偽隨機數(shù)發(fā)生器，以及其他密碼函數(shù)。

?

以太坊使用的是一種名為Keccak的哈希算法。

可以說Keccak是SHA3正式批準前的名字，但正式批準的SHA3還是和Keccak有許多不一樣的地方，我們并不能認為SHA3和Keccak是完全對等的。

在以太坊中，常見的區(qū)塊哈希、交易哈希、狀態(tài)哈希等等都使用的Keccak256哈希算法。 256表示創(chuàng)建的信息指紋長度是256位，即32字節(jié)。當然以太坊也在慢慢向標準的SHA3算法靠攏，不管你是在開發(fā)DAPP還是做其他與要計算哈希值得工作，也建議你使用SHA3，除非你不得不做一些兼容性工作。在 Ether.js中同時提供了Keccak256和SHA256的哈希算法。同樣在Solidity中也內(nèi)置提供了Keccak256和SHA256，同大家靈活使用。

?

Keccak算法描述：

輸入數(shù)據(jù)沒有長度限制；

輸出哈希值的比特長度分為：224，256，384，512.

Keccak是一種被選定為SHA-3標準的單向散列函數(shù)算法。

Keccak可以生成任意長度的散列值，但為了配合SHA-2的散列值長度，SHA-3標準中規(guī)定了SHA3-224、SHA3-256、SHA3-384、SHA3-512這4種版本。在輸入數(shù)據(jù)的長度上限方面，SHA-1為2的64次方-1比特，SHA-2為2的128次方-1比特，而SHA-3則沒有長度限制。

?

（1）符號與函數(shù) Keccak算法使用以下符號與函數(shù)：

①符號

r：比特率 (比特rate)，其值為每個輸入塊的長度.

c：容量(capacity)，其長度為輸出長度的兩倍.

b：向量的長度， b = r + c，而 b的值依賴于指數(shù) I，即 b=25 * 2^l

②Keccak算法用到了5個函數(shù)： θ(theta)、ρ(rho)、π(pi)、χ(chi)、ι(iota)

（2）算法描述

Keccak算法對數(shù)據(jù)進行填充，然后迭代壓縮生成哈希值。

①填充

使填充后的數(shù)據(jù)長度為r的整數(shù)倍。因為迭代壓縮是對r位數(shù)據(jù)塊進行的，如果數(shù)據(jù)的長度不是r的整數(shù)倍，最后一塊數(shù)據(jù)將是短塊，這將無法處理。

設(shè)消息m長度為l比特。首先將比特“1”添加到m的末尾，再添加k個“0”，k是滿足下式的最小非負整數(shù)： l +1+ k = r-1 mod r ；然后再添加比特“1”添加到末尾。

?

②整體描述

Keccak算法采用海綿結(jié)構(gòu)(Sponge Construction)，在預(yù)處理（padding并分成大小相同的塊）后，海綿結(jié)構(gòu)主要分成兩部分：

吸入階段(Absorbing Phase)：將塊 xi傳入算法并處理。

擠出階段(Squeezing Phase)：產(chǎn)生一個固定長度的輸出。

?

Keccak算法的整體運算結(jié)構(gòu)如下圖

?

?③吸入與擠出階段

海綿結(jié)構(gòu)：輸入的數(shù)據(jù)進行填充之后，要經(jīng)過吸收階段和擠出階段，最終生成輸出的散列值。

①吸收階段

經(jīng)過填充的輸入消息按照每r比特為一組分割成若干個輸入分組；

將“內(nèi)部狀態(tài)的r比特”與“輸入分組1”進行XOR，將其結(jié)果作為“函數(shù)f的輸入值”；

反復(fù)執(zhí)行上述步驟，直到達到最后一個輸入分組。

函數(shù)f的作用是將輸入的數(shù)據(jù)進行復(fù)雜的攪拌操作并輸出結(jié)果，內(nèi)部狀態(tài)的初始值為0。

內(nèi)部狀態(tài)中有c個比特是不受輸入分組內(nèi)容直接影響的（但會通過函數(shù)f受到間接影響）。

②擠出階段

將“函數(shù)f的輸出值中的r個比特”保存為“輸出分組1”，并將整個輸出值（r+c個比特） ??????再次輸入到函數(shù)f中，

反復(fù)執(zhí)行上面的步驟，直到獲得所需長度的輸出數(shù)據(jù)。

兩個階段的函數(shù)f的邏輯本身是完全一樣的，每執(zhí)行一次，內(nèi)部狀態(tài)都會被攪拌一次。

容量c的意義在于防止將輸入消息中的一些特征泄露出去。

?

?

給定輸入串x，對x做padding，使其長度能被r整除，將padding后分割成長度為r的塊， 即x =x 0|| x1|| x2||...|| xt-1。然后執(zhí)行以下吸入階段和擠出階段：

①初始化一個長度為 r + c 比特的全零向量。

②輸入塊xi，將xi和向量的前r個比特做異或運算，然后輸入到f函數(shù)中處理。

③重復(fù)上一步，直至處理完x中的每個塊。

④輸出長為r的塊作為y0，并將向量輸入到f函數(shù)中處理，輸出y1，以此類推。得到的哈希序列，即為y = y 0 || y1|| y2 ||...|| yu 。在Keccak-224/256/384/512中，只需要在y0中取出前224/ 256/ 384/ 512位即可。

“||”符號表示比特串串聯(lián)。

?④壓縮函數(shù)

壓縮函數(shù)f是Keccak算法的核心，它包含n_r輪。

n_r的取值與計算b時用到的指數(shù)I ( b=25 * 25^l，向量長度b=r+c)有關(guān)，n_r =12+2* I。

Keccak-224/256/384/512中，取I=6， 因此n_r =24。

在每一輪中，要以此執(zhí)行五步，即 θ(theta)、ρ(rho)、π(pi)、 χ(chi)、ι(iota).

在處理過程中，把b=1600個比特排列成一個5*5* w的三維數(shù)組，w=2^I=64比特。

?

?（3）安全性與性能

安全性：可以抵御對哈希函數(shù)的所有現(xiàn)有攻擊；目前為止，沒有發(fā)現(xiàn)它有嚴重的安全弱點。靈活性：可選參數(shù)配置，能夠適應(yīng)哈希函數(shù)的各種應(yīng)用。

高效性：設(shè)計簡單，軟硬件實現(xiàn)方便，是高效的。

尚未廣泛應(yīng)用，需要經(jīng)過實踐檢驗

?

?

（五）SM3算法

SM3是我國商用密碼管理局頒布的商用密碼哈希函數(shù)

用途廣泛：

商用密碼應(yīng)用中的輔助數(shù)字簽名和驗證；

消息認證碼的生成與驗證；

隨機數(shù)的生成；

SM3在結(jié)構(gòu)上屬于基本壓縮函數(shù)迭代型的哈希函數(shù).

?

SM3算法描述：

輸入數(shù)據(jù)長度為l比特，1≤ l ≤264-1；

輸出哈希值的長度為256比特。

?

（1）常量與函數(shù)：SHA-256算法使用以下常數(shù)與函數(shù)：

①常量：

初始值IV=7380166f 4914b2b9 172442d7 da8a0600 a96f30bc 163138aa e38dee4d b0fb0e4e。

?

②函數(shù)：

布爾函數(shù)：

置換函數(shù)：

?∧表示按位“與”；∨表示按位“或”；?表示按位“補”；

⊕表示按位“異或”；<<<表示循環(huán)左移；

?

（2）算法描述

①填充

設(shè)消息m長度為l比特。添加比特“1”，再添加k個“0”，k是滿足下式的最小非負整數(shù)。l +1+ k = 448 mod 512。然后再添加一個64位比特串，該比特串是長度l的二進制表示。

?②消息擴展

③迭代壓縮處理

將填充后的消息m′按512比特分組： m′= B^(0) B^(1) … B^(n?1)，其中：n = ( l+ k+65)/512。

對m′按下列方式迭代壓縮：//外層迭代

FOR i = 0 TO n-1

V ^(i+1)= CF^( V(i) ，B^(i) )

ENDFOR

CF是壓縮函數(shù)，V ^(0)為256比特初始值IV，B^(i)為填充后的消息分組，迭代壓縮的結(jié)果為V^(n)，它為消息m的哈希值。

?④壓縮函數(shù)

令A(yù), B, C, D, E, F, G, H為字寄存器，SS1, SS2, TT1, TT2為中間變量。

壓縮函數(shù)： V^( i+1) = CF( V^(i)，B^(i)), 0 ≤i ≤ n -1。壓縮函數(shù)CF的壓縮處理：//內(nèi)層迭代

FOR j=0 TO 63

CF= F(SS1, SS2, TT1, TT2，A, B, C, D, E, F, G, H，Wj，W′ j ) //基本壓縮函數(shù)

ENDFOR

⑤基本壓縮函數(shù)F

⑥SM3工作全過程

⑦壓縮函數(shù)的作用

1.數(shù)據(jù)壓縮。

SM3的壓縮函數(shù)CF把每一個512位的消息分組B(i)壓縮成256位。經(jīng)過各數(shù)據(jù)分組之間的迭代處理后把l位的消息壓縮成256位的哈希值。

2.提供安全性。

在SM3的壓縮函數(shù)CF中，布爾函數(shù)FFj (X,Y,Z) 和GGj (X,Y,Z)是非線性函數(shù)，經(jīng)過循環(huán)迭代后提供混淆作用。置換函數(shù)P0(X)和P1(X)是線性函數(shù)，經(jīng)過循環(huán)迭代后提供擴散作用。加上壓縮函數(shù)CF中的其它運算的共同作用，壓縮函數(shù)CF具有很高的安全性，從而確保SM3具有很高的安全性

?

（3）安全性

專業(yè)機構(gòu)設(shè)計，經(jīng)過充分測試和論證；

安全性可滿足上述應(yīng)用的安全需求；

學者已開展對SM3的安全分析（如縮減輪的分析），尚未發(fā)現(xiàn)本質(zhì)的缺陷。

?

?

六、哈希函數(shù)構(gòu)造方法

構(gòu)造哈希函數(shù)原則：

（1）函數(shù)本身便于計算

（2）計算出來的地址分布均勻，以盡可能減少沖突。

在實際應(yīng)用中，構(gòu)造哈希函數(shù)要考慮以下五個因素：

（1）計算哈希函數(shù)所需要的時間。

（2）關(guān)鍵字的長度。關(guān)鍵字過長，我們可以考慮取關(guān)鍵的某幾位來建立哈希函數(shù)。

（3）哈希表的大小。哈希表過短，或者過長都會使哈希法性能降低。

（4）關(guān)鍵字分布情況。使key值和哈希函數(shù)計算出來的地址分布均勻。

（5）記錄查找的頻率。

?

1.直接定址法（極少用）

以數(shù)據(jù)元素關(guān)鍵字k本身或其線性函數(shù)作為哈希地址：H（k）=a*k+b；(a，b為常數(shù))。

僅適合于：地址集合的大小==關(guān)鍵字集合的大小，浪費空間太大。

?

2.數(shù)字分析法

數(shù)字分析法是取數(shù)據(jù)元素關(guān)鍵字中某些取值較均勻的數(shù)字位作為哈希地址的方法。假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字都是由s位數(shù)字組成(u1,u2,…,us)，分析關(guān)鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址。

只適合于所有關(guān)鍵字值已知的情況（能預(yù)先估計出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度）。通過分析分布情況把關(guān)鍵字取值區(qū)間轉(zhuǎn)化為一個較小的關(guān)鍵字取值區(qū)間。

第①②位都是8，1，第③位只可能取3、4，第⑧位只可能取2、5、7，因此這4位都不可取。由于中間的4位可看成是近乎隨機的，因此可取其中任意兩位，或取其中兩位與另外兩位的疊加求和后舍去進位作為哈希地址。

?

3.折疊法

折疊法是將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），然后取這幾部分的疊加和（舍去進位）。兩種疊加處理的方法：

①移位疊加：將分割后的幾部分低位對齊相加；

②邊界疊加：從一端沿分割界來回折疊，然后對齊相加。

適用于關(guān)鍵字位數(shù)較多，而且關(guān)鍵字中每一位上數(shù)字分布大致均勻的情況。

例如：采用折疊法構(gòu)造一個四位數(shù)的哈希函數(shù)，對關(guān)鍵字1234 5678進行存儲：

移位疊加：H(key) = 1234 + 5678 = 6912 ；邊界疊加： H(key) = 1234 + 8765 = 9999

?

4.平方取中法（常用）

先取關(guān)鍵字的平方，然后根據(jù)可使用空間的大小，選取平方數(shù)是中間幾位為哈希地址。哈希函數(shù)H(key)=“key2的中間幾位”。取的位數(shù)由表長決定。

原理：通過取平方擴大差別，平方值的中間幾位和這個數(shù)的每一位都相關(guān)，則對不同的關(guān)鍵字得到的哈希函數(shù)值不易產(chǎn)生沖突，由此產(chǎn)生的哈希地址也較為均勻。

適于：關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象。

?

5.減去法

減去法是數(shù)據(jù)的鍵值減去一個特定的數(shù)值以求得數(shù)據(jù)存儲的位置。

?

6.基數(shù)轉(zhuǎn)換法

將十進制數(shù)X看作其他進制，比如十三進制，再按照十三進制數(shù)轉(zhuǎn)換成十進制數(shù)，提取其中若干位作為X的哈希值。一般取大于原來基數(shù)的數(shù)作為轉(zhuǎn)換的基數(shù)，并且兩個基數(shù)應(yīng)該是互素的。

?

7.除留余數(shù)法（常用）

假設(shè)哈希表長為m，p為小于等于m的最大素數(shù)，則哈希函數(shù)為h（k）=k?mod p。p取≤m且最接近m的素數(shù)時，效果最好，且p最好取1.1n～1.7n之間的一個素數(shù)（n為存在的數(shù)據(jù)元素個數(shù)）。

若p選的不好，容易產(chǎn)生同義詞。一般情況下可以選擇p為質(zhì)數(shù)或者不包含小于20的質(zhì)因數(shù)的合數(shù)。

這是最常用的構(gòu)造哈希函數(shù)的方法，不僅可以對關(guān)鍵字直接取模，還可以對折疊、平方區(qū)中等運算之后取模。

?

?8.隨機數(shù)法

設(shè)定哈希函數(shù)為：H(key)=Random(key)其中，Random為偽隨機函數(shù)。

適于：對長度不等的關(guān)鍵字構(gòu)造哈希函數(shù)。

?

9．隨機乘數(shù)法（乘余取整法）

隨機乘數(shù)法使用一個隨機實數(shù)f，0≤f<1，乘積f*k的分數(shù)部分在0～1之間，用這個分數(shù)部分的值與n（哈希表的長度）相乘，乘積的整數(shù)部分就是對應(yīng)的哈希值，顯然這個哈希值落在0～n-1之間。其表達公式為：Hash(k)=「n*(f*k%1)」，其中f*k%1表示f*k的小數(shù)部分，即f*k%1?=?f*k-「f*k」。

優(yōu)點是對n的選擇不很關(guān)鍵。通常若地址空間為p位就是選n=2p。Knuth對常數(shù)f的取法做了仔細的研究，他認為f取任何值都可以，但某些值效果更好。如f=（-1）/2=0.6180329...比較理想。

?

10．字符串數(shù)值哈希法

把字符串的前10個字符的ASCII值之和對N取摸作為Hash地址，只要N較小，Hash地址將較均勻分布[0，N]區(qū)間內(nèi)。

對于N很大的情形，可使用ELFHash（ExecutableandLinkingFormat，ELF，可執(zhí)行鏈接格式）函數(shù)，它把一個字符串的絕對長度作為輸入，并通過一種方式把字符的十進制值結(jié)合起來，對長字符串和短字符串都有效，這種方式產(chǎn)生的位置可能不均勻分布。

?

11.旋轉(zhuǎn)法

旋轉(zhuǎn)法是將數(shù)據(jù)的鍵值中進行旋轉(zhuǎn)。旋轉(zhuǎn)法通常并不直接使用在哈希函數(shù)上，而是搭配其他哈希函數(shù)使用。

?

七、哈希沖突的解決方法

常用的主要有兩種方法解決沖突：

1.鏈接法（拉鏈法）

將所有關(guān)鍵字為同義詞的結(jié)點鏈接在同一個單鏈表中。

若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針組成的指針數(shù)組 T[0..m-1]。凡是散列地址為i的結(jié)點，均插入到以T[i]為頭指針的單鏈表中。

T中各分量的初值均應(yīng)為空指針。

在拉鏈法中，裝填因子α可以大于 1，但一般均取α ≤ 1。

2.開放定址法（再散列法）

當沖突發(fā)生時，使用某種探測技術(shù)在散列表中形成一個探測序列。沿此序列逐個單元地查找，直到找到給定的關(guān)鍵字，或者碰到一個開放的地址（即該地址單元為空）為止（若要插入，在探查到開放的地址，則可將待插入的新結(jié)點存人該地址單元）。查找時探測到開放的地址則表明表中無待查的關(guān)鍵字，即查找失敗。

按照形成探查序列的方法不同，可將開放定址法區(qū)分為線性探查法、二次探查法、雙重散列法等。

?

a.線性探查法

hi=(h(key)+?i?)％m ，0 ≤ i ≤ m-1

探查時從地址d開始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循環(huán)到T[0]，T[1]，…，直到探查到有空余地址或者到T[d-1]為止。

?

b.二次探查法

hi=(h(key)+?i*i?) ％ m，0 ≤ i ≤ m-1

探查時從地址d開始，首先探查T[d]，然后依次探查T[d+1^2]，T[d+2^2]，T[d+3^2]…，直到探查到有空余地址或者到T[d-1]為止。

缺點：無法探查到整個散列空間。

?

c.雙重散列法（最好的方法之一）

hi=(h(key)+?i*h1(key)?) ％ m，0 ≤ i ≤ m-1

探查時從地址d開始，首先探查T[d]，然后依次探查T[d+h1(d)]，T[d + 2*h1(d)]，…。

該方法使用了兩個散列函數(shù) h(key) 和 h1(key)，故也稱為雙散列函數(shù)探查法。

?

定義 h1(key) 的方法較多，但無論采用什么方法定義，都必須使h1(key)的值和m互素，才能使發(fā)生沖突的同義詞地址均勻地分布在整個表中，否則可能造成同義詞地址的循環(huán)計算。

?

3.再哈希法

同時構(gòu)造多個不同的哈希函數(shù)：Hi = RHi(key)
哈希地址H1 = RH1(key)差生沖突時，再計算H2 = RH2(key)…直到?jīng)_突不再產(chǎn)生。

?

4.建立公共溢出區(qū)

哈希表分為基本表和溢出表兩部分，凡是和基本表發(fā)生沖突的元素一律填入溢出表。

?

八、哈希結(jié)構(gòu)的缺點：

Hash索引結(jié)構(gòu)的特殊性，檢索效率非常高，可以一次定位，不像B-Tree 索引需要從根節(jié)點到枝節(jié)點，才能訪問到葉子節(jié)點，所以Hash索引的查詢效率要遠高于B-Tree索引。

那為什么不用Hash 索引而還要使用B-Tree索引呢？

?

由于Hash索引中存放的是經(jīng)過Hash計算之后的Hash值，而且Hash值的大小關(guān)系并不一定和Hash運算前的鍵值完全一樣，所以

（1）Hash索引僅僅能滿足“=”，“IN”和“<=>”查詢，不能使用范圍查詢。

（2）Hash索引無法被用來避免數(shù)據(jù)的排序操作。

（3）MySQL Hash索引不能利用部分索引鍵查詢。

Hash索引在計算Hash值的時候是組合索引鍵合并后再一起計算Hash值，所以通過組合索引的前面一個或幾個索引鍵進行查詢的時候，Hash索引也無法被利用。

?

（4）MySQL Hash索引在任何時候都不能避免表掃描。

Hash索引是將索引鍵通過Hash運算之后，將Hash運算結(jié)果的Hash值和所對應(yīng)的行指針信息存放于一個Hash表中，由于不同索引鍵存在相同Hash值，所以即使取滿足某個Hash鍵值的數(shù)據(jù)的記錄條數(shù)，也無法從 Hash 索引中直接完成查詢，還是要通過訪問表中的實際數(shù)據(jù)進行相應(yīng)的比較，并得到相應(yīng)的結(jié)果。

?

（5）MySQL Hash索引遇到大量Hash值相等的情況后性能并不一定就會比B-Tree索引高。

?

對于選擇性比較低的索引鍵，如果創(chuàng)建Hash索引，那么將會存在大量記錄指針信息存于同一個Hash值相關(guān)聯(lián)。這樣要定位某一條記錄時就會非常麻煩，會浪費多次表數(shù)據(jù)的訪問，而造成整體性能低下。

?

①哈希是以 key-value的形式存儲數(shù)據(jù)的，數(shù)據(jù)之間沒有順序，無法通過下標訪問數(shù)據(jù)。

②占的空間大，犧牲空間換取了效率

③當哈希表接近裝滿的狀態(tài)時，性能下降得非常嚴重；因為當哈希表空間不足時需要執(zhí)行擴容操作且擴容操作非常耗時。例如哈希表的長度是100，現(xiàn)在有第101個數(shù)要插入，這時，不僅哈希表的長度可能要擴展到150，且擴展之后所有的數(shù)都需要重新rehash。因此在設(shè)計哈希表時最好能夠提前預(yù)知數(shù)據(jù)量的大小。

?

?

九、常見攻擊方法：

1.窮舉攻擊

（a）原像攻擊和第二原像攻擊（Preimage or Second Preimage attack）

對于給定的哈希值h，試圖找到滿足H（x）=h的x

對于m位的哈希值，窮舉規(guī)模大約是2^m

（b）碰撞攻擊（Collision Resistance）

找到兩個信息x不等于y，滿足H(x) = H(y)

對于m位的哈希值，平均預(yù)計在2^(m/2)次嘗試后就找到兩個具有相同哈希值的數(shù)據(jù)。

（c）因此對于m位的哈希值，抗窮舉攻擊的強度為2^m/2：

目前128比特已經(jīng)不夠，需要160比特甚至更多

?

2.生日悖論birthday attack：

birthday attack是用來指一類暴力攻擊的名稱。即23人一組中的兩個或兩個以上的人共享同一個生日的概率大于1/2。?

如果某種函數(shù)，當供給一個隨機輸入時，返回k 個古典概型值中的一個，那么通過對不同輸入的函數(shù)反復(fù)評估，我們期望在約1.2 k^(1/2)。?獲得相同的輸出。對于上述生日悖論，用365替換k。

birthday attack常被用來發(fā)現(xiàn)哈希函數(shù)的碰撞。

?

?關(guān)于在提供數(shù)字簽名時使用哈希函數(shù)，Yuval 基于生日悖論提出了以下策略，其中n為消息摘要的長度：

1.攻擊者選擇Alice很可能要簽名的無害目標消息。

2.攻擊者生成2^(n/2)個無害消息（做一些小的編輯修改）的變體，所有變體都傳達相同的含義和對應(yīng)的信息摘要。。

3.根據(jù)生日悖論，無害消息的變化之一與目標消息的變化之一匹配的概率大于1/2。?

4.攻擊者然后在無害消息的變化上獲得Alice的簽名。

5.從無害消息中取出簽名，并附加到產(chǎn)生相同消息摘要的目標消息的變體中。

被攻擊者在沒有運用加密密鑰的情況下成功偽造了消息。

6.為了避免依賴于蠻力方法的攻擊，哈希函數(shù)的輸出必須足夠長。

?

3.字典攻擊：

如果用戶信息被“脫庫”，黑客雖然拿到是加密之后的密文，但可通過“猜”破解密碼，因為有些用戶密碼太簡單。就需維護一個常用密碼的字典表，把字典中的每個密碼用哈希算法計算哈希值，然后拿哈希值跟脫庫后的密文比對。如果相同，基本上就可以認為，這個加密之后的密碼對應(yīng)的明文就是字典中的這個密碼。（哈希算法存在散列沖突，也可能密文一樣，但明文不一樣）

可引入一個鹽（salt），跟用戶的密碼組合在一起，增加密碼的復(fù)雜度。拿組合后的字符串做哈希算法加密，存儲到數(shù)據(jù)庫，進一步增加破解的難度。

?

4.中間相遇攻擊：

攻擊者構(gòu)造一種消息從兩端向中間傳播的方式。在某些情況下主要的部分是通過猜測而得到的。如果某些消息值在中間不匹配，那么這個猜測的值是錯誤的并將會被丟棄。

中間相遇攻擊比較的是中間鏈接變量的值。攻擊者首先將偽造的消息分成兩部分處理。先把前一部分消息按照原來的算法進行計算，從而得到一個中間變量值，然后根據(jù)原先函數(shù)的哈希值向前計算，直到退回到消息中間分開處理的部分，這樣也會產(chǎn)生一個中間變量值。

中間相遇攻擊這種分析方法常常用來攻擊像IDEA ，AES等分組密碼算法。

?

?

?

十、哈希的應(yīng)用

常用應(yīng)用：哈希表、分布式緩存

1.哈希表（散列表）

哈希表是實現(xiàn)關(guān)聯(lián)數(shù)組（associative array）的一種數(shù)據(jù)結(jié)構(gòu)，廣泛應(yīng)用于實現(xiàn)數(shù)據(jù)的快速查找。

用哈希函數(shù)計算關(guān)鍵字的哈希值（hash value），通過哈希值這個索引就可以找到關(guān)鍵字的存儲位置，即桶（bucket）。哈希表不同于二叉樹、棧、序列的數(shù)據(jù)結(jié)構(gòu)一般情況下，在哈希表上的插入、查找、刪除等操作的時間復(fù)雜度是 O(1)。

查找過程中，關(guān)鍵字的比較次數(shù)，取決于產(chǎn)生沖突的多少，產(chǎn)生的沖突少，查找效率就高，產(chǎn)生的沖突多，查找效率就低。因此，影響產(chǎn)生沖突多少的因素，也就是影響查找效率的因素。

影響產(chǎn)生沖突多少有以下三個因素：

①哈希函數(shù)是否均勻；

②處理沖突的方法；

③哈希表的加載因子。

哈希表的加載因子和容量決定了在什么時候桶數(shù)（存儲位置）不夠，需要重新哈希。

?

加載因子太大的話桶太多，遍歷時效率變低；太大的話頻繁rehash，導致性能降低。所以加載因子的大小需要結(jié)合時間和空間效率考慮。

在 HashMap 中的加載因子為 0.75，即四分之三。

?

2.分布式緩存

網(wǎng)絡(luò)環(huán)境下的分布式緩存系統(tǒng)一般基于一致性哈希（Consistent hashing）。簡單的說，一致性哈希將哈希值取值空間組織成一個虛擬的環(huán)，各個服務(wù)器與數(shù)據(jù)關(guān)鍵字K使用相同的哈希函數(shù)映射到這個環(huán)上，數(shù)據(jù)會存儲在它順時針“游走”遇到的第一個服務(wù)器?？梢允姑總€服務(wù)器節(jié)點的負載相對均衡，很大程度上避免資源的浪費。

在動態(tài)分布式緩存系統(tǒng)中，哈希算法的設(shè)計是關(guān)鍵點。使用分布更合理的算法可以使得多個服務(wù)節(jié)點間的負載相對均衡，可以很大程度上避免資源的浪費以及部分服務(wù)器過載。 使用帶虛擬節(jié)點的一致性哈希算法，可以有效地降低服務(wù)硬件環(huán)境變化帶來的數(shù)據(jù)遷移代價和風險，從而使分布式緩存系統(tǒng)更加高效穩(wěn)定。

?

十一、BTC中哪些地方用到了哈希函數(shù)

1.BTC的數(shù)據(jù)結(jié)構(gòu)：

哈希指針：存儲地址和哈希值。

哈希指針的內(nèi)容是把整個區(qū)塊的內(nèi)容取哈希。

區(qū)塊鏈用哈希指針代替了普通的指針。一個哈希指針改變會影響其他哈希指針。

BTC根據(jù)這個性質(zhì)，只保存最近的幾個區(qū)塊哈希。如果需要找之前的區(qū)塊，可以用哈希指針找到正確的區(qū)塊。

Merkle tree的好處：只要記住根哈希就可以檢測出對樹中任何部位的修改。

?

2.挖礦難度的設(shè)置

比特幣區(qū)塊鏈系統(tǒng)采用的哈希算法是SHA256，故搜索空間的大小為2^256。

比特幣難度是對挖礦困難程度的度量，即指：計算符合給定目標的一個哈希值的困難程度。difficulty = difficulty_1_target / current_target difficulty_1_target的長度為256比特，前32位為0，后面全部為1，一般顯示為哈希值，

0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF difficulty_1_target表示BTC網(wǎng)絡(luò)最初的目標哈希。current_target是當前塊的目標哈希，先經(jīng) 過壓縮然后存儲在區(qū)塊中，區(qū)塊的哈希值必須小于給定的目標哈希值，表示挖礦成功。

?

3.數(shù)字簽名

比特幣需要利用公鑰進行加鎖，利用私鑰簽名進行解鎖，從而實現(xiàn)數(shù)字貨幣的交易。解鎖過程實際上是利用ECDSA算法的產(chǎn)生數(shù)字簽名。給定交易信息m，簽名過程如下：

①選擇一個隨機數(shù)k；

②計算點R = k*G= (xR, yR )，計算r = xR mod n；

③利用私鑰d計算s＝k-1 * (( H( m) - d * r)) mod n；

④輸入簽名( r, s)

?

十二、ETH中哪些地方用到了哈希函數(shù)

1.以太坊的數(shù)據(jù)結(jié)構(gòu)

block header中的數(shù)據(jù)結(jié)構(gòu)：

?parentHash：父區(qū)塊的哈希值，區(qū)塊鏈中前一個區(qū)塊的哈希值（前一個區(qū)塊塊頭的哈希值）

uncleHash：叔父區(qū)塊的哈希值

三棵樹的根哈希。Root是狀態(tài)樹的根哈希值，TxHash是交易樹的根哈希值（類似比特幣系統(tǒng)的根哈希值），ReceipHash是收據(jù)樹的根哈希值。

2.以太坊用戶地址的生成

第一步：生成私鑰 (private key)

產(chǎn)生的256比特隨機數(shù)做為私鑰(256比特=16進制32字節(jié))： 18e14a7b 6a307f42 6a94f811 4701e7c8 e774e7f9 a47e2c20 35db29a2 06321725

第二步：生成公鑰 (public key)

①將私鑰(32字節(jié))和橢圓曲線ECDSA-secp256k1計算公鑰(65字節(jié))(前綴04||X公鑰||Y公鑰)：

04 ||50863ad6 4a87ae8a 2fe83c1a f1a8403c b53f53e4 86d8511d ad8a0488 7e5b2352 || 2cd47024 3453a299 fa9e7723 7716103a bc11a1df 38855ed6 f2ee187e 9c582ba6

?

②利用Keccak-256算法計算公鑰的哈希值(32bytes)：

fc12ad81 4631ba68 9f7abe67 1016f75c 54c607f0 82ae6b08 81fac0ab eda21781

③取上一步結(jié)果取后20bytes即以太坊地址：

1016f75c54c607f082ae6b0881fac0abeda21781

?

第三步：輸?shù)刂?(address)：0x1016f75c54c607f082ae6b0881fac0abeda21781

?

3.以太坊的三棵樹：狀態(tài)樹、交易樹、收據(jù)樹

在以太坊的block header中，存在有三個根哈希值。

舉例：狀態(tài)樹，賬戶狀態(tài)組織成一個Merkle Tree。

?

以太坊區(qū)塊鏈系統(tǒng)使用了壓縮前綴Merkle樹(Merkle Patricia Tree,MPT)的結(jié)構(gòu)來存儲賬戶的狀態(tài)。因為以太坊區(qū)塊鏈賬戶的地址長度是固定的，且長度為160位二進制數(shù)，即40位16進制數(shù)。如果采用前綴樹的方式來存儲以太坊區(qū)塊鏈的賬戶，構(gòu)成的狀態(tài)樹的節(jié)點最多只有17個分支（16位十六進制的編碼?+ 一個結(jié)束標志位）。以太坊區(qū)塊鏈賬戶的查找效率只與狀態(tài)樹的高度有關(guān)。

當以太坊區(qū)塊鏈網(wǎng)絡(luò)中產(chǎn)生新的交易時，即使不同的礦工打包交易的順序不同，但是每個交易可按照其地址編碼去尋找對應(yīng)分支的葉子節(jié)點，所以當打包交易順序不同時，形成的前綴樹的根節(jié)點還是一樣的。

壓縮前綴Merkle樹使樹的高度變小，提高了查找賬戶的時間效率，并且從葉子節(jié)點向根節(jié)點去驗證壓縮前綴Merkle樹，便可以得到賬戶的狀態(tài)以及賬戶的余額。

?

根哈希值的用處：

1.防止篡改，只要根哈希值不變，整個樹的任何部分都沒辦法被篡改。

2.提供Merkle proof，可以證明賬戶余額，輕節(jié)點可以進行驗證。如何證明呢，你賬戶所在的分支，整個分支自己向上，作為Merkle proof發(fā)給輕節(jié)點，輕節(jié)點就可以驗證一下，你賬戶上有多少錢。

3.證明MPT中某個健值是不存在的，將它所在的分支作為merkle proof 發(fā)出去就可以證明它是否存在。

?

4.布隆過濾器(Bloom Filter)

以太坊區(qū)塊鏈系統(tǒng)提供了一個布隆過濾器(Bloom Filter)的數(shù)據(jù)結(jié)構(gòu)，它可以在一個大的集合中計算出一個非常緊湊的摘要信息，通過該摘要信息可以快速定位和驗證某一交易信息是否存在。

在該集合中，一開始先對所有元素的初值都賦值為0，當某一交易信息進行消息摘要后映射到該集合中的某一位置時，將該位置的信息賦值為1 ，表示交易存在。

弊端是存在哈希碰撞的可能。該位置的元素為1時，并不能說明某一交易一定存在，還需要進一步去檢查交易樹的信息，但是該數(shù)據(jù)結(jié)構(gòu)一定可以確定某一交易不存在，所以通過該性質(zhì)可以快速過濾一些無關(guān)的區(qū)塊。

因為存在哈希碰撞的可能,在刪除時可能把另一個交易的交易信息一起刪除，所以為了系統(tǒng)的穩(wěn)定，該數(shù)據(jù)結(jié)構(gòu)并不支持刪除操作。

在以太坊區(qū)塊鏈系統(tǒng)中每個收據(jù)都保存了一個布隆過濾器記錄用于交易類型、地址等信息。并且會在塊頭形成一個總的布隆過濾器的并集。

?

5.挖礦算法

在以太坊區(qū)塊鏈系統(tǒng)中有兩種不同大小的數(shù)組，較小的數(shù)組大概在16×10^6左右，稱之為緩存數(shù)組，主要的作用是用于輕節(jié)點去驗證交易的合法性以及生成礦工挖礦時需要保存的大的數(shù)組。

緩存數(shù)組的生成方式為：

①計算一個隨機種子的哈希值，得到緩存數(shù)組的第一個元素；

②通過數(shù)組的第一個元素計算哈希值得到該緩存數(shù)組的第二個元素；

③以此類推，直到整個數(shù)組的元素填充完成；

④數(shù)組每隔3000個區(qū)塊會進行一次更新操作。

工作量證明數(shù)組的生成方式為：

①計算一個偽隨機數(shù)的哈希值，得到對應(yīng)緩存數(shù)組中的元素的位置；

②按照偽隨機的順序，在緩存數(shù)組中進行256次查找得到256位的一個數(shù)；

③利用該數(shù)去計算哈希值，便可以得到工作量證明數(shù)組的第一個元素；

④后面的元素按照同樣的方式依次生成。

?

?

十三、超級賬本Fabric中哪些地方用到了哈希函數(shù)

1.私有數(shù)據(jù)機制

私有數(shù)據(jù)機制基于策略創(chuàng)建私有數(shù)據(jù)集合，從而定義同通道中具有權(quán)限的組織才可以訪問私有數(shù)據(jù)，而通道內(nèi)的其余組織只知道發(fā)生了這樣一筆交易，并不具備查看和操作私有數(shù)據(jù)的權(quán)限，因此并不知道此交易的具體內(nèi)容。

私有數(shù)據(jù)集合包括兩個部分。

A.私有數(shù)據(jù)實體：在具有權(quán)限的節(jié)點之間通過Gossip協(xié)議傳輸數(shù)據(jù)，并且存儲在這些節(jié)點的私有狀態(tài)數(shù)據(jù)庫中，可通過鏈碼API進行訪問。

B.私有數(shù)據(jù)的哈希值：這部分數(shù)據(jù)用于背書和排序時調(diào)用，最后存儲到通道內(nèi)每一個peer節(jié)點的賬本數(shù)據(jù)庫中，哈希值用于驗證私有數(shù)據(jù)的正確性和完整性。

?

私有數(shù)據(jù)在通道內(nèi)的傳輸流程可分為七步。

?