现在我的问题是，$ n $将有多大，这样$ \ text {SHA256} ^ n（v）= v $？
在我看来，如果这是一种巨大的排列，则$ n $必须是$ 2 ^ {256} $，对吗？那是可证明的，或者有任何信息吗？ （真的，只是出于好奇。）
我遇到的另一个问题是，所有256位字符串是否都具有唯一的SHA256值，并且有办法显示吗？ （或者换句话说，是否可以证明所有“ 256位字符串”的语言都没有SHA-256冲突？）
#1 楼
$ \ text {SHA256} $旨在充当随机函数。在该假设下，可以预期对于大多数256位$ v $，不存在正整数$ n $，而$ \ text {SHA256} ^ n（v）$等于$ v $。换句话说，大多数$ v $不属于一个循环。为了直观地说明这一点，在下图显示了7位哈希的迭代过程中，我用红色绘制了属于循环的点。
评论
$ \ begingroup $
太好了。这使我想起了菲利普·弗拉霍莱特（Philippe Flajolet）的工作，不幸的是很多年前。我参加了他关于解析组合的演讲之一。
$ \ endgroup $
– Robert NACIRI
15年3月25日在21:18
$ \ begingroup $
Flajolet Odlyzko在1980年代的一篇论文（CRYPTO或Eurocrypt）中首次在加密环境中研究了这一点。
$ \ endgroup $
– kodlu
17年6月25日在8:28
$ \ begingroup $
总体而言，重新哈希可以提高安全性吗？
$ \ endgroup $
–亚伦·弗兰克（Aaron Franke）
18-10-21在23:05
$ \ begingroup $
@AaronFranke可以通过阻止长度扩展攻击来提高安全性，或者由于各种原因而损害安全性。需要更多详细信息！超出此问题的范围，但是如果您有更多详细信息，则可以打开一个新问题。
$ \ endgroup $
–吱吱作响的s骨
19年3月31日19:40
#2 楼
对于具有256位输出的随机函数，平均值几乎是$ \ sqrt {\ hspace {.03 in} 2 \ hspace {-0.05 in} \ cdot \ hspace { -0.04 in} \ pi} \ cdot 2 ^ {127} $。
我们没有什么可以说是SHA-256更具体的。
评论
$ \ begingroup $
让我纠正我的问题：这平均需要进行几次尝试？
$ \ endgroup $
–Richard M. Stroup
16年8月4日在2:19
$ \ begingroup $
@otus：为此，它取决于“时间”是指“评估哈希”还是“选择原始文本”。
$ \ endgroup $
–user991
16年8月4日在8:16
$ \ begingroup $
@RickyDemer，对不起，是的，我很快读了一个问题-都在问。因此，要回答这个问题：以上是您陷入循环的时间，但不一定要包含初始值（因为正在寻找第二个代码）。
$ \ endgroup $
–otus
16年8月4日在8:24
#3 楼
fgrieu提供了引人注目的视觉插图，但我们也可以对此进行量化。从哈里斯（Harris）1960年开始（无付费墙），对于$ \ ell $元素上的统一随机函数$ H $，循环上$ q $元素的数量由$$ p（q）= \ frac {（ \ ell-1）！ \，q} {（\ ell-q）！ \，\ ell ^ q}，$$，其期望随着$ \ frac 1 2 \ sqrt {2 \ pi \ ell} $而增长。如果我们将SHA-256建模为统一随机函数（当我们考虑长度扩展攻击时该模型会分解，但在固定长度输入上该模型基本合理），则我们有$ \ ell = 2 ^ {256} $。因此，任何特定元素在一个循环上的概率约为$ 1 /（2 ^ {127} \ sqrt {2 \ pi}）$。换句话说，除非您对SHA-256有所了解，否则您将永远找不到循环中的元素。循环长度$ n $的分布如何？事实证明，它们具有相同的分布，对于256位函数，期望值为$ 2 ^ {127} \ sqrt {2 \ pi} $。因此，即使您以某种方式在循环上找到了一个元素，您也几乎肯定无法确认它是否在循环上-再次，除非您对SHA-256有所了解。
哈里斯论文也涵盖了关于均匀分布的随机函数和排列以及从未将元素映射到其自身的均匀随机函数和排列的几乎所有其他信息！
#4 楼
如果将哈希从长度为256的输入字符串建模为随机函数$ H $到相同长度的输出，则$ H $实际上是排列的概率（这等于说所有输入都有唯一的输出）可忽略不计。因此，发生这种情况的机会接近于0。对于随机函数，已知一些关于循环长度的结果，我相信预期的循环长度约为$ 2 ^ {128} $ ，即输入大小的根。参见例如本文
评论
身份函数是一个置换，将获得$ \：n = 1 \; $。 $ \; \; \; \; $使用分组密码（这是一个置换），周期长度将在$ 2 ^ {255} $左右，而散列值则在$ 2 ^ {128} $附近。但是，当然，这些只是统计值，并且存在较短和较长的周期。
没有特别要求，但是如果您想通过这种构造防止循环，则可以在每次迭代时将n的256位表示形式与先前的哈希值连接起来。因此$$ \ text {SHA256} ^ n（v）== {SHA256}（n_ {256} || {SHA256} ^ {n-1}（v））$$
关于256位字符串冲突的其他问题在这里得到了回答（对于SHA-512，但原理相同）。
这些循环称为循环。周期通常非常大。