现代密码学（六）认证与哈希函数

发表于 更新于 分类于 阅读次数：
本文字数： 1.1k

介绍认证方法与哈希函数。

认证

认证是为了防止主动攻击。

  • 实体认证（确认发送者的身份）
  • 消息认证（验证消息的完整性）

保密和认证是两个概念，纯认证的系统模型如下。

image-20201228193828037

有三种方式产生认证符

  • 消息加密
  • 消息认证码MAC
    • 需要密钥
  • 哈希函数

基于公钥体制，可以实现加密与认证。

image-20201228195806099

消息认证码 MAC

MAC对给定消息，使用一个密钥，产生一个短小的定长数据分组。

可以提供认证，因为只有通信双方共享密钥。

image-20201228200208994

也可以实现认证与保密。

image-20201228200259938

image-20201228202104394

消息认证相较于常规加密

  • 适用于消息广播
  • 认证的代价低
  • 某些应用只关心消息的真实性
  • 认证与保密的分离能提供结构上的灵活性
  • 认证码可以延长消息的保护期限，同时能处理消息内容

认证函数应抗选择明文攻击，且生成同样的认证码在计算上不可行。

可以基于DES实现MAC

  • 将消息分为连续的64bit分组

\[ \begin{align} C_1 &= E_K(M_1) \\ C_2 &= E_K(M_2\oplus C_1) \\ &\dots \\ C_n &= E_K(M_n\oplus C_{n-1}) \end{align} \]

哈希函数

哈希函数将任意长度的消息映射为较短的定长消息。

  • \(E_K(M||H(M))\)$
    • 提供保密与鉴别
  • \(M||E_K(H(M))\)$
    • 提供鉴别
  • \(M||E_{K_{R_a}}(H(M))\)$
    • 提供鉴别与数字签名

简单的哈希函数，对每个分组按bit异或（奇偶校验）。 \[ C_i = b_{i1}\oplus b_{i2}\oplus\cdots\oplus b_{im} \]

Merkle-Damgard结构

image-20201228204306226 \[ CV_i = f(CV_{i-1}, Y_{i-1}) \\ H(M) = CV_L \]

MD5

符合Merkle-Damgard结构，输入分组长度512bit，输出128bit。

  • 添加填充位，满足\(length\equiv448\bmod512\)。
  • 添加长度，用64bit表示，若超过只取低64位。
  • 使用一个128bit缓存存放结果，表示为\((A,B,C,D)\)。
  • 处理512bit的报文分组，核心是包含4个循环的压缩函数f，每个循环包括16步。
  • 所有L个51bit的分组处理后，第L个阶段的输出作为128bit摘要输出。

image-20201228205401841

image-20201228205336335

MD4有3轮，每轮16步。

MD5每轮加上前一步的结果，有雪崩效应。

SHA-1

输入最大长度为\(2^{64}\)，输出160bit，分组大小512bit。

SHA-1的函数有四轮，每轮20步。

image-20201228210321190

安全性分析

  • SHA = MD4 + 扩展变换 + 外加一轮 + 更好的雪崩
  • MD5 = MD4 + 改进的比特杂凑 + 外加一轮 + 更好的雪崩

image-20201228210617475

哈希函数可以受到野蛮攻击和生日攻击

k个人中，至少存在两人生日相同的概率为 \[ P(365, k) = 1 - \frac {365!} {(365-k)365^k} \]