哈希算法—MD5介绍

算法的输入：任意长度的明文消息
算法输出：128比特长，或者说32个十六进制数的消息摘要

MD5的应用场景

1、数据完整性校验：MD5算法常用于验证数据的完整性。在数据传输过程中，发送方可以计算数据的MD5哈希值将其发送给接收方。接收方收到数据后，再次计算哈希值并与发送方提供的哈希值进行比较。如果两者匹配，则说明数据在传输过程中没有被篡改。

2、密码存储：MD5算法也常用于密码存储。将用户的密码通过MD5哈希后存储到数据库中，即时数据库被泄露，攻击者也无法直接获取用户的明文你密码。然而，由于MD5算法存在已知的安全漏洞（如彩虹表攻击和碰撞攻击），现在已不推荐使用MD5来存储密码。更安全的做法是使用加盐哈希（如bcrypt或Argon2）。

MD5算法原理

MD5算法的实现，可以分为以下4个步骤：

MD5算法的整体流程如上图所示，主要分为4步：处理原文、设置初始值、循环加工、拼接结果。

（一）处理原文

处理原文就是一个关键词：补位，此处的补位有两个地方需要补。那具体怎么补位呢？

1、填充。如果输入信息的长度(bit)对512求余的结果不等于448，就需要填充使得对512求余的结果等于448。填充的方法是填充一个1和n个0。填充完后，信息的长度就为N*512+448(bit)；

到这里，就会有两个问题：

为什么是对512取余，而且为什么补位要补到对512取余后为448？
如果原文的长度本来就是对512取余是448呢，是不是就不需要进行填充位的填补了？

首先我们来解决第2个问题：假设原文长度为len，且mod(len, 512) = 448，则需要再补充512位的填充位。假设填充位长度为appendLen，则有伪代码：


if(mod(len, 512) < 448) {
  appendLen = 448 - mod(len, 512);
} else {
  appendLen = 448 + 512 - mod(len, 512);
}

至于第1个问题，我们接着往下看：

2、补数据长度：这里需要补64位的原文长度，我们会发现，补充齐64位后，整体的长度就是512的整数倍了。这里就可以回答上面的第一个问题了：MD5是一种基于block的算法，要求每次处理的block都是512bits。64位的数据长度，即最长可以是2^64 。那如果原文的长度len > 2^64呢？则取len的低阶64位进行填充。

此时的数据是16字（32位）的整数倍，用M[0，…，N-1]表示此时的数据，其中N为16的倍数。如下图所示：

（二）设置初始值

装入标准幻数（四个整数）。标准的幻数（物理顺序）是（A=(01234567)16，B=(89ABCDEF)16，C=(FEDCBA98)16，D=(76543210)16）。

如果在程序中定义应该是:（A=0X67452301L，B=0XEFCDAB89L，C=0X98BADCFEL，D=0X10325476L）这样表示的原因是因为，数据在内存在为小端存储，举个例子，假设我们有一个16位的整数0x1234（这里0x表示十六进制数），在小端存储的系统中，这个数会被存储为0x34 0x12，其中0x34存储在低地址，0x12存储在高地址。

A=0x01234567
B=0x89ABCDEF
C=0xFEDCBA98
D=0x76543210

（三）循环加工

这一步是整个算法最重要的一步。

图中，ABCD就是哈希值的四个分组，每一次循环都会让旧的ABCD产生新的ABCD。一共进行多少次循环呢？由处理后的原文长度决定。

假设经过第一步处理原文之后的长度为M，则主循环次数L=M÷512，每个主循环中包含512÷32*4=64次子循环，分为4组16次。上面这张图表达的是一次子循环的流程。

主循环次数 = M / 512
每个主循环中包含 512 / 32 * 4 = 64 次子循环

其中F是一个非线性函数。MD5用到的非线性函数有下面四种，4组循环中依次使用FGHI。

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))

其中Mi为原文的一个分组，长度为32bits，每次循环所用到的分组编号不同，会交替使用到M0到M15中的数据。

而Ki则是一个32bits的常量，具体的计算公式如下：

