V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
jaylong
V2EX  ›  程序员

一直困惑我很久了的关于MD5算法的原理,求各位大神指点

  •  
  •   jaylong · 2012-01-17 11:01:45 +08:00 · 5194 次点击
    这是一个创建于 4679 天前的主题,其中的信息可能已经有所发展或是发生改变。
    一直不太明白为什么每个文件经过算法都能生成唯一的一个16位(或32位)hash代码,如果说一串密码经过md5加密之后得到唯一的16位代码还可以理解,可是不同的文件之间哪怕只有1个0和1的差别都会导致截然不同的16位代码,虽然是16位的字母数字组合,毕竟还是一个有限的集合吧 (应该是每一位总字符数的16次方个吧)而不同的文件应该说是个无限集合,远远大于前者,请问它们怎么能够做到一一对应?
    12 条回复    1970-01-01 08:00:00 +08:00
    reus
        1
    reus  
       2012-01-17 11:23:08 +08:00 via Android
    做不到一一对应的,会出现碰撞,也就是不同的输入得到相同的输出。不同的算法碰撞率不同,所以安全性也有强弱差异
    ch_linghu
        2
    ch_linghu  
       2012-01-17 11:30:26 +08:00
    hash算法本来就做不到一一对应。hash算法的安全性在于:1. 对原文的微弱改动会引起hash值的巨大变化。2. 难以找到与指定原文对应的另一份原文,他们的hash值相同。 3. 难以找到两份不同的原文,他们的hash值相同。

    不过 陈小云 证明了对于MD5算法来说,第三点可以在有限时间内做到。所以MD5的安全性已经大大削弱了。
    zhatrix
        3
    zhatrix  
       2012-01-17 11:36:30 +08:00
    @ch_linghu 是 山东大学的 王小云吧
    surf
        4
    surf  
       2012-01-17 11:49:10 +08:00
    做不到一对一对应 MD5是有冲突的
    但是可以表示的范围已经很大了 2^128次 足够大
    clino
        5
    clino  
       2012-01-17 11:53:53 +08:00
    没办法一一对应,但是越好的算法越难构造碰撞的情况吧
    likuku
        6
    likuku  
       2012-01-17 12:01:34 +08:00
    王小云那个,据说适用范围其实很窄,实用价值不大。
    loading
        7
    loading  
       2012-01-17 12:09:36 +08:00 via Android
    如果是一一对应,数据压缩算法都靠边了。
    virushuo
        8
    virushuo  
       2012-01-17 12:17:56 +08:00
    要弄明白这个得看看数论。
    jaylong
        9
    jaylong  
    OP
       2012-01-18 15:33:25 +08:00
    感谢楼上各位的讲解 原来不是一一对应的啊,这就可以理解了 不过据我使用各大md5破解查询网站反查Md5加密前原始数值时基本没遇到过多于一个的结果
    CoX
        10
    CoX  
       2012-01-18 15:52:55 +08:00
    @jaylong 以前记得有个文章提起过,中文md5的结果很容易出现多对一
    Platinum
        11
    Platinum  
       2012-01-18 17:34:53 +08:00
    @CoX 不太可能,首先你得明白 md5 的 16^32 是多大的范围

    我倒一直很想知道有哪两串有意义的字符串能有相同的 md5(比如两张图片或者两句话的 md5 一样)

    王小云的那个,理论上可以做到,在可承受的时间内、通过给一个图片的 exif 里填充大量特殊字符串的方式,让这图片跟另外一张图片的 md5 相同
    CoX
        12
    CoX  
       2012-01-18 18:32:56 +08:00
    @Platinum 额,是我记错了,应该是脚本语言算法有问题,搜到51js上一个类似的情况:
    http://bbs.51js.com/thread-5538-1-1.html

    不过想让两张图片md5一样,目前貌似容易做到,搜索一下 fastcoll 这个工具
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5487 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 06:45 · PVG 14:45 · LAX 22:45 · JFK 01:45
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.