已知哈希算法，如何通过非暴力算法生成同哈希的不同字符串？

当然可以，只要明确目标语言的字符串哈希算法（比如Java的String哈希规则），完全可以通过数学推导而非暴力枚举的方式批量生成哈希值相同的不同字符串。

先明确Java String的哈希计算规则 #

Java中String的哈希值计算逻辑核心如下：

public int hashCode() {
    int h = 0;
    for (char c : value) {
        h = 31 * h + c;
    }
    return h;
}

用数学公式表达就是：对于字符串 s = c₀c₁c₂...cₙ₋₁，哈希值为：
h = c₀×31ⁿ⁻¹ + c₁×31ⁿ⁻² + ... + cₙ₋₁

非暴力生成碰撞的具体方法 #

1. 基于已知碰撞对扩展

比如你提到的Ea和FB哈希均为2236，我们可以直接在这两个字符串的相同位置拼接相同内容，生成新的碰撞对：

• 后缀拼接：EaX 和 FBX（X为任意字符），两者哈希都是 31×2236 + 'X'，结果必然相等
• 前缀拼接：XEa 和 XFB，由于31×'E'+'a' = 31×'F'+'B'（原碰撞对的哈希），整体哈希值完全一致
• 多段拼接：比如EaABC 和 FBABC，同理哈希值完全相同

2. 构造等价字符组合

从哈希公式出发，我们可以直接推导满足哈希相等的字符组合。以双字符为例，需要找到两组字符(c1,c2)和(d1,d2)，满足：
31×c1 + c2 = 31×d1 + d2
整理后得到：31×(c1 - d1) = d2 - c2

比如取c1 - d1 = -1，则d2 - c2 = -31：

• 取c1='E'(69)，d1='F'(70)，d2='B'(66)，则c2=66+31=97('a')，这就是你提到的Ea和FB的组合
• 换一组：取c1='D'(68)，d1='E'(69)，d2='A'(65)，则c2=65+31=96('')，得到碰撞对D（字符串D）和EA`，两者哈希均为2204

通过调整c1-d1的取值（比如1、2等），可以批量生成无数个双字符碰撞对。

3. 构造更长字符串的碰撞

基于上述双字符碰撞对，我们可以对任意字符串进行局部替换，生成哈希相等的新字符串：

• 比如原字符串是ABCDE，将其中的AB替换为对应的碰撞对X（假设AB和X哈希相等），得到XCDE`，两者哈希必然相等
• 也可以组合多个碰撞对，比如EaFB和FBEa，因为Ea与FB哈希相等，整体加权和完全一致

扩展到其他语言 #

这种方法并非Java独有，只要目标语言的字符串哈希算法是公开且固定的，都可以通过分析其哈希计算的数学逻辑，找到等价的字符/字符序列组合，从而非暴力生成哈希碰撞字符串。

内容的提问来源于stack exchange，提问作者Aamir