哈希到底是个啥？

查克

发布于 2024-12-06 12:40:38

2930

文章被收录于专栏：碲矿碲矿

TL;DR[1]: 通过任意函数，把任意长度数据映射成固定长度数据，那么最终得到的这个固定长度的数据，就叫做哈希或者哈希值，这个函数叫做哈希函数，这个过程也可以叫哈希。（🤣看来哈希可以做动词、名词和形容词，难以理解也是情有可原。）

1 从奇偶校验说起

学通信或者搞嵌入式的，对奇偶校验应该是比较熟悉的；至少是听说过的。这里的 奇 和 偶 是针对数据中 1 的个数而言的。在串口通信中奇偶校验很常用。

1.1 奇校验与偶校验

1.1.1 奇校验

校验位补 0 或者 1，使信息中 1 的个数为奇数个。假设每个信息单元为 8 位，包括 7 位数据与 1 位校验码，那么对信息 0000 001（二进制）作奇校验，则最后一位校验码应该为 0，以使整个信息串中 1 的个数为奇（单）数个。信息串变为：0000 0010（最后一位是校验码）。

信息接收方收到信息后，会检查前 7 位：0000 001（二进制），然后根据奇校验规则，可知最后一位应该为 0，比较一下，如果最后一位确实为 0，那么便认为信息传输没有差错；否则，便认为信息传输出现差错，请求重新发送信息。

1.1.2 偶校验

校验位补 0 或者 1，使信息中 1 的个数为偶数个。假设每个信息单元为 8 位，包括 7 位数据与 1 位校验码，那么对信息 0000 001（二进制，通常用 0b 为前缀：0b0000 001）作奇校验，则最后一位校验码应该为 1，以使整个信息串中 1 的个数为偶（双）数个。信息串变为：0b0000 0011（最后一位是校验码）。

信息接收方收到信息后，会检查前 7 位：0b0000 001（二进制），然后根据偶校验规则，可知最后一位应该为 1，比较一下，如果最后一位确实为 1，那么便认为信息传输没有差错；否则，便认为信息传输出现差错，请求重新发送信息。

1.2 奇偶校验的局限

其实前面的分析是有漏洞的。假设采用奇校验，要发送的信息为 0b0000 001，那么信息串应该为：0b0000 0010（最后一位是校验码）。

1.2.1 错序

如果接收方接收到的信息串是 0b0000 0100，那么符合奇校验规则（信息串中有奇数个 1 ），但信息却是错的！

1.2.2 错码

如果接收方接收到的信息串是 0b0000 1110，那么符合奇校验规则（信息串中有奇数个 1 ），但信息却是错的！

1.2.3 前导零

如果接收方接收到的信息串是 0b0000 0000 1110，那么符合奇校验规则（信息串中有奇数个 1 ），但信息却是错的！

这两种情况，偶校验也一样不能幸免。扯远了，再远一点可以扯到纠错码，跟 “摘要” 差点有点远，先收回来吧（其实是我自己也几乎忘光光了 -_-!!）。

为什么从奇偶校验说起呢？因为奇偶校验可以理解为最简单的 “摘要”（哈希、散列）——把一串信息，映射成 0 或者 1。但因为结果的 “空间” 太小了（只有 0 和 1），所以会有大量 “重合”（不同的信息映射成一样的结果），术语叫“哈希碰撞”（collision）。

2 再谈谈 CRC 校验

上面介绍的奇偶校验只能检测奇数位错误，不能检测错序错误和偶数位错误。有理由相信，CRC （Cyclic Redundancy Check，循环冗余校验）是为解决这问题而出现的。

CRC 校验的计算是通过一种称为 模 2 除 的计算方法，其中，信息作被除数，生成项 作除数（先别问什么是生成项，就当它是个除数），余数即为校验码。模 2 除 不需要借位，直接进行异或（不同为真：1 xor 1 = 0，1 xor 0 = 1，0 xor 0 = 0）。咱们从最简单的校验码开始—— 1 位的校验码。

2.1 CRC-1

假设信息为 0b0000 001，生成项为 0b10，校验码是 1 位，需要在信息后面补一个零。下面进行 模 2 除：

CRC-1a

最后的余数就是校验码，即 0，所以信息串为：0b0000 0010（最后一位是校验码）。

假设信息为 0b0000 001，生成项为 0b11，校验码是一位，需要在信息后面补一个零。下面进行 模 2 除：

CRC-1b

最后的余数就是校验码，即 1，所以信息串为：0b0000 0011（最后一位是校验码）。

