哈希算法

：Hash algorithm ，又称为散列函数。用于将一段数据映射到一个接近随机的值，称为散列值、哈希值、摘要值。

• 常用于检验数据的一致性。
  • 例如根据一个文件的哈希值是否变化，能判断该文件的内容是否变化。
  • 例如 Web 服务器不储存用户的明文密码，而是储存密码的哈希值。如果用户输入的密码的哈希值与数据库中存储的哈希值一致，则判断密码正常。这样连网站管理员都看不到用户的明文密码，避免泄露。
• 哈希算法存在多种类型，通常将哈希算法用于加密领域，不过也有图片哈希算法等其它类型。
• 哈希算法并不属于加密算法，使用哈希值只能避免泄露数据原文，但不能从哈希值反推出数据原文。

原理

哈希算法有多种，通常具有以下特点：

• 正向快速：输入一段任意长度的数据，会快速输出一个固定长度的、取值难以预测的数据。
  • 通常在二进制格式下进行哈希运算。例如将图片等文件转换成二进制流，再计算哈希值。
  • 通常将输出的哈希值转换成十六进制，便于阅读。
• 逆向困难：如果只知道一个数据的哈希值，则难以据此反推出原数据的内容。
  • 因为理论上生成同一个哈希值的原数据可能有无数种。想反推出原数据，除非哈希算法存在容易被反推的缺陷，或者建立一个庞大的数据库，存储常见的一些数据的哈希值。
• 确定性：如果两个输入数据相同，则它们的哈希值一定相同。
  • 在计算机上编辑图片等文件时可能会自动加上时间信息等内容，导致最后保存的文件内容看起来一样，实际上二进制数据并不一样，因此哈希值不同。
• 抗碰撞性：很难找到两个不同的输入数据，映射到相同的哈希值。
  • 如果哈希值相同，则称为发生碰撞。
  • 哈希算法的碰撞率越低越好。这需要哈希值的取值空间大，并且映射的哈希值均匀分布。
  • 例如 MD5 生成 128 位的哈希值，而 SHA256 生成 256 位的哈希值，取值空间更小，因此碰撞率更低。
• 输入敏感：如果两个输入数据不同，即使只有一个 bit 的差异，哈希值也会有很大差异。

存储方案

通过哈希算法检验大量数据（比如大量文件）的一致性时，常见的存储方案：

• 哈希列表（Hash List）

  • 原理：
    1. 计算每个数据的哈希值，保存为一个列表。
    2. 记录该列表的哈希值，用于检验整体的一致性。
  • 当发现整个 Hash List 的哈希值变化时，需要遍历检验每个数据的哈希值是否变化，从而找出变化的数据。时间复杂度为 O(n) 。

• 哈希链（Hash Chain）

  

  • 原理：
    1. 计算每个数据的哈希值。
    2. 将两个数据的哈希值组合，计算哈希值，再与下一个数据的哈希值组合，计算哈希值。以此类推，最后得到链尾的哈希值。
  • 如果任一节点的哈希值发生变化，则在哈希链中，其后所有节点的哈希值都会变化。

• 哈希树（Hash Tree）：又称为默克尔树（Merkle Tree）

  

  • 原理：
    1. 计算每个数据的哈希值，存放在二叉树的叶子节点。
    2. 父节点存放了其下所有子节点组合之后的哈希值。
  • 从一个叶子节点到根节点的路径称为 Merkle 路径。
  • 任一节点变化，都会导致根节点的哈希值变化。
    • 当发现根节点的哈希值变化时，需要按二分法检验子孙节点的哈希值是否变化，从而找出变化的节点。时间复杂度为 O(logn) ，效率较高。
  • 假设哈希值存储在其它主机上，则采用 Hash List、Hash Chain 时，本机需要下载所有数据的哈希值用于遍历检验。而采用 Merkle Tree 时，本机只需下载 Merkle 路径上相关节点的哈希值用于检验，开销更低。

MD5

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

• 于 1992 年发布，生成 128 位的哈希值。
• 存在容易被碰撞攻击的漏洞，安全性差。但生成速度快，依然可以用于非安全用途。

SHA

：安全哈希算法（Secure Hash Algorithm）

• 由美国国家安全局发布，分为几个版本：
  • SHA-1 ：于 1995 年发布，会生成 160 位的哈希值。安全性较差，可能被碰撞攻击。
  • SHA-2 ：于 2001 年发布。常用的是 SHA-256、SHA-512 ，分别生成 256、512 位的哈希值。安全性更高，但是生成速度较慢。
  • SHA-3 ：于 2015 年发布。

♢ Hashlib

：Python 的标准库，提供了实现 MD5、SHA1、SHA256、SHA512 等常见哈希算法的函数。

• 例：

  >>> import hashlib
  >>> h = hashlib.sha256()          # 创建一个 Hash 对象
  >>> h.update("Hello".encode())    # 输入要 Hash 的内容（必须转换成 bytes 类型）
  >>> h.update("World".encode())    # 可以累加
  >>> h.digest()                    # 生成哈希值（ bytes 类型）
  b'\x87.NP\xce\x99\x90\xd8\xb0A3\x0cG\xc9\xdd\xd1\x1b\xeckP:\xe98j\x99\xda\x85\x84\xe9\xbb\x12\xc4'
  >>> h.hexdigest()                 # 生成十六进制的哈希值（ str 类型）
  '872e4e50ce9990d8b041330c47c9ddd11bec6b503ae9386a99da8584e9bb12c4'
  >>> hashlib.sha256("HelloWorld".encode()).hexdigest()      # 可简化成一步
  '872e4e50ce9990d8b041330c47c9ddd11bec6b503ae9386a99da8584e9bb12c4'
  

• 在哈希时加盐：

  import os
  salt       = os.urandom(10)       # 生成指定字节数的随机 bytes 对象
  password   = '123456'.encode()
  Hash_bytes = salt + password
  result     = hashlib.sha256(Hash_bytes).hexdigest()
  

  • 用 Python 的 random 模块生成的随机数是不安全的，此处应该用 os.urandom() 函数生成随机数。

♢ hmac

：Python 的标准库，提供了实现 hmac 算法的函数。

• hmac 算法使用一个密钥搭配一个哈希算法来计算哈希值，比单纯的哈希加盐更难以预测。
• 例：

  >>> import hmac
  >>> key = os.urandom(10)
  >>> msg = '123456'.encode()
  >>> hmac.new(key, msg, 'sha256').hexdigest()
  '62f33c9d8af25adb6ca6180f9351618084de7d95d5f2689489700f48f982bae6'
  >>> hmac.compare_digest(b'123', b'123')    # 比较两个数据的哈希值是否相同
  True