近日笔者在学习区块链的相关知识，接触到SHA-256算法，这里做一个知识梳理和总结。

强烈推荐大家自行去学习下面链接github上的工程，作者的动画演示和解释做的非常出色，逻辑非常清晰，B站搬运的对应的油管的讲解视频也放在下面，本文也是基于此github工程和作者学习过程的思路进行呈现。

github：

https://github.com/in3rsha/sha256-animation

B站讲解视频：

https://www.bilibili.com/video/BV1Jg411G7tc

ruby（windows）安装教程：

https://www.cnblogs.com/minisayo/p/14015747.html

可以先将github工程下载到本地，因为作者是用的ruby进行动画展示，所以需要再windows/Linux系统上安装ruby，之后在工程目录下调用ruby xxx.rb指令即可啦。

下面是整个工程的流程图，也对应着SHA-256算法的设计思路。

一、运算定义

为了后续分析思路与流程的连贯性，在这里先统一声明一下一些运算的定义，后续一些函数会直接对这些运算进行封装使用。

1、右移Right Shift (shr.rb)

这里的右移会产生两种结果，第一种结果是左侧移动完之后位为0，右侧被移走的位丢失，如上图所示SHR 32的操作，原数据为32位，在右移32位之后原数据都被右移丢失，剩下的左侧移动完的位全为0。

2、旋转右移Right Shift (rotr.rb)

这里要尤其注意和SHR右移的区别，观察演示图可以发现对于旋转右移而言数据组成了一个环形，移动位数只是改变位的绝对位置，并不会丢弃数据，所以原数据32位，再进行ROTR 32的操作实际上就是所有数据位旋转了一整圈，又回到了原来的位置。

3、异或XOR (xor.rb)

按位异或，0^0 = 0，1^0 = 1，0^1 = 1，1^1 = 0。

4、加法Addition (add.rb) 

这里和二进制加法一样，但是由于多个32位的数据相加，最终的存在着溢出的风险，因此最终的结果进行取模2*32将其约束在32位输出。

二、函数定义

第一部分的运算被封装组合起来就是这部分的函数，在这里先列出一些后续算法流程分析会用到的函数，读者可以先有个大概印象，后面第三部分算法流程分析的时候再回看也可以。

前四个函数使用希腊符号 Sigma（小写 σ，大写 Σ）命名。这些名称没有特殊含义，只是为了方便给一些组合运算命名。

1、σ0 (sigma0.rb)

σ0(x) = ROTR7(x) ^ ROTR18(x) ^ SHR3(x)

先分别计算ROTR 7位和ROTR18位和SHR 3位，再将三者异或

2、σ1 (sigma1.rb)

σ1(x) = ROTR17(x) ^ ROTR19(x) ^ SHR10(x)

先分别计算ROTR 17位和ROTR 19位和SHR 10位，再将三者异或

3、Σ0 (usigma0.rb)

Σ0(x) = ROTR2(x) ^ ROTR13(x) ^ ROTR22(x)

先分别计算ROTR 2位和ROTR 13位和ROTR 22位，再将三者异或

4、Σ1 (usigma1.rb) 

Σ1(x) = ROTR6(x) ^ ROTR11(x) ^ ROTR25(x)

先分别计算ROTR 6位和ROTR 11位和ROTR 25位，再将三者异或

5、Choice (ch.rb)

这个函数使用x位在y位和z位之间进行选择。如果x=1，则选择y位；如果x=0，则选择z位。

6、Majority (maj.rb)  

这个函数返回三位中的多数位。

7、常量Constants (constants.rb)

SHA-256 使用六十四个常量 Kt 来帮助在主哈希计算过程中混合比特。

首先计算前64个质数的立方根，然后取其小数部分乘2^32，将得到的常量作为Kt使用，其中t表示第t个质数运算后的结果。

这些立方根的小数部分是无理数（它们无限延伸），因此它们是用于常量的良好随机比特选择。这比使用特别选择的常量更好，因为这降低了哈希函数被设计成具有后门的可能。

三、算法流程分析 

在这里message的内容是可以自己指定的，我们以message = dyq 为例（在每个rb文件的开头可以自定义默认输入）

