密码哈希函数的历史

密码哈希函数（Cryptographic hash function）自 1980 年代以来就已存在，并在密码学、数据完整性验证、数据库索引等领域得到了广泛应用。

在运算密码哈希函数时，我们会输入任意长度的数据，对应函数会将其转换为固定长度的输出值。输入数据时，把不同栏位的字元放进某个公式中去计算，这个行为通常被叫做杂凑或散列（Hash，因此哈希值又译杂凑值/散列值），此时输出的值被叫做哈希值，这个公式本身被叫做哈希函数。

我们生活中的例子之一，是使用 P2P 下载器时常会看到的 MD5 算法，它就是一种密码哈希函数，长度为 128 位元。用户下载完档案后可以将得到的哈希值与发行者提供的哈希值进行比对，如果两个值一样，则可以认为档案大概率没有被篡改。

另一个常见的例子是一般网站的密码验证。大部分网站的后端数据库并不会直接储存使用者的密码，因为假如后端数据库外泄，后果可想而知。正常的流程时储存用户设置密码的对应哈希值，当用户输入密码时，要验证密码是否正确，只需要运算原本使用的哈希函数得到哈希值，再与后端数据库的对应用户名比对是否一致。由于哈希值「抗原像攻击」的特点，就算骇客拿到了后端数据库的所有哈希值，也无法反推出用户的密码。

密码哈希函数的特性

如果以「SHA256 Generator」作为关键字，找到任意一个 SHA256 的在线生成器，你会发现不论使用哪个网站的相同算法、不论试多少次，相同的文字总是会生成相同的哈希值。

另外，上面的文字稍微改变了一下大小写，输出的哈希值就完全不同，这又被称为雪崩效应（Avalanche effect）。以下这些特性，主要是衡量密码哈希函数是否足够安全：

• 抗原像攻击（Pre-image resistance）：很难根据输出的哈希值，反推出原本输入的值，这与单向函数的属性有关。

按照上面的例子，骇客很难根据盗窃来的哈希值，反推出用户原本的密码。这是由于密码哈希函数涉及到多次的运算和浓缩信息，因此不太可能将输出结果回推出原本的文本，一般认为密码哈希函数的运算过程应该是单向、不可逆的。

• 抗二次原像攻击（Second pre-image resistance）：给定一个输入的值，很难找到另一个值也可以生成出相同的哈希值。 **这个特性又被称作弱抗碰撞性。

• 抗碰撞性（Collision resistance）：很难找到两个不同的值，可以输出相同的哈希值。我们把这两个值称为密码哈希碰撞，这个特性又被称为强碰撞性。

以上面提到的 MD5 为例，有没有可能档案不同，但生成的哈希值一样呢？答案是有的，但概率极低，这就叫密码哈希碰撞，可以分成偶然发生或蓄意攻击两种情况。标准的 MD5 算法碰撞概率在1/2¹²⁸左右，偶然发生的概率非常低，但MD5 已被认为可能遭受蓄意的碰撞攻击，因为让两个纯文本产生一样的哈希值是相对容易的；所以MD5 在不涉及安全性的任务上这个算法还可以用，安全性认证（比如金钥认证/数位签章等）则已不适用。

密码哈希函数在区块链中的应用

以太坊使用的密码哈希函数是 KECCAK-256，不少人都把这个函数误认为 SHA-3（包括 Celestia 创始人的博士论文），因为这个函数早期在 Solidity 中就被写作 sha3。后来因为太过混淆，被提 issue 改成了 Keccak256。

MetaMask 这使用了多个密码哈希函数，流程是这样的：

1.你会先得到由 12 个单词组成的一组助记词，它们是来自 BIP39提案的 2048 个单词随机排列组合而成。
2.每个单词有对应的数值。因此助记词可以组成一串数值，被称为种子整数（seed integer）。
3.拿到种子整数后，MetaMask 会对种子整数使用SHA-256 函数，生成的哈希值为私钥（Private key），这就是有时在新设备「导入已有钱包」时要输入的值。
4.接着 MetaMask 会对私钥使用椭圆曲线算法（ECDSA），生成一个公钥（Public key）。
5.最后MetaMask 会对公钥使用Keccak-256 函数生成一个哈希值，取该哈希值的最后20 个字节（换算成十六进位，即40 个字母或数字的长度），再加上0x 作为前缀，成为以太坊地址。

