现代密码学5.2--域扩张：Merkle-Damgard Transform

• Merkle-Damgard Transform

博主正在学习INTRODUCTION TO MODERN CRYPTOGRAPHY (Second Edition) --Jonathan Katz, Yehuda Lindell，做一些笔记供自己回忆，如有错误请指正。整理成一个系列现代密码学，方便检索。

• 第二章定义了完美安全及其对应的密码方案“一次一密”，
• 第三章介绍了安全定义和满足安全定义的密码方案：
  • 3.1-3.3 计算安全，PRG和基于PRG构造的满足计算安全的密码方案；
  • 3.4-3.5 CPA安全，PRF和基于PRF构造的满足CPA安全的密码方案
  • 3.6 基于PRG和PRF构造的流密码和分组密码；
  • 3.7 CCA安全，对非CCA安全密码方案的攻击
• 第五章介绍哈希函数：
  • 5.1节介绍了哈希函数的定义
  • 5.2节将介绍一种域扩张，可以将固定长度的输入扩张到任意长度的输入，这样我们就可以只考虑固定长度输入的哈希函数，简化了问题。

Merkle-Damgard Transform

• 根据5.1节哈希函数的定义，我们知道哈希函数是将任意长度的字符串映射到固定长度的字符串：$\{0,1{\}}^{\ast }\to \{0,1{\}}^l,\ast >l$，
• 但是实际中我们去构建一个哈希函数往往不会考虑对任意长度的输入，这样需要考虑的范围太广了
• 我们考虑固定长度的输入，比如$2n\to n$，压缩一半长度的哈希函数
• 因为有域扩张，考虑固定长度输入与任意长度输入在抗碰撞性上是等价的，所以我们可以只考虑固定长度输入。

现在证明考虑固定长度输入$(Gen,h)$与任意长度输入$(Gen,H)$在抗碰撞性上是等价的：

• 假设$(Gen,h)：\{0,1{\}}^{2n}\to \{0,1{\}}^n$
• $(Gen,H)：x\in \{0,1{\}}^{\ast }\to \{0,1{\}}^n，|x|=L<2^n$
• 定义$(Gen,H)$：设置$B:=\lceil \frac{L}{n}\rceil$，原始输入$x$被划分成$B$个$n$-比特块，令$x_{B+1}=L$，$z_0=0^n$，$z_i=h^s(z_{i-1}||x_i)$，输出$z_{B+1}$。

我们只要说明$\forall s$，$H^s$上的碰撞是$h^s$上的碰撞。

• 假设$H^s$上有一对碰撞对$(x,x^{\prime })$，$x_{B+1}=L$，$x_{B^{\prime }+1}^{\prime }=L^{\prime }$
• 考虑两种情况
  • case1：$L\ne L^{\prime }$
    • $H^s(x)=z_{B+1}=h^s(z_B||L)$
    • $H^s(x^{\prime })=z_{B^{\prime }+1}^{\prime }=h^s(z_{B^{\prime }}^{\prime }||L^{\prime })$
    • 因为$H^s(x)=H^s(x^{\prime })$，则$h^s(z_B||L)=h^s(z_{B^{\prime }}^{\prime }||L^{\prime })$。
    • 因为$L\ne L^{\prime }$，所以$z_B||L\ne z_{B^{\prime }}^{\prime }||L^{\prime }$，所以这是$h^s$上的碰撞对。
  • case2：$L=L^{\prime }$
    • 类似地，因为最后输出是一样的，而$x\ne x^{\prime }$，所以一定有某个中间输入是不一样的

总结

以上是生活随笔为你收集整理的现代密码学5.2--域扩张：Merkle-Damgard Transform的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。