数据结构与算法简记--哈希算法

哈希算法

 定义

将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法。

而通过原始数据映射之后得到的二进制值串就是哈希值。

特点

• 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）；
• 对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同；
• 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小；
• 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。

应用一：安全加密

• 常用于加密的哈希算法：

　　 MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法）

SHA（Secure Hash Algorithm，安全散列算法）。

• 其他加密算法：DES（Data Encryption Standard，数据加密标准）、AES（Advanced Encryption Standard，高级加密标准）。

应用二：唯一标识

• 图片唯一标识
  • 从图片的二进制码串开头取 100 个字节，从中间取 100 个字节，从最后再取 100 个字节，然后将这 300 个字节放到一块，通过哈希算法（比如 MD5），得到一个哈希字符串。
  • 用它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库中，这样就可以减少很多工作量。

应用三：数据校验（利用输入数据敏感性）

• BT下载原理
  • 基于 P2P 协议的。从多个机器上并行下载一个 2GB 的电影，这个电影文件可能会被分割成很多文件块（比如可以分成 100 块，每块大约 20MB）。等所有的文件块都下载完成之后，再组装成一个完整的电影文件就行了
• BT下载文件的数据检验：
  • 通过哈希算法，对 100 个文件块分别取哈希值，并且保存在种子文件中
  • 当文件块下载完成之后，通过相同的哈希算法，对下载好的文件块逐一求哈希值，然后跟种子文件中保存的哈希值比对。
  • 如果不同，说明这个文件块不完整或者被篡改了，需要再重新从其他宿主机器上下载这个文件块。

应用四：散列函数

• 散列函数关注点：
  • 不关心是否能反向解密
  • 关注散列后的值是否能平均分布
  • 关注散列算法的性能

如何防止数据库中的用户信息被脱库？

• 通过哈希算法，对用户密码进行加密之后再存储，不过最好选择相对安全的加密算法，比如 SHA 等（因为 MD5 已经号称被破解了）
• 字典攻击风险：维护一个常用密码的字典表，把字典中的每个密码用哈希算法计算哈希值，然后拿哈希值跟脱库后的密文比对。如果相同，基本上就可以认为，这个加密之后的密码对应的明文就是字典中的这个密码。
• 针对字典攻击策略：引入一个盐（salt），跟用户的密码组合在一起，增加密码的复杂度。我们拿组合之后的字符串来做哈希算法加密，将它存储到数据库中，进一步增加破解的难度。

数据结构与算法简记--哈希算法

原文：https://www.cnblogs.com/wod-Y/p/12198550.html