区块链中的密码学（1）：散列算法 SHA256算法分析与实现 - BlockAA/blockchain-courses GitHub Wiki
在很多技术人员的眼中，区块链并不是一种新的技术，而是过去很多年计算机技术的组合运用。而在这个方方面面技术的运用上，基于密码学的加密算法可以说是区块链各种特点得以表现的根本，一旦目前使用的加密算法被证实可以破解，那么现有的区块链技术很有可能土崩瓦解。本文所要讲述的就是目前区块链中运用最广的加密算法：SHA256。
SHA是一个密码散列函数家族，是英文Secure Hash Algorithm的缩写。由美国国家安全局（NSA）所设计，并由美国国家标准与技术研究院（NIST）发布。本文的主角SHA256算法就是这个家族中的一员。在此之前的SHA0，SHA1都被证明是可以破解的，目前SHA2以及SHA3尚未被证实可以破解。这里引申一下，在密码学的定义中，所谓可以破解，即是计算复杂度少于暴力破解所需要的计算复杂度。SHA256中的256取的这种算法的摘要长度。下面会具体讲一下SHA256的实现原理。
SHA256算法的设计思路主要是依赖于一个优秀的HASH散列算法的特点：任何微小的输入都有可能对输出产生巨大的影响，以及HASH算法极低的碰撞概率。
常量定义：
SHA256算法中首先规定了8个哈希初值和64个哈希常量。8个哈希初值取的是自然数中前8个质数（2,3,5,7,11,13,17,19）的平方根的小数部分的前32bit的值。例如：
取小数部分：0.414213562373095048（用16进制表示）= 6\times16^{-1}+a\times16^{-2}+0\times16^{-3}+...
所以8个哈希初值的第一个可以表示为： h0 : = 0X6a09e667。最终取到的8个哈希初值分别是：
H0= 0x6a09e667
H1 = 0xbb67ae85
H2 = 0x3c6ef372
H3 = 0xa54ff53a
H4 = 0x510e527f
H5 = 0x9b05688c
H6 = 0x1f83d9ab
H7 = 0x5be0cd19
在看前面8个哈希初值的定义，64个哈希常量的定义是取自然数中前64个质数的立方根的小数部分的前32bit的值。这里就不贴出来了，了解定义即可。细心的读者应该能发现，8个哈希初值，每个32位，总长度对应的就是SHA256算法的最后结果的长度。
逻辑函数定义：
SHA256算法定义了6中逻辑函数，这6个逻辑函数的作用这里先简单了解，后续的代码部分会看到如何使用。
备注： AND 表示”与“运算，NOT 表示：”或“运算，XOR 表示”异或“运算。ROTR^2（X）表示对X进行循环右移两位，SHR^3（X）表示对X右移三位。函数的输入都是32bit的字。
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)
算法过程:
补位：
补位的目的是为了使消息长度满足： （消息原始长度+1+K） mod 512 = 448 这个公式。为什么是448，目的是为了后续留有64位的长度来表示消息的长度，SHA256支持的消息长度是不大于2的64次方。1表示补位第一步补的一个位，K表示需要补的0的个数。补位的第一步是不管消息长度多少（即使对512去模等于448），都在末尾补一个1。
假设原始消息是这样： 01111101 01110000 11110000 00000001
补位第一步后的消息： 01111101 01110000 11110000 00000001 1
根据上面的解释很容易算出需要补 415个0。
补长度：
补充的长度一般是固定的64bit，用来表示消息的初始长度。上面输入的长度是32位，转换成16进制是100000。所以将会把100000补在上面的消息后面，不足64位用0补。
计算过程：
整体思路：把消息分成大小512bit的N份，取第一个数据块的数据，分成16份32bit的数组。最开始的8个哈希初值H(0)经过第一个消息块数据运算得到H(1),经过第二个消息块数据运算得到H(2)，一次循环，直到得到H(N),就是最后得到的信息摘要。
详细过程如下：
1）首先使用一个256-bit 的缓存来存放该散列函数的中间及最终结果。我们前面提到SHA256中定义了8个初始值，这8个初始值用a,b,c,d,e,f,g,h表示：
a=0x6a09e667, b=0xbb67ae85,
c=0x3c6ef372, d=0xa54ff53a,
e=0x510e527f, f=0x9b05688
c, g=0x1f83d9ab, h=0x5be0cd19。
2）把补长过的消息进行拆分成N个512bit数据。首先计算函数的外部有个大的循环，形如： For i =1 to N;
3 ) 在每一次的循环里，需要给函数W(t)的输入t为0到63的结果赋值，即W(0),W(1),W(2)...W(63)。其中W(0)到W(15)的值为当前快消息被拆分的16个值（前面提到的每个块分成16个32bit的数据）。然后W(16)到W（63）取的值为依赖前面16个值产生，具体算法如下 ：
For t = 0 to 15
Wt = M(i)t //赋值W（t）的前16个值
For t = 16 to 63
Wt = SSIG1(W(t-2)) + W(t-7) + SSIG0(w(t-15)) + W(t-16) //利用W（t）前面的16个值计算后面的值
4）利用第三步取到的W(t)的64个值，进行64次循环，打乱原有的顺序。过程中有一些中间变量，但是目的是为了重新给a,b,c,d,e,f,g,h赋值。代码过程：
For t = 0 to 63
T1 = h + BSIG1(e) + CH(e,f,g) + Kt + Wt //这里的Wt就是在文章开头定义的64个哈希常量。
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
可以看到，利用之前介绍的逻辑函数和第三步的运算结果，重新计算了a,b,c,d,e,f,g,h的值。
5） 最后一步就是根据第四步重新赋值的8个变量得出这个块的SHA256结果。
通过上一步的H(i-1)0到H(i-1)7的值计算H(i)0到H(i)7的值。
H(i)0 = a + H(i-1)0 //a是一个32bit的值，H（i-1）0也是一个32bit的值
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
到这里，第一次循环就结束了，还记得之前提过的”外部有个大的循环，形如： For i =1 to N “ 吗？在SHA256中，消息的长度越长，循环的次数也越多。经过N此循环得到H(N)0,H(N)1,H(N)2,...H(N)7，8个32位的数拼接起来就形成了SHA256算法的最终结果：一个长度为256位的消息摘要。
在比特币中，SHA256运用在了钱包地址的产生，也是实现pow共识机制的主要手段。就目前来说，2的256次方近似于10的77次方，10的77次方有多大？到目前为止，人类可观测的宇宙中的原子数约为10的80次方，这种数量级的散列算法想要通过碰撞来攻击基本是不可能的。这也是目前为什么SHA256算法得到普遍应用的原因之一。
本文首发于blockgeek.org
BG论坛思考题
按照惯例，为大家随机挑选一条Blockgeek.org上的技术问题，有兴趣的同学可以挑战一下，来吧，别犹豫！
作者简介
Figo：Blockgeek.org 签约技术作者，区块链重度爱好者。热衷于区块链技术推广，参与hyperledger fabric中文社区翻译，对以太坊，EOS，HPB,星云等各大公链有深入研究。