我正在制作一个存储文档的应用程序，并根据包括时间戳在内的一些内容的 SHA1 摘要为每个文档提供一个 UID。摘要有很多字符，我想让用户通过使用完整摘要的前 x 个字符来识别文档。如果文档数量可能在 10K - 100K 左右，那么 x 有什么好的价值？
问问题
9995 次
5 回答
26
为生日问题调整维基百科上的公式，您可以将碰撞概率近似为1 - e^(-n^2/(2^(b+1)))，其中n是文档数，b是位数。用 n=100,000 绘制这个公式，看起来你至少需要 b > 45。我更倾向于使用 64 以使其成为一个不错的整数。也就是说，如果发生冲突，是否有处理冲突的计划（可能稍微改变时间戳，或者添加一个随机数？）
就此而言，如果 sha1 不仅仅基于文档的内容，为什么不简单地将其设为随机 ID？在这种情况下，冲突问题不大，因为您总是可以生成一个新的随机数并再次尝试（但是，一次尝试的冲突概率是相同的）。
于 2011-01-24T16:33:03.953 回答
3
请注意截断，因为较小的散列是安全的证据并没有减少。请参阅 Kelsey 的http://csrc.nist.gov/groups/ST/hash/documents/Kelsey_Truncation.pdf。Kelsey 给出了相同的启发式参数（“相关哈希输出”和“近乎碰撞”）。Biham/Chen 提供了近乎碰撞的例子；Knudsen 演示了截断微分。
最后，您可能希望将数据输入到具有截断大小的 HMAC（该大小也被 HMAC 消化），然后使用截断的 HMAC。
于 2012-12-18T05:20:16.290 回答
2
这真的没有价值。使 SHA 成为一种良好的通用散列算法的部分原因是相似的数据不一定会产生相似的散列值。您最好的选择（不了解您的系统的任何其他信息）只是搜索其哈希以用户提供的值开头的文档列表，然后向他们提供要从中选择的文档列表或直接转到文档如果只有一个。
于 2011-01-24T16:27:23.750 回答
1
这是生日问题的概括。在您的情况下， n是文档数，而不是常量 365 您将有多种可能性，即截止给您（因此对于 k 位，它是 2 k）。
当然精确计算是不可能的，但你可以使用approximation。
于 2011-01-24T16:30:26.490 回答
0
好吧，这可能是一个过于简单的答案..
如果使用完整的 sha1，您在 2^160 中获得大约 1 的碰撞机会，那么通过截断一个字符，您可以将碰撞的机会增加 16（截断字符的所有可能值）......这是 2^4.. 所以，如果你截断 x 个字符，你会得到 1 in 2^(160 - 4*x) 的碰撞机会.. 对吗？
于 2011-01-24T16:27:40.660 回答