MD5

Introduzione

Con il termine messaggio si indica una sequenza di bit utilizzata come input per l'algoritmo, come ad esempio il contenuto di un file oppure una stringa di caratteri. La prima operazione effettuata dall'algoritmo è il padding del messaggio. Esso consiste nel aggiungere dei dati alla fine del messaggio in modo che la sua lunghezza, ovvero il numero dei bit, sia un multiplo di 512 (equivalentemente il numero dei byte sia un multiplo di 64).
Il valore finale dell'algoritmo è contenuto in 4 word A, B, C, D (128 bit) che vengono modificate da alcune funzioni ed operazioni. Ogni blocco da 512 bit viene convertito in una sequenza di 16 word ed elaborato indipendentemente.
Padding

Sia l il numero dei bit di cui è composto il messaggio originale. Il padding viene effettuato in due parti: prima viene inserita una sequenza di bit del tipo: {10000 … 0} composta da un bit "1" seguito da un certo numero di bit "0" e dopo viene inserito il valore binario della lunghezza originale l del messaggio. Quest'ultimo valore viene espresso da un numero binario a 64 bit (Nel caso il messaggio sia più lungo di 264 bit, allora verrà usato il valore della lunghezza formato dai 64 bit meno significativi).
La sequenza di padding (che comprende la stringa di bit e il valore della lunghezza originale) deve rendere il messaggio completo con un lunghezza multipla di 512 bit. Essendo la parte del padding dedicata al valore della lunghezza originale di 64 bit, allora la stringa di bit deve essere tale che la lunghezza del messaggio sia 64 bit inferiore ad un multiplo di 512. In altre parole la lunghezza modulo 512 dovrà essere uguale a 448 (512-64).
L'algoritmo prevede che venga sempre aggiunto il bit "1" seguito da un numero di bit "0" che varia da 0 a 511.

Esempio

Sia l = 890 bit; il prossimo multiplo di 512 è 1024 bit, quindi il numero di bit di padding totale aggiunti al messaggio saranno 1024-890 = 134 bit. Per il valore della lunghezza devono essere utilizzati gli ultimi 64 bit, quindi la stringa di bit dovrà avere una lunghezza di 70 bit, di cui il primo bit avrà valore "1" mentre gli altri 69 avranno il valore "0".
Il messaggio così elaborato sarà composto da 890 bit dei dati originali, un bit "1", 69 bit "0", e 64 bit che contengono il valore binario della lunghezza originale (ovvero il valore 890).
Si può calcolare la lunghezza della stringa con l'operazione modulo: infatti si ha: 890 modulo 512 = 378. Dovendo essere pari a 448 allora si dovranno aggiungere 448-378 = 70 bit.

Esempio

Sia l = 448 bit; si aggiunge il bit "1" portandolo a 449 bit. Allora rimangono 512 - 449 = 63 bit per la lunghezza che non sono sufficienti: si deve utilizzare il multiplo di 512 superiore, ovvero 1024 bit. Vengono quindi aggiunti 511 bit "0" in modo da arrivare alla lunghezza di 960 bit a cui verranno aggiunti i 64 bit finali relativi alla lunghezza.

Esempio

Sia l = 959 bit; si aggiunge il bit "1" portandolo a 960 bit. A questo punto si ha che 960 mod 512 = 448 bit. In questo caso non si aggiungono bit "0" perchè è stato già raggiunto il valore desiderato. Si aggiungono i 64 bit finali relativi alla lunghezza.
Conversione in word

Il flusso di bit viene convertito in word da 32 bit in questo modo:
Una sequenza di 8 bit viene interpretata come un byte, in ordine big endian, ovvero con il primo bit della sequenza considerato il più significativo, quindi nel byte: b0 b1 b2 b3 b4 b5 b6 b7, il bit b0 è quello più significativo e b7 è quello meno significativo.
Un gruppo di 4 byte viene convertito in word da 32 bit in ordine little endian, ovvero il primo byte considerato il meno significativo: dati 4 byte B0 B1 B2 B3, il byte B0è il meno significativo e B3 il più significativo.

