4.1 Hash函数与数据完整性
数据完整性：
检测传输消息（加密或未加密）的修改。
密码学Hash函数：
构建某些数据的简短“指纹”；如果数据被篡改，则该指纹（以高概率）不再有效。Hash函数的一个特别重要的应用是数字签名方案的上下文中。
消息摘要：
设
h
(
x
)
h(x)
h(x)是一个Hash函数，
x
x
x是某些数据。对应的指纹定义为
y
=
h
(
x
)
y=h(x)
y=h(x)。这个指纹通常被称为消息摘要。
消息摘要是一个相对较短的二进制字符串，例如160位或256位。
Hash函数族：
带密钥的Hash函数族。对于每个可能的密钥，都有一个不同的Hash函数。
在不安全的信道中，Alice向Bob发送一对
(
x
,
y
)
(x,y)
(x,y)，其中
y
=
h
K
(
x
)
y=h_K(x)
y=hK(x)。
有效的配对
(
x
,
y
)
(x,y)
(x,y)满足
h
(
x
)
=
y
h(x)=y
h(x)=y。
定义 5.1： 一个Hash函数族是一个四元组 ( X , Y , K , H ) (\mathcal{X}, \mathcal{Y}, \mathcal{K}, \mathcal{H}) (X,Y,K,H)，满足以下条件：
- X \mathcal{X} X 是可能的消息集合
- Y \mathcal{Y} Y 是可能的消息摘要或认证标签（或简称标签）的有限集合
- K \mathcal{K} K，即密钥空间，是可能的密钥的有限集合
- 对于每个 K ∈ K K \in \mathcal{K} K∈K，存在一个Hash函数 h K ∈ H h_K \in \mathcal{H} hK∈H。每个 h K : X → Y h_K : \mathcal{X} \rightarrow \mathcal{Y} hK:X→Y。
在上述定义中， X \mathcal{X} X 可以是一个有限集或无限集； Y \mathcal{Y} Y 总是一个有限集。如果 X \mathcal{X} X 是一个有限集且 X > Y \mathcal{X} > \mathcal{Y} X>Y，该函数有时被称为压缩函数。在这种情况下，我们通常会假设一个更强的条件，即 ∣ X ∣ ≥ 2 ∣ Y ∣ |\mathcal{X}| \geq 2|\mathcal{Y}| ∣X∣≥2∣Y∣。
4.2 哈希函数的安全性
如果一个哈希函数被认为是安全的，那么以下三个问题应该难以解决：
- 原像问题（Preimage）
- 第二原像问题（Second Preimage）
- 碰撞问题（Collision）
问题 5.1：原像问题
实例： 给定一个哈希函数 h : X → Y h: \mathcal{X} \rightarrow \mathcal{Y} h:X→Y 和一个元素 y ∈ Y y \in \mathcal{Y} y∈Y。
求解： 找到一个 x ∈ X x \in \mathcal{X} x∈X 使得 h ( x ) = y h(x) = y h(x)=y。
问题 5.2：第二原像问题
实例： 给定一个哈希函数 h : X → Y h: \mathcal{X} \rightarrow \mathcal{Y} h:X→Y 和一个元素 x ∈ X x \in \mathcal{X} x∈X。
求解： 找到一个 x ′ ∈ X x' \in \mathcal{X} x′∈X，使得 x ′ ≠ x x' \neq x x′=x 且 h ( x ′ ) = h ( x ) h(x') = h(x) h(x′)=h(x)。
问题 5.3：碰撞问题
实例： 给定一个哈希函数 h : X → Y h: \mathcal{X} \rightarrow \mathcal{Y} h:X→Y。
求解： 寻找
x
,
x
′
∈
X
x, x' \in \mathcal{X}
x,x′∈X，使得
x
′
≠
x
x' \neq x
x′=x 且
h
(
x
′
)
=
h
(
x
)
h(x') = h(x)
h(x′)=h(x)。
如果一个哈希函数的原像问题无法高效解决，通常称其为单向的或原像抗性的。
如果一个哈希函数的第二原像问题无法高效解决，通常称其为第二原像抗性的。
如果一个哈希函数的碰撞问题无法高效解决，通常称其为抗碰撞的。
抗碰撞性
⟹
原像抗性
∧
第二原像抗性
\text{抗碰撞性} \implies \text{原像抗性} \land \text{第二原像抗性}
抗碰撞性⟹原像抗性∧第二原像抗性
随机预言模型（Random Oracle Model）——一种理想化的模型
如果一个哈希函数设计良好，那么唯一高效确定给定输入 x x x的哈希值 h ( x ) h(x) h(x)的方法是实际计算函数 h h h在 x x x处的值。
随机预言模型示例（该性质不成立）：
随机预言模型（由 Bellare 和 Rogaway 提出）
- 一个哈希函数 h : X → Y h: X \rightarrow Y h:X→Y是随机选择的，我们只能通过预言机访问该函数 h h h。
- 我们没有公式或算法来计算函数 h h h的值。
- 计算值 h ( x ) h(x) h(x)的唯一方法是查询预言机。
- 在现实生活中，真正的随机预言机是不存在的。
随机预言模型中的算法
- 我们展示和分析的算法是随机算法；它们在执行过程中可以做出随机选择。
- 拉斯维加斯算法（Las Vegas algorithm）是一种随机算法，它可能会失败（即，它可能会以“失败”消息终止），但如果算法返回答案，则答案必须是正确的。
定理 5.1 假设 h ∈ F X , Y h \in \mathcal{F}^{\mathcal{X},\mathcal{Y}} h∈FX,Y 是随机选择的，并且设 X 0 ⊆ X \mathcal{X}_0 \subseteq \mathcal{X} X0⊆X。记 ∣ Y ∣ = M |\mathcal{Y}| = M ∣Y∣=M。假设 h ( x ) h(x) h(x) 的值仅当 x ∈ X 0 x \in \mathcal{X}_0 x∈X0 时通过查询 h h h 的预言机来确定。那么对于所有 x ∈ X ∖ X 0 x \in \mathcal{X} \setminus \mathcal{X}_0 x∈X∖X0 和所有 y ∈ Y y \in \mathcal{Y} y∈Y，有 Pr [ h ( x ) = y ] = 1 M \Pr[h(x) = y] = \frac{1}{M} Pr[h(x)=y]=M1。
算法 5.1：FIND-PREIMAGE(h, y, Q)
选择任意
X
0
⊆
X
\mathcal{X}_0 \subseteq \mathcal{X}
X0⊆X，
∣
X
0
∣
=
Q
|\mathcal{X}_0| = Q
∣X0∣=Q
对于每个
x
∈
X
0
x \in \mathcal{X}_0
x∈X0
如果
h
(
x
)
=
y
h(x) = y
h(x)=y 则返回
(
x
)
(x)
(x)
返回
(
失败
)
(失败)
(失败)
该算法试图找到一个输入 x x x，使得其哈希值等于给定的 y y y。
定理 5.2
对于任意
X
0
⊆
X
\mathcal{X}_0 \subseteq \mathcal{X}
X0⊆X 且
∣
X
0
∣
=
Q
|\mathcal{X}_0| = Q
∣X0∣=Q，算法 5.1 的平均成功概率为
ϵ
=
1
−
(
1
−
1
/
M
)
Q
\epsilon = 1 - (1 - 1/M)^Q
ϵ=1−(1−1/M)Q。
该定理描述了算法 5.1 在给定条件下的平均成功概率。
算法 5.2：FIND-SECOND-PREIMAGE(h, x, Q)
y
←
h
(
x
)
y \leftarrow h(x)
y←h(x)
选择
X
0
⊆
X
∖
{
x
}
\mathcal{X}_0 \subseteq \mathcal{X} \setminus \{x\}
X0⊆X∖{x}，
∣
X
0
∣
=
Q
−
1
|\mathcal{X}_0| = Q - 1
∣X0∣=Q−1
对于每个
x
0
∈
X
0
x_0 \in \mathcal{X}_0
x0∈X0
如果
h
(
x
0
)
=
y
h(x_0) = y
h(x0)=y 则返回
(
x
0
)
(x_0)
(x0)
返回
(
失败
)
(失败)
(失败)
该算法试图找到一个不同于 x x x 的输入 x ′ x' x′，使得其哈希值等于 x x x 的哈希值。
定理 5.3
对于任意
X
0
⊆
X
∖
{
x
}
\mathcal{X}_0 \subseteq \mathcal{X} \setminus \{x\}
X0⊆X∖{x} 且
∣
X
0
∣
=
Q
−
1
|\mathcal{X}_0| = Q - 1
∣X0∣=Q−1，算法 5.2 的成功概率为
ϵ
=
1
−
(
1
−
1
/
M
)
Q
−
1
\epsilon = 1 - (1 - 1/M)^{Q-1}
ϵ=1−(1−1/M)Q−1。
以下是对每个图片内容的介绍，使用中文和Markdown格式，并且按照您的要求使用数学公式和符号：
算法 5.3：FIND-COLLISION(h, Q)
选择
X
0
⊆
X
,
∣
X
0
∣
=
Q
\mathcal{X}_0 \subseteq \mathcal{X}, |\mathcal{X}_0| = Q
X0⊆X,∣X0∣=Q
对于每个
x
∈
X
0
x \in \mathcal{X}_0
x∈X0
执行
y
x
←
h
(
x
)
y_x \leftarrow h(x)
yx←h(x)
如果
y
x
=
y
x
′
y_x = y_{x'}
yx=yx′ 对于某个
x
′
≠
x
x' \neq x
x′=x
则返回
(
x
,
x
′
)
(x, x')
(x,x′)
否则返回
(
失败
)
(失败)
(失败)
该算法试图找到两个不同的输入
x
x
x 和
x
′
x'
x′，使得它们的哈希值相同，即找到碰撞。
定理 5.4
对于任意
X
0
⊆
X
\mathcal{X}_0 \subseteq \mathcal{X}
X0⊆X 且
∣
X
0
∣
=
Q
|\mathcal{X}_0| = Q
∣X0∣=Q，算法 5.3 的成功概率为
ϵ
=
1
−
(
M
−
1
M
)
(
M
−
2
M
)
⋯
(
M
−
Q
+
1
M
)
.
\epsilon = 1 - \left(\frac{M-1}{M}\right)\left(\frac{M-2}{M}\right)\cdots\left(\frac{M-Q+1}{M}\right).
ϵ=1−(MM−1)(MM−2)⋯(MM−Q+1).
该定理描述了算法 5.3 在给定条件下的成功概率。
碰撞概率估计
使用此估计，找到没有碰撞的概率大约为
∏
i
=
1
Q
−
1
(
1
−
i
M
)
≈
∏
i
=
1
Q
−
1
e
−
i
M
=
e
−
∑
i
=
1
Q
−
1
i
M
=
e
−
Q
(
Q
−
1
)
2
M
.
\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}}.
i=1∏Q−1(1−Mi)≈i=1∏Q−1e−Mi=e−∑i=1Q−1Mi=e2M−Q(Q−1).
因此，我们可以估计找到至少一个碰撞的概率为
1
−
e
−
Q
(
Q
−
1
)
2
M
.
1 - e^{\frac{-Q(Q-1)}{2M}}.
1−e2M−Q(Q−1).
这段内容提供了找到至少一个碰撞的概率估计。
碰撞概率估计（忽略 − Q -Q −Q 项）
如果我们忽略
−
Q
-Q
−Q 项，那么我们估计
Q
≈
2
M
ln
1
1
−
ϵ
.
Q \approx \sqrt{2M \ln \frac{1}{1-\epsilon}}.
Q≈2Mln1−ϵ1.
如果我们取
ϵ
=
0.5
\epsilon = 0.5
ϵ=0.5，那么我们的估计是
Q
≈
1.17
M
.
Q \approx 1.17 \sqrt{M}.
Q≈1.17M.
这段内容提供了在特定条件下的碰撞概率估计，特别是当 ϵ = 0.5 \epsilon = 0.5 ϵ=0.5 时的估计值。
迭代哈希函数
- 迭代哈希函数：将压缩函数扩展为具有无限定义域的哈希函数 h h h。
- 预处理步骤必须确保映射是单射（injective）。
- 迭代哈希函数的处理步骤。
Merkle-Damgård 构造
- Merkle-Damgård 构造
- 这种构造被用于设计许多流行的哈希算法，例如 MD4、MD5、SHA-1 和 SHA-2。
- 如果压缩函数满足某些安全属性（例如抗碰撞性），那么得到的哈希函数也满足这些属性。
- x k + 1 应该在左侧填充零，使得 x k + 1 = t − 1 x_{k+1} \text{应该在左侧填充零，使得} x_{k+1} = t - 1 xk+1应该在左侧填充零，使得xk+1=t−1
- 如果可以为 h h h找到碰撞，那么也可以为压缩函数找到碰撞。换句话说，只要压缩函数是抗碰撞的， h h h就是抗碰撞的。
- 当 t = 1 t=1 t=1时， h h h是抗碰撞的，前提是压缩函数是抗碰撞的。
假设存在一个压缩函数
compress
:
{
0
,
1
}
m
+
t
→
{
0
,
1
}
m
\text{compress} : \{0,1\}^{m+t} \rightarrow \{0,1\}^{m}
compress:{0,1}m+t→{0,1}m（其中
t
≥
1
t \geq 1
t≥1）。我们将基于这个压缩函数构建一个迭代哈希函数
h
:
⋃
i
=
m
+
t
+
1
∞
{
0
,
1
}
i
→
{
0
,
1
}
ℓ
,
h : \bigcup_{i=m+t+1}^{\infty} \{0,1\}^i \rightarrow \{0,1\}^\ell,
h:i=m+t+1⋃∞{0,1}i→{0,1}ℓ,
哈希函数
h
h
h 的计算包括以下三个主要步骤：
预处理步骤
给定一个输入字符串
x
x
x，其中
∣
x
∣
≥
m
+
t
+
1
|x| \geq m+t+1
∣x∣≥m+t+1，构造一个字符串
y
y
y，使用一个公共算法，使得
∣
y
∣
≡
0
(
mod
t
)
|y| \equiv 0 (\text{mod } t)
∣y∣≡0(mod t)。记作
y
=
y
1
∥
y
2
∣
⋯
∣
y
r
,
y=y_{1}\|y_{2}|\cdots|y_{r},
y=y1∥y2∣⋯∣yr,
其中
∣
y
i
∣
=
t
|y_{i}|=t
∣yi∣=t 对于
1
≤
i
≤
r
1\leq i\leq r
1≤i≤r。
一个常用的预处理步骤是按照以下方式构造字符串
y
y
y：
y
=
x
∥
pad
(
x
)
,
y = x \| \text{pad}(x),
y=x∥pad(x),
其中
pad
(
x
)
\text{pad}(x)
pad(x) 是使用一个填充函数从
x
x
x 构造的。一个填充函数通常结合
∣
x
∣
|x|
∣x∣ 的值，并用额外的位（例如零）填充结果，使得结果字符串
y
y
y 的长度是
t
t
t 的倍数。
其中 pad ( x ) \text{pad}(x) pad(x) 是使用填充函数从 x x x 构造的。一个填充函数通常结合 ∣ x ∣ |x| ∣x∣ 的值，并用额外的位（例如零）填充结果，使得结果字符串 y y y 的长度是 t t t 的倍数。
处理步骤
设
IV
\text{IV}
IV 是一个公共初始值，它是一个长度为
m
m
m 的比特串。然后计算以下内容：
z
0
←
IV
z
1
←
compress
(
z
0
∥
y
1
)
z
2
←
compress
(
z
1
∥
y
2
)
⋮
z
r
←
compress
(
z
r
−
1
∥
y
r
)
.
\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*}
z0z1z2zr←IV←compress(z0∥y1)←compress(z1∥y2)⋮←compress(zr−1∥yr).
输出转换
设
g
:
{
0
,
1
}
m
→
{
0
,
1
}
ℓ
g : \{0,1\}^{m} \rightarrow \{0,1\}^{\ell}
g:{0,1}m→{0,1}ℓ 是一个公共函数。定义
h
(
x
)
=
g
(
z
r
)
h(x) = g(z_{r})
h(x)=g(zr)。
备注 输出转换是可选的。如果不希望进行输出转换，则定义
h
(
x
)
=
z
r
h(x) = z_{r}
h(x)=zr。
例子
参数设置
- 压缩函数：
compress : { 0 , 1 } m + t → { 0 , 1 } m , m = 4 , t = 4 \text{compress} : \{0,1\}^{m + t} \rightarrow \{0,1\}^{m}, \quad m=4,\; t=4 compress:{0,1}m+t→{0,1}m,m=4,t=4
压缩函数将8位输入压缩为4位输出。 - 初始值：
IV = 1111 \text{IV}=1111 IV=1111 - 输出转换函数：
g ( z r ) = z r g(z_r)=z_r g(zr)=zr（即直接输出压缩结果，不作额外转换）。
输入示例
假设输入字符串：
x
=
101011010011
(
长度
12
位
,
∣
x
∣
=
12
)
x = 101011010011 \quad (\text{长度 }12\text{ 位},\; |x|=12)
x=101011010011(长度 12 位,∣x∣=12)
预处理步骤
目标：构造字符串 y y y，使其长度是 t = 4 t=4 t=4的倍数。
- 原长度 ∣ x ∣ = 12 |x|=12 ∣x∣=12，已满足条件（无需填充）。
- 分割为
r
=
3
r=3
r=3个4位块：
y 1 = 1010 , y 2 = 1101 , y 3 = 0011 y_1 = 1010,\; y_2 = 1101,\; y_3 = 0011 y1=1010,y2=1101,y3=0011
处理步骤
逐块应用压缩函数：
z
0
←
IV
=
1111
z
1
←
compress
(
z
0
∥
y
1
)
←
compress
(
1111
∥
1010
)
←
compress
(
11111010
)
=
0110
（通过一定算法）
z
2
←
compress
(
z
1
∥
y
2
)
←
compress
(
0110
∥
1101
)
←
compress
(
01101101
)
=
1001
z
3
←
compress
(
z
2
∥
y
3
)
←
compress
(
1001
∥
0011
)
←
compress
(
10010011
)
=
1100
\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*}
z0z1z2z3←IV=1111←compress(z0∥y1)←compress(1111∥1010)←compress(11111010)=0110（通过一定算法）←compress(z1∥y2)←compress(0110∥1101)←compress(01101101)=1001←compress(z2∥y3)←compress(1001∥0011)←compress(10010011)=1100
输出转换
哈希值为：
h
(
x
)
=
g
(
z
3
)
=
1100
h(x) = g(z_3) = 1100
h(x)=g(z3)=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 f，它将固定长度的比特串映射到相同长度的比特串。
- 通常 f f f是双射函数，因此每个比特串都有唯一的原像。
- 海绵构造可以产生任意长度的输出（即消息摘要）。
-
f
:
{
0
,
1
}
b
→
{
0
,
1
}
b
f: \{0,1\}^b \rightarrow \{0,1\}^b
f:{0,1}b→{0,1}b
整数 b b b称为宽度。 - 将 b b b写成 r + c r + c r+c，其中 r r r是比特率（bitrate）， c c c是容量（capacity）。
海绵函数
-
输入为消息 M M M，这是一个任意长度的比特串。
-
M M M适当填充，使其长度是 r r r的倍数。
-
然后将填充后的消息分成长度为 r r r的块。
-
吸收阶段（Absorbing Phase）：将填充后消息的第一个块与状态的前 r r r位进行异或操作。然后应用函数 f f f，更新状态。
-
挤压阶段（Squeezing Phase）：对当前状态应用 f f f，并取前 r r r位输出比特。这个过程重复进行，直到我们得到至少 ℓ \ell ℓ位的总输出。将连接结果截断为 ℓ \ell ℓ位。
SHA-3
SHA-3 包括四种哈希函数，分别称为 SHA3-224、SHA3-256、SHA3-384 和 SHA3-512。（后缀表示消息摘要的长度，即上述讨论中的参数
ℓ
\ell
ℓ。）
此外，SHA-3还包括名为SHAKE128和SHAKE256的可扩展输出函数（XOF）。
如果碰撞安全性为
t
t
t，这表明攻击需要大约
2
t
2^t
2t步。
消息认证是一种验证过程，用于确认以下内容：
- 接收到的消息来自声称的来源
- 接收到的消息未被篡改
- 消息的顺序和及时性
三种替代方法如下：
- 消息加密
- 哈希函数
- 消息认证码（MAC）
对称消息加密
- 加密也可以提供认证。
- 如果使用对称加密，则：
- 接收者知道消息必须由发送者创建，因为只有发送者和接收者知道密钥。
- 如果消息具有合适的结构、冗余或校验和以检测任何更改，则可以检测到篡改。
公钥消息加密
- 如果使用公钥加密：
- 任何人都可能知道公钥。
- 然而，如果：
- 发送者使用其私钥对消息进行签名，
- 然后使用接收者的公钥进行加密，
- 则可以同时实现保密性和认证。
- 再次需要识别被篡改的消息，但代价是需要对消息进行两次公钥操作。
消息认证码（MAC）
- 通过一个算法生成一个小的固定大小的块，依赖于消息和某个密钥。
MAC = C ( K , M ) \text{MAC} = C(K, M) MAC=C(K,M)- 与加密类似，但不需要可逆。
- 将其附加到消息上作为签名。
- 接收者对消息执行相同的计算，并检查其是否与MAC匹配。
- 提供消息未被篡改且来自发送者的保证。
- 构建MAC的一种常见方法是将密钥嵌入到无密钥哈希函数中，通过将密钥作为要哈希的消息的一部分。
嵌套MAC
- 嵌套MAC通过两个（带密钥的）哈希函数族的组合构建MAC算法。
- 假设 ( X , Y , K , G ) (X, Y, K, G) (X,Y,K,G)和 ( Y , Z , L , H ) (Y, Z, L, H) (Y,Z,L,H)是哈希函数族。
- 这些哈希函数族的组合是哈希函数族
(
X
,
Z
,
M
,
G
∘
H
)
(X, Z, M, G \circ H)
(X,Z,M,G∘H)，其中
M
=
K
×
L
M = K \times L
M=K×L，
( G ∘ H ) ( K , K ′ ) = { f K ∘ h K ′ : f K ∈ G , h K ′ ∈ H } (G \circ H)_{(K,K')} = \{f_K \circ h_{K'} : f_K \in G, h_{K'} \in H\} (G∘H)(K,K′)={fK∘hK′:fK∈G,hK′∈H}
其中， ( f K ∘ h K ′ ) ( x ) = h K ′ ( f K ( x ) ) (f_K \circ h_{K'})(x) = h_{K'}(f_K(x)) (fK∘hK′)(x)=hK′(fK(x)) - 嵌套MAC是安全的，前提是满足以下两个条件：
- ( Y , Z , L , H ) (Y, Z, L, H) (Y,Z,L,H)作为MAC是安全的，给定一个固定的（未知的）密钥；
- ( X , Y , K , G ) (X, Y, K, G) (X,Y,K,G)是抗碰撞的，给定一个固定的（未知的）密钥。
HMAC
- HMAC是一种嵌套MAC算法，于2002年3月被采纳为FIPS标准。
- 基于SHA-1的HMAC：
- 一个512位的密钥，记为 K K K。
-
i
p
a
d
ipad
ipad和
o
p
a
d
opad
opad是512位的常量，以十六进制表示如下：
i p a d = 3636 ⋯ 36 , o p a d = 5 C 5 C ⋯ 5 C ipad = 3636 \cdots 36, \quad opad = 5C5C \cdots 5C ipad=3636⋯36,opad=5C5C⋯5C - 设
x
x
x是要认证的消息。160位的MAC定义如下：
HMAC K ( x ) = SHA-1 ( ( K ⊕ o p a d ) ∥ SHA-1 ( ( K ⊕ i p a d ) ∥ x ) ) \text{HMAC}_K(x) = \text{SHA-1}((K \oplus opad) \parallel \text{SHA-1}((K \oplus ipad) \parallel x)) HMACK(x)=SHA-1((K⊕opad)∥SHA-1((K⊕ipad)∥x))
- HMAC非常高效。第二次“外部”哈希以固定长度的短比特串作为输入。
- 随着SHA-3的采用，HMAC可能会变得过时，因为基于海绵构造的MAC不易受到长度扩展攻击。
CBC-MAC
- 构建MAC的一种流行方法是使用块密码的CBC模式和一个固定的（公开的）初始化向量。
- 已知如果底层加密满足适当的安全属性，则CBC-MAC是安全的。
消息认证码（MAC）的基本用途
- 加密用于提供保密性。
- MAC用于提供数据完整性。
- 结合这两种过程通常称为认证加密。
- 优先采用“加密后加MAC”的方式。
参考：
sha3
https://www.bilibili.com/video/BV1oY41197g4
md5
https://www.bilibili.com/video/BV1u44y1z7t1
