【文章】应用密码学 单向函数 单向Hash函数

2.3 单向函数

    单向函数的概念是公开密钥密码的中心。尽管它本身并不是一个协议，但对这本书中所讨论的大多数协议来说却是一个基本结构模块。

    单向函数的概念是计算起来相对容易，但求逆却非常困难。也就是说，已知x，我们很容易计算f（x）。但已知f（x），却难于计算出x。在这里，“难”定义成：即使世界上所有的计算机都用来计算，从f（x）计算出x也要花费数百万年的时间    。

    打碎盘子就是一个很好的单向函数的例子。把盘子打碎成数千片碎片是很容易的事情，然而，要把所有这些碎片再拼成为一个完整的盘子，却是非常困难的事情。

    这听起来很好，但事实上却不能证实它的真实性。如果严格地按数学定义，我们不能证明单向函数的存在性，同时也还没有实际的证据能够构造出单向函数。即使这样，还是有很多函数看起来和感觉像单向函数：我们能够有效地计算它们，且至今还不知道有什么办法能容易地求出它们的逆。例如，在有限域中x²是很容易计算的，但计算x^1/2却难得多。在这节的其余部分，假定单向函数存在， 11.2节将更详细地讨论它。

    那么，单向函数有什么好处呢？单向函数不能用作加密。用单向函数加密的信息是毫无用处的，无人能解开它（练习：在盘子上写上信息，然后砸成碎片，把这些碎片给你的朋友，要求你的朋友读这上面的信息，观察你的朋友对单向函数会有多么深刻的印象）。对公开密钥密码，我们还需要一些其它的东西（虽然有单向函数的密码学应用，参看3.2节）。

    陷门单向函数是有一个秘密陷门的一类特殊单向函数。它在一个方向上易于计算而反方向却难于计算。但是，如果你知道那个秘密，你也能很容易在另一个方向计算这个函数。也就是说， 已知x，易于计算f（x），而已知f（x），却难于计算x。然而，有一些秘密信息y，一旦给出f（x）和y，就很容易计算x。

    拆开表是很好的单向陷门函数的例子。很容易把表拆成数百片小片，把这些小片组装成能够工作的表是非常困难的。然而，通过秘密信息（表的装配指令），就很容易把表还原。

2.4 单向Hash函数

    单向Hash函数有很多名字：压缩函数、缩短函数、消息摘要、指纹、密码校验和、信息完整性检验（DIC）、操作检验码（MDC）。不管你怎么叫，它是现代密码学的中心。单向Hash函数是许多协议的另一个结构模块。

    Hash函数长期以来一直在计算机科学中使用，无论从数学上或别的角度看，Hash函数就是把可变输入长度串（叫做预映射，Pre-image）转换成固定长度（经常更短）输出串（叫做hash值）的一种函数。简单的Hash函数就是对预映射的处理，并且返回由所有输入字节异或组成的一字节。

    这儿的关键就是采集预映射的指纹：产生一个值，这个值能够指出候选选预映射是否与真实的预映射有相同的值。因为Hash函数是典型的多到一的函数，我们不能用它们来确定两个串一定相同，但我们可用它的来得到准确性的合理保证。

    单向Hash函数是在一个方向上工作的Hash函数，从预映射的值很容易计算其Hash值，但要产生一个预映射的值使其Hash值等于一个特殊值却是很难的。前面提到的Hash函数不是单向函数：已知一个特殊的字节值，要产生一个字节串使它的异或结果等于那个值是很容易的事情。用单向Hash函数你不可能那样做。好的hash函数也是无冲突的：难于产生两个预映射的值，使他们的hash值相同。

    Hash函数是公开的，对处理过程不用保密。单向hash函数的安全性是它的单向性。无论怎么看，输出不依赖于输入。预映射的值的单个比特的改变，平均而言，将引起hash值中一半的比特改变。已知一个hash值，要找到预映射的值，使它的hash值等于已知的hash值在计算上是不可行的。

    可把单向Hash函数看作是构成指纹文件的一种方法。如果你想验证某人持有一特定的文件（你同时也持有该文件），但你不想他将文件传给你，那么，就要求他将该文件的单向Hash值传送给你，如果他传送的Hash值是正确的，那么几乎可以肯定地说他持有那份文件。这是在金融交易中的特殊使用，你不希望在网络的一些地方把提取100美圆变成提取1000美圆。一般情况下，你应使用不带密钥的单向Hash函数，以便任何人都能验证Hash值。如果你只想接收者才能验证Hash值，那么就读下一节。

消息鉴别码

    消息鉴别码（MAC）也叫数据鉴别码（DAC），它是带有秘密密钥的单向hash函数（见18.14节）。Hash值是预映射的值和密钥的函数。这在理论上与hash函数一样，除非只有拥有密钥的某些人才能验证hash值。你可以用hash函数或分组加密算法产生MAC；也有专用于MAC的算法。