学不完了学不完了学不完了

密码学还有大作业,设计加密算法,到现在还没有着落,课又有两三节没听了,赶紧补赶紧补

本篇内容包括:

  • § 8:密码 Hash 函数
  • § 9:消息认证码

密码 Hash 函数

Hash 函数基础

Hash 函数与压缩函数

定义(Hash 函数):Hash 函数 $H: \{0, 1\}^{\star} \rightarrow \{ 0, 1 \}^l$,将任意长的消息压缩为一个固定长度的摘要,记作 $Y = H(M)$。

定义(压缩函数):将固定长度的消息 M 压缩成一个固定长度的输出 $f: \{0, 1\}^{m+l} \rightarrow \{ 0, 1 \}^l$.

Hash 函数属性

  • 有效性:已知消息 $M$,计算消息指纹 $Y=H(M)$ 是容易的。
  • 抗原像攻击:给定任意消息指纹 $Y=H(M)$,恢复消息 $M$ 是计算不可行的。
    • 理想的复杂度是搜索攻击 $2^n$ 次计算
  • 抗第二原像攻击:给定任意消息 $M_1$,找到另一个消息 $M_2$ 具有相同电子指纹 $H(M_1)=H(M_2)$ 是计算不可行的。
    • 理想的复杂度是 $2^n$
  • 无碰撞性:找到不同的消息 $(M_1, M_2)$ 有相同的指纹 $H(M_1)=H(M_2)$ 是计算不可行的。
    • 生日攻击复杂度 $2^{n/2}$

MD 迭代结构

大多数 Hash 函数的设计采用迭代结构,每次处理一个固定程度的消息分组。这便是基于压缩函数的 MD 设计准则。

Mekle’s meta-迭代算法
  • 输入:无碰撞的压缩函数 $f$
  • 输出:无碰撞的 Hash 函数 $h$
  1. 假设 $f$ 把 $(n+r)$ bit 的输入映成 n 比特的输出(例如 $n=128, r=512$ )。由 $f$ 构造一个具有 $n$ 比特杂凑值的 Hash 函数如下。
  2. 把长度为 $b$ 的输入 $x$ 分解成 $t$ 个长度为 $r$ 比特的分组 $x_1x_2\cdots x_t$。假如 $b$ 不是 $r$ 的倍数,则在 $x_t$ 的后面添充上若干个 0,使其成为一个完整的消息分组。
  3. 添加最后的一个分组 $x_{t+1}$,它是 $b$ 的长度的二进制表示(假设 $b<2r$)
  4. 归纳定义 $n$ bit 的散列值计算:$H_0 = 0^n; \ H_i = f(H_{i-1} || x_i), 1 \le i \le t+1; \ h = H_{t+1}$.

证明 若 $f$ 是无碰撞的,则 $h$ 是无碰撞的。可考虑逆否命题,假设 $\exist M_1 \ne M_2, h(M_1) = h(M_2)$,则根据归纳定义的过程,

常用迭代结构
Wide-pipe 结构

image-20220430112632600

Sponge 结构

image-20220430112859041

Hash 函数算法

MD5 算法

image-20220430114535918

① Padding. 填充消息至 $448 + 512 \times k$ bit,即使消息本身满足长度要求也要填充,即填充长度需要在 $1 - 512$ bit 之间。

② 在结尾增加 64 Bit 的报文长度。

③ 初始化 MD 缓存。(低位优先)

④ 以 512 Bit 为单位分组处理消息。

⑤ 输出。

其压缩函数 $f$ 可表示为:

image-20220430133451882

每个框中有 16 次单步计算,单步计算的流程为:

image-20220430133959441

$K_i$ 使用正弦函数生成:

image-20220430134200888

$M_i$ 是输入的 32 bit 的数据(因为 512 / 32 = 16,所以需要 16 次单步计算)

SHA-1

SHA-1 算法也将消息按照 512 位分组,但 Hash 值长为 160 位。

① Padding to $448 + k \times 512$ bit.

② 填充 64 bit 长度信息。

③ 初始化 MD 缓存。(高位优先)

④ 以 512 Bit 为单位分组处理消息。

⑤ 输出。

那么,它是怎么以 512 bit 为单位处理消息的呢?

image-20220430143232047

每一次循环以当前正在处理的 512 bit($Y_q$)和 160 bit 的缓存值(ABCDE)为输入,进而更新缓存中的内容。每个循环使用一个额外的常数值 $K_t$,其中 $0 \le t \le 79$.

然后我们来看下 SHA-1 的压缩函数。

image-20220430143625147

其他加密算法

  • SHA-2 family
  • SM3

Hash 的攻击

生日攻击

定理(生日攻击) 若 $k \ge 2^{n/2}$,则 $k$ 个在 $[1, 2^n]$ 中的随机数有两个相同的概率不低于 0.5.

Remark 生日攻击可以用于伪造数字签名。对两份不同的文件 A, B 分别作 $\frac n 2$ 次扰动,选择扰动后 $A’$ 与 $B’$ Hash 值相同,将 B’ 发送给对方获得签名,即获得了 A’ 的签名。

寻找碰撞的其他方法

  • 穷举搜索
  • 生日攻击
  • 随机路径算法
  • Nivasch Algorithm

消息认证码与认证加密算法

网络通信威胁:我们需要对消息完整性消息源进行认证。

认证的功能

  • 用于验证消息的完整性,未被篡改、插入或删除
  • 用于验证消息的来源(真实性)
  • 用于验证消息的顺序性和时间性
  • 用于验证消息的不可否认性
    • 防止通讯双方中的某一方对所传输消息的否认

消息完整性的认证

加密算法不能提供消息完整性认证,实现消息的完整性认证必须有以下方法:

  • Hash 函数 + 可信通道
  • Hash 函数 + 加密算法
  • 消息认证码

image-20220430150015669

消息认证码 MAC

消息认证码是在密钥的控制下,将任意长的消息映射为一个固定长度的短数据分组。

消息认证码的参数:密钥的长度 $k$,输出标签长度 $n$.

image-20220430150512453

消息认证码的构造

密钥前缀方案:基于 MD 迭代结构

缺点:长度扩展攻击,攻击者可以在消息的尾部增加一个新的消息分组,伪造一个新的 MAC $(M||S, newtag)$

密钥前缀方案:基于 MD 增强结构 Hash

image-20220430151153962

缺点:长度扩展攻击,攻击者仍然可以在消息的尾部增加一个新的消息分组,伪造一个新的 MAC $(M||pad||S, newtag) $.

密钥后缀方案

image-20220430155432819