Hašovací funkce

Hašovací funkce je matematická funkce (resp. algoritmus) pro převod vstupních dat do (relativně) malého čísla. Výstup hašovací funkce se označuje výtah, miniatura, otisk, fingerprint či hash (česky též někdy jako haš). Hašovací funkce se používají k rychlejšímu prohledávání tabulky, porovnávání dat (například pro hledání položek v databázi, odhalování duplicitních záznamů, hledání malware antivirovým programem), při hledání podobných úseků DNA sekvencí v bioinformatice i jinde. V podobě kryptografické hašovací funkce je používána pro vytváření a ověřování elektronického podpisu, zajištění integrity dat, ochranu uložených hesel atd.

Vlastnosti

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

jakékoliv množství vstupních dat poskytuje stejně dlouhý výstup (otisk),
malou změnou vstupních dat dosáhneme velké změny na výstupu (tj. výsledný otisk se od původního zásadně na první pohled liší),
z hashe je prakticky nemožné rekonstruovat původní text zprávy (což je rozdíl oproti klasickému šifrování),
v praxi je vysoce nepravděpodobné, že dvěma různým zprávám odpovídá stejný hash, jinými slovy pomocí hashe lze v praxi identifikovat právě jednu zprávu (ověřit její správnost).

Hašování v základní variantě dovoluje testovat vstupní data na shodu, tedy rovnost. Nezachovává podobnost dat ani uspořádání.

Popis

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

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 větší než počet možných různých otisků. Vhodnou volbou funkce lze snížit pravděpodobnost, že nastane kolize pro podobná data.

Použití

Hašovací funkce se používají k několika účelům a podle toho se liší požadavky na ně.

Hašovací tabulka

Datová struktura hašovací tabulka používá hašovací funkci (nebo funkce) na transformaci klíče na index, podle kterého se do tabulky přistupuje. Požaduje se rovnoměrné rozdělení zahašovaných klíčů do rozsahu indexů. Tabulka nemusí být velikosti mocniny dvojky. Tabulka může být v některých aplikacích distribuována na víc počítačů, pak jde o distribuovanou hašovací tabulku.

Při tomto použití je důležitá rychlost výpočtu (tj. časová složitost) funkce na rozdíl od použití v kryptografii. Často se používá modulární aritmetika a zbytek po dělení jako závěrečná operace zajistí číslo v daném rozsahu. Tabulky jsou většinou v operační paměti a v tom případě je rozsah řádově do miliard položek, tj. 32 bitů.

Například funkce může vynásobit parametr nějakou hodnotou nesoudělnou s velikostí tabulky a pak spočítat zbytek (modulo).

Bloomův filtr je datová struktura, která využívá víc hašovacích funkcí pro indexování, ale pro jiné aplikace než vyhledávání.

Otisk, signatura

Kontrolní otisk souboru (nebo jiných dat) jako metoda detekce chyb při přenosu nebo ukládání. V tomto případě jde o náhodné a neúmyslné chyby a příkladem metody je cyklický redundantní součet (CRC).

Jiný způsob využití otisků, v tomto kontextu někdy nazývaných signatury, je pro (rychlé) filtrování dat. Pokud chceme nalézt data se stejným klíčem (nebo stejný soubor) k danému klíči k, porovnáme signaturu k s (předpočítanými) signaturami dat a pokud se neshoduje, můžeme data vyloučit jako určitě nerelevantní. Při shodě máme potenciální kandidáty, které musíme otestovat podrobněji. Výhoda této metody je, že je použitelná na různá data a že signatura může být podstatně menší než data. Příklad tohoto použití jsou seznamy signatur problémových souborů u antivirů a spamových filtrů. Strukturovaná data lze před hašováním serializovat.

Použitím delší signatury nebo více signatur standardního rozsahu 32/64 bitů lze zmenšit pravděpodobnost náhodné shody dat, pokud ta není žádoucí. Speciálně lze použít kryptografickou hašovací funkci (viz dále) nebo její úvodní část, ale tato možnost je pomalejší než jednoúčelové funkce. Pokud nevadí tato malá pravděpodobnost chyby, není nutno při shodě otisku testovat původní "surová" data a tudíž je ani předávat, resp. pamatovat si.

Algoritmus Rabin-Karp pro vyhledávání v textu používá postupné počítání otisků postupujícího textového okna pro zvýšení efektivity.

Pojem signatura se v informatice používá i ve významu typové signatury.

Kryptografická hašovací funkce

Kryptografická hašovací funkce je používána pro ochranu proti úmyslnému poškození dat a v dalších kryptografických aplikacích. Rozsah výstupních hodnot je větší, např. SHA-2 má varianty pro 224, 256, 384 a 512 bitů.

Prvořadá není rychlost funkce, ale kryptografické vlastnosti.

Perfektní hašování

Perfektní (dokonalé) 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í.

Jiné aplikace

Hašovací funkce se používá jako součást dalších algoritmů, které přímočaře nespadají do tří hlavních výše zmíněných skupin. Bloomův filtr používá několik funkcí jako indexů do bitové tabulky.

Použití otisků dovoluje testovat přesnou shodu. Při hledání podobných dat se počítají několikrát otisky z části dat a hledá se shoda otisků a tedy shoda části dat, která se následně rozšiřuje, např. při hledání podobnosti v DNA. Jiná možnost je z hodnot otisků sestavit histogram a porovnávat tyto histogramy. V tomto případě speciálně navržené funkce mohou maskovat určité druhy chyb. Takto lze např. porovnávat dokumenty pomocí hašování trojic sousedících slov. Ignorovanou chybou může být prohození slov a to zajistíme ve funkci tak, že nebude záležet na pořadí vstupních slov a funkce bude vracet v těchto případech stejný otisk.

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í)
Message-Digest algorithm (MD5)

Externí odkazy

Obrázky, zvuky či videa k tématu hašovací funkce na Wikimedia Commons
Hašovací funkce v encyklopedii MathWorld (anglicky)
Minimal Perfect Hashing (anglicky)