切碎、存储、加密 —— 哈希函数的故事
2026 年 6 月 9 日，作者在 GitHub 仓库中提供了所有这些算法的 Python 实现。彼得·卢恩提出了运用数学方法验证和存储信息的想法；生日问题解释了哈希表中的冲突现象；拉宾 - 卡普算法利用滚动哈希来搜索字符串。不过，作者多次提及哈希，却从未给出哈希函数本身的定义。
1. 哈希最早是何时出现的？
1956 年，阿诺德·杜米首次提出了哈希的概念。他从 14 岁起就对密码学充满热情，还拥有哥伦比亚大学的数学学位。这使他先是加入了美国陆军通信兵部队，后来又进入了波特仪器公司。在后来接受查尔斯·巴贝奇研究所的采访时，杜米说：“我写了一篇论文，这是第一篇关于哈希编码的论文，它基于我在波特仪器公司所做的工作。” 在那篇论文中，杜米描述了利用数学变换将数据映射到内存地址以实现更快搜索的概念，并将其称为索引。
2. 索引是如何工作的？
在他的论文中，杜米给出了清晰的说明。
首先，要将一个单词存储到内存中，需先将其转换为一个数字。以单词 “BOX” 为例，可将其转换为 37 进制的数字，也可使用 ASCII 码，这里选择前者。为此，将字母映射到它们在字母表中的位置，然后将它们乘以 37 的幂次方。在这个例子中，单词 “BOX” 的数值为 3317。早期的计算机系统和穿孔纸带主要处理字母和数字，英文字母表的 26 个字母，加上 10 个数字，再加上一个空格，总共 37 个可用符号。
其次，要找到一个略小于可寻址位置数量的质数。在这个例子中，有 100 个可寻址位置，最接近的质数是 97。
最后，将数值除以质数，然后舍弃商，使用余数，即进行取模运算。这意味着单词 “BOX” 将被存储在内存地址 19 处。
3. 索引和哈希有什么区别？
实际上，索引和哈希没有区别。后来，索引被称为多项式哈希，在几周前的拉宾 - 卡普算法中已经介绍过。“哈希（hash）” 这个词本身源自法语单词 “hacher”，意为 “切碎”“剁碎”，这很形象地反映了哈希函数在将信息存储到内存之前对其进行的处理方式。有一段时间，它只是密码学家之间广泛使用的行话。20 世纪 60 年代末，“哈希” 这个术语首次正式出现在赫伯特·赫勒曼的《数字计算机系统原理》一书中。
4. 那么，加密哈希就是这样工作的吗？
并非如此。其基本思路是相同的，都是利用数学方法转换数据。然而，现在的目标还包括保护数据不被攻击者获取。
作者给出的加密哈希的定义，基于惠特菲尔德·迪菲和马丁·E·赫尔曼撰写的一篇非常有趣的论文《密码学的新方向》。这篇论文引人入胜、易于阅读，不仅涵盖了加密哈希，还涉及 RSA 算法，作者强烈推荐大家进一步阅读。
5. 那么，什么是加密哈希呢？
哈希是一种用于保护易受攻击数据的值。例如，网站将用户的登录信息存储为哈希值，而不是明文，以防止其被攻击者窃取。当用户首次注册时，输入密码（PW），网站使用单向函数 f(x)（也称为哈希函数）生成一个哈希值，并存储 f(PW)。在用户后续的每次登录时，网站都会使用用户输入的数据计算 f(x)，只有当 f(x) 等于 f(PW) 时，密码才会被接受。
由于用户的密码在从计算机传输到网站的过程中仍可能被窃取，因此密码哈希通常会与 TLS 等加密协议一起使用，以保护数据在传输过程中的安全。
6. 为什么存储 f(PW) 比存储 PW 更安全？
创建哈希的单向函数的主要特性是其不可逆性。即使知道用于转换的函数，从哈希值反推明文在计算上也是不可能的。“在计算上不可能” 意味着，即使使用最强大的计算机，要找到原始值也需要花费很长时间。
7. 为什么反转哈希函数会如此困难？
在学校里，学过每个函数都有其反函数，如加法的反运算是减法，乘法的反运算是除法，指数的反运算是对数。然而，对于某些函数，根本不存在已知的 “撤销按钮”，这类函数被称为抗前像函数。
比如高次多项式，n 次多项式的形式如下：p(x) = a_n x^n + a_{n - 1} x^{n - 1} + … + a_1 x + a_0 。计算机可以通过简单的线性加法和乘法轻松计算出任意 x 值对应的 p(x)，然而，要解出 p(x) = y 中的 x 则要困难得多。根据阿贝尔 - 鲁菲尼定理，“当 n ≥ 5 时，一般的 n 次多项式不能用根式求解”，这意味着求解高次多项式没有捷径或特殊公式，因此，攻击者别无选择，只能使用迭代算法，基本上就是猜测根的值。而且，这些高次多项式必须定义在有限域 Fp 上，这意味着在每次运算后，都要对中间结果取一个大质数的模。
再如离散指数运算，即在将 a 进行 x 次幂运算的每一步都进行取模运算：y = a^x (mod q) 。对于每个 x，这个函数也很容易计算，然而，其逆运算，即有限域上的对数运算，对攻击者来说又是一项艰巨的任务。
8. 为什么这些函数必须定义在有限域上，什么是有限域？
有限域 Fp（或伽罗瓦域 GF(p)）是一个元素数量有限的域，这个数量必须是一个质数的幂。例如，一个包含 7 个元素的有限域只能有 0、1、2、3、4、5、6 这些值，不存在 5.99 这样的中间值，只有整数。相比之下，实数域 R 包含无限个元素。
在学校代数中，习惯了在无限域中工作，在那里函数图像是一条可以分析、追踪和预测的曲线。有限域更像是混乱的点集，y = 101 对应的 x 值和 y = 100 对应的 x 值可能相差甚远。因此，攻击者无法像玩 “冷热游戏” 那样逐步逼近答案，只能对函数进行暴力破解。检查 2^256 个输入是一个极其漫长的过程。
9. 这些函数总是安全的吗？
冲突越少越好。假设存在另一个 X 使得 f(X) = f(PW)，在这种情况下，攻击者找到 X 还是 PW 并不重要，因为 f(X) = f(PW)，他仍然可以成功登录。
最近又出现了另一个问题。还记得说过单向函数在计算上是不可逆的吗？现在情况不同了。量子计算机突破了现代计算机的极限，使暴力破解变得更快，这就产生了对后量子密码学的需求。
10. 哈希还有其他用途吗？
加密安全哈希函数的其他应用包括用于文档验证的数字签名和区块链。（下次将详细介绍。）
安全背后的数学
探讨加密技术为何有效，以及为何有时会失效背后的数学原理。
原理与应用实战)
