RFC-1321MD5算法

RFC-1321 MD5信息-摘要算法

Network Working Group                                        R. Rivest
Request for Comments: 1321           MIT Laboratory for Computer Science
                                            and RSA Data Security, Inc.
                                                           April 1992

备忘录说明

    这份备忘录仅仅为因特网社区提供信息。它不会被指定为因特网的一个标准。发布本备
    忘录是不受限制的。

鸣谢

  Don Coppersmith, Burt Kaliski, Ralph Merkle,David Chaum, 和Noam Nisan向本文
    提供极大的帮助，在此表示忠心的感谢。

目录

    1.内容提要                                                              1
    2.专业术语和符号                                                        2
    3.MD5算法描述                                                           3
    4.摘要                                                                  6
    5.MD4和MD5的区别                                                       6
    引用                                                                    7
    附录A – 参考实现                                                       7
    安全性                                                                  21
    作者地址                                                                21

1.内容提要

    这份文件描述了MD5信息-摘要算法。该算法接收一段任意长度的信息输入，然后输出
    该消息的128比特的“指纹”或者“消息摘要”。可以认为假定两个不同的文件产生相
    同的报文摘要或由给定的报文摘要产生原始信息在计算上是行不通的。MD5算法适合用
    在数据签名应用中，在此应用中，一个大的文件必须在类似RSA算法的公用密钥系统中
    用私人密钥加密前被“压缩”在一种安全模式下。

    MD5算法被设计成能在32位机器上快速运行。特别的是，MD5算法不需要任何巨大的置
    换表；算法能够被紧凑的实现。

    MD5算法是MD4信息-摘要算法的扩展。它比MD4运行慢，但是被设计得更加“保守”。
    设计MD5算法的原因是感觉到MD4算法的应用速度远远快于理论上的证明速度；因为
    MD4被运算速度非常快，导致它处在遭受成功秘密攻击的边缘。MD5后退了一步，它舍
    弃了一些速度以求更好的安全性。它集中了不同的评论家提出的建议，并采取了一些附
    加的优化措施。它被放在公共的地方以求公众的评论意见，它可能当作一个标准被采纳。

    作为基于OSI的基础应用，MD5的对象标识符是：

    md5 OBJECT IDENTIFIER ::=
        iso(1) member-body(2) US(840) rsadsi(113549) digestAlgorithm(2) 5}

    在X.509类型AlgorithmIdentifier [3]中，MD5算法参数应该包括NULL类型。

2.专业术语和符号

    在这份文件中，一个“字”是32位，一个“字节”是8位。位串可以被自然的看作是
    字节串，其中连续的8位被看作是一个字节，高位(最重要的位)在前。同样的，字节串
    可以被看作是32位的字串，其中连续的4个字节被看作是一个字，低位字节(最不重要
    的)在前。

    定义x_i为x减去i，如果减数是一个表达式，则用大括号括住，如x_{i+1}。同样的，
    我们用^代表幂，因此，x^i代表x的i次幂。

    定义符号“+”为“字”的加法。定义x<<<s为32位的x循环左移s位。定义not(s)
    为对x按位求补，xvy为x和y按位或，xXORy为x和y按位异或，xy为x和y按位与。

3.MD5算法描述

    我们假设有一段b位的信息输入，并且我们想要找到他的信息摘要。这里b是一个任意
    的无符号整数；b可能为0；它不一定是8的倍数，也可能是任意大的长度。我们假想
    信息串的比特流如下：

    m_0 m_1...m_(b-1)

    接下来的5个步骤描述了如何计算该信息的摘要。

3.1 附加填充位

    消息需要进行填充，使得它的长度(位)对512求余为448，即消息的长度加上64比特
    后刚好是512的整数倍。填充是必需进行的，即使消息的长度对512求余的结果已经是
    448。

    填充规则如下：先填充一比特的“1”，然后一直填充“0”，直到消息的长度对512求余
    的结果是448。总共，至少要填充1比特，最多填充512比特。

3.2 附加长度

    一个64位的无符号整数b(消息被填充前的长度)被附加在先前被填充的消息后面。如
    果b的实际长度超过64位，只附加b的低64位(这些比特会被放在两个32位的字中，
    填充的时候按照先前的约定，低位优先)。

    此时，目标消息(被填充了附加位和长度b)的长度刚好是512比特的整数倍。即，消息
    的长度刚好是16个字(32位)的整数倍。定义M[0 ... N-1]为目标消息的字串，N是16
    的整数倍。

3.3 初始化MD缓存

    一个4个字的缓存(A,B,C,D)被用于计算消息的摘要。这里每一个A,B,C,D都是一个32
    位的寄存器。这些寄存器使用如下的16进制的值进行初始化(低位优先)：

    A : 01 23 45 67
    B : 89 ab cd ef
    C : fe dc ba 98
    D : 76 54 32 10

