SHA-256哈希算法「Hash函数」

机器之心报道

机器之心编辑部

哈希算法到底是什么？它又是如何运行的？Greg Walker 用视频给出了一个可视化的解答，并在 GitHub 上进行了共享，详细介绍了 SHA-256 函数的工作原理。

项目链接：https://github.com/in3rsha/sha256-animation

Greg Walker 喜欢构建一些教育性网站，简单易懂地讲解一些科普类算法。

他在这个解释 SHA-256 的视频中，不仅介绍了哈希计算，还涉及比特币挖矿、基础运算、函数、常量等知识。

什么是哈希函数？

哈希就是将不同的输入映射成独一无二的、固定长度的值（又称 "哈希值"），是最常见的软件运算之一。很多网络服务会使用哈希函数，产生一个 token，标识用户的身份和权限。

那它是如何运行的呢？哈希函数可以把给定的数据转换成固定长度的无规律数值。此处为方便读者理解，我们借用《我的第一本算法书》里的比喻：将哈希函数想象成搅拌机。

图源：《我的第一本算法书》

将数据 “abc” 放入搅拌机里，经过哈希函数计算后，会输出固定长度且无规律的数值，而这个无规律数值就是“哈希值”，绝大多数情况用十六进制来表示。

哈希函数有一系列特征，如上图所示，输出的哈希值与输入数据的大小、长度等没有任何关系。

若输入相同，输出的哈希值也必定相同。

如输入不同，输出的哈希值也必然不同，哪怕是只有细微区别。

在输入数据完全不同的情况下，输出的哈希值有可能是相同的，这种少数特殊情况称为“哈希冲突”。

同时，哈希值是不可逆的，也就是说，通过哈希值不可能反向推算出原本的数据。

在本项目中，Greg Walker 也通过视频介绍了以上几大特征。

SHA-256

SHA 包括 SHA-0、SHA-1、SHA-2 和 SHA-3 系列，SHA-256 是 SHA-2 系列的函数之一。其摘要长度为 256 bits，即 32 个字节，故称 SHA-256。SHA-256 常出现于比特币领域。

那么 SHA-256 到底是什么样的呢？Greg Walker 提供了动画展示。

动画展示 SHA-256，你也能做到

只需对需要进行 hash 处理的数据运行 sha256.rb 脚本即可。

# simpleruby sha256.rb abc

# hash binary or hex data by using `0b` or `0x` prefixesruby sha256.rb 0b01100001ruby sha256.rb 0xaabbccdd

# speed up or step through the animation (optional)ruby sha256.rb abc normal # defaultruby sha256.rb abc fastruby sha256.rb abc enter

输入二进制字符串作为参数，从而运行 SHA-256 中的各个函数：

ruby shr.rb 11111111111111110000000000000000 22ruby rotr.rb 11111111111111110000000000000000 22ruby sigma0.rb 11111111111111110000000000000000ruby sigma1.rb 11111111111111110000000000000000ruby usigma0.rb 11111111111111110000000000000000ruby usigma1.rb 11111111111111110000000000000000ruby Ch.rb 11111111111111110000000000000000 11110000111100001111000011110000 00000000000000001111111111111111ruby maj.rb 11111111111111110000000000000000 11110000111100001111000011110000 00000000000000001111111111111111

你也可以使用 hash256.rb 来进行 double-SHA256，该脚本默认接受十六进制数据，如交易数据等。

ruby hash256.rb 0100000000000000000000000000000000000000000000000000000000000000000000003ba3edfd7a7b12b27ac72c3e67768f617fc81bc3888a51323a9fb8aa4b1e5e4a29ab5f49ffff001d1dac2b7c # genesis block header

SHA-256 的工作原理

基础运算

这里只对 SHA-256 的基础运算进行简单介绍。

SHA-256 uses four basic bitwise operations on words.

SHA-256 对 words 使用 4 种 bitwise 基础运算。

右移 (shr.rb)

SHRn(x) = x >> n

将 bits 向右移动多个位置，同时从右侧移出的 bits 丢失。

向右旋转 (rotr.rb)

将 bits 向右移动多个位置，然后将移动后的 bits 放在左侧，也称为「循环右移」。

Exclusive Or (xor.rb)

x ^ y ^ z

XOR 的输入为两个 bit，如果其中只有一个为 1，则输出 1。在合并多个 bit 时通过多次 XOR 运算进行，同时获得多个 bit 的“平衡表示”（balanced representation）。

加法 (add.rb)

(v w x y z) % 232

这是非常标准的整数加法运算，唯一的不同是，此处采用结果模数为 2^32，从而将结果限制为 32 位数字。

函数

将上述运算组合起来，就可以创建函数。

前四个函数使用希腊符号 Sigma 命名（小写σ和大写Σ）。

σ0 (sigma0.rb)

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

σ1 (sigma1.rb)

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

Σ0 (usigma0.rb)

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

Σ1 (usigma1.rb)

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

最后两个函数 “Choice” 和“Majority”可接受三个不同的输入，如下所示：

Choice (ch.rb)

该函数基于 x 位在 y 位和 z 位之间做出选择。如果 x = 1，则选择 y 位；如果 x = 0，则选择 z 位。

Ch(x, y, z) = (x & y) ^ (~x & z)

Majority (maj.rb)

该函数返回的是三个 bits 中的多数。

Maj(x, y, z) = (x & y) ^ (x & z) ^ (y & z)

压缩

该教程中还介绍了很多有趣的基础知识，这里不再赘述。我们重点来看哈希函数的压缩函数，这也是其核心功能。

对于消息调度中的每个词，我们都使用 “状态寄存器” 中的当前值来计算两个新的临时词（设为 T_1 和 T_2）。

Temporary Word 1 (t1.rb)

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

此临时词将消息调度中的下一个单词与列表中的下一个常量并在一起运行。

Temporary Word 2 (t2.rb)

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

通过将状态寄存器中第一个值Σ_0 进行旋转，与前三个寄存器中的 Majority 的值相加来计算这个临时词。

压缩 (compression.rb)

在计算了两个临时词之后，将状态寄存器中的值移至下一个位置，并更新寄存器：

状态寄存器中的第一个值变为 T_1 T_2，同时状态寄存器中的第五个值已添加了 T_1。

这即是一轮压缩，对于信息调度中的每个词该过程都会重复一次。

在压缩了整个消息调度之后，我们将得到的哈希值添加到初始哈希值中，由此得出消息块的最终哈希值。

但如果还有其他消息块要处理，则将当前哈希值在下一次压缩中用作初始哈希值。如下图所示：