1703864500
特性3:谜题友好
1703864501
1703864502
哈希函数需要的第三个安全特性为谜题友好特性。这一特性较为复杂,我们首先解释该特性的技术要求,然后通过举例来阐释该特性的意义。
1703864503
1703864504
直觉上,谜题友好可以这样解释,如果有一个人想找到y值所对应的输入,假定在输入集合中,有一部分是非常随机的,那么他将非常难以求得y值对应的输入。
1703864505
1703864506
谜题友好 如果对于任意n位输出值y,假定k选自高阶最小熵分布,如果无法找到一个可行的方法,在比2n小很多时间内找到x,保证H(k‖x)=y成立,那么我们称哈希函数H为谜题友好。
1703864507
1703864508
应用:搜索谜题
1703864509
1703864510
现在,让我们试想一个应用以阐释谜题友好特性的意义。在这个应用中,我们将建立一个搜索谜题,该谜题是一个需要对庞大空间进行搜索,才能找到解决办法的数学问题。该搜索谜题没有捷径,也就是说除了搜索庞大的空间来进行求解,别无他法。
1703864511
1703864512
搜索谜题 搜索谜题构成:
1703864513
1703864514
● 一个哈希函数H。
1703864515
1703864516
● 从高阶最小熵分布选出的一个取值,id(我们称其为谜题ID)。
1703864517
1703864518
● 目标集合Y。
1703864519
1703864520
该谜题的解决方法为一个解,x,应该满足以下公式:
1703864521
1703864522
H(id‖x)∈Y
1703864523
1703864524
这个直觉是:如果H有一个n位输出,那么它的可能取值有2n个。解决这个谜题要求找到一个位于集合Y(通常比所有输出值集合小很多)内的输出值,Y的大小决定了谜题的难度。如果Y是所有n位字符串的集合,这个谜题就毫无意义。然而,如果Y只有一个元素,那么这个谜题难度最大,谜题ID取自高阶最小熵分布,这个事实保证了求解无捷径。反过来,如果该ID的确定性很高,那么有人可能会作弊,比如通过使用该ID,事先对谜题进行求解。
1703864525
1703864526
如果一个哈希函数具备谜题友好特性,这就意味着对于这个谜题没有一个解决策略,比只是随机地尝试x取值会更好。因此,如果我们要把谜题做成很难解决是可以的,只要我们能用适合的随机方式生成谜题ID。当我们讨论比特币采矿(是一种搜索谜题)时会采用这一思路。
1703864527
1703864528
安全哈希算法
1703864529
1703864530
我们讨论了哈希函数的三个特性及其相应的应用。现在,让我们讨论本书中将会大量用到的一个哈希函数,安全哈希算法(Secure Hash Algorithm 256,简称SHA-256)。哈希函数有很多,但SHA-256是一个主要被比特币世界采用,并且效果还很不错的哈希函数。
1703864531
1703864532
回想一下,我们要求哈希函数可以用于任意长度输入。幸运的是,只要我们能建立一个用于固定长度输入的哈希函数,然后通过一般方法,就可以将接受固定长度的哈希函数转化为可接受任意长度输入的哈希函数,我们称这个转换过程为MD(Merkle-Damgard)变换,SHA-256是采用这种变换方法的常用哈希函数之一。在通用术语中,这种基础型,可用于固定长度,具备碰撞阻力的哈希函数被称为是压缩函数(compression function)。经过验证,如果基本压缩函数具有碰撞阻力的特性,那么经过转换而生成的哈希函数也具有碰撞阻力。
1703864533
1703864534
MD变换很简单。比如压缩函数代入长度为m的输入值,并产生长度短一些为n的输出值。哈希函数的输入(可为任意大小)被分为长度为m-n的区块。MD变换运作过程如下:将每个区块与之前区块的输出一起代入压缩函数,注意,输入长度则变为(m-n)+n=m,也刚好就是压缩函数的输入长度。对于第一个区块而言,之前没有的区块,我们需要选取一个初始向量(见图1.3)。每次调用哈希函数,这个数字都会被再一次使用,而在实践中,你可以直接在标准文档中找到它。最后一个区块的输出也就是你返回的结果。
1703864535
1703864536
SHA-256函数利用了这样的一个压缩函数,这个压缩函数把一个768位的输入压缩成一个256位的输出,每一个区块的大小是512位。我们可以通过图1.3来理解SHA-256的工作过程。
1703864537
1703864538
1703864539
1703864540
1703864541
图1.3 SHA-256哈希函数简化图
1703864542
1703864543
注:SHA-256利用MD变换把一个固定输入的防止碰撞的压缩函数变换成一个接受任意长度输入的哈希函数。通过初始化向量的补位,可以把输入变成512位比特的整数倍。
1703864544
1703864545
截至目前,我们已经讨论了哈希函数、密码学上使用具备特性的哈希函数、这些特性的应用,以及在比特币世界中使用的一类特殊的哈希函数。在下面的章节中,我们将讨论通过哈希函数来构建比特币网络中的更为复杂的数据结构。
1703864546
1703864547
1703864548
哈希函数建模
1703864549
[
上一页 ]
[ :1.7038645e+09 ]
[
下一页 ]