比特币历史 91 | 随机（5）：生日袭击

（生日来袭。图片来自网络）

往期情况回顾：

文本：

对比特币地址的攻击旨在控制其背后的资产——私钥。 2010年7月25日，中本聪在论坛参与讨论“盗币”话题时指出比特币地址使用了160位哈希[1]：

“比特币地址是唯一使用 160 位哈希的地方。其他一切都是 SHA-256。计算是：”

“比特币地址 = RIPEMD-160(SHA-256(公钥))”

中本聪剖析了两种攻击方法。 一种是碰撞攻击，另一种是分析攻击。 前者是暴力攻击，后者则是试图寻找哈希算法的弱点来攻破它。

针对哈希函数的碰撞攻击，有一种叫做“生日攻击”（birthday attack）[2]的方法可以出人意料地提高效率。 能提高多少？ 对160位哈希进行生日攻击所需的尝试次数不是2的160次方（表示为2^160），而是2的80次方（表示为2^80），效率完全提高了 2 80 倍 (2^80 * 2^80 = 2^160)。 因此，哈希函数的最小安全位数不能低于160位。 比特币使用的RIPEMD-160是已知最短的安全哈希函数，也是已知的最短哈希函数中最安全的。 在保证安全的前提下，长度较短可以方便记录和交流。

生日攻击的稍微违反直觉的原因来自组合爆炸。 我们每个人的生日都是随机分布在一年365天的某一天。 在一个有 23 名学生的班级中，至少有两名学生生日相同的概率是多少？ 答案是略微令人吃惊的50%概率，也就是有一半以上的概率有些同学会在同一天过生日。 如果班级人数增加到 50 人，这个概率会上升到 97%。

将生日视为一个哈希函数，它将每个人作为输入并具有 365 个输出值。 查找哈希冲突所需的计算次数与值空间的大小不成正比，而是与值空间大小的平方根成正比。 据称，量子计算机可以将这种效率进一步提高到价值空间大小的立方根。 只是实用的量子计算机迟迟没有问世，所以学术界对这一点也存在争议。

但是在攻击比特币地址背后的私钥这件事上，生日攻击方式是不行的，因为私钥是用户随机选择的，攻击者不能绝对选择私钥。 正如中本聪在上述论坛帖子中指出的那样，“如果你可以使用生日攻击，它就是 2^80。你不能为此使用生日攻击，所以难度是完整的 2^160 位。虽然，如果，如果你尝试 **100 万 (2^20) 笔交易中的任何一笔，你都可以执行部分​​生日攻击 2^160/2^20 = 2^140。”

关于分析攻击，中本聪再次写道，“如果我错了请指正（我会很乐意收回我说的话），但在这种情况下，我认为很难分析 RIPEMD-160 攻击。分析攻击预设范围或输入值的模式来尝试，这将大大增加发现碰撞的机会。在这里，你对RIPEMD-160的输入没有那种控制，因为输入是SHA-256的输出. 如果 Analysis attacks 帮助你找到一个产生碰撞的 RIPEMD-160 输入，那么你会怎么做呢？你仍然必须使用 SHA-256 来输出那个值，所以你仍然必须重新** SHA-256。 “

最后中本聪总结道，“因为，RIPEMD-160(SHA-256(x))并不比单独的RIPEMD-160强。但是对于分析攻击比特币生日快乐，似乎有必要对RIPEMD-160和SHA-256进行分析攻击同时。如果我错了比特币生日快乐，强度与RIPEMD-160相同，而SHA-256仅用作一轮**硬化。”