Connected: An Internet Encyclopedia
RFC 1321 - 3.4 Step 4. Process Message in 16-Word Blocks

Top: Connected: An Internet Encyclopedia
Up: Requests For Comments
Up: RFC 1321
Up: 3. MD5 Algorithm Description
Prev: 3.3 Step 3. Initialize MD Buffer
Next: 3.5 Step 5. Output

### 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 not(X)Z will never have 1's in the same bit position.) It is interesting to note that if the bits of X, Y, and Z are independent and unbiased, the each bit of F(X,Y,Z) will be independent and unbiased.

The functions G, H, and I are similar to the function F, in that they act 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 are independent and unbiased, 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" or "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 are given in the appendix.

Do the following:

       /* 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

         CC = C
         DD = D

         /* Round 1. */
         /* Let [abcd k s i] denote the operation
              a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
         /* Do the following 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]  [BCDA  7 22  8]
         [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]  [BCDA 15 22 16]

         /* Round 2. */
         /* Let [abcd k s i] denote the operation
              a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
         /* Do the following 16 operations. */
         [ABCD  1  5 17]  [DABC  6  9 18]  [CDAB 11 14 19]  [BCDA  0 20 20]
         [ABCD  5  5 21]  [DABC 10  9 22]  [CDAB 15 14 23]  [BCDA  4 20 24]
         [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 14 31]  [BCDA 12 20 32]

         /* Round 3. */
         /* Let [abcd k s t] denote the operation
              a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
         /* Do the following 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]  [CDAB  7 16 39]  [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]  [CDAB 15 16 47]  [BCDA  2 23 48]

         /* Round 4. */
         /* Let [abcd k s t] denote the operation
              a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
         /* Do the following 16 operations. */
         [ABCD  0  6 49]  [DABC  7 10 50]  [CDAB 14 15 51]  [BCDA  5 21 52]
         [ABCD 12  6 53]  [DABC  3 10 54]  [CDAB 10 15 55]  [BCDA  1 21 56]
         [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]  [BCDA  9 21 64]

         /* Then perform the following additions. (That is 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 */

Next: 3.5 Step 5. Output

Connected: An Internet Encyclopedia
RFC 1321 - 3.4 Step 4. Process Message in 16-Word Blocks