单向哈希算法-提取信息的指纹

想象一下，你有一份非常重要的文件，需要通过网络发送给远方的朋友。但你担心文件在传输过程中可能会被损坏或篡改，无法保证其完整性。

这时，聪明的你想到了一种巧妙的方法：使用单向哈希函数给文件做“指纹”。

第一步：获取文件的“指纹”

[+] 你使用单向哈希函数对文件进行计算，得到一个独一无二的哈希值，就像为文件创建了一个唯一的“指纹”。这个哈希值就像文件的身份证，能够准确地标识文件的原始内容。

第二步：将“指纹”和文件一起发送

[+] 你将文件和哈希值一起打包发送给朋友。就像在文件上盖上了带有你印章的邮戳，这样即使文件在传输过程中出现意外，也能通过“指纹”来验证文件的真实性。

第三步：验证文件的完整性

[+] 朋友收到文件后，也使用相同的单向哈希函数对文件进行计算，得到另一个哈希值。然后，他将收到的哈希值与你发送的哈希值进行比较。

如果两个哈希值完全一致：说明文件在传输过程中没有被损坏或篡改，朋友收到的文件与你发送的文件完全相同。
如果两个哈希值不同：说明文件在传输过程中一定发生了某些改动，朋友收到的文件可能与你发送的文件不一致，存在完整性问题。

在下载 Debian 系统镜像时，官方会一同给出 iso 的文件的哈希值，用户在下载完文件后，可以通过跟官方的值比对是否一致，来确认文件是否完整或是已损坏。

|60%

打开其中的 SHA256SUMS 链接，会列出目录下所有文件的哈希值。

|60%

在哈希函数中，输入的内容称为消息（message），输出的哈希值（Hash Value）也称为消息摘要（Message Digest）或者指纹（fingerprint）。

我们都知道，没有谁的指纹形状是相同的。指纹形状与 DNA 相关，即使是同卵双胞胎，他们的指纹也不会一模一样。单向哈希算法便是提取内容指纹的算法，通过哈希算法，对输入的内容计算出哈希值，而哈希值就是输入内容的指纹。根据不同的输入，输出不同的哈希值，哪怕只有一个比特位不同，输出的哈希值也是不同的。说它是单向的哈希算法，是因为无法通过哈希值反算出内容。

哈希算法历史

哈希函数（又称散列函数）的概念起源于1950年代，当时美国数学家 Michael O. Rabin 和 Robert W. Karp 在研究随机函数时，提出了“通用单向哈希函数”的概念。他们设想了一种函数，能够将任意长度的输入转换为固定长度的输出，并且满足这几个特性：

唯一性：相同的输入将产生相同的输出。
不可逆性：仅根据输出，几乎不可能恢复原始输入。
易于计算：计算输出相对容易，但验证输出是否匹配输入却非常困难。

现代哈希函数的历史可以追溯到20世纪80年代和90年代，在这个时期，许多重要的哈希函数算法被开发出来，并且逐渐成为密码学和计算机科学领域的重要组成部分。

MDA 系列

MDA（Message-Digest Algorithm，消息摘要算法）系列是由美国计算机科学家 Ronald L. Rivest 设计的一组哈希函数。这些算法在数据完整性验证和密码学领域有着广泛的应用。

MD2

1989年，Ronald L. Rivest 发布了 MD2 算法，是最早的 MDA 系列算法，最初设计用在8位操作系统的算法。MD2 算法结构简单，运行速度也不错，但安全性相对较低。2004年，MD2 被发现存在理论上的漏洞，在安全领域不被推荐使用。

MD4

到了1990年，Ronald L. Rivest 发布了 MD4 算法，作为 MD2 算法的改进版本。MD4 算法在运行速度和安全性上比 MD2 算法有所提高，但也存在一些潜在的弱点。1995年，Hans Dobbertin 发现了对 MD4 的碰撞攻击方法，MD4 被证明已经不再安全。

MD5

1991年，Ronald L. Rivest 发布了MD5算法。作为 MD4 的替代，MD5 增加了更多复杂性和安全性，但在安全性和效率方面取得了较好的平衡，很快成为最流行的哈希函数之一。MD5 算法被广泛应用于各种领域，例如文件完整性校验、密码存储、数字签名等。

