密码散列函数的属性 [英] properties of a cryptographic hash function

问题描述

在比特币课程第一周的讲座中，我们讨论了密码散列函数的三个属性：

防碰撞：散列函数如果找到两个值x和y，使得x！= y，但H（x）= H（y），则H被认为是抗碰撞的。

隐藏：在以下情况下，哈希函数H隐藏：如果从具有高熵的概率分布中选择秘密值r，则给定H（r‖x），找到x是不可行的。 ‖表示串联两个字符串。

益智游戏。如果对于每个可能的n位输出值y，如果k从高熵分布中选择k，则散列函数H被认为是难以解开的，那么找到x使得H（k‖x）= y是不可行的在时间上显着小于2 ^ n。

拼图友情似乎是一个更详细的隐藏描述。 2之间有什么显着差异？有没有散列函数与属性1，但不是两个？

解决方案

我有同样的想法，差异确实很微妙。我不得不考虑这一点。

假设你有一个散列BadHash。你选择x'和随机数r'，计算y'= BadHash（r'| x'），并给我y'。事实证明，如果x'是UTF8编码的英文文本，我可以告诉你x是什么，（尽管不是绝对必要），我甚至可以告诉你r'。如果x'碰巧只是一个随机比特串，那么我会很失败。但无论如何，这显然不是一个隐藏的散列。

现在这个难题：我给你一个值Y'和一个随机选择的值R'（比如说11110011 ... 100），并且让你找到一个x使得BadHash（R'| x）= Y'。好消息：事实证明，Y'= BadHash（00101 ... 0001 | UTF8（比特币是通货紧缩））。因此，因为BadHash是非隐藏的（加号），所以可以确定一个R（即00101 ... 0001）和x（即UTF8（比特币是通货紧缩）），这样BadHash（R | x）= Y '但是这对你没有帮助，因为这个谜题指出你需要一个与不同的R一起工作的x，即11110011 ... 100。所以你还没有解决这个难题。

然后你会发现这两个属性并不相同。至于是否有一个属性存在哈希值，而不是另一个 - 我不知道。

In the week 1 lecture of the bitcoin coursera course, there is a discussion of the 3 properties of a cryptographic hash functions:

Collision-resistance: A hash function H is said to be collision resistant if it is infeasible to find two values, x and y , such that x != y , yet H(x)= H(y).

Hiding: A hash function H is hiding if: when a secret value r is chosen from a probability distribution that has high entropy, then given H(r ‖ x) it is infeasible to find x. ‖ means concatenation of two strings.

Puzzle friendliness. A hash function H is said to be puzzle-friendly if for every possible n-bit output value y , if k is chosen from a distribution with high entropy, then it is infeasible to find x such that H(k ‖ x) = y in time significantly less than 2^n.

Puzzle friendliness seems to be a more detailed description of hiding. Is there any significant differences between the 2? Are there hash functions with 1 of the properties but not both?

解决方案

I had the same thought, and the difference is indeed subtle. I had to think about this awhile.

Suppose you had a hash, BadHash. You pick x' and a random nonce r', compute y' = BadHash(r'|x'), and give me y'. It turns out that if x' is UTF8-encoded English text, I am able to tell you what x' was, and (though not strictly necessary), I can even tell you r'. If x' happened to be just a random bit-string, I'd be out of luck. But no matter, this is clearly not a hiding hash.

Now the puzzle: I give you a value Y', and a randomly chosen value R' (say "11110011...100"), and ask you to find an x such that BadHash(R'|x) = Y'. Good news: it turns out that Y'= BadHash(00101...0001 | UTF8("Bitcoin is deflationary")). So because BadHash is non-hiding (plus), you can determine an R (namely 00101...0001), and and x (namely UTF8("Bitcoin is deflationary")), such that BadHash(R|x) = Y' But this doesn't help you, because the puzzle specified that you need an x that works with a different R, namely "11110011...100". So you haven't solved the puzzle.

You see, then, that the two properties aren't equivalent. As to whether there are indeed hashes with one property but not the other -- that I don't know.

这篇关于密码散列函数的属性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！