为什么哈希函数是一种方法？如果我知道算法，为什么不能从中计算输入？

#1 楼

让我发明一个简单的“密码哈希算法”，向您展示其工作原理。与该线程中的其他示例不同，如果您可以承受一些奇怪的密码限制，那么该示例实际上是可行的。您的密码是两个大质数，x和y。例如：

x = 48112959837082048697
y = 54673257461630679457

您可以轻松编写一个计算机程序来计算O（N ^ 2）时间中的xy，其中N是x和y中的位数。 。 （基本上，如果数字是两倍，则需要四倍的时间。虽然算法更快，但这无关紧要。）将xy存储在密码数据库中。

x*y = 2630492240413883318777134293253671517529

< br五年级的孩子，给了足够的便条纸，就可以找出答案。但是你如何扭转呢？人们已经设计出许多用于分解大数的算法，但是与将x乘以y的速度相比，即使最好的算法也很慢。除非数字很小（例如，x = 3，y = 5），否则五年级学生都无法执行这些算法。

这是关键特性：计算简单得多前进比倒退。对于许多问题，您必须发明一种全新的算法来逆向计算。

与单射或双射函数无关。破解密码时，获取相同的密码或具有相同哈希的其他密码通常并不重要。哈希函数经过精心设计，因此即使是具有相同哈希值的不同密码，也很难将其反转并获得任何答案。用加密的话来说：容易受到原像攻击的哈希函数毫无价值。 （上面的密码散列算法是单射，如果你有一个规则，X
密码学专家做什么？有时，他们试图找出新的算法来反转哈希函数（前映像）。他们完全按照您说的去做：分析算法并尝试将其逆转。某些算法以前已经被颠倒，而其他算法则没有。

读者专用：密码数据库包含以下条目：

3521851118865011044136429217528930691441965435121409905222808922963363310303627

密码是什么？ （实际上，对于计算机而言，这并不算太难。）

脚注：由于人们在实践中选择的密码数量很少，因此良好的密码散列不仅难以向后计算，而且还可以节省时间-耗费大量时间来计算转发次数，以减慢字典攻击速度。作为另一层保护，随机加盐可以防止使用预先计算的攻击表（例如“彩虹表”）。

脚注2：我们如何知道很难逆转哈希函数？不幸的是，我们没有。我们只是不知道任何简单的方法来反转哈希函数。使得哈希函数难以逆转是哈希函数设计的圣杯，并且尚未实现（也许永远不会发生）。

评论

---

好吧，那么告诉我您给我做的运动的答案吗？我不知道如何解决这个问题，我会怎么做？什么是内射和双射？

–马克
2012年2月16日在1:05

---

@DietrichEpp您能否在答案中加上大多数加密哈希函数实际上使用简单的操作（例如加，和，或异或，旋转，mod进行哈希而不是质数）？ （只是为了使其更清楚）

–JoãoPortela
2012年2月16日在10:27

---

@Mucker：显然，这是1451730470513713778492236629598992166035067 x 2425967623052370772757633156976982469681（实际上，在单个3GHz内核上使用SIQS方法花费了大约10分钟的CPU时间。）

– jimbob博士
2012-02-16 19:21

---

我想补充一点，哈希也可以压缩。您可以哈希（高熵）x GiB文件并接收160位摘要。信息丢失（即使len（m）
–领带战士
2012年7月17日在15:32

---

@ Tie-fighter：非常非常有损的压缩-正如您所注意到的，丢失的信息量是如此之大，以至于仅出于技术上的意义，我很想补充。

– Piskvor离开了建筑物
2012年7月17日在15:39

---

#2 楼

现在，这是个好问题。

我们必须首先给出一个精度：许多单向函数，特别是密码学中常用的哈希函数，接受来自比该空间大得多的空间的输入输出值。例如，为输入定义SHA-256，输入最多为18446744073709551615位。有218446744073709551616-1可能的输入，但是由于输出始终是256位的序列，因此SHA-256仅有2256个可能的输出。某些不同的输入必然会产生相同的输出。因此，对于SHA-256的给定输出，不可能明确地恢复所使用的输入，但是有可能计算出产生给定输出值的输入。像前电阻就是这样：很难找到与输出匹配的输入（无论如何首先获得输出）。

所以我们谈论的是每个人都可以在任何函数上计算的函数输入（使用公开程序，不涉及秘密价值-我们不是在谈论加密）。


学者怎么说

