MD5加密算法

发表于： 分类于：
字数： 3965 阅读：≈ 8分钟 浏览： 评论：

在安卓逆向的过程中,对加密算法有足够的了解是必要的,下面将以"password"这个字符串为例,将演示他的加密过程

原始数据准备

字符串: password 二进制: 01110000 01100001 01110011 01110011 01110111 01101111 01110010 01100100
十六进制: 70 61 73 73 77 6F 72 64
长度 8 字节=64 位

完整的 MD5 计算过程

填充消息

1.当输入的字节数小于 56 个字节的时候,对其正常填充 原始长度是 64 位
填充规则:先补一个 1,即 1000 0000,换成 16 进制就是 0x80,再补 0 直到长度 448
计算填充:

  • 64+1+k=448(mod 512)
  • 65+k=448
  • k=383 所以说需要填充 383 个 0
    最后 64 位填充长度即 0x0000000000000040
    完整的填充就是下面这个样子:
1
2
3
4

70 61 73 73 77 6F 72 64 80 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 40 00 00 00 00 00 00 00

2.当输入等于 56 个字节的时候,直接填充长度,不填充 80
3.当输入大于 56 字节,小于 64 字节的时候,此时已经没法填充长度了,例如:输入是 60 个字节,先填充 0x80,接着填充 0x0 填充到 64 字节,接着在新的 512 位的块中,先填充 0x80,然后一直填充 0x0,直到满足 56(mod 64),左后 8 个字节填充长度
4.当输入大于 64 字节的时候,比如:输入是 100 个字节,前 64 字节正常数据块,后 64 字节的前 36 字节填充剩余字节数据,然后一直填充 0,最后 8 字节填充长度

分组 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

M[0]: 0x73736170
M[1]: 0x64726f77
M[2]: 0x00000080
M[3]: 0x00000000
M[4]: 0x00000000
M[5]: 0x00000000
M[6]: 0x00000000
M[7]: 0x00000000
M[8]: 0x00000000
M[9]: 0x00000000
M[10]: 0x00000000
M[11]: 0x00000000
M[12]: 0x00000000
M[13]: 0x00000000
M[14]: 0x00000040
M[15]: 0x00000000

初始化常量

这个是 Md5 算法中第一个关键点:初始化常量,这些参数以小端字节序表示,会参与到后续的运算中,也会影响到最终的结果

1
2
3
4

A = 0x67452301
B = 0xEFCDAB89
C = 0x98BADCFE
D = 0x10325476

最简单的魔改 md5 算法,就是魔改这里的模数

处理分组数据

在前面完成了对数据的填充分组,接下来开始进行运算了,默认的初始变量有 a,b,c,d 四个变量,会以第三步得到的初始化常量值对其进行赋值

1
2
3
4

a = A
b = B
c = C
d = D

之后进行 4 轮循环运算,每轮循环运算进行 16 次运算,分别对应一个非线性函数,以及分组,常量等,每次运算都会得到 a,b,c,d 的值,然后作为新值进行替换,最后经过四轮这样的运算,得到新的 a,b,c,d 的值,然后与初始化常量进行相加,最后将 a,b,c,d 的值进行拼接起来,得到最终的 md5 值

接着就引出了 md5 算法中的第二个关键点:非线性函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def F(X, Y, Z):
    compute = (X & Y) | ((~X) & Z)
    return compute


# if z then x else y
def G(X, Y, Z):
    return (X & Z) | (Y & (~Z))


# if X = Y then Z else ~Z
def H(X, Y, Z):
    return X ^ Y ^ Z


def I(X, Y, Z):
    return Y ^ (X | (~Z))

每一轮都会使用到其中的一个线性函数进行运算,因此,非线性函数也就影响到了最终的结果,常常魔改算法,也会魔改这个地方

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def FF(a, b, c, d, M, s, t):
    result = b + leftCircularShift((a + F(b, c, d) + M + t), s)
    return result


def GG(a, b, c, d, M, s, t):
    result = b + leftCircularShift((a + G(b, c, d) + M + t), s)
    return result


def HH(a, b, c, d, M, s, t):
    result = b + leftCircularShift((a + H(b, c, d) + M + t), s)
    return result


def II(a, b, c, d, M, s, t):
    result = b + leftCircularShift((a + I(b, c, d) + M + t), s)
    return result

接着看一下主要的 64 次运算

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

