是否有可能通过算法得出具有相同哈希码的不同字符串？

Question

在 Java 中，我们知道一些字符串的示例，尽管它们是不同的字符串，但它们具有相同的哈希码，例如

Ea

和

FB

都具有

2236

的哈希码。

考虑到我们知道每种语言中使用的确切哈希算法，是否有一种算法方法可以提供更多共享哈希代码的不同字符串的示例，而无需对许多字符串进行强力测试？

Answer 1

考虑到我们知道每种语言中使用的确切哈希算法，是否有一种算法方法可以提供更多共享哈希代码的不同字符串的示例，而无需对许多字符串进行强力测试？

有时。 让我们以 Java 为例...“Ea 和 FB 的哈希码均为 2236”并考虑哈希函数（此处为 C++，且仅适用于 ASCII 字符串）：

int java_hash(const std::string& s) {
    int hash = 0;
    for (char c : s) (hash *= 31) += c;
    return hash;
}

我们可以看到它是从第一个字符的值开始的。 然后，对于两个字符的字符串，它将乘以 31 并添加下一个字符。

假设我们概括并解释这一点：我们有一个两个字符的字符串 KL（例如，对于“Ea”，K == 'E' 且 L == 'a'）；哈希值最终为 31K + L。然后为了找到冲突的键，我们可以尝试将 K 增加到下一个字符值（例如“F”），这会将哈希输出增加 31，因此为了平衡我们减少 L 的字符值除以 31（即 'a'==ASCII 97 回到 'B'==66）。

我们可以通过增加到“G”并减少到“#”来找到另一个碰撞。

或者，我们可以朝另一个方向移动：如果新的 L 值超出了字符类型的有效值范围，我们可以减少 K 并将 L 增加 31，仍然对字符值产生净 0 影响，但在这种特殊情况下，“Ea”需要“E”变为“D”，“a”变为 128，这在您的字符串类型中可能有效，也可能无效。

如果我们添加更多字符，我们可以观察到一些有趣的事情 - 整体哈希值变得更加复杂，但是为了创建冲突，我们仍然可以以相同的方式修改最后两个字符，确保它们对整体哈希值的影响对于我们的碰撞键来说是净零。

随着散列函数越来越好，这种分析变得越来越困难，而对于不妥协的密码强度函数，即使对于专业数学家来说，它也应该是不切实际的。 （这就是为什么我们看到加密货币挖掘必须使用强力搜索关键字段中的“nonce”值，寻求为块创建所需的整体哈希值。）