Hashovací funkce

Hashovací funkce je reprodukovatelná metoda pro převod vstupních dat do (relativně) malého čísla, které vytváří jejich otisk (můžeme ho označit jako charakteristika dat). Výsledný otisk se označuje také jako výtah, miniatura, fingerprint či hash (česky též někdy jako haš). Funkce může sloužit ke kontrole integrity dat, k rychlému porovnání dvojice zpráv, indexování, vyhledávání apod. Je důležitou součástí kryptografických systémů pro digitální podpisy.

[editovat] Vlastnosti

Mezi hlavní vlastnosti této funkce patří:

1. jakékoliv množství vstupních dat poskytuje stejně dlouhý výstup (otisk)
2. malou změnou vstupních dat dosáhneme velkou změnu na výstupu (tj. výsledný otisk se od původního zásadně na první pohled liší)
3. vysoká pravděpodobnost, že dvě zprávy se stejným hašem jsou stejné

[editovat] Popis

Formálně jde o funkci h, která převádí vstupní posloupnost bitů (či bytů) na posloupnost pevné délky n bitů.

kde |D| > |R|.

Z definice plyne existence kolizí, to znamená dvojic vstupních dat (x,y), x≠y, takových, že h(x) = h(y), tj. dvojice různých vstupních dat může mít stejný otisk. Kolize jsou nežádoucí, ale v principu se jim nelze úplně vyhnout. Lze jen snižovat pravděpodobnost, že nastane kolize pro podobná data, například při náhodné změně v části vstupní posloupnosti. Cílem je tedy dosáhnout co nejvyšší pravděpodobnosti, že dvě zprávy se stejným hashem (hešem) jsou stejné.

[editovat] Perfektní hašování

Perfektní hašování (perfect hashing) je specifická varianta hašování. Předpokládejme, že máme množinu klíčů S. Potom můžeme najít takovou hašovací funkci, která pro danou množinu nebude mít ani jednu kolizi. Perfektní hašování se dělí na statické a dynamické, podle toho, zda se množina S v době existence Perfektní hašovací funkce mění.

[editovat] Související články

• Cyklický redundantní součet (CRC)
• Kontrolní součet
• Hashovací tabulka
• Kryptografická hashovací funkce
• Cormackovo hashování (metoda dokonalého hašování)

[editovat] Externí odkazy

• (en)Hashovací funkce na MathWorldu

• Minimal Perfect Hashing (anglicky)