6

详解 MD5 信息摘要算法 - xiaxveliang - 博客园

 3 years ago
source link: https://www.cnblogs.com/xiaxveliang/p/15004954.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

对于软件研发人员来说 MD5 不是一个陌生的词汇，平时的软件研发中，经常使用 MD5 校验消息是否被篡改、验证文件完整性，甚至将MD5当作加密算法使用。
MD5虽不陌生，但不是所有研发人员都了解其算法原理，通过这篇文章详细学习MD5 摘要算法。

  • 认识 MD5
  • 掌握 MD5 算法原理
  • 编码实现 MD5 摘要算法
    使用Java开发语言 编码实现MD5摘要算法。

一、认识MD5

MD5（Message Digest Algorithm 5）中文名为消息摘要算法第五版，是计算机安全领域广泛使用的一种散列函数，用以提供消息的完整性保护。

MD5作为一种常用的摘要算法（或指纹算法），其具有以下几个重要的特点（个人观点）：

  • 输入任意长度信息，输出长度固定：
    MD5 可输入任意长度的信息，其输出均为128位(bit)固定长度的二进制数据。
  • 运算速度快：
    MD5的运算均为32位 与、或、非、位移等位运算，因此其运算速率快，几乎不消耗CPU时间。
  • 不可逆：
    根据MD5的的散列结果，无法计算出原始数据（查字典除外）。
  • 碰撞性：
    原始数据与其MD5散列结果并非一一对应，存在多个原始数据的MD5结果相同的可能性。
  • 不安全：
    2011年，RFC 6151 禁止MD5用作密钥散列消息认证码。

1.1 长度

日常软件研发中 MD5计算结果一般为长度为32的字符串，偶尔也会遇到长度为16的字符串。那么，MD5到底是多长的字符串？

MD5散列结果是128位(bit)固定长度的二进制数据，也就是128个0/1的二进数据。
用128位二进制数据呈现MD5的散列结果，对于软件开发者很不友好。
一般将二进制转成16进制，每4个二进制数据转化为一个16进制数据，128位二进制数据转化为32个十六进制数据（128/4 = 32），最终以字符串形式呈现十六进制数据后则为长度为32的字符串。

8位二进制数据，转化为2个十六进制数据举例如下：

// 8位二进制 ——> 2个十六进制数据
// 二进制数据
0100 0101
// 对应的 十六制数据
4 5

为什么网上还有16位MD5散列结果呢？

这里以 Message Digest Algorithm 作为原始数据，分别计算其32位与16位的散列结果：

// 32位散列结果
MD5(Message Digest Algorithm,32) = e4b0190b2fadc0adbe54471ffd79a729
// 16位散列结果
MD5(Message Digest Algorithm,16) = 2fadc0adbe54471f

仔细观察以上两个散列结果，发现其中间部分完全相同均为2fadc0adbe54471f。
因此猜测16位长度的散列结果为：32位散列结果去掉前八位、后八位得到的。

1.2 用途

平时的软件研发中经常使用MD5校验消息是否被篡改、验证文件完整性。

  • 验证是否被篡改：
    比如，上传下载文件。
    数据的 发送方 将原始数据生成MD5摘要，然后把 原始数据 与其 MD5摘要一起发送给 接收方；
    接收方收到数据后，先将原始数据用MD5算法生成摘要信息，然后再将此摘要信息与发送方发过来的摘要信息进行比较，如果一致就认为原始数据没有被修改、或者损坏。
  • 防止抵赖：
    例如A写了一个文件，某认证机构对此文件用MD5算法产生摘要信息并做好记录。
    若以后A说这文件不是他写的，权威机构只需对此文件重新产生摘要信息，然后跟记录在册的摘要信息进行比对，若摘要信息相同，则证明为A写的文件。

1.3 不安全

