跳转至

MD5

MD5是将明文处理成16byte的哈希摘要

用途

md5常与其他算法结合,用于数字签名,如邮件发送

加密过程

\[ \begin{aligned} \rm m&={\rm md5}(letter)\\ \rm m'&={\rm rsa}(m,\rm private\ key) \end{aligned} \]

检验过程

\[ \begin{aligned} \rm md5(letter) == \rm rsa(m', public\ key)\\ \end{aligned} \]

实现

结构体定义

typedef struct _MD5_CTX
{
    unsigned long state[4];
    unsigned long count[2]; /* 已处理的报文的二进制位数,最大值=2^64-1 */
    unsigned char data[4];  /* 64字节message块 */
}

Init

对state赋初始值,清空count

Update

每64个字节为一组,进行处理更新

Final

因为不是所有的明文都是64字节的倍数,所以需要对缺失的内容进行补充,补充的内容包括填充物明文长度

  • 填充物 0x80, 0x00, 0x00, ..., 0x00
  • 规则

破解

MD5的破解关键在于找到Collision

Collision

\({\rm md5}(x)={\rm md5}(x') \ \ (x\ne x')\)

rainbow table

一种较弱的MD5破解方法,关键在于预计算

  • 找N组数据
  • 对N组数据分别使用MD5处理K轮
  • 对目标数X进行MD5处理,并将结果与N个(处理K轮后的)结果进行比较
  • 若X与其中某个数相等,则根据X被MD5处理的轮数即可倒推出Collision
  • 否则继续对X进行MD5处理