散列函数与消息鉴别

博主： Xherlock
发布时间：2022 年 06 月 04 日
452 次浏览
暂无评论
1838字数
分类：密码学

# 散列函数与消息鉴别

## 散列函数

哈希函数，一种单向密码体制，从明文到密文的不可逆映射，只有加密过程，没有解密过程

散列函数作用：M（输入消息）&longrightarrow;MD（消息摘要/散列码）

作用：生成文件或者其他数据块的“数字指纹”

### 性质

**基本特性**

* h(m)算法公开，不需要密钥
* 具有数据压缩功能，可将任意长度的输入数据转换为一个固定长度的输出
* 对任何给定的m，h(m)易于计算

**安全性要求**

* 单向性：给定散列值h(m)，求得m在计算上不可行
* 弱抗碰撞性：对任意给定消息m，寻找与m不同的消息m'使得它们的散列值相等，在计算上不可行
* 强抗碰撞性：寻找任意两个不同的消息m和m'，使得两者散列值相等，在计算上不可行

碰撞攻击：两个不同的消息产生了相同的哈希值（必然存在冲突）

### 应用

* 保证数据的完整性：验证散列码是否相等
* 单向数据加密：口令表存储散列值进行对比验证
* 数字签名：提高签名速度，不泄露原始消息

## 散列函数的构造和设计

### 简单的散列函数