2011年，RFC 6151 禁止MD5用作密钥散列消息认证码。

  • MD5不安全主要指的是，不可再用MD5对原始秘钥进行加密：
    比如：将用户的登录秘钥进行MD5加密后，存储于数据库中。
    MD5虽然理论上不可逆，但有些黑客网站通过查字典方式获取MD5原文信息。
    提前将一些比较常见的密文做MD5运算，将结果保存下来，破译密文时，通过MD5摘要信息直接查询原文。
    比如：字符串 123 的MD5值是 202cb962ac59075b964b07152d234b70 ，黑客在破解后的数据库中看到某位用户的密码是 202cb962ac59075b964b07152d234b70 ，通过字典一查就知道密码明文是 123 了。
  • MD5的碰撞性，决定了存在两个不用的输入信息，其MD5相同的可能。
    2009年，中国科学院的谢涛和冯登国仅用了 2的20.96次幂 的碰撞算法复杂度，破解了MD5的碰撞抵抗，该攻击在普通计算机上运行只需要数秒钟。

二、算法原理

MD5 摘要算法大概计算过程可以描述如下：
MD5 将 “输入信息” 分为N*512bit的数据分组；
每一512bit分组又分为16个子分组，每个子分组为32bit的原始数据；
16个子分组分别命名为 M0~M15；
每个子分组都要进行4次运算，运算公式分别为FF、GG、HH、II；
总的运算次数为N*16*4（运算均为位运算）。

“输入信息” 分组计算情况如下图所示：

MD5分组计算

以上为MD5 摘要算法的大概原理总结，下边按照 rfc1321 中算法的介绍顺序，梳理MD5 摘要算法：

  • 填充数据
    填充数据，使 输入数据 % 512 = 448
  • 填充长度信息
    补充 “输入信息” 位长 (Bits Length)信息，占用空间64位
  • 初始化A、B、C、D 四个数据
    初始化 A、B、C、D 四个数据，用于后续的分组计算
  • 分组数据运算
    512bit分组数据，需进行16 * 4 = 64次运算

2.1 填充数据

首先需要对 “输入信息” 进行填充，使其位长对512求余的结果为448（填充必须进行，即使其位长对512求余的结果等于448）。

填充数据的方式：
在 “输入信息” 的后面填充一个1和无数个0，直到满足上面的条件时才停止信息填充。

填充后的 “输入信息” 其位长 (Bits Length) 将扩展到：
N*512+448 ( N>=0 )

2.2 补充长度信息

用64bit记录 “输入信息” 的位长 (Bits Length)，把64位长度二进制数据补在最后。

经过此步骤后，其位长 (Bits Length) 将扩展到：
N*512+448+64 = (N+1)*512 ( N>=0 )

2.3 初始化A、B、C、D

这里需要初始化四个数据 A、B、C、D，这四个变量将用于后续的公式计算。
四个数据均为8个16进制数据组合，每个16进制数据为4bit，每个数据占32bit。

// 每个数据占空间 32bit 
// 四个数据分别为 8个 16进制数据的组合构成
// 单个16进制数据占空间 4bit
A: 01 23 45 67 （16进制）
B: 89 ab cd ef （16进制）
C: fe dc ba 98 （16进制）
D: 76 54 32 10 （16进制）

将A、B、C、D输入计算机进行计算时，A、B、C、D将变化为：

A: 0x67452301
B: 0xefcdab89
C: 0x98badcfe
D: 0x10325476

为什么会变化为 0x67452301、0xefcdab89、0x98badcfe、0x10325476 ？

// A的16进制表示
A: 01 23 45 67 （16进制）
// A的二进制表示
A: 00000 0001 0010 0011 0100 0101 0110 0111 （二进制）
// 计算机中首先编写的为低字节位，当从右向左获取字节数据(8位一个字节)时，最终A将变化为0x67452301
A: 67 45 23 01 （16进制）

2.4 分组数据运算

上文层提到子分组的运算公式：FF、GG、HH、II ，32bit子分组的运算公式如下：

// FF、GG、HH、II
// <<< 为循环左移
FF(a ,b ,c ,d ,Mj ,s ,ti) 操作为 a = b + ( (a + F(b,c,d) + Mj + ti) <<< s)
GG(a ,b ,c ,d ,Mj ,s ,ti) 操作为 a = b + ( (a + G(b,c,d) + Mj + ti) <<< s)
HH(a ,b ,c ,d ,Mj ,s ,ti) 操作为 a = b + ( (a + H(b,c,d) + Mj + ti) <<< s)
II(a ,b ,c ,d ,Mj ,s ,ti) 操作为 a = b + ( (a + I(b,c,d) + Mj + ti) <<< s)

