gpt4 book ai didi

hash - 通过_brute force_破坏单向哈希属性和证明碰撞之间的区别

转载 作者:行者123 更新时间:2023-12-01 22:44:06 34 4
gpt4 key购买 nike

对于任何哈希函数,从概念上或其他方面来说,上述两种操作之间有什么区别。我通过以下方式解决了这个问题:

H=hash(someplaintext)
n=0
while 1:
if hash(str(n))==H:
print n
n+=1

这两个性质都可以这样证明,有什么不对吗?忽略效率、内存使用或任何此类属性。请严格按照正确性回答我的问题

最佳答案

“单向”意味着给定一个函数输出,您无法找到匹配的输入,除非尝试许多可能的输入并幸运地获得。碰撞是关于找到两个产生相同输出的不同输入,而对所述输出没有任何预定义的约束。

一个好的(加密)散列函数应该具备三个经典属性:

  • 原像抗性:给定x,找到m应该是不可行的h(m) = x.
  • 对第二原像的抵抗:给定 m,找到与 m 不同的 m' 应该是不可行的, 这样 h(m) = h(m')
  • 抗碰撞:找到 mm' 应该是不可行的,它们彼此不同,这样 h (m) = h(m')

这可以看作是对攻击者的三个挑战,按难度递减排序。对于原像,我给你一个输出,我挑战你找到一个匹配的输入。对于第二个原像,我给你一个输入(并隐含地给出相应的输出),然后我挑战你找到另一个匹配的输入。对于碰撞,这就像第二个原像挑战,除了我不要求你找到特定的输出;任何人都可以。或者,换句话说:对第二个原像的挑战就像对碰撞的挑战,其中一个碰撞消息不能由攻击者自由选择。

在不利用哈希函数本身的任何弱点的情况下,对于具有 n 位输出的哈希函数,用于查找原像、第二原像和碰撞的通用方法的成本约为 2n(用于原像和第二原像)和 2n/2(用于碰撞)。因此,查找碰撞要容易得多。对于原像,您只需尝试输入直到幸运为止(这就是您所说的“蛮力”);每次尝试都有 2-n 成功的概率。对于碰撞,这与 birthday attack 有关: 基本上,一旦你积累了大约 sqrt(2n) 对输入/输出,其中两个具有相同输出的对的概率上升得非常快。

就生日而言,这意味着如果您随机抽取 20 个人,其中两人生日相同的可能性很高 - 但您无法选择哪一天或哪些人。另一方面,如果你想找到与生日相同的人,那么你将不得不平均抽样 365 个人。

关于hash - 通过_brute force_破坏单向哈希属性和证明碰撞之间的区别,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5643612/

34 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com