MD5 全称为 Message-Digest Algorithm ,一般用来保证信息传输的完整一致,MD5 的结果是固定长度 128bit 。MD5 算法最开始是为密码学而设计,但是后来被发现有很大的缺陷,所以后来就用来校验文件的完整性(无意识而造成的不完整,比如下载)。MD5 在非密码学领域也有其他用途,比如在一个数据库中快速检查一个 key 是否存在。

密码学的 hash 方法一个最基本的要求是,计算机难以通过计算来找到两个不同的内容拥有同一个 hash 值,MD5 无法满足该基本条件。MD5 算法无法防止碰撞,无法用于安全性验证,对于安全性高的资料,建议使用其他算法。

MD5 是 Ronald Rivest 在 1991 年设计用来代替 MD4, 具体的说明定义在 RFC 1321 中。

MD5 的用途

  • 校验文件完整性,比如下载一个文件包,或者发送一个文件,接受者收到之后用提供方提供的 md5 来校验
  • 将明文信息 hash 到密文信息,在只需要对比一致性时可以使用,比如密码校验(但一般不建议直接使用 md5 hash 密码)
  • git 的 commit ID 也是 MD5,未来可能慢慢被 SHA 代替

原理

MD5 的输入不定长,输出定长 128 bits。MD5 计算方式可以分为几个步骤:

  • 输入信息被分成每一块 512 bit 长的 (16 个 32 位子分组)组,此时必定有剩余,对剩余部分,先填充一个 1,然后是若干 0,最后预留出 64 位来保存前面信息的长度(这个信息的长度包括若干 512 bit 的区块 + 1 + 若干 0 组成),补充完成后整体一定是 512 bit 的倍数(包括三个部分,原始数据 + 补充数据 + 信息长度)。如果信息的长度超过了 64 位能够表示的范围,则取低 64 位。
  • 再得到 N*512 个数据组之后,初始 A B C D 四个 32 bit 长度的变量,里面依次存放十六进制

    A: 01 23 45 67 B: 89 ab cd ef C: fe dc ba 98 D: 76 54 32 10

  • 分组处理数据,已经将数据分成了 512 位一组,512 位又可以分成 16 * 32 位,小组中共有 16 个 32 位的子分组,用 M0 到 M15 来表示
  • 常数 Ti 是 4294967296*abs(sin(i))的整数部分,i 取值从 1 到 64
  • 接下来定义四个线性函数,每一个方法接受三个 32 位的 word 然后产生一个 32 位的 word

    F(X,Y,Z) = (XY) | (not(X) Z) if X then Y else Z G(X,Y,Z) = (XZ) | (Y not(Z)) if Z then X else Y H(X,Y,Z) = X xor Y xor Z I(X,Y,Z) = Y xor (X | not(Z))

伪代码:

主要分成这几部分,先针对第一个分组,处理 16 个子分组,通过初始 A B C D 计算得到新的 A B C D,然后将新的 A B C D 加到原来的 A B C D 中。如此往复直到计算完所有的分组,最终得到的 ABCD 就是 MD5 的值。