// F、G、H、I
F( X ,Y ,Z ) = ( X & Y ) | ( (~X) & Z )
G( X ,Y ,Z ) = ( X & Z ) | ( Y & (~Z) )
H( X ,Y ,Z ) =X ^ Y ^ Z
I( X ,Y ,Z ) =Y ^ ( X | (~Z) )
  • 公式中初始输入数据a、b、c、d 为A、B、C、D
  • Mj 代表32bit子分组数据，每个子分组数据均需要经过 FF、GG、HH、II 四次运算：
    512bit原始输入数据，有16个子分组，每个分组进行4次运算，总共16 * 4 = 64次运算。
  • s 常量数据，代表循环左移的位数。
  • ti 常量；

512bit分组数据，64 次位运算如下（输入数据为32bit原始数据，输出为32bit数据）：

// 512bit分组数据，16 * 4 次运算
// 输入数据为32bit原始数据，输出为32bit数据
// 第一次运算FF
a = FF(a, b, c, d, M0, 7, 0xd76aa478L);
d = FF(d, a, b, c, M1, 12, 0xe8c7b756L);
c = FF(c, d, a, b, M2, 17, 0x242070dbL);
b = FF(b, c, d, a, M3, 22, 0xc1bdceeeL);
a = FF(a, b, c, d, M4, 7, 0xf57c0fafL);
d = FF(d, a, b, c, M5, 12, 0x4787c62aL);
c = FF(c, d, a, b, M6, 17, 0xa8304613L);
b = FF(b, c, d, a, M7, 22, 0xfd469501L);
a = FF(a, b, c, d, M8, 7, 0x698098d8L); 
d = FF(d, a, b, c, M9, 12, 0x8b44f7afL);
c = FF(c, d, a, b, M10, 17, 0xffff5bb1L);
b = FF(b, c, d, a, M11, 22, 0x895cd7beL);
a = FF(a, b, c, d, M12, 7, 0x6b901122L);
d = FF(d, a, b, c, M13, 12, 0xfd987193L);
c = FF(c, d, a, b, M14, 17, 0xa679438eL);
b = FF(b, c, d, a, M15, 22, 0x49b40821L);

// 第二轮运算GG
a = GG(a, b, c, d, M1, 5, 0xf61e2562L);
d = GG(d, a, b, c, M6, 9, 0xc040b340L);
c = GG(c, d, a, b, M11, 14, 0x265e5a51L);
b = GG(b, c, d, a, M0, 20, 0xe9b6c7aaL);
a = GG(a, b, c, d, M5, 5, 0xd62f105dL);
d = GG(d, a, b, c, M10, 9, 0x2441453L);
c = GG(c, d, a, b, M15, 14, 0xd8a1e681L);
b = GG(b, c, d, a, M4, 20, 0xe7d3fbc8L);
a = GG(a, b, c, d, M9, 5, 0x21e1cde6L);
d = GG(d, a, b, c, M14, 9, 0xc33707d6L);
c = GG(c, d, a, b, M3, 14, 0xf4d50d87L);
b = GG(b, c, d, a, M8, 20, 0x455a14edL);
a = GG(a, b, c, d, M13, 5, 0xa9e3e905L);
d = GG(d, a, b, c, M2, 9, 0xfcefa3f8L);
c = GG(c, d, a, b, M7, 14, 0x676f02d9L);
b = GG(b, c, d, a, M12, 20, 0x8d2a4c8aL);

// 第三轮运算HH
a = HH(a, b, c, d, M5, 4, 0xfffa3942L);
d = HH(d, a, b, c, M8, 11, 0x8771f681L);
c = HH(c, d, a, b, M11, 16, 0x6d9d6122L);
b = HH(b, c, d, a, M14, 23, 0xfde5380cL);
a = HH(a, b, c, d, M1, 4, 0xa4beea44L);
d = HH(d, a, b, c, M4, 11, 0x4bdecfa9L);
c = HH(c, d, a, b, M7, 16, 0xf6bb4b60L);
b = HH(b, c, d, a, M10, 23, 0xbebfbc70L);
a = HH(a, b, c, d, M13, 4, 0x289b7ec6L);
d = HH(d, a, b, c, M0, 11, 0xeaa127faL);
c = HH(c, d, a, b, M3, 16, 0xd4ef3085L);
b = HH(b, c, d, a, M6, 23, 0x4881d05L);
a = HH(a, b, c, d, M9, 4, 0xd9d4d039L);
d = HH(d, a, b, c, M12, 11, 0xe6db99e5L);
c = HH(c, d, a, b, M15, 16, 0x1fa27cf8L);
b = HH(b, c, d, a, M2, 23, 0xc4ac5665L);

