#SHA-256 的原理与实现

SHA-2（Secure Hash Algorithms 2）是一系列散列函数算法标准，可以说是目前最重要，使用最广泛的 Hash 函数家族。SHA-256 和 SHA-512 又是家族中最流行的两支。在量子计算机真正实用化之前，它都是密码学中的重要武器。

今天，就来研究一下 SHA-256 的算法原理，并试着用 JavaScript 实现了一下。

##核心原理

SHA-256 的核心原理可以用一句话来概括：通过一系列复杂的数学计算，将任意长度的输入数据转换成一个固定长度（256 位）的「数字指纹」。核心目标是确保这个「数字指纹」的唯一性、不可逆性和抗碰撞性。

SHA-256 对消息做 Hash 摘要，例如：

经过 SHA-256 算法处理后将会变成：

以下是 SHA-256 算法处理数据的核心步骤：

其中的核心数学原理主要是混淆与扩散（Confusion & Diffusion）：

##初始 Hash 值

前文提到了 SHA-256 算法中会用到 8 个 Hash 初始值（$H_i$）；他们分别是：

$\begin{aligned} H_0 &= 6a09e667 \\ H_1 &= bb67ae85 \\ H_2 &= 3c6ef372 \\ H_3 &= a54ff53a \\ H_4 &= 510e527f \\ H_5 &= 9b05688c \\ H_6 &= 1f83d9ab \\ H_7 &= 5be0cd19\end{aligned}$

$H_1$ 至 $H_7$ 来自于自然数中前 8 个质数（$2, 3, 5, 7, 11, 13, 17, 19$）的平方根的小数部分的前 32 位。

除此之外，还会用到 64 个 Hash 常量（$K_{t}$），他们分别是：

$\begin{aligned} 428a2f98 &\space 71374491 & b5c0fbcf &\space e9b5dba5 & 3956c25b &\space 59f111f1 & 923f82a4 &\space ab1c5ed5 \\ d807aa98 &\space 12835b01 & 243185be &\space 550c7dc3 & 72be5d74 &\space 80deb1fe & 9bdc06a7 &\space c19bf174 \\ e49b69c1 &\space efbe4786 & 0fc19dc6 &\space 240ca1cc & 2de92c6f &\space 4a7484aa & 5cb0a9dc &\space 76f988da \\ 983e5152 &\space a831c66d & b00327c8 &\space bf597fc7 & c6e00bf3 &\space d5a79147 & 06ca6351 &\space 14292967 \\ 27b70a85 &\space 2e1b2138 & 4d2c6dfc &\space 53380d13 & 650a7354 &\space 766a0abb & 81c2c92e &\space 92722c85 \\ a2bfe8a1 &\space a81a664b & c24b8b70 &\space c76c51a3 & d192e819 &\space d6990624 & f40e3585 &\space 106aa070 \\ 19a4c116 &\space 1e376c08 & 2748774c &\space 34b0bcb5 & 391c0cb3 &\space 4ed8aa4a & 5b9cca4f &\space 682e6ff3 \\ 748f82ee &\space 78a5636f & 84c87814 &\space 8cc70208 & 90befffa &\space a4506ceb & bef9a3f7 &\space c67178f2\end{aligned}$

与 Hash 初始值类似，它们分别取自于自然数中前 64 个质数（$2, 3, 5, \dotsc, 307, 311$）的立方根的小数部分的前 32 位。

##数据预处理

然后是对数据进行预处理，主要是两个步骤：补位与分块。

###数据填充

对数据进行补位处理，确保其最终的长度是 512 位的倍数。其规则为，先在末尾补上一位 $1$（即 0x80），表示填充开始。再在末尾补上 $k$ 个 $0$，直至原始数据长度 $L$ 满足：

$L + 1 + k \equiv 448 \pmod {512}$

最后，在末尾附加原始数据长度 $L$ 的二进制表示（大端序，64 位）。

例如，假设数据位 abc，则其对应的 ASCII 码和二进制编码如下：

所以 abc 的二进制编码为：

$01100001 \space 01100010 \space 01100011$

先在末尾补上一位 $1$：

$01100001 \space 01100010 \space 01100011 \space 1$

再补上 423 个 $0$：

$01100001 \space 01100010 \space 01100011 \space 1 \space \underbrace{0 \dotsc 0}_{423 \text{ times}}$

最后，在末尾附加数据 abc 的长度 24 的二进制表示（64 位）：

$\overbrace{01100001 \space 01100010 \space 01100011 \space 1 \space \underbrace{0 \dotsc 0}_{458 \text{ times}} 11000}^{512 \text{ bit}}$

###分块处理

分块处理很好理解，就是将填充后的数据 $M$ 分解成 $n$ 个大小为 512 比特的块。

此后在做循环处理时，每次对 512 比特的数据块进行运算，得到的 256 比特的结果再与下一个块进行运算，如此运行 $n$ 次后，得到最终的哈希值，即 256 bit 的「数字签名」。