目前尚不清楚-way函数实际上可以存在。现在，我们有许多功能，没人知道如何求逆。但这并不意味着从数学意义上讲它们不可能反转。但是请注意，尚未证明单向功能不存在，因此希望仍然存在。有人怀疑单向函数是否存在可能是这些令人讨厌的数学断言之一，既不能证明也不能反证（哥德尔定理证明这类事物必须存在）。但是也没有证据。

因此，也没有证据表明任何给定的散列函数确实可以抵抗原像。

有一些功能可以链接到众所周知的难题。例如，如果n是两个大质数的乘积，则函数x⟼x2 mod n难以求反：能够对非素数整数n求模的平方根（一般而言）等同于能够将其分解为n倍，这个问题很难解决。请注意，这并不困难。只有数学家在过去至少2500年中一直尝试有效地分解大整数，尽管取得了一些进展，但是这些聪明的人都没有找到一个真正的杀手级算法。 “ RSA模数”（两个相似长度的随机选择的大素数的乘积）的因式分解世界纪录是一个768位整数。

基于这种“硬问题”的一些哈希函数提议参见例如MASH-1和MASH-2（关于RSA问题）和ECOH（具有椭圆曲线）。这样的功能很少存在，因为：将“难题”转换为安全的哈希函数并不容易；有很多棘手的问题。例如，虽然以非素数n取模的平方根通常很困难，但有些值的平方根提取很容易。
此类哈希函数的性能往往是次优的。就像比常用的SHA-1慢100倍。

建立散列函数的更“标准”方法是将密码学家聚集在一起，让他们于某些建议的设计。然后，在密码分析尝试中存活了几年的功能被认为“可能很健壮”。 SHA-3竞赛就是这样的努力；获奖者应在今年晚些时候宣布。在51位候选人（成功完成行政程序的候选人）中，有14位被保留参加“第2轮”活动，而这14位候选人已经被许多密码学家相对仔细地研究过，他们之中没有人发现真正值得一提的功能。该列表已减少到5，不久将进一步减少到1，但这不是出于安全原因（大多数实际数据是关于性能，而不是阻力）。


使得MD5难以反转

由于我们不知道如何证明某个函数很难反转，因此我们能做的最好的就是尝试一下特定的函数，从而获得一个功能如何实现其视在电阻的“直觉”。

我选择了众所周知的MD5。是的，MD5被“破坏”了，但这是为了碰撞，而不是原像。存在一种已知的原像攻击，至少从理论上讲，它比通用方式快（“通用方式”是“运气”，即尝试输入直到找到匹配项），因为MD5具有128，因此平均评估成本为2128位输出； Sasaki-Aoki攻击的成本为2123.4，虽然较低，但仍过高而无法实际尝试，因此结果仍是理论上的）。但是MD5相对简单，并且已经经受了相当长一段时间的攻击，因此这是一个有趣的示例。

MD5包含对数据块的“压缩功能”的许多评估。首先填充输入消息，以便其长度变为512位的倍数。然后将其拆分为512位块。将128位运行状态（保存在名为A，B，C和D的四个32位变量中）初始化为常规值，然后使用压缩函数进行处理。压缩功能采用运行状态和一个512位消息块，并将它们混合为运行状态的新值。这样处理完所有消息块后，运行状态的最终值是哈希输出。

因此，让我们集中讨论压缩函数。它的工作原理如下：


输入：运行状态（A B C D）和消息块M。消息块为512位；默认值为512。我们将其分为16个32位字M0，M1，M2，... M15。
输出：新的运行状态值。

处理：


将当前状态保存在一些变量中：A→A'，B→B'，C→C'和D→D'

进行64个如下所示的回合：

计算T = B +（（A + fi（B，C，D）+ Mk + Xi）<<< si）。内容如下：我们在B，C和D上计算给定的函数fi（一个简单的按位函数，它取决于整数i）。在A的值上加上一个消息字Mk和一个常数Xi（加法以模232完成）。将结果向左旋转一些位（移位量也取决于回合）。最后，添加B：结果为T。
旋转状态字：D→A，C→D，B→C，T→B。


添加保存的状态值到当前状态变量：A + A'→A，B + B'→B，C + C'→C，D + D'→D。



重要的是，有64个回合，但只有16个消息词。这意味着每个消息词都会进入处理四次。我用黑体写这是因为这是中心点。对原像的抵抗来自于这一特征。 MD5规范（RFC 1321）中描述了在每个回合中使用哪个消息字。该规范还描述了函数fi，旋转计数si和32位常数Xi。现在，假设您正在尝试“反转” MD5；您可以从输出开始，然后逐步提高压缩功能。首先，您必须确定第64轮的输出。确实，压缩函数的输出是第64轮的输出与保存状态（A'B'C'D'值）的总和。您都没有，因此必须选择。您的希望是，您将能够找到消息单词的值，从而使您能够在第1轮的输入中获得一些与您对A'及其兄弟的任意决定相一致的值。

