哈希函数的原理及应用

    哈希（Hash）函数又称为散列函数、杂凑函数。它是一种单向密码体制，即一个从明文到密文的不可逆映射，只有加密过程，没有解密过程。

创新互联公司IDC提供业务:托管服务器,成都服务器租用,托管服务器,重庆服务器租用等四川省内主机托管与主机租用业务;数据中心含:双线机房,BGP机房,电信机房,移动机房,联通机房。

    哈希函数可以将满足要求的任意长度的输入经过变换后得到固定长度的输出。这个固定长度的输出称为原消息的散列或消息摘要（Message Digest）。哈希函数的数学表述为：

                                    h=H(m)

    其中，H是哈希函数，m是任意长度明文，h是固定长度的哈希值。

    理想的哈希函数对于不同的输入可以获得不同的哈希值。如果x、x' 是两个不同的消息，存在H(x)=H(x'),则称x和x'是哈希函数H的一个碰撞。

    由于哈希函数的这种单向的特征以及长度固定的特征使得它可以生成消息或者数据块的消息摘要（也称为散列值、哈希值），因此在数据完整性和数字签名领域有着广泛的应用。

    典型的哈希函数有两类：消息摘要算法（MD5）和安全散列算法（SHA）。

    1.哈希函数的性质

    哈希函数有以下特点：

    ①压缩。对于任意大小的输入x，哈希值H（x）的长度很小，实际应用中哈希函数H产生的哈希值是固定长度。

    ②易计算。对于任意给定的消息，容易技术其哈希值。

    ③单向性。对于给定的哈希值h，要找到m'使得H(m')=h在计算上是不可行的，即求哈希的逆很困难。

    ④抗碰撞性。理想的哈希函数是无碰撞的，但实际算法设计中很难做到。有两种抗碰撞性：一种是弱抗碰撞性，即对于给定的消息x，要发现另一个消息y，满足H(x)=H(y)在计算上不可行；另一种是强抗碰撞性，即对于任意一对不同的消息（x,y），使得H(x)=H(y)在计算上不可行。

    ⑤高灵敏性。当一个输入位发生变化时，输出位将有一半以上会发生变化。

    2.哈希函数的应用

    （1）消息认证

    在一个开放通信网络的环境中，信息面临的***包括窃听、伪造、修改、插入、删除、否认等。因此，需要提供用来验证消息完整性的机制或服务，即消息认证。这种服务的主要功能是确保收到的消息确实与发送的一样和确保消息的来源真实有效。用于消息认证的最常见的密码技术是基于哈希函数的消息认证码。

    （2）数字签名

    因为非对称算法的运算速度较慢，所以在数字签名协议中，哈希函数扮演了一个重要的角色。对消息摘要进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。

    （3）口令的安全性

    由于哈希函数具有单向性的特征，因此在口令保护中应用非常广泛。通常，仅将口令的哈希值进行保存，进行口令校验的时候对比哈希值即可。即使***者获得了保存的哈希值，也无法计算出口令。

    （4）数据完整性

    比较熟悉的校验算法有奇偶检验和循环冗余校验码CRC。这两种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信息误码，但却不能防止对数据的恶意破坏。哈希算法消息摘要的特征使它成为目前应用最广泛的一种数据完整性校验的算法。

    3.消息摘要算法

    消息摘要算法MD5可以对任意长度的明文产生128位的消息摘要。

    MD5算法是按512位进行处理的，对于任意长度的消息将首先通过填充的方法使其成为512的倍数。首先，要对任意长度的信息进行填充，使信息的长度等于L*512+448，即长度≡448 mod 512 .填充的方法为：首先在消息后面先添加一个位“1”，再依次添加位“0”，直到长度满足条件；然后，将原始消息的长度以64位表示，添加在最后面，使得信息长度恰好达到512位的倍数。

    MD5将填充后的消息以512为单元分为L个分组，然后对每个分组进行处理。对每个分组处理的时候，都执行4轮非常相似的运算，每一轮包括了16个类似的步骤。

    每一个步骤的数据处理都是针对4个32位记录单元数据进行的，这4个记录单元的初始值以十六进制数表示如下：A=0123 4567 ,B =89AB CDEF ,C =FEDC BA98 ,D =7654 3210。进行4轮，共64个步骤运算之后，记录单元A、B、C、D中的128位即为中间处理的输出结果，它将作为下个512位分组处理的输入初始值。这样，对L个分组都处理完毕后，最后输出一个128位的哈希结果。

    当第一轮的第一步骤开始处理时，A、B、C、D记录单元中的值先复制到另外4个记录单元AA BB CC DD 中。这4个值将在第4轮的最后一个步骤与相关的A B C D相加。在每一个步骤的操作中都是将A B C D中的3个记录单元中的数据以非线性的操作方式处理，此结果再与512位明文分组中的一个32位子明文分组M[K]及一固定数T[i]相加。相加的结果向左循环移动S位（以<

    在每一轮的操作中，MD5都使用不同的逻辑运算将3个记录单元中的数据以非线性方式处理，可以用下面的方式来表示在4个不同轮中，每个步骤的操作程序：

    第一轮：FF（A.B,C,D,M[K],S,T[i]）表示a←b+((F(B,C,D)+M[k]+T[i])<

    第二轮：GG（A.B,C,D,M[K],S,T[i]）表示a←b+((G(B,C,D)+M[k]+T[i])<

    第三轮：HH（A.B,C,D,M[K],S,T[i]）表示a←b+((H(B,C,D)+M[k]+T[i])<

    第四轮：II（A.B,C,D,M[K],S,T[i]）表示a←b+((I(B,C,D)+M[k]+T[i])<

    第四轮最后一个步骤的A B C D输出，将分别与 AA BB CC DD记录单元中的数值相加，其结果将成为下一个512位明文分组处理时 A B C D 的初始值。当完成了最后一个分组运算时，A B C D中的设置就是最后哈希值。

    值得一提的是 ，2004年 我国密码学家王小云所提的杂凑冲撞算法只需少于2的69次方步骤