定義

Hash （哈希或散列）算法是信息技術(shù)領(lǐng)域非?；A(chǔ)也非常重要的技術(shù)。它能任意長(zhǎng)度的二進(jìn)制值（明文）映射為較短的固定長(zhǎng)度的二進(jìn)制值（Hash 值），并且不同的明文很難映射為相同的 Hash 值。

$ echo "hello blockchain world, this is yeasy@github"|md5
89242549883a2ef85dc81b90fb606046
Hash 的核心思想十分類(lèi)似于基于內(nèi)容的編址或命名。

注：hash 值在應(yīng)用中又被稱(chēng)為指紋（fingerprint）、摘要（digest）。
注：MD5 是一個(gè)經(jīng)典的 hash 算法，其和 SHA-1 算法安全性不足應(yīng)用于商業(yè)場(chǎng)景。

一個(gè)優(yōu)秀的 hash 算法，將能實(shí)現(xiàn)：

正向快速：給定明文和 hash 算法，在有限時(shí)間和有限資源內(nèi)能計(jì)算出 hash 值。
逆向困難：給定（若干） hash 值，在有限時(shí)間內(nèi)很難（基本不可能）逆推出明文。
輸入敏感：原始輸入信息修改一點(diǎn)信息，產(chǎn)生的 hash 值看起來(lái)應(yīng)該都有很大不同。
沖突避免：很難找到兩段內(nèi)容不同的明文，使得它們的 hash 值一致（發(fā)生沖突）。
沖突避免有時(shí)候又被稱(chēng)為“抗碰撞性”。如果給定一個(gè)明文前提下，難以找到碰撞的另一個(gè)明文，稱(chēng)為“弱抗碰撞性”；如果難以找到任意兩個(gè)明文，發(fā)生碰撞，則稱(chēng)算法具有“強(qiáng)抗碰撞性”。

很多場(chǎng)景下，也要求對(duì)于任意長(zhǎng)的輸入內(nèi)容，輸出定長(zhǎng)的 hash 結(jié)果。

安全散列算法SHA（Secure Hash Algorithm）是美國(guó)國(guó)家安全局 （NSA） 設(shè)計(jì)，美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院（NIST） 發(fā)布的一系列密碼散列函數(shù)，包括 SHA-1、SHA-224、SHA-256、SHA-384 和 SHA-512 等變體

SHA256

對(duì)任何長(zhǎng)度的報(bào)文（就是你要加密的信息），它計(jì)算出來(lái)都是 一個(gè) 32個(gè)byte的 結(jié)果，可以稱(chēng)之為驗(yàn)證碼。 等你拿到報(bào)文 和 驗(yàn)證碼之后， 自己對(duì)報(bào)文進(jìn)行SHA 256算法，把計(jì)算出的結(jié)果和收到的驗(yàn)證碼比對(duì)，如果一樣，就說(shuō)明 報(bào)文在傳輸過(guò)程中沒(méi)有被修改。
參考文檔：http://blog.sina.com.cn/s/blog_d66494300102wz0z.html
處理信息最大為2的64次方的bit，輸出信息按512 bit進(jìn)行分組，為2的9次方bit的信息

step 1：補(bǔ)位

就是先在報(bào)文后面加一個(gè) 1，再加很多個(gè)0，直到長(zhǎng)度 滿(mǎn)足 mod 512=448.

為什么是448，因?yàn)?48+64=512. 第二步會(huì)加上一個(gè) 64bit的 原始報(bào)文的 長(zhǎng)度信息。

怎么補(bǔ)，在后面先補(bǔ)一個(gè)1，再一直補(bǔ)0知道符合條件，哪怕一開(kāi)始就符合了，也要補(bǔ)

STEP2：附加長(zhǎng)度值。

通常用一個(gè)64位的數(shù)據(jù)來(lái)表示原始消息的長(zhǎng)度。如果消息長(zhǎng)度不大于2^64，那么第一個(gè)字就是0
這即是處理信息不超過(guò) 2^64bit的原因

STEP3：使用常量

在SHA256算法中，用到64個(gè)常量，這些常量是對(duì)自然數(shù)中前64個(gè)質(zhì)數(shù)的立方根的小數(shù)部分取前32bit而來(lái)。這64個(gè)常量如下：

        3956c25b 59f111f1 923f82a4 ab1c5ed5 
        d807aa98 12835b01 243185be 550c7dc3 
        72be5d74 80deb1fe 9bdc06a7 c19bf174 
        e49b69c1 efbe4786 0fc19dc6 240ca1cc 
        2de92c6f 4a7484aa 5cb0a9dc 76f988da 
        983e5152 a831c66d b00327c8 bf597fc7 
        c6e00bf3 d5a79147 06ca6351 14292967 
        27b70a85 2e1b2138 4d2c6dfc 53380d13 
        650a7354 766a0abb 81c2c92e 92722c85 
        a2bfe8a1 a81a664b c24b8b70 c76c51a3 
        d192e819 d6990624 f40e3585 106aa070 
        19a4c116 1e376c08 2748774c 34b0bcb5  
        391c0cb3 4ed8aa4a 5b9cca4f 682e6ff3 
        748f82ee 78a5636f 84c87814 8cc70208 
        90befffa a4506ceb bef9a3f7 c67178f2

