哈希函数

[q464824151]

  哈希函数，或者叫散列函数，是一种从任何一种数据中创建一个数字指纹（摘要）的方法，散列函数把数据压缩压缩（或者放大）成一个长度固定的摘要。

  哈希函数的输入空间（文本或者二进制数据）是无限大，但是输出空间（一个固定长度的摘要）却是有限的。将「无限」映射到「有限」，不可避免的会有概率不同的输入得到相同的输出，这种情况我们称为碰撞（collision）。

  一个简单的哈希函数是直接对输入数据/文本的字节求和。它会导致大量的碰撞，例如 hello 和 ehllo 将具有相同的哈希值。

  更好的哈希函数可以使用这样的方案：它将第一个字节作为状态，然后转换状态（例如，将它乘以像 31 这样的素数），然后将下一个字节添加到状态，然后再次转换状态并添加下一个字节等。这样的操作可以显着降低碰撞概率并产生更均匀的分布。
一个好的「加密哈希函数」必须满足抗碰撞（collision-resistant）和不可逆（irreversible）这两个条件。
  抗碰撞是指通过统计学方法（彩虹表）很难或几乎不可能猜出哈希值对应的原始数据，而不可逆则是说攻击者很难或几乎不可能从算法层面通过哈希值逆向演算出原始数据。一个理想的加密哈希函数，应当具有如下属性：

• 快速：计算速度要足够快；
• 确定性：对同样的输入，应该总是产生同样的输出；
• 难以分析：对输入的任何微小改动，都应该使输出完全发生变化；
• 不可逆：从其哈希值逆向演算出输入值应该是不可行的。这意味着没有比暴力破解更好的破解方法。
• 无碰撞：找到具有相同哈希值的两条不同消息应该非常困难（或几乎不可能）。

  现代加密哈希函数（如 SHA2 和 SHA3）都具有上述几个属性，并被广泛应用在多个领域，各种现代编程语言和平台的标准库中基本都包含这些常用的哈希函数。