我很好奇,例如,如果SHA-256数量有限,怎么会是唯一的呢?!

为了澄清:
有多少个MD5哈希可以生成$ 16 ^ {32} $ MD5哈希值。
可以生成$ 16 ^ {64} $ SHA-256哈希。
只有SHA-512哈希有$ 16 ^ {128} $,更不用说长文本了。

需要更多说明:
我们希望所有SHA-256哈希中的MD5。我们可以有$ 16 ^ {32} $个MD5哈希,而有$ 16 ^ {64} $ SHA-256哈希值。
我们将有3.4 * $ 10 ^ {38} $个MD5哈希值重复!

SHA-256哈希也是如此,如果我们计算所有SHA-512哈希的SHA-256,我们将有1.15 * $ 10 ^ {77} $个重复的SHA-256哈希! />
编辑:这不限于SHA-256之类的特定哈希。

评论

由于鸽子洞原理,当您接受大于输出的输入时,您将永远无法避免冲突。哈希不是唯一的,它们只是设计来使查找冲突变得困难(因此,是的,有重复项,至少在SHA-2中不会找到任何重复项)。

是什么让您认为哈希是独特的?实际上,它们并非唯一是“哈希函数”定义的一部分,该函数将一个可能无限大的输入空间映射到一个较小的固定输出空间。

SHA-256的副本“几乎唯一”? –事实上,此处接受的答案处理的内容与其他Q&A的接受答案完全相同(SHA-256,唯一性等),这说明此答案是重复的,因此我将此Q&A搁置。

哈希不应该是唯一的。当我在〜1 GB的映像中更改配置文件时,sha1及其压缩大小不会更改。但是,如果我想以一种特定的方式更改较小的图像以符合将起作用并产生相同散列的配置文件格式,则不会有数学上可证明的,通用且快速的(因为它的速度快于应考虑的速度)散列中的位数)。这就是密码安全哈希函数的目的。这是MD5失败的地方,而大多数SHA系列都占了上风。

#1 楼


如果仅有限数量的SHA-256,例如该如何唯一?!


出现问题的地方是它们不是唯一的。他们再次发生是非常不可能的。在这种情况下,唯一性不是数学定义,而是人文主义。

就人类数而言,$ 2 ^ {256} $ = 115792089237316195423570985008687907853269984665640564039457584007913129129639936是可见宇宙中原子数的0.1%。

还有一个更好的答案@为什么还没有发现SHA-256碰撞?但是您应该从冗长的116 quattuorvigintillion数字中获取要点。

评论


$ \ begingroup $
评论不用于扩展讨论;此对话已移至聊天。
$ \ endgroup $
– e-sushi
18年4月12日在3:16

#2 楼

没错,哈希值不会像您已经展示的那样唯一。重要的部分是实际冲突-在整个生命周期中,整个地球会产生多少SHA-512哈希?绝对比$ 2 ^ {512} $小得多,甚至比$ 2 ^ {128} $小。

让我们猜测不切实际的高,说我们从完全随机的输入生成这些$ 2 ^ {128} $哈希,没有两个输入相同。其中任何两个相同的概率有多高?不能保证它们都会有所不同,但是发生碰撞的机会非常小,您可以忽略它。它是如此之小,即使连续五次赢得彩票,也有更大的机会。这就是为什么我们说哈希是唯一的(只要哈希函数是安全的),因为它不太可能在地球的生命周期中不会发生碰撞。

评论


$ \ begingroup $
产生$ 2 ^ {128} $哈希后,如果哈希的大小为256而不是512位,则生日悖论会介入并产生50%机会的冲突。因此,风险确实非常低:这就像在256个哈希的截断部分中选择一个碰撞,然后碰巧所有剩余的256位都必须匹配。因此,这实际上就像是第一次尝试用一个公平的硬币连续扔掉256个磁头
$ \ endgroup $
– Hagen von Eitzen
18年4月11日在6:33

#3 楼

256位散列的数量大约是银河原子数的一百万倍(给定或取几百个原子...)。因此,这不仅是一个有限的数目,而且是一个很大的有限数目。

您有什么机会在银河系中挑选任何两个原子(而不仅仅是我们的太阳系)并意外地得到一个?

因此,说它们是唯一的,从技术上来说确实是错误的,但这是一个合理的,实际的假设。您不会活出相反的事实。

评论


$ \ begingroup $
评论不用于扩展讨论;此对话已移至聊天。
$ \ endgroup $
– e-sushi
18年4月12日在3:17

#4 楼

正确,尽管我们说哈希函数会产生“唯一的”输出,无论您多么努力,它都永远不会与不同的输入复制,但从理论上讲,可以创建一个哈希冲突,其中两个不同的输入给出一个匹配的输出。例如,字符串:

d131dd02c5e6eec4 693d9a0698aff95c 2fcab58712467eab 4004583eb8fb7f89
55ad340609f4b302 83e488832571415a 085125e8f7cdc99f d91dbdf280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2b487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080a80d1e c69821bcb6a88393 96f9652b6ff72a70


和字符串:

d131dd02c5e6eec4 693d9a0698aff95c 2fcab50712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325f1415a 085125e8f7cdc99f d91dbd7280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e23487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080280d1e c69821bcb6a88393 96f965ab6ff72a70


也会产生相同的MD5哈希是几个不同的数字。这是特别重要的,因为使用MD5来验证数据完整性(针对有意和无意的破坏),因为通常会破坏一些数据。 1992年,它被认为可以产生“唯一的”输出,但是在那时,计算机的处理能力大大降低,并且搜索MD5哈希冲突的效率极低。在2018年,现在可以在几秒钟内找到MD5碰撞。

就SHA-256和SHA-2系列的其余部分而言,它们目前不是已知的碰撞(但是SHA1专用,此处有更多信息:https://shattered.it/),但由于SHA哈希都具有有限的输出长度(256位,512位),因此使用Pigeonhole原理(https://en.wikipedia.org/ wiki / Pigeonhole_principle)指出,如果输入大于预定义输出长度的输入,例如使用SHA-256散列的300位输入,则必须有另一个256位以下的输入,该输入提供与散列相同的输出300位字符串中的无论您多么努力,您都无法将比散列更多的数据放入散列中。

回到最初的问题,因为几乎所有散列算法都会产生预定义长度的散列,与输入大小无关,只要您的哈希函数允许任意大小的输入(对于几乎所有哈希函数都是如此),总是有两个不同的输入具有相同的哈希的可能性。

对于不耐烦的人,我很好奇,答案很好,例如,如果只有有限数量的SHA-256,SHA-256怎么能唯一?!


是:他们不能。输出数量有限,数学规则表明,如果没有重叠(即哈希冲突),我们就无法将更多数据放入较小的空间。任何“固定输出大小”哈希值在数学上都不是唯一的,而在我们计算事物的能力上不是唯一的。如果可能的话,一种“伪唯一”,就像“伪随机”一样。而且我们只说哈希函数产生唯一的输出,因为我们没有足够的能力来找到两个不同字符串的相同哈希。就像我们所说的指纹一样。从理论上讲,两个人可能有相同的指纹,但很难找到。

那该怎么办呢?

现在,我们应该完全使用当前的哈希算法很好,但是从理论上讲,如果实际上存在哈希不够“唯一”的问题,我们可以转向产生无限长输出(或可变大小输出)的哈希算法。据我所知,这些都不存在,但是我确信可以做到。而且,如果我们总是使哈希值比数据长,那么从理论上讲,我们将保证有一个哈希函数每次都能产生真正唯一的输出。

所以这只是我的两点。密码学存在比这更大的问题,但这值得一提。干杯!