时间戳

首页 > 解决方案 > 给定此哈希函数、预期输出和输入字符串的长度，我如何找到返回给定结果的输入字符串？

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

问题描述

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

我知道对于长度为 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;

}

作为字符串“敏捷”的示例，它的哈希值为 29662550362

标签： javascriptreverse-engineeringbrute-forcehash-function

解决方案

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

g * 82 + d

只要 d 小于 82，g 和 d 的每个可能值都会给出不同的结果，因为 g * 82 和 (g + 1) * 82 之间有足够的空间来适应 82 个不同的d s（从 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的“哈希”相反，它可以用 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);
}

推荐阅读