Hash函数

Hash函数计算的是一个消息的摘要，并且这个摘要是一个非常短、长度固定的位字符串。对某个特定的消息而言，消息摘要（或哈希值）可以看作是该消息的指纹，即消息的唯一表示。

Hash函数是一种没有密钥的加密方法，没有密钥证明Hash函数是不可逆的，即从实际计算角度出发，根据密文不能得出实际明文（因为受限于当前的计算能力，Hash结果的破解需要很长很长的时间，所以是计算不可行）。

Hash函数主要应用在数字签名和消息验证码。

为什么数字签名需要Hash函数？

在之前介绍的非对称加密与数字签名中提到过数字签名的签名生成与验证均是作用于明文数据的哈希值，为什么要这样呢？因为在所有的签名方案中（主要三大类：大素数因式分解难（RSA）、离散对数（Elgamal）以及椭圆曲线（ECC）），明文的长度都是有限的，例如在RSA中，消息长度通常在1024位～3072位之间
（128字节～384字节），但实际应用中明文长度通常超过这个范围很多，所以需要解决明文长度问题，而Hash函数便是一种解决方案。Hash函数签名过程如下图：

注意：在实际签名与验证签名的过程中，作用对象都是实际明文的哈希值，而非明文本身

Hash函数的安全性

对于Hash函数，以下三点属性需要了解：

1. 要想对任意大小的消息使用哈希函数，则哈希函数在计算上必须是高效的，即使消息大小有几百MB。
2. 哈希函数的输出长度是固定的，即对同一个哈希函数，无论消息长度是多少，哈希函数的输出长度总是固定的。
3. 哈希函数必须对所有的输入位都高度敏感，即使输入发生了很小的改变，哈希函数的输出也有很大的不同。

如下图：

为了保证安全性，Hash函数还需要拥有以下三个核心属性：

1. 抗第一原像性（或单向性）

   哈希函数必须具有单向性，即给定一个哈希输出z，找到满足z = h(x)的输入消息x在计算上必须是不可行的，即给定一个指纹，我们不可能找到对应的消息。

2. 抗第二原像性（或弱抗冲突性）

   对使用哈希的数字签名而言，确保两个不同的消息不会映射到相同的值是非常重要的，明确的说就是使用相同的哈希值 = h() = h() = 创建两个不同的消息 != 在计算上是不可行的。

   给定明文，弱冲突性就是存在的哈希值与相同，这在理论上是可行的，这里有一个有趣的原理，叫鸽巢原理：如果你有100只鸽子，却只有99个笼子，则至少有一个鸽笼会装两个鸽子。由于Hash函数的输
   出长度都是固定的，而输入的数目没有限制，所以一定会存在多个输入哈希到相同输出值的情况。但是因为哈希输出长度（比如80位）在计算上如果要计算出相同的输入，目前的计算能力需要很长的时间，所以实际应用中可
   以认为是安全的，但是随着计算能力的提升，对应Hash的输出长度也会增加，这样就衍生衍生出了很多不同算法的Hash函数，对应的输出长度也不尽相同。

3. 抗冲突性（或强抗冲突性）

   只有当找不到满足h() = h()的，时，哈希函数才是抗冲突或具有强抗冲突性，这个属性比弱抗冲突性更难获得，因为攻击者具有两方面的自由：可以更改两个消息以获得相似的哈希值。这里也有一个
   有趣的理论，叫做生日悖论，大概描述的是：至少需要多少人聚会，才能使得至少两个人拥有相同生日的概率足够高？有兴趣的话可以去详细了解以下。

基于以上内容，Hash函数具有以下属性：

1. 任意的消息大小： h(x)对任何大小的消息x都适用

2. 固定的输出长度： h(x)生成的哈希值z的长度是固定的

3. 有效性： h(x)的计算相对简单

4. 抗第一原像性： 给定一个输出z，找到满足h(x) = z的输入x是不可能，即h(x)具有单向性

5. 抗第二原像性： 给定和h()，找到满足h()=h()的在计算上是不可能的

6. 抗冲突性： 找到满足h()=h()的一对 != 在计算上是不可行的

Hash函数的构建以及分类

从构建方式来看，Hash函数主要分为两类:

1. 专用的Hash函数，专门为Hash函数设计的一些算法
2. 基于分组密码的Hash函数

Hash函数的实质是将任意长度的消息转换称固定长度的输出，所以Hash函数的核心功能是压缩，输入消息的哈希值可以定义为上一轮压缩函数的输出，如下图所示：

关于算法理论细节请参考书籍上更详细的内容，本文内容参考《深入浅出密码学——常用加密技术原理与应用》

哈希函数主要分类如下图所示:

上图内容引《自维基百科》

Hash函数实践(Golang)

package main

import (
    "crypto"
    "fmt"
    "github.com/pyihe/secret"
)

func main() {
    data := []byte("明文数据")
    s := secret.NewHasher()
    hash, err := s.HashToBytes(data, crypto.SHA256)
    if err != nil {
        fmt.Printf("exit with err: %v\n", err)
        return
    }
    base64Str, err := s.DoubleHashToString(data, crypto.SHA256)
    if err != nil {
        fmt.Printf("exit with err: %v\n", err)
        return
    }
    fmt.Printf("bytes result: %s\n", hash)
    fmt.Printf("string result: %s\n", base64Str)
}

消息验证码

消息验证码（MAC）也称为密码学校验和或密钥的哈希函数。在安全功能方面，MAC与数字签名共享一些属性，因为它们都提供消息完整性和消息验证，但是与数字签名不同的是，MAC是对称密钥方案，并且它也不提供不可否认性。

与数字签名一样，MAC也是将验证标签附加到消息后面，MAC与数字签名最大的区别就是，MAC在生成和确认验证标签的过程中使用的都是对称密钥K，即：m = (x)，MAC流程如下图所示：

发送方计算出MAC，并将消息和验证标签m一起发送给接收方，接收方收到消息x和m时将这两者进行验证，验证与发送方的操作完全相同：使用收到的消息和对称密钥重新计算并认证即可。

消息验证码具有以下属性：

1. 密码学校验和： 给定一个消息，MAC可以生成一个密码学安全的验证标签

2. 对称性： MAC基于对称密钥，签名方和验证方必须共享一个密钥

3. 任意的消息大小： MAC可以接受任意长度的消息

4. 固定的输出长度： MAC生成固定长度的验证标签

5. 消息完整性： MAC提供了消息完整性，在传输过程中对消息的任何修改都能被接收者检测到

6. 消息验证： 接收方可以确定消息的来源

7. 不具有不可否认性： 由于MAC是基于对称原理的，所以不提供不可否认性，即无法向第三方证明消息来自发送方还是接收方

HMAC

HMAC是MAC的一种实现方案，由一个内部哈希和一个外部哈希组成，如下图所示：

图中||表示连接。MAC计算首先使用0在对称密钥k的左边进行填充，直到得到的的长度为b位，其中b是哈希函数输入分组的宽度。扩展后的密钥然后与内部填充进行异或操作，直到达到长度b，其中内部填充是由下位模式的重复组成的：

ipad = 0011 0110, 0011 0110, ..., 0011 0110

异或操作的输出形成了哈希函数的第一个输入分组。后续的输入分组为消息分组(, , ..., )。

使用填充的密钥与第一个哈希的输出一起计算出第二个外部哈希，这里的密钥也需要使用0进行填充，并与外部填充进行异或操作：

opad = 0101 1100, 0101 1100, ..., 0101 1100

异或操作的结果形成了外部哈希的第一个输入分组，其他输入分组为内部哈希的输出。计算完外部哈希得到的输出就是x的消息验证码。

消息验证码实践(Golang)

package main

import (
    "crypto"
    "fmt"
    "github.com/pyihe/secret"
)

func main() {
    data := []byte("明文数据")
    key := []byte("12345678")
    s := secret.NewHasher()
    mac := s.MAC(crypto.SHA512, data, key)
    ok := s.CheckMac(crypto.SHA512, data, key, mac)
    fmt.Println(ok)
}

相关资料

《维基百科—SHA3》

《深入浅出密码学——常用加密技术原理与应用》

最后

原文链接
如有错误，欢迎指正！
Thanks!
附上代码链接[github.com/pyihe/secret]