1、message.rb 

输入一个message字符串时，我们将每个字符转换为 ASCII 表中的对应数字。这些数字被转换为二进制，我们使用这些二进制数据作为哈希函数的输入。 

2、padding.rb

SHA-256 哈希函数以 512 位的block数据块为单位进行操作，因此所有消息都需要用零填充至最接近的 512 位的倍数，可以是512、1024等，这里先填充到448位，后64位预留出用来表示message的比特位数。

为了防止相似输入哈希到相同的结果，我们用 1 位将消息与零分隔开，并在填充的最后 64 位中包含消息的大小。 

以上这种用 1 分隔消息并在填充中包含消息大小的方法被称为 Merkle–Damgård 加强（MD 加强）。 

3、blocks.rb

消息经过填充后，我们将其切割成等长的 512 位消息块 Mi 以便哈希函数处理。

每个消息块也可以进一步分成 16 个词Wj ( 512 / 32 = 16 words )，每个词的长度为32bit，这将在后续使用。 

4、schedule.rb

 对于前16个word，每个word有32个bit，相当于是把原本的block0分为了32*16。

从第17个word开始根据下面的公式进行计算

Wt = σ1(Wt-2) + Wt-7 + σ0(Wt-15) + Wt-16

其中σ1和σ0在第二部分可以找到函数的定义。

5、expansion.rb

这一步展示的是上面最后一个word W63生成的运算过程。 

6、initial.rb

初始哈希值使用了前八个质数的平方根的小数部分。我们将这八个字母作为状态寄存器，我们可以将其作为开始哈希计算的起点（初始状态）

7、t1.rb t2.rb

我们需要先使用状态寄存器中的当前值来计算两个新的临时词（ T1 和 T2 ），为后续的压缩过程做准备。

T1 = Σ1(e) + Ch(e, f, g) + h + Kt + Wt

其中Σ1和Ch函数在第二部分，h为h状态寄存器存储的值，Kt为第二部分的64个常数值，Wt为schedule.rb求得的word。

T2 = Σ0(a) + Maj(a, b, c)

其中Σ0函数和Maj函数均在第二部分。

8、compression.rb

压缩是整个算法的核心。我们再将其细化进行分析

（1） step1：计算出T1和T2

 （2） step2：所有寄存器下移一个

 （3） step3：更新a和e寄存器的值

以上三步可以概括为计算T1,T2；下移寄存器；更新a和e值，至此我们称为完成一轮压缩。这样的压缩要对一共64个word都进行一遍。

以上就是第二轮的step1开始以此类推。 

压缩完64轮之后，将最终的abcdefgh寄存器的值和initial.rb中的abcdefgh中的值相加得到最后的寄存器值

如果还有进一步要处理的消息块（block1，block2……），按照下图当前的哈希值将作为下一个压缩的初始哈希值。 

9、final.rb

 最终将8个32位的寄存器值转化为8个16进制的哈希值并拼接在一起，最终得到message的哈希值

 

使用哈希计算器验证一下是没问题的

10、sha256.rb 

# 直接进行哈希运算
ruby sha256.rb abc# 也可以输出二进制和十六进制数据
ruby sha256.rb 0b01100001
ruby sha256.rb 0xaabbccdd# 哈希一个文件 (请注意，文件末尾将有一个换行符)
ruby sha256.rb file.txt# 添加不同的命令行参数
ruby sha256.rb abc normal # 默认
ruby sha256.rb abc fast   # 加速演示
ruby sha256.rb abc enter  # 每按一次回车，步进一次动画

sha256.rb是一个集成上述功能的完整代码，除此之外，还可以指定命令行参数实现不同操作。

将sha-256.rd的输出改成可分为多个block的长message，测试多个block条件下hash算法 

观察以上代码运行后的结果发现，进行了多个block的流水线运算，最终的结果正确，真是太吊了。但是这里注意改变输入时不能直接在命令行输入段落，因为作者的代码中不能识别空格，所以只能在rb文件里改变input，但是也无伤大雅，笔者有时间会完善一下这个小bug的。