散列真的是一个不可逆转的过程吗？

Question

我一直在使用哈希和 RSA（在非常肤浅的层面上，例如：SSH 连接上的 RSA 身份验证），我想了解更多相关信息。

首先，我知道加密是一个可以恢复的双向过程。散列是一种不可逆转的单向过程。

最后一点对我来说没有意义，如果我使用算法来散列“你好”，不会是相同的算法，而是“反转”（意思是，它“向后”工作），能够转换该散列再次“你好”。

编辑：

感谢 @GeorgDangl、@klutt 和 Pete Kirkham 指出我根本不理解“不可逆数学”的概念。这些例子真的很有帮助。

Answer 1

从某种意义上说，这是不可逆的，对于每个输入，您只有一个输出，而不是相反。有多个输入产生相同的输出。

对于任何给定的输入，有很多（实际上是无限的）不同的输入会产生相同的哈希值。这很容易实现，因为输出具有固定大小，但输入没有大小限制。

为了实现这一点，使用了不可逆的数学。例如，很容易计算10%3。答案很简单10%3=1。但是如果我给你这个等式x%3=1，你会怎么做？这个等式对所有人都成立x=3*k+1。因此，您无法获得我开始使用的数字。

不可逆数学的另一个例子是正弦和余弦。例如，cos(0)=1，但有更多的输入值计算为 1。实际上，cos(n*2pi)=1。这些函数有“逆”，但它们要么给出一定范围内的答案，要么给出多值答案。第三个例子是x²=1。对于x=1和都是如此x=-1。但是，在此示例中，您得到的可能答案数量有限（而且相当少）。

在处理加密时，可以说私钥用于选择正确的解决方案。您总是可以非常轻松地解密加密消息，但您会得到大量可能的答案。密钥用于找到正确的密钥，而不是实际解密。

另一件值得一提的事情是，一个好的散列算法可以最小化冲突，即两个输入生成相同的散列。此外，当涉及到密码学时，您希望它尽可能难以逆转。但这也伴随着算法是 CPU 密集型的成本。

一个非常基本且不安全的哈希算法可能如下所示：

hash = 0
for each byte in input:
    hash = hash + byte

在这里，我假设这hash是一个简单的整数变量，当它达到最大值时会环绕。该算法易于实现，而且速度很快。但是如果安全很重要，你就不想使用它。修改文件通常很容易，这样哈希检查就不会检测到它。

真正的加密哈希算法力求实现这样的特性：如果您更改输入中的任何一位，则输出中的每一位都有 50% 的机会翻转。此外，如果您翻转输入中的两位，则输出中翻转的位将与如果您只是一位一位更改位将翻转的位完全无关。

我在这个主题上找到了一个很好的 YouTube 视频：https : //www.youtube.com/watch?v=yoMOAIzBSpY

Answer 2

简单的例子 - 假设对于我们的不可逆函数，我们采用输入的数字并返回模 7 的值。

   hash( 0) => 0
   hash( 1) => 1
   hash( 2) => 2
   hash( 3) => 3
   hash( 4) => 4
   hash( 5) => 5
   hash( 6) => 6
   hash( 7) => 0
   hash( 8) => 1
   hash( 9) => 2
   hash(10) => 3
   hash(12) => 4
   hash(13) => 5
   hash(14) => 6

因此，如果哈希值为 6，您不知道输入是 6、还是 14，还是 6 + 7 * N 的任何值，其中 N 是整数。