# Round 1
FF(a, b, c, d, M[0], S1[0], T[0])
FF(d, a, b, c, M[1], S1[1], T[1])
FF(c, d, a, b, M[2], S1[2], T[2])
FF(b, c, d, a, M[3], S1[3], T[3])
FF(a, b, c, d, M[4], S1[0], T[4])
FF(d, a, b, c, M[5], S1[1], T[5])
FF(c, d, a, b, M[6], S1[2], T[6])
FF(b, c, d, a, M[7], S1[3], T[7])
FF(a, b, c, d, M[8], S1[0], T[8])
FF(d, a, b, c, M[9], S1[1], T[9])
FF(c, d, a, b, M[10], S1[2], T[10])
FF(b, c, d, a, M[11], S1[3], T[11])
FF(a, b, c, d, M[12], S1[0], T[12])
FF(d, a, b, c, M[13], S1[1], T[13])
FF(c, d, a, b, M[14], S1[2], T[14])
FF(b, c, d, a, M[15], S1[3], T[15])
# Round 2
GG(a, b, c, d, M[1], S2[0], T[16])
GG(d, a, b, c, M[6], S2[1], T[17])
GG(c, d, a, b, M[11], S2[2], T[18])
GG(b, c, d, a, M[0], S2[3], T[19])
GG(a, b, c, d, M[5], S2[0], T[20])
GG(d, a, b, c, M[10], S2[1], T[21])
GG(c, d, a, b, M[15], S2[2], T[22])
GG(b, c, d, a, M[4], S2[3], T[23])
GG(a, b, c, d, M[9], S2[0], T[24])
GG(d, a, b, c, M[14], S2[1], T[25])
GG(c, d, a, b, M[3], S2[2], T[26])
GG(b, c, d, a, M[8], S2[3], T[27])
GG(a, b, c, d, M[13], S2[0], T[28])
GG(d, a, b, c, M[2], S2[1], T[29])
GG(c, d, a, b, M[7], S2[2], T[30])
GG(b, c, d, a, M[12], S2[3], T[31])
# Round 3
HH(a, b, c, d, M[5], S3[0], T[32])
HH(d, a, b, c, M[8], S3[1], T[33])
HH(c, d, a, b, M[11], S3[2], T[34])
HH(b, c, d, a, M[14], S3[3], T[35])
HH(a, b, c, d, M[1], S3[0], T[36])
HH(d, a, b, c, M[4], S3[1], T[37])
HH(c, d, a, b, M[7], S3[2], T[38])
HH(b, c, d, a, M[10], S3[3], T[39])
HH(a, b, c, d, M[13], S3[0], T[40])
HH(d, a, b, c, M[0], S3[1], T[41])
HH(c, d, a, b, M[3], S3[2], T[42])
HH(b, c, d, a, M[6], S3[3], T[43])
HH(a, b, c, d, M[9], S3[0], T[44])
HH(d, a, b, c, M[12], S3[1], T[45])
HH(c, d, a, b, M[15], S3[2], T[46])
HH(b, c, d, a, M[2], S3[3], T[47])

# Round 4
II(a, b, c, d, M[0], S4[0], T[48])
II(d, a, b, c, M[7], S4[1], T[49])
II(c, d, a, b, M[14], S4[2], T[50])
II(b, c, d, a, M[5], S4[3], T[51])
II(a, b, c, d, M[12], S4[0], T[52])
II(d, a, b, c, M[3], S4[1], T[53])
II(c, d, a, b, M[10], S4[2], T[54])
II(b, c, d, a, M[1], S4[3], T[55])
II(a, b, c, d, M[8], S4[0], T[56])
II(d, a, b, c, M[15], S4[1], T[57])
II(c, d, a, b, M[6], S4[2], T[58])
II(b, c, d, a, M[13], S4[3], T[59])
II(a, b, c, d, M[4], S4[0], T[60])
II(d, a, b, c, M[11], S4[1], T[61])
II(c, d, a, b, M[2], S4[2], T[62])
II(b, c, d, a, M[9], S4[3], T[63])

在这个流程中,会用到 T 常量表,他的值也会影响到算法结果,这里也是一个魔改点,这也是 md5 算法中第三个需要关注的点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

T = [
	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
]

同时还有第四个关键点,常量转换,他也会参与到非线性函数中循环左移的函数运算中,同样是个魔改点

1
2
3
4

S1 = [7, 12, 17, 22]
S2 = [5, 9,  14, 20]
S3 = [4, 11, 16, 23]
S4 = [6, 10, 15, 21]

通过这 64 次初始化常量,T 常量表,常量转换,非线性函数,就得到了新的 a,b,c,d 值
与初始化常量进行相加,就得到了最终的结果

算法代码实现

