密码学哈希与碰撞

通常应由不同的输入消息产生不同的输出哈希值（消息摘要）。

哈希碰撞

碰撞是指两个不同输入得到相同的哈希值。简单的哈希函数很容易发生碰撞。例如，假设哈希函数 h(text) 将文本中所有字符的编码相加，那么包含相同字母但顺序不同的文本将得到相同的哈希值（发生碰撞），即 h('abc') == h('cab') == h('bca')。为避免碰撞，密码学家设计了抗碰撞哈希函数。

密码学哈希函数：避免碰撞

在密码学哈希函数中找到碰撞的可能性极低，因此可以认为密码学哈希几乎能够唯一标识其对应的输入。此外，要找到哈希值为某个给定值的输入消息也极其困难。

密码学哈希函数是单向哈希函数，几乎不可能求逆。对于 SHA-256 这类强密码学哈希函数，通过暴力破解找到碰撞的概率极低。具体可以这样表述：

• 对于某个强密码学哈希函数 hash，设哈希值 h=hash(p)。
• 要找到满足 hash(p')=h 的输入 p'，预期应当极其困难。
• 对大多数现代强密码学哈希函数而言，目前没有已知碰撞。

理想的密码学哈希函数应具有以下性质：

• 确定性：相同的输入消息应始终得到相同的哈希值。
• 快速：应能快速计算任意给定消息的哈希值。
• 难以分析：输入消息发生微小变化时，输出哈希值应完全改变。
• 不可逆：从哈希值生成一个有效的输入消息应当不可行。也就是说，除了暴力破解（尝试所有可能的输入消息），不应存在明显更好的方法。
• 无碰撞：找到哈希值相同的两条不同消息应当极其困难，或在实践中不可能。

现代密码学哈希函数（如 SHA2 和 SHA3）符合上述性质，广泛用于密码学领域。