3.4 16个字一组处理消息

    我们首先定义4个辅助函数，每个函数的输入是3个32位的字，输出是1个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
    和Z是各自独立的和公正的，则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是一个对输入进行按位异
    或或等于的函数(译者注：原文Note that the function H is the bit-wise "xor" or
    "parity" function of its inputs)。

    这一步需要用到一个64位的常数组T[1...64]，它有sine函数构造。定义T[i]位常数
    组中的第i个元素，它的值等于经过4294967296次abs(sin(i))后的值的整数部分（其
    中i是弧度）。数组元素在附录中给出。

         过程如下：

         /*16个字节一组处理*/
    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/*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 i]为操作
      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算法已经过非常细致的检查。最后的结论是还需
    要相关的更好的算法和更进一步的安全分析。

5.MD4和MD5的区别

    下面是MD4和MD5的区别：

        1.增加了第四步循环。
        2.每一步增加了一个唯一的常数。
        3.第二轮循环的g函数从 (XY v XZ v YZ) 变成了 (XZ v Y not(Z)) ，以减
           少g函数的平衡性。
       4.每一步的结果都会被加进上一步的结果中，这样就加速了“雪崩效应”。
        5.在第二和第三步循环中，存取输入字的顺序被改变了，使得各个样式彼此之间
          的相似度更小
        6.每个循环中位移的量是经过近似优化的，为了更快的产生“雪崩效应”。每步循
          环中的位移是截然不同的

引用

    [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头文件
    md5.c    -- MD5源代码

    要知道更多RSAREF的信息，请发邮件给<rsaref@rsa.com>

    附录还包含以下文件：

    mddiver.c – MD2,MD4,MD5测试驱动。

    驱动默认编译MD5，但是如果在C编译器命令行下定义MD位2或者4，则会相应编译MD2和
    MD4

    这份实现是紧凑的，并且可以工作在多种平台上面。不过，在特定的平台上对实现
    进行优化也不是件困难的事，这作为一个练习留给读者。例如，在“little-endian”
    平台上，低32位的比特是没有意义的，并且没有成直线的限制。译码函数MD5Transform
    能够被其他调用替代。

A.1 global.h

/* GLOBAL.H - RSAREF types and constants*/

/* PROTOTYPES should be set to one if and only if the compiler
supports function argument prototyping.

The following makes PROTOTYPES default to 0 if it has not
already

#ifndef PROTOTYPES

#define PROTOTYPES 0

#endif

/* POINTER defines a generic pointer type */

typedef unsigned char *POINTER;

/* UINT2 defines a two byte word */

typedef unsigned short int UINT2;

/* UINT4 defines a four byte word */

typedef unsigned long int UINT4;

/* PROTO_LIST is defined depending on how PROTOTYPES is
defined above.

If using PROTOTYPES, then PROTO_LIST returns the list,
otherwise it returns an empty list.

#if PROTOTYPES

#define PROTO_LIST(list) list

#else

#define PROTO_LIST(list) ()

#endif

A.2 md5.h

/* MD5.H - header file for MD5C.C*/

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 thissoftware 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 context. */

