Hašovací funkce

Z Wikipedie, otevřené encyklopedie

Je navrženo začlenit obsah tohoto článku do článku Kryptografická hašovací funkce (diskuse), a tak oba články sloučit.

Hašovací funkce je reprodukovatelná metoda pro převod vstupních dat do (relativně) malého čísla, které vytváří jejich jednoznačnou charakteristiku a je velmi obtížné najít taková data, která vyhovují požadovanému otisku (tzv. jednocestná funkce). Výstup hašovací funkce označujeme jako výtah, miniatura, otisk, fingerprint či hash (česky též někdy jako haš). Funkce je důležitou součástí kryptografických systémů pro digitální podpisy a často se též používá pro kontrolu integrity dat, k rychlému porovnání dvojice zpráv, indexování, vyhledávání apod.

[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é
4. vysoká obtížnost nalezení vstupu, který odpovídá požadovanému haši (výstupu), viz jednocestná funkce

[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 vyhnout, protože počet možných různých vstupních zpráv je nekonečný a počet různých otisků je omezený (limitovaný, konečný, menší). Vhodnou volbou funkce lze snížit pravděpodobnost, že nastane kolize pro podobná data (např. při náhodné změně v části vstupní posloupnosti) a maximalizovat obtížnost nalezení inverzí funkce. 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
• Hašovací tabulka
• Kryptografická hašovací funkce
• Cormackovo hašování (metoda dokonalého hašování)

[editovat] Externí odkazy

• (en)Hašovací funkce na MathWorldu
• Minimal Perfect Hashing (anglicky)