注：这篇文章源自我10年前写的博客，今天看到有人谈密码安全的，再发一遍和大家讨论下。我发现哪怕10年后，这文章也没过时，很多人还是没拎清 冲突概率和样本空间的关系。

前段时间跟某大牛叽歪的时候，被提到我写的一篇文章（用CRC32实现短网址的一篇）里提到的CRC32算法有误。今天写代码，恰好需要用到这个函数，想起来了，就又回去看了下。确认了下，原先的文章并没有错误，但是有一处描述是很有问题的。

原文是这样的，『综合以上的思路，决定采用CRC32来实现。CRC32也是一个哈希算法，和MD5类似，不过它是32位的，故更短一些,速度也更快。它所能表示的范围为40亿，也会产生冲突，但是对于一般应用足够了，这也是个成本很低廉的做法。』

这只是提到的一种简单做法而已。但是确实是在这里可能误导数学不好的读者。我们知道，CRC32是32位的，MD5是128位（谁说16位、32位， 我敲死他。这里的位是bit，不是字符长度），也可以说是CRC128的演化版。通常我们习惯用MD5来做hash。但是我在之前文章为了简单和压缩长度，使用了CRC32。容易知道，CRC32的值域是2^32，即大约40亿。

很多人想当然地理解为，CRC32的冲突概率是1/2^32，这是错的。

对样本空间的误解

这是不是说在实际应用中，我们就可以大胆使用CRC32了呢？因为一般来说，我们所用的数据很少过亿，更别说40亿了。在原文，我是作为短网址算法的引子展开的。就算腾讯那样的规模，也没那么容易超过40亿（腾讯的短网址算法是用在微博里的）。

如果你回答，应该是的，那你的高数是周公教的。在这里，我们说的40亿分之一的指的是CRC32所拥有的样本空间。在概率论中，尤其要注意至少这样的字眼。CRC32的样本空间是2^32次方，这并不表 明在40亿（2的32次方）的数据中就才可能产生一对碰撞，而是比这大得多。

假设有1000万组数据，

则第一个数据不碰撞的概率为,1/4000000000

第二个数据不和第一个碰撞的概率是(4000000000-1)/4000000000

以此类推，1000万个数据完全不碰撞的概率是个小的不能再小的数字，反过来，就是有可能碰撞了，即“完全不碰撞”的逆事件。1减去一个小的不能再小的数据，那么就是一个大的不能再大的数据了（和小于1的数比较）。想到了什么？生日悖论！不是吗？

生日悖论

也叫做"生日问题"（birthday problem）：一个班级需要有多少人，才能保证每个同学的生日都不一样？

答案很出人意料。如果至少两个同学生日相同的概率不超过5%，那么这个班只能有7个人。事实上，一个23人的班级有50%的概率，至少两个同学生日相同；50人班级有97%的概率，70人的班级则是99.9%的概率。

这意味着，如果哈希值的取值空间是365，只要计算23个哈希值，就有50%的可能产生碰撞。也就是说，哈希碰撞的可能性，远比想象的高。

来推算一下：

至少两个人生日相同的概率，可以先算出所有人生日互不相同的概率，再用 1 减去这个概率。

我们把这个问题设想成，每个人排队依次进入一个房间。第一个进入房间的人，与房间里已有的人（0人），生日都不相同的概率是365/365；第二个进入房间的人，生日独一无二的概率是364/365；第三个人是363/365，以此类推。

因此，所有人的生日都不相同的概率，就是下面的公式。

上面公式的 n 表示进入房间的人数。可以看出，进入房间的人越多，生日互不相同的概率就越小。

这个公式可以推导成下面的形式。

那么，至少有两个人生日相同的概率，就是 1 减去上面的公式。

Hash冲突的概率

同理。

任意两个数经过CRC32后不碰撞，是一个随机事件。根据期望的线性限制，对模型简化，可以得到，碰撞对的数目，即E(X)=k(k-1)/2n，代入1000万，结果可知。实际上，只需要92682组数据，CRC32就已经有碰撞的可能性了。

那么为了让1000万组数据碰撞的可能性不大于1/2，也该有多少位呢？如果利用从一个全散列中随机选出的散列函数h,将n个关键字存储到一个大小为 m=n^2的那么出现碰撞的概率小于1/2.E(X)=(n,2)*1/n^2<1/2。即N的桶最好承载square(N)的数据，这样保证冲突概率小于50%。

到这里已经很清楚了，CRC32不是足够用，而是用不成的。

很轻松就能举出CRC32碰撞的例子，因为它的碰撞概率不到10W分之一，随便写个循环就可以跑出来。

我举个例子

package baicai.other;

import java.util.zip.CRC32;
public class Crc32 {

    public static void main(String[] args) {
        CRC32 crc32 = new CRC32();
        crc32.update("86821".getBytes());
        System.out.println(crc32.getValue());
        CRC32 crcTwo = new CRC32();
        crcTwo.update("14740600".getBytes());
        System.out.println(crcTwo.getValue());
    }
}

这个例子，两个数字就冲突了，它们的CRC32结果都是 350569284

那MD5呢，MD5冲突概率虽然小得多，但也是很容易发生的，也很容易构造。这里也给个例子

下面这张图片，它显示的内容也是它本身的MD5值，这明显是精心构造的碰撞

[ren@ren-pc 下载]$ md5sum md5.gif 
f5ca4f935d44b85c431a8bf788c0eaca  md5.gif

注：由于上传的关系，这种图片可能被压缩，会导致你验证失败。各位读者可以自行下载验证下。