校验和、哈希值

贡献者： addis

　　¹校验和（checksum）是指一类算法，可以将任意字节的数据（以下统称为文件）转换为一个简短的值。我们通常也将其称为文件的指纹（fingerprint）或者哈希值（hash）²。这可以用于检查两个文件的内容是否相同。

　　 通常来说，文件在储存或传输的过程中有一定可能会被损坏，例如网络故障，黑客攻击，或者储存介质的个别字节出现故障。如果我们知道文件原来的校验和，就可以随时重新做一次校验和，如果结果和以前不一样，就说明文件被改变了。这也是为什么一些网站的提供文件下载时同时也会提供各种校验和，以便用户下载以后对照校验和确保文件无误。

1. 碰撞

　　 然而要达到上述目的，理想的情况就是确保任何文件和它的指纹都是一一对应的。但实际上，我们只能确保内容相同的文件得到同样的指纹，或者说不同的指纹必定对应内容不同的文件。不同的文件有可能对应相同的指纹，我们把这种情况叫做碰撞（collision/clash）。

　　 哈希碰撞的概率通常很小，但却无法避免。例如某文件有 100 个比特，那么就有可能有 $2^{100}$ 种不同的内容，但如果哈希值只有 10 个比特，那么只可能有 $2^{10}$ 个不同的哈希值，所以必定会出现碰撞。为了减小碰撞的可能性，我们可以使用更好的算法，或者用更长的指纹。

　　 为什么不同的算法会影响碰撞的可能性呢？我们可以考虑一个最简单的算法：把文件中每个字节对应的整数相加得到指纹。这显然是一个不好的算法，因为实际操作中很可能会出现两个文件仅仅存在字节顺序上的不同，例如 abcd 和 dcba 按照这个算法得到的结果都是一样的。所以好的算法在于能尽量减小实际使用时发生碰撞的概率。

2. 安全性

　　 除了碰撞，一个校验和算法的安全性也十分重要。安全性是指能否创造或修改某个文件，使得它具有指定的指纹。这种操作越难实现，算法就越安全。

　　 例如一个黑客在某文件被传输时将其篡改，为了防止被发现，将其篡改的文件略作不重要的修改使其具有和源文件相同的指纹，那么即使文件的接收者对比指纹，也不会有所察觉，这就使得这个算法不安全。

用于服务器保存密码

　　 网站的服务器中经常使用某种安全的指纹算法保存密码。这是因为如果一个网站的服务器中直接保存用户的密码明文，那么一旦这些明文密码被泄露，那么得到密码的人将可以任意访问用户的数据。

　　 更好的做法是服务器仅仅保存每个用户密码的哈希值，用户每次输入密码时，服务器先将密码转换为哈希值再验证是否正确。这样即使这些哈希值泄露，也不能把他们作为密码直接使用，或者逆向得到密码原文。

3. 常用算法

　　 SHA1（Secure Hash Algorithm 1）著名文件版本控制软件 Git 就是使用 SHA1 散列值来检查文件是否发生变化。这是一个广泛使用的算法，但 SHA1 已被破解，所以安全性无保障。

　　 MD5 是一个更安全的算法。

4. 常用软件

　　 大部分时候我们在命令行中操作，如 linux 的 sha1sum 文件名, md5sum 文件名 等命令，但也有一些软件提 GUI 界面，可以通过鼠标右键菜单的方式获得校验和，如压缩软件 7zip。

　　 Linux 用 find 文件夹 -type f -exec sha1sum {} \; | sort | sha1sum 可以对比两个文件夹。对比包含文件名，文件夹名，和每个文件的 hash，不包括 metadata（例如权限，最后修改时间等）。

1. ^ 本文参考 Wikipedia 相关页面。
2. ^ 严格来说这些不是同义词，但人们经常混用