本節書摘來自華章計算機《區塊鍊開發指南》一書中的第3章，第3.1節,作者：申屠青春 主編 宋 波 張 鵬 汪曉明 季宙棟 左川民 編著更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。
hash函數是密碼學的一個重要分支，它是一種将任意長度的輸入變換為固定長度的輸出且不可逆的單向密碼體制。hash函數在數字簽名和消息完整性檢測等方面有着廣泛的應用。
3.1.1 技術原理
hash函數又稱為哈希函數、散列函數、雜湊函數。它是一種單向密碼體制，即一個從明文到密文的不可逆映射，隻有加密過程，沒有解密過程。
hash函數可以将滿足要求的任意長度的輸入進行轉換，進而得到固定長度的輸出。這個固定長度的輸出稱為原消息的散列值（hash value）或消息摘要（message digest）。hash函數的數學表述為：
其中，h是hash函數，沒m是任意長度明文，h是固定長度的hash值。
理想的hash函數對于不同的輸入可以獲得不同的hash值。如果是兩個不同的消息，存在，則稱x和x′是hash函數的一個碰撞。
由于hash函數這種單向的特征及長度固定的特征使得它可以生成消息或資料塊的消息摘要（也稱為散列值、哈希值），是以在資料完整性和數字簽名領域有着廣泛的應用。
典型的hash函數有兩類：消息摘要算法（md5）和安全雜湊演算法（sha）。
hash函數具有如下特點。
易壓縮：對于任意大小的輸入x，hash值的長度很小，在實際應用中，函數h産生的hash值其長度是固定的。
易計算：對于任意給定的消息，計算其hash值比較容易。
單向性：對于給定的hash值，要找到使得在計算上是不可行的，即求hash的逆很困難。
抗碰撞性：理想的hash函數是無碰撞的，但在實際算法的設計中很難做到這一點。有兩種抗碰撞性：一種是弱抗碰撞性，即對于給定的消息，要發現另一個消息，滿足在計算上是不可行的；另一種是強抗碰撞性，即對于任意一對不同的消息，使得在計算上也是不可行的。
高靈敏性：這是從比特位角度出發的，指的是1比特位的輸入變化會造成1/2的比特位發生變化。
3.1.2 sha-1算法
1993年美國國家标準技術研究所nist公布了安全雜湊演算法sha-0标準，1995年4月17日公布的修改版本稱之為sha-1。sha-1在設計方面很大程度上是模仿md5進行設計的，但它對任意長度的消息均是生成160位的消息摘要（md5僅僅生成128位的摘要），是以抗窮舉搜尋能力更強。它有5個參與運算的32位寄存器字，消息分組和填充方式與md5相同，主循環也同樣是四輪，但每輪要進行20次操作，包含非線性運算、移位和加法運算等，但非線性函數、加法常數和循環左移操作的設計與md5有一些差別。
sha-1的輸入是最大長度小于264位的消息，輸入消息以512位的分組為機關進行處理，輸出是160位的消息摘要。sha-1具有實作速度高、容易實作、應用範圍廣等優點，其算法描述如下。
1）對輸入的消息進行填充：經過填充後，消息的長度模512應與448同餘。填充的方式為第一位是1，餘下各位都為0。再将消息被填充前的長度以big-endian的方式附加在上一步留下的最後64位中。該步驟是必須的，即使消息的長度已經是所希望的長度。填充的長度範圍是1到512。
2）初始化緩沖區：可以用160位來存放hash函數的初始變量、中間摘要及最終摘要，但首先必須進行初始化，對每個32位的初始變量指派，即：
3）進入消息處理主循環，處理消息塊：一次處理512位的消息塊，總共進行4輪處理，每輪進行20次操作，如圖3-1所示。這4輪處理具有類似的結構，但每輪所使用的輔助函數和常數都各不相同。每輪的輸入均為目前處理的消息分組和緩沖區的目前值a、b、c、d、e，輸出仍放在緩沖區以替代舊的a、b、c、d、e的值。第四輪的輸出再與第一輪的輸入相加，以産生，其中加法是緩沖區5個字中的每個字與中相應的字模相加。
4）輸出：所有的消息分組都被處理完之後，最後一個分組的輸出即為得到的消息摘要值。
sha-1的步函數如圖3-2所示，它是sha-1最為重要的函數，也是sha-1中最關鍵的部件。
sha-1每運作一次步函數，a、b、c、d的值就會依次指派給b、c、d、e這幾個寄存器。同時，a、b、c、d、e的輸入值、常數和子消息塊在經過步函數運算後就會指派給。
其中，是步數，，是由目前512位長的分組導出的一個32位的字，kt是加法常量。
基本邏輯函數f的輸入是3個32位的字，輸出是一個32位的字，其函數表示如下。
其中∧、∨、-、⊕分别是與、或、非、異或4個邏輯運算符。
對于每個輸入分組導出的消息分組，前16個消息字即為消息輸入分組對應的16個32位字，其餘可按如下公式得到：
其中，表示左循環移位s位，如圖3-3所示。
此外，每輪中使用的不同消息常量，其具體數值為：
。
圖3-3 sha-1的80個消息字的産生過程
3.1.3 sha-2算法
2002年，nist推出sha-2系列hash算法，其輸出長度可取224位、256位、384位、512位，分别對應sha-224、sha-256、sha-384、sha-512。它還包含另外兩個算法：sha-512/224、sha-512/256。sha-2系列hash算法比之前的hash算法具有更強的安全強度和更靈活的輸出長度，其中sha-256是常用的算法。下面将對前四種算法進行簡單描述。
1.?sha-256算法
sha-256算法的輸入是最大長度小于264位的消息，輸出是256位的消息摘要，輸入消息以512位的分組為機關進行處理。算法描述如下。
（1）消息的填充
添加一個“1”和若幹個“0”使其長度模512與448同餘。在消息後附加64位的長度塊，其值為填充前消息的長度。進而産生長度為512整數倍的消息分組，填充後消息的長度最多為位。
（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步循環操作（如圖3-4所示）。每一輪的輸入均為目前處理的消息分組和得到的上一輪輸出的256位緩沖區a、b、c、d、e、
f、g、h的值。每一步中均采用了不同的消息字和常數，下面将給出它們的擷取方法。
圖3-4 sha-256的壓縮函數
（4）得出最終的hash值
所有512位的消息塊分組都處理完以後，最後一個分組處理後得到的結果即為最終輸出的256位的消息摘要。
步函數是sha-256中最為重要的函數，也是sha-256中最關鍵的部件。其運算過程如圖3-5所示。
且表示對32位的變量循環右移位。
的擷取方法是取前64個素數（2，3，5，7，……）立方根的小數部分，将其轉換為二進制，然後取這64個數的前64位作為。其作用是提供了64位随機串集合以消除輸入資料裡的任何規則性。
對于每個輸入分組導出的消息分組，前16個消息字直接按照消息輸入分組對應的16個32位字，其他的則按照如下公式來計算得出：
，
式中，表示對32位的變量右移位，其導出方法如圖3-6所示。
圖3-6 sha-256的64個消息字的生成過程
2.?sha-512算法
sha-512是sha-2中安全性能較高的算法，主要由明文填充、消息擴充函數變換和随機數變換等部分組成，初始值和中間計算結果由8個64位的移位寄存器組成。該算法允許輸入的最大長度是位，并産生一個512位的消息摘要，輸入消息被分成若幹個1024位的塊進行處理，具體參數為：消息摘要長度為512位；消息長度小于位；消息塊大小為1024位；消息字大小為64位；步驟數為80步。圖3-7顯示了處理消息、輸出消息摘要的整個過程，該過程的具體步驟如下。
1）消息填充：填充一個“1”和若幹個“0”，使其長度模1024與896同餘，填充位數為0-1023，填充前消息的長度以一個128位的字段附加到填充消息的後面，其值為填充前消息的長度。
2）連結變量初始化：連結變量的中間結果和最終結果都存儲于512位的緩沖區中，緩沖區用8個64位的寄存器a、b、c、d、e、f、g、h表示。初始連結變量也存儲于8個寄存器a、b、c、d、e、f、g、h中，其值為：
圖3-7 sha-512的整體結構
初始連結變量采用big-endian方式存儲，即字的最高有效位元組存儲于低位址位置。初始連結變量取自前8個素數的平方根的小數部分其二進制表示的前64位。
3）主循環操作：以1024位的分組為機關對消息進行處理，要進行80步循環操作。每一次疊代都把512位緩沖區的值a、b、c、d、e、f、g、h作為輸入，其值取自上一次疊代壓縮的計算結果，每一步計算中均采用了不同的消息字和常數。
4）計算最終的hash值：消息的所有個1024位的分組都處理完畢之後，第次疊代壓縮輸出的512位連結變量即為最終的hash值。
步函數是sha-512中最關鍵的部件，其運算過程類似sha-256。每一步的計算方程如下所示，b、c、d、f、g、h的更新值分别是a、b、c、e、f、g的輸入狀态值，同時生成兩個臨時變量用于更新a、e寄存器。
對于80步操作中的每一步t，使用一個64位的消息字，其值由目前被處理的1024位消息分組導出，導出方法如圖3-8所示。前16個消息字分别對應消息輸入分組之後的16個32位字，其他的則按照如下公式來計算得出：
圖3-8 sha-512的80個消息字生成的過程
其中，
式中，表示對64位的變量循環右移n位，表示對64位的變量右移位。
從圖3-8可以看出，在前16步進行中，的值等于消息分組中相對應的64位字，而餘下的64步操作中，其值是由前面的4個值計算得到的，4個值中的兩個要進行移位和循環移位操作。
的擷取方法是取前80個素數（2，3，5，7，……）立方根的小數部分，将其轉換為二進制，然後取這80個數的前64位作為，其作用是提供了64位随機串集合以消除輸入資料裡的任何規則性。
3.?sha-224與sha-384
1995年，美國國家标準與技術研究所（nist）公布了新的安全雜湊演算法sha-1，該算法替代了1993年頒布的hash函數标準算法sha；2001年，為了滿足更高的安全等級，nist又頒布了3個新的hash函數，即sha-256、sha-384和sha-512，hash值的長度分别為256位、384位和512位；2004年，又增加了sha-224。5種hash函數一起作為安全散列标準。
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相同，也是小于位，而且其分組的大小也是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.1.4 sha-3算法
由于md5、sha系列的hash函數遭受到了碰撞攻擊，nist在2005年10月31日到11月1日和2006年8月24日至25日舉辦了兩次hash函數研讨會，評估了hash函數目前的使用狀況，征求了公衆對hash函數的新準則。經過讨論之後，在2007年11月，nist決定通過公開競賽，以進階加密标準aes的開發過程為範例開發新的hash函數，新的hash算法被稱為sha-3，用于擴充包含sha-2算法在内的fips 180-3中的安全hash标準。截止到2008年10月31日，有64個算法送出到nist。2008年12月10日，nist宣布在這64個算法中有51個算法滿足對候選算法提出的可接受的最低标準，确定為第一輪的候選，并開始進行sha-3的第一輪競選。送出的第一輪候選算法公布在www.nist.gov/hash-competition上以用于公衆的評審。到2009年7月24日，第一輪的候選算法中剩下14個候選算法進入到第二輪的競選中，這14個第二輪的候選算法為blake、blue midnight wish、cubehash、echo、fugue、gr?stl、hamsi、jh、keccak、luffa、shabal、shavite-3、simd和skein。
nist于2010年8月23日至24日在加州大學聖塔芭芭拉分校舉行第二次sha-3候選會議。在2010年12月9日，nist宣布5個候選算法進入到第三輪，也是最後一輪的競選，這5個候選分别是：blake、gr?stl、jh、keccak和skein。其中，black使用haifa疊代架構，在壓縮函數中加入鹽和計數器，内部結構是局部寬管道結構；gr?stl和jh采用寬管道md結構，能抵抗一般的通用攻擊；keccak使用sponge函數；skein既可以使用疊代結構，也可以使用樹結構。nist在2012年評選出最終算法并産生了新的hash标準。keccak算法由于其較強的安全性和軟硬體實作性能，最終被選為新一代的标準hash算法，并被命名為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函數可建立從任意長度輸入到任意長度輸出的映射。
3.1.5 ripemd160算法
ripemd（race integrity primitives evaluation message digest），即race原始完整性校驗消息摘要，是比利時魯汶大學cosic研究小組開發的hash函數算法。ripemd使用md4的設計原理，并針對md4的算法缺陷進行改進，1996年首次釋出ripemd-128版本，它在性能上與sha-1相類似。
ripemd-160是對ripemd-128的改進，并且是ripemd中最常見的版本。ripemd-160輸出160位的hash值，對160位hash函數的暴力碰撞搜尋攻擊需要次計算，其計算強度大大提高。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位的目的。