我正在读教科书中有关查找碰撞方法的信息。它声明考虑输出大小为256位的散列函数发生冲突，如果选择随机输入并计算散列值，则会写出一个发现，即如果我们选择$ 2 ^ {130}，则发现冲突的可能性很高。 $ + 1个输入，结果至少有两个输入发生碰撞的机率高达99.8％。它还说，我们可以通过大概看一下可能的输出结果数的平方根来找到冲突。
问题：
如果选择$ 2 ^ {130} $ + 1个输入至少2个输入，用于计算的公式是什么会以99.8％的概率发生冲突吗？
从我的研究来看，这似乎与“生日攻击”问题有关，在该问题中，您首先计算哈希输入不发生冲突的可能性并将其减去从1.开始，每当我尝试使用在网上发现的公式进行插拔时，都没有得到书中所述的结果。
编辑：我尝试使用公式P（A）= 1-$ \ frac {k！} {（kn）！k ^ {n}} $，并获得了
99.99 .. 。％。我不知道作者如何获得99.8％的百分比。有人可以说明使用的显式方程式，以便让我看到这本书如何通过$ 2 ^ {130} $ +1随机选择的输入获得99.8％的碰撞概率吗？ +1的来源是什么？
平方根函数与此有何关系？如果我取256的平方根，我得到16。这在冲突的情况下意味着什么？
输出的大小为256位。这是否意味着可能的输出总数为$ 2 ^ {256} $？
信鸽原理是否适用于此？您正在获取无限量的输入并将它们映射到有限量的输出。
#1 楼
密码散列的生日问题，101。让$ p_n $为多个$ n $随机离散输入的散列为$ k $可能值的冲突概率（即至少假设哈希是完美的，则两个哈希是相同的）。 $ p_n $也是在散列上没有任何假设的情况下发生碰撞的最小概率。如果$ j> k \; $，则$ p_j = 1 $（根据信鸽的原理，如果有$ k $个孔，则有超过$ k $的信鸽，至少一个信鸽需要与另一个信鸽共享一个信鸽）。
让$ q_j = 1-p_j \; $是$ j $散列没有碰撞的概率，其中$ q_0 = 1 $。当我们在先前的$ j $哈希值之间没有冲突之后添加另一个哈希值时，新哈希值具有匹配$ j $先前哈希值之一（创建第一个冲突）的概率$ \ frac jk $，并且概率为$ 1- \不会产生碰撞。因此，重复发生：$ q_ {j + 1} = q_j \，\ bigl（1- \ frac j k \ bigr）$。确切的是：
$$ p_n = 1-q_n \ quad \ text {with} \ quad q_n = \; \ prod_ {j = 0} ^ {n-1} {\ Bigl（1- \ frac jk \ Bigr）} \; = \; {\ frac {k！} {（kn）！\; k ^ n}} $$
也就是$ \ displaystyle q_n \，= \ ，P（k，n）/ k ^ n \，= \，C（k，n）\，n！/ k ^ n \，= \，{k \选择n} \，\ frac {n！} { k ^ n} $，其中$ P（k，n）$是$ k $中$ n $事物的排列数，而$ C（k，n）= {k \ choose n} $是$ k $中$ n $事物的组合（请注意，与链接引用相比，$ k $和$ n $在此答案中是相反的）。
对于$ k $和$低的情况很好n $，但对于大价值不切实际。在$ n \ ll k \，$的情况下，将其应用到较小的$ \ epsilon> 0 $时，可得出$ \ log（1- \ epsilon）\ lessapprox- \ epsilon \; $，我们得到
$$ \ log（q_n）\; = \; \ sum_ {j = 0} ^ {n-1} {\ log \ Bigl（1- \ frac jk \ Bigr）} \; \ lessapprox \;-frac 1 k \ sum_ {j = 0} ^ {n-1} j \; = \; {-\，\ frac {n \，（n-1）} {2k}} $$
总而言之，我们完全是
$$
＆= 1 -{k \选择n} \，\ frac {n！} {k ^ n} && = 1-C（k，n）\，n！/ k ^ n
\ end {align *} $$
，当上述方法不方便时，作为合理的近似值
$$ p_n = 1-q_n \ quad \ text {with} \ quad
\ begin {align}
＆q_n \ lessapprox e ^ {-n \，（n-1）/（2k）}＆\ text {（假设$ n \ ll k $）} \\
＆q_n \约e ^ {-n ^ 2 /（2k） }＆\ text {（另外假设大$ n $）}
\ end {align} $$
由此我们可以得出密码术中使用的大$ k $，或者$ b $位哈希（其中$ k = 2 ^ b）$，$ n $随机消息的碰撞概率和几率大约为
$$
\ def \ alignedcolumn＃1＃2＃ 3＃4＃5 {\ phantom {＃1} \ llap {＃3} \ mathrel {＃4} \ rlap {＃5} \ phantom {＃2}}％
％在左侧指定最宽的表达式左右手。
\ def \ ncolumn {\ alignedcolumn {1.177 \ sqrt k} {2 ^ {b / 2 + 0.236 \ ldots}}}％
\ def \ pncolumn {\ alignedcolumn {1-e ^ {-1/2}} {00.0 \％}}％
\ def \ oddscolumn {\ alignedcolumn {} {11/17}}％
\ begin {array} { c | c | c}
n＆\ text {$ p_n $ of c ollision}＆\ text {碰撞的可能性} \\
\ hline
\ ncolumn {\ sqrt k} = {2 ^ {b / 2}}＆\ pncolumn {1-e ^ {-1 / 2}} \ approx {39.3 \％}＆\ oddscolumn {} \ approx {11/17} \\
\ ncolumn {1.177 \ sqrt k} \ approx {2 ^ {b / 2 + 0.236 \ ldots }}＆\ pncolumn {1/2} = {50 \％}＆\ oddscolumn {} {\ phantom {=}} {\ hphantom {1} 1/1} \\
\ ncolumn {1.414 \ sqrt k} \ approx {2 ^ {（b + 1）/ 2}}＆\ pncolumn {1-e ^ {-1}} \ approx {63.2 \％}＆\ oddscolumn {} \ approx {12/7} \ \
\ ncolumn {2 \ sqrt k} = {2 ^ {b / 2 + 1}}＆\ pncolumn {1-e ^ {-2}} \约{86.5 \％}＆\ oddscolumn {} \ approx {19/3}
\ end {array}
$$
应用的密码学家通常对冲突概率极低的$ p_n $感兴趣，发生在$ n \ ll \ sqrt k $中。上述近似值在数学上仍然有效并且可用于$ q_j $，但由于$ p_j = 1-q_j $的差值比减法中的任一项都小，数量级较小，因此得出的结果可能不准确。我们需要另一种方法。
当$ i $ th散列等于$ j $ th散列时，对于任何$ 1 \ le i
＆\ lessapprox {\ frac {n ^ 2} {2k}}＆\ text {（另外假设大$ n $）} \ end {align *} $$
例如，将$ n = 2 ^ {100} $个不同的随机输入（假设地）散列为$ b = 256 $个具有完美（甚至可传递）散列的位，则碰撞的可能性约为$ 2 ^ {2 \ cdot100 -1-256} = 2 ^ {-57} $（在一亿亿美元中有不到8个机会，可以安全地打折）。
问题中，我们有一个使用$ b = 256 $位的散列，因此可以获取$ k = 2 ^ b = 2 ^ {256} $的输出值和$ n = 2 ^ {130} +1 \; $的输出值。这里$ k $大，$ n \ ll k $和$ n \ not \ ll \ sqrt k $，因此合适的公式是
$$ p_n = 1-q_n \ quad \ text {与} \ quad q_n \ approx e ^ {-n ^ 2 /（2k）} \ quad \ text {（假设大$ k $和$ n \ ll k $）} $$
$ n = 2 ^ {130} + 1 $中的$ + 1 $项可以忽略不计，我们得到$ -n ^ 2 /（2k）\ approx- \ left（2 ^ {130} \ right）^ 2 / \ left（2 \ cdot2 ^ {256} \ right）=-2 ^ {2 \ cdot130-1-256} =-2 ^ 3 = -8 \; $，得到$ q_n \ approx e ^ {-8} \ approx0 .034 \％$和$ p_n \ approx99.966 \％\; $。
注意：$ n \ approx2 ^ {130} $太大，以至于几乎不可能携带该数量的操作，更少的哈希值。因此，问题的正文和当前的答案均不包含任何有助于在输出大小为256位的哈希函数中发现冲突的内容（如问题的原始标题一样）。
无论四舍五入约定如何，问题中的大约99.8％和99.99％的最后一位数字都不正确。
评论
$ \ begingroup $
感谢您的答复。我不确定您是否仍在逐步构建解决方案，但这是我的问题：1）您如何使用公式：1-$ \ frac {k！} {（kn）！k ^ {n}} $计算发生碰撞的概率x？这里说x = 99％-还是说对于（k，n）值，输出是发生碰撞的概率？ 2）这是否是公式的正确“即插即用”：1-$ \ frac {2 ^ {256}！} {（2 ^ {256} -2 ^ {130}）！（2 ^ {256}） ^ {2 ^ {130}}} $？ 3）我应该使用斯特林近似中的哪个特定公式，以及我的示例中的“ plug n chug”版本是什么？谢谢！
$ \ endgroup $
–最大
16年8月27日在19:42
$ \ begingroup $
4）sqrt（2 ^ 256）能否告诉我发生碰撞的概率约为50％（在我的示例中）？
$ \ endgroup $
–最大
16年8月27日在19:47
$ \ begingroup $
@fgrieu，您对$ p_n $的近似公式是正确的。 Max无法直接计算那些阶乘，无法使用答案中给出的近似值求解$ k $或$ x $，无论您希望用哪个来表示。答案中的重复精确给出了您的表达式$ k！/（（（k-n）！k ^ n。$
$ \ endgroup $
– kodlu
16年8月28日在1:40
$ \ begingroup $
@ fgrieu--我想接受你的回答。但是，请解决以下问题：＃1是：1-e ^（（-2 ^ 130）^ 2）/（2 *（2 ^ 256））= .9996 ...您编写的近似值的正确应用？ ＃2：此响应的第一个评论是否正确应用是生日攻击公式？ ＃3：以$ 2 ^ {256} $的平方根表示碰撞是什么意思？
$ \ endgroup $
–最大
16年8月28日在11:55
$ \ begingroup $
@ fgrieu-这不是家庭作业。我正在自学（不知道有什么要问的教授），所以这就是为什么我试图理解我正在阅读的文本中的每个句子。非常感谢您的回应。您回答了我的问题，因此接受了您的答复。谢谢！ :)
$ \ endgroup $
–最大
16年8月28日在12:15
评论
这是生日问题的基本变体。是的$ b $位输出表示$ 2 ^ b $可能的输出（并且您没有应用该值，因此至少存在一些问题）。 $ 2 ^ b $是近似碰撞/生日边界的平方根。信鸽原理适用于鸽子/哈希数多于漏洞/可能的输出值的情况，因此，在上下文中，哈希数远大于碰撞边界。感谢您的回复。您能解释一下用于计算$ 2 ^ {130} + 1 $随机输入的公式时，发生碰撞的概率为99.8％吗？我尝试使用公式P（A）= 1-$ \ frac {k！} {{kn）！k ^ {n}} $ = 1-$ \ frac {256！} {（256-130）！256 ^ {130}} $ = 99.99 ...％，而不是书中的99.8％。这来自：cs.duke.edu/courses/cps102/spring09/Lectures/L-18.pdf第49页。能否解释该公式并举例说明如何进行计算？
我的猜测：这本书使用了近似的公式，得出了“略微”较不精确的答案。另外，我认为您无需在计算中使用位长，而应使用实际值，例如，如果$ 256 $（与130相同），请使用$ 2 ^ {256} $。
弗格里乌（Fgrieu），这本书并不清楚我对您有多少价值观/哈希。我假设$ 2 ^ {256} $个可能的输出哈希值和$ 2 ^ {130} $个随机选择的输入哈希值（来自可能的无限量）。有问题的问题与：i.imgur.com/WcEk8xh.jpg有关。您知道+1的来源吗？
@max：您拥有正确的计数（哈希值可能在1之内，现在暂时忽略它，并假设$ 2 ^ {130} + 1 $意味着刚好在$ 2 ^ {130} $以上）。但是您还没有完全将其插入公式中。而且数字太大，以至于计算器或Excel无法处理它们。您的$ 3.4 \ cdot10 ^ {38} $是正确的，可以为您提供50％的碰撞几率的哈希值。 $ 2 ^ {130} $更大，发生碰撞的可能性更大；全部对齐。