STEP4：需要使用的函數(shù)

CH（x, y, z) = (x AND y) XOR ( (NOT x) AND z)
MAJ( x, y, z) = (x AND y) XOR (x AND z) XOR (y AND z)
BSIG0(x) = ROTR^2(x) XOR ROTR^13(x) XOR ROTR^22(x)
BSIG1(x) = ROTR^6(x) XOR ROTR^11(x) XOR ROTR^25(x)
SSIG0(x) = ROTR^7(x) XOR ROTR^18(x) XOR SHR^3(x)
SSIG1(x) = ROTR^17(x) XOR ROTR^19(x) XOR SHR^10(x)
其中x、y、z皆為32bit的word,即一個(gè)word（字）為4個(gè)byte，32bit。
ROTR^2(x)是對(duì)x進(jìn)行循環(huán)右移2位。

STEP5：需要使用的函數(shù)計(jì)算消息摘要

    基本思想：就是將消息分成N個(gè)512bit的數(shù)據(jù)塊，哈希初值H(0)經(jīng)過(guò)第一個(gè)數(shù)據(jù)塊得到H（1），H（1）經(jīng)過(guò)第二個(gè)數(shù)據(jù)塊得到H（2），......，依次處理，最后得到H（N），然后將H（N）的8個(gè)32bit連接成256bit消息摘要
    I、哈希初值H（0）
    SHA256算法中用到的哈希初值H（0）如下
    H(0)0 = 6a09e667 
    H(0)1 = bb67ae85  
    H(0)2 = 3c6ef372 
    H(0)3 = a54ff53a 
    H(0)4 = 510e527f 
    H(0)5 = 9b05688c 
    H(0)6 = 1f83d9ab 
    H(0)7 = 5be0cd19

注：這些初值是對(duì)自然數(shù)中前8個(gè)質(zhì)數(shù)3、5、7、11等的平方根的小數(shù)部分取前32bit而來(lái)。

    II、 計(jì)算過(guò)程中用到的三種中間值
    1、64個(gè)32bit字的message schedule標(biāo)記為w0、w1、…、w63。
    2、8個(gè)32bit字的工作變量標(biāo)記為a、b、c、d、e、f、g。
    3、包括8個(gè)32bit字的哈希值標(biāo)記為H(i)0、…、H(i)7。

這里kt叫做輪常數(shù)，wt叫做輪消息
　Kt是輪常數(shù)，每一輪的輪常數(shù)均不相同，用來(lái)使每輪的計(jì)算不同。這些常數(shù)獲得方法如下：對(duì)前80個(gè)素?cái)?shù)開(kāi)立方根，取小數(shù)部分前64位。這些常數(shù)提供了64位隨機(jī)串集合，可以初步消除輸入數(shù)據(jù)中的統(tǒng)計(jì)規(guī)律。
III、 工作流程
原始消息分為N個(gè)512bit的消息塊。每個(gè)消息塊分成16個(gè)32bit的字標(biāo)記為M(i)0、M(i)1、M(i)2、…、M(i)15然后對(duì)這N個(gè)消息塊依次進(jìn)行如下處理

        For i=1 to N

       1）   For t = 0 to 15 
                        Wt = M(i)t 
                For t = 16 to 63 
                        Wt = SSIG1(W(t-2)) + W(t-7) + SSIG0(t-15) + W(t-16) 
第一步之后：一個(gè)512bit的信息，變成了64個(gè)32bit的信息，擴(kuò)充了4倍

         2）  a = H(i-1)0 
                b = H(i-1)1 
                c = H(i-1)2 
                d = H(i-1)3 
                e = H(i-1)4 
                f = H(i-1)5 
                g = H(i-1)6 
                h = H(i-1)7
         3）For t = 0 to 63 
                    T1 = h + BSIG1(e) + CH(e,f,g) + Kt + Wt 
                    T2 = BSIG0(a) + MAJ(a,b,c) 
                    h = g
                    g = f 
                    f = e 
                    e = d + T1 
                    d = c 
                    c = b 
                    b = a 
                    a = T1 + T2
 
           4）H(i)0 = a + H(i-1)0 
                 H(i)1 = b + H(i-1)1 
                 H(i)2 = c + H(i-1)2 
                 H(i)3 = d + H(i-1)3 
                 H(i)4 = e + H(i-1)4 
                 H(i)5 = f + H(i-1)5  
                 H(i)6 = g + H(i-1)6 
                 H(i)7 = h + H(i-1)7

對(duì)N個(gè)消息塊依次進(jìn)行以上四步操作后將最后得到的H(N)0、H(N)1、H(N)2、…、H(N)7串聯(lián)起來(lái)即可得到最后的256bit消息摘要。
它是如何保證最終是256bit的，因?yàn)槊恳惠喌?12bit信息，最終都通過(guò)H向后傳遞，永遠(yuǎn)都是256bit
至于這個(gè)算法為什么暫時(shí)看來(lái)很安全， I don‘t know

補(bǔ)充：

其他的hash算法有很多，如FNV hash算法等。
補(bǔ)充一致性hash算法，基本思想是hash環(huán)，優(yōu)化點(diǎn)是虛擬節(jié)點(diǎn)解決少量節(jié)點(diǎn)時(shí)，不平衡的問(wèn)題