截断md5哈希，如何计算发生冲突的几率? [英] Truncating an md5 hash, How do I calculate the odds of a collision occurring?

问题描述

我想将md5哈希值截断到大约一半的大小.多少增加了碰撞的几率?如果我要处理大约50万个世代，我应该担心碰撞吗?一百万世代呢?

I want to truncate an md5 hash to about half size. How much does that increase the odds of collisions? if I'm dealing with around 500 000 generations, should I be worried about a collision? what about 1m generations.

推荐答案

您要查找的数学信息已在Wikipedia的

The math you're looking for is on Wikipedia's birthday attack page.

我们考虑以下实验.从一组 H 值中，我们随机均匀地选择 n 个值，从而允许重复.令 p(n; H)为在此实验中至少一个值被多次选择的概率.该概率可以近似为

We consider the following experiment. From a set of H values we choose n values uniformly at random thereby allowing repetitions. Let p(n; H) be the probability that during this experiment at least one value is chosen more than once. This probability can be approximated as

具有128位时，500,000个哈希值之间发生冲突的可能性约为

With 128 bits the chance of a collision among 500,000 hash values is around 10^-28. If you halve the size of the collision space then the chance of collision is around 10^-9. That is, even though the chance is vastly greater it's still very, very low. It depends on how critical it is that there be no collisions. 10^-9 is on the order of one in a billion, so while extremely unlikely it's within the realm of possibility.

供参考:

10 ²⁸ = 10八十亿= 100十亿亿
10 ⁹ = 10亿

10²⁸ = 10 octillion = 10 billion billion billion
10⁹ = 1 billion

这篇关于截断md5哈希，如何计算发生冲突的几率?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！