哈希函数：从加密货币到密码学核心

·

在密码学中，加密并非唯一重要的工具。哈希函数作为另一种基础密码学原语，在数据完整性、数字签名和加密货币等领域发挥着关键作用。尽管你可能在其他领域接触过哈希函数，但密码学中的哈希函数具备一些特殊性质，使其能够满足更高的安全需求。本文将深入探讨哈希函数的定义、核心属性、常见攻击方式以及如何扩展其输入域。

加密货币中的核心问题

传统货币体系是中心化的，由中央机构制定货币政策、确认所有权并管理整个系统。而加密货币则通过密码学工具构建去中心化系统，比特币便是其中最著名的例子。在这种去中心化环境中，几个关键问题需要解决：

双重支付问题

假设A向B支付一枚加密货币（由唯一标识符ID代表的比特串）。如果没有中央机构验证，A可能使用同一ID向C再次支付。解决方案是建立公共账本记录所有交易。当A向B支付时，“A将硬币ID转移给B”的消息会被添加到账本中。一旦账本确认B获得所有权，B就会向A发货。如果A试图重复使用同一硬币，C通过查看账本会发现硬币已不属于A，从而拒绝交易。

账本共识问题

在去中心化系统中，谁负责维护账本并添加新交易？用户如何就交易顺序达成共识？当出现分叉（即不同方声称的下一个交易冲突）时，系统需要一种机制确保用户对有效账本保持共识。

比特币的解决方案是引入工作量证明机制：用户通过消耗计算资源（CPU周期）来获得账本更新权。具体而言，系统要求用户找到特定输入x，使得哈希函数H(ID∥x)的输出前T位为0。找到解需要大约O(2^T)次计算，而验证只需一次哈希计算。成功添加交易的用户（矿工）会获得新铸造的硬币作为奖励。

交易标识符冲突

为确保交易顺序不可篡改，新交易t_{n+1}会包含之前所有交易t_1,…,t_n的哈希值H(t_1,…,t_n)作为标识符。由于哈希函数将大集合映射到较小集合，输出不可能唯一。但只要找到碰撞（两个不同输入产生相同输出）在计算上困难，该系统就是安全的。

哈希函数的定义与属性

哈希函数的核心是将任意长度比特串映射到固定长度输出（例如160或256位）。与加密不同，哈希函数不需要密钥，且必须是公开和确定性的，以便多方验证结果。

形式化定义

哈希函数是高效可计算的函数：
[ H:{0,1}^* \rightarrow {0,1}^\ell ]
其中{0,1}^*表示所有长度比特串的集合，\ell为输出长度。计算哈希函数的过程称为哈希，输出称为哈希值。

安全属性

由于输入空间大于输出空间，碰撞必然存在。但密码学哈希函数需满足以下安全性质：

这些属性之间存在内在联系：碰撞抵抗性蕴含第二原像抵抗性。而对于实际使用的哈希函数（执行有意义压缩），第二原像抵抗性通常也意味着原像抵抗性。

👉 探索哈希函数的实际应用场景

生日攻击：碰撞搜索的优化

对哈希函数H: {0,1}^* → {0,1}^\ell的暴力攻击最多需要2^ℓ + 1次尝试（因为只有2^ℓ种输出）。这似乎表明ℓ位输出提供ℓ比特安全性。但生日悖论表明实际情况并非如此。

生日悖论原理

考虑40名学生的班级，任何两人共享生日的概率是多少？直觉上可能认为概率很低（一年365天）。但计算显示，所有人生日都不同的概率仅为：
[ \frac{364}{365} \times \frac{363}{365} \times \cdots \times \frac{326}{365} \approx 0.108768 ]
因此，至少两人共享生日的概率高达约89.1%。这种反直觉现象源于碰撞概率随样本数平方根增长。

对哈希函数的影响

对于输出长度为ℓ的哈希函数，找到碰撞的概率在约√(2^ℓ) = 2^{ℓ/2}次尝试后就会变得显著。这意味着：

例如，SHA-256提供128比特安全性，足以抵抗生日攻击。

Merkle-Damgård变换：扩展输入域

实际哈希函数常先构建固定长度输入函数（如H: {0,1}^{2ℓ} → {0,1}^ℓ），再通过Merkle-Damgård变换扩展至任意长度输入。SHA家族哈希函数便采用此方法。

变换过程

  1. 将输入\mathbf{x}（长度L ≤ 2^ℓ）分块为\mathbf{x}_1, …, \mathbf{x}_n，每块长ℓ位
  2. 添加额外块\mathbf{x}_{n+1}，包含L的二进制编码（因L ≤ 2^ℓ -1，可用ℓ位表示）
  3. 递归计算：
    [ \mathbf{z}_i = H(\mathbf{z}_{i-1} | \mathbf{x}_i) \quad \text{对于} i=1,\dots,n+1 ]
    其中|表示连接，\mathbf{z}_0为初始化向量（通常全0，无需保密）
  4. 最终哈希值\mathbf{H}(\mathbf{x}) = \mathbf{z}_{n+1}

安全性保证

关键性质：若底层函数H是碰撞抵抗的，则通过Merkle-Damgård构造的\mathbf{H}也是碰撞抵抗的。这确保了扩展后哈希函数的安全性。

常见问题

哈希函数与加密函数有何区别？

加密函数需要密钥且可逆（解密），而哈希函数无需密钥且不可逆。哈希函数用于完整性验证和承诺，加密则用于保密性。

为什么哈希函数碰撞不可避免？

因为输入空间（任意长度）远大于输出空间（固定长度），根据鸽巢原理，碰撞必然存在。密码学要求的是计算上难以找到碰撞。

生日攻击对哈希函数选择有何实际影响？

为抵抗生日攻击，哈希函数输出长度应足够长。目前推荐至少256位（如SHA-256），以提供128比特安全性。较短哈希函数（如MD5、SHA-1）已不推荐使用。

Merkle-Damgård构造是否有缺点？

该构造可能容易受到长度扩展攻击：已知H(x)和x长度时，可计算H(x∥y)而不知x。现代哈希函数如SHA-3采用不同结构避免此问题。

哈希函数在区块链中具体如何应用？

在比特币中，哈希函数用于：

如何选择适合的哈希函数？

应根据安全需求选择：