校验和、哈希值

                     

贡献者: addis

预备知识 计算机文件简介

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

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

1. 碰撞

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

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

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

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. ^ 严格来说这些不是同义词,但人们经常混用


致读者: 小时百科一直以来坚持所有内容免费无广告,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元,我们一周就能脱离亏损, 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利