SHA-512 是否抗碰撞？

Question

根据我读过的书，它说S.H.A（安全哈希算法）是抗碰撞的。但是如果输入空间是1024位数字，输出空间是512位消息摘要，那么它不应该碰撞吗为了 (2^1024)/(2^512) 次？由于范围小于所映射的域，因此应该会发生冲突。请解释我哪里出错了。

Answer 1

碰撞的机会并不取决于输入的大小。 512 位哈希冲突的几率是 1.4×10^77，参见概率表

Answer 2

也许你的书中也提到了抗碰撞的定义？这并不意味着不会产生冲突（显然不是这种情况），而是给定一个哈希值，您无法轻松创建生成该哈希值的消息。

如果很难找到两个哈希函数 H，那么它是抗碰撞的输入散列到相同的输出；也就是说，两个输入 a 和 b 这样 H(a) = H(b)，且 a ≠ b

来自维基百科

Answer 3

正如您所描述的：由于输入空间（任意大小）大于输出空间（例如 sha512 为 512 位），因此总是存在冲突。

“防碰撞”意味着不太可能发生碰撞。

当考虑输出空间“512位”到底有多大时，你的困惑就得到了解答：

2^512（512 位数组的可能配置数量）的数量级为 10^154。

作为比较：可见宇宙中的原子数量大约在 10^80 的范围内。一百万是 10^6。所以像我们这样的一百万个宇宙有 10^86 个原子。一百万乘以一百万个宇宙是 10^92 个原子。

如果您可以在单个原子上存储单个 512 位值，那么您需要多少个宇宙来存储所有可能的 512 位哈希值？

从特定的 512 位数字开始（假设 has 函数没有被破坏），获得碰撞的概率

假设您可以以

的速率生成新的哈希值，并且总时间为

这样做是：

p = R*t/(2^(512/2))

（指数减半（谷歌“生日攻击”），因为：成功的预期搜索空间是在 n 位中找到碰撞，为 n/2。）让我们插入一些示例数字：

比特币网络的哈希率目前约为

R = 200*10^15 / s

（每秒 2 亿 terrahashes）。

考虑这样一种情况，自宇宙诞生以来，比特币网络当前的哈希容量将仅用于查找特定哈希值的冲突，即可用时间为

t=13.787*10^9 years

,

那么现在发现碰撞的概率约为 7 × 10^-41 %

再次强调，很难理解这个数字有多么小。