以下是算法的 C 语言实现

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318

/*
 * RFC1321标准的MD5算法C实现
 * 完全兼容Android Native层和标准C
 */

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

/* 基本类型定义 */
typedef uint32_t UINT4;    /* 32位无符号整数 */
typedef uint8_t POINTER;   /* 无符号字符指针 */

/* MD5上下文结构 */
typedef struct {
  UINT4 state[4];          /* 状态 (A,B,C,D) */
  UINT4 count[2];          /* 位计数 (低32位, 高32位) */
  unsigned char buffer[64]; /* 输入缓冲区 */
} MD5_CTX;

/*
 * MD5基本变换函数定义
 * 每轮使用不同的非线性函数
 */
#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
#define H(x, y, z) ((x) ^ (y) ^ (z))
#define I(x, y, z) ((y) ^ ((x) | (~z)))

/* 循环左移宏 */
#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))

/*
 * 四轮压缩函数中的变换
 * FF/GG/HH/II分别对应四轮
 * 参数: a,b,c,d: 寄存器, x: 消息字, s: 循环左移位数, ac: 常量
 */
#define FF(a, b, c, d, x, s, ac) { \
  (a) += F((b), (c), (d)) + (x) + (UINT4)(ac); \
  (a) = ROTATE_LEFT((a), (s)); \
  (a) += (b); \
}

#define GG(a, b, c, d, x, s, ac) { \
  (a) += G((b), (c), (d)) + (x) + (UINT4)(ac); \
  (a) = ROTATE_LEFT((a), (s)); \
  (a) += (b); \
}

#define HH(a, b, c, d, x, s, ac) { \
  (a) += H((b), (c), (d)) + (x) + (UINT4)(ac); \
  (a) = ROTATE_LEFT((a), (s)); \
  (a) += (b); \
}

#define II(a, b, c, d, x, s, ac) { \
  (a) += I((b), (c), (d)) + (x) + (UINT4)(ac); \
  (a) = ROTATE_LEFT((a), (s)); \
  (a) += (b); \
}

/*
 * T表常量 - 基于sin函数生成
 * T[i] = floor(4294967296 * |sin(i)|)
 */
static const UINT4 T[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
};

/* 循环左移位数表 */
static const unsigned char S[64] = {
  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
};

/* 消息分块索引表 */
static const unsigned char X_index[64] = {
  0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
  1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12,
  5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2,
  0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9
};

/*
 * 字节顺序转换
 * 小端序机器上无需转换，但为了可移植性保留
 */
static void Encode(unsigned char *output, UINT4 *input, unsigned int len) {
  unsigned int i, j;
  
  for (i = 0, j = 0; j < len; i++, j += 4) {
    output[j] = (unsigned char)(input[i] & 0xff);
    output[j+1] = (unsigned char)((input[i] >> 8) & 0xff);
    output[j+2] = (unsigned char)((input[i] >> 16) & 0xff);
    output[j+3] = (unsigned char)((input[i] >> 24) & 0xff);
  }
}

static void Decode(UINT4 *output, const unsigned char *input, unsigned int len) {
  unsigned int i, j;
  
  for (i = 0, j = 0; j < len; i++, j += 4) {
    output[i] = ((UINT4)input[j]) | 
               (((UINT4)input[j+1]) << 8) | 
               (((UINT4)input[j+2]) << 16) | 
               (((UINT4)input[j+3]) << 24);
  }
}

/*
 * MD5核心变换函数
 * 处理一个512位的消息块
 */
static void MD5Transform(UINT4 state[4], const unsigned char block[64]) {
  UINT4 a = state[0], b = state[1], c = state[2], d = state[3];
  UINT4 x[16];
  int i;
  
  /* 将64字节块解码为16个32位字 */
  Decode(x, block, 64);
  
  /* 第1轮: 16次操作 */
  for (i = 0; i < 16; i++) {
    FF(a, b, c, d, x[X_index[i]], S[i], T[i]);
    /* 循环右移寄存器值 */
    UINT4 temp = d;
    d = c;
    c = b;
    b = a;
    a = temp;
  }
  
  /* 第2轮: 16次操作 */
  for (i = 16; i < 32; i++) {
    GG(a, b, c, d, x[X_index[i]], S[i], T[i]);
    UINT4 temp = d;
    d = c;
    c = b;
    b = a;
    a = temp;
  }
  
  /* 第3轮: 16次操作 */
  for (i = 32; i < 48; i++) {
    HH(a, b, c, d, x[X_index[i]], S[i], T[i]);
    UINT4 temp = d;
    d = c;
    c = b;
    b = a;
    a = temp;
  }
  
  /* 第4轮: 16次操作 */
  for (i = 48; i < 64; i++) {
    II(a, b, c, d, x[X_index[i]], S[i], T[i]);
    UINT4 temp = d;
    d = c;
    c = b;
    b = a;
    a = temp;
  }
  
  /* 更新状态值 */
  state[0] += a;
  state[1] += b;
  state[2] += c;
  state[3] += d;
  
  /* 清除敏感数据 */
  memset(x, 0, sizeof(x));
}

