5 Funzioni di hash e MAC

Una funzione di hash è una funzione che, dato un qualunque messaggio di lunghezza arbitraria, ne produce un'impronta (detta digest) di lunghezza prefissata (di solito dell'ordine di 100-200 bit). L'utilità di una funziona di hash sta nel poter utilizzare l'impronta come rappresentazione compatta del messaggio stesso, tipicamente firmando l'impronta anziché l'intero messaggio; perchè questo possa avvenire è desiderabile che la funzione presenti due proprietà particolari, sia cioè senza collisioni e unidirezionale.

Una funzione di hash $h\left( x\right)$ è detta debolmente senza collisioni se, dato un messaggio $x$ , è computazionalmente impraticabile trovare un messaggio $x'\neq x$ tale che $h\left( x'\right) =h\left( x\right)$ .
Una funzione di hash $h\left( x\right)$ è detta fortemente senza collisioni se è computazionalmente impraticabile trovare due messaggi $x$ e $x'$ tali che $x'\neq x$ e $h\left( x'\right) =h\left( x\right)$ .
Una funzione di hash $h\left( x\right)$ è detta unidirezionale se, data un'impronta $z$ , è computazionalmente impraticabile trovare un messaggio $x$ tale che $h\left( x\right) =z$ .

Le funzioni di hash possono essere utilizzate insieme con delle chiavi segrete per ottenere autenticazione e integrità dei messaggi, realizzando così dei MAC (Message Authentication Code). Più precisamente, possiamo definire algoritmo di MAC una funzione $h_{k}\left( x\right)$ , parametrizzata da una chiave $k$ , con le seguenti proprietà:

Dati una chiave $k$ e un input $x$ , è facile calcolare $h_{k}\left( x\right)$ . Tale valore è detto brevemente MAC.
Dato un input $x$ di lunghezza qualsiasi la funzione genera un output $h_{k}\left( x\right)$ di lunghezza prefissata.
Noto un certo numero di coppie $\left( x_{i},h_{k}\left( x_{i}\right) \right)$ è computazionalmente impraticabile calcolare qualunque altra coppia $\left( x,h_{k}\left( x\right) \right)$ per un qualsiasi nuovo input $x\neq x_{i}$ senza conoscere $k$ .