量化投资技术文档

死磕密码学_SHA256算法-3

10分钟阅读

死磕密码学|SHA256算法 文章资料代码请查看 https://github.com/blockchainGuide/

文章有不对的地方，欢迎指正哦，觉得帮到您了，给个小关注，谢谢

u=1808440736,2594609531&fm=26&gp=0

SHA-256简介

SHA256是SHA-2下细分出的一种算法。

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

这些变体除了生成摘要的长度 、循环运行的次数等一些微小差异外，算法的基本结构是一致的。

说白了，它就是一个哈希函数。

哈希函数，又称散列算法，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（或哈希值）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。

对于任意长度的消息，SHA256都会产生一个256bit长的哈希值，称作消息摘要。

这个摘要相当于是个长度为32个字节的数组，通常用一个长度为64的十六进制字符串来表示

来看一个例子：

密码学

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

96a2193935d2cf4000cc4c499ac940c020b6cbfc161893c3ab8dacdb5ac007ad

SHA-256原理

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

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

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

image-20210201150647255

分别表示以下意思：

  • 按位异或
  • 按位与
  • 按位或
  • 补位
  • 相加以后对2^32^求余
  • 右移n位
  • 循环右移n位

常量初始化

初始哈希值H^(0)^取自自然数中前面 8 个素数(2,3,5,7,11,13,17,19)的平方根的小数部分, 并且取前面的 32 位.

下面举个例子:

小数部分约为0.414213562373095048, 而其中

image-20210201153212409

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

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

image-20210201151553600

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

消息预处理

SHA256算法中的预处理就是在想要Hash的消息后面补充需要的信息，使整个消息满足指定的结构。

信息的预处理分为两个步骤：附加填充比特和附加长度

①：附加填充比特

在报文末尾进行填充，使报文长度在对 512 取模以后的余数是 448

填充步骤：先补第一个比特为1，然后都补0，直到长度满足对 512 取模后余数是 448。

需要注意的是，信息必须进行填充，也就是说，即使长度已经满足对 512 取模后余数是 448，补位也必须要进行，这时要填充 512 个比特。

因此，填充是至少补一位，最多补 512 位。

例：以信息“abc”为例显示补位的过程。

a,b,c对应的ASCII码分别是97,98,99

于是原始信息的二进制编码为：01100001 01100010 01100011

补位第一步，首先补一个“1” ： 0110000101100010 01100011 1

补位第二步,补423个“0”：01100001 01100010 01100011 10000000 00000000 … 00000000

补位完成后的数据如下（为了简介用16进制表示）：

61626380 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000
1234

为什么是448?

因为在第一步的预处理后，第二步会再附加上一个64bit的数据，用来表示原始报文的长度信息。而448+64=512，正好拼成了一个完整的结构。

②：附加长度值

附加长度值就是将原始数据（第一步填充前的消息）的长度信息补到已经进行了填充操作的消息后面。

wiki百科中给出的原文是：append length of message (before pre-processing), in bits, as 64-bit big-endian integer

SHA256用一个 64 位的数据来表示原始消息的长度。

因此，通过SHA256计算的消息长度必须要小于，当然绝大多数情况这足够大了。

长度信息的编码方式为64-bit big-endian integer

消息“abc”，3 个字符，占用 24 个bit

因此，在进行了补长度的操作以后，整个消息就变成下面这样了（16进制格式）

61626380 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000018

逻辑运算

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

image-20210201154213124

计算消息摘要

哈希计算的算法如下面几张图所示：

image-20210201154731788

image-20210201154804170

image-20210201154827524

基于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

代码参考： https://github.com/blockchainGuide/

参考

https://mindcarver.cn

https://github.com/blockchainGuide/

http://www.iwar.org.uk/comsec/resources/cipher/sha256-384-512.pdf

https://link.zhihu.com/?target=https%3A//zh.wikipedia.org/wiki/SHA-2

https://zhuanlan.zhihu.com/p/94619052

关系图谱