/*
 * MD5初始化
 * 初始化上下文结构
 */
void MD5Init(MD5_CTX *context) {
  context->count[0] = context->count[1] = 0;
  
  /* 加载魔术常量 (小端序) */
  context->state[0] = 0x67452301;
  context->state[1] = 0xEFCDAB89;
  context->state[2] = 0x98BADCFE;
  context->state[3] = 0x10325476;
}

/*
 * MD5更新
 * 处理输入数据，可以多次调用
 */
void MD5Update(MD5_CTX *context, const unsigned char *input, unsigned int inputLen) {
  unsigned int i, index, partLen;
  
  /* 计算已有字节数 */
  index = (unsigned int)((context->count[0] >> 3) & 0x3F);
  
  /* 更新位计数 */
  if ((context->count[0] += ((UINT4)inputLen << 3)) < ((UINT4)inputLen << 3)) {
    context->count[1]++;
  }
  context->count[1] += ((UINT4)inputLen >> 29);
  
  partLen = 64 - index;
  
  /* 如果缓冲区足够，直接复制 */
  if (inputLen >= partLen) {
    memcpy(&context->buffer[index], input, partLen);
    MD5Transform(context->state, context->buffer);
    
    /* 处理完整的64字节块 */
    for (i = partLen; i + 63 < inputLen; i += 64) {
      MD5Transform(context->state, &input[i]);
    }
    
    index = 0;
  } else {
    i = 0;
  }
  
  /* 复制剩余数据到缓冲区 */
  memcpy(&context->buffer[index], &input[i], inputLen - i);
}

/*
 * MD5结束
 * 添加填充，返回最终哈希值
 */
void MD5Final(unsigned char digest[16], MD5_CTX *context) {
  unsigned char bits[8];
  unsigned int index, padLen;
  
  /* 保存位计数 */
  Encode(bits, context->count, 8);
  
  /* 填充: 0x80 后跟 0x00 */
  index = (unsigned int)((context->count[0] >> 3) & 0x3F);
  padLen = (index < 56) ? (56 - index) : (120 - index);
  MD5Update(context, (unsigned char *)"\x80", 1);
  for (unsigned int i = 1; i < padLen; i++) {
    MD5Update(context, (unsigned char *)"\x00", 1);
  }
  
  /* 添加位计数（64位） */
  MD5Update(context, bits, 8);
  
  /* 从上下文提取哈希值 */
  Encode(digest, context->state, 16);
  
  /* 清除敏感数据 */
  memset(context, 0, sizeof(*context));
}

/*
 * 方便的MD5计算函数
 * 输入任意数据，输出16字节MD5哈希
 */
void MD5(const unsigned char *input, unsigned int len, unsigned char digest[16]) {
  MD5_CTX context;
  
  MD5Init(&context);
  MD5Update(&context, input, len);
  MD5Final(digest, &context);
}

/*
 * 测试函数和示例
 */
void print_md5(const unsigned char digest[16]) {
  for (int i = 0; i < 16; i++) {
    printf("%02x", digest[i]);
  }
  printf("\n");
}

int main() {
  /* 测试用例 */
  unsigned char *msg = (unsigned char *)"password";
  unsigned char digest[16];
  
  MD5(msg, strlen((char *)msg), digest);
  
  printf("输入: \"%s\"\n", msg);
  printf("预期: %s\n", "5f4dcc3b5aa765d61d8327deb882cf99");
  printf("计算: ");
  print_md5(digest);
    

  
  /* 增量计算示例 */
  printf("\n增量计算示例:\n");
  MD5_CTX ctx;
  MD5Init(&ctx);
  MD5Update(&ctx, (unsigned char *)"pass", 4);
  MD5Update(&ctx, (unsigned char *)"word", 4);
  MD5Final(digest, &ctx);
  
  printf("增量计算 \"pass\" + \"word\": ");
  print_md5(digest);
  
  return 0;
}

常见的算法魔改点

  • 初始化常量
  • 非线性函数
  • T 常量表
  • 常量转换