如何计算截断哈希时对冲突概率的影响？
How can I calculate the impact on collision probability when truncating a hash?
我想将 MD5 摘要从 32 个字符减少到理想情况下接近 16 个字符。我将使用它作为数据库键来检索一组 (public) 用户定义的参数。我预计唯一 "IDs" 的数量最终会超过 10,000。碰撞是不可取的，但不是世界末日。
我想了解直接截断 MD5 摘要以获得更短密钥的可行性。但是我在挖掘一个我能理解的公式时遇到了麻烦（假设我的数学背景有限），更不用说用来确定截断哈希对碰撞概率的影响了。
越短越好，在情理之中。我觉得必须有一个简单的公式，但我宁愿有一个明确的答案，也不愿根据我在网上阅读的零碎内容拼凑自己的猜测。
你可以用这个公式计算碰撞的几率：
chance of collision = 1 - e^(-n^2 / (2 * d))
其中n是消息数，d是可能性数，e是常量e（2.718281828...）。
太棒了。
我发现了其他一些或多或少准确的方程式 and/or 简化的 here，以及一个很好的解释和对现实世界概率的方便比较：
- 1−e^((−k(k−1))/2N) - sample plot here
- (k(k-1))/2N - sample plot here
- k^2/2N - sample plot here
...其中 k 是您将生成的 ID 的数量（"messages"），N 是哈希摘要可以生成的最大数字或您截断的十六进制数可以表示的最大数字（技术上 + 1，占 0）。
更多关于 "N"
例如，如果您的原始哈希是“38BF05A71DDFB28A504AFB083C29D037”（32 个十六进制字符），并且您将其截断为 12 个十六进制字符（例如：“38BF05A71DDF”），那么您可以在十六进制是“0xFFFFFFFFFFFF”（281474976710655 - 即 16^12-1（或者 256^6，如果你喜欢用字节来思考的话）。但是因为“0”本身算作你理论上可以产生的数字之一，你添加回到那个 1，这只剩下 16^12.
因此您可以将 N 视为 16 ^ (numberOfHexDigits)。
我想将 MD5 摘要从 32 个字符减少到理想情况下接近 16 个字符。我将使用它作为数据库键来检索一组 (public) 用户定义的参数。我预计唯一 "IDs" 的数量最终会超过 10,000。碰撞是不可取的，但不是世界末日。
我想了解直接截断 MD5 摘要以获得更短密钥的可行性。但是我在挖掘一个我能理解的公式时遇到了麻烦（假设我的数学背景有限），更不用说用来确定截断哈希对碰撞概率的影响了。
越短越好，在情理之中。我觉得必须有一个简单的公式，但我宁愿有一个明确的答案，也不愿根据我在网上阅读的零碎内容拼凑自己的猜测。
你可以用这个公式计算碰撞的几率：
chance of collision = 1 - e^(-n^2 / (2 * d))
其中n是消息数，d是可能性数，e是常量e（2.718281828...）。
我发现了其他一些或多或少准确的方程式 and/or 简化的 here，以及一个很好的解释和对现实世界概率的方便比较：
- 1−e^((−k(k−1))/2N) - sample plot here
- (k(k-1))/2N - sample plot here
- k^2/2N - sample plot here
...其中 k 是您将生成的 ID 的数量（"messages"），N 是哈希摘要可以生成的最大数字或您截断的十六进制数可以表示的最大数字（技术上 + 1，占 0）。
更多关于 "N"
例如，如果您的原始哈希是“38BF05A71DDFB28A504AFB083C29D037”（32 个十六进制字符），并且您将其截断为 12 个十六进制字符（例如：“38BF05A71DDF”），那么您可以在十六进制是“0xFFFFFFFFFFFF”（281474976710655 - 即 16^12-1（或者 256^6，如果你喜欢用字节来思考的话）。但是因为“0”本身算作你理论上可以产生的数字之一，你添加回到那个 1，这只剩下 16^12.
因此您可以将 N 视为 16 ^ (numberOfHexDigits)。