javascript - 给定此哈希函数、预期输出和输入字符串的长度，我如何找到返回给定结果的输入字符串？

Question

我在下面有这个哈希函数。

我知道对于长度为 8 的输入字符串，我得到一个值为 16530092119764772 的散列

输入的字符串只能由字符“abcdefghijklmnop”组成

查找输入字符串的最佳方法是什么？

有没有一种方法可以在不依赖蛮力查找字符串的情况下从数学上分解问题？

递归解决方案会溢出堆栈吗？

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;

}

以字符串“agile”为例，它散列为 29662550362

Answer 1

这甚至不是真正的哈希，因为 charset 中没有 82 个字符。这更像是将字符串解析为 base-82 数字，您只能使用前 16 个符号。如果它不使用 float ，那将是完全可逆的， float 对于那么大的整数来说是不精确的。如果您不熟悉原因，简化版本是循环内的操作:

g * 82 + d

只要 d 小于 82，g 和 d 的每个可能值都会给出不同的结果，因为 g * 82 和 (g + 1) * 82 之间有足够的空间来容纳 82 个不同的 ds(从 0 到 81)。通过除以 82，每个不同的结果都可逆回到 g 和 d；整数为g，余数为d。当循环内的每个操作都是可逆的时，您就可以逆转整个事情。

因此，就像您可以使用一次除掉一位数字的循环手动将数字转换为十进制一样，您可以将这个不精确的数字转换为基数 82:

const getDigits = (value, base) => {
    const result = [];
  
    while (value) {
        result.push(value % base);
        value /= base;
    }
  
    return result.reverse();
};

const getLetter = index =>
    String.fromCharCode(97 + index);

const getPreimage = value =>
    getDigits(value, 82n)
        .map(Number)
        .map(getLetter)
        .join('');

console.log(getPreimage(29662550362n));
console.log(getPreimage(16530092119764772n));

结果以“i”开头，因为 g 从 8 而不是 0 开始。第二个数字也足够大而不是唯一的(与 agile 对比) s “散列”，可以用 JavaScript 数字精确表示)，但如果您只是想查找任何原像，它就足够了。

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;

}

for (const s of ['hijackec', 'hijacked', 'hijackee', 'hijackef', 'hijackeg']) {
    console.log(s, hash(s) === 16530092119764772);
}