反转字符串哈希函数

Question

我有以下函数，用于哈希一个字符串:

public static uint hashString(string myString)
{
     uint hash = 0;

     foreach (char c in myString)
     {
         hash *= 0x1F;
         hash += c;
     }

     return hash;
}

如果我想将“hello”哈希，它会生成“99162322”。

是否可能编写一个反向函数，输入一个数字并输出字符串（假设字符串结果未知）？

- Helen Che

---

哈希值并不等同于加密，它更像是校验和。 - Sir Rufo

哈希算法最多能做的就是获取一些输入，当哈希后会产生与原始哈希相同的哈希值。但并不能保证你会得到原始字符串。根据哈希算法的复杂性，获取生成给定哈希值的输入可能很困难或需要长时间运行。 - Lasse V. Karlsen

Answer 1

由于您没有使用加密哈希算法，因此您的实现很容易被反向破解（即返回给定哈希值的一些字符串）

代码:

public static uint hashString(string myString) {
  //DONE: validate public methods' parameters
  if (null == myString)
    return 0;

  uint hash = 0;

  //DONE: hash function must never throw exceptions
  unchecked {
    foreach (char c in myString) {
      hash *= 0x1F;
      hash += c;
    }
  }

  return hash;
}

private static string HashReverse(uint value) {
  StringBuilder sb = new StringBuilder();

  for (; value > 0; value /= 31) 
    sb.Append((char)(value % 31));

  return string.Concat(sb.ToString().Reverse());
}

示例: (给定一个 哈希值，我们生成一个 字符串 并计算出从中检查的 哈希值)

uint[] tests = new uint[] {
  99162322,
  123,
  456
};

// Since the string can contain control characters, let's provide its Dump
string Dump(string value) => string.Join(" ", value.Select(c =>((int) c).ToString("x4")));

string report = string.Join(Environment.NewLine, tests
  .Select(test => new { 
    test,
    reversed = HashReverse(test)
  })
  .Select(item => $"{item.test,9} :: {Dump(item.reversed),-30} :: {hashString(item.reversed),9}"));

Console.WriteLine(report);

结果：

 99162322 :: 0003 000e 000b 0012 0012 0012  ::  99162322
      123 :: 0003 001e                      ::       123
      456 :: 000e 0016                      ::       456

请注意，很多字符串（例如"hello"和"\u0003\u000e\u000b\u0012\u0012\u0012"）会产生相同的哈希值。这是由于哈希函数本身存在冲突导致的。

- Dmitry Bychenko

Answer 2

不。

哈希的基本原则之一是它是不可逆的。

有许多字符串可以产生哈希值99162322，因此尽管可能可以找到所有这些字符串（给定最大字符串长度），但没有办法确定哪个是“正确”的。

- Jasper Kent

---

抱歉，但由于hashString不是加密哈希，因此很容易被反转。 - Dmitry Bychenko

只有在字符串长度有限制的情况下才会出现这种情况。 - Jasper Kent

这取决于您对“reverse”的定义。OP想要原始字符串，获取一个字符串是可行的，但获取原始字符串不可行。 - Lasse V. Karlsen