SHA-256计算原理

SHA-256（Secure Hash Algorithm 256-bit）是SHA-2系列中的一种哈希算法，它由美国国家安全局（NSA）设计，并由美国国家标准与技术研究院（NIST）发布。SHA-256主要用于数据完整性验证和数字签名等领域。以下是SHA-256的详细计算原理。

1. SHA-256的基本概念

SHA-256是一种密码学哈希函数，它将任意长度的输入数据转换为一个固定长度的256位（32字节）哈希值。其主要特点包括：

• 不可逆性：无法从哈希值逆推出原始输入数据。
• 唯一性：不同的输入数据具有不同的哈希值。
• 快速计算：能够快速计算哈希值。
• 抗碰撞性：找到两个具有相同哈希值的不同输入数据是非常困难的。

2. SHA-256的计算步骤

SHA-256的计算过程主要包括以下几个步骤：

2.1. 消息填充

首先对输入消息进行填充，使其长度满足特定条件：

1. 附加一个“1”位：在消息末尾添加一个“1”位。
2. 附加“0”位：添加若干个“0”位，使得填充后的消息长度比512的倍数少64位。
3. 附加消息长度：用64位二进制表示的消息长度附加到消息末尾。此时消息的总长度为512的倍数。

2.2. 初始化哈希值

定义八个32字节（256位）的初始哈希值，分别为：

h0 = 0x6a09e667
h1 = 0xbb67ae85
h2 = 0x3c6ef372
h3 = 0xa54ff53a
h4 = 0x510e527f
h5 = 0x9b05688c
h6 = 0x1f83d9ab
h7 = 0x5be0cd19

2.3. 处理消息块

将消息分割成512位（64字节）的消息块，每个消息块进一步分为16个32位的字。

1. 消息调度：将16个32位的字扩展为64个32位的字。扩展方式如下：

   for i from 16 to 63:
       s0 = (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift 3)
       s1 = (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor (w[i-2] rightshift 10)
       w[i] = w[i-16] + s0 + w[i-7] + s1
   

2. 初始化工作变量：将初始哈希值复制到工作变量中：

   a = h0
   b = h1
   c = h2
   d = h3
   e = h4
   f = h5
   g = h6
   h = h7
   

3. 主循环：进行64轮压缩操作，每轮使用一个常量K[i]和一个消息字w[i]，常量K是固定的。

   for i from 0 to 63:
       S1 = (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
       ch = (e and f) xor ((not e) and g)
       temp1 = h + S1 + ch + K[i] + w[i]
       S0 = (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
       maj = (a and b) xor (a and c) xor (b and c)
       temp2 = S0 + maj
   
       h = g
       g = f
       f = e
       e = d + temp1
       d = c
       c = b
       b = a
       a = temp1 + temp2
   

4. 哈希值更新：将计算结果加到当前哈希值：

   h0 = h0 + a
   h1 = h1 + b
   h2 = h2 + c
   h3 = h3 + d
   h4 = h4 + e
   h5 = h5 + f
   h6 = h6 + g
   h7 = h7 + h
   

2.4. 输出最终哈希值

当所有消息块处理完毕后，将h0到h7连接起来，形成256位（32字节）的最终哈希值。这就是SHA-256的输出。

3. 总结

SHA-256通过一系列复杂的步骤，将任意长度的输入数据转换为固定长度的哈希值。其主要过程包括消息填充、初始化哈希值、处理消息块（包括消息调度和主循环）、哈希值更新以及最终输出哈希值。SHA-256的强大之处在于其不可逆性和抗碰撞性，广泛应用于数据完整性验证和密码学中。

参考：https://en.wikipedia.org/wiki/SHA-2

作者简介：https://shimo.im/docs/rp3OVwxle2fJn7Am/
上海徐汇
2024年6月2日