MD5 碰撞的新玩意儿

作者: , 共 493 字

从 hash 函数到王小云的 MD5 破解 我们介绍了 hash 函数的一些基本概念和 MD5 碰撞的一个「应用」,最近在这个问题上又有了新的进展。

Marc Stevens, Arjen Lenstra 和 Benne de Weger 在 这篇论文 里给出了寻找 Chosen-prefix 碰撞的有效方法,这种碰撞指对任意给定的 A, B ,找到 x, y ,使得 MD5(Ax) = MD5(By),即可以找到碰撞,使得以任意两个字符串开头。

作者给出了两个非常有意思的应用,一个是 预测 2008 年美国大选结果 。其实是建立了 12 个 PDF 文档,它们的 MD5 完全相同,但显示内容却互不相同。这种效果在 从 hash 函数到王小云的 MD5 破解 已经讨论并实现了。

另一个就是 给出了两个具有同样 MD5 的可执行文件 。以后下载文件的时候即使有 MD5 验证也不一定是安全的了。

在这个结果之前,还有一个有意思的应用, [1][2] 这两个网页具有相同的 MD5 值,但显示内容截然不同。想知道怎么实现的看看它们的源代码即可。

Q. E. D.

类似文章:
密码学是理论计算机的一个很大的方向。之前准备先写密码学概论再提在 hash 函数破解上做出重大贡献的王小云教授的工作,不过前两天新闻报道《王小云获得求是杰出科学家奖以及 100 万奖金》,在媒体上又掀起了一轮宣传狂潮,但是有些报道极端弱智,错误百出,所以我趁机纠正一下,并介绍密码学的一个组成部分 ——hash 函数,以及王小云老师在这上面的工作。
比特币协议里使用了 ECDSA (椭圆曲线签名算法),我之前以为它和基于大数分解的 RSA 公钥密码体系差不多。这两天看了下维基百科,才发现它们之间的差异挺大。
IT » 比特币
上篇大致描述了 bitcoin 的技术原理 ,只想说明一件事情: bitcoin 的协议是可靠的,它保证了 bitcoin 虚拟货币的信用问题,别人不会偷走我的 bitcoin ,我拿到的 bitcoin 也是真实可靠的。使用 bitcoin 交易有很多好处,可以轻易列出一大堆:
英文是 communication complexity ,不知道该翻译成通信复杂性,还是通讯复杂性呢。这里先用通讯复杂性吧。这是一个理论计算机的子领域,在过去 30 年衍生了很多东西。它是我的研究的主要内容,这里简略介绍一下。
前一篇:
很多人一看到 NP-hard ,就从字面上理解成为比 NP 还难的问题。但如果这里的「更难」指得是解决问题所花费时间更长的话,这个论断是不正确的。从算法角度来看, NP-hard 问题的确比 NP 难,但比 NP 还难(指花费时间更多)的问题却不见得是 NP-hard 的。
后一篇:
最近常看到官方的报导说今年的物价上涨属于结构性上涨,但一直没太明白这个结构性上涨是什么意思,上网看了一下,没找到什么特别权威的资料,大致有两种说法。