modified: SpatialOmicsCoord.py
[GalaxyCodeBases.git] / c_cpp / etc / md5_sha / README.md5
blobb31ff6bbdcfa55360dc5405cdf58ac31f186e48e
1 $Id: README.md5,v 13.1 2006/08/14 03:16:33 chongo Exp $
3 This is an implementation of the RSA Data Security, Inc.
4                 MD5 Message-Digest Algorithm
6 The digests produced from strings (-s string), files or stdin are
7 identical to the RSA's original md5 program.  The command line and
8 output interface are upward compatible as well.  Users of the
9 original shs program may replace it with this version has their
10 existing use and digests will be preserved.
12 See md5drvr.c for version information.  See the man page md5.1
13 for other details.
15 Landon Curt Noll (chongo was here) /\../\
16 http://www.isthe.com/chongo/index.html
18 Share and enjoy! :-)
20 =-=
23 Network Working Group                                          R. Rivest
24 INTERNET-DRAFT                       MIT Laboratory for Computer Science
25                                                                 S. Dusse
26                                                  RSA Data Security, Inc.
27                                                             10 July 1991
29                     The MD5 Message-Digest Algorithm
31 STATUS OF THIS MEMO
33    This draft document will be submitted to the RFC editor as a protocol
34    specification. Comments should be sent to <pem-dev@tis.com> or to the
35    authors. Distribution of this memo is unlimited.
37 ACKNOWLEDGEMENT
39    We would like to thank Don Coppersmith, Burt Kaliski, Ralph Merkle,
40    David Chaum, and Noam Nisan for numerous helpful comments and
41    suggestions.
43 Table of Contents
45    1. Executive Summary                                                1
46    2. Terminology and Notation                                         2
47    3. MD5 Algorithm Description                                        3
48    4. Summary                                                          7
49    5. Summary of Differences Between MD4 and MD5                       7
50    6. Security Considerations                                          7
51    References                                                          8
52    Authors' Addresses                                                  8
53    APPENDIX - Reference Implementation                                 9
55 1. Executive Summary
57    This document describes the MD5 message-digest algorithm. The
58    algorithm takes as input an input message of arbitrary length and
59    produces as output a 128-bit "fingerprint" or "message digest" of the
60    input. It is conjectured that it is computationally infeasible to
61    produce two messages having the same message digest, or to produce
62    any message having a given prespecified target message digest. The
63    MD5 algorithm is intended for digital signature applications, where a
64    large file must be "compressed" in a secure manner before being
65    encrypted with a private (secret) key under a public-key cryptosystem
66    such as RSA.
68    The MD5 algorithm is designed to be quite fast on 32-bit machines. In
69    addition, the MD5 algorithm does not require any large substitution
70    tables; the algorithm can be coded quite compactly.
72    The MD5 algorithm is an extension of the MD4 message digest algorithm
73    [1,2]. MD5 is slightly slower than MD4, but is more "conservative" in
74    design. MD5 was designed because it was felt that MD4 was perhaps
75    being adopted for use more quickly than justified by the existing
76    critical review; because MD4 was designed to be exceptionally fast,
77    it is "at the edge" in terms of risking successful cryptanalytic
78    attack. MD5 backs off a bit, giving up a little in speed for a much
79    greater likelihood of ultimate security. It incorporates some
80    suggestions made by various reviewers, and contains additional
81    optimizations.
83    The MD5 algorithm is being placed in the public domain for review and
84    possible adoption as a standard.
86    A version of this document including the C source code in the
87    appendix is available by FTP from RSA.COM in the file "pub/md5.doc".
89    This document may be referred to, unofficially, as Internet draft
90    [MD5-A].
92    For OSI-based applications, MD5's object identifier is
94    md5 OBJECT IDENTIFIER ::=
95      {iso(1) member-body(2) US(840) rsadsi(113549) digestAlgorithm(2) 5}
97    In the X.509 type AlgorithmIdentifier [3], the parameters for MD5
98    should have type NULL.
101 2. Terminology and Notation
103    In this document a "word" is a 32-bit quantity and a "byte" is an
104    eight-bit quantity. A sequence of bits can be interpreted in a
105    natural manner as a sequence of bytes, where each consecutive group
106    of eight bits is interpreted as a byte with the high-order (most
107    significant) bit of each byte listed first. Similarly, a sequence of
108    bytes can be interpreted as a sequence of 32-bit words, where each
109    consecutive group of four bytes is interpreted as a word with the
110    low-order (least significant) byte given first.
112    Let x_i denote "x sub i". If the subscript is an expression, we
113    surround it in braces, as in x_{i+1}. Similarly, we use ^ for
114    superscripts (exponentiation), so that x^i denotes x to the i-th
115    power.
117    Let the symbol "+" denote addition of words (i.e., modulo-2^32
118    addition). Let X <<< s denote the 32-bit value obtained by circularly
119    shifting (rotating) X left by s bit positions. Let not(X) denote the
120    bit-wise complement of X, and let X v Y denote the bit-wise OR of X
121    and Y. Let X xor Y denote the bit-wise XOR of X and Y, and let XY
122    denote the bit-wise AND of X and Y.
125 3. MD5 Algorithm Description
127    We begin by supposing that we have a b-bit message as input, and that
128    we wish to find its message digest. Here b is an arbitrary
129    nonnegative integer; b may be zero, it need not be a multiple of
130    eight, and it may be arbitrarily large. We imagine the bits of the
131    message written down as follows:
133                             m_0 m_1 ... m_{b-1}
135    The following five steps are performed to compute the message digest
136    of the message.
138 3.1 Step 1. Append Padding Bits
140    The message is "padded" (extended) so that its length (in bits) is
141    congruent to 448, modulo 512. That is, the message is extended so
142    that it is just 64 bits shy of being a multiple of 512 bits long.
143    Padding is always performed, even if the length of the message is
144    already congruent to 448, modulo 512 (in which case 512 bits of
145    padding are added).
147    Padding is performed as follows: a single "1" bit is appended to the
148    message, and then enough zero bits are appended so that the length in
149    bits of the padded message becomes congruent to 448, modulo 512.
151 3.2 Step 2. Append Length
153    A 64-bit representation of b (the length of the message before the
154    padding bits were added) is appended to the result of the previous
155    step. In the unlikely event that b is greater than 2^64, then only
156    the low-order 64 bits of b are used. (These bits are appended as two
157    32-bit words and appended low-order word first in accordance with the
158    previous conventions.)
160    At this point the resulting message (after padding with bits and with
161    b) has a length that is an exact multiple of 512 bits. Equivalently,
162    this message has a length that is an exact multiple of 16 (32-bit)
163    words. Let M[0 ... N-1] denote the words of the resulting message,
164    where N is a multiple of 16.
166 3.3 Step 3. Initialize MD Buffer
168    A four-word buffer (A,B,C,D) is used to compute the message digest.
169    Here each of A, B, C, D is a 32-bit register. These registers are
170    initialized to the following values in hexadecimal, low-order bytes
171    first):
173                             word A: 01 23 45 67
174                             word B: 89 ab cd ef
175                             word C: fe dc ba 98
176                             word D: 76 54 32 10
178 3.4 Step 4. Process Message in 16-Word Blocks
180    We first define four auxiliary functions that each take as input
181    three 32-bit words and produce as output one 32-bit word.
183                          F(X,Y,Z) = XY v not(X) Z
184                          G(X,Y,Z) = XZ v Y not(Z)
185                          H(X,Y,Z) = X xor Y xor Z
186                        I(X,Y,Z) = Y xor (X v not(Z))
188    In each bit position F acts as a conditional: if X then Y else Z.
189    (The function F could have been defined using + instead of v since XY
190    and not(X)Z will never have 1's in the same bit position.) It is
191    interesting to note that if the bits of X, Y, and Z are independent
192    and unbiased, the each bit of F(X,Y,Z) will be independent and
193    unbiased.
195    The functions G, H, and I are similar to the function F, in that they
196    act in "bitwise parallel" to produce their output from the bits of X,
197    Y, and Z, in such a manner that if the corresponding bits of X, Y,
198    and Z are independent and unbiased, then each bit of G(X,Y,Z),
199    H(X,Y,Z), and I(X,Y,Z) will be independent and unbiased. Note that
200    the function H is the bit-wise "xor" or "parity" function of its
201    inputs.
203    Do the following:
205    /* Process each 16-word block. */
206    For i = 0 to N/16-1 do
208        /* Copy block i into X. */
209        For j = 0 to 15 do
210            Set X[j] to M[i*16+j].
211        end /* of loop on j */
213        /* Save A as AA, B as BB, C as CC, and D as DD. */
214        AA = A
215        BB = B
216        CC = C
217        DD = D
219        /* Round 1. */
220        /* Let FF(a,b,c,d,X[k],s,t) denote the operation
221            a = b + ((a + F(b,c,d) + X[k] + t) <<< s). */
222        /* Here the additive constants t are chosen as follows:
223           In step i, the additive constant is the integer part of
224           4294967296 times abs(sin(i)), where i is in radians. */
225        /* Let S11 = 7, S12 = 12, S13 = 17, and S14 = 22. */
226        /* Do the following 16 operations. */
227        FF (a, b, c, d, X[ 0], S11, 3614090360); /* Step 1 */
228        FF (d, a, b, c, X[ 1], S12, 3905402710); /* 2 */
229        FF (c, d, a, b, X[ 2], S13,  606105819); /* 3 */
230        FF (b, c, d, a, X[ 3], S14, 3250441966); /* 4 */
231        FF (a, b, c, d, X[ 4], S11, 4118548399); /* 5 */
232        FF (d, a, b, c, X[ 5], S12, 1200080426); /* 6 */
233        FF (c, d, a, b, X[ 6], S13, 2821735955); /* 7 */
234        FF (b, c, d, a, X[ 7], S14, 4249261313); /* 8 */
235        FF (a, b, c, d, X[ 8], S11, 1770035416); /* 9 */
236        FF (d, a, b, c, X[ 9], S12, 2336552879); /* 10 */
237        FF (c, d, a, b, X[10], S13, 4294925233); /* 11 */
238        FF (b, c, d, a, X[11], S14, 2304563134); /* 12 */
239        FF (a, b, c, d, X[12], S11, 1804603682); /* 13 */
240        FF (d, a, b, c, X[13], S12, 4254626195); /* 14 */
241        FF (c, d, a, b, X[14], S13, 2792965006); /* 15 */
242        FF (b, c, d, a, X[15], S14, 1236535329); /* 16 */
244        /* Round 2. */
245        /* Let GG(a,b,c,d,X[k],s,t) denote the operation
246            a = b + ((a + G(b,c,d) + X[k] + t) <<< s). */
247        /* Let S21 = 5, S22 = 9, S23 = 14, and S24 = 20. */
249        /* Do the following 16 operations. */
250        GG (a, b, c, d, X[ 1], S21, 4129170786); /* 17 */
251        GG (d, a, b, c, X[ 6], S22, 3225465664); /* 18 */
252        GG (c, d, a, b, X[11], S23,  643717713); /* 19 */
253        GG (b, c, d, a, X[ 0], S24, 3921069994); /* 20 */
254        GG (a, b, c, d, X[ 5], S21, 3593408605); /* 21 */
255        GG (d, a, b, c, X[10], S22,   38016083); /* 22 */
256        GG (c, d, a, b, X[15], S23, 3634488961); /* 23 */
257        GG (b, c, d, a, X[ 4], S24, 3889429448); /* 24 */
258        GG (a, b, c, d, X[ 9], S21,  568446438); /* 25 */
259        GG (d, a, b, c, X[14], S22, 3275163606); /* 26 */
260        GG (c, d, a, b, X[ 3], S23, 4107603335); /* 27 */
261        GG (b, c, d, a, X[ 8], S24, 1163531501); /* 28 */
262        GG (a, b, c, d, X[13], S21, 2850285829); /* 29 */
263        GG (d, a, b, c, X[ 2], S22, 4243563512); /* 30 */
264        GG (c, d, a, b, X[ 7], S23, 1735328473); /* 31 */
265        GG (b, c, d, a, X[12], S24, 2368359562); /* 32 */
267        /* Round 3. */
268        /* Let HH(a,b,c,d,X[k],s,t) denote the operation
269            a = b + ((a + H(b,c,d) + X[k] + t) <<< s). */
270        /* Let S31 = 4, S32 = 11, S33 = 16, and S34 = 23. */
272        /* Do the following 16 operations. */
273        HH (a, b, c, d, X[ 5], S31, 4294588738); /* 33 */
274        HH (d, a, b, c, X[ 8], S32, 2272392833); /* 34 */
275        HH (c, d, a, b, X[11], S33, 1839030562); /* 35 */
276        HH (b, c, d, a, X[14], S34, 4259657740); /* 36 */
277        HH (a, b, c, d, X[ 1], S31, 2763975236); /* 37 */
278        HH (d, a, b, c, X[ 4], S32, 1272893353); /* 38 */
279        HH (c, d, a, b, X[ 7], S33, 4139469664); /* 39 */
280        HH (b, c, d, a, X[10], S34, 3200236656); /* 40 */
281        HH (a, b, c, d, X[13], S31,  681279174); /* 41 */
282        HH (d, a, b, c, X[ 0], S32, 3936430074); /* 42 */
283        HH (c, d, a, b, X[ 3], S33, 3572445317); /* 43 */
284        HH (b, c, d, a, X[ 6], S34,   76029189); /* 44 */
285        HH (a, b, c, d, X[ 9], S31, 3654602809); /* 45 */
286        HH (d, a, b, c, X[12], S32, 3873151461); /* 46 */
287        HH (c, d, a, b, X[15], S33,  530742520); /* 47 */
288        HH (b, c, d, a, X[ 2], S34, 3299628645); /* 48 */
290        /* Round 4. */
291        /* Let II(a,b,c,d,X[k],s,t) denote the operation
292            a = b + ((a + I(b,c,d) + X[k] + t) <<< s). */
293        /* Let S41 = 6, S42 = 10, S43 = 15, and S44 = 21. */
295        /* Do the following 16 operations. */
296        II (a, b, c, d, X[ 0], S41, 4096336452); /* 49 */
297        II (d, a, b, c, X[ 7], S42, 1126891415); /* 50 */
298        II (c, d, a, b, X[14], S43, 2878612391); /* 51 */
299        II (b, c, d, a, X[ 5], S44, 4237533241); /* 52 */
300        II (a, b, c, d, X[12], S41, 1700485571); /* 53 */
301        II (d, a, b, c, X[ 3], S42, 2399980690); /* 54 */
302        II (c, d, a, b, X[10], S43, 4293915773); /* 55 */
303        II (b, c, d, a, X[ 1], S44, 2240044497); /* 56 */
304        II (a, b, c, d, X[ 8], S41, 1873313359); /* 57 */
305        II (d, a, b, c, X[15], S42, 4264355552); /* 58 */
306        II (c, d, a, b, X[ 6], S43, 2734768916); /* 59 */
307        II (b, c, d, a, X[13], S44, 1309151649); /* 60 */
308        II (a, b, c, d, X[ 4], S41, 4149444226); /* 61 */
309        II (d, a, b, c, X[11], S42, 3174756917); /* 62 */
310        II (c, d, a, b, X[ 2], S43,  718787259); /* 63 */
311        II (b, c, d, a, X[ 9], S44, 3951481745); /* 64 */
313        /* Then perform the following additions. (That is, increment each
314           of the four registers by the value it had before this block
315           was started.) */
316        A = A + AA
317        B = B + BB
318        C = C + CC
319        D = D + DD
321    end /* of loop on i */
323 3.5 Step 5. Output
325    The message digest produced as output is A, B, C, D. That is, we
326    begin with the low-order byte of A, and end with the high-order byte
327    of D.
329    This completes the description of MD5. A reference implementation in
330    C is given in the Appendix.
333 4. Summary
335    The MD5 message-digest algorithm is simple to implement, and provides
336    a "fingerprint" or message digest of a message of arbitrary length.
337    It is conjectured that the difficulty of coming up with two messages
338    having the same message digest is on the order of 2^64 operations,
339    and that the difficulty of coming up with any message having a given
340    message digest is on the order of 2^128 operations. The MD5 algorithm
341    has been carefully scrutinized for weaknesses. It is, however, a
342    relatively new algorithm and further security analysis is of course
343    justified, as is the case with any new proposal of this sort.
346 5. Summary of Differences Between MD4 and MD5
348    The following are the differences between MD4 and MD5:
350      --   A fourth round has been added.
352      --   Each step now has a unique additive constant.
354      --   The function g in round 2 was changed from (XY v XZ v YZ)
355           to (XZ v Y not(Z)) to make g less symmetric.
357      --   Each step now adds in the result of the previous step.
358           This promotes a faster "avalanche effect".
360      --   The order in which input words are accessed in rounds 2
361           and 3 is changed, to make these patterns less like each
362           other.
364      --   The shift amounts in each round have been approximately
365           optimized, to yield a faster "avalanche effect". The
366           shifts in different rounds are distinct.
369 6. Security Considerations
371    The level of security discussed in this memo is considered to be
372    sufficient for implementing very high security hybrid digital-
373    signature schemes based on MD5 and a public-key cryptosystem.
376 References
378      [1]  Rivest, R.L., The MD4 Message Digest Algorithm (RFC 1186),
379           October 1990.
381      [2]  Rivest, R.L., The MD4 message digest algorithm, presented at
382           CRYPTO '90 (Santa Barbara, CA, August 11-15, 1990).
384      [3]  CCITT, The Directory---Authentication Framework
385           (Recommendation X.509), 1988.
388 Authors' Addresses
390    Ronald L. Rivest
391    Massachusetts Institute of Technology
392    Laboratory for Computer Science
393    NE43-324
394    545 Technology Square
395    Cambridge, MA  02139-1986
396    Phone: (617) 253-5880
397    EMail: rivest@theory.lcs.mit.edu
399    Steve Dusse
400    RSA Data Security, Inc.
401    10 Twin Dolphin Drive
402    Redwood City, CA  94065
403    Phone: (415) 595-8782
404    EMail: dusse@rsa.com
407 APPENDIX - Reference Implementation
409    This appendix contains the following files:
411      md5.h -- header file for implementation of MD5
413      md5.c -- the source code for MD5 routines
415      md5driver.c -- sample test routines
417      session -- sample results of running md5driver
419    It is not difficult to improve this implementation on particular
420    platforms, an exercise left to the reader. Following are some
421    suggestions:
423      1.   Change MD5Update so that the context is not used at all
424           if it is empty (mdi == 0) and 64 or more bytes remain
425           (inLen >= 64). In other words, call Transform with inBuf
426           in this case. (This requires that byte ordering is
427           correct in inBuf.)
429      2.   Implement a procedure MD5UpdateLong modeled after
430           MD5Update where inBuf is UINT4 * instead of unsigned char
431           *. MD5UpdateLong would call Transform directly with 16-
432           word blocks from inBuf. Call this instead of MD5Update in
433           general. This works well if you have an I/O procedure
434           that can read long words from a file.
436      3.   On "little-endian" platforms where the lowest-address
437           byte in a long word is the least significant (and there
438           are no alignment restrictions), change MD5Update to call
439           Transform directly with 64-byte blocks from inBuf
440           (typecast to a UINT4 *).