2014-03-13 166 views
0

我很难在纸上和头脑中完成这项工作。我知道这是围绕生日悖论,但是,我似乎无法理解我的问题和BP的解决方案之间的价值互换性。SHA-1碰撞概率

好的,所以我知道SHA-1产生160位的散列。

两个消息和0.5的概率之间,多少次应该说,“攻击者”必须搜索找到相同的哈希值?

我遇到了一系列解决方案,从搜索,但没有说透走我走过的过程,并在某种程度上对我来说很有意义解释。下面是我在搜索过程中能够想到的最接近的地方。

enter image description here

我希望这有助于解释我的问题。

+0

我认为我在一定程度上解决了它。基本上因为总共有160位涉及到2^160/2,所以找到搜索的次数来找到0.5的概率。 如果有人有更好的解决方案或可以澄清我的解决方案,请做。 –

+0

有一个加密SE,这样的问题是适合的... –

回答

0

是的,你是对的;这个圆圈围绕着Birthday Problem。在哈希中,你基本上试图通过数学过程将理论上无限长度的东西放入固定长度的字符串中;因此碰撞是不可避免的。

生日问题基本上意味着假设你有一个满是人的大厅,你问每个人他们的出生日期。由于你有更多的出生日期,两个人可以拥有相同的生日,因此找到与另一个生日相同的人的概率增加。最终你会找到有同样生日的人。

SHA1本来是针对MD5的替代品:

Graph of the birthday problem

亚伦Toponce在他的作品"The Reality of SHA1"他指出,写了这一点。 MD5的输出空间为 ,只有128位,其中SHA1的输出空间为160位。 SHA1是 也是设计不同于MD5,并且不会承受MD5面临的同类弱点或攻击。然而,随着时间的推移,密码学家已经能够严重攻击SHA1,并且作为 的结果,他们都警告我们要下SHA1,并转移到SHA2。 使用生日悖论查找与SHA1的冲突应该需要2^160次操作,但是使用生日悖论的 ,我们可以在大约2^80次操作中发现SHA1冲突的概率为50%。然而,密码学家已经将SHA1拆分为只有2^61 操作的复杂性。更好。

本质上,SHA1是一种数学算法,可以在算法中找到弱点,使它们更易于破解并降低碰撞概率。这项通常由计算机科学家,密码学家和数学家完成的研究可以用于通过使用新算法找到发现碰撞的新方法来减少发现碰撞的机会。