让我们看看向后移动压缩功能时的外观。您有一个回合的输出（该回合之后的变量A，B，C和D），并且您想重新计算该回合的输入。您已经知道B，C和D的先前值，但是对于A和Mk，您有很多选择：A可以使用每个32位值，并且每个都有一个对应的Mk。首先，您对此感到高兴；谁会拒绝这种自由？只需选择一个随机Mk，这只需进行几次操作即可产生对应的A（尝试一下！）。

但是在您以这种方式反转了16轮后（由于您是在向后工作，因此从第49轮到第64轮），自由消失了。您已经“选择”了所有消息词的值。尝试反转第48轮时，您想在该轮之前重新计算A的值；根据MD5规范，在第48轮中使用了消息字M2，并且您已经选择了M2的值（在第63轮取反时）。因此，A仅有一个选择。那么，您会说什么。一种选择足以继续向后走。因此，继续。

现在，您正处于压缩功能的开始。请记住，起初，您对A'B'C'D'的值进行了任意选择：这使您可以计算第64回合的输出，并开始向后走。现在您已经获得了第1轮的输入，该输入应该与A'B'C'D'...相同，并且不匹配。这是很正常的：您任意选择A'B'C'D'，并且还任意选择了消息词Mk，因此可以预期它在大多数情况下都不会起作用。因此，您可以通过追溯性地更改A'B'C'D'的初始选择或Mk的一个或多个随机选择来修复计算。但是对任何Mk的每次修改都意味着在其他地方进行修改，因为每个Mk被使用了四次。因此，您需要进行其他修改以抵消其他修改，依此类推...

此时，您开始了解反转MD5的问题：每次触摸单个位，都会触发一个整个算法中有很多修改，您需要通过触摸其他位来抵消，并且交互太多。基本上，您同时玩2128个球，这太多了，无法跟踪所有球。

如果每个消息块的长度为2048位，分成64个字，并且每个消息字在MD5中仅使用一次，则可以轻松地将其反转。您可以按照上面的步骤进行操作：任意选择A'B'C'D'，任意选择第64至5轮的消息字；在前四个回合中，您只需考虑要为回合输入获取的值（该值与您对A'，B'，C'或D'的任意选择相匹配）并计算出相应的消息字。非常简单。但是MD5不会按2048位块来处理数据，而是按512位块来处理数据，每个消息字使用了四次。


一些其他的错误

MD5压缩函数的结构实际上是Feistel密码的概括。在Feistel密码中，数据被分为两半，并且对于每一轮，我们通过将数据的一半相加/异或到中间值来更改一半，该中间值由另一半和密钥计算得出；然后我们将两半交换。将此方案扩展为四部分，您将获得与MD5回合相同的结构-旋转90º：MD5看起来像使用消息块作为密钥对当前状态进行加密（并且还额外增加了具有保存状态的第64回合的输出，它与旋转的密码有别于MD5。）

那么也许我们可以从分组密码中构建哈希函数？的确，我们可以做到：那就是漩涡。基于旋转的块密码（消息块是密钥）建立的哈希函数；惠而浦的分组密码是“ W”，它是Rijndael的派生词，通常被称为AES。但是W具有更大的块（512位而不是128位）和重新设计的密钥计划。

当您从旋转的分组密码中生成哈希函数时，对哈希函数的前映像攻击在某种程度上等同于对分组密码的密钥重建攻击；因此有人希望，如果分组密码是安全的，那么散列函数也是安全的。再次，那里有肮脏的细节。同样，对于这种结构，散列函数上的冲突就像对块密码的相关密钥攻击一样。相关密钥攻击通常被认为是非致命性的，并且经常被忽略（例如，它们不是AES竞争评估标准的一部分，并且Rijndael在这方面被认为有些脆弱，这就是W具有全新密钥的原因时间表）。

一些较新的设计是基于不旋转的块密码构建的，因此可以从块密码的安全性中更直接地得出哈希函数的安全性；例如，参见SHA-3候选Skein，它是在称为Threefish的分组密码上定义的。

相反，人们可以尝试从哈希函数中生成分组密码。例如参见SHACAL，它是SHA-1“竖立”。而且，据提示，SHACAL具有一些与关键点相关的弱点，这些弱点与SHA-1在冲突方面的已知弱点非常相似（没有计算实际的冲突，但是我们有一种方法应该比该方法快近一百万倍）。通用碰撞发现算法）。

