给电脑装个Linux系统我才很多人都王国，之前也下载了一个 Linux ISO 镜像，准备装虚拟机。结果安装到一半报错，说文件损坏。我检查了一下发现是下载过程中网络断了续传导致的——下载器没有做完整性校验，续传回来的数据混在一起了。
从那之后，我养成了一个习惯：下载大型文件后先比对哈希值再使用。
这就是数据完整性校验最朴素的应用场景：确认你拿到的数据跟发送方发出的数据是同一个东西。
从最简单的校验和方法开始
CRC 和哈希函数是高阶的手段，但在讨论它们之前，先看最原始的校验方法——校验和（Checksum）。
最简单的校验和就是把数据所有字节加起来，取结果的一部分。比如：
数据: [0x48, 0x65, 0x6C, 0x6C, 0x6F]
校验和: (0x48 + 0x65 + 0x6C + 0x6C + 0x6F) & 0xFF = 0x2E
传输时把校验和和数据一起发过去。接收方收到后重新算一遍校验和，如果结果不一样，说明数据在传输中被改变了。
这个方法的问题非常明显：如果有两个字节发生了交换，或者一个字节增 1 另一个字节减 1，校验和完全一样。比如 [0x48, 0x66] 和 [0x49, 0x65] 的校验和都是 0xAE，但数据不同。
之前也有遇到，在调试串口通信协议，发送方不断重传同一包数据，但接收方收到的数据和校验和都对上了——就是数据不对。后来发现是两个字节互相颠倒了，简单的加法校验和完全检测不到。
所以简单校验和只适合对完整性要求不高的场景，比如 TCP 头部校验。对数据正确性要求高的场景，需要更可靠的校验方法。
CRC，更聪明的除法校验
CRC 的核心思想是把数据看作一个巨大的二进制数，然后用一个约定的"生成多项式"去除它，把余数当作校验码。
这个思路跟加法校验和的区别在于：CRC 用的是模 2 除法（不带进位的二进制除法），本质上是一种多项式环上的运算。
举个例子。假设生成多项式是 x³ + x + 1，二进制表示为 1011。要计算数据 1101 的 CRC-3 校验码，步骤是：
- 在数据末尾补 3 个 0（阶数等于多项式的阶数）
- 用 1011 做模 2 除法
- 余数就是 CRC 码
模 2 除法跟普通除法的区别是：它用 XOR 代替减法，不进位也不借位。这意味着它可以用移位寄存器加 XOR 门电路在硬件里极高效地实现。
这就是 CRC 能在网卡、硬盘控制器等硬件里广泛使用的原因：它只需要几个逻辑门和移位寄存器，不需要 CPU 参与。
CRC 的检错能力比简单校验和强很多。它保证能检测到：
- 所有单比特错误
- 所有双比特错误（只要多项式选得合适）
- 任意奇数个错误
- 所有长度不超过多项式阶数的突发错误
- 更长的突发错误，检测率为 1 - 2^(-r)
因为最后一条，CRC-32（使用 32 位多项式）检测长突发错误的失败率只有 1/2³² ≈ 0.00000002%。对大部分工程应用来说，这个概率够低了。
哈希函数，从完整性校验到安全校验
CRC 有一个本质缺陷：它是线性的。如果你知道 CRC 的算法和多项式，你可以故意篡改数据并重新计算正确的 CRC 码。CRC 的设计目标是检测"随机错误"，而不是"恶意篡改"。
这就是加密哈希函数（也叫密码学哈希函数）登场的地方。
哈希函数对数据做不可逆的压缩映射。它的核心性质有三条：
抗原像性：给定哈希值 h，很难找到任意数据 d 使得 hash(d) = h。换句话说，你不能从哈希值反推出原文。
抗第二原像性：给定数据 d1，很难找到另一个不同的数据 d2 使得 hash(d1) = hash(d2)。
抗碰撞性：很难找到任意两个不同的数据 d1 和 d2 使得 hash(d1) = hash(d2)。
这些性质保证了哈希函数的安全性。如果有人篡改了文件，他无法计算出对应的正确哈希值（除非他控制了哈希值的发布渠道）。
常见哈希函数的输出长度：
- MD5：128 bits（16 字节），已被证明存在碰撞攻击，不推荐再用
- SHA-1：160 bits（20 字节），2017 年 Google 展示了实际碰撞攻击
- SHA-256：256 bits（32 字节），目前认为安全
- SHA-3：输出长度可配置，最新的 NIST 标准
但是等等，这里有个坑：MD5 和 SHA-1 虽然被"破解"了，但那是针对抗碰撞性——你能找到两个碰撞对，但你不能根据给定的哈希值反推出原文。在大多数完整性校验场景（检测随机损坏）中，MD5 仍然够用。但在安全场景（检测恶意篡改）中，绝对不行。
Merkle 树，大规模数据的校验
如果你要校验一个 4GB 的文件，下载完整文件再算一次 SHA-256 是可行的。但如果你要校验的是一个分布式文件系统里不断变化的海量数据呢？
Merkle 树（也叫哈希树）解决的就是这个问题。
原理是把数据切分成很多小块（比如每个 1MB），每个小块算一个哈希值，然后把相邻的哈希值两两拼接再哈希，逐层往上，最后得到一个根哈希。
这样做的好处是：你不需要下载完整数据就能验证某个部分是否正确。只需要从数据源拿到从当前块到根哈希路径上的兄弟哈希值，就能验证这个块是否属于这棵树。
比特币和 Git 都用了 Merkle 树的思想。Git 的每次提交都有一个 SHA-1 哈希，这个哈希包含了树对象、父提交、作者等信息。你验证一次 git log 就能确认整个提交历史的完整性。
Git 早期用 SHA-1 在 2017 年之后引起了争议，因为 SHA-1 的碰撞攻击已经被实现了。但 Git 的实际安全性不是来自 SHA-1 的抗碰撞性，而是来自 Git 的数据模型——要篡改历史必须同时修改所有后续提交的哈希值，而这在分布式环境下几乎不可能不被发现。但 Git 还是从 2.47 版本开始正式支持 SHA-256 了。
实际用到的场景
文件下载校验。 很多开源软件下载页会提供 SHA-256 校验码。下载后用 sha256sum 命令比对一下：
sha256sum ubuntu-22.04-desktop-amd64.iso
如果跟官网的哈希值一致，文件就是完好的。这个习惯能帮你避免下载到被篡改的版本——不过前提是 HTTPS 证书没被伪造，或者你从多个独立来源交叉验证了哈希值。
分块上传。 上传大文件到云存储时，客户端和服务端会在每个分块上传完成后校验 CRC 或 MD5。如果校验不一致，服务端会要求客户端重传这个分块。AWS S3 的多部分上传就是用 ETag（通常是 MD5）来做分块校验的。
数据库校验。 有些数据库系统会在每一页数据末尾存储 CRC 值，读数据时校验。MySQL 的 InnoDB 引擎从 5.6 版本开始默认对每页数据做 CRC-32 校验，防止半页写入（partial page write）导致的数据损坏。
二维码容错。 QR 码用的是 Reed-Solomon 纠错码，跟 CRC 一样基于多项式除法，但 Reed-Solomon 不仅能检错还能纠错。本质上它们是同源的——都是从多项式环上的代数性质派生出来的编码技术。
如果想计算这些值，可以用在线的MD5 哈希工具和 SHA 哈希工具，计算字符串和文件的哈希值，方便验证下载的文件或者做数据比对。
写在最后
CRC 和哈希函数解决的是同一个问题的不同层面：CRC 检测"意外损坏"，哈希函数检测"恶意篡改"。在传输通道不可靠但无恶意的场景（如网络传输、存储介质）用 CRC，在需要防止主动攻击的场景（如软件分发、密码存储）用加密哈希。
Merkle 树在这个基础上增加了一个能力：你不需要拿到全部数据就能验证某个部分。这个特性对大规模分布式系统来说，是基础性的。