Algorithm Description
A brief description of the MD5 algorithm may be: MD5 is grouped with 512-bit grouping 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 bits. The packet consists, and the four 32-bit grouping level will generate a 128-bit scatter value.
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 right, ^ is different or)
Description of these four functions: If the corresponding position of X, Y and Z is independent and uniform, 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 J20 packet (from 0 to 15), <<
FF (A, B, C, D, MJ, S, Ti) represents A = B ((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) represents 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: first round
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, 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, 0xFFFF5BB1)
FF (B, C, D, A, M11, 22, 0X895CD7BE)
FF (A, B, C, D, M12, 7, 0x6b901122)
FF (D, A, B, C, M13, 12, 0xFD987193)
FF (C, D, A, B, M14, 17, 0XA679438E)
FF (B, C, D, A, M15, 22, 0X49B40821)
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, B, M15, 14, 0XD8A1E681)
GG (B, C, D, A, M4, 20, 0XE7D3FBC8)
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, A, M12, 20, 0X8D2A4C8A)
Third round
HH (A, B, C, D, M5, 4, 0xFFFA3942)
HH (D, A, B, C, M8, 11, 0X8771F681)
HH (C, D, A, 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, 0X4BDECFA9)
HH (C, D, A, B, M7, 16, 0XF6BB4B60)
HH (B, C, D, A, M10, 23, 0XBEBFBC70)
HH (A, B, C, D, M13, 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, A, M2, 23, 0XC4AC5665)
Fourth round
II (A, B, C, D, M0, 6, 0xF4292244)
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, 0x65559c3)
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, 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, 0XBD3AF235)
II (C, D, A, B, M2, 15, 0X2AD7D2BB)
II (B, C, D, A, M9, 21, 0XEB86D391)
The constant TI can choose from:
In the first step, Ti is 4294967296 * ABS (SiN (i)) integer part, and the unit of I is an arc. (4294967296 equal to 2) 32 times)
After all of these completed, A, B, C, and D were added to A, B, C, D, respectively. 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 ("123456789012345678901234567890123456789012345678901234567890123456789
01234567890 ") = 57EDF4A22BE3C955AC49DA2E2107B67A
If you use the information on the above information to test the MD5 algorithm instance, finally, the conclusions and standard answers are exactly the same, then I will have a congratulations here. To know, my program is not derived from the same result when the first compilation is successful.
MD5 security
Improvements made by MD5 relative to MD4:
1. Added the fourth round;
2. Each step has a unique addition constant;
3. To reduce the symmetry of function G in the second round from (X & Y) | (Y & Z) to (Y & Z) | (Y & (~ Z));
4. The first step plus the result of the previous step, which will cause faster avalanche effects;
5. Change the order of accessing the message sub-packet in the second round and third rounds, making it more different;
6. Approximately optimize the loop left shift transmissions in each round to achieve a faster avalanche effect. The displacement amount of each wheel is different.
