1.1. Cryptographic Hash Function.加密哈希函数

1 2	`这里的不存在不是真的不存在，而是nobody can` `find，没有人能找到。哈希的输出是固定的长度，那么输出空间就是有限的。然而输入是可以任意长度的，那么输入的空间就是无限的。` `既然输出空间（有限）小于输入空间（无限），一定存在某些不同的输入经过哈希映射的输出是一样的。`

哈希的碰撞性一定存在

学新通

1	`FIGURE 1.2. Inevitability of collisions. Because the number of inputs exceeds the number of outputs, <br>we are guaranteed that there must be at least one output to` `which` `the` `hash` `function` `maps` `more` `than one input.`

#为什么一定能找到哈希碰撞呢？举个例子，哈希函数H1的输出长度是256-bit，那么输出就有2256个可能y1,y2...y2^256。假设挑选2256 1个不同的输入x1,x2, ...x2^256 1 ，那么一定存在某些x的输出一样。

这种方法保证了一定能找到哈希碰撞。

如果每次随即输入，那么尝试2130 1个输入时，有99.8%的可能找到哈希碰撞。怎么算的？参考生日悖论birthday paradox。

找到哈希碰撞的难度性

针对输出为256-bit的哈希函数，找到哈希碰撞平均需要2128次，最坏的情况就是2256 1次（参考上文#红色字体部分）。这种计算方法十分费时，书中给出了目前的计算机想找到哈希碰撞有多费力：

1	`如果一台计算机每秒计算10000个哈希，那么计算2128个哈希将需要超过1亿（1027）年！<br>从另一个角度来看，我们可以说，如果人类制造的每一台计算机都从宇宙开始就开始计算，那么他们现在发现碰撞的可能性仍然是极小的。<br>如此之小，以至于地球在接下来的两秒钟内被一颗巨大流星摧毁的几率都远远小于此。`

不过尽管通用哈希碰撞检测算法不可行，但是仍然存在一些哈希函数，输出空间很大，但是找到碰撞却很容易：

H(x)= x mod 2256

这个函数满足了，输入可以为任意长度的任意输入，输出是固定size的256 bits。但是这个函数很容易找到碰撞，比如 3 and 3 2256。

然而其他函数，我们并不能知道是否有这样找到碰撞的方法。

我们在实践中所使用的的加密哈希函数都是人们已经非常努力地寻找冲突但尚未成功的函数。所以我们选择相信这些函数是抗碰撞的。

应用

通过比较两个大文本即网络文件和本地文件的哈希值，来验证二者是否相同。

(2) hiding隐藏性

定义

隐藏性（Hiding）或者叫做单向性（one-way）

书中原话： The hiding property asserts that if we’re given the output of the hash function y = H(x), there’s no feasible way to figure out what the input, x, was.

我的理解：已知加密哈希函数H，给定H（X），不可能找出X。

如果H（x）=x，那么这个函数不满足Hiding。已知H（x）=3，那么我们一定可以推算出x=3.

怎么能让这种“简单”得哈希函数也满足Hiding呢？

Hiding 哈希函数

一个方法是改造这个哈希函数H。H（x）——>H（r || x）

书中原话：Hiding. A hash function H is said to be hiding if when a secret value r is chosen from a probability distribution that has high min-entropy, then, given H(r ‖ x), it is infeasible to find x.

其中“||”符号标识连接（concatenation），r表示一个从高阶最小熵（ high min-entropy）的概率分布中选的一个值。

在信息理论中，min-entropy是度量一个结果的可预测性（how predictable an outcome is）。

high min-entropy指的是，任何一个值出现的概率都是一样小，没办法预测。

1 2	`一个简单的理解，如果我让你从1-5中，任意选一个值k，那就是low min-entropy分布;` `如果我让你从1-100000000000000000中，任意选一个值k,那就是high min-entropy分布。`

（3）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 min-entropy, then it is infeasible to find x such that H(k ‖ x) = y in time significantly less than 2n .

有点难理解，直接网上找到两个比较直白的解释：

1	`1、就是说看x不知道H（x）是什么？这个无法从输入数据，判断到底输出是什么样子。就是说，知道输入的信息，无法一眼看出来输出的hash值是什么，谜题友好性值得就是这一点：你无法通过控制输入值x来获得想要的输出值H（x）`

2、除了通过使用hash函数去计算hash的值，没有其他什么方法能让你仅仅通过输入的数据判断出它的hash值是怎么样的。举个例子假设为256比特位的hash结果，现在需要的是前k位为0的hash的结果，除了去一个个试探每个输入值的hash结果判断结果是否满足这个特征之外没有其他有效的办法能让你直接看出哪个输入会有这样的hash输出。这个特性有什么作用呢？它主要体现在它是比特币挖矿过程工作量证明的基础。常说的比特币挖矿的过程，其实就是求解一个长随机数n，这个n和区块链中的区块的块头组成输入信息x，使x的hash值h(x)落在某个指定的范围内。由于puzzle friendly的原因，只能通过一个个遍历输入的方式去寻找这个n而没有其他捷径寻找到这个随机数n，而这个寻找随机数的过程就是工作量的证明。

我的理解：根据书中描述，Y（哈希的输出的集合）的size决定了puzzle（达到迷惑性的难度）。如果Y是n-bits的所有string，那么达到puzzle很简单；如果Y只包含一个值，那么puzzle非常难（达到迷惑性很难）。

SHA-256

Merkle-Damgård transform ：

学新通

SHA-256使用Merkle Damgård变换将固定长度的抗碰撞压缩函数转换为接受任意长度输入的哈希函数。

哈希函数的输入可以是任意大小，将它分为多个长度为m–n的块。c：compression function，输入是(m-n) n=768，输出是256。每个块的长度是512。

这篇好文章是转载于：学新通技术网

1.1. Cryptographic Hash Function.加密哈希函数