3. MD5 Algorithm Description (Descrizione dell'algoritmo MD5)
Iniziamo supponendo di avere un messaggio di b bit come input e di voler trovare il suo message digest. Qui b è un intero non negativo arbitrario; b può essere zero, non deve essere un multiplo di otto e può essere arbitrariamente grande. Immaginiamo i bit del messaggio scritti come segue:
m_0 m_1 ... m_{b-1}
I seguenti cinque passi vengono eseguiti per calcolare il message digest del messaggio.
3.1 Step 1. Append Padding Bits (Passo 1. Aggiungere bit di riempimento)
Il messaggio viene « riempito » (esteso) in modo che la sua lunghezza (in bit) sia congrua a 448, modulo 512. Cioè, il messaggio viene esteso in modo che sia esattamente 64 bit in meno di essere un multiplo di 512 bit di lunghezza. Il riempimento viene sempre eseguito, anche se la lunghezza del messaggio è già congrua a 448, modulo 512.
Il riempimento viene eseguito come segue: un singolo bit « 1 » viene aggiunto al messaggio, e quindi vengono aggiunti bit « 0 » in modo che la lunghezza in bit del messaggio riempito diventi congrua a 448, modulo 512. In totale, vengono aggiunti almeno un bit e al massimo 512 bit.
3.2 Step 2. Append Length (Passo 2. Aggiungere la lunghezza)
Una rappresentazione a 64 bit di b (la lunghezza del messaggio prima dell'aggiunta dei bit di riempimento) viene aggiunta al risultato del passo precedente. Nel caso improbabile che b sia maggiore di 2^64, vengono utilizzati solo i 64 bit meno significativi di b. (Questi bit vengono aggiunti come due parole a 32 bit e la parola meno significativa viene aggiunta per prima in conformità con le convenzioni precedenti.)
A questo punto, il messaggio risultante (dopo il riempimento con bit e con b) ha una lunghezza che è un multiplo esatto di 512 bit. Equivalentemente, questo messaggio ha una lunghezza che è un multiplo esatto di 16 parole (a 32 bit). Sia M[0 ... N-1] che denota le parole del messaggio risultante, dove N è un multiplo di 16.
3.3 Step 3. Initialize MD Buffer (Passo 3. Inizializzare il buffer MD)
Un buffer di quattro parole (A, B, C, D) viene utilizzato per calcolare il message digest. Qui ciascuno di A, B, C, D è un registro a 32 bit. Questi registri vengono inizializzati ai seguenti valori in esadecimale (byte meno significativo per primo):
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10
3.4 Step 4. Process Message in 16-Word Blocks (Passo 4. Elaborare il messaggio in blocchi di 16 parole)
Definiamo prima quattro funzioni ausiliarie che ciascuna prende come input tre parole a 32 bit e produce come output una parola a 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))
In ogni posizione di bit, F agisce come condizionale: se X allora Y altrimenti Z. La funzione F avrebbe potuto essere definita usando + invece di v poiché XY e not(X)Z non avranno mai 1 nella stessa posizione di bit. È interessante notare che se i bit di X, Y e Z sono indipendenti e non distorti, ogni bit di F(X,Y,Z) sarà indipendente e non distorto.
Le funzioni G, H e I sono simili alla funzione F, in quanto agiscono in « parallelo bit a bit » per produrre il loro output dai bit di X, Y e Z, in modo tale che se i bit corrispondenti di X, Y e Z sono indipendenti e non distorti, allora ogni bit di G(X,Y,Z), H(X,Y,Z) e I(X,Y,Z) sarà indipendente e non distorto. Si noti che la funzione H è la funzione « xor » o « parità » bit a bit dei suoi input.
Questo passo utilizza una tabella di 64 elementi T[1 ... 64] costruita dalla funzione seno. Sia T[i] che denota l'i-esimo elemento della tabella, che è uguale alla parte intera di 4294967296 volte abs(sin(i)), dove i è in radianti. Gli elementi della tabella sono forniti nell'appendice.
Eseguire quanto segue:
/* Elaborare ogni blocco di 16 parole. */
For i = 0 to N/16-1 do
/* Copiare il blocco i in X. */
For j = 0 to 15 do
Set X[j] to M[i*16+j].
end /* of loop on j */
/* Salvare A come AA, B come BB, C come CC e D come DD. */
AA = A
BB = B
CC = C
DD = D
/* Round 1. */
/* Sia [abcd k s i] che denota l'operazione
a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
/* Eseguire le seguenti 16 operazioni. */
[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. */
/* Sia [abcd k s i] che denota l'operazione
a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
/* Eseguire le seguenti 16 operazioni. */
[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. */
/* Sia [abcd k s t] che denota l'operazione
a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
/* Eseguire le seguenti 16 operazioni. */
[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. */
/* Sia [abcd k s t] che denota l'operazione
a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
/* Eseguire le seguenti 16 operazioni. */
[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]
/* Quindi eseguire le seguenti addizioni. (Cioè incrementare ciascuno
dei quattro registri del valore che aveva prima dell'inizio di questo
blocco.) */
A = A + AA
B = B + BB
C = C + CC
D = D + DD
end /* of loop on i */
3.5 Step 5. Output (Passo 5. Output)
Il message digest prodotto come output è A, B, C, D. Cioè, iniziamo con il byte meno significativo di A e terminiamo con il byte più significativo di D.
Questo completa la descrizione di MD5. Un'implementazione di riferimento in C è fornita nell'appendice.