密码哈希函数在区块链中的工作原理

而比特币使用的密码哈希函数是 SHA-256，下面我们会以挖矿来解释比特币矿工是如何运算密码哈希函数。

在比特币挖矿中，矿工会将待处理的比特币交易数据与一个称为「区块头」的信息进行组合。区块头包含了交易数据以及一些其他的元数据，如时间戳和随机数。矿工的目标是通过不断调整区块头中的随机数（称为「nonce」）来尝试生成一个特定的SHA-256 哈希值，这个哈希值必须满足一个预定的条件，通常是以一定数量的前导零开头。由于 SHA-256 哈希函数的性质，只有不断尝试不同的随机数才能找到满足条件的哈希值。

一旦一个矿工找到了符合条件的哈希值，他们就可以将该区块添加到比特币网络的区块链中，并获得一定数量的比特币作为奖励。这个过程称为「挖矿」，通过不断地进行运算哈希函数，来寻找满足条件的哈希值。

除了挖矿，区块之间的连结与交易的变更也和密码哈希函数有关。哈希指针（哈希指针）是一种数据结构，它可以让我们索引数据、取回数据并验证数据是否发生改变。区块链先将每笔交易进行哈希处理，然后再将它们分组为区块。接着哈希指针透过保存前一个区块中数据的哈希值，从而将每个区块连结到其前一个区块，由于每个区块都与其前一个区块相关，因此区块链中的数据是不可变的，意味着任何交易的变更都会产生完全不同的哈希值，将改变所有后续区块的哈希值。一个实际的例子，**假设我们有一个区块链，其中包含两个区块：

• 区块 1：包含交易 T1、T2 和 T3 的哈希值。

• 区块 2：包含交易 T4、T5 和 T6 的哈希值，以及区块 1 的哈希值。

如果有人想要篡改区块 1 中的交易 T1，那么他需要重新计算区块 1 的哈希值，并将新的哈希值更新到区块 2 中。但是，由于密码哈希函数具有抗原像攻击的单向性，因此很难根据区块 2 中的哈希值反推出区块 1 中的交易 T1。

此外，由于区块 2 中包含了区块 1 的哈希值，因此如果区块 1 被篡改，那么区块 2 的哈希值也会发生变化。这意味着，如果有人想要篡改区块链中的任何一个区块，他都需要同时篡改所有后续的区块，这是非常困难的。因此，密码哈希函数可以有效地确保区块链数据的一致性和完整性。

我们可以发现，密码哈希函数在区块链中扮演的角色为：

• 区块连结：每个区块的头部都会包含前一个区块的哈希值，这样可以将所有区块连接起来，形成一个不可篡改的链。

• 交易验证：交易数据会运算哈希函数，然后将对应的哈希值包含在区块中。这样可以验证交易的真实性和完整性。

• 共识机制：在工作量证明（PoW）的共识机制中，矿工需要通过运算哈希函数来找到符合难度要求的 nonce 值。

密码哈希函数的未来

2022年9月2日，Vitalik 在 Twitter（X）上发了一个题目，问如果使用 Shor 算法的量子电脑如果被发明，哪一种密码哈希函数还是安全的？

来源：Vitalik 推文

他表示，能够使用 Shor 算法的量子电脑可以突破：RSA（一个历史悠久的公钥密码系统）或任何基于因式分解的东西、椭圆曲线（Elliptic curves）、未知阶的群（Unknown order groups）。

而哈希值（如 SHA-256）在量子计算机中存活得很好，虽然安全性将会有所下降，建议使用更长的哈希值。

结论

密码哈希函数，比如 SHA-256，到底有多安全可靠？这里的 256 是指 2 的 256 次方，这个数字已经大到我们很难有个具体的概念。

来源：3Blue1Brown

不过，3Blue1Brown 做过这样一个动态的比喻，或许可以帮助我们理解密码哈希函数的安全性：假设地球上40 亿人，每人都有一台超高算力的电脑，相当于Google 在全世界所拥有的算力的1000 倍；同时银河系中有40 亿颗我们这样的星球、又有40 亿个类似银河系的星系一起运算哈希函数，也要经过大于5000 亿年才会有40 亿分之一的机率猜中「究竟是输入了什么才能得到SHA-256 输出的特定哈希值」。