深入哈希函数：SHA-256的数学之旅

XR2025-06-182026-02-03

深入哈希函数：SHA-256的数学之旅

上次我们聊了哈希是干啥的，说它是个”单向搅拌机”。那今天，咱们就把这台搅拌机的盖子掀开，看看里面的齿轮和刀片（也就是数学原理）到底是怎么工作的。

我们拿大名鼎鼎的 SHA-256 来开刀。放心，这篇文章不是让你去当数学家，也不是让你自己去实现一个。而是用一个开发者的视角，去理解我们每天都在用的工具，它背后那些精妙的设计。

理解原理是为了更好地使用它，而不是让你自己去实现一个！ 专业的事交给密码学家，我们负责把它用对。

宏观视角：Merkle–Damgård 结构

在我们一头扎进 SHA-256 的细节之前，得先了解大部分哈希函数（包括 MD5、SHA-1、SHA-256）的通用设计蓝图——Merkle–Damgård 结构。

这结构思想很简单：既然我一次性处理不了无限长的数据，那我把它切成一块一块的，不就行了？

它就像一个链式反应炉：

把你的输入数据（比如”hello world”）切成固定大小的块（Block）。
定义一个初始的哈希值（IV - Initial Value），这可以看作是反应炉的”种子”。
把第一个数据块和”种子”一起扔进一个叫做”压缩函数（Compression Function）”的黑盒里。
这个黑盒会输出一个新的哈希值。
把这个新的哈希值作为新的”种子”，和下一个数据块一起，再次扔进那个黑盒里。
如此循环，直到最后一个数据块被处理完毕。
最后输出的那个哈希值，就是你整个数据的最终哈希结果。

  graph TD
    IV(初始哈希值) --> C1(压缩函数);
    B1(数据块1) --> C1;
    C1 --> H1(中间哈希值1);

    H1 --> C2(压缩函数);
    B2(数据块2) --> C2;
    C2 --> H2(中间哈希值2);

    H2 --> Cn(压缩函数);
    Bn(数据块n) --> Cn;
    Cn --> FinalHash(最终哈希值);

    style IV fill:#f9f,stroke:#333,stroke-width:2px
    style FinalHash fill:#ccf,stroke:#333,stroke-width:2px

这个结构的核心就是那个”压缩函数”。SHA-256 的所有魔法，都发生在这个函数里。

SHA-256 的解剖过程

现在，我们正式开始解剖 SHA-256。

第一步：消息填充（Padding）

反应炉要求每个数据块大小都得一样，SHA-256 要求是 512 位（64 字节）。可我们的输入数据千奇百怪，怎么办？

填充！ 规则如下：

在你的原始数据末尾，先补一个 1。
然后，一直补 0，直到消息的总长度距离”512的倍数”只差 64 位为止。
最后这 64 位，用来存放你原始数据的长度（用二进制表示）。

举个例子，假设我们要哈希字符串 “abc”。

“abc” 的 ASCII 编码是 01100001 01100010 01100011，共 24 位。
补 1：变成 25 位。
补 0：我们需要补到 512 - 64 = 448 位。所以要补 448 - 25 = 423 个 0。
补长度：最后 64 位，填入原始长度 24 的二进制。

这样一来，任何长度的输入，都会被处理成一个或多个精确的 512 位数据块。这个填充方案确保了不同长度的原始消息，不会产生相同的填充后消息。

第二步：初始化哈希值（H）

还记得上面说的”种子”吗？SHA-256 的”种子”是 8 个 32 位的整数，我们称之为 H0 到 H7。

H0 = 0x6a09e667
H1 = 0xbb67ae85
H2 = 0x3c6ef372
H3 = 0xa54ff53a
H4 = 0x510e527f
H5 = 0x9b05688c
H6 = 0x1f83d9ab
H7 = 0x5be0cd19

这些”魔法数字”可不是随便拍脑袋想的。它们是自然界最纯粹的 8 个素数（2, 3, 5, 7, 11, 13, 17, 19）的平方根的小数部分，取前 32 位。这么做的目的是为了消除任何可能的后门或人为偏见，保证其初始状态的”随机性”。

备注：其实也不是说只能是这个8个数字而已。其实主要是为了表明来源，密码学中的常数如果没有来源会被认为是后门。

第三步：处理数据块（核心压缩函数）

终于到了最核心的部分。对于每一个 512 位的数据块，SHA-256 会执行一个包含 64 “轮”计算的循环。

在循环开始前，会先初始化 8 个”工作变量”，用当前的哈希值（对于第一个块，就是初始 H 值）来赋值：
a, b, c, d, e, f, g, h = H0, H1, H2, H3, H4, H5, H6, H7

然后，开始 64 轮的”搅拌”：

1. 消息调度（Message Schedule）

