Odpověď na názor

Bezkoliznost je překlad anglického collision free. Neznamená to, že kolize nenastanou, ale že je výpočetně nemožné je NALÉZT (viz též správné odpovědi ostatních v diskusi). Protože fakt o EXISTENCI kolizí je zcela triviální, nikdo zasvěcený si při vyslovení pojmu bezkolizní (collision free) nemyslí, že by snad neexistovaly (to je také odpověď na jiný příspěvek do diskuse). Pár definic z kapitoly 12 mojí přednášky na MFF UK (viz lit., k dispozici on-line, prosím nevnucuji, ale když už to je napsané, nechci to opisovat, kromě toho je to v kontextu i s příklady apod.) pro osvěžení (také odpověď na více příspěvků):

Definice: jednosměrná (jednocestná) funkce
Funkci f: X --> Y nazveme jednosměrnou (jednocestnou), jestliže z jakékoli hodnoty x z množiny X je snadné vypočítat y = f(x), ale pro náhodně vybranou hodnotu y z množiny f(X) neumíme (je výpočetně nemožné) najít její vzor x z množiny X tak, aby y = f(x).

Definice: bezkolizní funkce
Funkci f: X --> Y nazveme bezkolizní, jestliže je výpočetně nemožné nalézt různá x, x´ z množiny X tak, že f(x) = f(x´).

Definice: hašovací funkce
Mějme přirozená čísla L, n a nechť X je množina všech binárních řetězců délky 0 až L (prázdný řetězec je platným vstupem a má délku nula). Funkci h: X --> {0,1}^n nazveme hašovací, jestliže je jednosměrná a bezkolizní. Říkáme, že každému binárnímu řetězci z množiny X přiřadí binární hašový kód (hash, haš) délky n.

Z důvodu definice, tedy samé podstaty hašovacích funkcí, je nalezení kolizí pro hašovací funkci smrtelné.

Dále (také odpověď na více příspěvků) nalezení kolize neznamená, že jsem povinen nalézt druhou kolidující zprávu ke zprávě dané, ale libovolné dvě různé zprávy. Tyto dvě situace se také někdy rozlišují jako kolize prvního a druhého řádu. V definici hašovací funkce se požaduje odolnost silnější, tj. nesmí se najít jakékoliv i nesmyslné různé zprávy se stejnou haší.

Proč? Je opatření proti tomu, když útočníkem je sám tvůrce zpráv (už jsem o tom psal v jiné odpovědi). Pokud bude schopen připravit dvě různé zprávy se stejnou haší, může dát jednu podepsat smluvní straně, ale u soudu předložit druhou (pro něj výhodnější) a tvrdit, že protistrana podepsala tu druhou. Pokud by bylo možné nalézat kolize k "dané" zprávě, byla by to katastrofa. Podepsaný kernel by šel zaměnit za vyrobený kolidující (haš je stejná), "JAKÁKOLIV" smlouva (jakýkoliv digitální podpis) by byla zpochybnitelná předložením vyrobené kolidující smlouvy nebo kolidujícího dokumentu nebo by to umožňovalo podvržení vykonstruovaného kolidujícího programu za pravý (podepsaná je pouze haš).