Ki=floor(2^64*sin(i)) i的范围是1~64，单位是弧度

而<<<s则代表移位操作，注意：这里的移位是循环移位！而移多少位，则如下：

[7，12，17，22 ]
[5，9，14，20]
[4，11，16，23]
[6，10，15，21]

第一组16次循环中依次使用【7，12，17，22】，使用4次，以此类推。所以经过一次循环后可以发现(其中=左边为新，等号右边全部使用旧的abcd)：

A—>经过运算—>B
B—>直接—>C
C—>直接—>D
D—>直接—>A

a=d
b=(F(b，c，d)+Mi+Ki)<<<s+a
c=a
d=c

而一次主循环的4组16次子循环依次如下：

 第一轮
a=FF(a,b,c,d,M0,7,0xd76aa478)
b=FF(d,a,b,c,M1,12,0xe8c7b756)
c=FF(c,d,a,b,M2,17,0x242070db)
d=FF(b,c,d,a,M3,22,0xc1bdceee)
a=FF(a,b,c,d,M4,7,0xf57c0faf)
b=FF(d,a,b,c,M5,12,0x4787c62a)
c=FF(c,d,a,b,M6,17,0xa8304613)
d=FF(b,c,d,a,M7,22,0xfd469501)
a=FF(a,b,c,d,M8,7,0x698098d8)
b=FF(d,a,b,c,M9,12,0x8b44f7af)
c=FF(c,d,a,b,M10,17,0xffff5bb1)
d=FF(b,c,d,a,M11,22,0x895cd7be)
a=FF(a,b,c,d,M12,7,0x6b901122)
b=FF(d,a,b,c,M13,12,0xfd987193)
c=FF(c,d,a,b,M14,17,0xa679438e)
d=FF(b,c,d,a,M15,22,0x49b40821)

第二轮
a=GG(a,b,c,d,M1,5,0xf61e2562)
b=GG(d,a,b,c,M6,9,0xc040b340)
c=GG(c,d,a,b,M11,14,0x265e5a51)
d=GG(b,c,d,a,M0,20,0xe9b6c7aa)
a=GG(a,b,c,d,M5,5,0xd62f105d)
b=GG(d,a,b,c,M10,9,0x02441453)
c=GG(c,d,a,b,M15,14,0xd8a1e681)
d=GG(b,c,d,a,M4,20,0xe7d3fbc8)
a=GG(a,b,c,d,M9,5,0x21e1cde6)
b=GG(d,a,b,c,M14,9,0xc33707d6)
c=GG(c,d,a,b,M3,14,0xf4d50d87)
d=GG(b,c,d,a,M8,20,0x455a14ed)
a=GG(a,b,c,d,M13,5,0xa9e3e905)
b=GG(d,a,b,c,M2,9,0xfcefa3f8)
c=GG(c,d,a,b,M7,14,0x676f02d9)
d=GG(b,c,d,a,M12,20,0x8d2a4c8a)

第三轮
a=HH(a,b,c,d,M5,4,0xfffa3942)
b=HH(d,a,b,c,M8,11,0x8771f681)
c=HH(c,d,a,b,M11,16,0x6d9d6122)
d=HH(b,c,d,a,M14,23,0xfde5380c)
a=HH(a,b,c,d,M1,4,0xa4beea44)
b=HH(d,a,b,c,M4,11,0x4bdecfa9)
c=HH(c,d,a,b,M7,16,0xf6bb4b60)
d=HH(b,c,d,a,M10,23,0xbebfbc70)
a=HH(a,b,c,d,M13,4,0x289b7ec6)
b=HH(d,a,b,c,M0,11,0xeaa127fa)
c=HH(c,d,a,b,M3,16,0xd4ef3085)
d=HH(b,c,d,a,M6,23,0x04881d05)
a=HH(a,b,c,d,M9,4,0xd9d4d039)
b=HH(d,a,b,c,M12,11,0xe6db99e5)
c=HH(c,d,a,b,M15,16,0x1fa27cf8)
d=HH(b,c,d,a,M2,23,0xc4ac5665)

