SHA256算法原理及其实现

Posted on 2019-11-22 In 区块链 Views: Disqus:

学习区块链，总是无法避开各种加密算法，因为各种加密算法在实现区块链当中的各个环节都有着不可替代的作用。这里介绍一下在比特币挖矿以及merkle树当中被大量使用的鼎鼎大名的SHA256算法。

SHA-2 族算法简介

一个n位的哈希函数就是一个从任意长的消息到n位哈希值的映射，一个n位的加密哈希函数就是一个单向的、避免碰撞的n位哈希函数。这样的函数是目前在数字签名和密码保护当中极为重要的手段。

当前比较流行的哈希函数主要有128位的MD4和MD5和160位的SHA-1，今天介绍的SHA-2族有着更多位的输出哈希值，破解难度更大，能够提高更高的安全性。

SHA-2，名称来自于安全散列算法2（英语：Secure Hash Algorithm 2）的缩写，一种密码散列函数算法标准，由美国国家安全局研发，由美国国家标准与技术研究院（NIST）在2001年发布。属于SHA算法之一，是SHA-1的后继者。其下又可再分为六个不同的算法标准，包括了：SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。

这些变体除了生成摘要的长度、循环运行的次数等一些细微差异之外，基本结构是一致的。本文主要讲一讲SHA256。

SHA256原理详解

概述

对于任意长度的消息，SHA256都会产生一个256位的哈希值，称作消息摘要。这个摘要相当于是个长度为32个字节的数组，通常有一个长度为64的十六进制字符串来表示，其中1个字节=8位，一个十六进制的字符的长度为4位。

来看一个具体的例子：

1	BlockChain

这句话经过哈希函数SHA256后得到的哈希值为：

1	3a6fed5fc11392b3ee9f81caf017b48640d7458766a8eb0382899a605b41f2b9

总体上，SHA256与MD4、MD5以及HSA-1等哈希函数的操作流程类似，待哈希的消息在继续哈希计算之前首先要进行以下两个步骤：

对消息进行补位处理，是的最终的长度是512位的倍数，然后
以512位为单位对消息进行分块为 $M^{(1)},\,M^{(2)},...,M^{(N)}$

消息区块将进行逐个处理：从一个固定的初始哈希 $H^{(0)}$ 开始，进行以下序列的计算：

H^{(i)}=H^{(i-1)}+C_{M^{(i)} }(H^{(i-1)})

其中 $C$ 是SHA256的压缩函数， $+$ 是mod $2^{32}$ 加法，即将两个数字加在一起，如果对 $2^{32}$ 取余, $H^{(N)}$ 是消息区块的哈希值.

算法详细描述

SHA256的压缩函数主要对512位的消息区块和256位的中间哈希值进行操作，本质上，它是一个通过将消息区块为密钥对中间哈希值进行加密的256位加密算法。
因此，为了描述SHA256算法，有以下两方面的组件需要描述：

SHA256压缩函数
SHA256消息处理流程

以下的描述当中所使用到的标记如下：

$\oplus$ : 按位异或
$\wedge$ : 按位与
$\vee$ : 按位或
$\lnot$ : 补位
$+$ : 相加以后对 $2^{32}$ 求余
$R^n$ : 右移n位
$S^n$ : 循环右移n位

以上所有的操作都是针对32位字节.

常量初始化

初始哈希值 $H^{(0)}$ 取自自然数中前面8个素数(2,3,5,7,11,13,17,19)的平方根的小数部分, 并且取前面的32位. 下面举个例子:
$\sqrt{2}$ 小数部分约为0.414213562373095048, 而其中

0.414213562373095048 \approx 6*16^{-1}+a*16^{-2}+0*16^{-3}+...

于是, 质数2的平方根的小数部分取前32位就对应0x6a09e667.

如此类推, 初始哈希值 $H^{(0)}$ 由以下8个32位的哈希初值构成:

SHA256算法当中还使用到64个常数, 取自自然数中前面64个素数的立方根的小数部分的前32位, 如果用16进制表示, 则相应的常数序列如下:

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

消息预处理

在计算消息的哈希摘要之前需要对消息进行预处理:

对消息进行补码处理: 假设消息 $M$ 的二进制编码长度为 $l$ 位. 首先在消息末尾补上一位"1", 然后再补上 $k$ 个"0", 其中 $k$ 为下列方程的最小非负整数

l+1+k\equiv448 \mod 512

举个例子, 以消息"abc"为例显示补位的过程.

a,b,c对应的ASCII码和二进制编码分别如下:

原始字符    ASCII码    二进制编码
a          97         01100001
b          98         01100010
c          99         01100011

因此, 原始信息"abc"的二进制编码为:01100001 01100010 01100011, 第一步补位, 首先在消息末尾补上一位"1", 结果为: 01100001 01100010 01100011 1;
然后进行第二步的补位, 因为 $l=24$ , 可以得到 $k=423$ , 在第一步补位后的消息后面再补423个"0", 结果如下:

