[区块链]加密算法——Hash算法（进阶）
为了为保证存储于区块链中的信息的安全与完整，区块链中使⽤了包含密码哈希函数和椭圆曲线公钥密码技术在内的⼤量的现代密码学技术，同时，这些密码学技术也被⽤于设计基于⼯作量证明的共识算法并识别⽤户。
在前边的⽂章中已经系统的讲述了密码学中的哈希算法，在本节，将会给⼤家介绍Hash算法在区块链中的应⽤！
概念回顾：
哈希函数：是⼀类数学函数，可以在有限合理的时间内，将任意长度的消息压缩为固定长度的⼆进制串，其输出值称为哈希值，也称为散列值。
以哈希函数为基础构造的哈希算法，在现代密码学中扮演着重要的⾓⾊，常⽤于实现数据完整性和实体认证，同时也构成多种密码体制和协议的安全保障。
碰撞是与哈希函数相关的重要概念，体现着哈希函数的安全性，所谓碰撞是指两个不同的消息在同⼀个哈希函数作⽤下，具有相同的哈希值。
哈希函数的安全性是指在现有的计算资源（包括时间、空间、资⾦等）下，到⼀个碰撞是不可⾏的。
区块链中的加密算法······即将开始！
噔噔、噔···噔···！
⽐特币中的加密算法：
在⽐特币系统中使⽤了两个密码学Hash函数，⼀个是SHA256 和 RIPEMD160。
其中：RIPEMD160主要⽤于⽣成⽐特币地址，我们着重分析⽐特币中⽤得最多的SHA256算法。
SHA历史介绍：
SHA256属于著名的SHA家族⼀员。SHA（Secure Hash Algorithm，安全哈希算法）是⼀类由美国国家标准与技术研究院（NIST）发布的密码哈希函数。
正式名称为SHA的第⼀个成员发布于1993年，两年之后，著名的SHA-1发布，之后另外的4种变体相继发布，包括SHA224、SHA256、SHA384和SHA512，这些
算法也被称作SHA2。SHA256算法是SHA2算法簇中的⼀类。对于长度⼩于264位的消息，SHA256会产⽣⼀个256位的消息摘要。SHA256具有密码哈希函数的⼀般特性。
那么⽐特币中的SHA256⼜是何⽅神圣？它的设计原理是什么？代码⼜如何实现呢？
下⾯让我娓娓道来·····
SHA256⼜是何⽅神圣？
SHA256是构造区块链所⽤的主要密码哈希函数。⽆论是区块的头部信息还是交易数据，都使⽤这个哈希函数去计算相关数据的哈希值，以保证数据的完整性。同时，在⽐特币系统中，基于寻给定前缀的SHA256哈希值，设计了⼯作量证明的共识机制；SHA256也被⽤于构造⽐特币地址，即⽤来识别不同的⽤户。
SHA256是⼀个Merkle-Damgard结构的迭代哈希函数，其计算过程分为两个阶段：消息的预处理和主
循环。在消息的预处理阶段，主要完成消息的填充和扩展填充，将所输⼊的原始消息转化为n个512⽐特的消息块，之后对每个消息块利⽤SHA256压缩函数进⾏处理。这个计算流程是⼀个迭代计算的过程，当最后1个消息块（第n块）处理完毕以后，最终的输出值就是所输⼊的原始消息的SHA256值。
在⽐特币系统中，SHA256算法的⼀个主要⽤途是完成PoW（⼯作量证明）计算。按照⽐特币的设计初衷，PoW要求钱包（节点）数和算⼒值⼤致匹配，因为需要通过CPU的计算能⼒来进⾏投票。然⽽随着⼈们对SHA256的计算由CPU逐渐升级到GPU，到FPGA，直⾄到ASIC矿机，这使得节点数和PoW算⼒也渐渐失配。解决这个问题的⼀个思路是引⼊另外的⼀些哈希函数来实现PoW。
scrypt算法最早⽤于基于⼝令的密钥⽣成，该算法进⾏多次带参数的SHA256计算，即基于SHA256的消息认证码计算，这类计算需要⼤量的内存⽀持。采⽤scrypt算法进⾏PoW计算，将PoW计算由已有的拼算⼒在⼀定程度上转化为拼内存，能够使得节点数和PoW的计算⼒的失配现象得到缓解。莱特币就是采⽤scrypt算法完成PoW计算的。
SHA3算法是2012年10⽉由NIST所选定的下⼀代密码哈希算法。在遴选SHA3算法过程中⼈们提出了⼀系列的候选算法，包括了BLAKE、Grostl、JH、Keccak、Skein、ECHO、Luffa、BMW、CubeHash、SHAvite、SMID等，最后胜出的是Keccak算法。达世币（DASH，原名暗⿊币，DarkCoin）定义了顺序调⽤上述11个哈希算法的X11算法，并利⽤这个算法完成PoW计算。同样，由于采⽤了X11算法，使得节点数和PoW的计算⼒能够保持⼀定程度上的匹配。
设计原理
下⾯介绍SHA算法计算消息摘要的原理：
对于任意长度（按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进制写成下⾯的样⼦
61626380000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
0000000000000000
现在，数据的长度是448了，我们可以进⾏下⼀步操作。
（⼆）补长度
所谓的补长度是将原始数据的长度补到已经进⾏了补位操作的消息后⾯。通常⽤⼀个64位的数据来表⽰原始消息的长度。如果消息长度不⼤于2^64，那么第⼀个字就是0。在进⾏了补长度的操作以后，整个消息就变成下⾯这样了（16进制格式）
61626380000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000018
（三）使⽤的常量
在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
该算法使⽤了六种基本逻辑函数，由64 步迭代运算组成。每步都以256-bit 缓存值ABCDEFGH 为输⼊，然后更新缓存内容。
每步使⽤⼀个32bit 常数值Kt 和⼀个32bit Wt。
（四）六种基本逻辑函数
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消息摘要。
代码实现
I 调⽤库函数：
下⾯的⽰例计算 data 的SHA256哈希值，并将它存储在 result 中。此⽰例假定存在⼀个预定义的常数 DATA_SIZE：
C#的代码⽰例：
1byte[] result;
2byte[] data = new byte[DATA_SIZE];
3 SHA256 shaM = new SHA256Managed();
4 result = shaM.ComputeHash(data);
Java的代码⽰例：
1 ubyteresult[];
2 ubyte data[] = new ubyte[DATA_SIZE];
3 SHA256 shaM = new SHA256Managed();
4 result = shaM.ComputeHash(data);
SQL的代码⽰例：
1 SELECT sha2(data,256);
PHP的代码⽰例：
1$result=hash('sha256', $data);
II ⾃⼰编写代码实现：
前⾯我们已经说明了SHA-256的计算过程，接下来我们将这⼀过程代码化。同样的⾸先定义⼀个上下⽂的结构。
1 /** 定义SHA-256哈希操作的内容信息结构体 */
2 typedef struct SHA256Context {
3 uint32_t Intermediate_Hash[SHA256HashSize/4]; /* 信息摘要 */
4 uint32_t Length_High; /* 按位计算的信息长度⾼字 */
5 uint32_t Length_Low; /* 按位计算的信息长度低字 */
6 int_least16_t Message_Block_Index; /* 信息分组数组的索引 */
7 uint8_t Message_Block[SHA256_Message_Block_Size];/* 512位信息分组 */
8 int Computed; /* 摘要计算标识 */
9 int Corrupted; /* 信息摘要损坏标识 */
10 } SHA256Context;
实现SHA256Context结构的初始化，为后续的计算过程做准备。
1 static SHAStatusCode SHA224_256Reset(SHA256Context *context, uint32_t *H0)
2 {
3 if (!context) return shaNull;
4 context->Length_High = context->Length_Low = 0;
5 context->Message_Block_Index = 0;
6 context->Intermediate_Hash[0] = H0[0];
7 context->Intermediate_Hash[1] = H0[1];
8 context->Intermediate_Hash[2] = H0[2];
9 context->Intermediate_Hash[3] = H0[3];
10 context->Intermediate_Hash[4] = H0[4];
11 context->Intermediate_Hash[5] = H0[5];
12 context->Intermediate_Hash[6] = H0[6];
13 context->Intermediate_Hash[7] = H0[7];
14 context->Computed = 0;
15 context->Corrupted = shaSuccess;
16 return shaSuccess;
17 }
接下来实现信息分组的输⼊，这个函数接受⼀个字节数组作为下⼀个消息分组以便进⾏处理。
1 SHAStatusCode SHA256Input(SHA256Context *context, const uint8_t *message_array,unsigned int length)
2 {
3 if (!context) return shaNull;
4 if (!length) return shaSuccess;
5 if (!message_array) return shaNull;
6 if (context->Computed) return context->Corrupted = shaStateError;
7 if (context->Corrupted) return context->Corrupted;
8 while (length--)
9 {
10 context->Message_Block[context->Message_Block_Index++] =*message_array;
11 if ((SHA224_256AddLength(context, 8) == shaSuccess) &&(context->Message_Block_Index == SHA256_Message_Block_Size))
12 SHA224_256ProcessMessageBlock(context);
13 message_array++;
14 }
15 return context->Corrupted;
16 }
当然还需要⼀个消息处理及最终摘要输出的函数，这个函数将返回⼀个224位或者256位的信息摘要到调⽤者给定的Message_Digest数组。返回的信息摘要，第⼀个元素索引为0，最后⼀个元素索引为27（SHA-2244）或者31（SHA-256）。
1 static SHAStatusCode SHA224_256ResultN(SHA256Context *context,uint8_t Message_Digest[ ], int HashSize)
2 {
3 int i;
4 if (!context) return shaNull;
5 if (!Message_Digest) return shaNull;
6 if (context->Corrupted) return context->Corrupted;
7 if (!context->Computed)
8 SHA224_256Finalize(context, 0x80);
9 for (i = 0; i < HashSize; ++i)
10 Message_Digest[i] = (uint8_t)(context->Intermediate_Hash[i>>2] >> 8 * ( 3 - ( i & 0x03 ) ));
11 return shaSuccess;
12 }
区块链中的哈希指针链
哈希指针是⼀类数据结构，除了包含通常的指针外，还包含⼀些数据信息以及与这些信息相关的密码哈希值，这就使得正常的指针可⽤于取回信息，哈希指针⽤于验证信息是否发⽣改变。区块链就可以看作⼀类使⽤哈希指针的链表，如下图所⽰。这个链表链接⼀系列的区块，每个区块包含数据以及指向表中前⼀个区块的指针。区块链中，前⼀个区块指针由哈希指针所替换，因此每个区块不仅仅告诉前⼀个区块的位置，也提供⼀个哈希值去验证这个区块所包含的数据是否发⽣改变。
哈希指针链
可以利⽤区块链去构造⼀个防篡改的⽇志系统。在这个系统中，基于区块链的⽇志节点链表被⽤来存储数据，链表节点通过哈希指针链接，新节点追加在⽇志链表的尾部。同时，⽇志链表的头哈希指针所指向的头节点内容不可改变。若⽇志链表中的某个节点的数据被篡改，则系统能够检测出来。
假定攻击者改变了节点k的数据，由于其后继节点k+1存储了节点k的哈希值，由于密码哈希函数的抗碰撞性，通过简单地计算节点k的数据的哈希值，就能发现计算出的值与节点k+1的哈希指针值不⼀致，于是可以断定节点k或节点k+1的信息被篡改。当然，攻击者可能能够连续改变前⼀个节点的哈希值来掩盖不同，但这个策略在处理⽇志链表的头节点时将会失败。特别地，⼀旦将链表头部的哈希指针存储在不能改变的地⽅，攻击者将不能改变任何节点⽽不被发觉。
因此，若攻击者想在⽇志链表中的任意位置改变数据，为保持⼀致性，他必须向表头⽅向修改所有的哈希指针，最终由于不能改变链表头部⽽失败。因此，只需单个哈希指针，基本上就能保证整个链表的哈希值的⼀致性，从⽽达到防篡改的⽬的。
哈哈哈哈哈哈，区块链中加密算法——Hash算法之SHA256算法到这⾥就更新完了！
下⼀节给⼤家讲Merkle树，敬请期待·····
【时间仓促，如有错误，欢迎指正！ || 欢迎留下您的评语！⼤家⼀起探讨、学习区块链!】
【转载请注明出处！】
Reference：
1.SHA256代码实现：
2.SHA256算法介绍：
3.《区块链技术指南》，，，著
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论