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
1703864550
哈希函数是密码学中的瑞士军刀:它们在众多各具特色的应用中找到了一席之地。这种多功能性的另一面是,为了保证安全,不同的应用会要求不同的哈希函数特性。事实已经证明,要确定一系列哈希函数特性以全面达成可证安全极度困难。
1703864551
1703864552
本书中,我们会选出在比特币和其他加密数字货币中,对哈希函数使用方式很重要的三个特性。即使在这个范围内,并非所有这些特性对哈希函数的每一次使用都有必要。比如,我们之后会看到,谜题友好只在比特币采矿中具有重要性。
1703864553
1703864554
安全系统设计师常常会放弃,并且把哈希函数建立成对于任意一个可能的输入,都会得到一个独立的随机输出的函数。这种使用“随机预言模式”来证明安全的做法在密码学中仍具争议。不论在这个辩论中你的立场如何,在建立安全系统时,当我们应用哈希函数基本特性,推论如何减少安全特性的数量,都是宝贵的智力训练。本章的目的便是帮你学习这一项技能。
1703864555
1703864556
[1]生日悖论是指,如果一个房间里有23个或23个以上的人,那么至少有两个人的生日相同的概率要大于50%。这就意味着在一个典型的标准小学班级(30人)中,存在两人生日相同的可能性更高。对于60或者更多的人,这种概率要大于99%。——译者注
1703864557
1703864558
[2]3和3+2256对2256求余数之后,结果都是3。——译者注
1703864559
1703864560
[3]结论反之不成立,就是说,我们可以找到碰撞,但都不是满足H(nonce‖msg)==H(nonce’‖ msg’)意义下的碰撞。例如,你可以对于同一个信息来产生满足同一承诺的随机数,但这里的哈希函数不具备碰撞阻力特性。
1703864561
1703864562
1703864563
1703864564
[
上一页 ]
[ :1.703864515e+09 ]
[
下一页 ]