MD5 algorithm description
Author: rufi 2004.06.22
When I want to write a MD5 algorithm program, I found that there are some indifferent places in the language description of Chinese and English. Some details are unclear, or very puzzled. Finally, I have to take out the source of the C language to debug, which is very disadvantageous for understanding algorithms. So I summarized some points I have grown.
1. The full name of the origin MD5 is Message-Digest Algorithm 5 (Information - Summary Algorithm, in the 1990s by Mit Laboratory For Computer Science and RSA Data Security Inc's Ronald L. Rivest developed, developed by MD2, MD3 and MD4 .Http://www.ietf.org/rfc/rfc1321.txt is the most authoritative document, by Ronald L. Rivest submitted to IEFT in August 1992.
2. The role of the use MD5 is to generate information summary (Message-Digest), which is unique to this information, which can be used as a digital signature. The validity of the file is used to verify the file (if there is lost or damaged data), the encryption of the user password is calculated in the hash function.
3. Features an arbitrary length byte string to generate a 128-bit integer. Due to certain irreversible features of the algorithm, there is better security in the encryption application. And, the use of the MD5 algorithm does not require any copyright cost.
4. Explanation of uniqueness and irreversibility is not absolute, from theoretically analyzing is a multi-to-one relationship, but two different information have the same probability of the same summary. Inverse refers to the amount of computational volume and calculation time required from the output reverse input, and the method of using the poor Supreme Dictionary requires too much storage space.
5. Description of algorithm
The algorithm input is a byte string, each byte is 8 bit. The execution of the algorithm is divided into the following steps:
The first step, the reix: The MD5 algorithm is initiated to the input data, so that the length of the data to 64 is 56 for the length of the data. That is, the data is extended to the Len = K * 64 56 bytes, k is an integer. Adding method: make up one 1, then supplement 0 to satisfy the above requirements. Equipped with one 0x80 byte, the onette of the value is 0. The total number of bytes in this step is 0 ~ 63.
Step 2, Additional Data Length: Use a 64-bit integer to indicate the original length of the data (in bits), the 8 bytes of this number are added in the previous, and the high position is attached to the post. The data is behind. At this time, the total length of the data is filled: len = k * 64 56 8 = (k 1) * 64 bytes.
※ Note that 64-bit integer is the original length of input data rather than filled bytes, I am planted here.
In the third step, initialization MD5 parameters: there are four 32-bit integer variables (A, B, C, D) to calculate information summary, each variable is initialized into the following value, low words Festival is in front. Word A: 01 23 45 67 Word B: 89 AB CD EF Word C: FE DC BA 98 WORD D: 76 54 32 10 ※ Note the low byte in front of the Little Endian platform arrangement And when writing in the program, you must write: a = 0x67452301 b = 0xefcdab89 c = 0x98badcfe d = 0x10325476
The fourth step is to define four MD5 basic bitmap operation functions: x, y, z is 32-bit integers. F (x, y, z) = (x and y) OR (NOT (X) AND Z) g (x, y, z) = (x and z) or (Y AND NOT (Z)) h (x, Y, z) = x xor y xor z i (x, y, z) = y xor (x or not (z)) Reconfers the four functions that are used for four-wheel transform. Set the J2 of the message (from 0 to 15), <<< S represents the loop left shift S bit, then four operations are: FF (A, B, C, D, MJ, S, Ti) A = B ((A (F (B, C, D) MJ Ti) <<< S) Gg (A, B, C, D, MJ, S, Ti) represents A = B ((A (G) (B, C, D) MJ Ti) <<< S) HH (A, B, C, D, MJ, S, Ti) represents A = B ((A (H (B, C, D) MJ Ti) <<< S) II (A, B, C, D, MJ, S, Ti) Represents A = B ((A (i (B, C, D) MJ Ti) <<< )
In the fifth step, the input data is converted. Processing data, n is the total number of bytes, with 64 bytes as a group, each set of cycles, four-wheel operation per cycle. 64 bytes to be transformed with 16 32-bit integer array M [0 ... 15]. The array T [1 ... 64] represents a set of constants, T [I] is 4294967296 * ABS (SiN (i)) 32-bit integer portion, the unit of I is an arc, and the value of I is from 1 to 64. The specific process is as follows:
/ * Set the main loop variable * / for i = 0 to N / 16-1 DO
/ * Each cycle, store the document of 16 elements in the array x. * / For j = 0 to 15 doset x [j] to m [i * 16 j ]nd / end to J's loop
/ * Save A AA, B AS BB, C AS CC, And D As Dd. * / AA = ABB = BCC = CDD = D
/ * The first round * // * is indicated by [ABCD KSI] A = B ((A F (B, C, D) X [K] T [I]) <<<). * // * 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] [BCDA 11 22 12] [ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]
/ * The second round * * // * is indicated by [ABCD KSI] A = B ((A G (B, C, D) X [K] T [I]) <<< S) * // * do the folload 16 Operations. * / [Abcd 1 5 17] [CDAB 11 14 19] [BCDA 0 20 20] [ABCD 5 5 21] [DABC 10 9 22] [ 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] [CDAB 7 [BCDA 12 20 32] / * The third round * // * is shown in [Abcd KSI] A = B ((A H (B, C, D) X [K] T [K] T [ I]) <<< s). * // * do the folload 16 Operations. * / [Abcd 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36] [ABCD 1 4 37 [DABC 4 11 38] [BCDA 10 23 40] [ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44] [ABCD 9 4 45] [ DABC 12 11 46] [BCDA 2 23 48]
/ * The fourth round * // * is indicated by [ABCD KSI] A = B ((A I (B, C, D) X [K] T [I]) <<<). * // * 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 [BCDA 1 21 57] [DABC 15 10 59] [BCDA 13 21 60] [ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64]
/ * Then do the following: * / a = a aab = b bbc = C CCD = D DD
Next I / * ends the loop of i * /
The sixth step is output. A, B, C, D continuously store, a total of 16 bytes, 128 bits. Press hexadecimal to output this 16 bytes.
Finally, after implementing the algorithm with the program language, you can enter the following information to make a simple test for the program, 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 ( "12345678901234567890123456789012345678901234567890") = 57EDF4A22BE3C955AC49DA2E2107B67AMD5 algorithm C # program
The MD5 algorithm is more special, and it is best to write with assembly language. Many advanced language pairs are unable to power or low efficiency. For example, I started to prepare with Python and Euphoria and found that it is not easy. In contrast, C # is a comprehensive .NET language in the C class cluster, comparative comparison. After spending a night, I finally realized MD5 with C # first. Mainly due to some details of the algorithm, the result output is always wrong, debugging for a long time.
[code] // Source file: md5.cs // md5 alogrithm // by rufi 2004.6.20 http://rufi.yculblog.com/using system; using system.collections; using system.io;
Public class md5 {// static state variables private static uint32 a; private static uint32 b; private static uint32 c; private static uint32 d;
// Number of Bits To Rotate In TranForming Private const INT S11 = 7; Private const INT S12 = 12; Private const INT S13 = 17; private const INT S14 = 22; private const INT S21 = 5; private const INT S22 = 9 PRIVATE CONST INT S23 = 14; Private const INT S31 = 4; Private const INT S32 = 11; private const INT S33 = 16; private const INT S34 = 23; private const INT S41 = 6; Private const Int s42 = 10; private const INT S43 = 15; private const INT S44 = 21;
/ * F, g, h and i are Basic MD5 functions. * Four nonlinear functions: * * 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)) * * (&, | Or, ~ Non, ^ Doss or) * / Private Static uint32 f (uint32 x, uint32 y, uint32 z) {return (x & y) | (~ x) & z);} private static uint32 g (Uint32 x, uint32 y, uint32 z) {return (x & z) | (Y & (~ z));} private static uint32 h (uint32 x, uint32 y, uint32 z) {returnix x ^ y ^ z;} private stat UINT32 I (uint32 x, uint32 y, uint32 z) {RETURN Y ^ (x | (~ z));} / * ff, gg, hh, and ii transformations for rounds 1, 2, 3, and 4. * rotation IS Separate from addition to prevent recomputation. * / private static void ff (Ref uint32 a, uint32 b, uint32 c, uint32 d, uint32 mj, int S, uint32 Ti) {a = a f (b, c, d) MJ Ti; A = a << S | a >> (32-S); A = B;} Private Static Void GG (Ref uint32 a, uint32 b, uint32 c, uint32 d, uint32 MJ, INT S , Uint32 ti) {a = a g (b, c, d) mj Ti; a = a << s | a >> (32-s); A = B;} private static void hh Ref uint32 a, uint32 b, uint32 c, uint32 d, uint32 mj, int s, uint32 Ti) {a = a h (b, c, d) mj Ti; a = a << s | a >> (32-s); A = B;} Private Static Void II (Ref uint32 a, uint32 b, uint32 c, uint32 d, uint32 mj, int s, uint32 Ti) {a = a i (b, c, D) MJ Ti; a = a << S | a >> (32-S); A = B;}
private static void MD5_Init () {A = 0x67452301; // in memory, this is 0x01234567 B = 0xefcdab89; // in memory, this is 0x89abcdef C = 0x98badcfe; // in memory, this is 0xfedcba98 D = 0x10325476; // in MEMORY, THIS 0x76543210} private static uint32 [] md5_append (byte [] INPUT) {INT ZEROS = 0; int one = 1; int size = 0; int N = INPUT.LENGTH; INT m = N% 64; IF M <56) {zeros = 55-m; size = n-m 64;} else if (m == 56) {zeros = 0; ones = 0; size = n 8;} else {zeros = 63- M 56; size = n 64-m 64;}
ArrayList BS = New ArrayList (INPUT); if (ones == 1) {bs.add ((byte) 0x80); // 0x80 = $ 10000000} for (int i = 0; i UINT64 N = (UINT64) N * 8; Byte H1 = (Byte) (N & 0xFF); Byte H2 = (Byte) ((N >> 8) & 0xFF); Byte H3 = (Byte) ((N >> 16) & 0xFF ); Byte H4 = (byte) ((n >> 24) & 0xff); Byte H5 = (Byte) ((N >> 32) & 0xFF); Byte H6 = (Byte) ((N >> 40) & 0xFF); BYTE H7 = (BYTE) ((N >> 48) & 0xFF); Byte H8 = (Byte) (N >> 56); BS.Add (H1); BS.Add (H2); BS.Add (H3); Bs.Add (H5); BS.Add (h6); bs.add (h7); bsed (h8); byte [] ts = (byte []) BS.ToArray (Typeof (BYTE)); / * DECODES INPUT (byte []) INTO OUTPUT (uint32 []). Assumes Len is * a multiple of 4. * / uint32 [] Output = new uint32 [size / 4]; for (int64 i = 0, j = 0; i For (int K = 0; k / * ROUND 2 * / GG (REF A, B, C, D, X [K 1], S21, 0xF61E2562); / * 17 * / gg (Ref D, A, B, C, X [K 6], S22, 0XC040B340); / * 18 * / gg (REF C, D, A, B, X [K 11], S23, 0x265E5A51); / * 19 * / gg (Ref B, C, D, A, X [K 0], S24, 0xE9B6C7AA); / * 20 * / gg (Ref A, B, C, D, X [K 5], S21, 0XD62F105D); / * 21 * / gg (REF D, A, B , C, X [K 10], S22, 0X2441453); / * 22 * / gg (REF C, D, A, B, X [K 15], S23, 0xD8A1E681); / * 23 * / gg ( REF B, C, D, A, X [K 4], S24, 0xE7D3FBC8); / * 24 * / gg (Ref A, B, C, D, X [K 9], S21, 0x21E1CDE6); / * 25 * / Gg (Ref D, A, B, C, X [K 14], S22, 0XC33707D6); / * 26 * / gg (Ref C, D, A, B, X [K 3], S23, 0xF4D50D87 ); / * 27 * / gg (REF B, C, D, A, X [K 8], S24, 0x455A14ED); / * 28 * / gg (Ref A, B, C, D, X [K 13 ], S21, 0XA9E3E905); / * 29 * / gg (Ref D, A, B, C, X [K 2], S22, 0xFCEFA3F8); / * 30 * / gg (Ref C, D, A, B, X [K 7], S23, 0X676F02D9); / * 31 * / gg (Ref B, C, D, A, X [K 12], S24, 0x8D2A4C8A); / * 32 * / / * ROUND 3 * / HH (REF A, B, C, D, X [K 5], S31, 0xFFFFA3942); / * 33 * / HH (Ref D, A, B, C, X [K 8], S32, 0x8771F681); / * 34 * / hh (Ref C, D, A, B, X [K 11], S33, 0x6D9D6122); / * 35 * / HH (Ref B, C, D, A, X [K 14], S34, 0xFDE5380C); / * 36 * / HH (Ref A, B, C, D, X [K 1], S31, 0xA4Beea44); / * 37 * / HH (Ref D, A, B, C, X [K 4], S32, 0X4BDECFA9); / * 38 * / HH (REF C, D, A, B, X [K 7], S33, 0xF6BB4B60); / * 39 * / hh (Ref B, C, D, A, X [K 10], S34, 0XBEBFBC70); / * 40 * / HH (REF A, B, C, D, X [K 13], S31, 0x289B7EC6); / * 41 * / hh (Ref D, A, B, C, X [K 0], S32, 0xEAA127FA); / * 42 * / HH (Ref C, D, A, B, X [K 3], S33, 0xD4ef3085 ); / * 43 * / hh (Ref B, C, D, A, X [K 6], S34, 0x4881D05); / * 44 * / HH (Ref A, B, C, D, X [K 9] , S31, 0XD9D4D039); / * 45 * / HH (Ref D, A, B, C, X [K 12], S32, 0xE6DB99E5); / * 46 * / HH (Ref C, D, A, B, X [K 15], S33, 0X1FA27CF8); / * 47 * / HH (Ref B, C, D, A, X [K 2], S34, 0xC4AC5665); / * 48 * / / * ROUND 4 * / II (REF A, B, C, D, X [K 0], S41, 0xF4292244); / * 49 * / II (Ref D, A, B, C, X [K 7], S42, 0x432AFF97); / * 50 * / ii (Ref C, D, A, B, X [K 14], S43, 0XAB9423A7); / * 51 * / II (Ref B, C, D, A, X [K 5], S44, 0xFC93A039); / * 52 * / II (Ref A, B, C, D, X [K 12], S41, 0X655B59C3); / * 53 * / II (Ref D, A, B, C, X [K 3], S42, 0x8F0CCC92); / * 54 * / II (Ref C, D, A, B, X [K 10], S43, 0xffeff47d); / * 55 * / ii ( REF B, C, D, A, X [K 1], S44, 0X85845DD1); / * 56 * / II (Ref A, B, C, D, X [K 8], S41, 0x6FA87E4F); / * 57 * / Ii (Ref D, A, B, C, X [K 15], S42, 0XFE2CE6E0); / * 58 * / II (Ref C, D, A, B, X [K 6], S43, 0XA3014314 ); / * 59 * / ii (REF B, C, D, A, X [K 13], S44, 0X4E0811A1); / * 60 * / II (Ref A, B, C, D, X [K 4 ], S41, 0xF7537E82); / * 61 * / ii (Ref D, A, B, C, X [K 11], S42, 0XBD3AF235); / * 62 * / II (Ref C, D, A, B , X [K 2], S43, 0X2AD7D2BB); / * 63 * / II (Ref B, C, D, A, X [K 9], S44, 0XEB86D391); / * 64 * / a = a; B = B; C = C; D = D;} return new uint32 [] {a, b, c, d};} public static Byte [] md5aaRray (byte [] infut) {md5_init (); uint32 [] block = MD5_APPEND (INPUT); uint32 [] bits = md5_trasform (block); / * Encodes bits (uint32 []) INTO OUTPUT (byte []). Assumes Len is * a multiple of 4. * / byte [] Output = new byte [bits.length * 4]; for (int i = 0, J = 0; i Public static string mdstring (string message) {char [] c = message.tochararray (); byte [] b = new byte [C.Length]; for (int i = 0; i