因此，与我在本文开头介绍的内容相反，我们一直在谈论加密。关于散列函数和对称加密之间的链接，还有很多要发现和研究。


TL; DR：此消息没有TL; DR。完整阅读或阅读。

#3 楼

回答这个问题的第一步是看到示例，例如@Dietrich的示例，这些示例在一个方向上比在逆方向上运行困难得多，并且抵制了许多寻求速度突破的尝试。但是问题很复杂，因此我将尝试使其更加充实。

很多人似乎陷入了陷阱（heh），认为哈希函数实际上在某种程度上是神奇的-它们实际上是绝对的“单向函数”，在数学上根本无法向后运行，因为它们被称为哈希。在安全论坛中考虑这不是一种健康的方法。在实践中这通常是错误的。考虑到函数从域到图像的映射的基本数学定义，从理论上讲，这总是错误的。

原则上所有哈希都可以逆转。它可能是杂乱无章的（就像在蛮力中一样），对于当今的硬件来说，它可能花费不切实际的长时间，甚至可能长期维持下去，但是从数学上来说，这只是时间问题。正如@mucker指出的那样，所有信息都可以在其中找到原始密码（或至少有效的密码）。如果我们忘记了这一点，那么我们就忘记了巧妙地试探性地挑选可能的密码的危险，这些密码经常成为新闻。散列是一个工程问题，而主要的挑战是效率问题-如何在给定散列的情况下使密码查找变得昂贵。这种想法的主要原理之一是使密码散列变慢的重要性。

哈希的科学和数学只是在逐渐变好。确实没有任何证据证明任何哈希值真的很难。
@迪特里希的回答是说明理想的散列函数可能是可能的一种很好的方式。但是，只需看看描述我们如何没有最佳加密算法证明的真正专家：对称密码和摘要算法的安全性声明背后的数学模型是什么？

LanMan的事实在问题中被引用的还有更多证据表明我们需要避免理想化哈希。的LanMan是什么，但一个理想的散列函数，很容易被有些分析的组合，并迫使有点蛮力击败。有关恐怖的散列函数的另一个流行示例，请参见MySQL OLD_PASSWORD cryptanalysis?。

因此，让自己摆脱陷阱-陷入困境不必单程。认识到散列是可逆的，并在寻找最佳方式将其可信时保持可信赖的安全思想。这通常是找到真正难以逆转的最佳方法。我并没有尝试对最佳实践（例如bcrypt或PBKDF2或scrypt）进行撒谎。但是有明显的证据表明，即使是优秀的程序员也经常会出错。
所以请谨慎使用它们，不要试图发明自己的东西。

#4 楼

因为这就是加密哈希函数的工作方式，所以它们是单向（从普通到哈希）数学函数。专门设计并测试了算法来避免这种情况，并避免冲突（2种不同的纯文本生成相同的哈希值）。
您可以在Wikipedia上阅读更多内容，但本文的重点是：
<理想的加密哈希函数具有四个主要或重要属性：

很容易（但不一定很快）为任何给定消息计算哈希值
不可行具有给定哈希值的消息
在不更改哈希值的情况下修改消息是不可行的
找到具有相同哈希值的两条不同消息是不可行的


对散列函数的大多数攻击都基于发现冲突（因此2个不同的纯文本将匹配相同的散列）或预先生成数百万个散列并进行比较，直到找到生成散列的平原为止。
：如果哈希算法可逆向工程或可以被这种方式攻击，则它不是一个好的哈希算法。
对于密码，请输入使用BCrypt煽动，这篇文章中有很多信息。

#5 楼

想象一下使用散列使用单个位的散列函数。因此您的哈希可以为0或1。

我们说哈希函数将数据的每个字节加起来，如果数据为偶数，则哈希值为0。如果数据为奇数，则哈希为1。

您知道为什么无法通过反向工程该哈希函数来恢复数据吗？

实际哈希算法相同，只有公式

您的困难可能是您正在考虑将哈希用于密码。尚不清楚为什么不能从128位哈希中恢复8个字符的密码。但是，用于密码的哈希函数也可以用于计算整个TB数据的哈希，并且哈希仍将仅占用128位数据。显然，您无法对该128位哈希进行反向工程并恢复您的TB数据。

此外，假设您可能对单个TB数据进行了各种排列，那么会有大量不同的数据生成相同的哈希。毕竟，如果您有超过2 ^ 127个不同的数据置换，您很可能会遇到具有相同哈希值的两个不同数据。

#6 楼

有些算法本质上是不可逆的。它们将输入A转换为输出B，即使您知道算法的确切步骤，也无法从B恢复A。