// 第四轮运算II
a = II(a, b, c, d, M0, 6, 0xf4292244L);
d = II(d, a, b, c, M7, 10, 0x432aff97L);
c = II(c, d, a, b, M14, 15, 0xab9423a7L);
b = II(b, c, d, a, M5, 21, 0xfc93a039L);
a = II(a, b, c, d, M12, 6, 0x655b59c3L);
d = II(d, a, b, c, M3, 10, 0x8f0ccc92L);
c = II(c, d, a, b, M10, 15, 0xffeff47dL);
b = II(b, c, d, a, M1, 21, 0x85845dd1L);
a = II(a, b, c, d, M8, 6, 0x6fa87e4fL);
d = II(d, a, b, c, M15, 10, 0xfe2ce6e0L);
c = II(c, d, a, b, M6, 15, 0xa3014314L);
b = II(b, c, d, a, M13, 21, 0x4e0811a1L);
a = II(a, b, c, d, M4, 6, 0xf7537e82L);
d = II(d, a, b, c, M11, 10, 0xbd3af235L);
c = II(c, d, a, b, M2, 15, 0x2ad7d2bbL);
b = II(b, c, d, a, M9, 21, 0xeb86d391L);

2.5 结果累加

若A、B、C、D为变量，并且A、B、C、D的初始化信息为 A: 0x67452301；B: 0xefcdab89；C: 0x98badcfe；D: 0x10325476 ，每一512bit分组的运算结果为a、b、c、d。则第N个512bit组的计算结果为：

// a、b、c、d 为每一512bit分组的运算结果； 
// A、B、C、D 是下一组计算的输入参数；
// 若无下一个512bit分组 A、B、C、D 则为最终计算结果；
A = a + A;  
B = b + B; 
C = c + C; 
D = d + D;

三、编码实现 MD5 摘要算法

网上找到一个用Java编码实现MD5摘要算法的案例，我从头到尾加了详细的注释。因此对于代码实现，朋友们可以结合注释读代码，打日志进行MD5摘要算法分析、学习。


/**
 * Java 实现MD5摘要算法：
 * 基本每一行我都加了注释，因此不再对代码进行详细介绍，
 * 如有疑问，可联系：[email protected]
 */
public class MD5Hash {

    /**
     * RFC1321中定义的标准4*4矩阵的常量:循环位移常量数据 s
     */
    static final int S11 = 7, S12 = 12, S13 = 17, S14 = 22;
    static final int S21 = 5, S22 = 9, S23 = 14, S24 = 20;
    static final int S31 = 4, S32 = 11, S33 = 16, S34 = 23;
    static final int S41 = 6, S42 = 10, S43 = 15, S44 = 21;

    /**
     * 填充数据 1000 0000 0000 ...
     * 长度：64*8 = 512bit
     * 注：-128为1000 0000
     */
    static final byte[] PADDING =
            {
                    -128, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                    0, 0, 0, 0, 0, 0, 0
            };
    /**
     * a、b、c、d 四个变量
     */
    private long[] abcd = new long[4];

    /**
     * 512字节分组数据缓冲 64*8=512bit
     */
    private byte[] buffer512Bit = new byte[64];
    // 输入数据的位长信息（64bit）
    private long[] inputBitCount = new long[2];


    /**
     * MD5计算结果
     */
    // MD5计算结果：16 * 8bit = 128bit
    public byte[] md5ByteArray = new byte[16];
    // MD5计算结果：字符串表示的MD5计算结果
    public String md5ResultStr;


    /**
     * 调用其可对任意字符串进行加密运算，并以字符串形式返回加密结果。
     *
     * @param inputStr 输入字符串
     * @return 输入md5计算结果
     */
    public String getMD5(String inputStr) {
        // 数据初始化A、B、C、D
        md5Init();
        // 调用MD5的主计算过程
        md5Update(inputStr.getBytes(), inputStr.length());
        // 输出结果到digest数组中
        md5Final();
        // 转化为16进制字符串
        for (int i = 0; i < 16; i++) {
            md5ResultStr += byte2HEX(md5ByteArray[i]);
        }
        return md5ResultStr;
    }

