单向散列函数如何工作？ [英] How do one-way hash functions work?

问题描述

我阅读了关于md5哈希的维基百科文章，但是我仍然无法理解哈希无法重构回原文。

I read the Wikipedia article about md5 hashes but I still can't understand how a hash can't be "reconstituted" back to the original text.

可以有人向有关密码学知之甚少的人解释一下它是如何工作的？

Could someone explain to someone who knows very little about cryptography how this works? What part of the function makes it one-way?

推荐答案

由于每个人到现在都只是定义了一个哈希函数，所以我将会咬住。

Since everyone until now has simply defined what a hash function was, I will bite.

单向函数不仅仅是一个散列函数 - 一个失去信息的函数，而是一个函数 f ，给定图像 y （现有答案中为SE或294），很难找到前图像x，使 f（x）= y 。

A one-way function is not just a hash function -- a function that loses information -- but a function f for which, given an image y ("SE" or 294 in existing answers), it is difficult to find a pre-image x such that f(x)=y.

这就是为什么他们被称为单向的：你可以计算一个图像，但你找不到给定图像的前图像。

This is why they are called one-way: you can compute an image but you can't find a pre-image for a given image.

现有答案中直到现在提供的普通哈希函数都没有此属性。它们都不是单向加密散列函数。例如，给定SE，你可以轻松地拿出输入SXXXE，一个输入与X编码（SXXXE）= SE的属性。

None of the ordinary hash function proposed until now in existing answers have this property. None of them are one-way cryptographic hash functions. For instance, given "SE", you can easily pick up the input "SXXXE", an input with the property that X-encode("SXXXE")=SE.

没有简单的单向功能。他们必须混合他们的输入，以便不仅您不输出输出，但，您也不会识别另一个输入。

There are no "simple" one-way functions. They have to mix their inputs so well that not only you don't recognize the input at all in the output, but you don't recognize another input either.

SHA-1和MD5曾经是流行的单向功能，但它们几乎已经破裂（专家知道如何为给定图像创建预图像，或几乎能够这样做）。还有一个比赛正在进行中，选择一个新的标准赛，将被命名为 SHA- 3 。

SHA-1 and MD5 used to be popular one-way functions but they are both nearly broken (specialist know how to create pre-images for given images, or are nearly able to do so). There is a contest underway to choose a new standard one, which will be named SHA-3.

反转单向函数的一个明显方法是计算许多图像，并将它们保留在与每个图像相关联的表中，形成了它。为了在实践中不可能，所有的单向函数都有很大的输出，至少64位，但是可能要大得多（直到512位）。

An obvious approach to invert a one-way function would be to compute many images and keep them in a table associating to each image the pre-image that produced it. To make this impossible in practice, all one-way function have a large output, at least 64 bits but possibly much larger (up to, say, 512 bits).

编辑：大多数加密散列函数的工作原理如何？

How do most cryptographic hash functions work?

通常，他们的核心是一个单一的功能，可以对一个位进行复杂的转换（a 块密码）。该函数应该几乎是双射的（它不应该将太多的序列映射到同一个图像，因为这将导致以后的缺陷），但它不一定是双射的。这个函数被迭代了一个固定的次数，足以使输入（或任何可能的输入）不可能被识别。

Usually they have at their core a single function that does complicated transformations on a block of bits (a block cipher). The function should be nearly bijective (it shouldn't map too many sequences to the same image, because that would cause weaknesses later) but it doesn't have to be exactly bijective. And this function is iterated a fixed number of times, enough to make the input (or any possible input) impossible to recognize.

以 Skein ，SHA-3语境的强有力的候选人之一。其核心功能重复72次。函数的创建者知道如何有时将输出与某些输入相关联的唯一迭代次数为25.他们认为安全系数为2.9。

Take the example of Skein, one of the strong candidates for the SHA-3 context. Its core function is iterated 72 times. The only number of iterations for which the creators of the function know how to sometimes relate the outputs to some inputs is 25. They say it has a "safety factor" of 2.9.

这篇关于单向散列函数如何工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！