一个非常简单的示例：转换每个字符在密码中输入其ASCII值，然后将所有值相加。无法从结果中恢复原始密码。

#7 楼

问题的一个方面是，先前的答案中缺少人们。这就是哈希函数的多对一性质。由于（大多数）散列函数是固定长度的输出（例如256位），因此从技术上讲，有无限多的字符串都被散列为相同的值。

例如，如果您采用全部512位字符串（其中有2 ^ 512）。哈希函数只有2 ^ 256个输出。因此，对于散列函数的每个输出，大约有2 ^ 256 512位字符串散列到该值。我之所以这么说，是因为我们不知道哈希函数实际上是否是随机函数，它可能会有一些偏差。

因此，给定摘要，有很多字符串哈希为相同值。因此，如果您在输出用户密码时定义了“反向哈希函数”，那么反向函数将如何处理可能导致给定摘要产生的无数个字符串？

#8 楼

您在问“为什么散列函数是单向的为什么很重要？”这是一种安全属性。

当今普遍使用两种“哈希”（或称“消息摘要”）。一种是普通的消息摘要，您可能会熟悉它作为一种校验和算法，例如CRC32。该算法经过设计，使输入中的单个位更改将产生不同的摘要值。这样做的主要目的是确保消息不会被意外破坏。 CRC32校验和出现在每个TCP / IP数据包上，并且不匹配会导致重新传输以更正错误。

消息摘要通常在密码术中用作“签名”消息的一部分。邮件由发件人使用其私钥加密，任何人都可以使用公钥来验证邮件仅由发件人加密。但是RSA公钥加密只能加密小于密钥大小（256字节）的消息，该消息比大多数有用的消息短得多。消息摘要算法产生的值小于RSA密钥。因此，通过加密摘要而不是消息，可以在任何大小的消息上使用RSA签名。

但是普通的消息摘要对于攻击者而言并不安全。考虑一个非常简单的校验和，它仅将字符的值求和。如果您签署了这样的校验和，我可以交换产生相同校验和的任何其他消息，并且签名将匹配，从而欺骗受害者。

消息摘要的另一种常用用法是存储期间的密码保护。如果在将密码存储到系统中之前对其进行加密，则知道密钥的系统管理员可以将其全部解密。 （最近，当某些网站被黑客入侵时，您可能已经注意到了这个问题。）

为了避免这些问题，需要使用另一种哈希，即“加密安全”的哈希。安全哈希算法具有两个附加属性，即抗冲突性和不可逆性。

抗冲突性意味着我不应该找到产生相同摘要的消息。这样一来，我就无法将您的恶意消息换成您的好消息。

非可逆性属性意味着我无法将摘要转换为纯文本，因此无法解密原始消息，就像用户的密码一样。

创建摘要与加密非常相似，因为您必须以不泄漏有关原始数据信息的方式对数据进行加密。这甚至更加困难，因为相同的数学不必提供有关如何成功创建碰撞的任何线索。

#9 楼

其他人已经解释了为什么良好的加密哈希函数难以逆转-但是，根据Wikipedia的这篇文章，LanMan设计欠佳，并且可以相对容易地逆转：


尽管它基于DES，作为一种经过充分研究的分组密码，LM哈希
不是真正的单向函数，因为可以从
哈希中确定密码，因为它的实现存在一些弱点... By
现代台式机分别在每半部分上进行强力攻击，现代的台式机可以在几个小时内破解字母数字LM哈希... 2003年，发布了实现彩虹表技术的Ophcrack。它专门针对LM加密的弱点，并包括足以在几秒钟内破解几乎所有字母数字LM哈希值的预先计算的数据。

#10 楼

我认为有很多原因，但是有一个明显的原因：哈希函数产生的摘要永远不会包含无限信息，因为摘要具有有限的位。但是哈希函数可用于哈希无限信息的输入。输入实际上可以是任何东西。

找出碰撞的困难不是答案。真正的困难是证明原始数据实际上是与特定摘要匹配的唯一可能输入。我认为您可能永远都不会计算一个输入并声称这是摘要的唯一答案。

#11 楼

逆转mod哈希很简单。例如：-（字节累加）mod (d) = hash。因此，如果要生成哈希的所有输入，请问int bytes summatory = int n*int d + int hash
是什么？

Ff是两个简单块之间的XOR，例如，该位为1，即block 1 = 0和block 2 = 1或block 1 = 1和block 2 = 0。说该位是0或(b1=0 ^ b2=0)或(b1=1 ^ b2=1)。这些是相同输出的正确答案。