MD5摘要与十六进制摘要的碰撞风险比较。

Question

我正在比较个人信息，具体包括姓名、出生日期、性别和种族。我通过哈希一个包含所有这些信息的字符串，并比较哈希对象的十六进制摘要来进行比较。这会产生一个32位的十六进制数字，我将其用作数据库中的主键。例如，使用我的标识字符串将按以下方式工作：

>> import hashlib
>> id_string = "BrianPeterson08041993MW"
>> byte_string = id_string.encode('utf-8')
>> hash_id = hashlib.md5(bytesring).hexdigest()
>> print(hash_id)
'3b807ad8a8b3a3569f098a575091bc79'

目前，我正在尝试确定碰撞风险。我的理解是，在字符串相对较小的情况下（大约20-40个字符），MD5没有显着的碰撞风险。但是，我并没有使用128位摘要对象，而是32位十六进制摘要。

现在，我认为十六进制摘要是摘要的压缩形式（即它存储在较少的字符中），因此在比较十六进制摘要时是否存在增加的碰撞风险？还是我误解了？

- Brian Peterson

---

32个字符·每个字符4位=128位 - Gumbo

啊，所以hexdigest是表示哈希的正确方式，不会增加非唯一性的风险？ - Brian Peterson

好的，我想我的问题是：不同的表示法是否有不同的机会成为非唯一的，这取决于它们用多少信息单元来进行表示，以及原始消息需要编码多少信息单元？如果是这样，那么最好使用哪种表示法？嗯，让我先说一下你下一个回答：像对待一个10岁的孩子一样和我交流。 - Brian Peterson

我已经看完了。那么最后一个问题：如果在一段时间内，散列函数没有出现冲突，我是否可以假定我的十六进制ID都是唯一的？ - Brian Peterson

我正在从事一个开源项目——你可以在这里找到它——该项目为Cook County监狱人口数据提供API。我们决定一开始不在数据库中包含个人身份信息，包括姓名和出生日期（后者可以大大缩小某个人的范围）。然而，我正在扩展我们的数据库模式——直到现在，我们使用系统分配的监狱ID作为囚犯对象的主键。现在，我想跟踪个人本身——仍然是匿名的——以便我们可以看到累犯的现象。 - Brian Peterson

Answer 1

现在，我认为hexdigest是digest的压缩（也就是说，它用更少的字符存储），因此比较hexdigest时会增加碰撞的风险，对吗？还是我想多了？

[...]

我想我的问题是：不同的表示法是否有不同的非唯一机会，这取决于它们用多少个信息单元来进行表示，以及原始消息需要编码多少个信息单元？如果是这样，最好使用哪种表示法？呃，让我先说一下你下一个回答：像我十岁一样跟我说话。

旧问题，但是是的，你有点偏离基础base，可以这么说。

重要的是随机位数，而不是演示文稿的长度。

摘要只是一个数字，一个整数，可以使用不同数量的不同数字将其转换为字符串。例如，以某些不同的进制显示的128位数字：

"340106575100070649932820283680426757569" (base 10)
"ffde24cb47ecbff8d6e461a67c930dc1" (base 16, hexadecimal)
"7vroicmhvcnvsddp31kpu963e1" (base 32)

较短的表示更加简洁和便捷（在授权令牌等方面），但每个表示都具有相同的信息和碰撞几率。较短的表示之所以较短，是因为与“110111”相比，“55”更短，但仍编码相同的内容。 本答案可能也能澄清问题，还可以玩弄类似以下代码的东西：

new BigInteger("340106575100070649932820283680426757569").toString(2)

...或者在其他语言中使用类似的方式（如Java/Scala）。

更实际的是，

[...] 我将其用作数据库中的主键

我不明白为什么不使用普通的自增id列（MySQL中的BIGINT AUTO_INCREMENT，PostgreSQL中的BIGSERIAL）来消除任何碰撞的机会。

- Jonik

---

这是一个很好的答案 - 谢谢！关于为什么不只使用普通的自增ID的问题，如果你使用哈希，你可以通过知道底层数据简单地在数据库中找到相关记录。然而，如果你使用自增键（我确实用于某些目的），你需要该键才能找到记录（即使你已经知道了该记录，也不能直接访问）。哈希还提供了速度优势，当你想要快速搜索一长串字段组合而不必枚举查询中的每个字段时。 - Ben

Answer 2

一个只有8位十六进制字符的32位摘要无法有效地保证用户数据库是无冲突的。

生日碰撞概率公式在这里：

https://dev59.com/UmUp5IYBdhLWcg3w5Kk6

使用32位密钥意味着您的软件会在大约10,000个用户处开始出现问题。 碰撞概率约为1％。 在此之后，情况会迅速恶化。 在100,000个用户时，碰撞概率为69％。

在拥有100亿用户（可预见未来地球人口的慷慨上限）时，64位密钥是另一个破坏点，具有约2.7％的碰撞率。

对于拥有1000亿个用户的情况（可预见未来地球人口的慷慨上限），我认为96位密钥有点冒险。碰撞几率约为一亿分之一。实际上，您需要一个128位密钥，它可以提供约1X10 ^ -17的碰撞率。

128位密钥长度为128/4 = 32个十六进制字符。如果您想使用更短的密钥以美观为目的，您需要使用23个字母数字字符才能超过128位。或者如果使用可打印字符（ASCII 32-126），则可以使用20个字符。

因此，当您在谈论用户时，至少需要128位以获得无冲突的随机密钥，或者长度为20-32个字符的字符串，或者128/8 = 16字节的二进制表示。

- David Beckwith