Kolizja (kryptografia)

Kolizja funkcji skrótu H to taka para różnych wiadomości m1, m2, że mają one taką samą wartość skrótu, tj. H(m1) = H(m2).

Ponieważ funkcja skrótu zwraca skończenie wiele wartości, a przestrzeń argumentów jest nieskończona (w przypadku funkcji akceptujących dowolnie długie argumenty), lub przynajmniej znacznie większa od przestrzeni wyników, dla każdej funkcji skrótu istnieją kolizje.

W wielu zastosowaniach zależy nam na tym, żeby nie była znana żadna kolizja funkcji skrótu. Jest to jednak bardzo silne wymaganie, i często zależy nam na słabszej właściwości funkcji (od silniejszych do słabszych właściwości):

• niemożliwość łatwego generowania nowych kolizji
• niemożliwość znalezienia, dla danego m1 takiego m2, że H(m1) = H(m2), czyli second preimage resistance
• niemożliwość znalezienia, dla danego h takiego m że H(m) = h, czyli preimage resistance