再谈哈希(HASH)加密算法

目前很多网站都用 MD5 算法保存用户密码，但对于哈希（HASH）加密算法的认识还存在很多误区，所以今天就有必要再重新认识一下哈希加密算法。

一、哈希加密算法不是加密算法

哈希加密算法是一种消息摘要算法，不是一种加密算法，但由于其单向运算，具有一定的不可逆性，成为加密算法中的一个构成部分，完整的加密机制不能仅依赖哈希加密算法。

二、哈希加密算法的破解与社会工程学

哈希加密算法本身为单向性，很难直接破解，现有的破解都是将常用字符计算HASH值后反向比较。例如密码123456，假设MD5值为1ab9744e58acee3ed8f03508cbf82bf5，那么数据库中查到MD5值即知道了密码。通过社会工程学的应用，大量常用密码已可直接破解。

三、哈希加密算法的碰撞现象

哈希加密算法可以理解为将任意的信息经过提炼后，成为一个定长的字符串。世界上的信息数量为无穷大，所以定长的字符串不可能表达所有的摘要，因此存在所谓的“碰撞”，即2个同样的信息源摘要是一样的。

2004年山东大学王晓云提出有关快速查找“碰撞对”的算法，引起安全界对于HASH算法的极大关注，NIST提出到2010年不再使用MD5和SHA-1。目前仍可使用的哈希加密算法包括：SHA-256，SHA-512，SHA-224，SHA-384。

2011年2月FIPS180-4草案还增加了SHA-512/224，SHA-512/256。这些算法都是SHA-2系列算法，SHA3-256算法也即将到来。

关于碰撞必须还要说的是，有几率找到碰撞对，但并不意味着哈希加密算法整体被否定，例如将合同文本整体哈希加密算法并数字签名，如果找到碰撞对，很难还原成一个正常的文本，如果是一堆乱码，没有人会认可此文件，在不篡改哈希加密算法的前提下无法有实际意义的修改合同。

四、合理使用哈希加密算法

1. 废除旧算法，至少使用SHA-256，64位操作系统SHA-512运算速度更佳，建议选用。

2. 合理加点“SALT”，即干扰字符串。

例如：SALT1=C`3/$xUM,5ltL4pze;avf9#kgmET^ SALT2=1qYIs,vOSfn%UHhm5+3TX:#iety0d 计算HASH SHA-512(SALT1+用户名+SALT2+密码)

那么社会工程学和目前的暴力运算是无法解决的。

3. 不要以为联合使用HASH算法会安全。例如MD5+SHA1，或者SHA1(MD5)嵌套，有文献证实都是无效的。

哈希算法在字典上的测试应用

此前我们了解过二叉树算法，哈希算法，二分法等等，其中由最常用的二叉树算法演变过来的哈希算法乃是从刚开始就学过的，此次因为一些项目的需要，要做一个类似ispell 的软件，其中会产生大量的对单词的查找操作，于是经过一翻研究，得出以下HASH算法，经过验证比一般的查表的FNV HASH算法产生的分布曲线基本没什么两样，并且在大部分的不同字典下，本算法要比查表的FNV HASH算法表现出速度更快，分布更均匀。但是因为是实验结果，所以暂时还没得出有效的数学推论，但是从大量的不同的字典测试数据来看，此算法确实效率不错。
由于以前没有涉及过相关的纯算法的设计，所以刚刚开始的时候，打算随便选用一种HASH，比如说用%除大质数，然后借此搭建一个比较强壮的测试环境，然后打算根据测试结果来改进HASH算法的模型。

最开始，我的HASH函数是这样的：
unsigned int hash_func(char *str, int len)
{
register unsigned int sum = 0;
register char *p = str;

while(p - str < len)
sum += *(p++);

return sum % MAX_PRIME_LESS_THAN_HASH_LEN;
}
非常简单，但是这是绝对不可取的，通过这个函数，我选取了一个23w词的字典做为测试，当HASH SIZE=1024的时候，震荡幅度相当大，那么如何来改进呢？首先想到可能产生的冲突的是这种情况：abcd和acbd，对于这两种单词来说，如果用上面的HASH函数，就一定会发生碰撞，为什么呢？因为每个字符少了关于它自己的位置信息，于是第一次改进版本的HASH函数就给每个字符加上了它的位置信息，将上面所描述的函数改进为：

unsigned int hash_func(char *str, int len)
{
register unsigned int sum = 0;
register char *p = str;

while(p - str < len)
sum += *(p++) * (p–str);

return sum % MAX_PRIME_LESS_THAN_HASH_LEN;
}

某种程度上来说，比不带位置信息产生的分布图要好多了，但是仍然非常的不均匀。那么接来分析产生分布不均匀的原因，因为是用的乘法，所以仍然太过于依赖字母产生的结果了。于是改用XOR操作，选用以下函数：

unsigned int hash_func(char *str, int len)
{
register unsigned int sum = 0;
register char *p = str;

while(p - str < len)
sum += (*(p++) * (p–str)) ^ sum;

return sum % MAX_PRIME_LESS_THAN_HASH_LEN;
}

虽然震荡幅度比较，不过做出来的regression line明显比上两张图片平得多了。但是结果仍然非常不好，从800到100的range太大。原因还是因为数据分布得不够均匀，于是思考单独的用加法来算是不是不太好，根据其他查表类HASH算法的过程，发现其大多都用了高低位来组合成最后的结果，于是我也采用了他们的方法：

unsigned int hash_func(char *str, int len)
{
register unsigned int sum = 0; 
register unsigned int h = 0;
register char *p = str;

while(p - s < len) 
{
register unsigned short a = *(p++);
sum ^=  a * (p - str); 
h ^= a / (p - str);
}
return ((sum << 16) | h) % MAX_PRIME_LESS_THAN_HASH_LEN;
}

最后得出结论，不用查表的方法，而通过字符串本身的位置对字符本身进行修正的方法也能得到结果相当满意的HASH函数，之后换了几个大小不同的字典进行测试，得出的图象都大致和上图一致，非常令人满意。对于这个项目，包括如何检查单词错误，和自动修正等等相关的内容，会随着项目的完成一一在整理成文档，希望大家支持。

本文为收集整理，文章部分观点不代表本站观点，如有侵权或其它问题请反馈客服。https://www.wgj7.com/cjwt/16180.html