第四轮
a=II(a,b,c,d,M0,6,0xf4292244)
b=II(d,a,b,c,M7,10,0x432aff97)
c=II(c,d,a,b,M14,15,0xab9423a7)
d=II(b,c,d,a,M5,21,0xfc93a039)
a=II(a,b,c,d,M12,6,0x655b59c3)
b=II(d,a,b,c,M3,10,0x8f0ccc92)
c=II(c,d,a,b,M10,15,0xffeff47d)
d=II(b,c,d,a,M1,21,0x85845dd1)
a=II(a,b,c,d,M8,6,0x6fa87e4f)
b=II(d,a,b,c,M15,10,0xfe2ce6e0)
c=II(c,d,a,b,M6,15,0xa3014314)
d=II(b,c,d,a,M13,21,0x4e0811a1)
a=II(a,b,c,d,M4,6,0xf7537e82)
b=II(d,a,b,c,M11,10,0xbd3af235)
c=II(c,d,a,b,M2,15,0x2ad7d2bb)
d=II(b,c,d,a,M9,21,0xeb86d391)

具体的实现和原理这些，都可以参考如下内容：

https://mp.weixin.qq.com/s/Yem3oWb3sg3kh4j-MjWbcA

实现标准MD5算法

#include <jni.h>
#include <string>

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

// Constants are the integer part of the sines of integers (in radians) * 2^32.
const uint32_t k[64] = {
    0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee ,
    0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501 ,
    0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be ,
    0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821 ,
    0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa ,
    0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8 ,
    0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed ,
    0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a ,
    0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c ,
    0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70 ,
    0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05 ,
    0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665 ,
    0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039 ,
    0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1 ,
    0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1 ,
    0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391 };

// r specifies the per-round shift amounts
const uint32_t r[] = {7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
                      5,  9, 14, 20, 5,  9, 14, 20, 5,  9, 14, 20, 5,  9, 14, 20,
                      4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
                      6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21};

// leftrotate function definition
#define LEFTROTATE(x, c) (((x) << (c)) | ((x) >> (32 - (c))))

void to_bytes(uint32_t val, uint8_t *bytes)
{
    bytes[0] = (uint8_t) val;
    bytes[1] = (uint8_t) (val >> 8);
    bytes[2] = (uint8_t) (val >> 16);
    bytes[3] = (uint8_t) (val >> 24);
}

uint32_t to_int32(const uint8_t *bytes)
{
    return (uint32_t) bytes[0]
        | ((uint32_t) bytes[1] << 8)
        | ((uint32_t) bytes[2] << 16)
        | ((uint32_t) bytes[3] << 24);
}

