Hash算法

定义

Hash （哈希或散列）算法是信息技术领域非常基础也非常重要的技术。它能任意长度的二进制值（明文）映射为较短的固定长度的二进制值（Hash 值），并且不同的明文很难映射为相同的 Hash 值。

$ echo "hello blockchain world, this is yeasy@github"|md5
89242549883a2ef85dc81b90fb606046
Hash 的核心思想十分类似于基于内容的编址或命名。

注：hash 值在应用中又被称为指纹（fingerprint）、摘要（digest）。
注：MD5 是一个经典的 hash 算法，其和 SHA-1 算法安全性不足应用于商业场景。

一个优秀的 hash 算法，将能实现：

正向快速：给定明文和 hash 算法，在有限时间和有限资源内能计算出 hash 值。
逆向困难：给定（若干） hash 值，在有限时间内很难（基本不可能）逆推出明文。
输入敏感：原始输入信息修改一点信息，产生的 hash 值看起来应该都有很大不同。
冲突避免：很难找到两段内容不同的明文，使得它们的 hash 值一致（发生冲突）。
冲突避免有时候又被称为“抗碰撞性”。如果给定一个明文前提下，难以找到碰撞的另一个明文，称为“弱抗碰撞性”；如果难以找到任意两个明文，发生碰撞，则称算法具有“强抗碰撞性”。

很多场景下，也要求对于任意长的输入内容，输出定长的 hash 结果。

安全散列算法SHA（Secure Hash Algorithm）是美国国家安全局 （NSA） 设计，美国国家标准与技术研究院（NIST） 发布的一系列密码散列函数，包括 SHA-1、SHA-224、SHA-256、SHA-384 和 SHA-512 等变体

SHA256

对任何长度的报文（就是你要加密的信息），它计算出来都是 一个 32个byte的 结果，可以称之为验证码。 等你拿到报文 和 验证码之后， 自己对报文进行SHA 256算法，把计算出的结果和收到的验证码比对，如果一样，就说明 报文在传输过程中没有被修改。
参考文档：http://blog.sina.com.cn/s/blog_d66494300102wz0z.html
处理信息最大为2的64次方的bit，输出信息按512 bit进行分组，为2的9次方bit的信息

step 1：补位

就是先在报文后面加一个 1，再加很多个0，直到长度 满足 mod 512=448.

为什么是448，因为448+64=512. 第二步会加上一个 64bit的 原始报文的 长度信息。

怎么补，在后面先补一个1，再一直补0知道符合条件，哪怕一开始就符合了，也要补

STEP2：附加长度值。

通常用一个64位的数据来表示原始消息的长度。如果消息长度不大于2^64，那么第一个字就是0
这即是处理信息不超过 2^64bit的原因

STEP3：使用常量

在SHA256算法中，用到64个常量，这些常量是对自然数中前64个质数的立方根的小数部分取前32bit而来。这64个常量如下：

        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：需要使用的函数

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,即一个word（字）为4个byte，32bit。
ROTR^2(x)是对x进行循环右移2位。

STEP5：需要使用的函数计算消息摘要

    基本思想：就是将消息分成N个512bit的数据块，哈希初值H(0)经过第一个数据块得到H（1），H（1）经过第二个数据块得到H（2），......，依次处理，最后得到H（N），然后将H（N）的8个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

注：这些初值是对自然数中前8个质数3、5、7、11等的平方根的小数部分取前32bit而来。

    II、 计算过程中用到的三种中间值
    1、64个32bit字的message schedule标记为w0、w1、…、w63。
    2、8个32bit字的工作变量标记为a、b、c、d、e、f、g。
    3、包括8个32bit字的哈希值标记为H(i)0、…、H(i)7。

这里kt叫做轮常数，wt叫做轮消息
　Kt是轮常数，每一轮的轮常数均不相同，用来使每轮的计算不同。这些常数获得方法如下：对前80个素数开立方根，取小数部分前64位。这些常数提供了64位随机串集合，可以初步消除输入数据中的统计规律。
III、 工作流程
原始消息分为N个512bit的消息块。每个消息块分成16个32bit的字标记为M(i)0、M(i)1、M(i)2、…、M(i)15然后对这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) 
第一步之后：一个512bit的信息，变成了64个32bit的信息，扩充了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

对N个消息块依次进行以上四步操作后将最后得到的H(N)0、H(N)1、H(N)2、…、H(N)7串联起来即可得到最后的256bit消息摘要。
它是如何保证最终是256bit的，因为每一轮的512bit信息，最终都通过H向后传递，永远都是256bit
至于这个算法为什么暂时看来很安全， I don‘t know

补充：

其他的hash算法有很多，如FNV hash算法等。
补充一致性hash算法，基本思想是hash环，优化点是虚拟节点解决少量节点时，不平衡的问题