math - 密码散列函数是否达到每个可能的值，即它们是否是宾语？

Question

以一个常用的二进制哈希函数为例，例如SHA-256。顾名思义，它输出一个256位值。

令A为所有可能的256位二进制值的集合。 A很大，但是很有限。

令B为所有可能的二进制值的集合。 B是无限的。

令C为在B的每个成员上运行SHA-256所获得的一组值。显然，这在实践中是无法完成的，但我想我们仍然可以对其进行数学分析。

我的问题:必然，C⊆A。但是C = A吗？

编辑:正如一些答案所指出的，这完全取决于所讨论的has函数。因此，如果您知道任何特定哈希函数的答案，请这样说!

Answer 1

首先，让我们指出SHA-256不接受所有可能的二进制字符串作为输入。如FIPS 180-3所定义，SHA-256接受长度小于2 ^ 64位(即不超过18446744073709551615位)的任何位序列作为输入。这是很常见的。所有哈希函数都在某种程度上限制了形式输入的长度。原因之一是在计算成本方面定义了安全性概念。任何攻击者都可能会遇到有关计算能力的阈值。超出给定长度的输入将需要比最大计算能力更多的能量来简单地评估函数。简而言之，密码学家非常警惕无穷大，因为无穷大倾向于防止甚至定义安全性，更不用说量化了。因此，您的输入集C应该限制为最多2 ^ 64-1位的序列。

话虽如此，让我们看看关于哈希函数外射性的知识。

散列函数尝试模拟一个随机预言，这是一个概念性对象，它在“记住”以前的输入和输出的唯一约束下随机选择输出，并且，如果给定已经看到的输入，则返回的输出与以前相同。根据定义，只有通过尝试输入并耗尽输出空间，才能证明随机预言是具有排斥力的。如果输出的大小为n位，则预期将需要大约2 ^(2n)个不同的输入来耗尽大小为2 ^ n的输出空间。对于n = 256，这意味着散列大约2 ^ 512条消息(例如，所有512位消息)应该足够(平均)。 SHA-256接受的输入远远长于512位(实际上，它接受的输入最多为18446744073709709551615位)，因此SHA-256的推测是很合理的。

但是，尚未证明SHA-256是射影，即是预期的。如上所示，随机预言的证明性证明需要大量的计算能力，远远超过诸如原像(2 ^ n)和碰撞(2 ^(n / 2))之类的攻击。因此，良好的哈希函数“不应”允许诸如证明超越性之类的属性得到实际证明。这将是非常可疑的:哈希函数的安全性源于其内部结构的难处理性，而这种难处理性应坚决反对进行数学分析的任何尝试。

结果，对于任何体面的散列函数，甚至对于“断开的”散列函数(例如MD4)，都没有正式证明排斥性。它只是“高度怀疑”(输入比输出长得多的随机预言应该是排斥的)。