切碎、存储、安全——哈希函数的故事

# 切碎、存储、保护——哈希函数的故事 来源：https://0xkrt26.github.io/math_behind_security/2026/06/09/the-story-of-the-hash-function.html 所有算法的 Python 实现均可在我的 GitHub 仓库（https://github.com/0xkrt26/math_behind_security/blob/main/implementations/dumey_polynom_exponent_hash.py）中找到。 Peter Luhn 提出了利用数学验证和存储信息的想法（https://0xkrt26.github.io/math_behind_security/2026/04/28/the-accidental-ancestor-Luhn-algorithm.html），生日问题（https://0xkrt26.github.io/math_behind_security/2026/05/08/birthday-problem.html）解释了哈希表中的碰撞，Rabin-Karp 算法（https://0xkrt26.github.io/math_behind_security/2026/04/25/searching-smarter-rolling-hashes.html）使用滚动哈希进行字符串搜索。我们谈论了太多关于哈希的内容，却从未给出过哈希函数本身的定义。 ### 哈希是何时首次出现的？ 1956 年，Arnold Dumey 首次定义了哈希的概念。他 14 岁起就对密码学充满热情，并拥有哥伦比亚大学的数学学位，这使他先加入美国陆军通信兵部队，后进入 Potter Instrument（一家对计算机存储器工程感兴趣的打印机生产公司）。后来，他在接受 Charles Babbage Institute 的采访（https://conservancy.umn.edu/server/api/core/bitstreams/fa424683-eaf2-4563-a504-6f4d31720aed/content）时说：“我写了一篇论文，这是第一篇关于哈希编码的论文，基于我在那里（Potter Instrument）的工作。”在那篇论文中，Dumey 描述了使用数学变换将数据映射到内存地址以实现更快搜索的概念，并将其称为索引。 ### 索引是如何工作的？ 在他的论文中，Dumey 给出了清晰的说明。 ### 1. 将单词存储在内存中，首先将其转换为数字。 以单词“BOX”为例。我们可以像 Dumey 建议的那样，将其转换为 37 进制数，或者直接使用 ASCII 码。这里我们选择第一种方法。为此，我们将字母映射到它们在字母表中的位置。 `` A=1 B=2 ... X=24 Y=25 Z=26 `` 然后我们将它们乘以 37 的幂。 在我们的例子中，单词“BOX”的数值是 \\[2 \times 37^2 + 15 \times 37^1 + 24 \times 37^0 = 2738 + 555 + 24 = 3317\\] 早期的计算机系统和打孔纸带主要只处理字母和数字：英文字母的 26 个字母，加上 10 个数字和一个空格，总共 37 个可用符号。 ### 2. 找一个略小于可寻址位置数量的质数。 在我们的例子中，有 100 个可寻址位置。此时，最接近的质数是 97。 ### 3. 将数值除以这个质数…… ……然后扔掉商，保留余数。换句话说，执行我们最喜欢的模运算！ \\[3317 \pmod{97} = 19\\] 这意味着单词“BOX”将被存储在内存地址 19。 ### 索引和哈希之间有什么区别？ 没有区别。后来，索引被称为多项式哈希，我们在几周前的 Rabin-Karp 算法（https://0xkrt26.github.io/math_behind_security/2026/04/25/searching-smarter-rolling-hashes.html）中已经介绍过。*Hash* 这个词本身源于法语单词 *hacher*（“切碎”、“剁碎”），这很好地反映了哈希函数在将信息存储到内存之前所做的事情。有一段时间，这只是密码学家中广泛使用的行话。在 20 世纪 60 年代末，*hash* 一词首次正式出现在 Herbert Hellerman 的《数字计算机系统原理》中。 ### 那么密码学哈希就是这样工作的吗？ 并不完全是。其思想是相同的：使用数学来转换数据。然而，现在的目标还包括保护数据免受攻击者的攻击。 我将给出的密码学哈希的定义是基于一篇非常有趣的论文 ——《密码学的新方向》（1976 年）（https://www.cs.jhu.edu/~rubin/courses/sp03/papers/diffie.hellman.pdf），作者是 Whitfield Diffie 和 Martin E. Hellman。这篇论文引人入胜，易于阅读，不仅涵盖了密码学哈希，还涉及 RSA，所以我非常推荐进一步阅读。 ### 那么什么是密码学哈希？ 哈希是用于保护易受攻击数据的一个值。例如，网站将您的登录信息存储为哈希值，而不是纯文本，以防止其被攻击者窃取。当您注册时，您首次输入密码（PW）。网站使用一个单向函数（也称为哈希函数）f(x) 生成一个哈希值，并存储 f(PW)。在您后续的每次登录中，网站都会用您输入的数据计算 f(x)。只有当 f(x) 等于 f(PW) 时，密码才会被接受。 由于您的密码在从您的计算机传输到网站的过程中仍可能被窃取，密码哈希通常与 TLS 等加密协议一起使用，以保护传输中的数据。 ### 为什么存储 f(PW) 比存储 PW 更安全？ 创建哈希的单向函数的主要特性是其不可逆性。即使您拥有用于转换的函数，从哈希回到纯文本在计算上也是不可能的。 “计算上不可能”意味着即使使用最强大的计算机，找到原始值也需要极长的时间。 ### 为什么逆转哈希函数如此困难？ 在学校里我们学到，每个函数都有一个逆函数：加法由减法逆转，乘法由除法逆转，指数由对数逆转。然而，对于某些函数，根本没有已知的“撤销按钮”。这样的函数被称为抗原像攻击函数。让我们看一些例子。 ### 1. 高次多项式 n 次多项式如下所示： \\[p(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0\\] 计算机可以通过简单的线性加法和乘法轻松计算任何 x 的 p(x)。然而，求解 p(x) = y 中的 x 则要困难得多。我们都解过一次、二次甚至三次多项式，使用了二次公式和二项式公式。但五次多项式呢？十次呢？根据 Abel-Ruffini 定理，“当 n ≥ 5 时，一般 n 次多项式不能由根式求解”，这意味着没有捷径或特殊公式可以求解高次多项式。因此，攻击者别无选择，只能使用迭代算法，基本上就是猜测根。 但即便如此，这还不够。这些高次多项式必须在有限域 Fp 上，这意味着每次运算后，都会对中间结果取一个大质数的模。（为什么是“大质数”在 这里（https://0xkrt26.github.io/math_behind_security/2026/04/25/searching-smarter-rolling-hashes.html）有解释。） ### 2. 离散指数运算。 换句话说，我们又一次在计算 a 的 x 次幂的每一步中执行我们最喜欢的模运算： \\[y = a^x \pmod{q}\\] 这个函数对于每个 x 也很容易计算。然而，其逆运算——有限域上的对数——对攻击者来说又是一项艰巨的任务。 ### 为什么这些函数必须在一个有限域上？有限域是什么？ 有限域 Fp（或伽罗瓦域 GF(p)）是一个包含有限数量元素的域。这个数量必须等于一个质数的幂。例如，一个大小为 7 的有限域只能包含值 0、1、2、3、4、5、6。没有像 5.99 这样的中间值，只有整数。相比之下，实数域 R 包含无限多个元素。 在学校代数中，我们习惯了在无限域上工作，其图形是曲线，可以分析、跟踪和预测。有限域更像是一些混乱的点，其中 y=101 对应的 x 与 y=100 对应的 x 甚至不是接近的值。因此，不是“冷热”游戏，攻击者别无选择，只能对函数进行暴力破解。检查比如 2^256 个输入是一个非常非常非常漫长的过程。 ### 这些函数总是安全的吗？ 碰撞越少越好。想象一下，存在另一个 X 使得 f(X) = f(PW)。在这种情况下，攻击者找到的是 X 还是 PW 并不重要。由于 f(X) = f(PW)，他仍然可以成功登录。 另一个问题最近出现了。还记得我们说过，逆转单向函数在计算上是不可可能的吗？现在不再是这样了。量子计算机超越了现代计算机的极限，使得暴力破解速度大大加快。这产生了对后量子密码学的需求。 ### 哈希还可以用于什么？ 密码学安全哈希函数的其他应用包括用于文档验证的数字签名和区块链。（我们下次会更详细地介绍这些。） ### 我的来源和进一步阅读： - Arnold Dumey《计算机与自动化》（http://bitsavers.informatik.uni-stuttgart.de/magazines/Computers_And_Automation/195612.pdf） - Arnold Dumey 接受 Charles Babbage Institute 采访（https://conservancy.umn.edu/server/api/core/bitstreams/fa424683-eaf2-4563-a504-6f4d31720aed/content） - Diffie 和 Hellman《密码学的新方向》（https://www.cs.jhu.edu/~rubin/courses/sp03/papers/diffie.hellman.pdf） - 维基百科关于哈希函数的条目（https://en.wikipedia.org/wiki/Hash_function#History） - 芝加哥大学关于 Abel-Ruffini 定理（https://math.uchicago.edu/~may/REU2019/REUPapers/Mrinal.pdf）