数据结构之哈希函数

亦凉 2022-06-15 01:15 442阅读 0赞

# 概念： #

哈希（hash），也叫做散列、数据摘要等，是一种常见的[数据结构][Link 1]。哈希的表的核心概念分为哈希表和哈希函数。

# 哈希表（hashTable） #

哈希表之前讲过，有需要的可以参考：[点击打开哈希表][Link 2]

# 哈希函数 #

哈希函数就是将某一不定长的对象映射为另一个定长的对象。能够做到这一点的函数有很多，那什么可以作为哈希函数？这里我们首先要明确下什么可以作为哈希函数。

如果两个不同的对象经过哈希函数计算后得到相同的哈希值，则这就是所谓的冲突。冲突会导致很多的异常，说一种极端的情况：如果一个哈希函数的计算记过经常为0，那么它根本无法帮助我们来区分对象，也就不能帮助我们快速查找对象了，也就违反了哈希的作用。

在设计哈希函数的时候我们主要关注两点：

*  冲突少：很少出现不同的对象函数作用后得到相同的值。
 *  计算快：计算哈希能够快速找到对象。

Hash函数还有另外的含义。实际中的Hash函数是指把一个大范围映射到一个小范围。把大范围映射到一个小范围的目的往往是为了节省空间，使得数据容易保存。除此以外，Hash函数往往应用于查找上。所以，在考虑使用Hash函数之前，需要明白它的几个限制：

*  Hash的主要原理就是把大范围映射到小范围；所以，你输入的实际值的个数必须和小范围相当或者比它更小。不然冲突就会很多。
 *  由于Hash逼近单向函数；所以，你可以用它来对数据进行加密。
 *  不同的应用对Hash函数有着不同的要求；比如，用于加密的Hash函数主要考虑它和单项函数的差距，而用于查找的Hash函数主要考虑它映射到小范围的冲突率。

从简单原则出发，我们首先考虑下字符串的哈希函数。我们知道字符串特指ASCII的编码字符串，他们哈希函数后值是不一样的。看一个简单的算法

djb2算法

![20161207103319031][]

**\[objc\]**  [view plain][]   [copy][view plain]

[print][view plain] [?][view plain]

1.  unsigned **int** DJB\_hash(**char****char** \*str)      
2.  \{      
3.           unsigned **int** hash = 5381;      
4.        
5.           **while** (\*str)      
6.           \{      
7.                   hash += (hash << 5) + (\*str++);      
8.           \}      
9.        
10.          **return** (hash & 0x7FFFFFFF);      
11. \}

在看一个和djb算法相似的算法，sdbm算法

**\[objc\]**  [view plain][]   [copy][view plain]

[print][view plain] [?][view plain]

1.  unsigned **int** SDBM\_hash(**char****char** \*str)      
2.  \{      
3.           unsigned **int** hash = 0;      
4.        
5.           **while** (\*str)      
6.           \{      
7.                   hash = (\*str++) + (hash << 6) + (hash << 16) - hash;      
8.           \}      
9.        
10.          **return** (hash & 0x7FFFFFFF);      
11. \}

虽然上面两种算法的很快，但是基于哈希冲突少的特点，djb算法和sdbm算法都没能提供理论的依据，而主要依赖于试验。

在哈希的应用中，还有一类特殊的哈希函数，叫做密码哈希函数。

## 密码学哈希函数 ##

### 定义： ###

Hash函数H将可变长度的数据块M作为输入，产生固定长度的Hash值h = H(M)。  
　　称M是h的原像。因为H是多对一的映射，所以对于任意给定的Hash值h，对应有多个原像。如果满足x≠y且H(x)=H(y)，则称为碰撞。

### 密码学Hash函数的应用 ###

**1、消息认证**

Hash码能够通过如下不同方法用于提供消息认证

![20161207103945814][]

a) 使用对称密码E加密消息和Hash码，由于只有A和B共享密钥K，所以消息必然发自A处，且可通过验证Hash码证明数据在传输过程中未被更改。

b) 使用对称密码只对Hash码加密。由于明文无需加密性的应用，这种方案大大减少了加密操作的负担。

c) 不使用加密[算法][Link 1]，仅使用Hash函数实现消息验证。该方案中，通信双方共享相同的秘密值S，发送方A将消息M和秘密值S串联后计算其Hash值，并将得到的Hash值附在消息M后发送。因为接收方B同时掌握S值，所以能够重新计算该Hash值进行验证。

d) 在方案c的基础上将整个消息和Hash值加密，以提供保密性。

处于成本和速度方面的考虑，人们越来越对那些不包含加密函数的方法感兴趣，因此b和c方案更受青睐，不过如果对整个消息有加密型要求，则a和d仍具有实际意义。

实际应用中，消息认证通常使用消息认证码（MAC）实现。MAC函数将通信双方共享的密钥和数据块作为输入，产生Hash值作为MAC码，然后将MAC码和受保护的消息一起传递或存储。需要检查消息的完整性时，使用MAC函数对消息重新计算，并将计算结果与存储的MAC码对比。MAC提供安全保护，用于抵抗不知道密钥的攻击者的攻击。在实现中，往往使用比加密算法效率更高的特殊设计的MAC函数。

**　　2、数字签名**