首先，SHA-256 不会直接用 512 位的数据块，而是会把它扩展成 64 个 32 位的”字”（word），我们称之为 W[0] 到 W[63]。

前 16 个字 W[0] 到 W[15] 就是把 512 位数据块直接切开得到的。
后面的 48 个字 W[16] 到 W[63] 是通过一个公式，由前面的字生成的：
W[t] = σ1(W[t-2]) + W[t-7] + σ0(W[t-15]) + W[t-16]

这里的 σ0 和 σ1 是一些”小魔法”，它们包含了按位循环右移（ROTR）和右移（SHR）操作。

σ0(x) = ROTR(x, 7) ^ ROTR(x, 18) ^ SHR(x, 3)
σ1(x) = ROTR(x, 17) ^ ROTR(x, 19) ^ SHR(x, 10)
(注：^ 是异或 XOR)

这个过程的目的是制造雪崩效应。输入的微小变化，会通过这个扩展过程，迅速扩散到整个消息调度数组中。

2. 64 轮循环

接下来就是长达 64 轮的循环。在每一轮（我们称之为第 t 轮），都会进行如下计算：

T1 = h + Σ1(e) + Ch(e, f, g) + K[t] + W[t]
T2 = Σ0(a) + Maj(a, b, c)

h = g
g = f
f = e
e = d + T1
d = c
c = b
b = a
a = T1 + T2

是不是看着有点头大？我们拆解一下里面的”大魔法”：

W[t]: 上一步消息调度中生成的第 t 个字。
K[t]: 第 t 轮的常量。和初始 H 值一样，这些也是”魔法数字”，来自前 64 个素数的立方根的小数部分。它们为每一轮的计算引入了不同的扰动。
Σ0(a) 和 Σ1(e): 又是两个循环移位和异或的组合，目的是进一步混淆数据。
- Σ0(a) = ROTR(a, 2) ^ ROTR(a, 13) ^ ROTR(a, 22)
- Σ1(e) = ROTR(e, 6) ^ ROTR(e, 11) ^ ROTR(e, 25)
Ch(e, f, g): “Choose” 函数。Ch(e, f, g) = (e AND f) ^ ((NOT e) AND g)。如果 e 的某一位是 1，则结果的对应位取 f 的，否则取 g 的。这引入了非线性。
Maj(a, b, c): “Majority” 函数。Maj(a, b, c) = (a AND b) ^ (a AND c) ^ (b AND c)。对每一位看 a, b, c 中哪一个（0 或 1）占多数，结果就取哪个。同样是为了引入非线性。

为什么要做这些奇怪的操作？

所有这些眼花缭乱的移位、异或、与非操作，核心目的只有一个：混淆（Confusion）与扩散（Diffusion）。

混淆：让密钥（在这里是输入数据）和最终密文（哈希值）之间的关系变得尽可能复杂。Ch、Maj 等非线性函数是主力。
扩散：输入数据的任何一点微小改动，都能迅速地、大范围地影响到输出的每一位。这就是所谓的”雪崩效应”。各种循环移位 ROTR 就是干这个的。

这 64 轮疯狂”搅拌”之后，我们得到了 8 个新的 a, b, c, d, e, f, g, h 值。

第四步：更新哈希值

循环结束后，将这一轮计算得到的”工作变量”和该数据块处理之前的”哈希值”进行相加（模 2^32 加法）：

H0 = H0 + a
H1 = H1 + b
...
H7 = H7 + h

好了，一个数据块处理完毕。这个新生成的 H0 到 H7，将作为下一个数据块的”种子”，重复第三步。

第五步：生成最终结果

当所有的数据块都被处理完毕后，最后得到的 H0 到 H7 这 8 个 32 位整数，按顺序拼接在一起，就形成了最终的 256 位 SHA-256 哈希值。

大功告成！

终极问题：为什么我们找不到碰撞？

在理解了 SHA-256 的内部构造后，一个非常核心的问题浮出水面：”既然哈希函数的输入是无限的，输出是有限的，那必然存在碰撞。为什么我们还说它是安全的，而且找不到碰撞呢？”

这是一个绝佳的问题，它触及了哈希函数安全性的根基。要回答它，我们得从两个层面来看：理论层面和现实层面。

理论上：碰撞必然存在（鸽巢原理）

首先，一个残酷但必须承认的事实是：哈希碰撞是 100% 存在的。

这可以用一个我们初中就学过的数学知识来解释，叫”鸽巢原理“（Pigeonhole Principle）：如果你有 10 只鸽子，但只有 9 个鸽巢，那么无论你怎么放，至少有 1 个鸽巢里得挤着 2 只或更多的鸽子。

我们把这个原理套在 SHA-256 上：