    // #######################################################

    /**
     * 构造方法：初始化MD5核心变量
     */
    public MD5Hash() {
        md5Init();
    }

    /**
     * 初始化MD5核心变量
     */
    private void md5Init() {
        // 定义state为RFC1321中定义的标准幻数
        abcd[0] = 0x67452301L;
        abcd[1] = 0xefcdab89L;
        abcd[2] = 0x98badcfeL;
        abcd[3] = 0x10325476L;
        // 初始化 输入数据的位长信息
        inputBitCount[0] = inputBitCount[1] = 0L;

        // MD5计算结果：初始化digest数组元素为0
        for (int i = 0; i < 16; i++) {
            md5ByteArray[i] = 0;
        }
        // MD5计算结果：初始化resultStr
        md5ResultStr = "";
    }


    /**
     * MD5的主计算过程:
     *
     * @param inputByte    输入数据字节流
     * @param inputByteLen 输入数据字节长度
     */
    private void md5Update(byte[] inputByte, int inputByteLen) {
        int i, index, partLen;

        // 分配64个字节分组缓冲区：64*8bit = 512bit
        byte[] blockByteArray = new byte[64];

        // 添加inputByte信息前输入信息 字节长度（取低6位）
        index = (int) (inputBitCount[0] >>> 3) & 0x3F;
        System.out.println("index: " + index);
        // 添加inputByteLen信息后，最新的输入信息 位长
        // (inputByteLen << 3) = (inputByteLen * 8) 为输入数据位长（bit length）
        if ((inputBitCount[0] += (inputByteLen << 3)) < (inputByteLen << 3)) {
            inputBitCount[1]++;
        }
        // 0
        inputBitCount[1] += (inputByteLen >>> 29);

        // 差多少满512bit（64字节）
        partLen = 64 - index;

        if (inputByteLen >= partLen) {
            // 拷贝 partLen 字节数据
            // 数据运算
            md5Memcpy(buffer512Bit, inputByte, index, 0, partLen);
            md5Transform(buffer512Bit);
            //
            for (i = partLen; i + 63 < inputByteLen; i += 64) {
                // 拷贝64字节数据
                // 数据运算
                md5Memcpy(blockByteArray, inputByte, 0, i, 64);
                md5Transform(blockByteArray);
            }
            index = 0;
        } else {
            i = 0;
        }
        // 拷贝64字节数据
        md5Memcpy(buffer512Bit, inputByte, index, i, inputByteLen - i);
    }

    /**
     * 整理和填写输出结果，结果放到数组digest中。
     */
    private void md5Final() {
        /**
         * 64位输入数据的位长信息（bit length）
         * 数组中：低位在前，高位在后
         */
        // 8个字节 缓存空间 8 * 8bit = 64bit
        byte[] bits = new byte[8];
        longArray2ByteArray(bits, inputBitCount, 8);

        // 输入信息的字节数byte length
        int index = (int) (inputBitCount[0] >>> 3) & 0x3f;
        // 输入信息的位长<448,补充到448；输入信息的位长>=448,补充到（512+448）= 960，960/8=120字节
        // (56 * 8bit = 448bit)
        int padLen = (index < 56) ? (56 - index) : (120 - index);

        /**
         * 数据填充： N * 512 + 448
         */
        md5Update(PADDING, padLen);
        /**
         * 1、数据填充： N * 512 + 448 + 64
         * 2、计算最后一个分组数据
         */
        md5Update(bits, 8);

        /**
         * 根据a、b、c、d 得到最终的 md5ByteArray 数据结果
         * 数组结果中（低位在前，高位在后）
         */
        longArray2ByteArray(md5ByteArray, abcd, 16);
    }

