MD5最长32位,会重复啊!这个问题昆扰我很久了,现在终于明白了。
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1252784
[收藏到我的网摘] [发送Trackback] lee3f发表于 2006年09月20日 10:45:00
走近消息摘要--Md5产生重复的概率
问题:假设有十万个不同的文件,每个文件对应于一个MD5。这十万个MD5中,存在两个相同的MD5的概率是多大?
答:MD5是128位hash码(4个整数,每个整数4个字节)。我们假设它的计算结果是足够随机和足够分散的。因此,一个文件的MD5码,有2的128次方(用2e128表示,下面都用这种方式表示)个可能。进而我们知道,随意找出来的两个文件的MD5码相等的可能性,是2e128分之一。下面讨论中,我们用r来表示这个概率(即r=2e-128)。
假设这十万个MD5是一条条插入到数据库中的。第二个MD5插入时,它跟第一条重复的概率是r。第三条url插入时,它有可能跟第一条重复,也有可能跟第二条重复,因此总发生重复的概率是2×r。同理,第四条插入时发生重复的概率是3×r...第n条插入时发生重复的概率是(n-1)×r。n个MD5码,其中有两个重复的概率是上面那么多个可能的加和。
因此,n个md5码,自然产生重复的概率是:
(1+2+3+...+(n-1))×r = (1/2)×n×(n-1)×r
以n=10e4,r=1/2e128 代入,得到重复的概率为:
(1/2)×10e4×(10e4-1)×(1/2e128)
10e4-1约等于10e4,上式可以简化:
(1/2)×10e8×(1/2e128)
=10e8/(2×2e128)
我们使用近似2e10 = 1024 = 10e3,那么
=10e8/(10e9*2e89)
=1/(10*2e89)
=1/(10*10e27)
=1/(10e28)
这个数字小得可怜,到底有多小,我们来算一下:一般福利彩票的中头奖的机会,约一百万份之一,即1/10e6。而上面的数字,相当1/10e22个一百万份之一。也就是说:相当于某人买了一亿亿亿次福彩,每次都中头奖的概率。
结论:对于十万条数据,发生MD5冲突的概率非常小,可以忽略不计。
那么,大约要多少个文件才能产生自然重复呢?根据上面的计算,对于N个MD5码的集合,存在重复的概率是:
(1/2)*(N/2e64)e2
因此,只有N大到可以与2e64比拟,才需要考虑它的冲突问题。
2e64是怎样的一个数字?
2e64是4G个4G。目前32位系统的内存寻址范围才是区区4G。
形象地说就是:如果一台电脑上可以存放四十亿(4G)个文件,而系统中有四十亿台这样的电脑。那么,这么多的文件数才会令到系统自然产生重复。
所以MD5码作为系统的索引是非常可靠的。
补充:
上面对于MD5的计算,并未考虑到人为制造的MD5冲突(现在已经有方法可以制造有冲突的MD5码了),也未考虑到计算MD5码时,因数据补零而造成的MD5冲突。事实上,在一般的系统中,并没有必要考虑这两种情况。
分享到:
相关推荐
Digest-Perl-MD5
前端开源库-js-md5JS-MD5是一个简单的用于JavaScript的MD5哈希函数,支持UTF-8编码。
搞小程序开发,请求接口的加密部分用到md5,百度一大堆垃圾的js md5加密,每一个都正确,都是不支持中文的,爬墙才找到这个,希望大家别入坑了。js md5加密,md5支持utf-8加密,javascript md5加密,最好用js md5...
cyrus-sasl-md5-2.1.23-15.el6_6.2.x86_64.rpm cyrus-sasl-md5-2.1.23-15.el6_6.2.x86_64.rpm
Laravel开发-laravel-hashing-md5 暂无描述
官方离线安装包,亲测可用。使用rpm -ivh [rpm完整包名] 进行安装
Android-NDK-MD5-安卓jni 进行md5加密; Android-NDK-MD5-安卓jni 进行md5加密
asp-hmac-md5加密方法-md5函数文件-支持中文
cyrus-sasl-md5-2.1.23-13.el6.i686.rpm
离线安装包,亲测可用
前端项目-blueimp-md5,javascript MD5实现。
Laravel开发-laravel-md5-hashing Laravel MD5哈希支持
MD5信息摘要算法(英语:MD5 Message-Digest Algorithm),一种被广泛使用的密码散列函数,可以产生出一个128位(16字节)的散列值(hash value),用于确保信息传输完整一致。MD5由美国密码学家罗纳德·李维斯特...
离线安装包,亲测可用
MD5的全称是Message-Digest Algorithm 5,简单的讲,MD5值就相当于一个文件的ID,具有唯一性,如果这个文件被修改过(如被嵌入病毒,木马等),其MD5值就会变化。因此,一些正规的下载网址提供文件下载的同时一般...
包括了browser-md5-file.min.js 和browser-md5-file.js,可以在客户端查看文件的md5值
前端项目-spark-md5,Lightning fast normal and incremental md5 for javascript
windows64位,visual2017,配合Cmake使用,需要的可以下载使用。dcmtk有多种工具集合,包括实现jpeg2000压缩dcm文件。windows的支持库
输入需要加密的字符串,有两种加密方式,普通md5加密和加盐MD5加密。根据需要生成。
这个进行字符串加密 和解密 , 编码和 解码 包括(base64、DES、AES、SHA-1、MD5 ) ,都是亲测的,保证可用 这个进行字符串加密 和解密 , 编码和 解码 包括(base64、DES、AES、SHA-1、MD5 ) ,都是亲测的,保证...