Hash算法在信息安全方面的应用主要体现在三个方面:
(1) 文件校验
我们比较熟悉的校验算法有奇偶校验和CRC校验,这2种校验并没有抗数据篡改的能力,它们一定程度上能检測并纠正传输数据中的信道误码,但却不能防止对数据的恶意破坏。
MD5 Hash算法的”数字指纹”特性,使它成为眼下应用最广泛的一种文件完整性校验和(Checksum)算法,不少Unix系统有提供计算md5 checksum的命令。
(2) 数字签名
Hash 算法也是现代password体系中的一个重要组成部分。因为非对称算法的运算速度较慢,所以在数字签名协议中,单向散列函数扮演了一个重要的角色。 对 Hash 值,又称”数字摘要”进行数字签名,在统计上能够觉得与对文件本身进行数字签名是等效的。并且这种协议还有其它的长处。
(3) 鉴权协议
例如以下的鉴权协议又被称作挑战–认证模式:在传输信道是可被侦听,但不可被篡改的情况下,这是一种简单而安全的方法。
一般的说,Hash算法函数根据其原理,能够简单的划分为例如以下几类:
1. 加法Hash;
2. 位运算Hash;
3. 乘法Hash;
4. 除法Hash;
5. 查表Hash;
6. 混合Hash;
以下具体的介绍以上各种方式在实际中的运用。
1、加法Hash
所谓的加法Hash就是把输入元素一个一个的加起来构成最后的结果。标准的加法Hash的构造例如以下:
static int additiveHash(String key, int prime)
{
int hash, i;
for (hash = key.length(), i = 0; i < key.length(); i++)
hash += key.charAt(i);
return (hash % prime);
}
这里的prime是随意的质数,看得出,结果的值域为[0,prime-1]。
2、位运算Hash
这类型Hash函数通过利用各种位运算(常见的是移位和异或)来充分的混合输入元素。比方,标准的旋转Hash的构造例如以下:
static int rotatingHash(String key, int prime)
{
int hash, i;
for (hash=key.length(), i=0; i
hash = (hash<>28)^key.charAt(i);
return (hash % prime);
}
先移位,然后再进行各种位运算是这样的类型Hash函数的主要特点。
3、乘法Hash
这样的类型的Hash函数利用了乘法的不相关性(乘法的这样的性质,最有名的莫过于平方取头尾的随机数生成算法,尽管这样的算法效果并不好)。例如:
static int bernstein(String key)
{
int hash = 0;
int i;
for (i=0; i
return hash;
}
使用这样的方式的著名Hash函数还有FNV算法及其变种,需要注意的是ETH中的EThash算法中就部分采用FNV代替常见的异或操作:
// 32位FNV算法
int M_SHIFT = 0;
public int FNVHash(byte[] data)
{
int hash = (int)2166136261L;
for(byte b : data)
hash = (hash * 16777619) ^ b;
if (M_SHIFT == 0)
return hash;
return (hash ^ (hash >> M_SHIFT)) & M_MASK;
}
以及改进的FNV算法:
public static int FNVHash1(String data)
{
final int p = 16777619;
int hash = (int)2166136261L;
for(int i=0;i
hash = (hash ^ data.charAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
return hash;
}
除了乘以一个固定的数,常见的还有乘以一个不断改变的数,比方:
static int RSHash(String str)
{
int b = 378551;
int a = 63689;
int hash = 0;
for(int i = 0; i < str.length(); i++)
{
hash = hash * a + str.charAt(i);
a = a * b;
}
return (hash & 0x7FFFFFFF);
}
另外,尽管Adler32算法的应用没有CRC32广泛,只是,它可能是乘法Hash里面最有名的一个了。关于它的介绍,大家能够去看RFC 1950规范。
4、除法Hash
除法和乘法一样,相同具有表面上看起来的不相关性。只是,由于除法太慢,这样的方式差点儿找不到真正的应用。须要注意的是,我们在前面看到的hash的 结果除以一个prime的目的仅仅是为了保证结果的范围。假设你不须要它限制一个范围的话,能够使用例如以下的代码替代”hash%prime”: hash = hash ^ (hash>>10) ^ (hash>>20)。
5、查表Hash
查表Hash最有名的样例莫过于CRC系列算法。尽管CRC系列算法本身并非查表,但是,查表是它的一种最快的实现方式。
查表Hash中有名的样例有:Universal Hashing和Zobrist Hashing。他们的表格都是随机生成的。
6、 混合Hash
混合Hash算法利用了以上各种方式。各种常见的Hash算法,比方MD5、Tiger都属于这个范围。它们一般非常少在面向查找的Hash函数里面使用。
当然根据你的需要选择合适的hash函数是非常需要技巧的,最简单可以使用主要的乘法Hash,当乘数为33时,对于英文单词有非常好的散列效果(小于6个的小写形式能够保证没有冲突)。复杂一点能够使用FNV算法(及其改进形式),它对于比較长的字符串,在速度和效果上都不错。