MD5是由公钥加密算法创始人Rivest设计,MD是消息摘要( Message Digest )的意思,该算法将任意长度的消息进行一系列的运算是生成128bit的消息摘要

原理

概述:以512位分组来处理输入的信息,且每一分组又被划分为16个32位子分组,经过了一系列的处理后,算法的输出由四个32位分组组成,将这四个32位分组级联后将生成一个128位散列值,每次的运算都由前一轮的128位结果值和当前的512bit值进行运算

MD5结构:

算法步骤

消息填充

  • 填充消息,使消息长度模512 = 448
    • 如果消息长度模512恰好等于448,则增加512个填充比特,即填充的个数位1~512
    • 填充方法:第1比特为1,其余全部为0
  • 补足长度,将一个表示数据原始长度的64bit数(这是对原始数据没有补位前长度的描述,用二进制来表示)补在最后
    • 如果数据的长度超过64bit所能表示的数据长度,只保留最后64bit
    • 添加到填充数据后面,使数据为512bit的整数倍
  • 521bit按32bit分为16组

初始化链接向量

  • MD5使用4个32位的寄存器A、B、C、D,最开始存放4个固定的32位整数参数,用于第一轮迭代
    初始值
    A = 0x01234567
    B = 0x89abcdef
    C = 0xfedcba98
    D = 0x76543210

    分组处理(迭代压缩)

  • 由4轮组成,521bit的消息分组Mi被均分为16个分组,参与每轮16步函数运算,即每轮包括16个步骤。每步的输入是4个32bit的链接变量1个32bit的消息子分组,输出为32位值
  • 经过4轮共64步后,得到的4个寄存器值分别与输入链接变量进行模加,即得到此次分组处理的输出链接变量
  • 4轮操作之前,先将前一分组的链接变量(A、B、C、D的值)复制到备用记录单元,以便执行最后的模加操作

步函数

  • MD5每一轮包含16步,每一轮的步函数相同,使用同一个非线性函数;不同轮的步函数使用的非线性函数是不相同的,即4轮使用4个不同的非线性函数(逻辑函数)
  • 4个非线性函数F、G、H、I

  • MD5步函数的执行过程:

  • M[ j ] 表示消息分组 Mi 的第 j (0 ≤ j ≤ 15) 个32bit分组,第一轮中就是简单的 0, 1, …, 15

  • <<< s 表示循环左移s位,算法设计时规定好的

    # 每次循环左移的位数
    S = ((7,12,17,22)*4,
    (5,9,14,20)*4,
    (4,11,16,23)*4,
    (6,10,15,21)*4)
  • 伪随机常数 T[ i ],可以消除输入数据的规律性,i为弧度,1 ≤ i ≤ 64,方框代表取整数部分
    $$
    T[i]=[2^{32}×abs(sin(i))]=[4294967296×abs(sin(i))]
    $$

轮函数先取向量(A、B、C、D)中的后3个作一次非线性函数运算,所得的结果一次加上第1个变量32bit消息子分组1个伪随机常数,再将所得的结果循环左移指定位数,并加上(A、B、C、D)的第二个变量,最后把新值赋给向量中的第1个变量

Hash函数的安全性

攻击者的目标:找到两个不停的消息映射为同一杂凑值

对Hash函数的基本攻击方法

  1. 穷举攻击:
    • 最典型的方法是生日攻击:给定初值 H0,寻找M’ ≠ M,使 h(M’) = H0
  2. 密码分析法:依赖于Hash函数的结构和代数性质分析,采用针对Hash函数弱性质的方法进行攻击,中间相遇攻击修正分组攻击差分攻击