Сторнирование хеш-функции

Question

У меня есть следующая хеш-функция, и я пытаюсь найти способ изменить ее, чтобы найти ключ по хеш-значению.

uint Hash(string s)
{
    uint result = 0;
    for (int i = 0; i < s.Length; i++)
    {
        result = ((result << 5) + result) + s[i];
    }
    return result;
}

Код написан на C #, ноЯ предполагаю, что это понятно.

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

РЕДАКТИРОВАТЬ:

Строка, которую принимает функция, формируется только из цифр от 0 до 9 и символов '*' и '#', следовательно, функция Unhash должна соответствовать этому критериютоже.

Есть идеи?Спасибо.

Answer 1

Это должно полностью изменить операции:

string Unhash(uint hash)
{
    List<char> s = new List<char>();
    while (hash != 0)
    {
        s.Add((char)(hash % 33));
        hash /= 33;
    }
    s.Reverse();
    return new string(s.ToArray());
}

Это должно вернуть строку, которая дает тот же хеш, что и исходная строка, но вряд ли она будет точно такой же строкой.

Answer 2

Символы 0-9, *, # имеют значения ASCII 48-57,42,35 или двоичные: 00110000 ... 00111001, 00101010, 00100011

Первые 5 битов этих значений различны, а 6-й бит всегда равен 1. Это означает, что вы можете вывести свой последний символ в цикле, взяв текущий хеш:

uint lastChar = hash & 0x1F - ((hash >> 5) - 1) & 0x1F + 0x20;

(если это не сработает, я не знаю, кто это написал)

Теперь откат хеша,

hash = (hash - lastChar) / 33;

и повторяйте цикл до тех пор, пока хеш не станет равным нулю. У меня нет C #, но я на 70% уверен, что это должно работать только с небольшими изменениями.

Answer 3

Грубая сила должна работать, если значение uint составляет 32 бита.Попробуйте хотя бы 2 ^ 32 строки, и одна из них, скорее всего, хеширует к тому же значению.На современном компьютере это займет всего несколько минут.

У вас есть 12 возможных символов, а 12 ^ 9 - это примерно 2 ^ 32, поэтому, если вы попробуете 9 строк символов, вы, вероятно, найдете целевой хеш.Я буду делать 10 строк символов, чтобы быть в безопасности.

(простая рекурсивная реализация в C ++, не очень хорошо знаю C #)

#define NUM_VALID_CHARS 12
#define STRING_LENGTH 10
const char valid_chars[NUM_VALID_CHARS] = {'0', ..., '#' ,'*'};

void unhash(uint hash_value, char *string, int nchars) {
  if (nchars == STRING_LENGTH) {
    string[STRING_LENGTH] = 0;
    if (Hash(string) == hash_value) { printf("%s\n", string); }
  } else {
    for (int i = 0; i < NUM_VALID_CHARS; i++) {
      string[nchars] = valid_chars[i];
      unhash(hash_value, string, nchars + 1);
    }
  }
}

Затем вызовите его с помощью:

char string[STRING_LENGTH + 1];
unhash(hash_value, string, 0);

Answer 4

Хэш-функции разработаны так, чтобы их было трудно или невозможно повернуть вспять, отсюда и название (визуализируйте измельченное мясо + картофель)

Answer 5

Я бы начал с записи каждого шага, который result = ((result << 5) + result) + s[i]; делает в отдельной строке. Это сделает решение намного проще. Тогда все, что вам нужно сделать, это противоположность каждой линии (также в обратном порядке).