**　　**数字签名的应用比消息认证更加广泛。主要有如下两种方案：

![20161207104035315][]

a) 使用发送方的私钥利用公钥密码算法对Hash码进行加密。这种方法也可提供认证；由于只有发送方可以产生加密后的Hash码，所以这种方法也提供了数字签名。

b) 若既希望保证保密性又希望有数字签名，则先用发送方的私钥对Hash码加密，再用对称密码中的密钥对象消息和公钥算法加密结果进行加密，这种技术比较常用。

**3、其他应用**

对于Hash函数，通常还被用于产生单向口令文件。在[操作系统][Link 3]中，存储口令的Hash值而不是口令本身，当用户输入口令时，操作系统将比对输入口令的Hash值和存储在口令文件中的Hash值来进行用户验证。

Hash函数还能用于入侵检测和病毒检测。将每个文件的Hash值H(F)存储在安全系统中(如CD-R)，随后就能通过重新计算H(F)来判断文件是否被修改过。入侵者只能够改变F，而不能改变H(F)

密码学Hash函数能够用于构建随机函数PRF或用作伪随机数发生器。基于Hash函数的PRF可用于对称密码中的密钥产生。

### 密码学Hash函数的安全性需求 ###

![20161207104138253][]

**弱Hash函数：只**满足以上前五个要求的Hash函数。

**强Hash函数：**满足以上前六个要求的Hash函数。

强Hash函数能够保证免受以下攻击：假设Bob写一条借据消息并发送给Alice，Alice在借据上签名认可。Bob如果能找到两条消息具有同样的Hash值，其中一个借据消息要求Alice归还金额较小，另一个金额很大，那么让Alice签下第一个小额借据后，Bob就能声称第二个借据是真实的（将Alice在第一个借据的签名附到第二个借据中）。

下图展示了抗原像攻击、抗弱碰撞攻击和抗强碰撞攻击三者之间的关系

![20161207104203084][]

在传统观念中并没有把伪随机性作为密码学Hash函数的安全性需求，但在实际应用中或多或少有所要求。密码学Hash函数通常用于密钥产生、伪随机数发生器以及消息完整性应用，上述三个应用都要求Hash函数的输出是随机的。![20161207104227112][]

### **对Hash函数的攻击** ###

**1、穷举攻击**

a) **原像攻击和第二原像攻击**

攻击者对给定的Hash值h，试图找到满足H(y) = h的y。穷举攻击的方法是随机选择y，尝试计算其Hash值知道碰撞出现。对于m位的Hash值，穷举的规模大约是2m,对于攻击者平均尝试次数为2m-1，才能找到一个满足H(y)=h的y值。

**b) 碰撞攻击**

对于碰撞攻击，攻击者试图找到两个消息或数据块x和y，满足H(x)=H(y)，与原像攻击和第二原像攻击相比，其穷举的规模相对更小一些，这也通过数学上的生日悖论得到印证。本质上，如果我们在均匀分布的0到N-1的范围内选择随机整数变量，那么在N1/2次选择后发生重复的概率就会超过0.5。因此，对于m位的Hash值，如果我们随机选择数据块，预计在2m/2次尝试后就能找到两个具有相同Hash值的数据块。

Yuval提出以下策略进行碰撞攻击：

1、发送方A准备对文本消息x进行签名（尚未签名，但可预期要签名的文件内容），其使用的方法是：用A的私钥对m位的Hash码加密并将加密后的Hash码附于消息之后。

2、攻击者产生该消息x的2m/2种变式x'，每种变式都表达相同的意义，将这些消息以及对应的Hash值存储起来。

产生多个具有相同意义的变式并不难，例如攻击者可以在文件的词与词之间插入若干“空格-空格-退格”字符对，然后在实例中用“空格-退格-空格”替代这些字符，从而产生各种变式。攻击者也可以简单地改变消息中的某些词但不改变消息的意义。

3、攻击者准备伪造一条消息y，并想获取A的签名，只需要伪造y的变式y',然后计算H(y')，并与所有的H(x')进行比对，直到碰撞出现。

4、攻击者将发生碰撞的消息x'提供给A签名，然后将该签名附于伪造消息y'后。这样攻击者就在不知道A密钥的情况下获得了有A数字签名的消息y'，并可以此获利。

参考：[密码hash函数][hash]

[Link 1]: http://lib.csdn.net/base/datastructure
[Link 2]: http://blog.csdn.net/xiangzhihong8/article/details/51598299
[20161207103319031]: /images/20220615/e10e394a460045c895bcb5aa61097883.png
[view plain]: http://blog.csdn.net/xiangzhihong8/article/details/53502453#
[20161207103945814]: /images/20220615/0a86b881afee4384bad6e50e2c09ac92.png
[20161207104035315]: /images/20220615/18c57b8340354472b81a63e15c936bcd.png
[Link 3]: http://lib.csdn.net/base/operatingsystem
[20161207104138253]: /images/20220615/306e35e2492a4607aa861eb506cfa8f5.png
[20161207104203084]: /images/20220615/324dc791fce24b7ab05b51e024c0628e.png
[20161207104227112]: /images/20220615/c9f2ad5dff434d79a5d4a8f7ea1bae71.png
[hash]: http://www.cnblogs.com/block2016/p/5623902.html