void md5(const uint8_t *initial_msg, size_t initial_len, uint8_t *digest) {

    // These vars will contain the hash
    uint32_t h0, h1, h2, h3;

    // Message (to prepare)
    uint8_t *msg = NULL;

    size_t new_len, offset;
    uint32_t w[16];
    uint32_t a, b, c, d, i, f, g, temp;

    // Initialize variables - simple count in nibbles:
    h0 = 0x67452301;
    h1 = 0xefcdab89;
    h2 = 0x98badcfe;
    h3 = 0x10325476;

    //Pre-processing:
    //append "1" bit to message
    //append "0" bits until message length in bits ≡ 448 (mod 512)
    //append length mod (2^64) to message

    for (new_len = initial_len + 1; new_len % (512/8) != 448/8; new_len++)
        ;

    msg = (uint8_t*)malloc(new_len + 8);
    memcpy(msg, initial_msg, initial_len);
    msg[initial_len] = 0x80; // append the "1" bit; most significant bit is "first"
    for (offset = initial_len + 1; offset < new_len; offset++)
        msg[offset] = 0; // append "0" bits

    // append the len in bits at the end of the buffer.
    to_bytes(initial_len*8, msg + new_len);
    // initial_len>>29 == initial_len*8>>32, but avoids overflow.
    to_bytes(initial_len>>29, msg + new_len + 4);

    // Process the message in successive 512-bit chunks:
    //for each 512-bit chunk of message:
    for(offset=0; offset<new_len; offset += (512/8)) {

        // break chunk into sixteen 32-bit words w[j], 0 ≤ j ≤ 15
        for (i = 0; i < 16; i++)
            w[i] = to_int32(msg + offset + i*4);

        // Initialize hash value for this chunk:
        a = h0;
        b = h1;
        c = h2;
        d = h3;

        // Main loop:
        for(i = 0; i<64; i++) {

            if (i < 16) {
                f = (b & c) | ((~b) & d);
                g = i;
            } else if (i < 32) {
                f = (d & b) | ((~d) & c);
                g = (5*i + 1) % 16;
            } else if (i < 48) {
                f = b ^ c ^ d;
                g = (3*i + 5) % 16;
            } else {
                f = c ^ (b | (~d));
                g = (7*i) % 16;
            }

            temp = d;
            d = c;
            c = b;
            b = b + LEFTROTATE((a + f + k[i] + w[g]), r[i]);
            a = temp;

        }

        // Add this chunk's hash to result so far:
        h0 += a;
        h1 += b;
        h2 += c;
        h3 += d;

    }

    // cleanup
    free(msg);

    //var char digest[16] := h0 append h1 append h2 append h3 //(Output is in little-endian)
    to_bytes(h0, digest);
    to_bytes(h1, digest + 4);
    to_bytes(h2, digest + 8);
    to_bytes(h3, digest + 12);
}


extern "C"
    JNIEXPORT jstring JNICALL
Java_com_roysue_md5_MainActivity_md5(JNIEnv *env, jobject thiz, jstring message) {
    // TODO: implement md5()
    char *msg = const_cast<char *>(env->GetStringUTFChars(message,0));
    int len = strlen(msg);
    uint8_t result[16];
    md5(reinterpret_cast<const uint8_t *>(msg), len, result);
    char res[32];
    for (int i = 0;i < 16 ;i++)
        sprintf(res+i*2,"%2.2x",result[i]);
    return env->NewStringUTF(res);
}

MD5函数算法描述

初始化向量

首先是初始化链接向量。需要4个初始值，每个长32bit。即8个十六进制数。它是运算的主要部分（这块是小端存储）

消息填充

附加填充，使得其比特长度除以512余数448。填充方式为：先填充一个1，后面跟上足够多的0，一直到符合要求。

在上一步新生成的字符串后面加上消息长度。消息长度为8字节=64bit

首先将初始长度*8放到填充字符串的后面；如果初始长度超出32位表示范围，就只取它超出的部分。总共是8个字节

运算

下面是一个循环 “ for(offset=0; offset<new_len; offset += (512/8)) “ 每64个字节为一组，进行分组处理。

如果我们本身的字符串长度小于448，那也就是不用填充。

将64个字节，又分为16个小组（4字节=32bit）

下面将4个初始化链接向量进行了处理

可以表示为下面图所示的样子。。。。（具体实现可以网上查一下）

A—>经过运算—>B

B—>直接—>C

C—>直接—>D

D—>直接—>A

可以看到上图中有F、Mi、Ki等标识。

F：可以理解为一个函数，下面会细说
Mi：表示一种运算，简单理解就是+-*/
Ki：是一种参与运算的特定序列，如下所示。一般情况，该序列是固定的，也就是Ki如果没有修改过，是不会变化的。这个也是辨别当前算法是否为md5的一个思路。

其实图中的F确实表示的是函数，但不是一个函数，而是4个函数，接收三个参数

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))

MD5汇编算法识别

【小技巧】

可以借助PEID中的插件【Krypto ANALyzer】实现对so中的加密算法进行简单分析。

IDA加载so文件后，定位到md5函数为止

有几个关键点，可以帮助判断当前算法是否为MD5

一、4个初始化链接向量

二、两个固定数组（加法常数矩阵+循环左移表）

上面这两个点，可以作为md5算法识别的参考。

同时，如果对MD5算法魔改，其实也是修改常量ABCD 和 加法常数矩阵。