4

我通过散列包含所有这些信息的字符串并比较散列对象的十六进制摘要来比较个人的个人信息，特别是他们的姓名、出生日期、性别和种族。这会产生一个 32 位的十六进制数，我将其用作数据库中的主键。例如，使用我的识别字符串将像这样工作：

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

在这一点上，我正在尝试确定碰撞风险。我的理解是 MD5 没有明显的碰撞风险，至少对于我的相对较小的字符串（长度约为 20-40 个字符）而言。但是，我使用的不是 128 位摘要对象，而是 32 位十六进制摘要。

现在，我相信 hexdigest 是对摘要的压缩（也就是说，它存储在更少的字符中），所以在比较 hexdigest 时不会增加冲突的风险吗？还是我不在基地？

4

2 回答 2

5

现在，我相信 hexdigest 是对摘要的压缩（也就是说，它存储在更少的字符中），所以在比较 hexdigest 时不会增加冲突的风险吗？还是我不在基地？

[...]

我想我的问题是：不同的表示是否有不同的机会是非唯一的，这取决于他们使用多少信息单元来进行表示与原始消息需要多少信息单元进行编码？如果是这样，最好的表示是什么？嗯，让我在你的下一个答案前言：像我 10 岁一样跟我说话

老问题，但是是的，可以这么说，你有点离谱。

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

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

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

越短越好（在身份验证令牌等中），但每个表示具有完全相同的信息和碰撞机会。较短的表示较短，原因与“55”比“110111”短的原因相同，但仍编码相同的内容。

这个答案也可能会澄清一些事情，以及玩弄如下代码：

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

...或其他语言中的等价物（上面的 Java/Scala）。

在更实际的层面上，

[...] 我在数据库中用作主键

我不明白为什么不通过使用普通的自动递增 id 列（在 MySQL 中，在 PostgreSQL 中）来消除任何冲突的机会。BIGINT AUTO_INCREMENTBIGSERIAL

于 2015-12-20T02:55:02.210 回答
2

缩写的 32 位十六进制摘要（8 个十六进制字符）不足以有效保证用户数据库的无冲突。

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

如果我传入 2^32 组字符串，md5 冲突的概率是多少？

使用 32 位密钥意味着您的软件将在大约 10,000 个用户时开始崩溃。 碰撞概率约为 1%。 在那之后它变得非常迅速。在 100,000 个用户时，冲突概率为 69%。

一个 64 位密钥，一个 100 亿用户是另一个突破点，大约 2.7% 的碰撞率。

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

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

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

于 2015-07-02T02:36:48.063 回答