哈希函数基础

哈希函数的定义

密码学哈希函数 H 是一个确定性函数，将任意长度的输入映射为固定长度的输出（称为哈希值、摘要或指纹）：

h = H(M)，其中 M 为任意长度消息，h 为固定长度输出

例如 SHA-256 无论输入是 1 字节还是 1 TB，输出总是 256 位（32 字节）。

哈希函数的五大性质

  1. 确定性（Deterministic）：相同输入永远产生相同输出。H("hello") 每次结果一样。
  2. 快速计算（Computationally Efficient）：对于任意输入，计算哈希值应当很快。SHA-256 在现代 CPU 上可达数 GB/s。
  3. 抗原像性（Pre-image Resistance）：给定哈希值 h，很难找到 M 使得 H(M) = h。即"给定输出，找不到输入"。这是单向性的体现。
  4. 抗第二原像性（Second Pre-image Resistance）：给定输入 M₁，很难找到 M₂ ≠ M₁ 使得 H(M₁) = H(M₂)。即"给定一个输入，找不到另一个同输出的输入"。
  5. 抗碰撞性（Collision Resistance）：很难找到任意两个不同的 M₁ ≠ M₂ 使得 H(M₁) = H(M₂)。即"任意找一对碰撞都不可行"。

性质之间的关系

抗碰撞性 → 抗第二原像性 → 抗原像性（前者蕴含后者）。因此抗碰撞性是最强的要求。

安全强度

对于 n 位哈希函数：

  • 抗原像攻击：需要约 2n 次运算
  • 抗第二原像攻击：需要约 2n 次运算
  • 抗碰撞攻击：由于生日悖论，只需约 2n/2 次运算

所以 SHA-256 的碰撞安全强度为 128 位，原像安全强度为 256 位。

哈希函数的应用场景

数据完整性验证

计算文件或消息的哈希值，传输后重新计算并比对。若哈希值一致，则数据未被篡改（假设哈希函数安全且哈希值本身未被篡改）。

数字签名

不对整个消息签名（消息可能很长），而是对消息的哈希值签名。签名 = Sign(H(M))。效率高且安全。

密码存储

数据库中不存储明文密码，而是存储 H(password + salt)。验证时对输入密码做同样哈希后比对。即使数据库泄露，攻击者也无法直接获取密码。

数据结构

  • 哈希表：用哈希函数将键映射到数组索引，O(1) 查找
  • 默克尔树（Merkle Tree）：区块链和 Git 使用的树形哈希结构

密钥派生

从一个共享密钥派生出多个子密钥：K₁ = H(K || "enc"), K₂ = H(K || "mac")。

承诺方案

承诺 C = H(value || nonce)，之后揭示 value 和 nonce 来验证。用于拍卖、投票等场景。

理想哈希函数：随机预言机

随机预言机（Random Oracle）是一个理想化的哈希函数模型：对每个新输入返回一个独立的均匀随机值，对已见过的输入返回相同值。

现实中不存在真正的随机预言机（因为哈希函数是确定性的公开算法），但它是密码学安全证明中的重要工具。任何可证明安全的哈希函数都"接近"随机预言机的行为。