Overview of MD5's full name is Message-Digest Algorithm 5 (Information - Summary Algorithm), in the 1990s, the Ronald L of Mit Laboratory for Computer Science and RSA Data Security Inc, developed by MD2, MD3, and MD4. Its role is to make large capacity information to be "compressed" into a confidential format before signing private privacy with digital signature software (that is, transforms an arbitrary length of byte string into a certain length). Whether it is MD2, MD4 or MD5, they all need to obtain a random length of information and generate a 128-bit information summary. Although the structure of these algorithms is more similar, the design of MD2 is completely different from MD4 and MD5, because MD2 is designed for 8-bit machines, while MD4 and MD5 are 32-bit computers. The three algorithms have a detailed description in the Internet RFCS 1321 (http://www.ietf.org/rfc/rfc1321.txt )/5 below is this article * /, this It is the most authoritative document, by Ronald L. Rivest submitted to IEFT in August 1992. Rivest developed an MD2 algorithm in 1989. In this algorithm, the information is first supplied to the information, so that the byte length of the information is a multiple of 16. Then, at a 16-bit test and append to the end of the information. And calculate the hash value based on this new information. Later, Rogier and Chauvaud found that if the test and the MD2 conflict will be generated. The result of the encryption of the MD2 algorithm is unique - neither repeat. In order to enhance the safety of the algorithm, RiveSt has developed an MD4 algorithm in 1990. The MD4 algorithm also needs to fill the information to ensure that the byte length of the information plus 448 can be divided by 512 (information byte length MOD 512 = 448). Then, one of the initial lengths of information indicated by 64-bit binary is added. The information is processed into blocks of 512-bit DAMG? RD / Merkle iterative structure, and each block is to be processed by three different steps. Den Boer and Bosselaers and others quickly discovered the first step and third steps in the MD4 version. Dobbertin demonstrates how to use a regular personal computer to find a conflict in the full version of the MD4 in a few minutes (this conflict is actually a vulnerability, which will result in encryption of different content but may get the same encryption. result). There is no doubt that MD4 is eliminated. Although the MD4 algorithm has such a large vulnerability in the security, it has a guiding role in the presence of several information security encryption algorithms that have been developed thereon. In addition to MD5, there are also SHA-1, RIPE-MD, and HAVAL, etc. One year later, that is, in 1991, Rivest developed technology more approached MD5 algorithm. It adds the concept of "safe-band" (safty-beelts) based on MD4. Although MD5 is slightly slower than MD4, it is safer. This algorithm is obvious by four and MD4 designs with a little different steps. In the MD5 algorithm, the size of the information - summary and the necessary conditions of the filler are identical to the MD4. Den Boer and Bosselaers have discovered pseudo-collisions in the MD5 algorithm, but there is no other resulting result.
Van Orschot and Wiener have considered a function of violent search conflicts in hash, and they guess a machine that is designed to search for MD5 conflicts (this machine is approximately manufactured in 1994 It is a million US dollars) to find a conflict every 24 days. However, from 1991 to 2001, there is no new algorithm for MD6 or other names that have alternative MD5 algorithms, and we can see that this flaw does not have much impact on MD5 security. All of these is not enough to become MD5 problems in practical applications. Also, since the use of the MD5 algorithm does not need to pay any copyright costs, in general (non-top secret applications. But even if the application is in the top secret field, MD5 is not a very good intermediate technology), MD5 It should be considered very safe. The typical application of the algorithm application MD5 is a message-digest to prevent tampering. For example, there are many software in UNIX to have a file name in the download, the file extension is the file named .md5, usually only one line of text in this file, general structure, MD5 (tanajiya.tar.gz) = 0ca175b9c0f726a831d895e269332461 This is a digital signature of tanajiya.tar.gz file. MD5 uses the entire file as a large text message, producing this unique MD5 information summary through its irreversible string conversion algorithm. If in the process of transmitting this file later, regardless of any form changes in the content of the file (including the transmission error caused by the line instability during the download process), as long as you recall the MD5, you will find it. The summary of the information is different, thereby determining that you get just an incorrect file. If there is another third party certification body, use MD5 to prevent "reliability" of the author, this is the so-called digital signature application. MD5 is also widely used in encryption and decryption technology. For example, the user's password in the UNIX system is stored in the file system after the MD5 (or other similar algorithm) is encrypted. When the user logs in, the system calculates the password entered into the MD5 value, then goes and saved the MD5 value in the file system to compare, and then determine if the input password is correct. By this step, the system can determine the legality of the user login system without knowing the coding of the user's password. This not only avoids the user's password known by the user of the system administrator privilege, but also adds the difficulty of password being crack to some extent. It is precisely because of this reason, the method of hacked the most deciphering password is a method called "running". There are two ways to get a dictionary, one is a character string table for daily collections, the other is to generate the MD5 value of these dictionaries with the MD5 program, and then use the target The MD5 value is retrieved in this dictionary. We assume that the maximum length of the password is 8-bit bytes (8 bytes), and the password can only be a letter and a number, a total of 26 26 10 = 62 characters, and the number of items that are arranged in the group is P (62, 1) p (62, 2) .... P (62, 8), it is already a very an astronomical number, storing this dictionary requires a TB-level disk array, and this method has a premise, It is possible to get the password MD5 value of the target account. This encryption technology is widely used in UNIX systems, which is why the UNIX system is more robust than a general operating system.
Algorithm Description The MD5 algorithm brief description can be: MD5 in a 512-bit packet to process the input information, and each group is divided into 16 32-bit sub-packets, after a series of processes, the output of the algorithm is from four 32-bit packets, which will generate a 128-bit quotation value after the four 32-bit grouping levels will be generated. In the MD5 algorithm, the information is first to be filled, so that the result of the byte length to 512 is equal to 448. Therefore, the byte length of the information will be extended to N * 512 448, namely N * 64 56 bytes, n is a positive integer. The filling method is as follows, and one 1 and countless 0 are filled in the rear of the information until 0 to the information of the information is stopped using 0. Then, the length of the pre-filling before this result is additionally indicated by 64-bit binary. After these two steps, the current information byte length = N * 512 448 64 = (n 1) * 512, that is, the length is exactly the integer multiple of 512. The reason for this is to meet the requirements of the information length in the back processing. The MD5 has four 32-bit integer parameters of chaining variable, which are: a = 0x01234567, b = 0x89abcdef, c = 0xfedcba98, d = 0x76543210. When these four link variables are set, the four-wheel loop calculation of the algorithm is started. The number of cycles is the number of 512-bit information packets in the information. Copy the above four link variables to the other four variables: A to A, B to B, C to C, D to D. The main circulation has four rounds (MD4 only three rounds), each round of cycles are similar. The first round of 16 operations. Each of the A, B, C, and D is operated for a nonlinear function calculation, and then the resulting result is added to the fourth variable, a sub-packet and a constant of the text. The resulting result is then moved to the right ring and plus one of A, B, C or D. Finally, the results are used to replace one of A, B, C or D. Take it is the four nonlinear functions used in each operation (one per wheel). F (x, y, z) = (x & y) | ((~ x) & z) g (x, y, z) = (x & z) | (Y & (~ z)) h (x, y, z) = x ^ Y ^ z i (x, y, z) = y ^ (x | (~ z)) (& Yes, | Yes, ~ is not, ^ is different or) these four functions: If x, The corresponding position of Y and Z is independent and uniform, and each bit of the result should also be independent and uniform. f is a function of bitmaping. That is, if x, then y, otherwise z. The function h is a bitmap parity.
Suppose MJ represents the jth packet (from 0 to 15), << ff (A, B, C, D, MJ, S, Ti) ((A (F (B, C, D) MJ Ti) << GG (A, B, C, D, MJ, S, Ti) represents A = B ((A (G (B, C, D) MJ Ti) << HH (A, B, C, D, MJ, S, Ti) represent A = B ((A (H (B, C, D) MJ Ti) << II (A, B, C, D, MJ, S, Ti ) Represents A = B ((A (i (B, C, D) MJ Ti) << These four rounds (64 steps) are:
The first round of FF (A, B, C, D, M0, 7, 0xD76AA478) FF (D, A, B, C, M1, 12, 0XE8C7B756) FF (C, D, A, B, M2, 17, 0X242070DB) FF (B, C, D, A, M3, 22, 0XC1BDCEEE) FF (A, B, C, D, M4, 7, 0xF57C0FAF) FF (D, A, B, C, M5, 12, 0X4787C62A) FF (C, D, A, B, M6, 17, 0XA8304613) FF (B, C, D, A, M7, 22, 0xFD469501) FF (A, B, C, D, M8, 7, 0x698098D8) FF (D , A, B, C, M9, 12, 0x8B44F7AF) FF (C, D, A, B, M10, 17, 0xFFFFF5BB1) FF (B, C, D, A, M11, 22, 0X895CD7BE) FF (A, B , C, D, M12, 7, 0x6b90112) FF (D, A, B, C, M13, 12, 0xFD987193) FF (C, D, A, B, M14, 17, 0XA679438E) FF (B, C, D , A, M15, 22, 0X49B40821) The second round Gg (A, B, C, D, M1, 5, 0xF61E2562) Gg (D, A, B, C, M6, 9, 0XC040B340) Gg (C, D, A, B, M11, 14, 0x265E5A51) Gg (B, C, D, A, M0, 20, 0XE9B6C7AA) Gg (A, B, C, D, M5, 5, 0xD62F105D) Gg (D, A, B, C, M10, 9, 0x02441453) Gg (C, D, A, B, M15, 14, 0XD8A1E681) Gg (B, C, D, A, M4, 20, 0 xE7D3FBC8) Gg (A, B, C, D, M9, 5, 0X21E1CDE6) Gg (D, A, B, C, M14, 9, 0XC33707D6) Gg (C, D, A, B, M3, 14, 0xF4D50D87) Gg (B, C, D, A, M8, 20, 0X455A14ED) Gg (A, B, C, D, M13, 5, 0xA9E3E905) Gg (D, A, B, C, M2, 9, 0XFCEFA3F8) Gg (C, D, A, B, M7, 14, 0x676f02d9) GG (B, C, D, M12, 20, 0x8D2A4C8A) third round HH (A, B, C, D, M5, 4, 0xFFFA3942) HH (D, A, B, C, M8, 11, 0x8771F681 HH (C, D, B, M11, 16, 0x6D9D6122) HH (B, C, D, A, M14, 23, 0XFDE5380C) HH (A, B, C, D, M1, 4, 0xA4Beea44) HH (D, A, B, C, M4, 11, 0x4 bdecfa9) HH (C, D, A, B, M7, 16, 0XF6Bb4B60) HH (B, C, D, A, M10, 23, 0XBEBFBC70) HH (a , B, C, D, M3, 4, 0X289B7EC6) HH (D, A, B, C, M0, 11, 0XEAA127FA) HH (C, D, A, B, M3, 16, 0xD4ef3085) HH (B, C , D, A, M6, 23, 0x04881D05) HH (A, B, C, D, M9, 4, 0xD9D4D039) HH (D, A, B, C, M12, 11, 0XE6DB99E5) HH (C, D, A , B, M15, 16, 0X1FA27CF8) HH (B, C, D, M2, 23, 0XC4AC5665) fourth round II (A, B, C, D, M0, 6, 0xF429244) II (D, A, B, C, M7, 10, 0x432AFF97) II (C, D, B, M14, 15, 0XAB9423A7) II (B, C, D, A, M5, 21, 0xFC93A039) II (A, B, C, D, M12, 6, 0x655559c3) II (D, A, B, C, M3, 10,
0x8F0CCC92) II (C, D, A, B, M10, 15, 0xFFEFF47D) II (B, C, D, A, M1, 21, 0X85845DD1) II (A, B, C, D, M8, 6, 0x6FA87E4F) II (D, A, B, C, M15, 10, 0XFE2CE6E0) II (C, D, A, B, M6, 15, 0XA3014314) II (B, C, D, A, M13, 21, 0X4E0811A1) II ( A, B, C, D, M4, 6, 0xF7537E82) II (D, A, B, C, M11, 10 x BD3AF235) II (C, D, A, B, M2, 15, 0X2AD7D2BB) II (B, C, D, A, M9, 21, 0 xeb86d391) constant Ti can be selected as follows: In the first step, Ti is the integer portion of 4294967296 * ABS (SiN (i)), and the unit of I is an arc. (4294967296 equal to 2 32) All of these completed, add A, B, C, and D, respectively, plus A, B, C, D. Then use the next packet data to continue the algorithm, and the last output is cascaded of A, B, C, and D. When you implement the MD5 algorithm according to the method I mentioned above, you can use the following information to make a simple test you made, see if there is any error. md5 ( "") = d41d8cd98f00b204e9800998ecf8427e md5 ( "a") = 0cc175b9c0f1b6a831c399e269772661 md5 ( "abc") = 900150983cd24fb0d6963f7d28e17f72 md5 ( "message digest") = f96b697d7cb7938d525a2f31aaf161d0 md5 ( "abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b md5 ( "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz0123456789") = d174ab98d277d9f5a5611c2c9f419d9f md5 ( "12345678901234567890123456789012345678901234567890123456789012345678901234567890") = 57edf4a22be3c955ac49da2e2107b67a If you use the above information for each instance of md5 algorithm do you do the test, and finally concluded that the standard answer exactly the same, then I will be here as you said loudly congratulated. To know, my program is not derived from the same result when the first compilation is successful. MD5's security MD5 relative to MD4 improvements: 1. Increase the fourth round; 2. Each step has a unique addition constant; 3. To reduce the symmetry of function G in the second round, (X & Y) | (x & z ) | (y & z) | (Y & (~ z)); 4. The first step plus the previous result, which will cause faster avalanches; 5. Change the second round and The sequence of the message sub-packet is accessed in the three-wheel, which makes it more similar; 6. Approximately optimize the loop left shift shift in each round to achieve a faster avalanche effect. The displacement amount of each wheel is different. Quote: http://www.gameres.com/articles/program/ABSTRACT/Arithmetic/md5.htm
Network Working Group R. RivestRequest for Comments:. 1321 MIT Laboratory for Computer Science and RSA Data Security, Inc. April 1992 The MD5 Message-Digest Algorithm Status of this Memo This memo provides information for the Internet community It does not specify an Internet standard . Distribution of this memo is unlimited. Acknowlegements We would like to thank Don Coppersmith, Burt Kaliski, Ralph Merkle, David Chaum, and Noam Nisan for numerous helpful comments and suggestions. Table of Contents 1. Executive Summary 1 2. Terminology and Notation 2 3. MD5 Algorithm Description 3 4. Summary 6 5. Differenc es Between MD4 and MD5 6 References 7 APPENDIX A -. Reference Implementation 7 Security Considerations 21 Author's Address 21 1. Executive Summary This document describes the MD5 message-digest algorithm The algorithm takes as input a message of arbitrary length and produces as output a 128 -bit "fingerprint" or "message digest"
of the input. It is conjectured that it is computationally infeasible to produce two messages having the same message digest, or to produce any message having a given prespecified target message digest. The MD5 algorithm is intended for digital signature applications, where a large file must be "compressed" in a secure manner before being encrypted with a private (secret) key under a public-key cryptosystem such as RSA. Rivest [Page 1] RFC 1321 MD5 Message-Digest algorithm April 1992 The MD5 algorithm is designed to be quite . fast on 32-bit machines In addition, the MD5 algorithm does not require any large substitution tables;. the algorithm can be coded quite compactly The MD5 algorithm is an extension of the MD4 message-digest algorithm 1,2] MD5 is slightly. Slower Than MD4, But Is More "Conservative" in Design. MD5 Was Designed Because It Was Felt That MD4 WAS Perhaps being adopted for use more quickly than justified by the existing critical review; because MD4 was designed to be exceptionally fast, it is "at the edge" in terms of risking successful cryptanalytic attack MD5 backs off a bit, giving up a little in speed. for a much greater likelihood of ultimate security. It incorporates some suggestions made by various reviewers, and contains additional optimizations. The MD5 algorithm is being placed in the public domain for review and possible adoption as a standard. for OSI-based applications, MD5's object Identifier is MD5 Object Identifier :: =
ISO (1) Member-body (2) US (840) Rsadsi (113549) Digestalgorithm (2) 5} in the x.509 type algorithmidentifier [3], The parameters for md5 shouth Should Have Type Null. 2. Terminology and notation in this document a "word" is a 32-bit quantity and a "byte" is an eight-bit quantity. A sequence of bits can be interpreted in a natural manner as a sequence of bytes, where each consecutive group of eight bits is interpreted as a byte with the high-order (most significant) bit of each byte listed first. Similarly, a sequence of bytes can be interpreted as a sequence of 32-bit words, where each consecutive group of four bytes is interpreted as a word with THE LOW-Order (Least Significant) Byte Given First. Let X_i Denote "X Sub I". If The SUBScript IS An Expression, WE Surround IT IN Braces, AS IN X_ {i 1}. Similarly, We Use ^ for SUPERSCRIPTS (Exponentiation), SO That X ^ I Denotes x to the I-th Power. Let the symbol " " Denote Addition of Words (IE, MODULO-2 ^ 32 Additio N). Let x <<< s Denote the 32-bit value obtained by circularly shifting (rotating) x Left by s bit positions. Let not (x) den Penote the bit-wise complement of x, and let x v y Denote the Bit-wise or of x and y. x xor y denote the bit-wise xor of x and y, and let xy denote the bit-wise and of x and y. rivest [Page 2] RFC 1321 MD5 Message-Digest Algorithm April 1992 3. MD5 Algorithm Description We Begin by Supposing That We Have A B- BIT Message As INPUT, AND THAT Message AS INPUT, AND THAT Message To Find ITS Message Digest. Here B;
b may be zero, it need not be a multiple of eight, and it may be arbitrarily large We imagine the bits of the message written down as follows:. m_0 m_1 ... m_ {b-1} The following five steps are performed to compute the message digest of the message. 3.1 Step 1. Append Padding bits The message is "padded" (extended) so that its length (in bits) is congruent to 448, modulo 512. that is, the message is extended so that it is just 64 bits shy of being a multiple of 512 bits long Padding is always performed, even if the length of the message is already congruent to 448, modulo 512. Padding is performed as follows:. a single "1" bit is appended To the message, and then "0"
bits are appended so that the length in bits of the padded message becomes congruent to 448, modulo 512. In all, at least one bit and at most 512 bits are appended. 3.2 Step 2. Append Length A 64-bit representation of b ( the length of the message before the padding bits were added) is appended to the result of the previous step. In the unlikely event that b is greater than 2 ^ 64, then only the low-order 64 bits of b are used. (These bits are appended as two 32-bit words and appended low-order word first in accordance with the previous conventions.) At this point the resulting message (after padding with bits and with b) has a length that is an exact multiple of 512 bits Equivalently, this Message Has a Length That IS An Exact Multiple Of 16 (32-Bit) Words. Let M [0 ... N-1] Denote The Words of The Resulting Message, WHERE N IS A MULTIPLE OF 16.3.3 Step 3. Initialize Md Buffer A Four-Word Buffer (A, B, C, D) IS Used to Compute The Message Digest. Here Each Of A, B, C, D IS A 32-BIT Register. THESE REGISTERS in Hexadecimal, Low-Order Bytes First): Rivest [Page 3] RFC 1321 MD5 Message-Digest Algorithm April 1992 Word A: 01 23 45 67 Word B: 89 AB CD EF Word C: FE DC BA 98 Word D: 76 54 32 10 3.4 Step 4. Process Message In 16-Word Blocks We First Define Four Auxiliary Functions That Each Take AS Input Three 32- Bit Words and Produce As Output One 32-Bit Word. f (x, y, z) = XY V NOT (X) Z g (x, y, z) = xz v y NOT (Z) h (x, y, Z) = x xor y xor z i (x, y, z) =
Y xor (x v not (z)) in Each Bit Position f ACTS AS A CONDITIONAL: IF X THEN Y ELSE Z. The Function F Could Have Been Defined Using Instead of V Since XY and NOTSTEAD OF V SINECE XY AND NOT 1's ITERESTINTING TO NOTE THAT INDEPENT AND UNBISED, The Functions G , H, AND I am SIMILAR TOT IN "Bitwise Parallel" to produce their output from the bits of x, y, and z, in Such a manner That if the corresponding bits of x, y, And Z Arepend, THEN Each Bit of G (X, Y, Z), H (x, y, z), AND i (x, y, z) Will be independent and unbiased. Note That The Function H IS THE BIT-WISE "xor" Parity "Function of ITS INPUTS. THIS STEP Uses A 64-Element Table T [1 ... 64] Constructed from the sine function. Let t [i] Denote The I-TH ELEMENT OF THE TABLE, WHICH IS Equal to The Integer Part of 4294967296 Times ABS (SIN (I)) WHERE I is in Radians. The elements of the table area given in the appendix. do the folload: / * process Each 16-word block * / for i = 0 to n / 16-1 do / * Copy Block I Into X. * / for j = 0 to 15 do set x [j] to m [i * 16 j]. End / * of loop on j * / / * save a as aa, b as bb, c as cc, And d as dd. * / aa = a bb = b Rivest [Page 4] RFC 1321 MD5 Message-Digest Algorithm April 1992 CC = C DD = D / * ROUND 1. * / / * let [Abcd KSI] DENOTE The Operation A = B ((A F (B, C, D) X [K] T [I]) <<<
s). * / / * do the folload 16 Operations. * / [Abcd 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4] [ABCD 4 7 5] [DABC 5 12 6 ] [CDAB 6 17 7] [ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12] [ABCD 12 7 13] [DABC 13 12 14] [ CDAB 14 17 15] / * Round 2. * / / * let [ABCD KSI] DENOTE THE OPERATION A = B ((A G (B, C, D) X [K] T [I]) <<< s). * / / * Do the folload 16 Operations. * / [Abcd 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20] [ABCD 5 5 21] [CDAB 15 14 23] [ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28] [ABCD 13 5 29 ] [DABC 2 9 30] [BCDA 12 20 32] / * ROUND 3. * / / * let [ABCD KST] DENOTE The Operation A = B ((A H (B, C, d) x [k] T [I]) <<< s). * / / * do the folload 16 Operations. * / [Abcd 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 37] [CDAB 7 16 39] [BCDA 10 23 40] [ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44] [DABC 12 11 45] [BCDA 2 23 48] / * ROUND 4. * / / * let [ABCD KST] DENOTE THE OPERATION A = B ( (A I (B, C, D) X [K] T [I]) <<<
s). * / / * do the folload 16 Operations. * / [Abcd 0 6 49] [CDAB 14 15 51] [BCDA 5 21 52] [ABCD 12 6 53] [DABC 3 10 54 [CDAB 10 15 55] [ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60] [ABCD 4 6 61] [DABC 11 10 62] [ CDAB 2 15 63] / * Then Perform The Following Additions. (That INCREMENT EACH OF THE FOUR Registers by The Value It Had Before This Block Was Started.) * / A = A AA B = B BB C = C CC D = D DD END / * OF LOOP ON i * / RIVEST [Page 5] RFC 1321 MD5 Message-Digest Algorithm April 1992 3.5 Step 5. Output The Message Digest Produced As Output IS A, B , C, D. That IS, We Begin with the low-order byte of a, and end with the high-order byte of d. this Completes the Description of MD5. A Reference Implementation IN C is Given in The Appendix. 4. S UMMARY THE MD5 Message-Digest Algorithm IS Simple To Implement, And Provides A "FingerPrint"
or message digest of a message of arbitrary length. It is conjectured that the difficulty of coming up with two messages having the same message digest is on the order of 2 ^ 64 operations, and that the difficulty of coming up with any message having a given message digest is on the order of 2 ^ 128 operations. The MD5 algorithm has been carefully scrutinized for weaknesses. It is, however, a relatively new algorithm and further security analysis is of course justified, as is the case with any new proposal of this . sort 5. Differences Between MD4 and MD5 The following are the differences between MD4 and MD5: 1. A fourth round has been added 2. Each step now has a unique additive constant 3. The function g in round 2 was changed from.. (XZ V xz V yz) TO (XZ V y NOT (z)) to make g less symmetric. 4. Each Step Now add. This Promotes A Faster "Avalanche Effect". 5. THE ORDER in which input words are accessed in rounds 2 and 3 is changed, to make these patterns less like each other. 6. The shift amounts in each round have been approximately optimized, to yield a faster "avalanche effect." The shifts in different rounds are distinct RFC 1321 MD5 Message-Digest Algorithm April 1992 References [1] Rivest, R., "THE MD4 Message Digest Algorithm", RFC 1320, Mit And RSA Data Security, Inc., April 1992. [2] Rivest, R., "THE MD4 Message Digest Algorithm", In Aj Menezes and Sa Vanstone, Editors, Advances In Cryptology - Crypto '
90 Proceedings, pages 303-311, Springer-Verlag, 1991. [3] CCITT Recommendation X.509 (1988), "The Directory - Authentication Framework." APPENDIX A - Reference Implementation This appendix contains the following files taken from RSAREF: A Cryptographic Toolkit for Privacy-enhanced Mail: Global.h - Global Header File Md5.h - Header File for MD5 MD5C.C - Source Code for Md5 for more information on rsaref, send email to
/ * UINT2 defines a two byte word * / typedef unsigned short int UINT2; / * UINT4 defines a four byte word * / typedef unsigned long int UINT4; / * PROTO_LIST is defined depending on how PROTOTYPES is defined above.If using PROTOTYPES, then Proto_list returns the list, Otherwise it Returns an Empty list. * / # If prototypes # define proto_list (list) list # else # define proto_list (list) #ENDIF A.2 MD5.H / * md5.h - Header file for MD5C.C * / / * Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. Allrights reserved. License to copy and use this software is granted provided that itis identified as the "RSA Data Security, Inc. MD5 Message-digestAlgorithm "in all material mentioning or referencing this softwareor this function. License is also granted to make and use derivative works providedthat such works are identified as" derived from the RSA DataSecurity, Inc. MD5 Message-Digest Algorithm "in all materialmentioning Or Referencing The Derived Work. Rsa Data Security, Inc. makes no representat ions concerning eitherthe merchantability of this software or the suitability of thissoftware for any particular purpose. It is provided "as is" without express or implied warranty of any kind. Rivest [Page 8] RFC 1321 MD5 Message-Digest Algorithm April 1992 These notices must Be retained in any copies of any part of thisdocumentation and / or software. * / / * md5 context. * / typef struct {uint4 state [4]; / * state (abcd) * / uint4 count [2]; / * Number Of Bits, MODULO 2 ^ 64 (LSB first) * / unsigned char buffer [64]; / * input buffer * /} MD5_CTX;
Void MD5init Proto_List ((MD5_CTX *)); Void Md5Update Proto_List ((MD5_CTX *, Unsigned Char *, Unsigned Int); Void Md5Final Proto_List (unsigned char [16], md5_ctx *)); A.3 MD5C.C / * MD5C.C - RSA Data Security, Inc., MD5 message-digest algorithm * / / * Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. Allrights reserved License to copy and use this software is granted. provided that itis identified as the "RSA Data Security, Inc. MD5 Message-digestAlgorithm" in all material mentioning or referencing this softwareor this function. License is also granted to make and use derivative works providedthat such works are identified as "derived from the RSA DataSecurity, Inc. MD5 Message-Digest Algorithm "in all materialmentioning or referencing the derived work. RSA Data Security, Inc. makes no representations concerning eitherthe merchantability of this software or the suitability of thissoftware for any particular purpose. It is provided" as is "WITHOUT EXPRESS or IMPLIED WARRANTY O FANY KIND. THESE NOTITETER, THESE COPIES OF ANY Part of thisDocumentation and / or softward. * / #include "global.h" #include "md5.h" / * constants for md5transform routine. * / Rivest [PAGE 9] RFC 1321 MD5 Message-Digest Algorithm April 1992 #define S11 7 # Define S12 12 # Define S13 17 # Define S14 22 # Define S21 5 # Define S22 9 # Define S23 14 # Define S24 20 # Define S31 4 # Define S32 11 # define s33 16 # Define s41 6 # define s42 10 # define s43 15 # define s44 21 static void md5transform proto_list ((uint4 [4), unsigned char [64])); static void encode proto_list ((( Unsigned char *, uint4 *, unsigned int);
static void Decode PROTO_LIST ((UINT4 *, unsigned char *, unsigned int)); static void MD5_memcpy PROTO_LIST ((POINTER, POINTER, unsigned int)); static void MD5_memset PROTO_LIST ((POINTER, int, unsigned int)); static unsigned Char Padding [64] = {0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; / * f, g, h and i are Basic MD5 functions. * / # define f (x, y, z) ((x) & (y)) | ((~ x) & (z))) # define g (x, y, z) ((x) & (z)) | ((Y) & (~ z))) # define h (x, y, z) ((x) ^ (y) ^ (z)) # define i (x, y, z) ( (y) ^ ((x) | (~ z))) / * Rotate_left rotates x left n bits. * / # define rotate_left (x, n) ((x) << (n)) | ((x) >> (32- (N))))))) / * ff, gg, hh, and ii transformations for rounds 1, 2, 3, and 4.Rotation is self "* / # define ff (A, B, C, D, X, AC) {/ (a) = f ((b), (c), (d)) (x) (UINT4) (AC); / (a) = Rotate_Left ((a), (s)) ; / Rivest [Page 10] RFC 1321 MD5 Message-Digest Algorithm April 1992 (a) = (b); /} #define GG (A, B, C, D, X, S, AC) {/ (a) = G ((b), (c), (d)) (x) (UINT4) (AC); / (a) = rotate_left ((a), (s)); / (a) = (b); /} #define HH (A, B, C, D, X, S, AC) {/ (a) = h ((b), (c), (d)) (x) (UINT4) (AC); / (a) = rotate_LEFT ((a), (s)); / (a) = (b); /} #define II (A, B, C, D, X, S , AC) {/ (a) = I ((b), (c), (d)) (x) (UINT4) (AC); / (a) = rotate_left ((a), (s) ); / (A) = (b);
/} / * Md5 initialization. Begins AN MD5 Operation, Writing a new context. * / Void md5init (context) md5_ctx * context; / * context * / {context-> count [0] = context-> count [1] = 0; / * / context-> state [0] = 0x67452301; context-> state [1] = 0xefcdab89; context-> state [2] = 0x98badcfe; context-> state [3] = 0x10325476 ;} / * MD5 block update operation Continues an MD5 message-digest operation, processing another message block, and updating the context * / void MD5Update (context, input, inputLen) MD5_CTX * context;.. / * context * / unsigned char * INPUT; / * INPUT block * / unsigned int inputlen; / * length of infut block * / {unsigned int I, index, partlen; / * compute number of bytes mod 64 * / index = (unsigned int) ((context-> Count [0] >> 3) & 0x3f); / * Update Number of Bits * / IF ((Context-> Count [0] = ((uint4) Inputlen << 3)) RIVE ST [Page 11] RFC 1321 MD5 Message-Digest Algorithm April 1992 <(uint4) Inputlen << 3)))) Context-> Count [1] ; context-> count [1] = ((uint4) inputlen> > 29); Partlen = 64 - INDEX; / * Transform as many Times as Possible. * / If (Inputlen> = Partle) {MD5_MEMCPY ((Pointer) & context-> buffer [index], (Pointer) Input, Partle; MD5Transform (Context-> State, Context-> Buffer); for (i = partlen; i 63
/ * Buffer remaining infut * / md5_memcpy ((Pointer) & context-> buffer [index], (pointer) & input [i], inputlen-i);} / * md5 finalization. Ends an md5 message-digest operation, Writing the the the the message digest and zeroizing the context * / void MD5Final (digest, context) unsigned char digest [16];. / * message digest * / MD5_CTX * context; / * context * / {unsigned char bits [8]; unsigned int index, Padlen; / * save number of bits * / encode (bits, context-> count, 8); / * Pad out to 56 mod 64. * / index = (unsigned int) ((context-> count [0] >> >> 3) & 0x3f); Padlen = (INDEX <56)? (56 - index): (120 - index); Md5Update (Context, Padding, Padlen); / * append length (before padding) * / md5Update (Context, BITS , 8); RiveSt [Page 12] RFC 1321 MD5 Message-Digest Algorithm April 1992 / * Store State in Digest * / Encode (Digest, Context-> State, 16); / * Zeroize S . Ensitive information * / MD5_memset ((POINTER) context, 0, sizeof (* context));..} / * MD5 basic transformation Transforms state based on block * / static void MD5Transform (state, block) UINT4 state [4]; Unsigned char block [64]; {uint4 a = state [0], b = state [1], c = state [2], d = state [3], x [16]; decode (x, block, 64) ; / * ROUND 1 * / ff (A, B, C, D, X [0], S11, 0xD76AA478); / * 1 * / ff (D, A, B, C, X [1], S12, 0xE8C7B756 ); / * 2 * / ff (C, D, A, B, X [2], S13, 0x242070dB); / * 3 * / ff (B, C, D, A, X [3], S14, 0XC1BDCEEE ); / * 4 * / ff (A, B, C, D, X [4], S11, 0xF57c0FAF); / * 5 * / ff (D, A, B, C, X [5], S12, 0X4787C62A ); / * 6 * / ff (C, D, A, B, X [6], S13, 0xA8304613);
/ * 7 * / ff (B, C, D, A, X [7], S14, 0xFD469501); / * 8 * / ff (A, B, C, D, X [8], S11, 0X698098D8); / * 9 * / ff (D, A, B, C, X [9], S12, 0x8B44F7AF); / * 10 * / ff (C, D, A, B, X [10], S13, 0xFFFF5BB1); / * 11 * / ff (B, C, D, A, X [11], S14, 0X895CD7BE); / * 12 * / ff (A, B, C, D, X [12], S11, 0x6b901122); / * 13 * / ff (D, A, B, C, X [13], S12, 0xFD987193); / * 14 * / ff (C, D, A, B, X [14], S13, 0XA679438E); / * 15 * / ff (B, C, D, A, X [15], S14, 0X49B40821); / * 16 * / / * ROUND 2 * / GG (A, B, C, D, X [1] , S21, 0xF61E2562); / * 17 * / gg (D, A, B, C, X [6], S22, 0XC040B340); / * 18 * / gg (C, D, A, B, X [11] , S23, 0x265E5A51); / * 19 * / gg (B, C, D, A, X [0], S24, 0XE9B6C7AA); / * 20 * / gg (A, B, C, D, X [5] S21, 0xD62F105D); / * 21 * / gg (D, A, B, C, X [10], S22, 0x2441453); / * 22 * / gg (C, D, A, B, X [15] , S23, 0xD8A1E681); / * 23 * / gg (B, C, D, A, X [4], S24, 0XE7D3FBC8); / * 24 * / gg (A, B, C, D, X [9] , S21, 0x21E1CDE6); / * 25 * / gg (D, A, B, C, X [14], S22, 0XC33707D6); / * 26 * / gg (C, D, A, B, X [3], S23, 0XF4D50D87); / * 27 * / Rivest [Page 13] RFC 1321 MD5 Message-Digest Algorithm April 1992 GG (B, C, D, A, X [8], S24, 0x455A14ED); / * 28 * / gg (A, B, C, D, X [13], S21, 0XA9E3E905); / * 29 * / gg (D, A, B, C, X [2], S22, 0xfcefa3f8); / * 30 * / gg (C, D, A, B, X [7], S23, 0x676F02D9); / * 31 * / gg (B, C, D, A, X [12], S24, 0x8D2A4C8A); / * 32 * / / * ROUND 3 * / HH (A, B, C, D, X [5], S31, 0xFFFA3942); / * 33 * / HH (D, A, B, C, X [8], S32, 0x8771F681); / * 34 * / HH (C, D, A, B, X [11], S33, 0X6D9D6122); / * 35 * / HH (B, C, D, A, X [14], S34, 0xFDE5380C); / * 36 * / HH (A, B, C, D, X [1], S31, 0XA4BEEA44);
/ * 37 * / hh (D, A, B, C, X [4], S32, 0X4BDECFA9); / * 38 * / HH (C, D, A, B, X [7], S33, 0xF6bb4b60); / * 39 * / hh (B, C, D, A, X [10], S34, 0XBEBFBC70); / * 40 * / hh (A, B, C, D, X [13], S31, 0X289B7EC6); / * 41 * / hh (D, A, B, C, X [0], S32, 0xEAA127FA); / * 42 * / hh (C, D, A, B, X [3], S33, 0xD4ef3085); / * 43 * / hh (B, C, D, A, X [6], S34, 0X4881D05); / * 44 * / hh (A, B, C, D, X [9], S31, 0XD9D4D039); / * 45 * / hh (D, A, B, C, X [12], S32, 0xE6DB99E5); / * 46 * / HH (C, D, A, B, X [15], S33, 0x1FA27CF8); / * 47 * / hh (B, C, D, A, X [2], S34, 0XC4AC5665); / * 48 * / / * ROUND 4 * / II (A, B, C, D, X [0] , S41, 0XF4292244); / * 49 * / II (D, A, B, C, X [7], S42, 0X432AFF97); / * 50 * / II (C, D, A, B, X [14] , S43, 0XAB9423A7); / * 51 * / II (B, C, D, A, X [5], S44, 0XFC93A039); / * 52 * / II (A, B, C, D, X [12] , S41, 0X655B59C3); / * 53 * / II (D, A, B, C, X [3], S42, 0x8F0CCC92); / * 54 * / II (C, D, A, B, X [10] , S43, 0xffeff47d); / * 55 * / II (B, C, D, A, X [1], S44, 0X85845DD1); / * 56 * / ii (a , B, C, D, X [8], S41, 0x6FA87E4F); / * 57 * / II (D, A, B, C, X [15], S42, 0XFE2CE6E0); / * 58 * / II (C , D, A, 0xA3014314); / * 59 * / II (B, C, D, A, X [13], S44, 0X4E0811A1); / * 60 * / II (A , B, C, D, X [4], S41, 0xF7537E82); / * 61 * / II (D, A, B, C, X [11], S42, 0XBD3AF235); / * 62 * / II (C , D, A, B, X [2], S43, 0X2AD7D2BB); / * 63 * / II (B, C, D, A, X [9], S44, 0XEB86D391); / * 64 * / state [0 ] = a; state [1] = b; state [2] = C; state [3] = D; / * Zeroize Sensitive Information. Rivest [Page 14] RFC 1321 MD5 Message-Digest Algorithm April 1992 * / MD5_MEMSET ((Pointer) x, 0, sizeof (x));
.} / * Encodes input (UINT4) into output (unsigned char) Assumes len is a multiple of 4. * / static void Encode (output, input, len) unsigned char * output; UINT4 * input; unsigned int len; {unsigned INT I, J; For (i = 0, j = 0; j } A.4 mddriver.c / * mddriver.c - test driver for MD2, MD4 and MD5 * / / / * Copyright (C) 1990-2, RSA Data Security, Inc. Created 1990. Allrights Reserved. RSA Data Security, Inc . makes no representations concerning eitherthe merchantability of this software or the suitability of thissoftware for any particular purpose. It is provided "as is" without express or implied warranty of any kind. These notices must be retained in any copies of any part of thisdocumentation and / / * The following makes md default to md5 if it has c compiler flags. * / # iFNDef MD # define md MD5 # endif #include 5 # define MD_CTX MD5_CTX # define MDInit MD5Init # define MDUpdate MD5Update # define MDFinal MD5Final # endif / * Main driver Arguments (may be any combination): -sstring - digests string -t - runs time trial -x - runs test script filename. - Digests File (None) - Digests Standard Input * / Int Main (Argc, Argv) Int Argc; Rivest [Page 17] RFC 1321 MD5 Message-Digest Algorithm April 1992 Char * Argv []; {INT I; IF (Argc> 1) for (i = 1; i / * Initialize Block * / for (i = 0; i Context); fclose (file); Printf ("MD% D (% s) =", MD, FileName); mdprint (Digest); Printf ("/ n");}} / * Digests the Standard Input and Prints THE Result. * / static void mdfilter () {md_ctx context; int Len; unsigned char buffer [16], Digest [16]; mdinit (& context); while (len = fread (buffer, 1, 16, stdin) MDUPDATE & context, Buffer, Len; Mdfinal (Digest, & Context); MDPrint (Digest); Printf ("/ n");} / * Prints a message digest in Hexadecimal. * / static void mdprint (Digest) unsigned char Digest [16 ]; {RiveSt [Page 20] RFC 1321 MD5 Message-Digest Algorithm April 1992 Unsigned Int i; for (i = 0; i <16; i ) Printf ("% 02x", Digest [i]);} A.5 Test suite The MD5 test suite (driver option "-x") should print the following results: MD5 test suite: MD5 ( "") = d41d8cd98f00b204e9800998ecf8427eMD5 ( "a") = 0cc175b9c0f1b6a831c399e269772661MD5 ( "abc") = 900150983cd24fb0d6963f7d28e17f72MD5 ( "message digest ") = F96b697d7cb7938d525a2f31aaf161d0MD5 (" abcdefghijklmnopqrstuvwxyz ") = c3fcd3d76192e4007dfb496cca67e13bMD5 (" ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789 ") = d174ab98d277d9f5a5611c2c9f419d9fMD5 (" 12345678901234567890123456789012345678901234567890123456789012345678901234567890 ") = 57edf4a22be3c955ac49da2e2107b67a Security Considerations The level of security discussed in this memo is considered to be sufficient for implementing very high security hybrid digital- signature schemes Based ON MD5 and a public-key cryptosystem. Author '
