V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
liqingcan
V2EX  ›  问与答

关于穷举一个字符串的 MD5 是他自己的想法

  •  
  •   liqingcan · 2016-10-04 20:59:24 +08:00 · 5112 次点击
    这是一个创建于 2954 天前的主题,其中的信息可能已经有所发展或是发生改变。

    前几天看了站中的一个帖子传送门 简单的说就是一个文本文件中的内容是这个文件的 md5 ,有没有可能找出这个 md5 值,然后我好奇心就起来了,于是我想动手验证一下。 我一开始的想法是,创建一个文本文件,然后计算他的 md5 ,但是感觉频繁的创建文件好像有点伤硬盘,于是我就试验了一下,直接计算一个字符串的 md5 和将这个字符串放在文本文件中在计算 md5 是不是一样。如果一样的话我就不用频繁创建文件了,经过试验这个是可行的。 然后我就写了一小段 python 的脚本来进行验证。 代码:

    import hashlib
    import time
    
    if __name__=="__main__":
        i=0
        md5 = format("%f"%time.time())
        while(True):
            i = i+1
            m=hashlib.md5()
            m.update(md5.encode("utf8"))
            temp = m.hexdigest()
            print("%d\t%s md5-> %s"%(i,md5,temp))
            if(temp==md5):
                print("找到一个相同的了,回车继续")
                print(md5)
                input()
                md5 = temp+format("%f"%time.time())
            else:
                md5 = temp
    

    简单的说,就是先取当前时间作为初始字符串,然后计算 md5 接着将计算出来的 md5 再计算,一直循环到找到一样的,然后我就放到了一台闲置的腾讯云的主机上跑了十几个小时

    跑了有快 4 千万条数据了。 然后我现在就在想,我这个方法有没有可能进入死循环啊?

    第 1 条附言  ·  2016-10-04 21:55:53 +08:00
    怎么改标题啊,发现打字打太快,标题都打错了。出现了一个是他自己的想法。。我想说的是,实验自己的想法
    50 条回复    2016-10-07 21:41:24 +08:00
    jasontse
        1
    jasontse  
       2016-10-04 21:10:30 +08:00 via iPad
    用十六进制数自增,补齐 32 位,跑一遍直到全 F ,这样就不会死循环了,不过还有大小写的可能性。😂
    skydiver
        2
    skydiver  
       2016-10-04 21:10:36 +08:00 via Android
    找到一个循环也很有价值啊
    bkmi
        3
    bkmi  
       2016-10-04 21:11:57 +08:00 via Android
    哥们,你好歹也多起几个线程啊
    bearqq
        4
    bearqq  
       2016-10-04 21:15:00 +08:00
    md5 多少位?每位哪些可能性?
    弄一堆 for
    就可以完成史诗级的巨慢解
    可保证唯一。

    不要拿 python 做这种蠢事,那才真是拍脑袋写个程序一秒钟,运行起来跑死个人
    yangff
        5
    yangff  
       2016-10-04 21:15:42 +08:00
    就算你这样跑出来了,得到的也是
    hex(x) == hex(md5(hex(x)))
    而不是
    x == md5(x)
    aploium
        6
    aploium  
       2016-10-04 21:33:51 +08:00
    用 py 做这种事......简直 gg

    歪楼的 ps: 不输出 stdout 能快很多
    popok
        7
    popok  
       2016-10-04 21:48:55 +08:00
    py 算这个效率太低了,再说你还要输出,那。。。。。
    liqingcan
        8
    liqingcan  
    OP
       2016-10-04 21:53:59 +08:00
    @jasontse 我本来是这样想的,不过想想,好像写起来比较麻烦
    @skydiver 重点是,找到死循环我也不知道是哪一个。。。
    @bkmi 我觉得同一个脚本直接多次执行不就行了,不过我一个就沾满了腾讯云主机 100%cpu 感觉没有多开的必要
    @bearqq
    @aploium
    @popok 用 python 主要是写起来快,哈哈
    @yangff 为啥?hex 是什么东西?
    metowolf
        9
    metowolf  
       2016-10-04 22:07:24 +08:00
    显然会有循环节的,只是不知道大还是小,如果找到 md5(x)==x 就比较有价值了
    binux
        10
    binux  
       2016-10-04 22:08:01 +08:00
    @yangff
    hex(x) == hex(md5(hex(x)))
    不就是
    x` == hex(md5(x`))

    而 md5 大多数时候就是 hex(md5(())
    zhujinliang
        11
    zhujinliang  
       2016-10-04 22:27:06 +08:00 via iPhone
    用 GPU 跑啊
    liqingcan
        12
    liqingcan  
    OP
       2016-10-04 22:32:54 +08:00
    @metowolf
    @binux 表示数学不好的看不懂你俩讲的是啥……
    @zhujinliang 不会搞。尴尬~
    sherlocktheplant
        13
    sherlocktheplant  
       2016-10-04 22:33:56 +08:00
    @liqingcan md5(string) != md5(hex(string))
    sneezry
        14
    sneezry  
       2016-10-04 23:28:00 +08:00 via Android
    要先证明函数收敛才能这么搞,楼主你其实在做牛顿迭代,这个有解是有前提条件的
    lance6816
        15
    lance6816  
       2016-10-04 23:36:00 +08:00
    可以的,很强势
    大概到太阳变成红巨星那天就能算出来了
    nfroot
        16
    nfroot  
       2016-10-04 23:51:43 +08:00 via Android
    先读源码吧 或许你就能猜到有木有这种可能存在
    liqingcan
        17
    liqingcan  
    OP
       2016-10-05 00:37:56 +08:00
    @sneezry
    @lance6816
    @nfroot 额,好吧,其实我就是心血来潮想试试。
    @sherlocktheplant 我比较想知道 hex ()这个是什么?
    Trim21
        18
    Trim21  
       2016-10-05 00:37:58 +08:00
    写了个穷举算法.........计算 1e6 个数字要 2s,穷举完要 6e36 年,多不多进程也没啥意义了...
    换了 pypy2 居然更慢了!变成了 5s
    liqingcan
        19
    liqingcan  
    OP
       2016-10-05 00:38:35 +08:00
    @sherlocktheplant 好吧,懂了, 16 进制
    GoForce5500
        20
    GoForce5500  
       2016-10-05 00:39:40 +08:00
    Java 不输出结果仅做 MD5 计算和计数的话,在 RMBP15 上开 8 核多线程跑满 CPU ,可以达到 1300 万次 MD5/秒。
    堆 GPU 的话还能快两个数量级。
    Trim21
        21
    Trim21  
       2016-10-05 00:46:36 +08:00
    @GoForce5500 减少到了 17 年...
    loveyu
        22
    loveyu  
       2016-10-05 00:48:29 +08:00
    来个全民计算的活动。先将要计算的字符串拆成一亿份,各种机器像挖矿一样计算就好了,说不定几天就有结果了
    dynos01
        23
    dynos01  
       2016-10-05 00:58:35 +08:00 via iPad
    搞一大堆超算,利用上大量的计算资源,也许很快出结果
    可惜这种项目没什么实际用处吧。。。
    abelyao
        24
    abelyao  
       2016-10-05 01:00:01 +08:00
    @loveyu 想起了 SETI@home 计划…… 我是不是暴露年龄了
    YvesX
        25
    YvesX  
       2016-10-05 01:10:29 +08:00 via iPhone
    你都定义为“穷举”了,为什么要用这种奇怪的算法,还是说其实是想顺便找个循环节出来?
    要是真的穷尽了,你就知道了所有 md5()与 md5(md5())的一一映射……
    脑洞有趣,但有点烧算力啊……
    liqingcan
        26
    liqingcan  
    OP
       2016-10-05 01:56:16 +08:00 via Android
    @YvesX 就是因为穷举数量太多了,所以用了这个,说不定踩到狗屎运就跳出来了………
    RqPS6rhmP3Nyn3Tm
        27
    RqPS6rhmP3Nyn3Tm  
       2016-10-05 01:58:34 +08:00 via iPhone
    不要那 python 做,性能太烂了
    关于你的问题,是的。
    StarBrilliant
        28
    StarBrilliant  
       2016-10-05 03:42:27 +08:00   ❤️ 3
    1 、存在 md5(x) == x 的概率是 63.21%,这是一个很大的概率
    2 、但是我们找不到这些 x ,因为对任意一个 x , md5(x) == x 的概率是 0.0000000000000000000000000000000000002939%
    3 、 MD5 的设计使你无法理论预测这样一个 x 值,所以你需要实际计算
    4 、如果计算一次 MD5 需要 1 ms 时间的话,你需要 10790283070806014188970529154.99 年才能算出来

    综上所述,研究这个问题没有意义。
    以及,搞计算机这一行,先学好数学,再买个游标卡尺来写 Python (误)。

    参考:
    http://crypto.stackexchange.com/a/19579
    http://stackoverflow.com/a/235788/2557927
    ryd994
        29
    ryd994  
       2016-10-05 08:11:41 +08:00 via Android
    @GoForce5500 远远不够啊
    md5 有 2^128 个
    13M≈2^24
    要 2^104 秒啊………
    t0byxdd
        30
    t0byxdd  
       2016-10-05 09:41:34 +08:00 via Android
    print 很慢的 不要这么频繁输出没意义的内容 最好别用 python 或者至少弄个多进程并行
    xuboying
        32
    xuboying  
       2016-10-05 10:38:10 +08:00 via iPhone
    import numba
    waruqi
        33
    waruqi  
       2016-10-05 11:01:05 +08:00 via iPhone
    拿 py 来跑也是醉了
    wy315700
        34
    wy315700  
       2016-10-05 13:54:13 +08:00
    至少也得拿个显卡来穷举
    SlipStupig
        35
    SlipStupig  
       2016-10-05 16:06:54 +08:00
    @t0byxdd 这种算数密集型好像多进程也没啥用,直接上 CUDA 或者 OpenGL ,速度不知道比 CPU 快多少
    ipwx
        36
    ipwx  
       2016-10-05 16:49:48 +08:00
    @sneezry 牛顿迭代?。。。数学不好就不要乱用术语。
    sneezry
        37
    sneezry  
       2016-10-05 18:07:13 +08:00
    @ipwx 那我虚心求教,这在数学上的专业术语应该叫什么呢
    ipwx
        38
    ipwx  
       2016-10-05 20:16:19 +08:00
    @sneezry 没什么术语,只是在寻找不动点而已。

    而且就算 MD5(x)=x 存在不动点,也不一定能通过楼主的方法找到,因为毕竟如果 MD5 的自变量空间里面存在某个不与不动点相通的环,而楼主恰巧从这个环的某个元素出发开始迭代,那么永远都只能在这个环里面走,到达不了不动点。
    sneezry
        39
    sneezry  
       2016-10-05 23:23:16 +08:00
    @ipwx 牛顿法是找 0 点的方法,同样用到了迭代,楼主的问题稍加变化就从 f(x)=x 转换为 F(x)=f(x)-x ,继而变成 0 点问题。牛顿法是用切线与 x 轴交点作为下次计算的输入值,楼主用的是函数值。那么我说这是一个特殊情况的牛顿逼近又有什么不妥呢?
    yangff
        40
    yangff  
       2016-10-05 23:33:54 +08:00
    @sneezry 来写一下 md5'(x)=?吧
    yangff
        41
    yangff  
       2016-10-05 23:42:10 +08:00
    @sneezry 另外,这玩意大概可以叫不动点迭代……
    当然你抠着脚趾头都知道这玩意不一定能收敛……
    sneezry
        42
    sneezry  
       2016-10-05 23:56:47 +08:00
    @yangff 哈哈,这个说到点上了, md5 是离散函数。算我偷换概念,离散函数就谈不上牛顿逼近。学艺不精,惭愧
    twl007
        43
    twl007  
       2016-10-06 04:14:37 +08:00
    我记得山大的王小云不就是做这个的么 = = 貌似叫 hash 碰撞?好像她的论文公开了吧?
    herozhang
        44
    herozhang  
       2016-10-06 08:59:15 +08:00
    prefix 12:
    54db1011d76dc70a0a9df3ff3e0b390f -> 54db1011d76d137956603122ad86d762

    suffix 12:
    df12c1434cec7850a7900ce027af4b78 -> b2f6053087022898fe920ce027af4b78

    ref:https://plus.google.com/+ThomasEgense/posts/SRxXrTMdrFN
    herozhang
        45
    herozhang  
       2016-10-06 09:03:56 +08:00
    可以先从 CRC 开始尝试,然后是 MD5 、 SHA 系列
    哈哈
    ipwx
        46
    ipwx  
       2016-10-06 09:33:27 +08:00
    @twl007 @herozhang 你们再仔细读一遍楼主的帖子再说。
    ryd994
        47
    ryd994  
       2016-10-06 11:02:52 +08:00 via Android
    @loveyu 不可能,看我 29 楼的
    大约是 10^23 年
    我今天用 C 和 OpenSSL 写了一下,单核大约 5-10M hash/s
    和上面的数据差不多
    也就是说,就算地球上人手一台电脑跑着,大概也可以考虑一下人类灭亡之类的事情了
    loveyu
        48
    loveyu  
       2016-10-06 15:16:23 +08:00
    @ryd994 现在的确不大可能,不过以后的计算速度上来了也许就有希望了!
    sutra
        49
    sutra  
       2016-10-06 17:47:44 +08:00
    直接查彩虹表吧。
    GoForce5500
        50
    GoForce5500  
       2016-10-07 21:41:24 +08:00
    @ryd994 经过将近八千亿次运算已弃坑……
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   976 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 21:28 · PVG 05:28 · LAX 13:28 · JFK 16:28
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.