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)Lo spostamento a sinistra di 10 bit genera questo risultato:
(2)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ì:
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
Spostamento a destra di 32 - 10 = 22 bit
(5)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.
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.
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) |