采用常用的二进制哈希函数-例如SHA-256。顾名思义，它输出一个256位值。
让A是所有可能的256位二进制值的集合。 A很大，但是有限。
让B是所有可能的二进制值的集合。 B是无限的。
让C是通过在B的每个成员上运行SHA-256而获得的一组值。显然，这不能在实践中完成，但我想我们仍然可以对其进行数学分析。
我的问题：根据需要，C⊆A。但是C = A吗？
编辑：正如一些答案所指出的，这完全取决于所讨论的has函数。因此，如果您知道任何特定哈希函数的答案，请这样说！
首先，我们要指出SHA-256不接受所有可能的二进制字符串作为输入。根据FIPS 180-3的定义，SHA-256接受长度小于2 ^ 64位（即不超过18446744073709551615位）的任何位序列作为输入。这很常见；所有哈希函数的形式输入长度都受到某种限制。原因之一是关于计算成本定义了安全性概念。任何攻击者都可能会遇到有关计算能力的阈值。超出给定长度的输入将需要比最大计算能力更多的能量来简单地评估函数。简而言之，密码学家非常警惕无穷大，因为无穷大倾向于防止甚至定义安全性，更不用说量化了。因此，您的输入集C应该限于最多2 ^ 64-1位的序列。
话虽这么说，让我们看看关于散列函数外推性的了解。
哈希函数尝试模仿random oracle，这是一个概念性对象，它在“记住”以前的输入和输出的唯一约束下随机选择输出，并且，如果给出了已经看到的输入，则返回相同的对象输出比以前。根据定义，只有通过尝试输入并耗尽输出空间，才能证明随机预言是具有排斥力的。如果输出的大小为[[n位，则预计将需要大约2 ^（2n）个不同的输入来耗尽大小为[[2 ^ n的输出空间。对于n = 256，这意味着对2 ^ 512消息（例如，所有512位消息）的散列应该足够（平均）。 SHA-256接受的输入远远长于512位（实际上，它接受的输入最多为18446744073709709551615位），因此，高度合理 SHA-256似乎是排斥性的。
但是]，尚未证明SHA-256是射影，即expected。如上所示，随机预言的证明性证明需要巨大的计算能力，远远超过诸如原像（2 ^ n）和冲突（2 ^（n / 2）
之类的攻击。 ）。因此，良好的散列函数“不应”允许诸如证明超越性之类的属性得到实际证明。这将是非常可疑的：哈希函数的安全性源于其内部结构的难处理性，而这种难处理性应坚决反对进行数学分析的任何尝试。因此，对于任何体面的散列函数，甚至对于诸如MD4之类的“散列”散列函数，都没有正式证明排斥性。它只是“高度怀疑”（输入比输出长得多的随机预言应该是排斥的）。