切碎、存储、加密 —— 哈希函数的故事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. 哈希还有其他用途吗加密安全哈希函数的其他应用包括用于文档验证的数字签名和区块链。下次将详细介绍。安全背后的数学探讨加密技术为何有效以及为何有时会失效背后的数学原理。