鸽巢（输出空间）：SHA-256 的输出长度是固定的 256 位。所以，它能产生的不同哈希值的总数是 2^256 个。这是一个天文数字，但它是有限的。
鸽子（输入空间）：哈希函数的输入可以是任意长度的数据。字符串 “a”、”b”、”hello world”、一部电影、整个互联网的数据…… 输入的可能性是无限的。

好了，现在我们用一个有限的鸽巢，去装无限的鸽子。结果不言而喻：必然会有无数个不同的输入，最终挤在同一个哈希值的”鸽巢”里。

所以，从理论上讲，绝对存在 x != y，但 sha(x) = sha(y)。我们管这种情况叫做”碰撞“（Collision）。

现实中：为什么你就是找不到它

既然碰撞必然存在，那为什么我们还每天放心地用着它，并认为它是安全的？

答案是：因为从理论上的”存在”，到实际上的”找到”，中间隔着一道名为”计算上不可行”的天堑。

这道天堑，就是由 SHA-256 内部那些复杂的设计精心构建的。我们刚刚拆解的那些眼花缭乱的操作，就是为了达到这个目的：

1. 雪崩效应（Avalanche Effect）

这是最核心的一点。一个设计良好的哈希算法，输入的任何一点微小变化（哪怕只改动 1 个 bit），都会导致输出结果天翻地覆、完全不同（理想情况下会有一半的 bit 位发生反转）。

这意味着什么？

没有规律可循：你无法通过观察 hash("abc") 和 hash("abd") 的结果，来推测如何修改输入才能让它们的哈希值更”接近”。两个结果之间看起来是完全随机的关系。
无法”逼近”目标：寻找碰撞不是一个可以逐步优化的过程。你不能像猜数字游戏那样，根据”大了”或”小了”来调整下一次猜测。每一次尝试都是一次独立的、全新的”盲猜”。

这让寻找碰撞变成了一场纯粹的、暴力的、运气差到极点的”抽奖”。

2. 非线性操作（Non-linearity）

我们刚刚分析过的 Ch (Choose) 和 Maj (Majority) 函数是关键。如果整个哈希过程都是线性的（比如只有加法、异或、移位），那密码学家就可以构建一套巨大的线性方程组，然后用计算机”解方程”的方式来找到碰撞。

但这些非线性函数的引入，彻底打乱了这种可能性。它让整个系统变得无法用简单的数学方程来描述和求解。就好像你没法通过分析一块蛋糕的成分，来精确反推出烤箱的温度和烘焙时间一样。

3. 生日攻击（Birthday Attack）与恐怖的 2^128

黑客们也不是只会”盲猜”。他们能用的最有效的寻找碰撞的捷径，叫做”生日攻击“。

这个名字来源于”生日悖论”：一个 23 人的房间里，有两个人同一天生日的概率就超过了 50%。这比直觉要高得多。

应用到哈希碰撞上：我们不需要尝试 2^256 次才能找到一个碰撞。根据概率学，我们只需要计算大约 sqrt(2^256) = 2^128 个不同输入的哈希值，就有很大概率在这些结果中找到一对碰撞。

2^128 次！这看起来比 2^256 小多了，对吧？

但它依然是个无法想象的数字。这么说吧：

假设你拥有当前地球上最强的算力，用全世界所有的计算机一起来算。要想完成 2^128 次 SHA-256 计算，所需要的时间，可能比宇宙的年龄（约 138 亿年）还要长得多得多。

这就是我们说它”计算上不可行“（Computationally Infeasible）的真正含义。它在理论上可行，但在可预见的未来，以人类已知的任何技术，都无法完成。

总结

我们再回顾一下这趟旅程：

打包行李（填充）：把任意长度的数据，按照严格规定打包成一或多个 512 位的行李箱。
设定起点（初始H值）：拿出密码学家给我们的、源于素数平方根的”魔法数字”作为起点。
循环搅拌（压缩函数）：对每一个行李箱，都用一套包含 64 道工序的复杂流程（消息调度、移位、异或、非线性函数）进行搅拌，并把搅拌结果和上一轮的结果混合。
得出终点（最终哈希）：当所有行李箱都搅拌完毕，最后输出的结果就是最终的哈希值。

这套流程被设计得如此复杂和精妙，充满了各种非线性和扩散操作，目的就是为了让它成为一个真正的”单向”过程，让任何试图从结果反推输入的努力，都淹没在计算量的汪洋大海之中。

而正是因为这种”计算上不可行”的特性，我们才能在理论上承认碰撞必然存在的同时，在现实中放心地依赖 SHA-256 来确保数据的完整性。我们不是在和数学博弈，我们是在和宇宙的物理定律、能量和时间本身博弈。

现在，当你再在代码里调用 sha256(data) 时，希望你能会心一笑，因为你已经知道了这台”搅拌机”内部的秘密。