    /**
     * MD5核心变换计算程序: 由md5Update函数调用，block是分块的原始字节数组
     *
     * @param blockByteArray 512bit分组数据，分为16个子分组，每个分组32bit数据
     */
    private void md5Transform(byte blockByteArray[]) {
        // 初始化a、b、c、d
        long a = abcd[0], b = abcd[1], c = abcd[2], d = abcd[3];
        // 512bit分成16个子分组,每个分组32bit
        // 16 * 32bit = 512bit
        long[] M32 = new long[16];
        byteArray2LongArray(M32, blockByteArray, 64);
        // 进行4级级联运算
        // 第1级
        a = FF(a, b, c, d, M32[0], S11, 0xd76aa478L); /* 1 */
        d = FF(d, a, b, c, M32[1], S12, 0xe8c7b756L); /* 2 */
        c = FF(c, d, a, b, M32[2], S13, 0x242070dbL); /* 3 */
        b = FF(b, c, d, a, M32[3], S14, 0xc1bdceeeL); /* 4 */
        a = FF(a, b, c, d, M32[4], S11, 0xf57c0fafL); /* 5 */
        d = FF(d, a, b, c, M32[5], S12, 0x4787c62aL); /* 6 */
        c = FF(c, d, a, b, M32[6], S13, 0xa8304613L); /* 7 */
        b = FF(b, c, d, a, M32[7], S14, 0xfd469501L); /* 8 */
        a = FF(a, b, c, d, M32[8], S11, 0x698098d8L); /* 9 */
        d = FF(d, a, b, c, M32[9], S12, 0x8b44f7afL); /* 10 */
        c = FF(c, d, a, b, M32[10], S13, 0xffff5bb1L); /* 11 */
        b = FF(b, c, d, a, M32[11], S14, 0x895cd7beL); /* 12 */
        a = FF(a, b, c, d, M32[12], S11, 0x6b901122L); /* 13 */
        d = FF(d, a, b, c, M32[13], S12, 0xfd987193L); /* 14 */
        c = FF(c, d, a, b, M32[14], S13, 0xa679438eL); /* 15 */
        b = FF(b, c, d, a, M32[15], S14, 0x49b40821L); /* 16 */

        // 第2级
        a = GG(a, b, c, d, M32[1], S21, 0xf61e2562L); /* 17 */
        d = GG(d, a, b, c, M32[6], S22, 0xc040b340L); /* 18 */
        c = GG(c, d, a, b, M32[11], S23, 0x265e5a51L); /* 19 */
        b = GG(b, c, d, a, M32[0], S24, 0xe9b6c7aaL); /* 20 */
        a = GG(a, b, c, d, M32[5], S21, 0xd62f105dL); /* 21 */
        d = GG(d, a, b, c, M32[10], S22, 0x2441453L); /* 22 */
        c = GG(c, d, a, b, M32[15], S23, 0xd8a1e681L); /* 23 */
        b = GG(b, c, d, a, M32[4], S24, 0xe7d3fbc8L); /* 24 */
        a = GG(a, b, c, d, M32[9], S21, 0x21e1cde6L); /* 25 */
        d = GG(d, a, b, c, M32[14], S22, 0xc33707d6L); /* 26 */
        c = GG(c, d, a, b, M32[3], S23, 0xf4d50d87L); /* 27 */
        b = GG(b, c, d, a, M32[8], S24, 0x455a14edL); /* 28 */
        a = GG(a, b, c, d, M32[13], S21, 0xa9e3e905L); /* 29 */
        d = GG(d, a, b, c, M32[2], S22, 0xfcefa3f8L); /* 30 */
        c = GG(c, d, a, b, M32[7], S23, 0x676f02d9L); /* 31 */
        b = GG(b, c, d, a, M32[12], S24, 0x8d2a4c8aL); /* 32 */

        // 第3级
        a = HH(a, b, c, d, M32[5], S31, 0xfffa3942L); /* 33 */
        d = HH(d, a, b, c, M32[8], S32, 0x8771f681L); /* 34 */
        c = HH(c, d, a, b, M32[11], S33, 0x6d9d6122L); /* 35 */
        b = HH(b, c, d, a, M32[14], S34, 0xfde5380cL); /* 36 */
        a = HH(a, b, c, d, M32[1], S31, 0xa4beea44L); /* 37 */
        d = HH(d, a, b, c, M32[4], S32, 0x4bdecfa9L); /* 38 */
        c = HH(c, d, a, b, M32[7], S33, 0xf6bb4b60L); /* 39 */
        b = HH(b, c, d, a, M32[10], S34, 0xbebfbc70L); /* 40 */
        a = HH(a, b, c, d, M32[13], S31, 0x289b7ec6L); /* 41 */
        d = HH(d, a, b, c, M32[0], S32, 0xeaa127faL); /* 42 */
        c = HH(c, d, a, b, M32[3], S33, 0xd4ef3085L); /* 43 */
        b = HH(b, c, d, a, M32[6], S34, 0x4881d05L); /* 44 */
        a = HH(a, b, c, d, M32[9], S31, 0xd9d4d039L); /* 45 */
        d = HH(d, a, b, c, M32[12], S32, 0xe6db99e5L); /* 46 */
        c = HH(c, d, a, b, M32[15], S33, 0x1fa27cf8L); /* 47 */
        b = HH(b, c, d, a, M32[2], S34, 0xc4ac5665L); /* 48 */

        // 第4级
        a = II(a, b, c, d, M32[0], S41, 0xf4292244L); /* 49 */
        d = II(d, a, b, c, M32[7], S42, 0x432aff97L); /* 50 */
        c = II(c, d, a, b, M32[14], S43, 0xab9423a7L); /* 51 */
        b = II(b, c, d, a, M32[5], S44, 0xfc93a039L); /* 52 */
        a = II(a, b, c, d, M32[12], S41, 0x655b59c3L); /* 53 */
        d = II(d, a, b, c, M32[3], S42, 0x8f0ccc92L); /* 54 */
        c = II(c, d, a, b, M32[10], S43, 0xffeff47dL); /* 55 */
        b = II(b, c, d, a, M32[1], S44, 0x85845dd1L); /* 56 */
        a = II(a, b, c, d, M32[8], S41, 0x6fa87e4fL); /* 57 */
        d = II(d, a, b, c, M32[15], S42, 0xfe2ce6e0L); /* 58 */
        c = II(c, d, a, b, M32[6], S43, 0xa3014314L); /* 59 */
        b = II(b, c, d, a, M32[13], S44, 0x4e0811a1L); /* 60 */
        a = II(a, b, c, d, M32[4], S41, 0xf7537e82L); /* 61 */
        d = II(d, a, b, c, M32[11], S42, 0xbd3af235L); /* 62 */
        c = II(c, d, a, b, M32[2], S43, 0x2ad7d2bbL); /* 63 */
        b = II(b, c, d, a, M32[9], S44, 0xeb86d391L); /* 64 */

        //分别累加到 a[0], b[1], c[2], d[3]
        abcd[0] += a;
        abcd[1] += b;
        abcd[2] += c;
        abcd[3] += d;
    }


