学好数学很重要-谈CRC32碰撞的概率和可能性

标签: 数学 crc32 碰撞 | 发表时间:2011-07-13 02:04 | 作者:白菜 三马
出处:http://aiyooyoo.com/
      前段时间跟某大牛叽歪的时候,才被提到我写的一篇文章里提到的CRC32算法有误。今天写代码,恰好需要用到这个函数,想起来了,就又回去看了下。确认了下,原先的文章并没有错误,但是有一处描述是很有问题的。
      原文是这样的,『综合以上的思路,决定采用CRC32来实现。CRC32也是一个哈希算法,和MD5类似,不过它是32位的,故更短一些,速度也更快。它所能表示的范围为40亿,也会产生冲突,但是对以一般应用足够了,这也是个成本很低廉的做法。
这只是我提到的一种简单做法而已。但是我确实是在这里可能误导数学不好的读者。我们知道,CRC32是32位的,MD5是128位(谁说16位、32位,我敲死他),也就是CRC128的演化版。通常我们习惯用MD5来做hash。但是我在此文为了简单和压缩长度,使用了CRC32。容易知道,CRC32发生冲突的概率是1//2^32,即大约40亿分之一。
     这是不是说在实际应用中,我们就可以大胆使用CRC32了呢?因为一般来说,我们所用的数据很少过亿,更别说40亿了。在原文,我是作为短网址算法的引子展开的。就算腾讯那样的规模,也没那么容易超过40亿(腾讯的短网址算法是用在微博里的)。如果你回答,应该是的。那么我断定,你一定没上过大学,要么就是你的高数是周公教的。在这里,我们说的40亿分之一的概率指的是40亿个对象CRC32后一定有一个会冲突。在概率论中,尤其要注意至少这样的字眼。CRC碰撞的概率是2^-32次方,这并不表明在40亿(2的32次方)的数据中就才可能产生一个碰撞,而是比这大得多。
  假设有1000万组数据,
则第一个数据不碰撞的概率为,1/4000000000
第二个数据不和第一个碰撞的概率是(4000000000-1)/4000000000
以此类推,1000万个数据完全不碰撞的概率是个小的不能再小的数字,反过来,就是有可能碰撞了,即“完全不碰撞”的逆事件。1减去一个小的不能再小的数据,那么就是一个大的不能再大的数据了(和小于1的数比较)。想到了什么?生日悖论!不是吗?
  任意两个数经过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 碰撞] 推荐:

学好数学很重要-谈CRC32碰撞的概率和可能性

- 三马 - 白菜的博客
      前段时间跟某大牛叽歪的时候,才被提到我写的一篇文章里提到的CRC32算法有误. 今天写代码,恰好需要用到这个函数,想起来了,就又回去看了下. 确认了下,原先的文章并没有错误,但是有一处描述是很有问题的.       原文是这样的,『综合以上的思路,决定采用CRC32来实现. CRC32也是一个哈希算法,和MD5类似,不过它是32位的,故更短一些,速度也更快.

在JVM中加入CRC32 Intrinsic加速CRC校验

- sggggy - 淘宝核心系统团队博客
在Java应用中例如在Hadoop中,经常用到CRC校验计算. 对于Java开发者来说,目前可用的实现是java.util.zip类,他通过JNI调用zlib中crc32函数. 其一,JNI的调用性能很低,如果每次计算的数据量很小,比如1、2个byte,那么JNI的调用开销远远高于计算开销. 其二,虽然zlib的crc32实现是查表实现,但是本身性能还有很大的提升空间.

方向的碰撞

- 小熊维尼 - 所有文章 - UCD大社区
以前做项目得到一个经验,就是在立项前,不需要拿个布好局的页面出来讨论,因为我们觉得,在方向还未清楚的时候,讨论页面细节可能是浪费时间. 这一回,战略部的新partner给了我一个不同的启示. 按说她的工作是在我上游,可是在最开始的实际操作中,她却把工作走到了我的下游,直接做了一个页面出来,把功能点、内容全都画好了…… 我一阵吃惊,对比着我自己的proposal,我跟她说,你这个东西,同事们能接受吗,因为他们都不知道方向在哪里,你却让他们看细节.

