哈希攻击：查找具有相同 hashCode() 的长度为 2^N 的字符串

Question

阅读 Robert Sedgewick 和 Kevin Wayne 合着的算法第四版我发现了以下问题：

Hash attack: find 2^N strings, each of length 2^N, that have the same hashCode() value, supposing that the hashCode() implementation for String is the following:

public int hashCode() {
   int hash = 0;
   for (int i = 0; i < length(); i++)
      hash = (hash * 31) + charAt(i);
   return hash;
}

Strong hint: Aa and BB have the same value.

我想到的是生成所有可能的长度为 2^N 的字符串并比较它们的哈希码。然而，这对于大 N 来说非常昂贵，我怀疑这是正确的解决方案。你能给我提示我在整个画面中遗漏了什么吗？

Answer 1

"Strong hint" 解释。

Strong hint: Aa and BB have the same value.

在 ASCII / Unicode 中，B 的值比 A 大 1。由于这些是倒数第二个字符，该值乘以 31，因此当您将 xxxxAa 更改为 xxxxBa 时，哈希码增加 31。

要抵消它，您需要将最后一个字符抵消 -31。由于小写字母比大写字母高32位，所以把a改成A就是-32，把一个字母改成B就是-31.

因此，它获得相同的哈希码，将倒数第二个字母更改为下一个字母（例如 A 更改为 B），并将最后一个字母从小写更改为下一个大写（例如 a 到 B).

您现在可以使用该提示生成最多 26 个具有相同哈希码的字符串。

Answer 2

让我们看一下 hashCode() 实现和给出的提示：

public int hashCode() {
    int hash = 0;
    for (int i = 0; i < length(); i++)
        hash = (hash * 31) + charAt(i);
    return hash;
}

我们知道 Aa 和 BB 产生相同的 hash 我们可以很容易地验证：

(65 * 31) + 97 = 2112
(66 * 31) + 66 = 2112

从这里开始，hash 对两个输入是相同的。也就是说，我们可以轻松地向两个字符串附加任意数量的字符，并且您将始终收到相同的值。

一个例子可以是：

hashCode("AaTest") = 1953079538
hashCode("BBTest") = 1953079538

因此，您只需将相同的字符序列附加到两个字符串即可生成足够的哈希值，更正式地说：

hashCode("Aa" + x") = hashCode("BB" + x)

关于生成所有可能的字符串并搜索重复项的想法的另一个说明。看一下 bithday paradox，您会注意到为不同的输入查找重复的哈希值所花费的时间要少得多。

找到原始散列值将非常困难（事实上，如果散列算法很好，您将不得不尝试所有可能的输入）。
重复的散列值很少见（因为散列的长度是固定的，所以必须有重复的）。如果发现重复项，则重复项应无意义（随机字符），因此不会被攻击者滥用。

Answer 3

Andreas 和 Glains 的答案都是正确的，但如果您的目标是产生 2^{N[=41，那么它们并不是您所需要的=] 长度为 2N.}

的不同字符串

相反，一种更简单的方法是构建仅由 Aa 和 BB 的串联序列组成的字符串。对于 2×1 的长度，您有 { Aa, BB }；对于长度 2×2 你有 { AaAa, AaBB, BBAa, BBBB }, 对于长度 2×3 你有 { AaAaAa, AAaaBB、AaBBAa、AaBBBB、BBAaAa、BBAaBB、BBBBAa、BBBBBB }；等等。

（注意：您引用的文字是说字符串的长度应为 2^N。我猜您被错误引用，它实际上要求长度 2N; 但如果它确实要求长度 2^N, 然后您可以在继续时简单地删除元素。)

Answer 4

仔细看看散列函数，它的工作原理类似于数字系统（例如十六进制），其中数字的权重为 31。也就是说，将其视为将数字转换为基数 31，这使您的最终哈希码类似于 hashCode = (31^n) * first-char + (31^n-1) * second-char + ..... + (31^0) * last-char

第二个观察是大写字母和小写字母之间的ASCII距离是32。用hash函数来解释，意思是当你用小写字母替换大写字母时，意味着你在添加高位加 1，当前位加 1。例如：

BB = (31)(B) + (31^0)B 也等于 (31)*(B - 1) + (31^0)*(31 + B) 请注意，我刚刚从较高的数字中取出一个单位并添加到较低的数字中，而没有改变整体值。最后一个等式等于 (31)*(A) + (a) == Aa

因此，要生成给定哈希码的所有可能字符串，请从初始字符串开始，将字符从右向左移动，方法是将小字符替换为大写字符，同时从较高位置开始递减字符 (适用时）。你可以在 O(1)

中运行

希望这对您有所帮助。

哈希攻击：查找具有相同 hashCode() 的长度为 2^N 的字符串

Hash attack: find strings of length 2^N with same hashCode()

java

string

algorithm

hash

hashcode