《BITCOIN AND CRYPTOCURRENCY TECHNOLOGIES》Chapter 1系列
1.1. Cryptographic Hash Function.加密哈希函数
目录
1.1. Cryptographic Hash Function.加密哈希函数
哈希函数的三个性质：
1 2 3 |
|
加密哈希函数比普通哈希函数多了三个性质：(1) collision resistance, (2) hiding, and (3) puzzle friendliness.
（1）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).
我的理解：不存在两个不同的输入通过哈希函数得到相同的输出。如果两个输入x 不等于 y，那么 H(x) ≠ H(y)。
1 2 |
|
哈希的碰撞性一定存在
1 |
|
#为什么一定能找到哈希碰撞呢？举个例子，哈希函数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 |
|
不过尽管通用哈希碰撞检测算法不可行，但是仍然存在一些哈希函数，输出空间很大，但是找到碰撞却很容易：
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 |
|
（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 |
|
我的理解：根据书中描述，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。