比特币历史 91 | Random(5): 生日攻击

（生日攻击，图片来自网络）

回顾以前的情况：

文字：

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

"比特币地址是唯一使用160位哈希的地方。其他都是SHA-256。公式是："

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

中本聪分析了两种攻击方式。一种是碰撞攻击，另一种是分析攻击。前者是蛮力攻击，后者是试图找出哈希算法的弱点并破解它。

对于哈希函数的碰撞攻击，有一种称为“生日攻击”[2] 的方法可以非常有效。能提高多少？对 160 位哈希执行生日攻击所需的尝试次数不是 2 的 160 次方（表示为 2^160)，而是 2 的 80 次方（表示为 2^8< @0)). ，效率提高了 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 的输出。如果分析攻击帮助你找到一个 RIPEMD-160 会产生一个碰撞 Input，那么你会怎么做呢？您仍然必须使用 SHA-256 来输出该值比特币生日是哪天，因此您仍然需要再次破解 SHA-256。”

最后，Nakamoto 总结道，“因为，RIPEMD-160 (SHA-256(x)) 并不强于单独的 RIPEMD-160。但是对于分析攻击来说，似乎 RIPEMD-160 和 SHA-256必须同时分析。如果我错了，强度与RIPEMD-160相同比特币生日是哪天，而SHA-256仅用作一轮关键加固。”