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

[liqingcan]

前几天看了站中的一个帖子传送门 简单的说就是一个文本文件中的内容是这个文件的 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 千万条数据了。 然后我现在就在想，我这个方法有没有可能进入死循环啊?

怎么改标题啊，发现打字打太快，标题都打错了。出现了一个是他自己的想法。。我想说的是，实验自己的想法

[jasontse]

用十六进制数自增，补齐 32 位，跑一遍直到全 F ，这样就不会死循环了，不过还有大小写的可能性。😂

[skydiver]

找到一个循环也很有价值啊

[bkmi]

哥们，你好歹也多起几个线程啊

[bearqq]

md5 多少位？每位哪些可能性？
弄一堆 for
就可以完成史诗级的巨慢解
可保证唯一。

不要拿 python 做这种蠢事，那才真是拍脑袋写个程序一秒钟，运行起来跑死个人

[yangff]

就算你这样跑出来了，得到的也是
hex(x) == hex(md5(hex(x)))
而不是
x == md5(x)

[aploium]

用 py 做这种事......简直 gg

歪楼的 ps: 不输出 stdout 能快很多

[popok]

py 算这个效率太低了，再说你还要输出，那。。。。。

[liqingcan]

@jasontse 我本来是这样想的，不过想想，好像写起来比较麻烦
@skydiver 重点是，找到死循环我也不知道是哪一个。。。
@bkmi 我觉得同一个脚本直接多次执行不就行了，不过我一个就沾满了腾讯云主机 100%cpu 感觉没有多开的必要
@bearqq
@aploium
@popok 用 python 主要是写起来快，哈哈
@yangff 为啥?hex 是什么东西？

[metowolf]

显然会有循环节的，只是不知道大还是小，如果找到 md5(x)==x 就比较有价值了

[binux]

@yangff
hex(x) == hex(md5(hex(x)))
不就是
x` == hex(md5(x`))

而 md5 大多数时候就是 hex(md5(())

[zhujinliang]

用 GPU 跑啊

[liqingcan]

@metowolf 恩
@binux 表示数学不好的看不懂你俩讲的是啥……
@zhujinliang 不会搞。尴尬~

[sherlocktheplant]

@liqingcan md5(string) != md5(hex(string))

[sneezry]

要先证明函数收敛才能这么搞，楼主你其实在做牛顿迭代，这个有解是有前提条件的

[lance6816]

可以的，很强势
大概到太阳变成红巨星那天就能算出来了

[nfroot]

先读源码吧 或许你就能猜到有木有这种可能存在

[liqingcan]

@sneezry
@lance6816
@nfroot 额，好吧，其实我就是心血来潮想试试。
@sherlocktheplant 我比较想知道 hex （）这个是什么？

[Trim21]

写了个穷举算法.........计算 1e6 个数字要 2s,穷举完要 6e36 年,多不多进程也没啥意义了...
换了 pypy2 居然更慢了!变成了 5s

[liqingcan]

@sherlocktheplant 好吧，懂了， 16 进制

[GoForce5500]

Java 不输出结果仅做 MD5 计算和计数的话，在 RMBP15 上开 8 核多线程跑满 CPU ，可以达到 1300 万次 MD5/秒。
堆 GPU 的话还能快两个数量级。

[Trim21]

@GoForce5500 减少到了 17 年...

[loveyu]

来个全民计算的活动。先将要计算的字符串拆成一亿份，各种机器像挖矿一样计算就好了，说不定几天就有结果了

[dynos01]

搞一大堆超算，利用上大量的计算资源，也许很快出结果
可惜这种项目没什么实际用处吧。。。

[abelyao]

@loveyu 想起了 SETI@home 计划…… 我是不是暴露年龄了

[YvesX]

你都定义为“穷举”了，为什么要用这种奇怪的算法，还是说其实是想顺便找个循环节出来？
要是真的穷尽了，你就知道了所有 md5()与 md5(md5())的一一映射……
脑洞有趣，但有点烧算力啊……

[liqingcan]

@YvesX 就是因为穷举数量太多了，所以用了这个，说不定踩到狗屎运就跳出来了………

[RqPS6rhmP3Nyn3Tm]

不要那 python 做，性能太烂了
关于你的问题，是的。

[StarBrilliant]

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]

@GoForce5500 远远不够啊
md5 有 2^128 个
13M≈2^24
要 2^104 秒啊………

[t0byxdd]

print 很慢的 不要这么频繁输出没意义的内容 最好别用 python 或者至少弄个多进程并行

[lain0]

https://stackoverflow.com/questions/235785/is-there-an-md5-fixed-point-where-md5x-x

[xuboying]

import numba

[waruqi]

拿 py 来跑也是醉了

[wy315700]

至少也得拿个显卡来穷举

[SlipStupig]

@t0byxdd 这种算数密集型好像多进程也没啥用，直接上 CUDA 或者 OpenGL ，速度不知道比 CPU 快多少

[ipwx]

@sneezry 牛顿迭代？。。。数学不好就不要乱用术语。

[sneezry]

@ipwx 那我虚心求教，这在数学上的专业术语应该叫什么呢

[ipwx]

@sneezry 没什么术语，只是在寻找不动点而已。

而且就算 MD5(x)=x 存在不动点，也不一定能通过楼主的方法找到，因为毕竟如果 MD5 的自变量空间里面存在某个不与不动点相通的环，而楼主恰巧从这个环的某个元素出发开始迭代，那么永远都只能在这个环里面走，到达不了不动点。

[sneezry]

@ipwx 牛顿法是找 0 点的方法，同样用到了迭代，楼主的问题稍加变化就从 f(x)=x 转换为 F(x)=f(x)-x ，继而变成 0 点问题。牛顿法是用切线与 x 轴交点作为下次计算的输入值，楼主用的是函数值。那么我说这是一个特殊情况的牛顿逼近又有什么不妥呢？

[yangff]

@sneezry 来写一下 md5'(x)=?吧

[yangff]

@sneezry 另外，这玩意大概可以叫不动点迭代……
当然你抠着脚趾头都知道这玩意不一定能收敛……

[sneezry]

@yangff 哈哈，这个说到点上了， md5 是离散函数。算我偷换概念，离散函数就谈不上牛顿逼近。学艺不精，惭愧

[twl007]

我记得山大的王小云不就是做这个的么 = = 貌似叫 hash 碰撞？好像她的论文公开了吧？

[herozhang]

prefix 12:
54db1011d76dc70a0a9df3ff3e0b390f -> 54db1011d76d137956603122ad86d762

suffix 12:
df12c1434cec7850a7900ce027af4b78 -> b2f6053087022898fe920ce027af4b78

ref:https://plus.google.com/+ThomasEgense/posts/SRxXrTMdrFN

[herozhang]

可以先从 CRC 开始尝试，然后是 MD5 、 SHA 系列
哈哈

[ipwx]

@twl007 @herozhang 你们再仔细读一遍楼主的帖子再说。

[ryd994]

@loveyu 不可能，看我 29 楼的
大约是 10^23 年
我今天用 C 和 OpenSSL 写了一下，单核大约 5-10M hash/s
和上面的数据差不多
也就是说，就算地球上人手一台电脑跑着，大概也可以考虑一下人类灭亡之类的事情了

[loveyu]

@ryd994 现在的确不大可能，不过以后的计算速度上来了也许就有希望了！

[sutra]

直接查彩虹表吧。

[GoForce5500]

@ryd994 经过将近八千亿次运算已弃坑……