Funzioni e operazioni

Addizione

Le addizioni nell'algoritmo non causano overflow: il risultato viene troncato a 32 bit. Quindi se a = 0xF351284C e b = 0xD58AB106 la loro somma non sarà 0x1C8DBD952 ma invece 0xC8DBD952.

Rotazione a sinistra

La rotazione a sinistra ciclica di una word a 32 bit di n bit comporta lo spostamento a sinistra di n bit. I bit che "uscirebbero" dalla parte sinistra vengono inseriti nella parte destra in questo modo:

(1)
\begin{equation} b_0 b_1 b_2 b_3 b_4 b_5 b_6 b_7 b_8 b_9 b_{10} b_{11} b_{12} b_{13} b_{14} b_{15} b_{16} b_{17} b_{18} b_{19} b_{20} b_{21} b_{22} b_{23} b_{24} b_{25} b_{26} b_{27} b_{28} b_{29} b_{30} b_{31} \end{equation}

Lo spostamento a sinistra di 10 bit genera questo risultato:

(2)
\begin{equation} b_{10} b_{11} b_{12} b_{13} b_{14} b_{15} b_{16} b_{17} b_{18} b_{19} b_{20} b_{21} b_{22} b_{23} b_{24} b_{25} b_{26} b_{27} b_{28} b_{29} b_{30} b_{31} 0000000000 \end{equation}

Le posizioni dei bit a destra che restano vuote vengono riempite con dei bit di valore "0". I bit da 0 a 9 sono stati "persi".
La rotazione, o spostamento ciclico, prevede che i bit da 0 a 9 vengano inseriti a destra al posto degli 0 così:

(3)
\begin{equation} b_{10} b_{11} b_{12} b_{13} b_{14} b_{15} b_{16} b_{17} b_{18} b_{19} b_{20} b_{21} b_{22} b_{23} b_{24} b_{25} b_{26} b_{27} b_{28} b_{29} b_{30} b_{31} b_0 b_1 b_2 b_3 b_4 b_5 b_6 b_7 b_8 b_9 \end{equation}

La rotazione può essere effettuata velocemente unendo tramite una operazione di or i bit ottenuti da uno spostamento a sinistra di n bit e da quelli ottenuti da uno spostamento a destra di 32 - n bit:
Spostamento a sinistra di 10 bit

(4)
\begin{equation} b_{10} b_{11} b_{12} b_{13} b_{14} b_{15} b_{16} b_{17} b_{18} b_{19} b_{20} b_{21} b_{22} b_{23} b_{24} b_{25} b_{26} b_{27} b_{28} b_{29} b_{30} b_{31} 0000000000 \end{equation}

Spostamento a destra di 32 - 10 = 22 bit

(5)
\begin{equation} 0000000000000000000000 b_0 b_1 b_2 b_3 b_4 b_5 b_6 b_7 b_8 b_9 \end{equation}

Funzioni

Si definiscono le seguenti funzioni:

  • F(X, Y, Z) = (X and Y) or (not(X) and Z)
  • G(X, Y, Z) = (X and Z) or (Y and not(Z))
  • H(X, Y, Z) = X xor Y xor Z
  • I(X, Y, Z) = Y xor (X or not(Z))

Esempio

se
X = 0xC4B68E8A { 11000100101101101000111010001010 }
Y = 0x824F31BB { 10000010010011110011000110111011 }
Z = 0x17C310BE { 00010111110000110001000010111110 }
allora la funzione F(X, Y, Z) può essere calcolata così:

11000100101101101000111010001010 and
10000010010011110011000110111011 =
----------------------------------
10000000000001100000000010001010 = 0x8006008A

00111011010010010111000101110101 and
00010111110000110001000010111110 =
----------------------------------
00010011010000010001000000110100 = 0x13411034

10000000000001100000000010001010 or
00010011010000010001000000110100 =
----------------------------------
10010011010001110001000010111110 = 0x934710BE

Quindi F(X, Y, Z) = 0x934710BE

Tabella T