typedef struct {

UINT4 state[4]; /* state (ABCD) */

UINT4 count[2]; /* number of bits, modulo 2^64 (lsb first) */

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 md5.c

/* MD5C.C - RSA Data Security, Inc., MD5 message-digest
algorithm*/

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 and I are basic MD5 functions.*/

#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 rotates x left n bits.*/

#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))

/* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.

Rotation is separate from addition to prevent recomputation.

#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 initialization. Begins an MD5 operation, writing a new context.

void MD5Init (context)

MD5_CTX *context; /* context */

{

context->count[0] = context->count[1] = 0;

/* Load magic initialization constants.*/

context->state[0] = 0x67452301;

context->state[1] = 0xefcdab89;

context->state[2] = 0x98badcfe;

context->state[3] = 0x10325476;

}

/* MD5 block update operation. Continues an MD5 message-digest

operation, processing another message block, and updating thecontext.

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;

/* Transform as many times as possible.*/

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 finalization. Ends an MD5 message-digest operation, writing the the message digest and zeroizing the context.

void MD5Final (digest, context)

unsigned char digest[16]; /* message digest */

MD5_CTX *context; /* context */

{

unsigned char bits[8];

unsigned int index, padLen;

/* Save number of bits */

Encode (bits, context->count, 8);

/* Pad out to 56 mod 64.*/

index = (unsigned int)((context->count[0] >> 3) & 0x3f);

padLen = (index < 56) ? (56 - index) : (120 - index);

MD5Update (context, PADDING, padLen);

/* Append length (before padding) */

MD5Update (context, bits, 8);

/* Store state in digest */

Encode (digest, context->state, 16);

/* Zeroize sensitive information.*/

MD5_memset ((POINTER)context, 0, sizeof (*context));

}

/* MD5 basic transformation. Transforms state based on block.

static void MD5Transform (state, block)

UINT4 state[4];

unsigned char block[64];

{

UINT4 a = state[0], b = state[1], c = state[2], d = state[3], x[16];

Decode (x, block, 64);

/* Round 1 */

FF (a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */

FF (d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */

FF (c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */

FF (b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */

FF (a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */

FF (d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */

FF (c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */

FF (b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */

FF (a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */

FF (d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */

FF (c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */

FF (b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */

FF (a, b, c, d, x[12], S11, 0x6b901122); /* 13 */

FF (d, a, b, c, x[13], S12, 0xfd987193); /* 14 */

FF (c, d, a, b, x[14], S13, 0xa679438e); /* 15 */

FF (b, c, d, a, x[15], S14, 0x49b40821); /* 16 */

/* Round 2 */

GG (a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */

GG (d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */

GG (c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */

GG (b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */

GG (a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */

GG (d, a, b, c, x[10], S22, 0x2441453); /* 22 */

GG (c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */

GG (b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */

GG (a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */

GG (d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */

GG (c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */

GG (b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */

GG (a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */

GG (d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */

GG (c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */

GG (b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */

/* Round 3 */

HH (a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */

HH (d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */

HH (c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */

HH (b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */

HH (a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */

HH (d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */

HH (c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */

HH (b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */

HH (a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */

HH (d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */

HH (c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */

HH (b, c, d, a, x[ 6], S34, 0x4881d05); /* 44 */

HH (a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */

HH (d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */

HH (c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */

HH (b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */

/* Round 4 */

II (a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */

II (d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */

II (c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */

II (b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */

II (a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */

II (d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */

II (c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */

II (b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */

II (a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */

II (d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */

II (c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */

II (b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */

II (a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */

II (d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */

II (c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */

II (b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */

state[0] += a;

state[1] += b;

state[2] += c;

state[3] += d;

/* Zeroize sensitive information.*/

MD5_memset ((POINTER)x, 0, sizeof (x));

}

/* Encodes input (UINT4) into output (unsigned char). Assumes len is a multiple of 4.

static void Encode (output, input, len)

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

}

/* Decodes input (unsigned char) into output (UINT4). Assumes len is a multiple of 4.

static void Decode (output, input, len)

UINT4 *output;

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

}

/* Note: Replace "for loop" with standard memcpy if possible.*/

static void MD5_memcpy (output, input, len)

POINTER output;

POINTER input;

unsigned int len;

{

unsigned int i;

for (i = 0; i < len; i++)

output[i] = input[i];

}

/* Note: Replace "for loop" with standard memset if possible.

static void MD5_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;

}

A.4 mddriver.c

/* MDDRIVER.C - test driver for MD2, MD4 and MD5*/

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.

/* The following makes MD default to MD5 if it has not already been defined with C compiler flags.

#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

/* Length of test block, number of test blocks.*/

#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

/* Main driver.

Arguments (may be any combination):

-sstring - digests string

-t - runs time trial

-x - runs test script

filename - digests file

(none) - digests standard input

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

}

/* Digests a string and prints the result.*/

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

}

/* Measures the time to digest TEST_BLOCK_COUNT TEST_BLOCK_LEN-byte

blocks.

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

/* Initialize block */

for (i = 0; i < TEST_BLOCK_LEN; i++)

block[i] = (unsigned char)(i & 0xff);

/* Start timer */

time (&startTime);

/* Digest blocks */

MDInit (&context);

for (i = 0; i < TEST_BLOCK_COUNT; i++)

MDUpdate (&context, block, TEST_BLOCK_LEN);

MDFinal (digest, &context);

/* Stop timer */

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

}

/* Digests a reference suite of strings and prints the results.*/

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

}

/* Digests a file and prints the result.*/

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

}

/* Digests the standard input and prints the result.*/

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

}

/* Prints a message digest in hexadecimal.*/

static void MDPrint (digest)

unsigned char digest[16];

{

unsigned int i;

for (i = 0; i < 16; i++)

printf ("%02x", digest[i]);

}

A.5.MD5测试的理论结果

MD5驱动的测试结果(驱动操作符号“-x”)如下：

MD5 test suite:
MD5 ("") = d41d8cd98f00b204e9800998ecf8427e
MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661
MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72
MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0
MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") =
d174ab98d277d9f5a5611c2c9f419d9f

MD5 ("123456789012345678901234567890123456789012345678901234567890123456
78901234567890") = 57edf4a22be3c955ac49da2e2107b67a

安全性

这份备忘录中提及的安全性的水平足以实现基于MD5和公钥加密系统的非常高水平的混
合数字签名方案。

作者地址

Ronald L. Rivest
Massachusetts Institute of Technology
Laboratory for Computer Science
NE43-324
545 Technology Square
Cambridge, MA 02139-1986
Phone: (617) 253-5880
EMail: rivest@theory.lcs.mit.edu

发表于 2009-03-07 13:44 ghbxx 阅读(1497) 评论(0) 编辑收藏引用

公告

常用链接

留言簿(6)

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜

算法与程序--游戏与玩乐一个新程序员在计算技术上的学习经验
C++博客 \| 首页 \| 发新随笔 \| 发新文章 \| 联系 \| 聚合 \| 管理	随笔：142 文章：0 评论：37 引用：0