在1996年，MD5 被发现存在碰撞漏洞。2004年，王小云等人提出有效的碰撞攻击，MD5 在实际应用中已经不安全。2008年，发现 MD5 在实际应用中存在严重安全风险（例如伪造数字证书），不再推荐用于安全应用。2009 年，中国科学院的谢涛和冯登国仅用了 $2^{20.96}$ 的碰撞算法复杂度，破解了 MD5 的碰撞抵抗，攻击测试在普通计算机上只需要运行几秒钟。2011年，RFC 6151 禁止 MD5 用作密钥散列消息认证码。 2017年，Google 的研究人员发现了一种新的 MD5 伪造攻击方法……

MD6

2008年，Ronald L. Rivest 和他的团队，向 NIST 提交了 MD6 作为 SHA-3 的候选算法。由于 MD6 的设计追求高度安全性和灵活性，这增加了算法的复杂性和计算开销，和其它候选算法相比，存在一定性能差距。另外，MD6 的设计相对复杂，缺乏足够广泛的审查和评估，这也导致了它的安全性和可靠性受到质疑。种种原因，MD6 未能成为 SHA-3 标准。

MDA 系列算法在哈希函数的发展过程中起到了重要的作用。虽然早期的 MD2、MD4 和 MD5 由于安全性问题逐渐被淘汰，但它们在数据完整性和密码学研究中提供了宝贵的经验和教训。MD5 尤其重要，它在实际应用中被广泛使用，并且它暴露的安全问题催生了后续更安全的哈希算法（如SHA系列）的发展。尽管 MD6 未被选为 SHA-3 标准，但它的设计理念和结构仍然对哈希函数的研究和开发有着重要影响。

SHA系列

SHA（Secure Hash Algorithm，安全哈希算法）系列是由 NIST 发布的一系列哈希函数。SHA 系列被广泛应用于信息安全领域，例如文件完整性校验、密码存储和数字签名等。

SHA-0

1993年，NIST发布了 SHA-0 算法，这是 SHA 系列算法中的第一个版本。SHA-0 算法在发布后不久就被发现存在安全漏洞，因此很快被 NIST 废弃了。

SHA-1

1995年，NIST 发布了 SHA-1 算法作为 SHA-0 的替代。SHA-1 在安全性、效率和易用性方面取得了不错的平衡，很快成为最流行的哈希函数之一（另一个是MD5）。但是，随着计算能力的提高，SHA-1 算法的安全性也逐渐受到了质疑。

2004年，Rijmen 和Oswald 发表了对 SHA-1 较弱版本的攻击：只需在$2^{80}$的计算复杂度之内就能找到碰撞。

2005年，王小云等人提出了对 SHA-1 算法的碰撞攻击，证明了理论上两个不同的输入能生成相同的 SHA-1 哈希值。虽然真正实施碰撞攻击还需要大量的计算资源，但这也表明 SHA-1 算法的安全存在潜在风险。

2017年2月23日，Google 宣布，他们与 CWI Amsterdam 合作创建了两个不同内容的 PDF，但是有着相同 SHA-1 值，这说明 SHA-1 算法已被正式攻破。

2017年，NIST 宣布逐步淘汰 SHA-1 算法，建议用户迁移到更安全的哈希函数，例如 SHA-2 系列算法。

SHA-2

2002年，NIST 发布了 SHA-2 系列算法，包括 SHA-256、SHA-384 和 SHA-512 等。相比 SHA-1，SHA-2 不仅性能更高，而且抗碰撞性更强，它使用了更复杂的结构，低于伪造的能力也更强，例如，它有着更强的抵御长度扩展攻击能力。

SHA-2 系列算法的发布，为哈希函数的发展奠定了新的基础。它广泛应用在数字签名、文件完整性校验等领域，是目前最主流的哈希函数之一。

SHA-3

2015年，NIST 发布了 SHA-3 算法。与 SHA-2 系列算法完全不同。SHA-3 算法采用选拔的机制产生的，它使用了全新的结构，具有高度的安全性和抗碰撞能力，抗碰撞性比 SHA-2 系列算法高出很多倍。

SHA-2

目前最常用的单向哈希算法当属 SHA-2 系列了，SHA-2 算法的输出长度是固定的，根据不同的输出长度，实际上分为多个不同版本：SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。其中 SHA-256 输出值长度是256比特位，SHA-512 输出值长度是512比特位。SHA-512/256 实际上是SHA-512，输出512长度，但是截断了一部分，实际只输出256。

