MD5
MD5 (RFC 1321)
Terminology:
word: 32 bit quantitybyte: 8 bit quantity- \(X <<< 3\): circularly rotating \(X\) by 3 times
MD5 Algorithm
To find the md5 for a message \(m\) of \(b\)-bits, where \(m\) can be visualized as
\[m_0 \, m_1 \, \cdots \, m_{b-1}\]Step 1: Appending Padding Bits
The mesage is padded so that its length is congruent to \(448\), modulo \(512\). This means after padding the message length is 64 bits shy of being a multiple of 512. Formally:
\[m\_size \cong 448 \, (modulo \, 512)\]Padding: to pad the message to the desired length, a single 1 bit is appended followed by 0 bits. At lease 1 bit (length \(447 \% %512\)) or at most 512 bit (already \(448\)).
Step 2: Append length
A 64-bit representation of \(b\) (length of the message before padding) is appeneded to the result of step 2. If \(b > 2^64\), only the lower 64 bits of b are used.
At this point the message is a multiple of \(512\) and multple of \(16\) (32 bit) words.
Now let the following denote the words of the resulting message where \(N\) is a multiple of 16
\[M[0,\, \cdots \,,N-1]\]Step 3: Initialize MD Buffer
A buffer of four word (4 x 32 bit) \((A, B, C, D)\) is used to compute the MD5
\[word\, A:\, 01\, 23\, 45\, 67\] \[word\, B:\, 89\, ab\, cd\, ef\] \[word\, C:\, fe\, dc\, ba\, 98\] \[word\, D:\, 76\, 54\, 32\, 10\]Step 4: Process Message in 16-Word Blocks (512 bits)
For every 512 bits, peform a set of complex operations on the buffer. These complex operations are bit wise parallel (see Step 4. Processing in 16-Word Blocks) for more information.
Step 5: Output
The final MD5 is just the concat the buffer DCBA