汽车最快速的碰撞测试

- 廖哥 - Poboo
这是有史以来 汽车最高速碰撞测试, 是Ford(福特)公司的一次测试,汽车时速120英里每小时(193公里/小时), 迎面撞上结实的混凝土墙,结果大家一目了然,汽车完全报废,想必如果里面有人的话,也都不可能生存下来,触目惊心的一个测试,大家也一定要把汽车慢慢开,不要拿自己的生命去赌博. 让人惊叹的汽车Illustrations设计.

绝对闪耀!伏特加碰撞光涂鸦

- scaoen - 设计|生活|发现新鲜
光涂鸦对大多数不懂得专业摄影的“门外汉”来说无疑是一种很玄幻的摄影技巧,今天我们可以看一个小短片,看看新茶锋潮的街头艺术家创作光涂鸦作品的花絮,了解一下看似神秘的“光涂鸦”到底是怎么创作的吧. 而且,这次活动的主角,可是绝对闪耀的大牌. 绝对伏特加最新限量版,绝对闪耀限量装ABSOLUT GLIMMER.

超唯美!慢镜头记录色彩液滴碰撞瞬间

- 李 - 河蟹娱乐
感谢火星网友囧、搞笑视频的分享. 我们用了1分钟看了仅仅0.6秒的“大世界”,但与之带来的享受不仅仅是1分钟. 生活中有太多不起眼的美好,放慢你的匆匆脚步,享受瞬间的魅力. 我国互联网各大公司现状精辟总结. 原文链接: http://hxyl.net/2011/09/10/wei-mei-jing/.

星系大碰撞——一组壮丽的太空照片

- 米 - 译言-每日精品译文推荐
碰撞星系形成的漩涡令人眼花缭乱. 图片提供:NASA, ESA, SAO, CXC, JPL-Caltech,及STScI. 这张合成的美丽照片是两个正在碰撞的星系,由NASA观测台发布. 两个触角星系发生的碰撞开始于一亿年前,目前碰撞还在继续. VV340号星系碰撞形成的感叹号. 图片来源:X-光NASA/CXC/IfA/ D.桑德斯等; 光学NASA/STScI/NRAO/A·埃文斯等.

世界车速最快的汽车碰撞试验

- David Chen - YesKafei Daily
欧洲汽车碰撞试验的测试车速是40MPH,即约64公里每小时. 这个时速发生事故,车辆的前脸已几乎报废,但我们的车速仍然在不断提升. 在高速公路上,尽管国内限速是120公里每小时,但经常会看到140公里每小时-160公里每小时飞奔的车辆,甚至我们也见过时速200公里的炫耀视频. 英国的Fifth Gear栏目,做了一个以120MPH(即193公里每小时)速度的汽车碰撞试验,看看那时车内的我们碰撞后会是什么样子:(碰撞试验中的汽车是福特的福克斯).

科学家称2012年地球不可能遭到死亡之星碰撞

- 消逝の航迹云 - cnBeta.COM
据国外媒体报道,多年前世界末日预言者曾预言称一颗未探测到的同伴恒星将周期性地向地球释放彗星,像宇宙时钟一样周期性地导致地球物种大灭绝. 目前,一位天文学家已掌握确凿证据,并声称彗星或者小行星周期性变迁并不存在. 在最新一项研究中,研究人员指出叫做“涅墨西斯”或者死亡之星的一颗黑暗同伴星体将于2012年碰撞地球,带来毁灭性灾难.

当VR遇上直播,两大“网红”会碰撞出什么火花?

- - 钛媒体:网罗天下创新事
日前,NextVR正式宣布完成8000万美元的B轮融资,网易、中信国安、华人文化等中国面孔的投资者赫然在列. 于是乎,这家成立于2009年的科技公司迅速登上国内各家媒体的版面,VR直播也再度成为关注的焦点. 一个是众星捧月般的VR,一个是不下200家平台角逐的直播,VR直播单从字面上来看就似乎是一个值得付出想象力的蓝海市场.