01100001 \, 01100010 \, 01100011 \,1\, \underbrace{00...0}_{423}

最后还需要在上述字节串后面继续进行补码, 这个时候补的是原消息"abc"的二进制长度 $l=24$ 的64位二进制表示形式, 补完以后的结果如下:

01100001 \, 01100010 \, 01100011 \,1\, \underbrace{00...0}_{423}\,\underbrace{00...011000}_{64}

最终补完以后的消息二进制位数长度是512的倍数.

这里需要注意的两点是不管原来的消息长度是多少, 即使长度已经满足对512取模后余数是448，补位也必须要进行，这时要填充512位. 另外, 考虑到最后要将消息长度 $l$ 转换为64位二进制编码, 因此, 长度的必须小于 $2^{64}$ , 绝大多数情况, 这个足够大了.

将补码处理后的消息以512位为单位分块为: $M^{(1)},\,M^{(2)},...,M^{(N)}$ , 其中第 $i$ 个消息块的前32位表示为: $M^{(i)}_0$ , 后面32位为: $M^{(i)}_1$ , 以此类推, 最后32位的消息块可表示为: $M^{(i)}_15$ . 我们采用Big endian约定对数据进行编码, 即认为第一个字节是最高位字节, 因此, 对于每一个32位字节, 最最左边的比特是最大的比特位.

摘要计算主循环

哈希计算算法如下:

$For\, i = 1 \to N$ $F o r i = 1 \to N$ ( $N$ $N$ = 补码后消息块个数)
- 用第个中间哈希值来对 $a,b,c,d,e,f,g,h$ 进行初始化, 当 $i=1$ 时, 就使用初始化哈希, 即:

应用SHA256压缩函数来更新 $a,b,...,h$ $a, b, . . ., h$
- $For\, j = 0 \to 63$ $F o r j = 0 \to 63$
  - 计算 $Ch(e,f,g), M_{aj}(a,b,c), \Sigma_0(a), \Sigma_1(e), W_j$ (具体定义如下)
计算第 $i$ 个中间哈希值 $H^{(i)}$

$H^{(N)}=(H^{(N)}_1,H^{(N)}_2,...,H^{(N)}_8)$ 为最终需要的哈希 $M$ 。

逻辑函数定义

SHA256算法当中所使用到的6个逻辑函数如下：每个函数都对32位字节进行操纵，并输出32位字节。

扩展消息块 $W_0, W_1, ..., W_{63}$ 通过以下方式进行计算：

$W_j=M^{(i)}_j \,for\,j=0,1,...,15$
$For \,j= 16\to 63$ $F o r j = 16 \to 63$
- $W_j\gets \sigma_1(W_{j-2})+W_{j-7}+\sigma_0(W_{j-15})+W_{j-16}$

图形表示

SHA256压缩函数的图形表示如下：

扩展消息块 $W$ 的求解算法可以表示如下：

SHA伪代码

Note 1: All variables are 32 bit unsigned integers and addition is calculated modulo 232
Note 2: For each round, there is one round constant k[i] and one entry in the message schedule array w[i], 0 ≤ i ≤ 63
Note 3: The compression function uses 8 working variables, a through h
Note 4: Big-endian convention is used when expressing the constants in this pseudocode,
    and when parsing message block data from bytes to words, for example,
    the first word of the input message "abc" after padding is 0x61626380

Initialize hash values:
(first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19):
h0 := 0x6a09e667
h1 := 0xbb67ae85
h2 := 0x3c6ef372
h3 := 0xa54ff53a
h4 := 0x510e527f
h5 := 0x9b05688c
h6 := 0x1f83d9ab
h7 := 0x5be0cd19

Initialize array of round constants:
(first 32 bits of the fractional parts of the cube roots of the first 64 primes 2..311):
k[0..63] :=
   0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
   0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
   0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
   0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
   0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
   0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
   0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
   0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2

Pre-processing (Padding):
begin with the original message of length L bits
append a single '1' bit
append K '0' bits, where K is the minimum number >= 0 such that L + 1 + K + 64 is a multiple of 512
append L as a 64-bit big-endian integer, making the total post-processed length a multiple of 512 bits