##运算

终于，我们来到了最核心的运算环节！

SHA-256 算法的运算主要包括两个方面：消息扩展和消息压缩（Message Expansion & Message Compression），其中消息压缩又可以拆分为主循环和更新 Hash 值。

消息扩展和消息压缩十分符合《道德经》中的「有无相生，难易相成」的思想；先扩展，再压缩，让数据变得混沌，从而实现不可逆性和抗碰撞性；又因为算法是完完全全没有任何副作用的纯函数，所以天生具有唯一性。

###消息扩展（Message Expansion）

消息扩展的目的是将原始数据块扩展为更长的位序列，以供后续的轮函数处理。消息扩展通过引入非线性变换和复杂的数据依赖关系，增强算法的安全性和扩散性。

在 SHA-256 中，吗，每个 512 比特的数据块会被分块处理，消息扩散的目标是将这 512 比特（16 个 32 比特的字）扩展为 64 个 32 比特的字，供后续 64 轮运算（即「主循环」）使用。

###消息压缩（Message Compression）

消息压缩负责将消息扩展生成的 64 个 32 比特的字（$W_t$）和 Hash 中间值（初始化为 $H_i$）混合，并生成新的 Hash 状态。

以下是具体步骤：

##用 TypeScript 实现

##参考资料

$W_0, W_1, W_2, W_3, W_4, W_5, \dotsc, W_{15}$

$\begin{aligned} a^{(0)} &= H_0 \\ b^{(0)} &= H_1 \\ c^{(0)} &= H_2 \\ d^{(0)} &= H_3 \\ e^{(0)} &= H_4 \\ f^{(0)} &= H_5 \\ g^{(0)} &= H_6 \\ h^{(0)} &= H_7\end{aligned}$

$\begin{aligned} H_0' &= H_0 + a^{(64)} \pmod{2^{32}} \\ H_1' &= H_1 + b^{(64)} \pmod{2^{32}} \\ H_2' &= H_2 + c^{(64)} \pmod{2^{32}} \\ H_3' &= H_3 + d^{(64)} \pmod{2^{32}} \\ H_4' &= H_4 + e^{(64)} \pmod{2^{32}} \\ H_5' &= H_5 + f^{(64)} \pmod{2^{32}} \\ H_6' &= H_6 + g^{(64)} \pmod{2^{32}} \\ H_7' &= H_7 + h^{(64)} \pmod{2^{32}}\end{aligned}$

将 $H_i'$ 依次拼接起来就得到了我们梦寐以求的 Hash 值！

$\begin{aligned} T_1^{(t)} &= h^{(t)} + \Sigma_1(e^{(t)}) + Ch(e^{(t)}, f^{(t)}, g^{(t)}) + K_t + W_t \\ T_2^{(t)} &= \Sigma_0(a^{(t)}) + Maj(a^{(t)}, b^{(t)}, c^{(t)}) \\\end{aligned}$

其中：

$\begin{aligned} Ch(x, y, z) &= (x \land y) \oplus (\neg x \land z) \\ Maj(x, y, z) &= (x \land y) \oplus (x \land z) \oplus (y \land z) \\ \Sigma_0(x) &= ROTR^2(x) \oplus ROTR^{13}(x) \oplus ROTR^{22}(x) \\ \Sigma_1(x) &= ROTR^6(x) \oplus ROTR^{11}(x) \oplus ROTR^{25}(x) \\ ROTR^n(x) &\equiv x \text{ rotated right by } n \text{ bits} \\ SHR^n(x) &\equiv x \text{ shifted right by } n \text{ bits}\end{aligned}$

然后更新工作变量：

$\begin{aligned} h^{(t+1)} &= g^{(t)} \\ g^{(t+1)} &= f^{(t)} \\ f^{(t+1)} &= e^{(t)} \\ e^{(t+1)} &= d^{(t)} + T_1^{(t)} \pmod{2^{32}} \\ d^{(t+1)} &= c^{(t)} \\ c^{(t+1)} &= b^{(t)} \\ b^{(t+1)} &= a^{(t)} \\ a^{(t+1)} &= T_1^{(t)} + T_2^{(t)} \pmod{2^{32}}\end{aligned}$

$W_{t} = \sigma_{1}(W_{t-2}) + W_{t-7} + \sigma_{0}(W_{t-15}) + W_{t-16}$

其中：

$\begin{aligned} \sigma_{0} &= ROTR^{7}(x) \oplus ROTR^{18}(x) \oplus SHR^{3}(x) \\ \sigma_{1} &= ROTR^{17}(x) \oplus ROTR^{19}(x) \oplus SHR^{10}(x) \\ ROTR^n(x) &\equiv x \text{ rotated right by } n \text{ bits} \\ SHR^n(x) &\equiv x \text{ shifted right by } n \text{ bits}\end{aligned}$