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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 23 - (show annotations) (download)
Sat Oct 8 06:11:57 2016 UTC (7 years, 5 months ago) by dashley
File MIME type: text/plain
File size: 36400 byte(s)
Initial commit.
1
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