(转)比特币算法-SHA256算法介绍

SHA256是安全哈希算法SHA（Secure Hash Algorithm）系列算法之一。 它的摘要长度为256位，即32个字节，所以称为SHA256。 SHA系列算法是由美国国家安全局（NSA）设计，美国国家标准技术研究院（NIST）发布的一系列密码哈希函数，包括SHA-1、SHA-224、SHA-256、SHA-384和 SHA -512 等变体。

主要适用于数字签名标准（DigitalSignature Standard DSS）中定义的数字签名算法（Digital Signature Algorithm DSA）。 下面介绍计算消息摘要的算法原理。

对于任意长度的消息（按位计算）比特币算法，SHA256 都会生成一个 32 字节长度的数据，称为消息摘要。 当收到消息时，这个消息摘要可以用来验证数据是否发生了变化，即验证其完整性。 在传输过程中，数据很可能发生变化，此时会产生不同的消息摘要。

SHA算法具有以下特点：

1.无法从消息摘要中恢复信息；

2. 两条不同的消息不会产生相同的消息摘要。

一、术语和概念

(1)位(Bit)、字节(Byte)和字(Word)

SHA 始终将消息视为一串位。 在这篇文章中，一个“字”（Word）是32位，一个“字节”（Byte）是8位。 例如，字符串“abc”可以转换为位串：01100001 01100010 01100011。也可以表示为十六进制字符串：0x616263。

二、SHA256算法说明

(1) 更换

必须对信息进行填充，使其长度模512的余数为448。即（填充后的消息长度）Q2 = 448。即使长度满足，模512后的余数为448，也必须补码执行。

填充是这样进行的：先填充一个1，再填充一个0，直到长度满足取模512，余数为448。总而言之，填充是最少1位，最多512位。 以信息“abc”为例，说明填写过程。

原始信息：01100001 01100010 01100011

第一步填写：0110000101100010 01100011 1

先加个“1”

第二步填充：0110000101100010 01100011 10…..0

然后加上423“0”

我们可以将最后一个补码后的数据用十六进制写成如下

　　61626380 0000000000000000 00000000
　　00000000 0000000000000000 00000000
　　00000000 0000000000000000 00000000
　　00000000 00000000

现在，数据的长度是448，我们可以进行下一步。

(2) 补充长度

所谓补长就是在补完后的报文后面补上原数据的长度。 通常用一个64位的数据来表示原始报文的长度。 如果报文长度不大于2^64，那么首字为0，进行长度补码运算后，整条报文如下（十六进制格式）

　　61626380 0000000000000000 00000000
　　00000000 0000000000000000 00000000
　　00000000 0000000000000000 00000000
　　00000000 0000000000000000 00000018

(3) 使用的常量

在SHA256算法中，使用了64个常数，这些常数来源于自然数中前64个质数的立方根小数部分的前32位。 64个常量如下：

　　     428a2f98 71374491 b5c0fbcf e9b5dba5 
        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

(4) 使用的函数

　　    CH（x,y,z) = (x AND y) XOR ( (NOT x) AND z)  
        MAJ( x,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都是32位字符。

ROTR^2(x)是将x向右旋转2位。

(5) 计算消息摘要

基本思想：将报文分成N个512比特的数据块。 初始哈希值H(0)经过第一个数据块得到H(1)，H(1)经过第二个数据块得到H(2)。 ...，依次处理，最终得到H(N)，然后将H(N)的8个32bits连接成一个256bit的消息摘要

一、哈希初值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等的平方根小数部分的前32位。

二。 计算过程中用到的三个中间值

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。

三、 工作流程

将原始消息分为N个512bit的消息块。每个消息块分为16个32位的字，标记为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) 
         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)拼接得到最终的256bit消息)7 总结。

3、SHA算法安全吗？

2013年9月10日，美国约翰霍普金斯大学计算机科学教授、著名加密算法专家Matthew Green被NSA要求删除其有关破解加密算法的NSA相关博客。 同时，该博客在约翰霍普金斯大学服务器上的镜像也被要求删除。 但当记者向校方求证时，校方表示从未收到过NSA删除博客或镜像资料的要求，但记者在原网站上已找不到该博客。 幸运的是，该博客是从 Google 的缓存中找到的。 博客提到NSA每年花费2.5亿美元在解密信息上取得优势，并列举了NSA的一系列黑幕。 在 BitcoinTalk 上，出现了一轮争论：SHA256 安全吗？

一些被认为不安全的观点包括：

NSA搞的sha256，我们不信任NSA比特币算法，他们不可能不留后门。

棱镜事件已经明确告诉我们，政府会用一切可能的手段进行监控和解密。

虽然会研究SHA-2的人很多，而且目前还没有公开证据表明存在漏洞。 但不公开不代表不存在，因为发现漏洞的人一定更倾向于保守秘密为自己所用，而不是对外公布。

一些被认为安全的观点包括：

SHA-2 是一种广泛使用的算法，应该在实践中进行过测试。 美国的对手中国和俄罗斯都有很多杰出的数学家，如果有问题，他们一定想通了。 如果真的不安全，这个世界上安全的东西太少了，我不能活在恐惧中，所以我选择相信安全。