Chopped, Stored, Secured – The Story of the Hash Function

背景

哈希（Hash）这一概念在计算机科学和密码学中无处不在，但我们往往只关注其应用，却忽略了其定义和起源。从 Peter Luhn 提出用数学方法验证和存储信息，到 Birthday problem（生日悖论）解释哈希表中的冲突，再到 Rabin-Karp 算法利用滚动哈希进行字符串搜索，哈希技术已经深深嵌入现代 IT 基础设施。然而，关于哈希函数本身的定义及其历史演变，往往被忽视。这篇文章旨在追溯哈希的起源，解析其从最初的“索引”概念到现代“密码学哈希”的演变过程，并深入探讨其背后的数学原理。

核心内容

哈希的起源：从“索引”到“哈希”

哈希思想的雏形最早出现在 1956 年，由 Arnold Dumey 首次定义。Dumey 自 14 岁起就对密码学充满热情，拥有哥伦比亚大学的数学学位。他的职业生涯始于美国陆军信号兵团，随后加入了 Potter Instrument（一家对计算机内存工程感兴趣的打印机制造公司）。Dumey 后来在接受 Charles Babbage Institute 采访时提到：“我写了一篇论文，这是关于哈希编码的第一篇论文，基于我在 [Potter Instrument] 所做的工作。”

在那篇论文中，Dumey 描述了利用数学变换将数据映射到内存地址以加快搜索速度的概念，并将其称为“索引”（Indexing）。

早期索引机制的工作原理

Dumey 在论文中给出了清晰的指令，展示了早期索引（即多项式哈希）的工作流程：

1. 将单词转换为数字： 以单词 “BOX” 为例。Dumey 建议将其转换为 base 37 数字，或者使用 ASCII。这里我们采用 base 37 的方法。首先将字母映射到其在字母表中的位置：

   • 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$$

2. 寻找质数： 找到一个略小于可寻址位置数量的质数。假设我们有 100 个可寻址位置，最近的质数是 97。

3. 取模运算： 将数值除以该质数，丢弃商，只保留余数（即执行取模运算）： $$3317 \pmod{97} = 19$$ 这意味着单词 “BOX” 将被存储在内存地址 19。

索引与哈希的区别

实际上，早期的“索引”与现代的“哈希”没有本质区别。后来，这种索引方式被称为多项式哈希（Polynomial Hash），这也正是我们在 Rabin-Karp 算法中讨论过的内容。

单词 “Hash” 本身源自法语单词 hacher（意为“切碎”或“剁碎”），这非常形象地反映了哈希函数在将信息存入内存之前对其进行处理的方式。在很长一段时间里，“哈希”只是密码学家之间的行话。直到 20 世纪 60 年代末，该术语才正式出现在 Herbert Hellerman 的《Digital Computer System Principles》一书中。

密码学哈希：从存储到安全

上述机制主要用于快速查找，而密码学哈希的目标则是保护数据免受攻击者侵害。

• 工作原理：哈希是一个用于保护脆弱数据的值。例如，网站存储你的登录信息时，存储的是哈希值而非明文。当你注册时，输入密码（PW），网站使用单向函数 $f(x)$（也称为哈希函数）生成 $f(PW)$ 并存储。每次登录时，网站计算输入数据的 $f(x)$，只有当 $f(x) = f(PW)$ 时，密码才被接受。
• 安全性核心：单向函数的主要属性是不可逆性（Irreversibility）。即使你知道用于变换的函数，从哈希值反推明文在计算上也是不可能的。

为什么哈希难以逆向？

在学校里我们学过，大多数函数都有逆运算（如加法对应减法，乘法对应除法）。但对于某些函数，不存在已知的“撤销按钮”，这类函数被称为原像 resistant（Preimage Resistant）。

1. 高次多项式： 多项式 $p(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0$ 很容易计算 $p(x)$ 的值。但是，求解 $p(x)=y$ 中的 $x$ 却非常困难。根据 Abel-Ruffini 定理，“对于 $n \ge 5$，一般 $n$ 次多项式不能用根式求解”。这意味着对于高次多项式，攻击者没有捷径，只能使用迭代算法（即猜测根）。此外，这些多项式必须在有限域 $F_p$ 上运算，即每次操作后对一个大质数取模。

2. 离散指数运算： 即 $y = a^x \pmod{q}$。该函数易于正向计算，但其逆运算——有限域上的离散对数——对攻击者来说极其困难。

有限域（Finite Field）的作用

为什么这些函数必须在有限域上运行？

• 定义：有限域 $F_p$（或伽罗瓦域 $GF(p)$）是一个元素数量有限的域。元素数量必须是质数的幂。例如，模 7 的有限域只包含整数 0 到 6，没有 5.99 这样的值。相比之下，实数域 $\mathbb{R}$ 包含无限多个元素。
• 特性：在代数中，我们习惯处理无限域，其图像是一条可分析、可追踪的曲线。而有限域更像是一系列混乱的点，$y=101$ 对应的 $x$ 和 $y=100$ 对应的 $x$ 甚至没有接近的值。
• 安全性：这种特性使得攻击者无法通过“冷热游戏”（Hot and Cold，即根据距离目标值的远近来调整猜测）来缩小范围，只能进行暴力破解。检查 $2^{256}$ 个输入是一个极其漫长的过程。

潜在威胁与未来

尽管哈希函数通常很安全，但仍存在两个主要问题：

1. 碰撞（Collisions）： 碰撞越少越好。如果存在另一个值 $X$ 使得 $f(X) = f(PW)$，攻击者无需知道原始密码，只需找到 $X$ 即可成功登录。
2. 量子计算： 过去认为逆向哈希在计算上是不可能的，但量子计算机的出现打破了这一界限。量子计算机超越了现代计算机的限制，使得暴力破解变得更快。这催生了对后量子密码学（Post-quantum cryptography）的需求。

其他应用

除了数据保护，密码学安全的哈希函数还广泛应用于数字签名（用于文档验证）和区块链技术。

关键要点

• 历史起源：哈希思想由 Arnold Dumey 于 1956 年首次定义，最初称为“索引”，用于通过数学变换将数据映射到内存地址以加速搜索。
• 术语演变：“Hash”一词源自法语 hacher（切碎），形象描述了数据处理过程。该术语在 20 世纪 60 年代末才正式进入学术文献。
• 早期机制：早期的索引本质上是多项式哈希。例如，将单词转换为 base 37 数值，再对质数取模以确定存储地址。
• 密码学哈希的核心：与用于查找的哈希不同，密码学哈希旨在保护数据。其核心在于使用单向函数，具有不可逆性（原像 resistant）。
• 数学基础：哈希的安全性依赖于有限域上的困难数学问题，如