哈希算法是否存在可以保证唯一性的情况？

Question

如果我使用比数据更大的字节大小的哈希算法（例如sha-256）对大小受限的相似数据（例如社会安全号码）进行哈希，那么哈希是否保证与原始数据具有相同的唯一性水平？

- matt

Answer 1

哈希碰撞的概率与输入字符串的大小无关（除了表明需要保持唯一性的输入数量）。即使使用完美哈希算法，当您对0和1进行哈希时，也可能发生哈希碰撞，尽管可能性为1/（2^位长度）。在SHA-256的情况下，这几乎是零。

哈希碰撞是生日悖论问题。在256位哈希的情况下，两个输入之间发生碰撞的概率纯粹取决于输入计数，公式如下：

1 - (2^256)! / ((2^256^inputcount) * (2^256-inputcount)!) 或者其他人已经说过的——对于合理数量的输入基本上为零。

- Michael Mullany

---

真的。我并不质疑安全方面的影响。我想知道当数据大小小于哈希值大小时，哈希的唯一性概率是多少。（我需要得到确定性/可重复的结果值，所以对x字节进行随机盐处理对我来说行不通。我可能会通过每个实现添加常量字符来“加盐” - 例如，在哈希之前，我可能会将类似于“593jra”的字符附加到社保号码上）。 - matt

生日悖论不是基于鸽巢原理吗？如果是的话，在理论上我没有鸽巢场景。 - matt

鸽巢原理是一个简单的概念，即当你有比鸽巢更多的物品时，你保证会发生碰撞。生日悖论只是说，如果你的物品与鸽巢的比率“高”，那么你非常有可能会发生碰撞。其中，“高”由上述公式定义。 - Michael Mullany

我相信你的公式中不需要 1 - 这一部分，除非你想要表达没有碰撞的概率。顺便问一下，你能给我们提供这个公式的来源吗？ - Zoltán

Answer 2

您可以创建一个自定义哈希，以确保唯一性。对于已知域中的数据（例如社会安全号码），这个过程相对简单。

如果您的目标哈希值实际上比正在哈希的内容具有更多的位数，则哈希将简单地将输入值映射到可用输出值之一。这将是从输入值作为多字节整数到输出作为多字节整数的简单线性映射。

当您的目标哈希值比正在哈希的内容少时，就无法保证唯一性。

- S.Lott

---

谢谢。我正在考虑对社会安全号码和“账户”标识符进行哈希处理，这些标识符可能因每个实现而异。因此，如果我可以使用哈希函数而不是预生成的函数，那将是更可取的。 - matt

如果遮盖社会安全号码是目标，那么实施一对一线性映射函数是不够的，因为从一些输出样本中计算原始输入将变得相当容易。此外，输入字符串的长度绝对不会影响加密安全哈希函数的有效性，因此使用已知的哈希算法是正确的选择。 - Silvio Donnini

Answer 3

其他人已经指出，碰撞不应该是一个问题；这就是加密安全哈希函数的全部意义。我想补充一下以下内容：

• 如果您的输入集足够小（例如数据为SSN——少于十亿），那么缺少冲突是可以验证的：只需详尽测试即可。
• 如果输入集太大而无法进行详尽扫描，则预计无法证明缺少冲突。良好的哈希函数被期望作为随机预言机，并且在随机预言机上，您无法在不详尽尝试的情况下证明此属性。能够证明缺少冲突将可疑地看起来像函数的弱点。

- Thomas Pornin

Answer 4

如果您正在使用像SHA这样的加密哈希函数，那么简短的答案是肯定的。

- Die in Sente

---

谢谢。我也是这么想的，但我找不到支持这个想法的参考资料，而且我不够聪明去深入研究数学并得出结论！ - matt

如上所述，加密哈希只是意味着碰撞极为不可能，而非不可能。 - Phil Miller

原问题的简短回答是肯定的。虽然理论上可能发生碰撞，但找到碰撞的平均时间比太阳演化为红巨星并毁灭地球所需的时间要长得多。 - Die in Sente

@Novelcrat。附言：如果您能够发布两个产生相同 SHA-256 哈希值的 10 位 SSN，我将支付您 $1,000 美元。 - Die in Sente

@DieinSente 我找到了它们！付钱给我，我会告诉你。:P - Andrew

Answer 5

加密安全哈希函数的一个关键特征是，无论输入是什么，你都可以毫无疑虑地安全免于碰撞。这也适用于比输出大小更短的输入，这与具有较小熵的较长消息相同。因此，您可以使用SHA-2而不必担心碰撞。

- Silvio Donnini