1703864414
1703864415
1703864416
图1.2 必然的碰撞
1703864417
1703864418
注：因为输入的数量超过输出的数量，我们可以确定某一个输出肯定对应多个输入。
1703864419
1703864420
而更糟糕的是，对于加密的哈希函数，我们虽然说应该找不到碰撞，但有些方法是能保证找到碰撞的。考虑以下对应于一个256位输出大小的哈希函数，选择2256+1个不同数值，计算每个数的哈希值，并检查是否有两个相等的输出。因为我们这里选择的输入多于输出，因此在应用哈希函数时，一些数对必将产生碰撞。
1703864421
1703864422
使用上述方法一定能找到碰撞。但如果我们随机性地选择输入，并计算哈希值，我们在检验第2256+1个输入之前便很可能找到碰撞。实际上，如果我们随机选择2130+1个输入值，找到至少两个等同哈希值的概率为99.8%。仅仅通过检验可能输出数量的平方根次数，便大体能找到碰撞，这一事实在概率学中被称为是生日悖论（birthday paradox）[1]。
1703864423
1703864424
这个碰撞检测算法对每个哈希函数都有效，但是它的问题是其计算需要花很长很长时间才能完成。对于一个256位输出的哈希函数来说，最坏的情况是你需要进行2256+1次哈希函数计算，平均次数为2128次，这简直是一个天文数字——如果一台电脑每秒计算10 000个哈希值，计算2128个哈希值，需要花1027多年时间！换个角度，我们可以说，如果人类制造的每台电脑在整个宇宙起源时便开始计算，到目前为止，它们找到碰撞的概率仍然无穷小，比下两秒钟地球将被大陨石摧毁的概率还要小得多。
1703864425
1703864426
因此，为了寻找一个任意的哈希函数的碰撞，我们只是有了一个一般，但并不实用的算法。一个更艰涩的问题是：有没有其他的方法，可以用于对于某一特定哈希函数找到碰撞？也就是说，虽然一般的碰撞测试算法不适用，但仍可能有其他的算法，可以有效地找到某个哈希函数的碰撞。
1703864427
1703864428
以下面的哈希函数为例：
1703864429
1703864430
H(x)=x mod 2256
1703864431
1703864432
这个函数接受任何长度的输入，产生一个固定大小输出（256位），且能进行有效计算，因此符合我们对哈希函数的要求。但是对于这个函数，我们确实具备一个有效的能够寻找碰撞的方法。注意，这个函数仅返回输入的最后256位，因此，数值3和3+2256就构成了碰撞[2]。这个简单的例子表明，虽然我们的一般碰撞测试方法在实践中不可行，但至少对于某些哈希函数，存在有效的测试碰撞的方法。
1703864433
1703864434
但对于某些哈希函数，我们无法确认识别碰撞的有效方法是否存在，我们只是怀疑这些函数具有防碰撞特性，但是我们已经证明，世界上没有哈希函数具有防碰撞特性。我们实践中依赖的加密的哈希函数仅仅是人们经过不懈努力之后暂未成功找到碰撞的函数。因此，我们选择相信那些加密的哈希函数具有哈希阻力（在某些情况下，如之前的MD5哈希函数，在多年的努力之后最终找到了碰撞，导致该函数在实践中被逐渐淘汰，最终被弃用）。
1703864435
1703864436
应用：信息摘要
1703864437
1703864438
现在我们知道什么是碰撞阻力了，我们自然会问：碰撞阻力有什么用途？以下就是一个应用：哈希函数H具有碰撞阻力，x和y是两个不同的输入，那么可以假设它们的哈希函数H(x)和H(y)也不同——如果已知x和y不同，但哈希值相同，那么H具有碰撞阻力的假设就不成立了。
1703864439
1703864440
这个论证使我们可以将哈希输出作为信息摘要（message digest）。以SecureBox为例，SecureBox是一个允许用户上传文件，并保证文件被完整下载的线上文件存储系统。假设爱丽丝上传了很大的文件，并希望能够在之后下载时确认她下载的文件与她上传的文件相同。一种方法是将整个文件进行本地存储，并直接将其与下载文件对比。如果这样可行，那么将文件上传便显得毫无意义，倘若爱丽丝需要使用本地文件副本以保证其完整性，她可以直接使用本地副本。
1703864441
1703864442
无碰撞哈希函数为这个问题提供了简单有效的解决方法，爱丽丝只需要记住原文件的哈希值，从SecureBox下载文件后，她可以计算下载文件的哈希值，并与原文件哈希值进行对比。如果哈希值相同，那么爱丽丝可以说该文件就是她上传的那一个，但是如果不同，她则可以确定文件被破坏了。记录哈希值可以帮助爱丽丝检测文件在传输过程中，或在SecureBox服务器上是否产生了意外损坏，或者检测文件是否受到服务器的蓄意修改。保证主体不受其他实体的恶意行为侵害，这正是密码学的核心。
1703864443
1703864444
这里的哈希函数对于一个信息生成固定长度的摘要，或生成了简明总结，这为我们提供了一种记住之前所见事物，并在今后认出这些事物的有效方法。虽然整个文件可能非常大，存储规模达数G，但其哈希值的长度固定。例如，哈希函数为256位。这样做，极大地降低了存储要求。在本章后面及整本书中，我们都会看到哈希作为信息摘要的应用。
1703864445
1703864446
特性2：隐秘性
1703864447
1703864448
我们希望哈希函数拥有的第二个特性是其隐秘性。隐秘性保证，如果我们仅仅知道哈希函数的输出y=H(x)，我们没有可行的办法算出输入值x。问题是，上述的表示形式不一定是正确的。考虑以下简单的例子：我们做一个抛硬币的实验，如果抛硬币结果为正面，我们会宣布字符串哈希为“正面”；如果结果为反面，我们会宣布字符串哈希为“反面”。
1703864449
1703864450
然后我们问我们的对手，在他没有见到抛硬币，而只见到哈希函数的输出的前提下说出哈希函数的输入字符串（很快我们就知道为什么要玩这个游戏了）。为了回答问题，对手会简单计算“正面”字符串的哈希值及“反面”字符串的哈希值，然后对手便可以知道他得到的是哪一个。这样，只需要几步，对手就能反解出输入值。
1703864451
1703864452
对手能够猜出字符串，这是因为x只有两个可能，他可以很轻易地将两个可能对应的哈希值计算出来。为了能够实现隐秘性，我们需要x的取值来自一个非常广泛的集合，也就是说，仅仅通过尝试几个特定的x，就能找到输出值的方式将不会发生了。
1703864453
1703864454
现在的问题是：在类似抛硬币的“正面”、“反面”实验中，如果我们想要的反解的输入值并非来自分散的集合，我们是否还能得到隐秘性？幸运的是，对于这个问题答案是肯定的！我们甚至能够通过与另一个较为分散的输入进行结合，而将一个并不分散的输入进行隐秘。现在我们可以更精确地表示隐秘的含义了（双竖线‖为连接符号，代表把一系列事件、事情等联系起来）。
1703864455
1703864456
隐秘性 哈希函数H具有隐秘性，如果：当其输入r选自一个高阶最小熵（high min-entroy）的概率分布，在给定H（r‖x）条件下来确定x是不可行的。
1703864457
1703864458
在信息论中，最小熵是用于测试结果可预测性的手段，而高阶最小熵这个概念比较直观描述了分布（如随机变量）的分散程度。具体来说，在从这样分布中取样时，我们将无法判定取样的倾向。举个具体的例子，如果r是从长度为256位的字符串中随意选出的，那么任意特定字符串被选中的概率为1/2256，这是一个小到几乎可以忽略的取值。
1703864459
1703864460
应用：承诺
1703864461
1703864462
现在来看一下隐秘性的应用。具体来说，我们把想做的事情称为承诺（commitment）。这里承诺是一个数字化过程，可以类比为以下动作：首先选定一个数字，将数字装进信封，然后将该信封放到一个人人都看得到的桌子上。这样做以后，可以说你就信封里的数字做出了承诺，在打开信封前，虽然你已经做出了承诺，对其他人来说它还是秘密。在之后，你可以打开信封，来展示承诺的数值。
1703864463
[
上一页 ]
[ :1.703864414e+09 ]
[
下一页 ]