细心的朋友可能已经发现：信息为 0b0000 001，生成项为 0b10 时，校验码为 0，跟奇校验一样；生成项为 0b11 时，校验码为 1，跟偶校验一样。这并非巧合，奇偶校验其实就是对应不同生成项的 CRC-1 。

2.2 CRC-4

我们跳过 CRC-2，CRC-3（原理是一样的），直接来看 CRC-4 吧。假设信息为 0b0011 0101 1011，生成项为：0b1 0011，校验码是四位，需要在信息后面补四个零（四就是所谓的 位宽）。下面进行模 2 除：

CRC-4

最后的余数就是校验码，即 1110，所以信息串为：0b0011 0101 1011 1110（最后四位是校验码）。对方接收到信息串后，以同样的方法对前 12 位信息进行 CRC-4 校验算出校验码，并将算出的校验码与接收到的校验码比对，如果一样则认为信息传输无误，否则认为传输有误请求重新发送。

CRC-4 的错误检测能力比 CRC-1（奇偶校验）要强些，因为 CRC-4 的“冗余量”（4 位）CRC-1（1 位）更大了。

2.3 CRC 家族

CRC 家族[2]里的其他成员，包括：CRC-5，CRC-7，CRC-8，CRC-16，CRC-32，CRC-64 等等，原理都是一样的：模 2 除（异或）。而最后生成的校验码的检错能力跟生成项有很大的关系。这些生成项都是经过众多专家们研究的，常用的有：

名称	多项式
CRC-1	（用途：硬件，也称为奇偶校验位）
CRC-5-USB	（用途：USB 信令包）
CRC-7	（用途：通信系统）
CRC-8
CRC-16-IBM	（用途：Modbus）
CRC-32-IEEE
CRC-64-ISO	（用途：ISO 3309）

在原始的 CRC 校验方法中，前导零和后继零不影响最后校验码，所以产生了各种 CRC 变形。（参见 变体[3]）

3 消息摘要

3.1 MD5（Message Digest 5）

虽然 CRC 能够生成摘要，但 CRC 是因校验而产生的，也用在校验上比较多。MD5 [4] 是消息摘要“专业户”，MD 就是信息摘要。本质上， MD5 跟 CRC 是一样的：通过一系列运算（移位、求和、异或、取反），得到一定位数（通常是 128 位）的“校验值”（摘要）。

MD5 的计算过程如下：

MD5

一个 MD5 运算：由类似的 64 次循环构成，分成 4 组 16 次。一个非线性函数；一个函数运算一次。表示一个 32-bits 的输入数据，表示一个 32-bits 常数，用来完成每次不同的计算。

多说一句，时常看到有人把 MD5 和 Base64[5] 叫做加密，这是不准确的——虽然有时候它们确实也能起到“加密”的作用。加密通常伴随着解密，而且通常是指只有拿着密钥或者方法的人才能解密。

MD5 是把信息生成摘要，并不可逆（没办法根据摘要，还原出原来的信息），显然不符合加密的需求。

Base64 则通常是把二进制数据编码成文本数据，无需密钥也可以解码成原来的数据，显然也不符合加密的需求。

3.2 SHA （Secure Hash Algorithm）

终于又到哈希了，相信一路看下来，对什么是哈希已经有概念了。SHA 可以理解为加强版 MD5，它的“校验值位数”更长了， SHA-1[6] 的摘要多达 160 位。SHA-1 的计算过程如下：

SHA-1

SHA-1 压缩算法中的一个循环。, , , 和是这个中的 32 位数；是会变化的非线性函数；<<<nbit="" 向左循环移动="" n="" 个位置。n="" 因操作而异。="" 田="" 2^{32}="" 之下的加法，k_t="" 是一个常数。<="" p="">

而 SHA-2[7] 就是加强版的 SHA-1，它的计算过程如下：

SHA-2

SHA-2 的第个加密循环。图中的深蓝色方块是事先定义好的非线性函数。ABCDEFGH 一开始分别是八个初始值，是第个密钥，是本区块产生第个 word。原消息被切成固定长度的区块，对每一个区块，产生个 word（视算法而定），透过重复运作循环次对这八个工作区段循环加密。最后一次循环所产生的八段字符串合起来即是此区块对应到的散列字符串。若原消息包含数个区块，则最后还要将这些区块产生的散列字符串加以混合才能产生最后的散列字符串。

哈希

说了这么多，哈希到底是个啥？咱也不自己编了，引用维基百科[8]吧：

A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes. The values are usually used to index a fixed-size table called a hash table. Use of a hash function to index a hash table is called hashing or scatter storage addressing.