php - Sha1 子字符串问题

Question

我正在制作一个 pastebin 类型的网站，并试图使 id 成为一个随机字符串，如 paste.com/4RT65L

在将其添加到数据库之前，我正在获取 id 的 sha1，但我正在获取 sha1 的前 8 个字符的子字符串。他们有可能成为同一个 sha1 的双重副本吗？我不希望他们意外地成为第二个带有已经使用过的 id 的粘贴？

Answer 1

好吧，在 8 个字符中发生冲突的几率明显高于与两个 Sha1 键发生冲突的几率，但这并不意味着它很可能会发生。

我建议您对其进行一些测试。生成随机输入并查看发生碰撞之前需要多长时间。如果你喜欢结果，那就去吧。否则，您将需要更长的字符串。

编辑：您还可以通过查看生日悖论来计算碰撞的几率。

基本上，如果您从 SHA-1 中获取前 8 个十六进制数字，那么您有 16**8 (4,294,967,296) 种不同的可用组合。

使用在线 Birthay Paradox 计算器，经过大约 9200 次哈希后，您将有 1% 的机会发生碰撞。在你有 10% 的机会之前需要大约 30,000 次哈希，在你有 50% 的机会之前需要 77,000 次。

重要的是要指出，只要您的哈希函数在伪随机方面做得不错，您使用哪个（无论是 SHA1、MD5 还是任何形式的校验和）都没有关系——这些数字假设完全随机的输入，因此您只能通过使用越来越好的哈希函数来处理这些值。

所以最后，这取决于你期望有多少流量。如果这是一个小站点，您可能可以侥幸逃脱。如果是大量的交通，那么你的碰撞几率非常高。

Answer 2

在分配 id 之前，您可以随时检查它是否未被占用...或者更好的是，在数据库字段上放置一个唯一的 id...问题解决了。:)

等等，你说 SHA1 的 id。你不是说autoinc id吧？我的第一个猜测是：

356a192b
da4b9237
77de68de

如果您使用的是随机 id，为什么要在其上运行 sha1？

Answer 3

我想通了，我的代码是：

strtoupper(substr(sha1($token_start . $id . $token_end), 0, 8))

其中 $id 是通过找出数据库中 id 的总数 + 1 获得的 id，因为它是自动递增的，所以它是下一个 id。

然后当它插入条目时，它会插入加密的。

$token_start 和 $token_end 都是随机字符串，您可以选择使新 id 唯一。

我做了一个循环，将它们插入数据库 32 000 次，只是 id、自动增量以及新的 id，我用不同的方式进行了搜索，没有得到任何重复项。这对我来说绰绰有余。任何评论都会有所帮助。我不知道需要多长时间才能让我发生碰撞。如果有人知道第一个是什么时候，那就太棒了。