Hash函数的定义和性质

Hash，一般音译为“哈希”。Hash函数把任意长度的输入通过Hash算法变换成固定长度的输出，该输出就是Hash值或消息摘要（Message Digest）。这种变换是一种压缩映射，即Hash值的空间通常远小于输入的空间。简单地说，Hash函数是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

数据的完整性是指数据从发送方产生，经过传输或存储以后，不以未授权的方式修改的性质。消息摘要是消息中所有比特的函数，因此Hash函数提供了一种检测数据完整性的能力，即改变消息中任何一比特或几比特都会使消息摘要发生改变。

设H是一个Hash函数，x是消息（可以是任意长度的二元比特串），消息摘要定义为y=H（x）。一般要求消息摘要是相当短的二元比特串，常用的消息摘要是160 bit或256 bit。如果消息x被修改为x′，则可以通过计算消息摘要y′=H（x′）并且验证y′=y是否成立来确认数据x是否被修改的事实。如果y′≠y，则说明消息x被修改，从而达到了检验消息完整性的目的。

Hash函数的安全性在于它的单向性。单向性是指对Hash函数H而言，由x计算y=H（x）是容易的，但从H（x）的值计算x是不可行的。对于Hash函数的安全要求，通常采用下面的三个问题来进行判断。若一个Hash函数对这三个问题都是难解的，计算上是不可行的，则认为该Hash函数是安全的。

设H：X→Y是一个Hash函数，X表示所有消息的集合（有限集或无限集），Y表示所有消息摘要构成的有限集合。

1）设已知y∈Y，是否能够找到x∈X，使得H（x）=y。(www.xing528.com)

2）设已知x∈X，是否能够找到x′∈X，使得x′≠x，并且H（x′）=H（x）。

3）是否能够找到x、x′∈X，使得x′≠x，并且H（x′）=H（x）。

如果有两个消息x、x′∈X，且x′≠x，计算得H（x′）=H（x），就说这两个消息是碰撞消息。如果上述三个问题的第1）个问题不可解，那么说明该Hash函数是单向的；如果第1）和2）问题不可解，那么说明该Hash函数是抗弱碰撞的；如果第1）和3）问题不可解，那么说明该Hash函数是抗强碰撞的。

实际应用中的Hash函数可分为简单的Hash函数和带密钥的Hash函数。带密钥的Hash函数通常用来作为消息认证码（Message Authentication Code，MAC）。假定A和B有一个共享的密钥k，通过该密钥可以产生一个Hash函数H_k。对于消息x，A和B都能够计算出相应的消息摘要y=H_k（x）。A通过公共通信信道将二元组（x，y）发送给B。当B接收到（x，y）后，可以通过检验y=H_k（x）是否成立来确定消息x的完整性。如果y=H_k（x）成立，说明消息x和消息摘要y都没有被篡改。