注:这篇文章源自我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了呢?因为一般来说ÿ