L'algoritmo utilizza una tabella di 64 word costanti, chiamata tabella T, generate in questo modo:
il valore i-esimo della tabella è calcolato come la parte intera del prodotto tra 232 e il valore assoluto di sin(i+1), con i espresso in radianti e compreso tra 1 e 64.

(6)
\begin{align} T[i] = \lfloor 2^{32} abs( \sin(i+1)) \rfloor \end{align}
ciclo valore ciclo valore ciclo valore ciclo valore
1 0xd76aa478 17 0xf61e2562 33 0xfffa3942 49 0xf4292244
2 0xe8c7b756 18 0xc040b340 34 0x8771f681 50 0x432aff97
3 0x242070db 19 0x265e5a51 35 0x6d9d6122 51 0xab9423a7
4 0xc1bdceee 20 0xe9b6c7aa 36 0xfde5380c 52 0xfc93a039
5 0xf57c0faf 21 0xd62f105d 37 0xa4beea44 53 0x655b59c3
6 0x4787c62a 22 0x02441453 38 0x4bdecfa9 54 0x8f0ccc92
7 0xa8304613 23 0xd8a1e681 39 0xf6bb4b60 55 0xffeff47d
8 0xfd469501 24 0xe7d3fbc8 40 0xbebfbc70 56 0x85845dd1
9 0x698098d8 25 0x21e1cde6 41 0x289b7ec6 57 0x6fa87e4f
10 0x8b44f7af 26 0xc33707d6 42 0xeaa127fa 58 0xfe2ce6e0
11 0xffff5bb1 27 0xf4d50d87 43 0xd4ef3085 59 0xa3014314
12 0x895cd7be 28 0x455a14ed 44 0x04881d05 60 0x4e0811a1
13 0x6b901122 29 0xa9e3e905 45 0xd9d4d039 61 0xf7537e82
14 0xfd987193 30 0xfcefa3f8 46 0xe6db99e5 62 0xbd3af235
15 0xa679438e 31 0x676f02d9 47 0x1fa27cf8 63 0x2ad7d2bb
16 0x49b40821 32 0x8d2a4c8a 48 0xc4ac5665 64 0xeb86d391

Esempio

Considerando i = 24, allora si ha:
sin(24) = -0.905578362 il cui valore assoluto è 0.905578362
$2^{32} 0.905578362 = 3889429448.755249152$ la cui parte intera è 3889429448, in esadecimale corrisponde a 0xe7d3fbc8.

Tabella M

La tabella M individua, per un certo ciclo i, la word del blocco da elaborare. Essendo il blocco da 512 bit ci saranno 16 word, indicizzate da 0 a 15. La word corrispondente ad un certo ciclo i viene generata dalle formule seguenti:
per 0<i<15 word = i
per 16<i<31 word = (1 + 5*(i-1)) mod 16
per 32<i<47 word = (5 + 3*(i-1)) mod 16
per 48<i<63 word = 7*(i-1) mod 16
Ad esempio nel ciclo 46 si usa la word (5 + 3*45) mod 16 = 140 mod 16 = 12

ciclo word ciclo word ciclo word ciclo word
1 0 17 1 33 5 49 0
2 1 18 6 34 8 50 7
3 2 19 11 35 11 51 14
4 3 20 0 36 14 52 5
5 4 21 5 37 1 53 12
6 5 22 10 38 4 54 3
7 6 23 15 39 7 55 10
8 7 24 4 40 10 56 1
9 8 25 9 41 13 57 8
10 9 26 14 42 0 58 15
11 10 27 3 43 3 59 6
12 11 28 8 44 6 60 13
13 12 29 13 45 9 61 4
14 13 30 2 46 12 62 11
15 14 31 7 47 15 63 2
16 15 32 12 48 2 64 9

Tabella S

La tabella S indica il numero di bit da ruotare a sinistra ciclicamente. Ad esempio nel ciclo 33 la rotazione sarà di 4 bit.

