已知特定哈希函数与哈希值，如何反推长度为8的合规输入字符串

嘿，这个问题真的很巧妙——我们完全不用暴力破解，靠数学逆向推导就能轻松找到输入字符串，而且递归方案也根本不会栈溢出。让我给你一步步拆解清楚：

先看看原哈希函数的计算逻辑：

function hash(str) { 
  let g = 8; 
  let charset = "abcdefghijklmnop"; 
  for(let i = 0; i < str.length; i++) { 
    g = (g * 82 + charset.indexOf(str[i])); 
  } 
  return g; 
}

假设输入的8个字符对应的索引是 c0, c1, c2, c3, c4, c5, c6, c7（每个索引是0-15，对应charset里的a-p），把迭代过程展开后，最终的哈希值H其实是一个以82为基数的多项式：

H = 882⁸ + c082⁷ + c182⁶ + c282⁵ + c382⁴ + c482³ + c582² + c682 + c7

因为每个c_i都小于82（最大是15），所以我们可以通过逆向取模+除法的方式，从后往前逐个解出每个字符的索引——这就像把一个十进制数拆解成各个数位一样，只不过这里的基数是82。

已知哈希值H = 16530092119764772，输入长度为8，charset是abcdefghijklmnop，我们一步步来：

1. 取最后一个字符c7：c7 = H % 82 = 16530092119764772 % 82 = 4，对应字符是e；然后更新H = (H - c7)/82 = (16530092119764772 -4)/82 = 201586489265424
2. 取倒数第二个字符c6：c6 = 201586489265424 %82 =4，对应字符e；更新H=(201586489265424-4)/82=2458371820310
3. 取c5：2458371820310%82=10，对应字符k；更新H=(2458371820310-10)/82=29980144150
4. 取c4：29980144150%82=2，对应字符c；更新H=(29980144150-2)/82=365611514
5. 取c3：365611514%82=0，对应字符a；更新H=(365611514-0)/82=4458677
6. 取c2：4458677%82=9，对应字符j；更新H=(4458677-9)/82=54374
7. 取c1：54374%82=8，对应字符i；更新H=(54374-8)/82=663
8. 取第一个字符c0：663%82=7，对应字符h；更新H=(663-7)/82=8，正好回到初始的g=8，验证正确！

把这些字符按顺序拼接起来，就是输入字符串：hijackee

暴力破解需要尝试16^8=4294967296次，这在普通机器上根本不现实；而逆向计算只需要8次模运算和除法，瞬间就能得到结果，效率天差地别。

完全不会！因为输入长度固定为8，递归的深度最多只有8层，远低于JavaScript默认的栈限制（一般是几千层以上）。比如我们可以写这样一个递归函数：

function reverseHash(hashVal, remainingLength, charset) {
  if (remainingLength === 0) return '';
  const charIndex = hashVal % 82;
  const currentChar = charset[charIndex];
  const newHash = (hashVal - charIndex) / 82;
  // 递归计算前面的字符，再拼接当前字符
  return reverseHash(newHash, remainingLength - 1, charset) + currentChar;
}

// 调用示例
const targetHash = 16530092119764772;
const charset = "abcdefghijklmnop";
const inputStr = reverseHash(targetHash, 8, charset);
console.log(inputStr); // 输出 "hijackee"

这个函数只会递归8次，栈完全没有压力。当然你也可以用迭代实现，逻辑一样，只是递归写法更简洁。

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