md5 - 截断 md5 哈希，如何计算发生冲突的几率？

Question

我想将 md5 散列截断到大约一半大小。这会增加多少碰撞几率？如果我正在处理大约 500 000 代，我应该担心碰撞吗？ 100万代呢？

Answer 1

你正在寻找的数学是在维基百科的birthday attack页。

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 个哈希值之间发生冲突的可能性约为 10^-28 .如果将碰撞空间的大小减半，那么发生碰撞的几率约为 10^-9 .也就是说，即使机会大得多，它仍然非常非常低。这取决于没有碰撞的重要性。 10-9 大约是十亿分之一，因此虽然极不可能，但它在可能性范围内。
以供引用:
1028 = 10 octillion = 100 亿亿
109 = 10 亿