前几天看了站中的一个帖子传送门 简单的说就是一个文本文件中的内容是这个文件的 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
jasontse 2016-10-04 21:10:30 +08:00 via iPad
用十六进制数自增,补齐 32 位,跑一遍直到全 F ,这样就不会死循环了,不过还有大小写的可能性。😂
|
2
skydiver 2016-10-04 21:10:36 +08:00 via Android
找到一个循环也很有价值啊
|
3
bkmi 2016-10-04 21:11:57 +08:00 via Android
哥们,你好歹也多起几个线程啊
|
4
bearqq 2016-10-04 21:15:00 +08:00
md5 多少位?每位哪些可能性?
弄一堆 for 就可以完成史诗级的巨慢解 可保证唯一。 不要拿 python 做这种蠢事,那才真是拍脑袋写个程序一秒钟,运行起来跑死个人 |
5
yangff 2016-10-04 21:15:42 +08:00
就算你这样跑出来了,得到的也是
hex(x) == hex(md5(hex(x))) 而不是 x == md5(x) |
6
aploium 2016-10-04 21:33:51 +08:00
用 py 做这种事......简直 gg
歪楼的 ps: 不输出 stdout 能快很多 |
7
popok 2016-10-04 21:48:55 +08:00
py 算这个效率太低了,再说你还要输出,那。。。。。
|
8
liqingcan OP |
9
metowolf 2016-10-04 22:07:24 +08:00
显然会有循环节的,只是不知道大还是小,如果找到 md5(x)==x 就比较有价值了
|
10
binux 2016-10-04 22:08:01 +08:00
|
11
zhujinliang 2016-10-04 22:27:06 +08:00 via iPhone
用 GPU 跑啊
|
12
liqingcan OP |
13
sherlocktheplant 2016-10-04 22:33:56 +08:00
@liqingcan md5(string) != md5(hex(string))
|
14
sneezry 2016-10-04 23:28:00 +08:00 via Android
要先证明函数收敛才能这么搞,楼主你其实在做牛顿迭代,这个有解是有前提条件的
|
15
lance6816 2016-10-04 23:36:00 +08:00
可以的,很强势
大概到太阳变成红巨星那天就能算出来了 |
16
nfroot 2016-10-04 23:51:43 +08:00 via Android
先读源码吧 或许你就能猜到有木有这种可能存在
|
17
liqingcan OP |
18
Trim21 2016-10-05 00:37:58 +08:00
写了个穷举算法.........计算 1e6 个数字要 2s,穷举完要 6e36 年,多不多进程也没啥意义了...
换了 pypy2 居然更慢了!变成了 5s |
19
liqingcan OP @sherlocktheplant 好吧,懂了, 16 进制
|
20
GoForce5500 2016-10-05 00:39:40 +08:00
Java 不输出结果仅做 MD5 计算和计数的话,在 RMBP15 上开 8 核多线程跑满 CPU ,可以达到 1300 万次 MD5/秒。
堆 GPU 的话还能快两个数量级。 |
21
Trim21 2016-10-05 00:46:36 +08:00
@GoForce5500 减少到了 17 年...
|
22
loveyu 2016-10-05 00:48:29 +08:00
来个全民计算的活动。先将要计算的字符串拆成一亿份,各种机器像挖矿一样计算就好了,说不定几天就有结果了
|
23
dynos01 2016-10-05 00:58:35 +08:00 via iPad
搞一大堆超算,利用上大量的计算资源,也许很快出结果
可惜这种项目没什么实际用处吧。。。 |
25
YvesX 2016-10-05 01:10:29 +08:00 via iPhone
你都定义为“穷举”了,为什么要用这种奇怪的算法,还是说其实是想顺便找个循环节出来?
要是真的穷尽了,你就知道了所有 md5()与 md5(md5())的一一映射…… 脑洞有趣,但有点烧算力啊…… |
27
RqPS6rhmP3Nyn3Tm 2016-10-05 01:58:34 +08:00 via iPhone
不要那 python 做,性能太烂了
关于你的问题,是的。 |
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 |
29
ryd994 2016-10-05 08:11:41 +08:00 via Android
|
30
t0byxdd 2016-10-05 09:41:34 +08:00 via Android
print 很慢的 不要这么频繁输出没意义的内容 最好别用 python 或者至少弄个多进程并行
|
31
lain0 2016-10-05 10:19:05 +08:00
|
32
xuboying 2016-10-05 10:38:10 +08:00 via iPhone
import numba
|
33
waruqi 2016-10-05 11:01:05 +08:00 via iPhone
拿 py 来跑也是醉了
|
34
wy315700 2016-10-05 13:54:13 +08:00
至少也得拿个显卡来穷举
|
35
SlipStupig 2016-10-05 16:06:54 +08:00
@t0byxdd 这种算数密集型好像多进程也没啥用,直接上 CUDA 或者 OpenGL ,速度不知道比 CPU 快多少
|
38
ipwx 2016-10-05 20:16:19 +08:00
@sneezry 没什么术语,只是在寻找不动点而已。
而且就算 MD5(x)=x 存在不动点,也不一定能通过楼主的方法找到,因为毕竟如果 MD5 的自变量空间里面存在某个不与不动点相通的环,而楼主恰巧从这个环的某个元素出发开始迭代,那么永远都只能在这个环里面走,到达不了不动点。 |
39
sneezry 2016-10-05 23:23:16 +08:00
@ipwx 牛顿法是找 0 点的方法,同样用到了迭代,楼主的问题稍加变化就从 f(x)=x 转换为 F(x)=f(x)-x ,继而变成 0 点问题。牛顿法是用切线与 x 轴交点作为下次计算的输入值,楼主用的是函数值。那么我说这是一个特殊情况的牛顿逼近又有什么不妥呢?
|
43
twl007 2016-10-06 04:14:37 +08:00
我记得山大的王小云不就是做这个的么 = = 貌似叫 hash 碰撞?好像她的论文公开了吧?
|
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 |
45
herozhang 2016-10-06 09:03:56 +08:00
可以先从 CRC 开始尝试,然后是 MD5 、 SHA 系列
哈哈 |
47
ryd994 2016-10-06 11:02:52 +08:00 via Android
@loveyu 不可能,看我 29 楼的
大约是 10^23 年 我今天用 C 和 OpenSSL 写了一下,单核大约 5-10M hash/s 和上面的数据差不多 也就是说,就算地球上人手一台电脑跑着,大概也可以考虑一下人类灭亡之类的事情了 |
49
sutra 2016-10-06 17:47:44 +08:00
直接查彩虹表吧。
|
50
GoForce5500 2016-10-07 21:41:24 +08:00
@ryd994 经过将近八千亿次运算已弃坑……
|