有效找到H的原像的函数的大小的上限小于H的输出大小，然后这对哈希函数的强度有影响。我们如何证明这样一个有效的原像查找功能必须大于输出大小？
#1 楼
密码散列函数（就像传统计算机所做的所有其他事情一样）可以描述为一组二进制运算，XOR，寄存器旋转和二进制加法非常常见。这些直接转化为经典的计算机科学问题，称为“二进制可满足性”或SAT。SAT问题已被证明是NP-完全的。为了掩盖这个崇高的数学概念的定义，这意味着没有已知的算法可以解决难题，而难题块的数量以描述所需工作量的指数结尾。加密算法会尝试将该指数增加到成千上万。
当然，有许多种方法可以使任何实际功能都存在弱点，从而导致它不会表现出如此糟糕的状态。攻击者的案例问题。但是密码学家已经积累了很多知识，可以评估超出其向外位数的算法的安全性。除最古老的加密功能外，所有其他功能都无法满足当今最好的SAT求解器的要求。
但是P！= NP现在尚未真正得到证明，对吗？ :-)
评论
$ \ begingroup $
+1有趣。您是否建议研究论文使用抗3SAT的证据证明各种哈希函数/密码的强度？
$ \ endgroup $
– Ethan Heilman
2011年8月5日14:38
$ \ begingroup $
当然，例如eprint.iacr.org/2006/254和eprint.iacr.org/2010/285。不过，最有趣的是，对SAT的态度似乎在短短四年内就发生了变化。从（从字面上看）“我们希望SAT求解器能够找到新的应用程序，作为实践密码分析员的验证和测试工具”，到“我们找到了一些简化版本的原像，并证明了完整的功能可以抵抗提出的攻击。”
$ \ endgroup $
–沼泽雷
2011年8月6日在4:23
$ \ begingroup $
这只是说如果SAT很简单（即P = NP），那么所有哈希函数都将被破坏，反之则不行（如果SAT很难，则哈希函数将是好的）。
$ \ endgroup $
–PaŭloEbermann
2011-10-12 22:27
#2 楼
一般的理由是试图“破坏”哈希函数的密码学研究已经进行了数年。据我所知，没有“证据”证明很难找到哈希的原像。仅根据尝试将其反转的努力历史来假定它是困难的。今天认为安全的哈希函数明天可能会变弱。
本文（单向功能和电路复杂性）可能有助于理解电路复杂性和单向功能之间的关系。
评论
$ \ begingroup $
我知道，在特定的数学假设下（如所提供的论文中所述的离散对数问题），在给定的条件下，有些函数很难被求逆。大多数密码哈希函数不使用此类假设，但实际上它们似乎难以逆转。为什么会这样呢？传统知识是否认为某种神秘的单向属性隐藏在异或旋转和GF S盒中？
$ \ endgroup $
– Ethan Heilman
2011年7月12日在20:19
$ \ begingroup $
不同之处更多在于被称为“数学”的基本基元。离散对数问题与哈希函数中涉及的“模糊”问题一样，在数学（IMO）方面也是如此。使用这种模糊安全性的原因（您可能知道）是效率。使用SHA256比使用基于DL的哈希要快得多。
$ \ endgroup $
– Jus12
2011年7月12日在20:29
$ \ begingroup $
“模糊”或“牛仔”密码学的哲学基础是什么，试图解释为什么很难破解。虽然可能没有已知的硬科学理论可以解释为什么SHA2尚未被打破，但在哲学或其他较软的领域中可能会有一些解释。密码学家对SHA2为何提供抗拒尝试的故事有什么故事？
$ \ endgroup $
– Ethan Heilman
2011年7月13日在17:50
$ \ begingroup $
@EthanHeilman我认为混淆和扩散是对称加密（即哈希，分组密码和流密码）的最佳论点。
$ \ endgroup $
–PaŭloEbermann
2011年10月12日在22:31
评论
什么意味着有效的原像查找功能必须大于输出大小？您是在这里指时间复杂度而不是函数的大小吗？@Paulo Ebermann-我的意思是，如果有效的原像查找功能的位数比散列函数的输出大小小，那么人们猜测原像查找功能的速度会比猜测原像的速度更快，从而破坏了散列功能。所谓高效，是指preimage函数在与散列函数生成输出的大致相同的时间内找到preimage（也就是说，preimage函数是hash函数的倒置，而不仅仅是猜测preimage的程序）。 br />
抱歉，我只是不了解函数大小的概念。 （输入）域的大小？输出大小？执行实现所需的时间/空间？
@Paulo Ebermann-描述一个函数所需的最小位数。例如，机器码可用于描述从一组整数到另一组整数的特定映射。给定使用语言L编码的哈希函数H，您是否可以找到另一个函数P，以使P以与H相同的时间/内存复杂度反转H，并且以L编码的P小于H的输出大小（已编码P的描述小于H的输出大小。
@Paulo Ebermann-考虑一个效率较低的函数LP，它实际上是所有$ 2 ^ n $可能的输出到输入的映射。这样的函数可以在O（1）的时间内找到原像，但需要2 ^ n的空间。现在将此映射压缩到小于2 ^ n。因此，对于每个哈希函数H，必须存在一个反相器函数，该函数可以找到比蛮力便宜的原像。所有哈希函数都被“破坏”了，技巧是发现破坏哈希函数的函数。如果这样的原像发现功能太大，则很难用蛮力发现它。