您现在的位置: 哈希hash论坛 > 哈希尾数 > Hash算法的分类和原理

Hash算法的分类和原理

来源:哈希交流群  热度:   时间:2022-05-14 20:21
Hash 算法在信息安全方面的应用主要体现在三个方面: (1) 文件校验 我们比较熟悉的校验算法有奇偶 校验和 CRC校验,这2种校验并没有抗数据篡改的能力,它们一定程度上能检測并纠正...

Hash算法在信息安全方面的应用主要体现在三个方面:

 

(1) 文件校验

我们比较熟悉的校验算法有奇偶校验和CRC校验,这2种校验并没有抗数据篡改的能力,它们一定程度上能检測并纠正传输数据中的信道误码,但却不能防止对数据的恶意破坏。

MD5 Hash算法的”数字指纹”特性,使它成为眼下应用最广泛的一种文件完整性校验和(Checksum)算法,不少Unix系统有提供计算md5 checksum的命令。

 

(2) 数字签名

Hash 算法也是现代password体系中的一个重要组成部分。因为非对称算法的运算速度较慢,所以在数字签名协议中,单向散列函数扮演了一个重要的角色。 对 Hash 值,又称”数字摘要”进行数字签名,在统计上能够觉得与对文件本身进行数字签名是等效的。并且这种协议还有其它的长处。

 

(3) 鉴权协议

例如以下的鉴权协议又被称作挑战–认证模式:在传输信道是可被侦听,但不可被篡改的情况下,这是一种简单而安全的方法。


Hash算法分类
 
 

 

一般的说,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算法(及其改进形式),它对于比較长的字符串,在速度和效果上都不错。