密码学（哈希函数）

4.1 Hash函数与数据完整性

数据完整性：
检测传输消息（加密或未加密）的修改。

密码学Hash函数：
构建某些数据的简短“指纹”；如果数据被篡改，则该指纹（以高概率）不再有效。Hash函数的一个特别重要的应用是数字签名方案的上下文中。

消息摘要：
设 $h (x)$ 是一个Hash函数， $x$ 是某些数据。对应的指纹定义为 $y = h (x)$ 。这个指纹通常被称为消息摘要。
消息摘要是一个相对较短的二进制字符串，例如160位或256位。

Hash函数族：
带密钥的Hash函数族。对于每个可能的密钥，都有一个不同的Hash函数。
在不安全的信道中，Alice向Bob发送一对 $(x, y)$ ，其中 $y=h_K(x)$ 。
有效的配对 $(x, y)$ 满足 $h (x) = y$ 。

定义 5.1： 一个Hash函数族是一个四元组 $(\mathcal{X}, \mathcal{Y}, \mathcal{K}, \mathcal{H})$ ，满足以下条件：

$\mathcal{X}$ 是可能的消息集合
$\mathcal{Y}$ 是可能的消息摘要或认证标签（或简称标签）的有限集合
$\mathcal{K}$ ，即密钥空间，是可能的密钥的有限集合
对于每个 $\in \mathcal{K}$ ，存在一个Hash函数 $h_K \in \mathcal{H}$ 。每个 $h_K : \mathcal{X} \rightarrow \mathcal{Y}$ 。

在上述定义中， $\mathcal{X}$ 可以是一个有限集或无限集； $\mathcal{Y}$ 总是一个有限集。如果 $\mathcal{X}$ 是一个有限集且 $\mathcal{X} > \mathcal{Y}$ ，该函数有时被称为压缩函数。在这种情况下，我们通常会假设一个更强的条件，即 $|\mathcal{X}| \geq 2|\mathcal{Y}|$ 。

4.2 哈希函数的安全性

如果一个哈希函数被认为是安全的，那么以下三个问题应该难以解决：

原像问题（Preimage）
第二原像问题（Second Preimage）
碰撞问题（Collision）

问题 5.1：原像问题

实例： 给定一个哈希函数 $\mathcal{X} \rightarrow \mathcal{Y}$ 和一个元素 $\in \mathcal{Y}$ 。

求解： 找到一个 $\in \mathcal{X}$ 使得 $h (x) = y$ 。

问题 5.2：第二原像问题

实例： 给定一个哈希函数 $\mathcal{X} \rightarrow \mathcal{Y}$ 和一个元素 $\in \mathcal{X}$ 。

