Hašovací funkce

Ilustrace principu hašovacích funkcí: ze 4 různě dlouhých vstupů jsou vytvořena 4 stejně dlouhá čísla (mezi 00 až 15; v ukázce bez kolize). Reálné kryptografické hašovací funkce pochopitelně vytváří mnohem delší výstup, ale opět vždy konstantní délky (dnes nejčastěji 256 nebo 512 bitů). 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. +more 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ů. +more 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. +more Č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í. +more 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. +more 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ř. +more 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í je specifická varianta hašování. Předpokládejme, že máme množinu klíčů S. +more 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ř. +more 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

[url=http://www.burtleburtle.net/bob/hash/perfect.html]Minimal Perfect Hashing[/url] (anglicky)

Kategorie:Matematické funkce Funkce Kategorie:Detekce a oprava chyb Kategorie:Algoritmy