单向哈希函数如何工作? (已编辑) [英] How do one-way hash functions work? (Edited)

问题描述

我阅读了Wikipedia上有关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)，很难找到像f(x)=y这样的原像x.

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-encode("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?

通常，它们的核心是单个功能，该功能可以对一块位进行复杂的转换(分组密码).该函数应该几乎是双射的(它不应将太多序列映射到同一张图像，因为那样会在以后导致弱点)，但是它不必是完全双射的.而且此功能会重复执行固定的次数，足以使输入(或任何可能的输入)无法识别.

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屋！