/* Process each 16-word block. */
For i = 0 to N/16-1 do

  /* Copy block i into X. */
  For j = 0 to 15 do
    Set X[j] to M[i*16+j].
  end /* of loop on j */

  /* 另存一份 */
  AA = A
  BB = B
  CC = C
  DD = D

  /* Round 1. */
  /* Let [abcd k s i] denote the operation
       a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
  /* Do the following 16 operations. */
  [ABCD  0  7  1]  [DABC  1 12  2]  [CDAB  2 17  3]  [BCDA  3 22  4]
  [ABCD  4  7  5]  [DABC  5 12  6]  [CDAB  6 17  7]  [BCDA  7 22  8]
  [ABCD  8  7  9]  [DABC  9 12 10]  [CDAB 10 17 11]  [BCDA 11 22 12]
  [ABCD 12  7 13]  [DABC 13 12 14]  [CDAB 14 17 15]  [BCDA 15 22 16]

  /* Round 2. */
  /* Let [abcd k s i] denote the operation
       a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
  /* Do the following 16 operations. */
  [ABCD  1  5 17]  [DABC  6  9 18]  [CDAB 11 14 19]  [BCDA  0 20 20]
  [ABCD  5  5 21]  [DABC 10  9 22]  [CDAB 15 14 23]  [BCDA  4 20 24]
  [ABCD  9  5 25]  [DABC 14  9 26]  [CDAB  3 14 27]  [BCDA  8 20 28]
  [ABCD 13  5 29]  [DABC  2  9 30]  [CDAB  7 14 31]  [BCDA 12 20 32]

  /* Round 3. */
  /* Let [abcd k s t] denote the operation
       a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
  /* Do the following 16 operations. */
  [ABCD  5  4 33]  [DABC  8 11 34]  [CDAB 11 16 35]  [BCDA 14 23 36]
  [ABCD  1  4 37]  [DABC  4 11 38]  [CDAB  7 16 39]  [BCDA 10 23 40]
  [ABCD 13  4 41]  [DABC  0 11 42]  [CDAB  3 16 43]  [BCDA  6 23 44]
  [ABCD  9  4 45]  [DABC 12 11 46]  [CDAB 15 16 47]  [BCDA  2 23 48]

  /* Round 4. */
  /* Let [abcd k s t] denote the operation
       a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
  /* Do the following 16 operations. */
  [ABCD  0  6 49]  [DABC  7 10 50]  [CDAB 14 15 51]  [BCDA  5 21 52]
  [ABCD 12  6 53]  [DABC  3 10 54]  [CDAB 10 15 55]  [BCDA  1 21 56]
  [ABCD  8  6 57]  [DABC 15 10 58]  [CDAB  6 15 59]  [BCDA 13 21 60]
  [ABCD  4  6 61]  [DABC 11 10 62]  [CDAB  2 15 63]  [BCDA  9 21 64]

  /* Then perform the following additions. (That is increment each
     of the four registers by the value it had before this block
     was started.) */
  A = A + AA
  B = B + BB
  C = C + CC
  D = D + DD

end /* of loop on i */

最后每一轮更新之后进入下一轮更新,最后会在 ABCD 中保存 4 * 32 位最后 Hash 的结果。

检查文件 MD5

128 位的 MD5 一般表示为 32 位的十六进制数。

CyanogenMod 中有一段检查文件 MD5 的代码:

/*
 * Copyright (C) 2012 The CyanogenMod Project
 *
 * * Licensed under the GNU GPLv2 license
 *
 * The text of the license can be found in the LICENSE file
 * or at https://www.gnu.org/licenses/gpl-2.0.txt
 */

package com.cyanogenmod.updater.utils;

import android.text.TextUtils;
import android.util.Log;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

public class MD5 {
    private static final String TAG = "MD5";

    public static boolean checkMD5(String md5, File updateFile) {
        if (TextUtils.isEmpty(md5) || updateFile == null) {
            Log.e(TAG, "MD5 string empty or updateFile null");
            return false;
        }

        String calculatedDigest = calculateMD5(updateFile);
        if (calculatedDigest == null) {
            Log.e(TAG, "calculatedDigest null");
            return false;
        }

        Log.v(TAG, "Calculated digest: " + calculatedDigest);
        Log.v(TAG, "Provided digest: " + md5);

        return calculatedDigest.equalsIgnoreCase(md5);
    }

    public static String calculateMD5(File updateFile) {
        MessageDigest digest;
        try {
            digest = MessageDigest.getInstance("MD5");
        } catch (NoSuchAlgorithmException e) {
            Log.e(TAG, "Exception while getting digest", e);
            return null;
        }

        InputStream is;
        try {
            is = new FileInputStream(updateFile);
        } catch (FileNotFoundException e) {
            Log.e(TAG, "Exception while getting FileInputStream", e);
            return null;
        }

        byte[] buffer = new byte[8192];
        int read;
        try {
            while ((read = is.read(buffer)) > 0) {
                digest.update(buffer, 0, read);
            }
            byte[] md5sum = digest.digest();
            BigInteger bigInt = new BigInteger(1, md5sum);
            String output = bigInt.toString(16);
            // Fill to 32 chars
            output = String.format("%32s", output).replace(' ', '0');
            return output;
        } catch (IOException e) {
            throw new RuntimeException("Unable to process file for MD5", e);
        } finally {
            try {
                is.close();
            } catch (IOException e) {
                Log.e(TAG, "Exception on closing MD5 input stream", e);
            }
        }
    }
}

reference