lev*_*and 28 math hash cryptography
采用常用的二进制哈希函数 - 例如,SHA-256.顾名思义,它输出256位值.
设A是所有可能的256位二进制值的集合.A非常大,但有限.
设B是所有可能的二进制值的集合.B是无限的.
设C是在B的每个成员上运行SHA-256获得的值集.显然这在实践中无法完成,但我猜我们仍然可以对它进行数学分析.
我的问题:根据需要,Ç ⊆ 一个.但C = A吗？
编辑:正如一些答案所指出的,这完全取决于有问题的函数.所以,如果您知道任何特定哈希函数的答案,请说出来!
Tho*_*nin 39
首先,让我们指出SHA-256不接受所有可能的二进制字符串作为输入.根据FIPS 180-3的定义,SHA-256接受长度低于2 ^ 64位(即不超过18446744073709551615位)的任何比特序列作为输入.这很常见; 所有哈希函数都以某种方式限制在正式输入长度中.一个原因是安全性的概念是在计算成本方面定义的; 有一个关于计算能力的门槛,任何攻击者都可以集合.超出给定长度的输入将需要超过最大计算能力来简单地评估功能.简而言之,密码学家对无限期非常警惕,因为无穷小往往会阻止安全性被定义,更不用说量化了.因此,您的输入集C应限制为最多2 ^ 64-1位的序列.
话虽如此,让我们看看有关哈希函数主观性的知识.
散列函数试图模拟一个随机oracle,这是一个概念对象,它在"记住"先前输入和输出的唯一约束下随机选择输出,并且,如果给定已经看到的输入,则返回与先前相同的输出.根据定义,只有通过尝试输入和耗尽输出空间,才能证明随机预言是无差异的.如果输出具有n位的大小,则预期将需要大约2 ^(2n)个不同的输入来耗尽大小为2 ^ n的输出空间.对于n = 256,这意味着散列大约2 ^ 512条消息(例如512位的所有消息)应该足够(平均).SHA-256接受的输入远远超过512位(实际上,它接受高达18446744073709551615位的输入),因此看起来很可能 SHA-256是满射的.
然而,尚未证明SHA-256是完全的,这是预期的.如上所示,随机预言的一种主观性证据需要大量的计算能力,远远超过诸如预图像(2 ^ n)和冲突(2 ^(n/2))之类的攻击.因此,良好的散列函数"不应该"允许实际证明诸如主观性之类的属性.这将是非常可疑的:哈希函数的安全性源于其内部结构的难以处理性,并且这种难以处理的行为应该坚决反对任何数学分析的尝试.
因此,对于任何有利的散列函数,都没有正式证明了主观性,甚至对于诸如MD4之类的"破坏"散列函数也没有.它只是"高度怀疑"(一个输入比输出长得多的随机预言应该是暴露的).