ciclo bit ciclo bit ciclo bit ciclo bit
1 7 17 5 33 4 49 6
2 12 18 9 34 11 50 10
3 17 19 14 35 16 51 15
4 22 20 20 36 23 52 21
5 7 21 5 37 4 53 6
6 12 22 9 38 11 54 10
7 17 23 14 39 16 55 15
8 22 24 20 40 23 56 21
9 7 25 5 41 4 57 6
10 12 26 9 42 11 58 10
11 17 27 14 43 16 59 15
12 22 28 20 44 23 60 21
13 7 29 5 45 4 61 6
14 12 30 9 46 11 62 10
15 17 31 14 47 16 63 15
16 22 32 20 48 23 64 21

Algoritmo md5

Elaborazione

Si inizializzano le 4 word a, b, c, d con i seguenti valori:

  • a = 0x67452301
  • b = 0xefcdab89
  • c = 0x98badcfe
  • d = 0x10325476

Per ogni blocco da 16 word si copia il valore dei valori a, b, c, d in valori temporanei aa, bb, cc, dd e si utilizza una valore temporaneo aggiuntivo chiamato temp.
L'elaborazione di un blocco avviene attraverso 64 cicli di operazioni. Ogni ciclo consiste delle seguenti operazioni:

  • temp assume il valore di una delle 4 funzioni a cui vengono forniti i valori di b, c, d. Nei primi 16 cicli viene usata la funzione F, dal 17 al 32 la funzione G, dal 33 al 48 la funzione H e dal 49 al 64 la funzione I.
  • al valore di temp viene aggiunto il valore di a
  • al valore di temp viene aggiunto il valore di una word del blocco. Ad ogni ciclo viene utilizzata una word diversa attraverso una tabella M
  • a temp viene aggiunto il valore di una costante contenuta nella tabella T calcolata attraverso la funzione sin
  • il valore di temp viene ruotato a sinistra di un numero di bit in corrispondenza della tabella S
  • si aggiunge a temp il valore di b
  • Si ruotano i valori di a, b, c, d assegnando ad a il valore di d, a d il valore di c, a c il valore di b e a b il valore di temp generato dalle operazioni precedenti

Al termine dei 64 cicli vengono aggiunti ai valori di a, b, c, d i valori originali che avevano prima dell'inizio dell'elaborazione del blocco corrente, memorizzati in aa, bb, cc, dd.

md5.png

Metodo alternativo

In modo equivalente, si possono definire 4 funzioni che effettuano le seguenti operazioni:

  • FF(a,b,c,d,Mj ,s,Ti): a = b + ((a + F(b,c,d) + Mj + Ti) <<< s)
  • GG(a,b,c,d,Mj ,s,Ti): a = b + ((a + G(b,c,d) + Mj + Ti) <<< s)
  • HH(a,b,c,d,Mj ,s,Ti): a = b + ((a + H(b,c,d) + Mj + Ti) <<< s)
  • II(a,b,c,d,Mj ,s,Ti): a = b + ((a + I(b,c,d) + Mj + Ti) <<< s)

Dove Mj indica la j-esima word del blocco e Ti indica l'i-esimo elemento della tabella i.

Si possono quindi descrivere tutti i 64 cicli in base a queste nuove funzioni in un'unica tabella:

