algorithm - 一种方法如何散列？

Question

我想知道，一种方法如何散列？你怎么能只在一个方向而不是另一个方向编码一个字符串？如果你把算法倒过来，你就不能解码像md5这样的东西吗？之前，对我来说，唯一可能的方法是让它生成一个随机答案，而不是使用算法。但它每次都以相同的方式散列。请给我解释一下。

Answer 1

如果您“反转”算法，则无法取回原始字符串，因为可能的字符串多于可能的哈希码。

考虑一种算法，其结果为 64 位整数。有 2^64 = (2^8)^8 = 256^8 个可能的数字。

但这意味着，如果有超过 256^8 个可能的字符串，那么必须有两个字符串哈希到相同的值（这称为鸽巢原理）。由于长度为 9 的字符串更多（256^9 个这样的字符串），因此您可以获得哈希值这一事实并不能保证您可以“返回”。

Answer 2

一方面，MD5 摘要（通常）比消息短得多，因此许多消息可能会生成相同的摘要。另一方面，对消息的任何微小更改都会产生完全不同的摘要。因此，可以快速判断摘要是否对应并给定消息，但是没有反向算法可以将摘要转换为合理的消息。

Answer 3

在散列的情况下，正如其他人所指出的那样，不可逆性仅仅来自于数十亿的输入都散列到相同的输出这一事实，因此即使原则上也无法逆转。

但是您的问题似乎暗示您想知道即使在 1 对 1 的情况下，如何也有可能具有确定性但不可逆的转换过程，这确实是可能的。例如，标准块加密。明文从一组位转换为相同大小的不同位组（密文）。这是完全可逆的，但是加密和解密都需要额外的信息——一个由发送者和接收者共享的“密钥”值，但没有其他人共享。因此，转换是不可逆的，只是因为密钥是秘密的——如果攻击者得到了密钥，他也得到了消息。

公钥加密是另一个完整的蜡球。在这种情况下，“活板门”来自这样一个事实，即某些操作虽然原则上是可逆的，但在一个方向上比在另一个方向上更难执行。例如，如果你有两个非常大的素数，你可以以毫秒为单位将它们相乘；但如果只给你产品，要花几个世纪才能发现主要因素。因此，如果您知道这两个因素，则可以根据它们计算两个单独的“键”，其中一个是另一个的倒数。如果你只给发送者一个密钥，他不能在不知道因素的情况下计算另一个，但他可以使用您给他的密钥加密消息，只有您可以解密。这使得它更安全——你可以通过简单地在你的网页上发布它来给他密钥，只要你对自己的反向私钥保密，没有人可以解密消息。

Answer 4

逆转不是不可能，只是不切实际。

散列从输入中删除信息：有无限多的字符串，但只有有限数量的散列。许多哈希对应于无限数量的字符串，因此通常不可能进行 1 对 1 的反转。但这并不意味着您不能生成一组匹配的输入。

如果您尝试反转像 md5 这样的散列算法，您很快就会发现算法的每个步骤都有多个中间值对应于该步骤产生的输出，或者不可能产生输出，因此您在一些点，不得不回溯。检查每个组合将花费很长时间。