After some initialization processing, the MD5 processes the input text in a 512-bit packet, and each group is divided into 16 32-bit sub-packets. The output of the algorithm consists of four 32-bit packets, and sets them to form a 128-bit scatter value.
First fill the message, so that the length is just a number of small 64 digits than the 512-bit multiple. The filling method is to attach one 1 after the message, the rear required multiple 0, and then attached thereafter with a 64-bit message length (before filling). These two steps are to make the message length exactly a 512-bit integer multiple (as required for the rest of the algorithm), and ensure that different messages are different after the fill is different.
Four 32-bit variables are initialized to:
A = 0x01234567
B = 0x89abcdef
C = 0xfedcba98
D = 0x76543210
They are called chaining variables (CHAINING VARIABLE)
Then the algorithm's primary cycle, the number of cycles is the number of 512-bit message packets in the message.
Copy the above four variables to the other variables: A to A, B to B, C to C, D to D.
The main cycle has four rounds (MD4 only three rounds), each round is very different. 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)
These functions are designed: if the corresponding position of X, Y, and Z is independent and uniform, each bit of the result should also be independent and uniform.
The function f is in one way mode: if x, then y, otherwise Z. The function h is a bitmap parity.
Set the J2 of the message (from 0 to 15) 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) represents 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) <<< S)
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. (2 of 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.
