Supongamos tener un mensaje de b bits a la entrada, y queremos obtener el extracto de salida. b es entero no negativo, puede o no der muzltiplo de 8 e incluse ser 0. Imaginamos los bits del mensaje como:
m0 m1 ... m(b-1)
Se realizan 5 pasos:
El mensaje se extiende (padding) hasta que su longitud es congruente con 448 bits (modulo 512). El padding se realiza así: se agrega un "1" y todos "0" hasta completar 448 bits, al menos se agrega 1 bit y a lo sumo 512.
La representación de b se abre y se modifica, dicha representacion es en 64 bits, si b ahora es mayor de 2^64 entonces sólo se usan los 32 bits de menor orden. El mensaje resultante tiene una longitud múltiplo de 512 bits. En forma equivalente también es múltiplo de 16 (32) bits.
Se usa un buffer de 4 words (A,B,C,D) para computar el extracto del mensaje. A, B, C y D son registros de 32 bits. Se inicializan así:
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10
Definimos primero 4 funciones auxiliares para que cada una tome como entrada 3 words de 32 bit y produzca 1 salida de 32 bit.
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))
En cada posicion F actua como condicional : Si X entonces Y de lo contrario Z. Si cada bit de X, Y y Z son independientes cada bit de F(X,Y,Z) ser n independientes Las funciones G, H, I son similares a la funcion F, act£an en paralelo formando sus propios bits de salida independientes a partir de X, Y y Z.
Este paso utiliza una tabla de 64 elementos T(1...64) construídos a partir de la función seno. Sea T(i), el mismo es igual a la parte entera de 4294967296 veces abs(sin(i)), donde i est en radianes.Se hace entonces lo siguiente:
/* 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. */
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 */
El extracto del mensaje producido como salida es A, B, C, D. Esto es, comenzamos con el Byte A de bajo orden y terminamos con el D que es el más significativo.
Esto completa la descripcion de MD5.