求解： 找到一个 $\in \mathcal{X}$ ，使得 $\neq x$ 且 $h (x^{'}) = h (x)$ 。

问题 5.3：碰撞问题

实例： 给定一个哈希函数 $\mathcal{X} \rightarrow \mathcal{Y}$ 。

求解： 寻找 $\in \mathcal{X}$ ，使得 $\neq x$ 且 $h (x^{'}) = h (x)$ 。
在这里插入图片描述

如果一个哈希函数的原像问题无法高效解决，通常称其为单向的或原像抗性的。
如果一个哈希函数的第二原像问题无法高效解决，通常称其为第二原像抗性的。
如果一个哈希函数的碰撞问题无法高效解决，通常称其为抗碰撞的。
$\text{抗碰撞性} \implies \text{原像抗性} \land \text{第二原像抗性}$

随机预言模型（Random Oracle Model）——一种理想化的模型

如果一个哈希函数设计良好，那么唯一高效确定给定输入 $x$ 的哈希值 $h (x)$ 的方法是实际计算函数 $h$ 在 $x$ 处的值。

随机预言模型示例（该性质不成立）：

随机预言模型（由 Bellare 和 Rogaway 提出）

一个哈希函数 $\rightarrow Y$ 是随机选择的，我们只能通过预言机访问该函数 $h$ 。
我们没有公式或算法来计算函数 $h$ 的值。
计算值 $h (x)$ 的唯一方法是查询预言机。
在现实生活中，真正的随机预言机是不存在的。

随机预言模型中的算法

我们展示和分析的算法是随机算法；它们在执行过程中可以做出随机选择。
拉斯维加斯算法（Las Vegas algorithm）是一种随机算法，它可能会失败（即，它可能会以“失败”消息终止），但如果算法返回答案，则答案必须是正确的。

定理 5.1 假设 $\in \mathcal{F}^{\mathcal{X},\mathcal{Y}}$ 是随机选择的，并且设 $\mathcal{X}_0 \subseteq \mathcal{X}$ 。记 $|\mathcal{Y}| = M$ 。假设 $h (x)$ 的值仅当 $\in \mathcal{X}_0$ 时通过查询 $h$ 的预言机来确定。那么对于所有 $\in \mathcal{X} \setminus \mathcal{X}_0$ 和所有 $\in \mathcal{Y}$ ，有 $\Pr[h(x) = y] = \frac{1}{M}$ 。

算法 5.1：FIND-PREIMAGE(h, y, Q)
选择任意 $\mathcal{X}_0 \subseteq \mathcal{X}$ ， $|\mathcal{X}_0| = Q$
对于每个 $\in \mathcal{X}_0$
如果 $h (x) = y$ 则返回 $(x)$
返回 $(失败)$

该算法试图找到一个输入 $x$ ，使得其哈希值等于给定的 $y$ 。

定理 5.2
对于任意 $\mathcal{X}_0 \subseteq \mathcal{X}$ 且 $|\mathcal{X}_0| = Q$ ，算法 5.1 的平均成功概率为 $\epsilon = 1 - (1 - 1/M)^Q$ 。
该定理描述了算法 5.1 在给定条件下的平均成功概率。

算法 5.2：FIND-SECOND-PREIMAGE(h, x, Q)
$\leftarrow h(x)$
选择 $\mathcal{X}_0 \subseteq \mathcal{X} \setminus \{x\}$ ， $|\mathcal{X}_0| = Q - 1$
对于每个 $x_0 \in \mathcal{X}_0$
如果 $h(x_0) = y$ 则返回 $x_0)$
返回 $(失败)$

该算法试图找到一个不同于 $x$ 的输入 $x^{'}$ ，使得其哈希值等于 $x$ 的哈希值。

定理 5.3
对于任意 $\mathcal{X}_0 \subseteq \mathcal{X} \setminus \{x\}$ 且 $|\mathcal{X}_0| = Q - 1$ ，算法 5.2 的成功概率为 $\epsilon = 1 - (1 - 1/M)^{Q-1}$ 。

以下是对每个图片内容的介绍，使用中文和Markdown格式，并且按照您的要求使用数学公式和符号：

算法 5.3：FIND-COLLISION(h, Q)
选择 $\mathcal{X}_0 \subseteq \mathcal{X}, |\mathcal{X}_0| = Q$
对于每个 $\in \mathcal{X}_0$
执行 $y_x \leftarrow h(x)$
如果 $y_x = y_{x'}$ 对于某个 $\neq x$
则返回 $(x, x^{'})$
否则返回 $(失败)$
该算法试图找到两个不同的输入 $x$ 和 $x^{'}$ ，使得它们的哈希值相同，即找到碰撞。

定理 5.4
对于任意 $\mathcal{X}_0 \subseteq \mathcal{X}$ 且 $|\mathcal{X}_0| = Q$ ，算法 5.3 的成功概率为
$\epsilon = 1 - \left(\frac{M-1}{M}\right)\left(\frac{M-2}{M}\right)\cdots\left(\frac{M-Q+1}{M}\right).$

该定理描述了算法 5.3 在给定条件下的成功概率。

碰撞概率估计
使用此估计，找到没有碰撞的概率大约为
$\prod_{i=1}^{Q-1} \left(1 - \frac{i}{M}\right) \approx \prod_{i=1}^{Q-1} e^{-\frac{i}{M}} = e^{-\sum_{i=1}^{Q-1} \frac{i}{M}} = e^{\frac{-Q(Q-1)}{2M}}.$
因此，我们可以估计找到至少一个碰撞的概率为
$e^{\frac{-Q(Q-1)}{2M}}.$

这段内容提供了找到至少一个碰撞的概率估计。

碰撞概率估计（忽略 $- Q$ 项）

如果我们忽略 $- Q$ 项，那么我们估计
$\approx \sqrt{2M \ln \frac{1}{1-\epsilon}}.$
如果我们取 $\epsilon = 0.5$ ，那么我们的估计是
$\approx 1.17 \sqrt{M}.$

这段内容提供了在特定条件下的碰撞概率估计，特别是当 $\epsilon = 0.5$ 时的估计值。

迭代哈希函数
在这里插入图片描述

迭代哈希函数：将压缩函数扩展为具有无限定义域的哈希函数 $h$ 。
预处理步骤必须确保映射是单射（injective）。
迭代哈希函数的处理步骤。

Merkle-Damgård 构造

Merkle-Damgård 构造
- 这种构造被用于设计许多流行的哈希算法，例如 MD4、MD5、SHA-1 和 SHA-2。
- 如果压缩函数满足某些安全属性（例如抗碰撞性），那么得到的哈希函数也满足这些属性。
- $x_{k+1} \text{应该在左侧填充零，使得} x_{k+1} = t - 1$
- 如果可以为 $h$ 找到碰撞，那么也可以为压缩函数找到碰撞。换句话说，只要压缩函数是抗碰撞的， $h$ 就是抗碰撞的。
- 当 $t = 1$ 时， $h$ 是抗碰撞的，前提是压缩函数是抗碰撞的。

假设存在一个压缩函数 $\text{compress} : \{0,1\}^{m+t} \rightarrow \{0,1\}^{m}$ （其中 $\geq 1$ ）。我们将基于这个压缩函数构建一个迭代哈希函数
$\bigcup_{i=m+t+1}^{\infty} \{0,1\}^i \rightarrow \{0,1\}^\ell,$
哈希函数 $h$ 的计算包括以下三个主要步骤：

预处理步骤
给定一个输入字符串 $x$ ，其中 $\geq m+t+1$ ，构造一个字符串 $y$ ，使用一个公共算法，使得 $\equiv 0 (\text{mod } t)$ 。记作
$y=y_{1}\|y_{2}|\cdots|y_{r},$
其中 $y_{i}|=t$ 对于 $1\leq i\leq r$ 。

一个常用的预处理步骤是按照以下方式构造字符串 $y$ ：
$\| \text{pad}(x),$
其中 $\text{pad}(x)$ 是使用一个填充函数从 $x$ 构造的。一个填充函数通常结合 $∣ x ∣$ 的值，并用额外的位（例如零）填充结果，使得结果字符串 $y$ 的长度是 $t$ 的倍数。

其中 $\text{pad}(x)$ 是使用填充函数从 $x$ 构造的。一个填充函数通常结合 $∣ x ∣$ 的值，并用额外的位（例如零）填充结果，使得结果字符串 $y$ 的长度是 $t$ 的倍数。

处理步骤
设 $\text{IV}$ 是一个公共初始值，它是一个长度为 $m$ 的比特串。然后计算以下内容：
$\begin{align*} z_{0} &\leftarrow \text{IV} \\ z_{1} &\leftarrow \text{compress}(z_{0} \| y_{1}) \\ z_{2} &\leftarrow \text{compress}(z_{1} \| y_{2}) \\ & \vdots \\ z_{r} &\leftarrow \text{compress}(z_{r-1} \| y_{r}). \end{align*}$

输出转换
设 $\{0,1\}^{m} \rightarrow \{0,1\}^{\ell}$ 是一个公共函数。定义 $h(x) = g(z_{r})$ 。
备注输出转换是可选的。如果不希望进行输出转换，则定义 $h(x) = z_{r}$ 。

例子

参数设置

压缩函数：
$\text{compress} : \{0,1\}^{m + t} \rightarrow \{0,1\}^{m}, \quad m=4,\; t=4$
压缩函数将8位输入压缩为4位输出。
初始值：
$\text{IV}=1111$
输出转换函数：
$g(z_r)=z_r$ （即直接输出压缩结果，不作额外转换）。

输入示例

假设输入字符串：
$\quad (\text{长度 }12\text{ 位},\; |x|=12)$

预处理步骤

目标：构造字符串 $y$ ，使其长度是 $t = 4$ 的倍数。

原长度 $∣ x ∣ = 12$ ，已满足条件（无需填充）。
分割为 $r = 3$ 个4位块：
$y_1 = 1010,\; y_2 = 1101,\; y_3 = 0011$

处理步骤

逐块应用压缩函数：
$\begin{align*} z_0 &\leftarrow \text{IV} = 1111 \\ z_1 &\leftarrow \text{compress}(z_0 \| y_1) \\ &\leftarrow \text{compress}(1111 \| 1010) \\ &\leftarrow \text{compress}(11111010) = 0110（通过一定算法） \\ z_2 &\leftarrow \text{compress}(z_1 \| y_2) \\ &\leftarrow \text{compress}(0110 \| 1101) \\ &\leftarrow \text{compress}(01101101) = 1001 \\ z_3 &\leftarrow \text{compress}(z_2 \| y_3) \\ &\leftarrow \text{compress}(1001 \| 0011) \\ &\leftarrow \text{compress}(10010011) = 1100 \end{align*}$

输出转换

哈希值为：
$h(x) = g(z_3) = 1100$

总结

预处理：填充（若需）并分割输入为固定长度块。
处理：逐块压缩，将前一状态与当前块组合。
输出转换：直接取最终压缩结果（或进一步处理）。

通过迭代设计，即使输入极长，也能高效生成固定长度输出，并累积处理全输入。

迭代哈希函数的示例

1990年，MD4，由 Rivest 提出。
1992年，MD5，对 MD4 的修改，由 Rivest 提出。
1993年，SHA(-0)，由 NIST 提出作为标准，被采用为 FIPS 180。
1995年，SHA-1，对 SHA 的小幅修改，被发布为 FIPS 180-1。
中期1990年代，发现了 MD4 和 MD5 的压缩函数的碰撞。
2004年，Joux 找到了 SHA-0 的碰撞，并在 CRYPTO 上报告。
2004年，在 CRYPTO 2004 上，Wang、Feng、Lai 和 Yu 展示了 MD5 和其他几种流行的哈希函数的碰撞。
2017年，Stevens、Bursztein、Karpman、Albertini 和 Markov 找到了 SHA-1 的第一个碰撞。
2002年，SHA-2 包括四种哈希函数，分别称为 SHA-224、SHA-256、SHA-384 和 SHA-512。
2015年，SHA-3 成为 FIPS 标准。（采用不同的设计技术——称为海绵构造）

海绵构造

SHA-3 基于一种称为海绵构造的设计策略。
由 Bertoni、Daemen、Peeters 和 Van Assche 开发。
不使用压缩函数，而是使用一个基本的“构建块”——一个函数 $f$ ，它将固定长度的比特串映射到相同长度的比特串。
通常 $f$ 是双射函数，因此每个比特串都有唯一的原像。
海绵构造可以产生任意长度的输出（即消息摘要）。
$\{0,1\}^b \rightarrow \{0,1\}^b$
整数 $b$ 称为宽度。
将 $b$ 写成 $r + c$ ，其中 $r$ 是比特率（bitrate）， $c$ 是容量（capacity）。

海绵函数

输入为消息 $M$ ，这是一个任意长度的比特串。
$M$ 适当填充，使其长度是 $r$ 的倍数。
然后将填充后的消息分成长度为 $r$ 的块。
吸收阶段（Absorbing Phase）：将填充后消息的第一个块与状态的前 $r$ 位进行异或操作。然后应用函数 $f$ ，更新状态。
挤压阶段（Squeezing Phase）：对当前状态应用 $f$ ，并取前 $r$ 位输出比特。这个过程重复进行，直到我们得到至少 $\ell$ 位的总输出。将连接结果截断为 $\ell$ 位。

SHA-3

SHA-3 包括四种哈希函数，分别称为 SHA3-224、SHA3-256、SHA3-384 和 SHA3-512。（后缀表示消息摘要的长度，即上述讨论中的参数 $\ell$ 。）
此外，SHA-3还包括名为SHAKE128和SHAKE256的可扩展输出函数（XOF）。
如果碰撞安全性为 $t$ ，这表明攻击需要大约 $2^t$ 步。

消息认证是一种验证过程，用于确认以下内容：

接收到的消息来自声称的来源
接收到的消息未被篡改
消息的顺序和及时性

三种替代方法如下：

消息加密
哈希函数
消息认证码（MAC）

对称消息加密

加密也可以提供认证。
如果使用对称加密，则：
- 接收者知道消息必须由发送者创建，因为只有发送者和接收者知道密钥。
- 如果消息具有合适的结构、冗余或校验和以检测任何更改，则可以检测到篡改。

公钥消息加密

如果使用公钥加密：
- 任何人都可能知道公钥。
- 然而，如果：
  - 发送者使用其私钥对消息进行签名，
  - 然后使用接收者的公钥进行加密，
  - 则可以同时实现保密性和认证。
- 再次需要识别被篡改的消息，但代价是需要对消息进行两次公钥操作。

消息认证码（MAC）

通过一个算法生成一个小的固定大小的块，依赖于消息和某个密钥。
$\text{MAC} = C(K, M)$
- 与加密类似，但不需要可逆。
将其附加到消息上作为签名。
接收者对消息执行相同的计算，并检查其是否与MAC匹配。
提供消息未被篡改且来自发送者的保证。
构建MAC的一种常见方法是将密钥嵌入到无密钥哈希函数中，通过将密钥作为要哈希的消息的一部分。

嵌套MAC

嵌套MAC通过两个（带密钥的）哈希函数族的组合构建MAC算法。
假设 $(X, Y, K, G)$ 和 $(Y, Z, L, H)$ 是哈希函数族。
这些哈希函数族的组合是哈希函数族 $\circ H)$ ，其中 $\times L$ ，
$\circ H)_{(K,K')} = \{f_K \circ h_{K'} : f_K \in G, h_{K'} \in H\}$
其中， $(f_K \circ h_{K'})(x) = h_{K'}(f_K(x))$
嵌套MAC是安全的，前提是满足以下两个条件：
1. $(Y, Z, L, H)$ 作为MAC是安全的，给定一个固定的（未知的）密钥；
2. $(X, Y, K, G)$ 是抗碰撞的，给定一个固定的（未知的）密钥。

HMAC

HMAC是一种嵌套MAC算法，于2002年3月被采纳为FIPS标准。
基于SHA-1的HMAC：
- 一个512位的密钥，记为 $K$ 。
- $i p a d$ 和 $o p a d$ 是512位的常量，以十六进制表示如下：
  $\cdots 36, \quad opad = 5C5C \cdots 5C$
- 设 $x$ 是要认证的消息。160位的MAC定义如下：
  $\text{HMAC}_K(x) = \text{SHA-1}((K \oplus opad) \parallel \text{SHA-1}((K \oplus ipad) \parallel x))$
HMAC非常高效。第二次“外部”哈希以固定长度的短比特串作为输入。
随着SHA-3的采用，HMAC可能会变得过时，因为基于海绵构造的MAC不易受到长度扩展攻击。