Process the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunk
    create a 64-entry message schedule array w[0..63] of 32-bit words
    (The initial values in w[0..63] don't matter, so many implementations zero them here)
    copy chunk into first 16 words w[0..15] of the message schedule array

    Extend the first 16 words into the remaining 48 words w[16..63] of the message schedule array:
    for i from 16 to 63
        s0 := (w[i-15] rightrotate  7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift  3)
        s1 := (w[i- 2] rightrotate 17) xor (w[i- 2] rightrotate 19) xor (w[i- 2] rightshift 10)
        w[i] := w[i-16] + s0 + w[i-7] + s1

    Initialize working variables to current hash value:
    a := h0
    b := h1
    c := h2
    d := h3
    e := h4
    f := h5
    g := h6
    h := h7

    Compression function main loop:
    for i from 0 to 63
        S1 := (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
        ch := (e and f) xor ((not e) and g)
        temp1 := h + S1 + ch + k[i] + w[i]
        S0 := (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
        maj := (a and b) xor (a and c) xor (b and c)
        temp2 := S0 + maj
 
        h := g
        g := f
        f := e
        e := d + temp1
        d := c
        c := b
        b := a
        a := temp1 + temp2

    Add the compressed chunk to the current hash value:
    h0 := h0 + a
    h1 := h1 + b
    h2 := h2 + c
    h3 := h3 + d
    h4 := h4 + e
    h5 := h5 + f
    h6 := h6 + g
    h7 := h7 + h

Produce the final hash value (big-endian):
digest := hash := h0 append h1 append h2 append h3 append h4 append h5 append h6 append h7

SHA256代码实现

下面是基于上述伪代码用go语言对SHA256进行的实现.

package main

import (
	"encoding/binary"
)

func wikiSha256(message []byte) [32]byte {
    //初始哈希值
	h0 := uint32(0x6a09e667)
	h1 := uint32(0xbb67ae85)
	h2 := uint32(0x3c6ef372)
	h3 := uint32(0xa54ff53a)
	h4 := uint32(0x510e527f)
	h5 := uint32(0x9b05688c)
	h6 := uint32(0x1f83d9ab)
	h7 := uint32(0x5be0cd19)
    
    //计算过程当中用到的常数
	k := [64]uint32{
                0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
		0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
		0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
		0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
		0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
		0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
		0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
		0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2}
    
	padded := append(message, 0x80)
	if len(padded) % 64 < 56 {
		suffix := make([]byte, 56 - (len(padded) % 64))
		padded = append(padded, suffix...)
	} else {
		suffix := make([]byte, 64 + 56 - (len(padded) % 64))
		padded = append(padded, suffix...)
	}
	msgLen := len(message) * 8
	bs := make([]byte, 8)
	binary.BigEndian.PutUint64(bs, uint64(msgLen))
	padded = append(padded, bs...)

	broken := [][]byte{};
    
	for i := 0; i < len(padded) / 64; i++ {
		broken = append(broken, padded[i * 64: i * 64 + 63])
	}
    
    //主循环
	for _, chunk := range broken {
		w := []uint32{}
        
		for i := 0; i < 16; i++ {
			w = append(w, binary.BigEndian.Uint32(chunk[i * 4:i * 4 + 4]))
		}
		w = append(w, make([]uint32, 48)...)
        
        //W消息区块处理
		for i := 16; i < 64; i++ {
			s0 := rightRotate(w[i - 15], 7) ^ rightRotate(w[i - 15], 18) ^ (w[i - 15] >> 3)
			s1 := rightRotate(w[i - 2], 17) ^ rightRotate(w[i - 2], 19) ^ (w[i - 2] >> 10)
			w[i] = w[i - 16] + s0 + w[i - 7] + s1
		}

		a := h0
		b := h1
		c := h2
		d := h3
		e := h4
		f := h5
		g := h6
		h := h7
        
        //应用SHA256压缩函数更新a,b,...,h
		for i := 0; i < 64; i++ {
			S1 := rightRotate(e, 6) ^ rightRotate(e, 11) ^ rightRotate(e, 25)
			ch := (e & f) ^ ((^e) & g)
			temp1 := h + S1 + ch + k[i] + w[i]
			S0 := rightRotate(a, 2) ^ rightRotate(a, 13) ^ rightRotate(a, 22)
			maj := (a & b) ^ (a & c) ^ (b & c)
			temp2 := S0 + maj

			h = g
			g = f
			f = e
			e = d + temp1
			d = c
			c = b
			b = a
			a = temp1 + temp2
		}
        
		h0 = h0 + a
		h1 = h1 + b
		h2 = h2 + c
		h3 = h3 + d
		h4 = h4 + e
		h5 = h5 + f
		h6 = h6 + g
		h7 = h7 + h
	}
	hashBytes := [][]byte{iToB(h0), iToB(h1), iToB(h2), iToB(h3), iToB(h4), iToB(h5), iToB(h6), iToB(h7)}
	hash := []byte{}
	hashArray := [32]byte{}
	for i := 0; i < 8; i ++ {
		hash = append(hash, hashBytes[i]...)
	}
	copy(hashArray[:], hash[0:32])
	return hashArray
}

func iToB(i uint32) []byte {
	bs := make([]byte, 4)
	binary.BigEndian.PutUint32(bs, i)
	return bs
}

//循环右移函数
func rightRotate(n uint32, d uint) uint32 {
	return (n >> d) | (n << (32 - d))
}