下面以 SHA-256 为例，简单看一看SHA-2系列算法的内部原理。

先对对信息进行预处理，就是在消息后面补足需要的信息，使其满足特定的结构：$M \bmod 512 = 0$，这里分成两步。

第一步对消息末尾附加比特信息，使其满足 $消息 \mod 512 = 448$。先补1，剩下的用0补足。即使消息恰好满足条件，也需要用同样的规则多补512个比特位。也就是说，这一步至少需要填充1个比特位，最多448个。

第二步继续附加64个比特位的原始消息长度信息，连同上一步多出的448，正好凑成512个比特位：$448+64=512$。

[!TIP] 提示
这一步也表明了 SHA-256 能处理信息的最大长度是$2^{64}-1$比特。

计算过程用到8个初始值和64个常量，其中对最小的8个质数的平方根的小数部分取前32位，得到的结果作为8个哈希初始值。64个常量也类似，不过有一点不同，它取的是前64个质数的立方根小数部分的前32位。

接着消息会被切分成多个长度为512的块。然后使用前面8个和64个初始值，先对第一个块进行一系列的逻辑位运算，得出256比特消息摘要，正好是8个32比特。对消息块的计算迭代64轮。上一个块的消息摘要输出参与下一个块的计算，依此类推，直至最后一个块，就是整个消息的哈希值。

SHA-3

随着计算能力的不断提高，MD5、SHA-0 和 SHA-1 先后被攻破，虽然 SHA-2 目前没有出现明显的弱点，但是以史为鉴，2007年，NIST 着手为未来替代 SHA-2 寻找一个新的标准。不同于以前的 SHA 标准，SHA-3 是通过竞赛产生的，就像 AES 那样。

SHA-3 的选拔过程历经数年。来自世界各国的密码学家们总共提交了64个算法，经过初步评估和公开评审，NIST 选定了5个最终候选算法，分别是：Blake、Grøstl、JH、Keccak 和 Skein。经过多轮评审，最终 Keccak 算法脱颖而出，成为 SHA-3 最终标准。

SHA-3 是一个全新的哈希算法，跟前代的结构完全不同。Keccak 采用了海绵结构（sponge construction）。输入的数据经过填充后，进入两个阶段：吸收（Absorbing）阶段和挤出（Squeezing）阶段。吸收阶段将输入消息分成块，然后逐步吸收到海绵状态中，接收任意长度的比特流输入。挤出阶段从海绵状态中提取任意长度的输出，生成最终的散列值。

Keccak 算法海绵结构的核心是压缩函数和状态更新函数。Keccak 先初始化状态，用一个 5×5×w 的三维比特数组表示，w 通常为 64（即 5 × 5 × 64 = 1600 比特）。

接下来经过吸收阶段，输入的消息被分成多个块，用 r 表示。对每个块，将其异或到状态的前 r 比特中，然后对状态应用压缩函数 f。压缩函数由一系列非线性变换组成，称为轮函数，每一轮包括这些步骤：

θ (Theta)：列混合，将每一列中的比特与相邻两列的某些比特进行异或运算。
ρ (Rho)：比特移位，对每个比特位置进行循环移位。
π (Pi)：比特置换，重新排列比特位置。
χ (Chi)：非线性混合，将每个比特与其它比特进行非线性混合。
ι (Iota)：常数加法，将常数加到状态中，增加额外的安全性。

最后来到挤出阶段，从状态的前 r 比特中提取输出，将 r 比特提取到输出缓冲区。如果输出不够，再次对状态应用压缩函数 f。

SHA-3 的计算速度与 SHA-2 相当，在大多数应用场景中，他们的性能差异可以忽略不计。在某些特定的场景中，SHA-3 可能略微优于 SHA-2。例如，在需要高吞吐量的应用中，SHA-3 的并行化性能更好。另外，SHA-3 能计算的信息的大小是没有上限的，也支持输出不同长度哈希值，这两点是 SHA-2 做不到的。到目前为止，虽然还没有已知针对 SHA-2 的有效攻击，但是在需要保证更长久哈希安全的领域，例如区块链，加上其灵活性，SHA-3 是更好的选择。