我目前使用SHA1算法来缩短网址：
Digest::SHA1.hexdigest("salt-" + url)
像GitHub一样，只使用SHA1的前8个字符作为唯一标识符有多安全？
4个回答
11
要计算给定长度和哈希数量的碰撞概率，请参见生日悖论。不知道您将拥有多少个哈希值，但以下是一些示例。8个十六进制字符是32位，因此对于大约100个哈希值，碰撞的概率约为1/1,000,000；对于10,000个哈希值，概率约为1/100；对于100,000个哈希值，概率为3/4等。
请查看维基百科上生日攻击文章中的表格，以找到一个满足您需要的好哈希长度。例如，如果您想要在超过100,000个哈希值的集合中使碰撞概率小于1/1,000,000,000，则使用64位或16个十六进制数字。
所有这些都取决于您将拥有多少个哈希值以及您愿意接受多大的碰撞概率（因为即使是极其小的概率，也总会存在一定的碰撞可能性）。
请查看维基百科上生日攻击文章中的表格，以找到一个满足您需要的好哈希长度。例如，如果您想要在超过100,000个哈希值的集合中使碰撞概率小于1/1,000,000,000，则使用64位或16个十六进制数字。
所有这些都取决于您将拥有多少个哈希值以及您愿意接受多大的碰撞概率（因为即使是极其小的概率，也总会存在一定的碰撞可能性）。
- rsp
7
如果你是在谈论SHA-1的十六进制表示，则每个字符只有4位，总共32位。发生碰撞的概率与该最大值的平方根成反比，约为1/65536。如果你的URL缩短器使用频繁，很可能不久就会开始出现碰撞。
至于替代方案，最明显的可能是仅维护一个计数器。由于需要存储一个URL表以将缩短后的URL转换回原始URL，因此基本上只需将每个新URL存储在表格中。如果它已经存在于表格中，则赋予其现有的数字。否则，插入它并赋予一个新数字。无论哪种方式，都将该数字提供给用户。
至于替代方案，最明显的可能是仅维护一个计数器。由于需要存储一个URL表以将缩短后的URL转换回原始URL，因此基本上只需将每个新URL存储在表格中。如果它已经存在于表格中，则赋予其现有的数字。否则，插入它并赋予一个新数字。无论哪种方式，都将该数字提供给用户。
- Jerry Coffin
1
缩短器首先不会被大规模使用 - 我们计划将其用于跟踪目的; 最终用户不必复制/粘贴它。我们希望获得相当短的URL，而不是长的SHA1; 你有其他算法建议吗？ - Thibaut Barrère
3
这取决于你想要达成什么目标。SHA1的输出对输入（一个好的哈希函数的输出根据输入中的一位改变，有一半的位数会改变，而SHA1虽然不完美但很好）实际上是随机的，通过取160位输出的32位（假设为8个十六进制数字），你将输出空间从2^160减小到了2^32个值。所有事情都保持相等，尽管它们永远不可能相等，但这将显著降低查找碰撞的难度。
然而，如果哈希函数的输入必须是有效的URL，那将大大减少可能的输入数。@rsp指出了生日问题，但鉴于此，我不确定它在简单形式下的适用性。此外，它在很大程度上假定没有其他预防措施。
我更想知道你为什么要这样做。这是否涉及用户需要记忆和键入的URL？如果是这样，在URL末尾添加一堆随机的十六进制数字可能不是一个好主意。它是一个URL或URL参数，只是在编程中传递的？那么，我不太关心长度。无论哪种方式，你可能有更好的方法来完成你想要达成的目标。
- user
3
如果您使用二进制输出进行SHA1，并对结果进行Base64编码，每个字符的信息密度将大大提高。您可以拥有相同的8个字符名称，但不仅有
假设50％的碰撞概率与1.177*sqrt(N)成比例，使用类似Base64的编码将需要256倍的输入才能达到50％的碰撞概率。
16^8（2^32）种可能性，而是有64^8（2^48）种可能性。假设50％的碰撞概率与1.177*sqrt(N)成比例，使用类似Base64的编码将需要256倍的输入才能达到50％的碰撞概率。
- sarnold
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接