ciclo operazione ciclo operazione ciclo operazione ciclo operazione
1 FF (a, b, c, d, M0 , 7, 0xd76aa478) 17 GG (a, b, c, d, M1 , 5, 0xf61e2562 33 HH (a, b, c, d, M5 , 4, 0xfffa3942) 49 II (a, b, c, d, M0 , 6, 0xf4292244)
2 FF (d, a, b, c, M1 , 12, 0xe8c7b756) 18 GG (d, a, b, c, M6 , 9, 0xc040b340) 34 HH (d, a, b, c, M8 , 11, 0x8771f681) 50 II (d, a, b, c, M7 , 10, 0x432aff97)
3 FF (c, d, a, b, M2 , 17, 0x242070db) 19 GG (c, d, a, b, M11 , 14, 0x265e5a51) 35 HH (c, d, a, b, M11 , 16, 0x6d9d6122) 51 II (c, d, a, b, M14 , 15, 0xab9423a7)
4 FF (b, c, d, a, M3 , 22, 0xc1bdceee) 20 GG (b, c, d, a, M0 , 20, 0xe9b6c7aa) 36 HH (b, c, d, a, M14 , 23, 0xfde5380c) 52 II (b, c, d, a, M5 , 21, 0xfc93a039)
5 FF (a, b, c, d, M4 , 7, 0xf57c0faf) 21 GG (a, b, c, d, M5 , 5, 0xd62f105d) 37 HH (a, b, c, d, M1 , 4, 0xa4beea44) 53 II (a, b, c, d, M12 , 6, 0x655b59c3)
6 FF (d, a, b, c, M5 , 12, 0x4787c62a) 22 GG (d, a, b, c, M10 , 9, 0x02441453) 38 HH (d, a, b, c, M4 , 11, 0x4bdecfa9) 54 II (d, a, b, c, M3 , 10, 0x8f0ccc92)
7 FF (c, d, a, b, M6 , 17, 0xa8304613) 23 GG (c, d, a, b, M15 , 14, 0xd8a1e681) 39 HH (c, d, a, b, M7 , 16, 0xf6bb4b60) 55 II (c, d, a, b, M10 , 15, 0xffeff47d)
8 FF (b, c, d, a, M7 , 22, 0xfd469501) 24 GG (b, c, d, a, M4 , 20, 0xe7d3fbc8) 40 HH (b, c, d, a, M10 , 23, 0xbebfbc70) 56 II (b, c, d, a, M1 , 21, 0x85845dd1)
9 FF (a, b, c, d, M8 , 7, 0x698098d8) 25 GG (a, b, c, d, M9 , 5, 0x21e1cde6) 41 HH (a, b, c, d, M13 , 4, 0x289b7ec6) 57 II (a, b, c, d, M8 , 6, 0x6fa87e4f)
10 FF (d, a, b, c, M9 , 12, 0x8b44f7af) 26 GG (d, a, b, c, M14 , 9, 0xc33707d6) 42 HH (d, a, b, c, M0 , 11, 0xeaa127fa) 58 II (d, a, b, c, M15 , 10, 0xfe2ce6e0)
11 FF (c, d, a, b, M10 , 17, 0xffff5bb1) 27 GG (c, d, a, b, M3 , 14, 0xf4d50d87) 43 HH (c, d, a, b, M3 , 16, 0xd4ef3085) 59 II (c, d, a, b, M6 , 15, 0xa3014314)
12 FF (b, c, d, a, M11 , 22, 0x895cd7be) 28 GG (b, c, d, a, M8 , 20, 0x455a14ed) 44 HH (b, c, d, a, M6 , 23, 0x04881d05) 60 II (b, c, d, a, M13 , 21, 0x4e0811a1)
13 FF (a, b, c, d, M12 , 7, 0x6b901122) 29 GG (a, b, c, d, M13 , 5, 0xa9e3e905) 45 HH (a, b, c, d, M9, 4, 0xd9d4d039) 61 II (a, b, c, d, M4 , 6, 0xf7537e82)
14 FF (d, a, b, c, M13 , 12, 0xfd98719 30 GG (d, a, b, c, M2 , 9, 0xfcefa3f8) 46 HH (d, a, b, c, M12 , 11, 0xe6db99e5) 62 II (d, a, b, c, M11 , 10, 0xbd3af235)
15 FF (c, d, a, b, M14 , 17, 0xa679438e) 31 GG (c, d, a, b, M7 , 14, 0x676f02d9) 47 HH (c, d, a, b, M15 , 16, 0x1fa27cf8) 63 II (c, d, a, b, M2 , 15, 0x2ad7d2bb)
16 FF (b, c, d, a, M15 , 22, 0x49b40821) 32 GG (b, c, d, a, M12 , 20, 0x8d2a4c8a) 48 HH (b, c, d, a, M2 , 23, 0xc4ac5665) 64 II (b, c, d, a, M9 , 21, 0xeb86d391)
Bibliography
1. R. Rivest, "The MD5 Message-Digest Algorithm", IETF Network Working Group - RFC1321, 1992, Sito web: http://www.ietf.org/rfc/rfc1321.txt
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License