![E526488BA919AEC403644682D1F4D227.png](http://xherlock.top/usr/uploads/2022/06/2905200746.png)

特点：简单高效

攻击方法：第二原像攻击（不满足弱抗碰撞）

![DF469AB0A5F5067654BD05B74D76093A.png](http://xherlock.top/usr/uploads/2022/06/3552590595.png)

### 迭代型散列函数

![image-20220604165718209.png](http://xherlock.top/usr/uploads/2022/06/3868432963.png)

使用基于对称分组密码的CBC/CFB工作模式（使用公钥密码算法计算效率太低，无实用价值）

密钥k不能公开，否则会使得攻击者构造消碰撞十分容易

以CBC模式公开密钥下的攻击为例：

![image-20220604170443794.png](http://xherlock.top/usr/uploads/2022/06/1035020919.png)

当然也有直接设计散列函数的，不基于任何假设和密码体制，通过构造复杂的非线性关系达到单向性要求（有MD2\~5、SHA系列）

## 安全散列算法SHA

### SHA1

NIST（美国国家标准与技术研究院）发布的数字签名标准DSS中使用的散列算法

大端存储

输入：最大长度为$2^{64}-1$位

输出：160位消息摘要

处理：输入以512位数据块为单位处理

1. 消息分割和填充

**最后一个报文分组**

![image-20220604171513730.png](http://xherlock.top/usr/uploads/2022/06/3738502451.png)
2. 初始化缓冲区：使用5个32位的字单元作为计算MD的缓存

A=67452301    B=EFCDAB89    C=98BADCFE    D=10325476    E=C3D2E1F0
3. 以512位一组处理消息

![image-20220604172252453.png](http://xherlock.top/usr/uploads/2022/06/1028896348.png)

**SHA系列算法比较**

| **算法** | **消息长度** | **分组长度** | **字长** | **散列值长** | **使用常数** | **基本函数** | **处理步骤** |
| ---------- | -------------- | -------------- | ---------- | -------------- | -------------- | -------------- | -------------- |
| SHA-1    | <264         | 512          | 32       | 160          | 4×32        | 4            | 80           |
| SHA-256  | <264         | 512          | 32       | 256          | 64×32       | 6            | 64           |
| SHA-384  | <2128        | 1024         | 64       | 384          | 80×32       | 6            | 80           |
| SHA-512  | <2128        | 1024         | 64       | 512          | 80×32       | 6            | 80           |

## 对散列函数的攻击

### 生日悖论和生日攻击

随机23人中，至少有两人生日相同的概率为0.5

实测如下（还真两次都出现相同生日的了）

![image-20220604180047695.png](http://xherlock.top/usr/uploads/2022/06/3200050117.png)

转换成攻击描述：给定一个散列函数H(x)，有n个可能的输出；若H有k个随机输入，问k必须取多大才能使至少存在一个碰撞的概率大于0.5

![image-20220604180535462.png](http://xherlock.top/usr/uploads/2022/06/1461207021.png)

## 消息鉴别

鉴别是指在两个通信者之间建立通信联系后，每个通信者对收到信息进行验证，以保证收到信息的真实性，确保：

* 报文是由确认的发送方产生的
* 报文内容没有被篡改过
* 报文是按与发送时的相同顺序收到的

### 基于加密技术的消息鉴别

#### 利用对称加密体制实现

![image-20220604193409336.png](http://xherlock.top/usr/uploads/2022/06/830194207.png)

局限性：需要接收方有某种方法能判定解密出的明文是否合法

#### 利用公钥密码体制实现

**提供消息鉴别**

![D01F368F962F5E2EE9B340F953DEF2DC.png](http://xherlock.top/usr/uploads/2022/06/1948184169.png)

注意：发送方使用自己的**私钥**加密！！！（和正常公钥密码体制中用公钥加密不一样）

能够实现数字签名，抗抵赖，提供鉴别

**提供消息鉴别和机密性保护**

![E34AEB546A1573F274BBAD354D647A54.png](http://xherlock.top/usr/uploads/2022/06/1519599824.png)

### 基于散列函数的消息鉴别

#### 消息鉴别码

报文/消息鉴别码（MAC）用于提供数据原发鉴别和数据完整性的密码校验值

一个MAC算法由一个秘密密钥k和参数化的一簇函数hk构成，函数性质如下：

* 容易计算
* 压缩：hk把任意具有有限长度的一个输入x映射成一个具有固定长度的输出hk(x)
* 强抗碰撞性

![EFC921B47A8FEE6DAD5B19A34D3992E7.png](http://xherlock.top/usr/uploads/2022/06/3270420425.png)

**MAC函数无需可逆**，因为整个过程中不需要解密

上图所示方法只能提供消息鉴别，不能提供机密性（消息以明文传输）

*以下两种方式提供机密性*

![7F73D79EA6F0ACA5FE5B8DA4BBBFD128.png](http://xherlock.top/usr/uploads/2022/06/2788935823.png)

#### 基于散列函数的消息鉴别

![3BBC7BC6022371A5570AAAE8218E63A1.png](http://xherlock.top/usr/uploads/2022/06/1479340289.png)

### HMAC算法

带密钥的单向散列函数

最后修改：2022 年 06 月 04 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

Reverse（十一）
浏览次数: 2629
Win11新机鼓捣记录
浏览次数: 2382
栈~数制转换
浏览次数: 1604
C++学习
浏览次数: 1603
Python实现文件管理系统（重命名和删除）
浏览次数: 1575

顶点软件
你写得非常清晰明了，让我很容易理解你的观点。
mars
博主你好，请问怎么知道的alloc函数属于Buffer下的方法...
lj
该评论仅登录用户及评论双方可见
Mr.Guan
:@(赞一个)
Typecho
欢迎加入 Typecho 大家族

ASCII艺术签名绘图
浏览次数: 855
文件管理
浏览次数: 454
密钥管理技术
浏览次数: 424
Sqli-labs学习4
浏览次数: 826
运输层（二）
浏览次数: 501

散列函数与消息鉴别

Xherlock • 2022 年 06 月 04 日

# 散列函数与消息鉴别

## 散列函数

哈希函数，一种单向密码体制，从明文到密文的不可逆映射，只有加密过程，没有解密过程

散列函数作用：M（输入消息）&longrightarrow;MD（消息摘要/散列码）

作用：生成文件或者其他数据块的“数字指纹”

### 性质

**基本特性**

* h(m)算法公开，不需要密钥
* 具有数据压缩功能，可将任意长度的输入数据转换为一个固定长度的输出
* 对任何给定的m，h(m)易于计算

**安全性要求**

碰撞攻击：两个不同的消息产生了相同的哈希值（必然存在冲突）

### 应用

* 保证数据的完整性：验证散列码是否相等
* 单向数据加密：口令表存储散列值进行对比验证
* 数字签名：提高签名速度，不泄露原始消息

## 散列函数的构造和设计

### 简单的散列函数

![E526488BA919AEC403644682D1F4D227.png](http://xherlock.top/usr/uploads/2022/06/2905200746.png)

特点：简单高效

攻击方法：第二原像攻击（不满足弱抗碰撞）

![DF469AB0A5F5067654BD05B74D76093A.png](http://xherlock.top/usr/uploads/2022/06/3552590595.png)

### 迭代型散列函数

![image-20220604165718209.png](http://xherlock.top/usr/uploads/2022/06/3868432963.png)

使用基于对称分组密码的CBC/CFB工作模式（使用公钥密码算法计算效率太低，无实用价值）

密钥k不能公开，否则会使得攻击者构造消碰撞十分容易

以CBC模式公开密钥下的攻击为例：

![image-20220604170443794.png](http://xherlock.top/usr/uploads/2022/06/1035020919.png)

当然也有直接设计散列函数的，不基于任何假设和密码体制，通过构造复杂的非线性关系达到单向性要求（有MD2\~5、SHA系列）

## 安全散列算法SHA

### SHA1

NIST（美国国家标准与技术研究院）发布的数字签名标准DSS中使用的散列算法

大端存储

输入：最大长度为$2^{64}-1$位

输出：160位消息摘要

处理：输入以512位数据块为单位处理

1. 消息分割和填充

**最后一个报文分组**

![image-20220604171513730.png](http://xherlock.top/usr/uploads/2022/06/3738502451.png)
2. 初始化缓冲区：使用5个32位的字单元作为计算MD的缓存

A=67452301    B=EFCDAB89    C=98BADCFE    D=10325476    E=C3D2E1F0
3. 以512位一组处理消息

![image-20220604172252453.png](http://xherlock.top/usr/uploads/2022/06/1028896348.png)

**SHA系列算法比较**

## 对散列函数的攻击

### 生日悖论和生日攻击

随机23人中，至少有两人生日相同的概率为0.5

实测如下（还真两次都出现相同生日的了）

![image-20220604180047695.png](http://xherlock.top/usr/uploads/2022/06/3200050117.png)

转换成攻击描述：给定一个散列函数H(x)，有n个可能的输出；若H有k个随机输入，问k必须取多大才能使至少存在一个碰撞的概率大于0.5

![image-20220604180535462.png](http://xherlock.top/usr/uploads/2022/06/1461207021.png)

## 消息鉴别

鉴别是指在两个通信者之间建立通信联系后，每个通信者对收到信息进行验证，以保证收到信息的真实性，确保：

* 报文是由确认的发送方产生的
* 报文内容没有被篡改过
* 报文是按与发送时的相同顺序收到的

### 基于加密技术的消息鉴别

#### 利用对称加密体制实现

![image-20220604193409336.png](http://xherlock.top/usr/uploads/2022/06/830194207.png)

局限性：需要接收方有某种方法能判定解密出的明文是否合法

#### 利用公钥密码体制实现

**提供消息鉴别**

![D01F368F962F5E2EE9B340F953DEF2DC.png](http://xherlock.top/usr/uploads/2022/06/1948184169.png)

注意：发送方使用自己的**私钥**加密！！！（和正常公钥密码体制中用公钥加密不一样）

能够实现数字签名，抗抵赖，提供鉴别

**提供消息鉴别和机密性保护**

![E34AEB546A1573F274BBAD354D647A54.png](http://xherlock.top/usr/uploads/2022/06/1519599824.png)

### 基于散列函数的消息鉴别

#### 消息鉴别码

报文/消息鉴别码（MAC）用于提供数据原发鉴别和数据完整性的密码校验值

一个MAC算法由一个秘密密钥k和参数化的一簇函数hk构成，函数性质如下：

* 容易计算
* 压缩：hk把任意具有有限长度的一个输入x映射成一个具有固定长度的输出hk(x)
* 强抗碰撞性

![EFC921B47A8FEE6DAD5B19A34D3992E7.png](http://xherlock.top/usr/uploads/2022/06/3270420425.png)

**MAC函数无需可逆**，因为整个过程中不需要解密

上图所示方法只能提供消息鉴别，不能提供机密性（消息以明文传输）

*以下两种方式提供机密性*

![7F73D79EA6F0ACA5FE5B8DA4BBBFD128.png](http://xherlock.top/usr/uploads/2022/06/2788935823.png)

#### 基于散列函数的消息鉴别

![3BBC7BC6022371A5570AAAE8218E63A1.png](http://xherlock.top/usr/uploads/2022/06/1479340289.png)

### HMAC算法

带密钥的单向散列函数

发表评论 取消回复

散列函数与消息鉴别

发表评论取消回复