    // #######################################################

    //定义F G H I 为4个基数 ，即为4个基本的MD5函数,进行简单的位运算
    private long F(long x, long y, long z) {
        return (x & y) | ((~x) & z);
    }

    private long G(long x, long y, long z) {
        return (x & z) | (y & (~z));
    }

    private long H(long x, long y, long z) {
        return x ^ y ^ z;
    }

    private long I(long x, long y, long z) {
        return y ^ (x | (~z));
    }

    // FF,GG,HH和II调用F,G,H,I函数进行进一步变换
    private long FF(long a, long b, long c, long d, long x, long s, long ac) {
        a += F(b, c, d) + x + ac;
        // 循环左移s位
        //这里long型数据右移时使用无符号右移运算符>>>
        a = ((int) a << s) | ((int) a >>> (32 - s));
        a += b;
        return a;
    }

    private long GG(long a, long b, long c, long d, long x, long s, long ac) {
        a += G(b, c, d) + x + ac;
        // 循环左移s位
        //这里long型数据右移时使用无符号右移运算符>>>
        a = ((int) a << s) | ((int) a >>> (32 - s));
        a += b;
        return a;
    }

    private long HH(long a, long b, long c, long d, long x, long s, long ac) {
        a += H(b, c, d) + x + ac;
        // 循环左移s位
        //这里long型数据右移时使用无符号右移运算符>>>
        a = ((int) a << s) | ((int) a >>> (32 - s));
        a += b;
        return a;
    }

    private long II(long a, long b, long c, long d, long x, long s, long ac) {
        a += I(b, c, d) + x + ac;
        // 循环左移s位
        //这里long型数据右移时使用无符号右移运算符>>>
        a = ((int) a << s) | ((int) a >>> (32 - s));
        a += b;
        return a;
    }

