摘要算法

MD2

介绍

MD2消息摘要算法是Ronald Rivest在1989年发现的加密哈希方法。这个算法是对八位计算机的优化。MD2在RFC1319中有详细的介绍。即使MD2在2014后已不再被认为是安全的,但它仍然保留在用MD2和RSA生成的证书的公钥的基础。『MD』在MD2中代表”Message Digest(消息摘要)”。

以下内容翻译自rfc1319

摘要

这个文档描述MD2消息摘要算法。该算法将一个任意长度的消息作为输入并且运行输出一个128bit的『指纹』或者『消息摘要』输入。据推测它不可能得出两条消息有一样的消息摘要,或者能计算出人格消息有一个预先给定的目标消息摘要。MD2算法旨在数字签名应用,在大文件必须在一个公钥加密系统像RSA产生的私钥签名之前用安全的行为进行『压缩』。
使用MD2的许可由非经营的 Internet Privacy Enhanced Mail{1-3}提供的。

术语和注意事项

本文中,1 “byte” 是代表8bit。
x_i 代表 “s sub i”。如果标注的是一个表达式,我们像x_{i+1}用大括号包裹它。同样的,我们使用^表示x^i为x的i次方。
X xor Y 表示X与Y异或。

MD2算法描述

开始我们假设有b-byte的消息作为输入,并且我们细化找到它的消息摘要。其中b是一个任意无符号正数;b可以是零,可以任意大小。我们想象这几byte消息如下:

m_0 m_1 ... m_{b-1}

接下来的五个步骤教你如何生成一个消息的消息摘要。

第一步 附上扩展的bytes

消息是被扩展的以至于他的长度(bytes)是模16等于零的,它是很多个16bytes长的。这个扩展是必须的,即便它的长度模16等于零。
扩展的工作如下:”i” 值 “i” byte被扩展的信息的长度能模16等于0。所以至少扩展1 byte和至多16 bytes。
这个时候,在扩展之后的信息的是准确的多个16 bytes长度。M[0 … N-1]为扩展后的信息,其中N是多个16。

第二步 扩展校验码

一个16-byte的信息的校验码被拼接在前一个步骤结果上。
这一步使用一个256-byte的 从pi 构建的『随机』排列。S[i]第i个表中的元素。这个表在附录中给出的。
如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 /* 清除校验码 */
For i = 0 to 15 do:
Set C[i] to 0.
end
Set L to 0.
/* 执行每个16子的块 */
For i = 0 to N/16-1 do
/* i个校验码块 */
For j = 0 to 15 do
Set c to M[i * 16 + j].
Set C[j] to S[c xor L].
Set L to C[j].
end
end

16-byte 的校验码C[0 … 15]就被拼接在了消息上,设M[0 和校验码], 其中N’ = N + 16。

第三步初始化MD缓冲区

48-byte 缓冲区X,是用来结算消息摘要的。这个缓冲区初始化为0.

第四步 创建 16-Byte 块的消息

这一步使用相同的256-byte序列S,像第二步一样做。
如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 执行每个16子的块*/
For i = 0 to N'/16-1 do
/* 复制每个块j到X */
For j = 0 to 15 do
Set X[16 + j] to M[i * 16 + j].
Set X[32 + j] to (X[16 + j] xor X[j]).
end
Set t to 0
/* 18次循环 */
For j = 0 to 17 do
/* 循环j */
For k = 0 to 47 do
Set t and X[k] to (X[k] xor S[t]).
end
end
end

第五步输出

消息摘要输出X[0 … 15]。开始于X[0],结束于X[15]。

代码

以下代码是来源参考文档,有所修改。

md2算法有如下三个文件global.h,md2.h,md2c.c。

global.h

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

/* PROTOTYPES */
#ifndef PROTOTYPES
#define PROTOTYPES 0
#endif

/* POINTER 定义为一个一般的指针类型 */
typedef unsigned char *POINTER;

/* UINT2 定义为2byte的变量 */
typedef unsigned short int UINT2;

/* UINT4 定义为4byte的变量 */
typedef unsigned long int UINT4;

/* PROTO_LIST 定义是基于PROTOTYPES怎样定义的,如果使用PROTOTYPES,那么PROTO_LIST返回这个列表,否则返回一个空的列表。 */

#if PROTOTYPES
#define PROTO_LIST(list) list
#else
#define PROTO_LIST(List) ()
#endif

md2.h

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

typedef struct {
unsigned char state[16]; /* 状态 */
unsigned char checksum[16]; /* 校验码 */
unsigned int count; /* 多少byte,模16 */
unsigned char buffer[16]; /* 输入缓冲 */
} MD2_CTX;

void MD2Init PROTO_LIST(( MD2_ CTX * ));'

void MD2Update PROTO_LIST(( MD2_CTX *, unsigned char *, unsigned int ));

void MD2Final PROTO_LIST ((unsigned char [16], MD2_CTX *));

md2c.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

#include "global.h"
#include "md2.h"

#include "global.h"
#include "md2.h"

static void MD2Transform PROTO_LIST
((unsigned char [16], unsigned char [16], unsigned char [16]));
static void MD2_memcpy PROTO_LIST ((POINTER, POINTER, unsigned int));
static void MD2_memset PROTO_LIST ((POINTER, int, unsigned int));

/* 从Pi中构造排列,它给出『随机』非线性置换操作
*/
static unsigned char PI_SUBST[256] = {
41, 46, 67, 201, 162, 216, 124, 1, 61, 54, 84, 161, 236, 240, 6,19, 98, 167, 5, 243, 192, 199, 115, 140, 152, 147, 43, 217, 188,
76, 130, 202, 30, 155, 87, 60, 253, 212, 224, 22, 103, 66, 111, 24,
138, 23, 229, 18, 190, 78, 196, 214, 218, 158, 222, 73, 160, 251,
245, 142, 187, 47, 238, 122, 169, 104, 121, 145, 21, 178, 7, 63,
148, 194, 16, 137, 11, 34, 95, 33, 128, 127, 93, 154, 90, 144, 50,
39, 53, 62, 204, 231, 191, 247, 151, 3, 255, 25, 48, 179, 72, 165,
181, 209, 215, 94, 146, 42, 172, 86, 170, 198, 79, 184, 56, 210,
150, 164, 125, 182, 118, 252, 107, 226, 156, 116, 4, 241, 69, 157,
112, 89, 100, 113, 135, 32, 134, 91, 207, 101, 230, 45, 168, 2, 27,
96, 37, 173, 174, 176, 185, 246, 28, 70, 97, 105, 52, 64, 126, 15,
85, 71, 163, 35, 221, 81, 175, 58, 195, 92, 249, 206, 186, 197,
234, 38, 44, 83, 13, 110, 133, 40, 132, 9, 211, 223, 205, 244, 65,
129, 77, 82, 106, 220, 55, 200, 108, 193, 171, 250, 36, 225, 123,
8, 12, 189, 177, 74, 120, 136, 149, 139, 227, 99, 232, 109, 233,
203, 213, 254, 59, 0, 29, 57, 242, 239, 183, 14, 102, 88, 208, 228,
166, 119, 114, 248, 235, 117, 75, 10, 49, 68, 80, 180, 143, 237,
31, 26, 219, 153, 141, 51, 159, 17, 131, 20
};

static unsigned char *PADDING[] = {
(unsigned char *)"",
(unsigned char *)"\001",
(unsigned char *)"\002\002",
(unsigned char *)"\003\003\003",
(unsigned char *)"\004\004\004\004",
(unsigned char *)"\005\005\005\005\005",
(unsigned char *)"\006\006\006\006\006\006",
(unsigned char *)"\007\007\007\007\007\007\007",
(unsigned char *)"\010\010\010\010\010\010\010\010",
(unsigned char *)"\011\011\011\011\011\011\011\011\011",
(unsigned char *)"\012\012\012\012\012\012\012\012\012\012",
(unsigned char *)"\013\013\013\013\013\013\013\013\013\013\013",
(unsigned char *)"\014\014\014\014\014\014\014\014\014\014\014\014",
(unsigned char *)
"\015\015\015\015\015\015\015\015\015\015\015\015\015",
(unsigned char *)
"\016\016\016\016\016\016\016\016\016\016\016\016\016\016",
(unsigned char *)
"\017\017\017\017\017\017\017\017\017\017\017\017\017\017\017",
(unsigned char *)
"\020\020\020\020\020\020\020\020\020\020\020\020\020\020\020\020"
};

/* MD2 初始化 。
*/
void MD2Init (context)
MD2_CTX *context; /* 上下文 */
{
context->count = 0;
MD2_memset ((POINTER)context->state, 0, sizeof (context->state)); MD2_memset ((POINTER)context->checksum, 0, sizeof (context->checksum));
}

/* MD2 块更新操作。继续MD2消息摘要生成操作,运行其他的消息块并且更新上下文。
*/
void MD2Update (context, input, inputLen)
MD2_CTX *context; /* 上下文 */
unsigned char *input; /* i输入块 */
unsigned int inputLen; /* 输入块的长度 */
{
unsigned int i, index, partLen;

/* 更新模16后所得的个数 */
index = context->count;
context->count = (index + inputLen) & 0xf;

partLen = 16 - index;

/* 多次转换
*/
if (inputLen >= partLen) {
MD2_memcpy
((POINTER)&context->buffer[index], (POINTER)input, partLen);
MD2Transform (context->state, context->checksum, context->buffer);

for (i = partLen; i + 15 < inputLen; i += 16)
MD2Transform (context->state, context->checksum, &input[i]);

index = 0;
}
else
i = 0;

/* 拷贝到输出缓冲区 */
MD2_memcpy
((POINTER)&context->buffer[index], (POINTER)&input[i],
inputLen-i);
}

/* MD2 终止。 结束MD2消息摘要操作,写入消息摘要并且初始化上下文。
*/
void MD2Final (digest, context)
unsigned char digest[16]; /* 消息摘要 */
MD2_CTX *context; /* 上下文 */
{
unsigned int index, padLen;

/* 填满到能被16整除
*/
index = context->count;
padLen = 16 - index;
MD2Update (context, PADDING[padLen], padLen);

/* 扩展校验码 */
MD2Update (context, context->checksum, 16);

/* 在摘要中储存状态信息 */
MD2_memcpy ((POINTER)digest, (POINTER)context->state, 16);

/* 初始化指针
*/
MD2_memset ((POINTER)context, 0, sizeof (*context));
}

/* MD2 基本的转换。基于块转换状态和跟新校验码。
*/
static void MD2Transform (state, checksum, block)
unsigned char state[16];
unsigned char checksum[16];
unsigned char block[16];
{
unsigned int i, j, t;
unsigned char x[48];

/* 从状态,块,状态^块构建加密块
*/
MD2_memcpy ((POINTER)x, (POINTER)state, 16);
MD2_memcpy ((POINTER)x+16, (POINTER)block, 16);
for (i = 0; i < 16; i++)
x[i+32] = state[i] ^ block[i];

/* 加密块 (18 次循环).
*/
t = 0;
for (i = 0; i < 18; i++) {
for (j = 0; j < 48; j++)
t = x[j] ^= PI_SUBST[t];
t = (t + i) & 0xff;
}
/* 保存新的状态 */
MD2_memcpy ((POINTER)state, (POINTER)x, 16);

/* 更新校验码。
*/
t = checksum[15];
for (i = 0; i < 16; i++)
t = checksum[i] ^= PI_SUBST[block[i] ^ t];

/* 初始化指针
*/
MD2_memset ((POINTER)x, 0, sizeof (x));
}

/* 注意: 尽可能使用memset代替for循环。
*/
static void MD2_memcpy (output, input, len)
POINTER output;
POINTER input;
unsigned int len;
{
unsigned int i;

for (i = 0; i < len; i++)
output[i] = input[i];
}

/* 注意: 尽可能使用memset代替for循环。
*/
static void MD2_memset (output, value, len)
POINTER output;
int value;
unsigned int len;
{
unsigned int i;

for (i = 0; i < len; i++)
((char *)output)[i] = (char)value;
}

mddriver.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

#ifndef MD
#define MD MD5
#endif

#include <stdio.h>
#include <time.h>
#include <string.h>
#include "global.h"
#if MD == 2
#include "md2.h"
#endif
#if MD == 4
#include "md4.h"
#endif
#if MD == 5
#include "md5.h"
#endif

/* 一个测试块的长度,测试块的数量。
*/
#define TEST_BLOCK_LEN 1000
#define TEST_BLOCK_COUNT 1000

static void MDString PROTO_LIST ((char *));
static void MDTimeTrial PROTO_LIST ((void));
static void MDTestSuite PROTO_LIST ((void));
static void MDFile PROTO_LIST ((char *));
static void MDFilter PROTO_LIST ((void));
static void MDPrint PROTO_LIST ((unsigned char [16]));

#if MD == 2
#define MD_CTX MD2_CTX
#define MDInit MD2Init
#define MDUpdate MD2Update
#define MDFinal MD2Final
#endif


#if MD == 4
#define MD_CTX MD4_CTX
#define MDInit MD4Init
#define MDUpdate MD4Update
#define MDFinal MD4Final
#endif
#if MD == 5
#define MD_CTX MD5_CTX
#define MDInit MD5Init
#define MDUpdate MD5Update
#define MDFinal MD5Final
#endif

/* 主程序。

参数(可能有许多的组合):
-sstring - 字符串的摘要
-t - 执行事件测试
-x - 执行测试较稳
filename - 文件测试
(none) - 摘要标准输入
*/
int main (argc, argv)
int argc;
char *argv[];
{
int i;

if (argc > 1)
for (i = 1; i < argc; i++)
if (argv[i][0] == '-' && argv[i][1] == 's')
MDString (argv[i] + 2);
else if (strcmp (argv[i], "-t") == 0)
MDTimeTrial ();
else if (strcmp (argv[i], "-x") == 0)
MDTestSuite ();
else
MDFile (argv[i]);
else
MDFilter ();

return (0);
}

/* 字符串的消息摘要
*/
static void MDString (string)
char *string;

{
MD_CTX context;
unsigned char digest[16];
unsigned int len = strlen (string);

MDInit (&context);
MDUpdate (&context, string, len);
MDFinal (digest, &context);

printf ("MD%d (\"%s\") = ", MD, string);
MDPrint (digest);
printf ("\n");
}

/* 测量摘要TEST_BLOCK_COUNT TEST_BLOCK_LEN-byte
块的事件.
*/
static void MDTimeTrial ()
{
MD_CTX context;
time_t endTime, startTime;
unsigned char block[TEST_BLOCK_LEN], digest[16];
unsigned int i;

printf
("MD%d time trial. Digesting %d %d-byte blocks ...", MD,
TEST_BLOCK_LEN, TEST_BLOCK_COUNT);

/*初始化块 */
for (i = 0; i < TEST_BLOCK_LEN; i++)
block[i] = (unsigned char)(i & 0xff);

/* 开始时间 */
time (&startTime);

/* 摘要块 */
MDInit (&context);
for (i = 0; i < TEST_BLOCK_COUNT; i++)
MDUpdate (&context, block, TEST_BLOCK_LEN);
MDFinal (digest, &context);

/* 结束时间 */
time (&endTime);

printf (" done\n");
printf ("Digest = ");
MDPrint (digest);
printf ("\nTime = %ld seconds\n", (long)(endTime-startTime));


printf
("Speed = %ld bytes/second\n",
(long)TEST_BLOCK_LEN * (long)TEST_BLOCK_COUNT/(endTime-startTime));
}
/* 字符串的消息摘要(测试)
*/
static void MDTestSuite ()
{
printf ("MD%d test suite:\n", MD);

MDString ("");
MDString ("a");
MDString ("abc");
MDString ("message digest");
MDString ("abcdefghijklmnopqrstuvwxyz");
MDString
("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789");
MDString
("1234567890123456789012345678901234567890\
1234567890123456789012345678901234567890");
}

/* 文件的消息摘要。
*/
static void MDFile (filename)
char *filename;
{
FILE *file;
MD_CTX context;
int len;
unsigned char buffer[1024], digest[16];

if ((file = fopen (filename, "rb")) == NULL)
printf ("%s can't be opened\n", filename);

else {
MDInit (&context);
while (len = fread (buffer, 1, 1024, file))
MDUpdate (&context, buffer, len);
MDFinal (digest, &context);

fclose (file);

printf ("MD%d (%s) = ", MD, filename);
MDPrint (digest);
printf ("\n");
}
}

/* 消息摘要输入和结果打印。
*/
static void MDFilter ()
{
MD_CTX context;
int len;
unsigned char buffer[16], digest[16];

MDInit (&context);
while (len = fread (buffer, 1, 16, stdin))
MDUpdate (&context, buffer, len);
MDFinal (digest, &context);

MDPrint (digest);
printf ("\n");
}

/* 十六进制打印消息摘要
*/
static void MDPrint (digest)
unsigned char digest[16];
{
unsigned int i;

for (i = 0; i < 16; i++)
printf ("%02x", digest[i]);
}

测试样例

如下测试是在-x参数下的测试结果

MD2 测试样例:

MD2 (“”) = 8350e5a3e24c153df2275c9f80692773
MD2 (“a”) = 32ec01ec4a6dac72c0ab96fb34c0b5d1
MD2 (“abc”) = da853b0d3f88d99b30283a69e6ded6bb
MD2 (“message digest”) = ab4f496bfb2a530b219ff33031fe06b0
MD2 (“abcdefghijklmnopqrstuvwxyz”) = 4e8ddff3650292ab5a4108c3aa47940b
MD2 (“ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789”) =
da33def2a42df13975352846c30338cd
MD2 (“123456789012345678901234567890123456789012345678901234567890123456
78901234567890”) = d5976f79d83d3a0dc9806c3c66f3efd8