/[dtapublic]/sf_code/esrgweba/htdocs/docs/rfc1321.txt
ViewVC logotype

Annotation of /sf_code/esrgweba/htdocs/docs/rfc1321.txt

Parent Directory Parent Directory | Revision Log Revision Log


Revision 23 - (hide annotations) (download)
Sat Oct 8 06:11:57 2016 UTC (7 years, 9 months ago) by dashley
File MIME type: text/plain
File size: 36400 byte(s)
Initial commit.
1 dashley 23
2    
3    
4    
5    
6    
7     Network Working Group R. Rivest
8     Request for Comments: 1321 MIT Laboratory for Computer Science
9     and RSA Data Security, Inc.
10     April 1992
11    
12    
13     The MD5 Message-Digest Algorithm
14    
15     Status of this Memo
16    
17     This memo provides information for the Internet community. It does
18     not specify an Internet standard. Distribution of this memo is
19     unlimited.
20    
21     Acknowlegements
22    
23     We would like to thank Don Coppersmith, Burt Kaliski, Ralph Merkle,
24     David Chaum, and Noam Nisan for numerous helpful comments and
25     suggestions.
26    
27     Table of Contents
28    
29     1. Executive Summary 1
30     2. Terminology and Notation 2
31     3. MD5 Algorithm Description 3
32     4. Summary 6
33     5. Differences Between MD4 and MD5 6
34     References 7
35     APPENDIX A - Reference Implementation 7
36     Security Considerations 21
37     Author's Address 21
38    
39     1. Executive Summary
40    
41     This document describes the MD5 message-digest algorithm. The
42     algorithm takes as input a message of arbitrary length and produces
43     as output a 128-bit "fingerprint" or "message digest" of the input.
44     It is conjectured that it is computationally infeasible to produce
45     two messages having the same message digest, or to produce any
46     message having a given prespecified target message digest. The MD5
47     algorithm is intended for digital signature applications, where a
48     large file must be "compressed" in a secure manner before being
49     encrypted with a private (secret) key under a public-key cryptosystem
50     such as RSA.
51    
52    
53    
54    
55    
56    
57    
58     Rivest [Page 1]
59    
60     RFC 1321 MD5 Message-Digest Algorithm April 1992
61    
62    
63     The MD5 algorithm is designed to be quite fast on 32-bit machines. In
64     addition, the MD5 algorithm does not require any large substitution
65     tables; the algorithm can be coded quite compactly.
66    
67     The MD5 algorithm is an extension of the MD4 message-digest algorithm
68     1,2]. MD5 is slightly slower than MD4, but is more "conservative" in
69     design. MD5 was designed because it was felt that MD4 was perhaps
70     being adopted for use more quickly than justified by the existing
71     critical review; because MD4 was designed to be exceptionally fast,
72     it is "at the edge" in terms of risking successful cryptanalytic
73     attack. MD5 backs off a bit, giving up a little in speed for a much
74     greater likelihood of ultimate security. It incorporates some
75     suggestions made by various reviewers, and contains additional
76     optimizations. The MD5 algorithm is being placed in the public domain
77     for review and possible adoption as a standard.
78    
79     For OSI-based applications, MD5's object identifier is
80    
81     md5 OBJECT IDENTIFIER ::=
82     iso(1) member-body(2) US(840) rsadsi(113549) digestAlgorithm(2) 5}
83    
84     In the X.509 type AlgorithmIdentifier [3], the parameters for MD5
85     should have type NULL.
86    
87     2. Terminology and Notation
88    
89     In this document a "word" is a 32-bit quantity and a "byte" is an
90     eight-bit quantity. A sequence of bits can be interpreted in a
91     natural manner as a sequence of bytes, where each consecutive group
92     of eight bits is interpreted as a byte with the high-order (most
93     significant) bit of each byte listed first. Similarly, a sequence of
94     bytes can be interpreted as a sequence of 32-bit words, where each
95     consecutive group of four bytes is interpreted as a word with the
96     low-order (least significant) byte given first.
97    
98     Let x_i denote "x sub i". If the subscript is an expression, we
99     surround it in braces, as in x_{i+1}. Similarly, we use ^ for
100     superscripts (exponentiation), so that x^i denotes x to the i-th
101     power.
102    
103     Let the symbol "+" denote addition of words (i.e., modulo-2^32
104     addition). Let X <<< s denote the 32-bit value obtained by circularly
105     shifting (rotating) X left by s bit positions. Let not(X) denote the
106     bit-wise complement of X, and let X v Y denote the bit-wise OR of X
107     and Y. Let X xor Y denote the bit-wise XOR of X and Y, and let XY
108     denote the bit-wise AND of X and Y.
109    
110    
111    
112    
113    
114     Rivest [Page 2]
115    
116     RFC 1321 MD5 Message-Digest Algorithm April 1992
117    
118    
119     3. MD5 Algorithm Description
120    
121     We begin by supposing that we have a b-bit message as input, and that
122     we wish to find its message digest. Here b is an arbitrary
123     nonnegative integer; b may be zero, it need not be a multiple of
124     eight, and it may be arbitrarily large. We imagine the bits of the
125     message written down as follows:
126    
127     m_0 m_1 ... m_{b-1}
128    
129     The following five steps are performed to compute the message digest
130     of the message.
131    
132     3.1 Step 1. Append Padding Bits
133    
134     The message is "padded" (extended) so that its length (in bits) is
135     congruent to 448, modulo 512. That is, the message is extended so
136     that it is just 64 bits shy of being a multiple of 512 bits long.
137     Padding is always performed, even if the length of the message is
138     already congruent to 448, modulo 512.
139    
140     Padding is performed as follows: a single "1" bit is appended to the
141     message, and then "0" bits are appended so that the length in bits of
142     the padded message becomes congruent to 448, modulo 512. In all, at
143     least one bit and at most 512 bits are appended.
144    
145     3.2 Step 2. Append Length
146    
147     A 64-bit representation of b (the length of the message before the
148     padding bits were added) is appended to the result of the previous
149     step. In the unlikely event that b is greater than 2^64, then only
150     the low-order 64 bits of b are used. (These bits are appended as two
151     32-bit words and appended low-order word first in accordance with the
152     previous conventions.)
153    
154     At this point the resulting message (after padding with bits and with
155     b) has a length that is an exact multiple of 512 bits. Equivalently,
156     this message has a length that is an exact multiple of 16 (32-bit)
157     words. Let M[0 ... N-1] denote the words of the resulting message,
158     where N is a multiple of 16.
159    
160     3.3 Step 3. Initialize MD Buffer
161    
162     A four-word buffer (A,B,C,D) is used to compute the message digest.
163     Here each of A, B, C, D is a 32-bit register. These registers are
164     initialized to the following values in hexadecimal, low-order bytes
165     first):
166    
167    
168    
169    
170     Rivest [Page 3]
171    
172     RFC 1321 MD5 Message-Digest Algorithm April 1992
173    
174    
175     word A: 01 23 45 67
176     word B: 89 ab cd ef
177     word C: fe dc ba 98
178     word D: 76 54 32 10
179    
180     3.4 Step 4. Process Message in 16-Word Blocks
181    
182     We first define four auxiliary functions that each take as input
183     three 32-bit words and produce as output one 32-bit word.
184    
185     F(X,Y,Z) = XY v not(X) Z
186     G(X,Y,Z) = XZ v Y not(Z)
187     H(X,Y,Z) = X xor Y xor Z
188     I(X,Y,Z) = Y xor (X v not(Z))
189    
190     In each bit position F acts as a conditional: if X then Y else Z.
191     The function F could have been defined using + instead of v since XY
192     and not(X)Z will never have 1's in the same bit position.) It is
193     interesting to note that if the bits of X, Y, and Z are independent
194     and unbiased, the each bit of F(X,Y,Z) will be independent and
195     unbiased.
196    
197     The functions G, H, and I are similar to the function F, in that they
198     act in "bitwise parallel" to produce their output from the bits of X,
199     Y, and Z, in such a manner that if the corresponding bits of X, Y,
200     and Z are independent and unbiased, then each bit of G(X,Y,Z),
201     H(X,Y,Z), and I(X,Y,Z) will be independent and unbiased. Note that
202     the function H is the bit-wise "xor" or "parity" function of its
203     inputs.
204    
205     This step uses a 64-element table T[1 ... 64] constructed from the
206     sine function. Let T[i] denote the i-th element of the table, which
207     is equal to the integer part of 4294967296 times abs(sin(i)), where i
208     is in radians. The elements of the table are given in the appendix.
209    
210     Do the following:
211    
212     /* Process each 16-word block. */
213     For i = 0 to N/16-1 do
214    
215     /* Copy block i into X. */
216     For j = 0 to 15 do
217     Set X[j] to M[i*16+j].
218     end /* of loop on j */
219    
220     /* Save A as AA, B as BB, C as CC, and D as DD. */
221     AA = A
222     BB = B
223    
224    
225    
226     Rivest [Page 4]
227    
228     RFC 1321 MD5 Message-Digest Algorithm April 1992
229    
230    
231     CC = C
232     DD = D
233    
234     /* Round 1. */
235     /* Let [abcd k s i] denote the operation
236     a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
237     /* Do the following 16 operations. */
238     [ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4]
239     [ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8]
240     [ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12]
241     [ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]
242    
243     /* Round 2. */
244     /* Let [abcd k s i] denote the operation
245     a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
246     /* Do the following 16 operations. */
247     [ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20]
248     [ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24]
249     [ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28]
250     [ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32]
251    
252     /* Round 3. */
253     /* Let [abcd k s t] denote the operation
254     a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
255     /* Do the following 16 operations. */
256     [ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36]
257     [ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40]
258     [ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44]
259     [ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48]
260    
261     /* Round 4. */
262     /* Let [abcd k s t] denote the operation
263     a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
264     /* Do the following 16 operations. */
265     [ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52]
266     [ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56]
267     [ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60]
268     [ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64]
269    
270     /* Then perform the following additions. (That is increment each
271     of the four registers by the value it had before this block
272     was started.) */
273     A = A + AA
274     B = B + BB
275     C = C + CC
276     D = D + DD
277    
278     end /* of loop on i */
279    
280    
281    
282     Rivest [Page 5]
283    
284     RFC 1321 MD5 Message-Digest Algorithm April 1992
285    
286    
287     3.5 Step 5. Output
288    
289     The message digest produced as output is A, B, C, D. That is, we
290     begin with the low-order byte of A, and end with the high-order byte
291     of D.
292    
293     This completes the description of MD5. A reference implementation in
294     C is given in the appendix.
295    
296     4. Summary
297    
298     The MD5 message-digest algorithm is simple to implement, and provides
299     a "fingerprint" or message digest of a message of arbitrary length.
300     It is conjectured that the difficulty of coming up with two messages
301     having the same message digest is on the order of 2^64 operations,
302     and that the difficulty of coming up with any message having a given
303     message digest is on the order of 2^128 operations. The MD5 algorithm
304     has been carefully scrutinized for weaknesses. It is, however, a
305     relatively new algorithm and further security analysis is of course
306     justified, as is the case with any new proposal of this sort.
307    
308     5. Differences Between MD4 and MD5
309    
310     The following are the differences between MD4 and MD5:
311    
312     1. A fourth round has been added.
313    
314     2. Each step now has a unique additive constant.
315    
316     3. The function g in round 2 was changed from (XY v XZ v YZ) to
317     (XZ v Y not(Z)) to make g less symmetric.
318    
319     4. Each step now adds in the result of the previous step. This
320     promotes a faster "avalanche effect".
321    
322     5. The order in which input words are accessed in rounds 2 and
323     3 is changed, to make these patterns less like each other.
324    
325     6. The shift amounts in each round have been approximately
326     optimized, to yield a faster "avalanche effect." The shifts in
327     different rounds are distinct.
328    
329    
330    
331    
332    
333    
334    
335    
336    
337    
338     Rivest [Page 6]
339    
340     RFC 1321 MD5 Message-Digest Algorithm April 1992
341    
342    
343     References
344    
345     [1] Rivest, R., "The MD4 Message Digest Algorithm", RFC 1320, MIT and
346     RSA Data Security, Inc., April 1992.
347    
348     [2] Rivest, R., "The MD4 message digest algorithm", in A.J. Menezes
349     and S.A. Vanstone, editors, Advances in Cryptology - CRYPTO '90
350     Proceedings, pages 303-311, Springer-Verlag, 1991.
351    
352     [3] CCITT Recommendation X.509 (1988), "The Directory -
353     Authentication Framework."
354    
355     APPENDIX A - Reference Implementation
356    
357     This appendix contains the following files taken from RSAREF: A
358     Cryptographic Toolkit for Privacy-Enhanced Mail:
359    
360     global.h -- global header file
361    
362     md5.h -- header file for MD5
363    
364     md5c.c -- source code for MD5
365    
366     For more information on RSAREF, send email to <rsaref@rsa.com>.
367    
368     The appendix also includes the following file:
369    
370     mddriver.c -- test driver for MD2, MD4 and MD5
371    
372     The driver compiles for MD5 by default but can compile for MD2 or MD4
373     if the symbol MD is defined on the C compiler command line as 2 or 4.
374    
375     The implementation is portable and should work on many different
376     plaforms. However, it is not difficult to optimize the implementation
377     on particular platforms, an exercise left to the reader. For example,
378     on "little-endian" platforms where the lowest-addressed byte in a 32-
379     bit word is the least significant and there are no alignment
380     restrictions, the call to Decode in MD5Transform can be replaced with
381     a typecast.
382    
383     A.1 global.h
384    
385     /* GLOBAL.H - RSAREF types and constants
386     */
387    
388     /* PROTOTYPES should be set to one if and only if the compiler supports
389     function argument prototyping.
390     The following makes PROTOTYPES default to 0 if it has not already
391    
392    
393    
394     Rivest [Page 7]
395    
396     RFC 1321 MD5 Message-Digest Algorithm April 1992
397    
398    
399     been defined with C compiler flags.
400     */
401     #ifndef PROTOTYPES
402     #define PROTOTYPES 0
403     #endif
404    
405     /* POINTER defines a generic pointer type */
406     typedef unsigned char *POINTER;
407    
408     /* UINT2 defines a two byte word */
409     typedef unsigned short int UINT2;
410    
411     /* UINT4 defines a four byte word */
412     typedef unsigned long int UINT4;
413    
414     /* PROTO_LIST is defined depending on how PROTOTYPES is defined above.
415     If using PROTOTYPES, then PROTO_LIST returns the list, otherwise it
416     returns an empty list.
417     */
418     #if PROTOTYPES
419     #define PROTO_LIST(list) list
420     #else
421     #define PROTO_LIST(list) ()
422     #endif
423    
424     A.2 md5.h
425    
426     /* MD5.H - header file for MD5C.C
427     */
428    
429     /* Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All
430     rights reserved.
431    
432     License to copy and use this software is granted provided that it
433     is identified as the "RSA Data Security, Inc. MD5 Message-Digest
434     Algorithm" in all material mentioning or referencing this software
435     or this function.
436    
437     License is also granted to make and use derivative works provided
438     that such works are identified as "derived from the RSA Data
439     Security, Inc. MD5 Message-Digest Algorithm" in all material
440     mentioning or referencing the derived work.
441    
442     RSA Data Security, Inc. makes no representations concerning either
443     the merchantability of this software or the suitability of this
444     software for any particular purpose. It is provided "as is"
445     without express or implied warranty of any kind.
446    
447    
448    
449    
450     Rivest [Page 8]
451    
452     RFC 1321 MD5 Message-Digest Algorithm April 1992
453    
454    
455     These notices must be retained in any copies of any part of this
456     documentation and/or software.
457     */
458    
459     /* MD5 context. */
460     typedef struct {
461     UINT4 state[4]; /* state (ABCD) */
462     UINT4 count[2]; /* number of bits, modulo 2^64 (lsb first) */
463     unsigned char buffer[64]; /* input buffer */
464     } MD5_CTX;
465    
466     void MD5Init PROTO_LIST ((MD5_CTX *));
467     void MD5Update PROTO_LIST
468     ((MD5_CTX *, unsigned char *, unsigned int));
469     void MD5Final PROTO_LIST ((unsigned char [16], MD5_CTX *));
470    
471     A.3 md5c.c
472    
473     /* MD5C.C - RSA Data Security, Inc., MD5 message-digest algorithm
474     */
475    
476     /* Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All
477     rights reserved.
478    
479     License to copy and use this software is granted provided that it
480     is identified as the "RSA Data Security, Inc. MD5 Message-Digest
481     Algorithm" in all material mentioning or referencing this software
482     or this function.
483    
484     License is also granted to make and use derivative works provided
485     that such works are identified as "derived from the RSA Data
486     Security, Inc. MD5 Message-Digest Algorithm" in all material
487     mentioning or referencing the derived work.
488    
489     RSA Data Security, Inc. makes no representations concerning either
490     the merchantability of this software or the suitability of this
491     software for any particular purpose. It is provided "as is"
492     without express or implied warranty of any kind.
493    
494     These notices must be retained in any copies of any part of this
495     documentation and/or software.
496     */
497    
498     #include "global.h"
499     #include "md5.h"
500    
501     /* Constants for MD5Transform routine.
502     */
503    
504    
505    
506     Rivest [Page 9]
507    
508     RFC 1321 MD5 Message-Digest Algorithm April 1992
509    
510    
511     #define S11 7
512     #define S12 12
513     #define S13 17
514     #define S14 22
515     #define S21 5
516     #define S22 9
517     #define S23 14
518     #define S24 20
519     #define S31 4
520     #define S32 11
521     #define S33 16
522     #define S34 23
523     #define S41 6
524     #define S42 10
525     #define S43 15
526     #define S44 21
527    
528     static void MD5Transform PROTO_LIST ((UINT4 [4], unsigned char [64]));
529     static void Encode PROTO_LIST
530     ((unsigned char *, UINT4 *, unsigned int));
531     static void Decode PROTO_LIST
532     ((UINT4 *, unsigned char *, unsigned int));
533     static void MD5_memcpy PROTO_LIST ((POINTER, POINTER, unsigned int));
534     static void MD5_memset PROTO_LIST ((POINTER, int, unsigned int));
535    
536     static unsigned char PADDING[64] = {
537     0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
538     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
539     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
540     };
541    
542     /* F, G, H and I are basic MD5 functions.
543     */
544     #define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
545     #define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
546     #define H(x, y, z) ((x) ^ (y) ^ (z))
547     #define I(x, y, z) ((y) ^ ((x) | (~z)))
548    
549     /* ROTATE_LEFT rotates x left n bits.
550     */
551     #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
552    
553     /* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
554     Rotation is separate from addition to prevent recomputation.
555     */
556     #define FF(a, b, c, d, x, s, ac) { \
557     (a) += F ((b), (c), (d)) + (x) + (UINT4)(ac); \
558     (a) = ROTATE_LEFT ((a), (s)); \
559    
560    
561    
562     Rivest [Page 10]
563    
564     RFC 1321 MD5 Message-Digest Algorithm April 1992
565    
566    
567     (a) += (b); \
568     }
569     #define GG(a, b, c, d, x, s, ac) { \
570     (a) += G ((b), (c), (d)) + (x) + (UINT4)(ac); \
571     (a) = ROTATE_LEFT ((a), (s)); \
572     (a) += (b); \
573     }
574     #define HH(a, b, c, d, x, s, ac) { \
575     (a) += H ((b), (c), (d)) + (x) + (UINT4)(ac); \
576     (a) = ROTATE_LEFT ((a), (s)); \
577     (a) += (b); \
578     }
579     #define II(a, b, c, d, x, s, ac) { \
580     (a) += I ((b), (c), (d)) + (x) + (UINT4)(ac); \
581     (a) = ROTATE_LEFT ((a), (s)); \
582     (a) += (b); \
583     }
584    
585     /* MD5 initialization. Begins an MD5 operation, writing a new context.
586     */
587     void MD5Init (context)
588     MD5_CTX *context; /* context */
589     {
590     context->count[0] = context->count[1] = 0;
591     /* Load magic initialization constants.
592     */
593     context->state[0] = 0x67452301;
594     context->state[1] = 0xefcdab89;
595     context->state[2] = 0x98badcfe;
596     context->state[3] = 0x10325476;
597     }
598    
599     /* MD5 block update operation. Continues an MD5 message-digest
600     operation, processing another message block, and updating the
601     context.
602     */
603     void MD5Update (context, input, inputLen)
604     MD5_CTX *context; /* context */
605     unsigned char *input; /* input block */
606     unsigned int inputLen; /* length of input block */
607     {
608     unsigned int i, index, partLen;
609    
610     /* Compute number of bytes mod 64 */
611     index = (unsigned int)((context->count[0] >> 3) & 0x3F);
612    
613     /* Update number of bits */
614     if ((context->count[0] += ((UINT4)inputLen << 3))
615    
616    
617    
618     Rivest [Page 11]
619    
620     RFC 1321 MD5 Message-Digest Algorithm April 1992
621    
622    
623     < ((UINT4)inputLen << 3))
624     context->count[1]++;
625     context->count[1] += ((UINT4)inputLen >> 29);
626    
627     partLen = 64 - index;
628    
629     /* Transform as many times as possible.
630     */
631     if (inputLen >= partLen) {
632     MD5_memcpy
633     ((POINTER)&context->buffer[index], (POINTER)input, partLen);
634     MD5Transform (context->state, context->buffer);
635    
636     for (i = partLen; i + 63 < inputLen; i += 64)
637     MD5Transform (context->state, &input[i]);
638    
639     index = 0;
640     }
641     else
642     i = 0;
643    
644     /* Buffer remaining input */
645     MD5_memcpy
646     ((POINTER)&context->buffer[index], (POINTER)&input[i],
647     inputLen-i);
648     }
649    
650     /* MD5 finalization. Ends an MD5 message-digest operation, writing the
651     the message digest and zeroizing the context.
652     */
653     void MD5Final (digest, context)
654     unsigned char digest[16]; /* message digest */
655     MD5_CTX *context; /* context */
656     {
657     unsigned char bits[8];
658     unsigned int index, padLen;
659    
660     /* Save number of bits */
661     Encode (bits, context->count, 8);
662    
663     /* Pad out to 56 mod 64.
664     */
665     index = (unsigned int)((context->count[0] >> 3) & 0x3f);
666     padLen = (index < 56) ? (56 - index) : (120 - index);
667     MD5Update (context, PADDING, padLen);
668    
669     /* Append length (before padding) */
670     MD5Update (context, bits, 8);
671    
672    
673    
674     Rivest [Page 12]
675    
676     RFC 1321 MD5 Message-Digest Algorithm April 1992
677    
678    
679     /* Store state in digest */
680     Encode (digest, context->state, 16);
681    
682     /* Zeroize sensitive information.
683     */
684     MD5_memset ((POINTER)context, 0, sizeof (*context));
685     }
686    
687     /* MD5 basic transformation. Transforms state based on block.
688     */
689     static void MD5Transform (state, block)
690     UINT4 state[4];
691     unsigned char block[64];
692     {
693     UINT4 a = state[0], b = state[1], c = state[2], d = state[3], x[16];
694    
695     Decode (x, block, 64);
696    
697     /* Round 1 */
698     FF (a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */
699     FF (d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */
700     FF (c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */
701     FF (b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */
702     FF (a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */
703     FF (d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */
704     FF (c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */
705     FF (b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */
706     FF (a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */
707     FF (d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */
708     FF (c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */
709     FF (b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */
710     FF (a, b, c, d, x[12], S11, 0x6b901122); /* 13 */
711     FF (d, a, b, c, x[13], S12, 0xfd987193); /* 14 */
712     FF (c, d, a, b, x[14], S13, 0xa679438e); /* 15 */
713     FF (b, c, d, a, x[15], S14, 0x49b40821); /* 16 */
714    
715     /* Round 2 */
716     GG (a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */
717     GG (d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */
718     GG (c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */
719     GG (b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */
720     GG (a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */
721     GG (d, a, b, c, x[10], S22, 0x2441453); /* 22 */
722     GG (c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */
723     GG (b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */
724     GG (a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */
725     GG (d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */
726     GG (c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */
727    
728    
729    
730     Rivest [Page 13]
731    
732     RFC 1321 MD5 Message-Digest Algorithm April 1992
733    
734    
735     GG (b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */
736     GG (a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */
737     GG (d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */
738     GG (c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */
739     GG (b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */
740    
741     /* Round 3 */
742     HH (a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */
743     HH (d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */
744     HH (c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */
745     HH (b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */
746     HH (a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */
747     HH (d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */
748     HH (c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */
749     HH (b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */
750     HH (a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */
751     HH (d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */
752     HH (c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */
753     HH (b, c, d, a, x[ 6], S34, 0x4881d05); /* 44 */
754     HH (a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */
755     HH (d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */
756     HH (c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */
757     HH (b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */
758    
759     /* Round 4 */
760     II (a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */
761     II (d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */
762     II (c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */
763     II (b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */
764     II (a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */
765     II (d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */
766     II (c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */
767     II (b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */
768     II (a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */
769     II (d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */
770     II (c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */
771     II (b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */
772     II (a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */
773     II (d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */
774     II (c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */
775     II (b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */
776    
777     state[0] += a;
778     state[1] += b;
779     state[2] += c;
780     state[3] += d;
781    
782     /* Zeroize sensitive information.
783    
784    
785    
786     Rivest [Page 14]
787    
788     RFC 1321 MD5 Message-Digest Algorithm April 1992
789    
790    
791     */
792     MD5_memset ((POINTER)x, 0, sizeof (x));
793     }
794    
795     /* Encodes input (UINT4) into output (unsigned char). Assumes len is
796     a multiple of 4.
797     */
798     static void Encode (output, input, len)
799     unsigned char *output;
800     UINT4 *input;
801     unsigned int len;
802     {
803     unsigned int i, j;
804    
805     for (i = 0, j = 0; j < len; i++, j += 4) {
806     output[j] = (unsigned char)(input[i] & 0xff);
807     output[j+1] = (unsigned char)((input[i] >> 8) & 0xff);
808     output[j+2] = (unsigned char)((input[i] >> 16) & 0xff);
809     output[j+3] = (unsigned char)((input[i] >> 24) & 0xff);
810     }
811     }
812    
813     /* Decodes input (unsigned char) into output (UINT4). Assumes len is
814     a multiple of 4.
815     */
816     static void Decode (output, input, len)
817     UINT4 *output;
818     unsigned char *input;
819     unsigned int len;
820     {
821     unsigned int i, j;
822    
823     for (i = 0, j = 0; j < len; i++, j += 4)
824     output[i] = ((UINT4)input[j]) | (((UINT4)input[j+1]) << 8) |
825     (((UINT4)input[j+2]) << 16) | (((UINT4)input[j+3]) << 24);
826     }
827    
828     /* Note: Replace "for loop" with standard memcpy if possible.
829     */
830    
831     static void MD5_memcpy (output, input, len)
832     POINTER output;
833     POINTER input;
834     unsigned int len;
835     {
836     unsigned int i;
837    
838     for (i = 0; i < len; i++)
839    
840    
841    
842     Rivest [Page 15]
843    
844     RFC 1321 MD5 Message-Digest Algorithm April 1992
845    
846    
847     output[i] = input[i];
848     }
849    
850     /* Note: Replace "for loop" with standard memset if possible.
851     */
852     static void MD5_memset (output, value, len)
853     POINTER output;
854     int value;
855     unsigned int len;
856     {
857     unsigned int i;
858    
859     for (i = 0; i < len; i++)
860     ((char *)output)[i] = (char)value;
861     }
862    
863     A.4 mddriver.c
864    
865     /* MDDRIVER.C - test driver for MD2, MD4 and MD5
866     */
867    
868     /* Copyright (C) 1990-2, RSA Data Security, Inc. Created 1990. All
869     rights reserved.
870    
871     RSA Data Security, Inc. makes no representations concerning either
872     the merchantability of this software or the suitability of this
873     software for any particular purpose. It is provided "as is"
874     without express or implied warranty of any kind.
875    
876     These notices must be retained in any copies of any part of this
877     documentation and/or software.
878     */
879    
880     /* The following makes MD default to MD5 if it has not already been
881     defined with C compiler flags.
882     */
883     #ifndef MD
884     #define MD MD5
885     #endif
886    
887     #include <stdio.h>
888     #include <time.h>
889     #include <string.h>
890     #include "global.h"
891     #if MD == 2
892     #include "md2.h"
893     #endif
894     #if MD == 4
895    
896    
897    
898     Rivest [Page 16]
899    
900     RFC 1321 MD5 Message-Digest Algorithm April 1992
901    
902    
903     #include "md4.h"
904     #endif
905     #if MD == 5
906     #include "md5.h"
907     #endif
908    
909     /* Length of test block, number of test blocks.
910     */
911     #define TEST_BLOCK_LEN 1000
912     #define TEST_BLOCK_COUNT 1000
913    
914     static void MDString PROTO_LIST ((char *));
915     static void MDTimeTrial PROTO_LIST ((void));
916     static void MDTestSuite PROTO_LIST ((void));
917     static void MDFile PROTO_LIST ((char *));
918     static void MDFilter PROTO_LIST ((void));
919     static void MDPrint PROTO_LIST ((unsigned char [16]));
920    
921     #if MD == 2
922     #define MD_CTX MD2_CTX
923     #define MDInit MD2Init
924     #define MDUpdate MD2Update
925     #define MDFinal MD2Final
926     #endif
927     #if MD == 4
928     #define MD_CTX MD4_CTX
929     #define MDInit MD4Init
930     #define MDUpdate MD4Update
931     #define MDFinal MD4Final
932     #endif
933     #if MD == 5
934     #define MD_CTX MD5_CTX
935     #define MDInit MD5Init
936     #define MDUpdate MD5Update
937     #define MDFinal MD5Final
938     #endif
939    
940     /* Main driver.
941    
942     Arguments (may be any combination):
943     -sstring - digests string
944     -t - runs time trial
945     -x - runs test script
946     filename - digests file
947     (none) - digests standard input
948     */
949     int main (argc, argv)
950     int argc;
951    
952    
953    
954     Rivest [Page 17]
955    
956     RFC 1321 MD5 Message-Digest Algorithm April 1992
957    
958    
959     char *argv[];
960     {
961     int i;
962    
963     if (argc > 1)
964     for (i = 1; i < argc; i++)
965     if (argv[i][0] == '-' && argv[i][1] == 's')
966     MDString (argv[i] + 2);
967     else if (strcmp (argv[i], "-t") == 0)
968     MDTimeTrial ();
969     else if (strcmp (argv[i], "-x") == 0)
970     MDTestSuite ();
971     else
972     MDFile (argv[i]);
973     else
974     MDFilter ();
975    
976     return (0);
977     }
978    
979     /* Digests a string and prints the result.
980     */
981     static void MDString (string)
982     char *string;
983     {
984     MD_CTX context;
985     unsigned char digest[16];
986     unsigned int len = strlen (string);
987    
988     MDInit (&context);
989     MDUpdate (&context, string, len);
990     MDFinal (digest, &context);
991    
992     printf ("MD%d (\"%s\") = ", MD, string);
993     MDPrint (digest);
994     printf ("\n");
995     }
996    
997     /* Measures the time to digest TEST_BLOCK_COUNT TEST_BLOCK_LEN-byte
998     blocks.
999     */
1000     static void MDTimeTrial ()
1001     {
1002     MD_CTX context;
1003     time_t endTime, startTime;
1004     unsigned char block[TEST_BLOCK_LEN], digest[16];
1005     unsigned int i;
1006    
1007    
1008    
1009    
1010     Rivest [Page 18]
1011    
1012     RFC 1321 MD5 Message-Digest Algorithm April 1992
1013    
1014    
1015     printf
1016     ("MD%d time trial. Digesting %d %d-byte blocks ...", MD,
1017     TEST_BLOCK_LEN, TEST_BLOCK_COUNT);
1018    
1019     /* Initialize block */
1020     for (i = 0; i < TEST_BLOCK_LEN; i++)
1021     block[i] = (unsigned char)(i & 0xff);
1022    
1023     /* Start timer */
1024     time (&startTime);
1025    
1026     /* Digest blocks */
1027     MDInit (&context);
1028     for (i = 0; i < TEST_BLOCK_COUNT; i++)
1029     MDUpdate (&context, block, TEST_BLOCK_LEN);
1030     MDFinal (digest, &context);
1031    
1032     /* Stop timer */
1033     time (&endTime);
1034    
1035     printf (" done\n");
1036     printf ("Digest = ");
1037     MDPrint (digest);
1038     printf ("\nTime = %ld seconds\n", (long)(endTime-startTime));
1039     printf
1040     ("Speed = %ld bytes/second\n",
1041     (long)TEST_BLOCK_LEN * (long)TEST_BLOCK_COUNT/(endTime-startTime));
1042     }
1043    
1044     /* Digests a reference suite of strings and prints the results.
1045     */
1046     static void MDTestSuite ()
1047     {
1048     printf ("MD%d test suite:\n", MD);
1049    
1050     MDString ("");
1051     MDString ("a");
1052     MDString ("abc");
1053     MDString ("message digest");
1054     MDString ("abcdefghijklmnopqrstuvwxyz");
1055     MDString
1056     ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789");
1057     MDString
1058     ("1234567890123456789012345678901234567890\
1059     1234567890123456789012345678901234567890");
1060     }
1061    
1062     /* Digests a file and prints the result.
1063    
1064    
1065    
1066     Rivest [Page 19]
1067    
1068     RFC 1321 MD5 Message-Digest Algorithm April 1992
1069    
1070    
1071     */
1072     static void MDFile (filename)
1073     char *filename;
1074     {
1075     FILE *file;
1076     MD_CTX context;
1077     int len;
1078     unsigned char buffer[1024], digest[16];
1079    
1080     if ((file = fopen (filename, "rb")) == NULL)
1081     printf ("%s can't be opened\n", filename);
1082    
1083     else {
1084     MDInit (&context);
1085     while (len = fread (buffer, 1, 1024, file))
1086     MDUpdate (&context, buffer, len);
1087     MDFinal (digest, &context);
1088    
1089     fclose (file);
1090    
1091     printf ("MD%d (%s) = ", MD, filename);
1092     MDPrint (digest);
1093     printf ("\n");
1094     }
1095     }
1096    
1097     /* Digests the standard input and prints the result.
1098     */
1099     static void MDFilter ()
1100     {
1101     MD_CTX context;
1102     int len;
1103     unsigned char buffer[16], digest[16];
1104    
1105     MDInit (&context);
1106     while (len = fread (buffer, 1, 16, stdin))
1107     MDUpdate (&context, buffer, len);
1108     MDFinal (digest, &context);
1109    
1110     MDPrint (digest);
1111     printf ("\n");
1112     }
1113    
1114     /* Prints a message digest in hexadecimal.
1115     */
1116     static void MDPrint (digest)
1117     unsigned char digest[16];
1118     {
1119    
1120    
1121    
1122     Rivest [Page 20]
1123    
1124     RFC 1321 MD5 Message-Digest Algorithm April 1992
1125    
1126    
1127     unsigned int i;
1128    
1129     for (i = 0; i < 16; i++)
1130     printf ("%02x", digest[i]);
1131     }
1132    
1133     A.5 Test suite
1134    
1135     The MD5 test suite (driver option "-x") should print the following
1136     results:
1137    
1138     MD5 test suite:
1139     MD5 ("") = d41d8cd98f00b204e9800998ecf8427e
1140     MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661
1141     MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72
1142     MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0
1143     MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
1144     MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") =
1145     d174ab98d277d9f5a5611c2c9f419d9f
1146     MD5 ("123456789012345678901234567890123456789012345678901234567890123456
1147     78901234567890") = 57edf4a22be3c955ac49da2e2107b67a
1148    
1149     Security Considerations
1150    
1151     The level of security discussed in this memo is considered to be
1152     sufficient for implementing very high security hybrid digital-
1153     signature schemes based on MD5 and a public-key cryptosystem.
1154    
1155     Author's Address
1156    
1157     Ronald L. Rivest
1158     Massachusetts Institute of Technology
1159     Laboratory for Computer Science
1160     NE43-324
1161     545 Technology Square
1162     Cambridge, MA 02139-1986
1163    
1164     Phone: (617) 253-5880
1165     EMail: rivest@theory.lcs.mit.edu
1166    
1167    
1168    
1169    
1170    
1171    
1172    
1173    
1174    
1175    
1176    
1177    
1178     Rivest [Page 21]
1179    

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25