Ide cisto o to ze pokial mas zdrojove subory velke 2^niekolko miliard a hash sumu velku 2^128 musis mat kolizie. A stojim si za vyjadrenim ze aj ak pouzijes vela hashovacich funkcii, vzdy najdes koliziu nakolko je moznosti na strane vstupnych dat relativne nekonecno.
A ak sa mi teraz niekto bude snazit oponovat, vlastne chce tvrdit ze niekolko TiB zdrojovych dat by vedel bestratovo komprimovat na 2^128 bitov... Kedze by podla neho nedoslo ku kolizii, bolo by mozne z tych 2^128 bitov presne dostat spat vstupne data [ano, hash, ale hoci aj brute forcovanim]. Lenze tak to proste NIE JE. Pretoze mapujes mnozinu n na mnozinu m, pricom plati ze mnozina n < m, cize to nemoze byt 1:1 ale 1:X, cize to X vyjadruje pocet roznych vstupnych dat ktore vypluju tu istu kontrolu sumu.
Preto hovorim ze najdes koliziu VZDY a je uplne jedno kolo hash funkcii pouzjes, pretoze ratame s 2 premisami:
1) Vstupne data mozu byt nekonecne velke
2) Kontrolne sumy musia byt RADOVO mensie
Pokial vyhodis jednu z tych 2 podmienok, nemusia existovat kolizie. Pokial tie podmienky zachovas, MUSIA existovat kolizie.
68 Odpovědí
9206 Zhlédnutí