反转哈希函数

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

如果 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);