# 哈希算法

: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