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] Dokonalé hašování

Dokonalé hašování (perfect hashing) je specifická varianta hašování, kterou lze použít tehdy, známe-li předem všechny platné klíče. Pak můžeme pro tuto množinu klíčů sestavit takovou hašovací funkci, která zcela vyloučí kolize.

[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)