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

比特币算法——SHA256算法介绍
标签: 密码技术 sha256 消息摘要

SHA256是安全散列算法SHA(Secure Hash Algorithm)系列算法之一,其摘要长度为256bits,即32个字节,故称SHA256。SHA系列算法是美国国家安全局 (NSA) 设计,美国国家标准与技术研究院(NIST) 发布的一系列密码散列函数,包括 SHA-1、SHA-224、SHA-256、SHA-384 和 SHA-512 等变体。

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

对于任意长度(按bit计算)的消息,SHA256都会产生一个32个字节长度数据,称作消息摘要。当接收到消息的时候,这个消息摘要可以用来验证数据是否发生改变,即验证其完整性。在传输的过程中,数据很可能会发生变化,那么这时候就会产生不同的消息摘要。

SHA算法有如下特性:
  1. 不可以从消息摘要中复原信息;
2. 两个不同的消息不会产生同样的消息摘要。

  一、术语和概念

  (一)位(Bit),字节(Byte)和字(Word)

  SHA始终把消息当成一个位(bit)字符串来处理。本文中,一个“字”(Word)是32位,而一个“字节”(Byte)是8位。比如,字符串“abc”可以被转换成一个位字符串:01100001 01100010 01100011。它也可以被表示成16进制字符串:0x616263.

   二、SHA256算法描述

  (一)补位

  信息必须进行补位,以使其长度在对512取模以后的余数是448。也就是说,(补位后的消息长度)Q2 = 448。即使长度已经满足对512取模后余数是448,补位也必须要进行。

  补位是这样进行的:先补一个1,然后再补0,直到长度满足对512取模后余数是448。总而言之,补位是至少补一位,最多补512位。以信息“abc”为例显示补位的过程。
  
  原始信息:01100001 01100010 01100011

  补位第一步:0110000101100010 01100011 1

  首先补一个“1”

  补位第二步:0110000101100010 01100011 10…..0

  然后补423个“0”

  我们可以把最后补位完成后的数据用16进制写成下面的样子
  

  61626380 0000000000000000 00000000

  00000000 0000000000000000 00000000

  00000000 0000000000000000 00000000

  00000000 00000000

  
  现在,数据的长度是448了,我们可以进行下一步操作。

  (二)补长度

  所谓的补长度是将原始数据的长度补到已经进行了补位操作的消息后面。通常用一个64位的数据来表示原始消息的长度。如果消息长度不大于2^64,那么第一个字就是0。在进行了补长度的操作以后,整个消息就变成下面这样了(16进制格式)
  

  61626380 0000000000000000 00000000
  00000000 0000000000000000 00000000

  00000000 0000000000000000 00000000

  00000000 0000000000000000 00000018

  (三)使用的常量

  在SHA256算法中,用到64个常量,这些常量是对自然数中前64个质数的立方根的小数部分取前32bit而来。这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

  (四)需要使用的函数
  

      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的字。
ROTR^2(x)是对x进行循环右移2位。

  (五)计算消息摘要

基本思想:就是将消息分成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。

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) 
         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消息摘要。

三、SHA算法安全吗?

2013年9月10日美国约翰霍普金斯大学的计算机科学教授,知名的加密算法专家,Matthew Green被NSA要求删除他的一份关于破解加密算法的与NSA有关的博客。 同时约翰霍普金斯大学服务器上的该博客镜像也被要求删除。但当记者向该大学求证时,该校称从未收到来自NSA的要求要删除博客或镜像的资料,但记者却无法在原网址再找到该博客。幸运的是,从谷歌的缓存可以找到该博客。该博客提到NSA每年花费2.5亿美元来为自己在解密信息方面获取优势,并列举了NSA的一系列见不得人的做法。在BitcoinTalk上,已经掀起了一轮争论:到底SHA256是否安全?

部分认为不安全的观点包括:

NSA制造了sha256, 我们不相信NSA,他们不可能不留后门。
棱镜事件已经明白的告诉我们,政府会用一切可能的手段来监视与解密。
虽然有很多人会研究SHA-2,且目前没有公开的证据表明有漏洞。但没有公开这并不能代表就没有,因为发现漏洞的人一定更倾向于保留这个秘密来自己利用,而不是公布。
部分认为安全的观点包括:

SHA-2是应用广泛的算法,应该已经经历了实践的检验。 美国的对头中国和俄国都有很多杰出的数学家,如果有问题的话,他们肯定已经发现了。 如果真的不安全,世界上安全的东西就太少了,我不能生活在提心吊胆里,所以我选择相信安全。

相关文章
相关标签/搜索