    // #######################################################


    /**
     * byte数组的块拷贝函数：将input数组中的起始位置为inpos，长度len的数据拷贝到output数组起始位置outpos处
     */
    private void md5Memcpy(byte[] output, byte[] input, int outpos, int inpos,
                           int len) {
        int i;
        for (i = 0; i < len; i++) {
            output[outpos + i] = input[inpos + i];
        }
    }

    // #######################################################


    /**
     * 把byte类型的数据转换成十六进制ASCII字符表示
     *
     * @param in
     * @return
     */
    private static String byte2HEX(byte in) {
        char[] digitStr =
                {
                        '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
                        'A', 'B', 'C', 'D', 'E', 'F'
                };
        char[] out = new char[2];
        out[0] = digitStr[(in >> 4) & 0x0F]; //取高4位
        out[1] = digitStr[in & 0x0F];        //取低4位
        String s = new String(out);
        return s;
    }

    /**
     * 将long型数组按顺序拆成byte型数组 （低位在前，高位在后）
     *
     * @param outputByteArray 输出byte数组
     * @param inputLongArray  输入long数组
     * @param byteLength      outputByteArray字节数组的长度
     */
    private void longArray2ByteArray(byte[] outputByteArray, long[] inputLongArray, int byteLength) {
        int i, j;
        for (i = 0, j = 0; j < byteLength; i++, j += 4) {
            // 低8位
            outputByteArray[j] = (byte) (inputLongArray[i] & 0xffL);
            // 中间8位[低]
            outputByteArray[j + 1] = (byte) ((inputLongArray[i] >>> 8) & 0xffL);
            // 中间8位[高]
            outputByteArray[j + 2] = (byte) ((inputLongArray[i] >>> 16) & 0xffL);
            // 高8位
            outputByteArray[j + 3] = (byte) ((inputLongArray[i] >>> 24) & 0xffL);
        }
    }

    /**
     * 将byte型数组按顺序合成long型数组，长度为len
     *
     * @param output
     * @param input
     * @param len
     */
    private void byteArray2LongArray(long[] output, byte[] input, int len) {
        int i, j;
        for (i = 0, j = 0; j < len; i++, j += 4) {
            output[i] = byte2Long(input[j])
                    | (byte2Long(input[j + 1]) << 8)
                    | (byte2Long(input[j + 2]) << 16)
                    | (byte2Long(input[j + 3]) << 24);
        }
    }

    /**
     * 把byte型数据转换为无符号long型数据
     *
     * @param b
     * @return
     */
    private static long byte2Long(byte b) {
        return b > 0 ? b : (b & 0x7F + 128);
    }
}

四、MD5 API使用

Java中使用Java API实现MD5的代码片段，记录一下，留着以后 coding 时快速使用：

public static String getMd5(String inputStr) {
    String md5Str = "";
    // 判空处理
    if (inputStr == null || inputStr.equals("")) {
        return md5Str;
    }
    try {
        //
        // 1、得到长度为16的byte字节数组
        MessageDigest md = MessageDigest.getInstance("md5");
        md.update(inputStr.getBytes());
        byte[] bytes = md.digest();
        //
        // 2、长度为16的byte字节数组，转化为长度为32的字符串
        StringBuilder sb = new StringBuilder();
        for (byte b : bytes) {
            // 转化为16进制字符串
            String hexStr = Integer.toHexString(b & 0xFF);
            // 字符串长度为1时补0
            if (hexStr.length() == 1) {
                sb.append("0");
            }
            sb.append(hexStr);
        }
        // 得到长度为32的字符串
        md5Str = sb.toString();
    } catch (Exception e) {
        e.printStackTrace();
    }
    return md5Str;
}

五、参考：

MD5 Message-Digest：
https://datatracker.ietf.org/doc/html/rfc1321

RFC 6151：
https://datatracker.ietf.org/doc/html/rfc6151

维基百科MD5：
https://zh.wikipedia.org/wiki/MD5

MD5算法原理：
https://www.cnblogs.com/nhdlb/p/12007162.html

MD5算法：
https://blog.csdn.net/sinat_27933301/article/details/79538169

= THE END =

欢迎关注我的公众号


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK