📄 rfc1321.txt
字号:
组织：中国互动出版网（http://www.china-pub.com/）
（http://www.china-pub.com/compters/emook/aboutemook.htm）
E-mail：ouyang@china-pub.com
译者：hlq（huangliuqi hlq@mail.ndsc.com.cn ）
译文发布时间：2001-3-29
版权：本中文翻译文档版权归China-Pub所有。可以用于非商业用途自由转载，但必须保留本文档的翻译及组织信息。
Network Working Group R. Rivest
Request for Comments: 1321 MIT Laboratory for Computer Science
and RSA Data Security, Inc.
April 1992
MD5消息摘要算法
RFC1321---The MD5 Message-Digest Algorithm
本备忘录的情况
This memo provides information for the Internet community. It does
not specify an Internet standard. Distribution of this memo is
unlimited.
致谢
We would like to thank Don Coppersmith, Burt Kaliski, Ralph Merkle,
David Chaum, and Noam Nisan for numerous helpful comments and
suggestions.
目录
1. Executive Summary 1
2. Terminology and Notation 2
3. MD5 Algorithm Description 3
4. Summary 6
5. Differences Between MD4 and MD5 6
References 7
APPENDIX A - Reference Implementation 7
Security Considerations 21
Author's Address 21
1. Executive Summary
该文档描述MD5消息摘要算法。该算法的输入为任意长度的消息，输出为128bit的“指纹”或称消息摘要。据推测通过计算不可能产生相同的消息摘要，也不可能通过事先给定的消息摘要产生任何消息。MD5算法为数字签名应用而设计，在这些应用中很大的文件在RSA中使用私人密钥进行加密之前必须进行压缩。
MD5算法设计成在能32位机器上快速运行。另外，MD5算法不需要任何大的替代表，该算法可以得到很紧凑的编码。
MD5算法是MD4消息摘要算法的扩展。MD5比MD4“慢”，但是在设计上更谨慎。设计MD5的是因为感到选择使用MD4是因为它运行得很快，而不是被现有的评论证明是正确的；因为MD4设计成特别快，就密码攻击的成功来说它已经“濒临边缘”。MD5在速度上作了让步，而赢得更大的安全性。它集结了很多评论家提出的建议，并进行了优化。MD5提出来供讨论并有可能采用成为一种标准。
在基于OSI的应用中， MD5的对象标识符为：
md5 OBJECT IDENTIFIER ::=
iso(1) member-body(2) US(840) rsadsi(113549) digestAlgorithm(2) 5}
在X.509的AlgorithmIdentifier类型中, MD5的参数类型应为NULL类型.
2. 术语和记号
本文中word是32-bit，byte是8-bit。bit序列为byte的序列，每一个８位组中最高有效位处于最前。同样byte序列为32-bit word序列,连续四个bytes理解为最低有效byte处于最前。
x_I代表x中的第I个元素。如果下标为一个表达式,则用花括号括起,比如x_{i+1}。同样，我们使用^表示上标(求幂),x^i代表x的i次方。
设符号“+”代表字（word）的相加(即模2^32加)； X <<< s代表32位值循环左移s位所得结果；not(X)代表X补码的按位取反,；X v Y 代表X和Y的按位或（OR）；X xor Y代表X和Y的按位异或（XOR）；XY代表X和Y的按位与（AND）。
3. MD5算法描述
我们假设开始有一个b位的消息作为输入,我们希望找到其消息摘要。这里b是任意一个非负整数；b可以为0,不要求是8的整数倍,它也可以任意大。我们假设消息的比特写为如下:
m_0 m_1 ... m_{b-1}
为计算出该消息的摘要执行下面五步。
3.1 第一步 附加填充位
该消息被“填充”（扩展）使其长度（比特数）模512 结果为448。也就是说，该消息被扩展以至比512的整数倍少64位。填充总是必需执行的,即使该消息的长度模512的结果已经是448。
填充按如下进行:给该消息填充一个比特“1”,然后填充比特“0”以使其比特数模512的结果为448。所有情况下,填充至少为1个比特，最多为512比特。
3.2 第二步 附加长度Length
在上一步所得结果后附加b的64位表示(b使所有填充之前消息的长度)。在b大于2^64的不可能情况中，仅用其低64位。(这些比特位附加时作为两个32位字，低序字在前，与前面的约定一致。)
此时结果消息(带有填充位和b)的比特位恰好为512的整数倍。等价地说，该消息的长度恰好为16个字(32-bit)的整数倍。设M[0 ... N-1]代表结果消息的所有字,N为16的整数倍。
3.3 第三步 初始化MD Buffer
计算消息摘要需要四个字(A,B,C,D)的缓冲区。这里A, B, C, D各自为一个32位寄存器。这些寄存器初始化为下面的十六进制值,低序字节在前:
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10
3.4 第四步 以16字节块为单位处理消息 Process Message in 16-Word Blocks
我们首先定义四个辅助函数，它们各自的输入为32位值，输出也为32位值。
F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))
对每一位，F作为条件判断:如果X则Y否则Z。函数F还可以使用+代替v定义，因为XY和not(X)Z不会在相同的位置出现1。注意如果X,Y,X的各比特位独立且不带偏见的，则F(X,Y,Z)的各比特位也将是独立和不带偏见的。
函数G, H, 和I具有与函数F类似功能，因为它们以“并行比特”形式从X,Y,Z的各个比特得到它们的结果 ,这样，如果X, Y, Z的对应比特位相互独立且不带偏见,那么G(X,Y,Z), H(X,Y,Z),和I(X,Y,Z)的各个比特将是独立的，不带偏见的。注意函数H是其输入的“xor”或“parity”函数。
本步骤使用由正弦函数（sine）构建的64个元素的表T[1 ... 64]。设T[i] 代表该表的第i个元素,该元素等于4294967296乘以abs(sin(i))的整数部分。该表的元素在附录中给出。
按如下步骤进行:
/* 处理每一个16-word块 */
For i = 0 to N/16-1 do
/* 把第i块拷贝到X中 */
For j = 0 to 15 do
Set X[j] to M[i*16+j].
end /* of loop on j */
/* 把A保存为AA, B保存为BB, C保存为CC, D保存为DD */
AA = A
BB = B
CC = C
DD = D
/* 第一遍*/
/* 设[abcd k s i]代表操作
a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
/*作如下16个操作 */
[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]
/* 第二遍 */
/*设[abcd k s i]代表操作
a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s) */
/* 作如下16个操作*/
[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]
/* 第三遍 */
/* 设[abcd k s t]代表操作
a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s) */
/*作如下16个操作 */
[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]
/*第四遍 */
/*设[abcd k s i]代表操作
a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
/*作如下16个操作*/
[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]
/* 然后再做下面的操作。 (即四个寄存器的值各增加执行本块之前的值 */
A = A + AA
B = B + BB
C = C + CC
D = D + DD
end /* 对i的循环 */
3.5 第五步 输出
消息摘要的输出为A, B, C, D。也就是说,低字节始于A,高字节终止于D。
这就完成了MD5算法的描述。C语言实现的参考见于附录。
4. 概要
MD5消息摘要算法易于实现,提供了任意长度消息的“指纹”或称消息摘要。 据推算要使两个消息产生相同的消息摘要需要做2^64次操作,给定消息摘要产生消息需要做2^128操作。MD5算法的缺陷已经被深入调查（但是没有发现什么）。但是,一个相对新的更安全的分析当然是需要的，这就是这种类型的新建议。 A
5. MD4和MD5之间的差异
下面是MD4和MD5之间的差异:
1. 增加了第四遍。
2. 每一步都有各自不同的常数
3. 第二遍的函数由(XY v XZ v YZ)变为(XZ v Y not(Z))以减小其对称。
4. 每一步累加了前一部的结果。这加速了“雪崩效应”。
5. 改变第二遍和第三遍中访问输入word的顺序,以使互相之间的相似性减小。
6. 每一遍的shift的字节数被大致的优化以产生更快的“雪崩效应”。每一遍shift的字节数都各不相同。
参考
[1] Rivest, R., "The MD4 Message Digest Algorithm", RFC 1320, MIT and
RSA Data Security, Inc., April 1992.
[2] Rivest, R., "The MD4 message digest algorithm", in A.J. Menezes
and S.A. Vanstone, editors, Advances in Cryptology - CRYPTO '90
Proceedings, pages 303-311, Springer-Verlag, 1991.
[3] CCITT Recommendation X.509 (1988), "The Directory -
Authentication Framework."
附录 A - 参考的实现
本附录包含取自RSAREF中的下列文件: A
Cryptographic Toolkit for Privacy-Enhanced Mail:
global.h -全局头文件
md5.h -- MD5的头文件
md5c.c - MD5的源程序
RSAREF更多的信息，请发Email至rsaref@rsa.com，本附录还包含了下面的文件：
mddriver.c -- MD2, MD4和MD5的测试Driver。该Driver缺省编译为MD5,但也可以编译为MD2或者MD4，只要把C编译器命令行中符号MD定义为2或者4就可以了。
该实现事可移植的，应该可以在不同的平台之上工作。但是，该实现在不同平台上的优化并不困难,我们把这一部分的工作留给读者作为练习。例如,在“小端字节序”平台上（即32位字中最低地址的字节为最低有效字节，并且没有对齐限制），那么MD5Transform 中的Decode调用将被一个转换所取代。
A.1 global.h
/* GLOBAL.H - RSAREF类型和常数
*/
/* 当且仅当编译器支持函数参数时PROTOTYPES设置为1。如果没有定义C编译器的标志位，以下将缺省地把PROTOTYPES设置为0 ，
*/
#ifndef PROTOTYPES
#define PROTOTYPES 0
#endif
/* POINTER 定义了通用的指针类型 */
typedef unsigned char *POINTER;
/* UINT2定义了一个包含两字节的字*/
typedef unsigned short int UINT2;
/* UINT4定义了一个包含4字节的字*/
typedef unsigned long int UINT4;
/* PROTO_LIST根据上面PROTOTYPES的定义而定义.如果使用PROTOTYPES,那么PROTO_LIST返回该list，否则返回一个空链。
*/
#if PROTOTYPES
#define PROTO_LIST(list) list
#else
#define PROTO_LIST(list) ()
#endif
A.2 md5.h
/* MD5.H -MD5C.C的头文件
*/
/* Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All
rights reserved.
License to copy and use this software is granted provided that it
is identified as the "RSA Data Security, Inc. MD5 Message-Digest
Algorithm" in all material mentioning or referencing this software
or this function.
License is also granted to make and use derivative works provided
that such works are identified as "derived from the RSA Data
Security, Inc. MD5 Message-Digest Algorithm" in all material
mentioning or referencing the derived work.
RSA Data Security, Inc. makes no representations concerning either
the merchantability of this software or the suitability of this
software for any particular purpose. It is provided "as is"
without express or implied warranty of any kind.
These notices must be retained in any copies of any part of this
documentation and/or software.
*/
/* MD5上下文 */
typedef struct {
UINT4 state[4]; /* state (ABCD) */
UINT4 count[2]; /*比特数,模2^64(最低有效字节在先 */
unsigned char buffer[64]; /* input buffer */
} MD5_CTX;
void MD5Init PROTO_LIST ((MD5_CTX *));
void MD5Update PROTO_LIST
((MD5_CTX *, unsigned char *, unsigned int));
void MD5Final PROTO_LIST ((unsigned char [16], MD5_CTX *));
A.3 md5c.c
/* MD5C.C - RSA Data Security, Inc., MD5消息摘要算法
*/
/* Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All
rights reserved.
License to copy and use this software is granted provided that it
is identified as the "RSA Data Security, Inc. MD5 Message-Digest
Algorithm" in all material mentioning or referencing this software
or this function.
License is also granted to make and use derivative works provided
that such works are identified as "derived from the RSA Data
Security, Inc. MD5 Message-Digest Algorithm" in all material
mentioning or referencing the derived work.
RSA Data Security, Inc. makes no representations concerning either
the merchantability of this software or the suitability of this
software for any particular purpose. It is provided "as is"
without express or implied warranty of any kind.
These notices must be retained in any copies of any part of this
documentation and/or software.
*/
#include "global.h"
#include "md5.h"
/* Constants for MD5Transform routine.
*/
#define S11 7
#define S12 12
#define S13 17
#define S14 22
#define S21 5
#define S22 9
#define S23 14
#define S24 20
#define S31 4
#define S32 11
#define S33 16
#define S34 23
#define S41 6
#define S42 10
#define S43 15
#define S44 21
static void MD5Transform PROTO_LIST ((UINT4 [4], unsigned char [64]));
static void Encode PROTO_LIST
((unsigned char *, UINT4 *, unsigned int));
static void Decode PROTO_LIST
((UINT4 *, unsigned char *, unsigned int));
static void MD5_memcpy PROTO_LIST ((POINTER, POINTER, unsigned int));
static void MD5_memset PROTO_LIST ((POINTER, int, unsigned int));
static unsigned char PADDING[64] = {
0x80, 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
};
/* F, G, H 和I是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)))
/* ROTATE_LEFT把x左移n位
*/
#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
/* FF, GG, HH,和II是第1，2，3，4遍的转换。左移与加分开以避免重新计算
*/
#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); \
}
/* MD5初始化。开始一次MD5操作，写一个新的上下文
*/
void MD5Init (context)
MD5_CTX *context; /* context */
{
context->count[0] = context->count[1] = 0;
/* 装载magic初始化常数
*/
context->state[0] = 0x67452301;
context->state[1] = 0xefcdab89;
context->state[2] = 0x98badcfe;
context->state[3] = 0x10325476;
}
/* MD5块更新操作。继续一次MD5消息摘要操作,处理另一个消息块，更新上下文 */
void MD5Update (context, input, inputLen)
MD5_CTX *context; /* context */
unsigned char *input; /* input block */
unsigned int inputLen; /* length of input block */
{
unsigned int i, index, partLen;
/* Compute number of bytes mod 64 */
index = (unsigned int)((context->count[0] >> 3) & 0x3F);
/* Update number of bits */
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) {
MD5_memcpy
((POINTER)&context->buffer[index], (POINTER)input, partLen);
MD5Transform (context->state, context->buffer);
for (i = partLen; i + 63 < inputLen; i += 64)
MD5Transform (context->state, &input[i]);
index = 0;
}
else
i = 0;
/* Buffer remaining input */
MD5_memcpy
((POINTER)&context->buffer[index], (POINTER)&input[i],
inputLen-i);
}
/* MD5结束。完成一个MD5消息摘要操作,写消息摘要并把上下文置0
*/
void MD5Final (digest, context)
unsigned char digest[16]; /* message digest */
MD5_CTX *context; /* context */
{
unsigned char bits[8];
unsigned int index, padLen;
/* 保存比特数 */
Encode (bits, context->count, 8);
/*填充至56 mod 64*/
index = (unsigned int)((context->count[0] >> 3) & 0x3f);
padLen = (index < 56) ? (56 - index) : (120 - index);
MD5Update (context, PADDING, padLen);
/* 附上（填充前的）长度*/
MD5Update (context, bits, 8);
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -