第5章：单向散列函数和消息认证

单向散列函数基础

Hash函数的定义

  • Hash函数h是一个公开函数，用于将任意长的消息m映射为较短的、固定长度的一个值h(m)，称为消息摘要或哈希值。

Hash函数的性质

  1. 输入任意长：函数的输入可以是任意长的消息。
  2. 输出固定长：函数的输出是固定长度的摘要。
  3. 计算简便：对任意给定的x，计算$h(x)$比较容易。
  4. 单向性：对任意给定的Hash值z，找到满足$h(x)=z$的$x$在计算上是不可行的。
  5. 抗弱碰撞性：已知x，找到另一个$y(y≠x)$使得$h(y)=h(x)$在计算上是不可行的。
  6. 抗强碰撞性：找到任意两个不同的输入$x, y$，使$h(y)=h(x)$在计算上是不可行的。

碰撞性

  • 碰撞是指对于两个不同的消息x和y，如果它们的Hash值相同，则发生了碰撞。Hash函数必须具有碰撞抵抗性，确保找到碰撞在计算上是不可行的。

Hash与加密的对比

  • 加密是双向的，需要使用密钥进行加密和解密。Hash是单向的，没有解Hash的过程。

迭代型Hash函数的一般结构

  • Merkle基于压缩函数f提出了一个Hash函数的一般结构。输入m被分为L个分组，每个分组的长度为b比特。如果最后一个分组长度不够，需对其填充。最终输出的链接变量CVL就是Hash值。
MD5算法

MD5算法描述

  • 前身是MD4算法，由Ron Rivest于1990年提出。MD5算法采用迭代型哈希函数的一般结构，输入任意长的消息，分组长度为512比特，输出128比特的消息摘要。

处理过程

  1. 填充消息：对消息填充，使其比特长度模512下为448，填充方式为第1位为1，其后各位皆为0。
  2. 填充长度：用64比特表示消息填充前的长度，以little-endian方式附在后面。
  3. 初始化MD缓冲区：使用128比特长的缓冲区，包含4个32比特长的寄存器(A, B, C, D)。
  4. 以512比特的分组为单位处理消息：每一分组都经一压缩函数处理。每一分组分为4轮处理，每轮16步迭代运算。
  5. 输出：所有分组处理完后，最后一个HMD5的输出即为消息摘要。
SHA-1算法

SHA-1算法描述

  • 安全哈希算法(Secure Hash Algorithm, SHA)由美国NIST设计，1993年作为联邦信息处理标准公布，1995年发布修订版FIPS PUB 180-1，通常称为SHA-1。

处理过程

  1. 填充消息：与MD5的步骤①完全相同。
  2. 附加消息长度：用64比特表示填充前消息的长度，并将其附在后面。
  3. 初始化缓冲区：使用160比特长的缓冲区，包含5个32比特长的寄存器(A, B, C, D, E)。
  4. 以分组为单位处理消息：每一分组都经一压缩函数处理。压缩函数由4轮处理过程构成，每轮20步迭代。
  5. 输出：所有分组处理完后，最后一个分组的输出即为160比特的消息摘要。

SHA-1与MD5的比较

  • SHA-1算法基于MD4，结构与MD4类似，但安全性更高，输出长度为160比特，而MD5为128比特。SHA-1在实际应用中比MD5更为广泛。