Учитывая эту хеш-функцию, ожидаемый результат и длину входной строки, как мне найти входную строку, которая возвращает данный результат? - PullRequest
Новая
       23

Учитывая эту хеш-функцию, ожидаемый результат и длину входной строки, как мне найти входную строку, которая возвращает данный результат?

2 голосов
/ 30 марта 2019

У меня есть эта хеш-функция ниже.

Я знаю, что для входной строки длиной 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

Ответы [ 2 ]

1 голос
/ 30 марта 2019

Это даже не хеш, потому что в charset нет 82 символов.Это больше похоже на синтаксический анализ строки как числа base-82, где вы можете использовать только первые 16 символов.Это было бы полностью обратимо, если бы оно не использовало числа с плавающей точкой, которые неточны для целых чисел такого большого размера.В случае, если вы не знаете, почему, упрощенная версия заключается в том, что операция внутри цикла: 

g * 82 + d

дает различный результат для каждого возможного значения g и d, если d меньше 82потому что между g * 82 и (g + 1) * 82 достаточно места для 82 различных d s (от 0 до 81).Каждый другой результат обратим обратно к g и d путем деления на 82;все значение 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);
}
0 голосов
/ 30 марта 2019

Вы можете создать рекурсивную функцию, которая начинается с 8, выполняет итерацию по индексам кодировки и останавливается (возвращает) всякий раз, когда текущее значение превышает переданный хеш.

Проверьте комментарии ниже для более подробной информации: 

const charset = 'abcdefghijklmnop';

function bruteforce(hash, base = 8, result = {value: ''}) {
  // Always multiply the previous value by 82
  base *= 82;

  for (let i = 0; i < charset.length; i++) {
    // Add the char index to the value
    value = base + i;
    // If we found the hash, append the current char and return
    if (value === hash) {
      result.value += charset[i];
      return base === 656 ? result.value : value;
    }
    // If we went past the hash, return null to mark this iteration as failed
    if (value > hash) {
      return null;
    }
    // Otherwise, attempt next level starting from current value
    value = bruteforce(hash, value, result);
    // If we found the hash from there, prepend the current char and return
    if (value === hash) {
      result.value = charset[i] + result.value;
      return base === 656 ? result.value : value;
    }
  }

  // We tried everything, no match found :(
  return null;
}

console.log(bruteforce(29662550362));
...