# 解密密码学：散列函数 By [eastmoney](https://paragraph.com/@eastmoney) · 2022-06-05 --- 散列函数是一种确定性数学函数，可将任意大小的某些输入映射到固定长度的输出。 介绍 -- 人类对密码学或相互编码/解码秘密信息的科学感兴趣，至少与有记录的历史一样长。¹然而，这个领域已变得越来越重要，并且与数字时代的每个人都息息相关。现代密码学让我们可以安全地访问 Web 服务，而不会泄露敏感的个人信息。它确保了数十亿美元的电子商务交易以及 SWIFT 银行间转账。最近，密码学形成了基于比特币等加密货币的全新金融范式的基础。 尽管互联网用户每天都依赖它，但密码学仍然显得神秘而神秘。幸运的是，我们不必知道它是如何工作的就可以欣赏它的好处。但是一点点理解可以帮助我们所有人成为更明智的用户。如果你很好奇（像我一样），知道某些东西在幕后是如何运作的也可以带来满足感甚至快乐。 这篇文章是关于区块链和数字货币中使用的密码学系列的第一篇。我们将研究的第一个原语是 _加密散列函数_。密码散列函数非常重要，以至于它们通常被称为现代密码学的“主力”。对于加密货币，这些功能构成了工作量证明等共识算法的基础。 快速免责声明：这篇文章（和系列文章）是为感兴趣的、受过教育的外行而不是学术研究人员写的。所以我可能对正式的定义有点“松散”来理解这一点。但是对于那些对更正式的主题处理感兴趣的人，我将链接到文章底部的一些资源。² 什么是哈希函数？ -------- 散列函数是一种确定性数学函数，可将任意大小的某些输入映射到固定长度的输出。一个简单的例子是一个函数，它根据您姓氏的第一个（英文）字母返回一个数字。无论您的姓氏有多长，该函数的输出都将是 1 到 26 之间的某个（最多 2 位）数字。由于该函数是确定性的，相同的输入每次都会产生相同的输出。 尽管散列函数的输入长度不必长于输出，但我们通常希望散列函数可以压缩。对于上面的示例，我们采用了可以构成姓氏的所有可能的英文字母组合，并将它们映射到 26 个可能的选项。这些数据比全长输入更容易搜索和存储。 当然，精明的读者已经意识到我上面的示例哈希函数存在一个明显的问题。如果两个姓氏以相同的字母开头，则哈希值将相同。这称为 _冲突_，在这种情况下，我们不能仅根据他们姓名的哈希值来区分两个人。因此，即使我们的哈希函数帮助我们节省了存储空间，它也压缩 _了太多_ 有用的信息。 加密哈希函数 ------ 加密散列函数在 1970 年代被形式化，从那时起几乎被集成到从对称密钥推导到零知识证明的所有事物中。它们是更广泛的哈希函数家族的子类，旨在帮助加密方案。特别是，在各种情况下应该很难找到碰撞。不同类型的抗碰撞性定义如下。 碰撞阻力——对于散列函数 H(x)，应该很难找到 _任何_ 碰撞。也就是说，应该很难找到两个输入 x\_1 和 x\_2，其中输出相同 (H(x\_1) = H(x\_2))。因为这个函数的可能输入多于可能的输出，所以 _肯定_ 有冲突。但是在 输出空间_足够大_ 的情况下，碰撞的概率应该可以忽略不计。  Target Collision Resistance —如果很难找到 _对手选择_ 的输入值的冲突，则哈希函数 H(x) 是 _抗目标冲突的。_ 第二原像抗性——如果对于 _随机选择_的 输入值很难找到冲突，则哈希函数 H(x) 是抗第二原像的。换句话说，第二原像电阻描述了每个输出有效独特的程度。 抗原像性——如果你只知道哈希函数 H(x) 的输出，就很难找到 x。换句话说，原像电阻意味着很难对 CRHF 的输出进行“逆向工程”以找到其输入。抗原像的函数有时也称为单向函数⁴，这意味着如果您只看到输出，它们实际上是不可逆的。 我以这种方式对列表进行排序，因为这些属性是分层的。所以抗碰撞意味着目标碰撞抗性，这意味着第二原像抗性等。但反之 _则不然。_ 仅仅因为一个函数是抗目标碰撞的，并不意味着它一定是抗碰撞的。 并非每个加密哈希函数/方案都具有这些属性。上面的列表暗示了一个好的实用密码散列函数的一些其他非正式属性。例如，即使输入的微小变化也会在输出中产生巨大的、不可预测的变化。这种“雪崩效应”是原像抗性的结果，它使工作量证明共识方案（如下所述）安全。 哈希函数和工作量证明 ---------- 对于使用工作量证明挖矿达成共识的加密货币（如比特币），我们最关心的属性是抗原像性和抗二次原像性。在我们能够理解为什么我们需要更详细地了解工作证明共识算法是如何工作之前，以比特币为例。⁵ 在比特币网络中，节点维护一个与不同公钥相对应的全球余额分类账。⁶ 它们还保留了所有历史交易的历史记录，这些交易被组织成块。每个块都包含在给定时间段内发生的交易列表，以及对前一个块的引用。前 _一个块头_ 只是哈希函数的输出，其中输入是该块的内容。 比特币网络上的节点可以生成新交易块以添加到区块链中以换取奖励（以 BTC 计价）。所以他们必须创建一个包含交易的新区块和一个新的区块头。但是网络上的其他节点不会接受任何块头。他们只会接受一个带有头部的块（哈希函数的输出）包含大量的前导 0（如 0000000000000000000bffeea5b705bbba0902579ab91da102e348be59d46310）。对于任何给定的输入集，这不太可能发生。但是，如果哈希函数是确定性的，那么比特币矿工如何创建具有正确结构的哈希函数输出呢？ 这就是工作量证明难题出现的地方。除了交易和先前的标头之外，比特币矿工添加一个称为 nonce 的额外值。⁶ 如果结果输出不符合“目标”标准，那么矿工增加 nonce 和再次运行该功能。这个过程一遍又一遍地重复，直到哈希函数产生一个值。 上述过程就是我们在比特币等工作量证明区块链中所说的“挖矿”。节点一遍又一遍地运行散列函数， _除了_ 随机数之外，使用相同的输入。一旦他们找到一个随机数，结合单个交易和前一个区块头，产生正确数量的前导零⁷，他们就可以将其提交给网络并获得他们的区块奖励。 加密哈希函数是这个过程的神奇成分。回想一下，原像抗性的属性意味着散列函数的输出应该是不可预测的。换句话说，它应该“看起来”是随机的。所以矿工不能只从目标哈希值开始，然后向后计算随机输入的值应该是什么。无论之前执行了多少次迭代，为散列函数找到目标输出的问题同样困难。 同时，第二原像阻力意味着很难为 _随机选择的输入_ （例如先前的块头和交易）找到冲突。实际上，这意味着散列函数的每个输出都是可靠唯一的。最后，目标抗碰撞性保证了对手很难找到任何导致特定哈希值的特定消息。这确保了以后没有人可以随意将区块链的一部分换成另一部分。并且因为每个新的块头都引用了前一个块，而前一个块又引用了前一个块，依此类推，整个账本历史的完整性得以保持。 结论 -- 尽管这篇文章只关注加密应用程序，但散列函数用于多种用途。例如，它们用于检测大文件中的更改。给定大量输入（如整个数据库），原像阻力（以及相关的“雪崩效应”）意味着即使更改整个文件中的单个字符也会导致不同的哈希输出。因此，可以比检查文件本身更有效地存储和比较哈希输出。 在其他加密应用方面，散列函数的一个主要优点是它们是抗量子的。其原因是，对于量子计算机和非量子计算机一样，对哈希函数的输出进行逆向工程同样困难。⁸ 其他加密原语（如比特币和其他加密货币中使用的数字签名方案）是基于关于量子计算机容易解决但普通计算机难以解决的问题。因此，尽管量子计算机对许多现有密码系统的其他方面构成威胁，但我们今天使用的密码哈希函数应该保持安全。此外，许多现有的加密方案可以更改为使用散列函数，为未来的安全加密提供基础。 正如我们所见，加密哈希函数是比特币和其他加密货币工作量证明挖掘的基石。密码哈希函数的抗目标碰撞、抗二次原像和抗原像特性保证了工作量证明共识的安全性、去中心化和“公平性”。一些人认为加密货币挖掘是一种能源“浪费”，声称类似比特币的工作量证明系统的蛮力性质是低效的。他们提出了基于“有用”工作的替代方案，例如蛋白质折叠或寻找大素数。但是没有一个提出的问题具有上面列举的属性。因此，他们无法在同等程度上确保安全性和去中心化。 正如引言中提到的，这是一系列揭秘密码原语的第一部分。我选择哈希函数是因为它们对于比特币、以太坊和许多其他加密货币的工作量证明挖掘至关重要。除了区块链之外，它们还因为它们在更广泛的密码学中无处不在。但尽管它们很重要，但它们并不神奇。只是有点数学所以希望这篇文章有助于阐明这些函数是什么以及它们为什么重要。我希望它也能启发你更多地了解日益重要的密码学领域。如果对我接下来应该介绍的内容有任何建议，或者您对这篇文章有任何反馈，请在下面发表评论！ 尾注： --- \[1\] 对于密码学的伟大历史，我强烈推荐大卫·卡恩 (David Kahn) 的书 [The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to Internet](https://www.amazon.com/Codebreakers-Comprehensive-History-Communication-Internet/dp/0684831309) \[2\] 为了更深入地讨论这个话题，我强烈推荐斯坦福大学教授 Dan Boneh 在 Coursera 上的密码学入门课程。为了更深入地了解，我推荐  Arno Mittelbach 和 Marc Fischlin的文章[The Theory of Hash Functions And Random Oracles](https://www.springer.com/gp/book/9783030632861) \[3\] 该术语指的是为“高效”对手寻找冲突的难度，这意味着对手受多项式运行时间的限制。如果这是不熟悉的术语，请不要担心，因为对于本文的目的而言它并不重要。但是，如果您想进入兔子洞，请查看  有关计算复杂性的[维基百科条目](https://en.wikipedia.org/wiki/Time_complexity#Polynomial_time) \[4\] 单向函数是最基本的密码原语之一。几乎每一种加密方案都以某种方式依赖于单向函数。 \[5\] 比特币使用称为 SHA-256 的散列函数，它是经过时间检验、NIST 认证的加密散列函数，具有上述所有属性。其他区块链有时使用不同的功能来进行工作量证明（例如，以太坊使用 Keccak-256）。但即使实现细节不同， _只要_ 使用的散列函数是具有上述属性的加密散列函数，任何工作量证明网络的总体方案看起来都大致相同 \[6\] “Nonce”是“不超过一次”使用的值的简写 \[7\] 为了保持区块生产时间相对恒定，比特币和大多数其他工作量证明区块链都有一个动态的“难度”参数。这个难度定义了找到目标哈希输出的难度，即更高的难度需要更多数量的前导零 \[8\] 同样，这里的硬度是指有效的对手。但是某些在传统计算机上效率低下的算法实际上在量子计算机上非常有效 --- *Originally published on [eastmoney](https://paragraph.com/@eastmoney/rtUE3eL93qON1M4vVg1w)*