Kryptografická hašovací funkce: Porovnání verzí

← Přejít na předchozí porovnání Přejít na další porovnání →

Smazaný obsah Přidaný obsah

V textu

Verze z 1. 12. 2007, 19:06

Hashovací funkce je předpis pro výpočet kontrolního součtu (hashe) ze zprávy či většího množství dat. 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. Formálně je to funkce h, která převádí vstupní posloupnost bitů (či bytů) na posloupnost pevné délky n bitů.

$h:D\rightarrow R\,,$

kde |D|>|R|.

Z definice plyne existence kolizí, to znamená dvojic vstupních dat (x,y) takových, že h(x)=h(y). 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 vysoká pravděpodobnost, že dvě zprávy se stejným kontrolním součtem jsou stejné.

Požadavky na hashovací funkci

Nejdůležitější je následující trojice vlastností. Obtížností se v tomto kontextu myslí výpočetní složitost.

Odolnost vůči získání předlohy. Pro daný hash c je obtížné spočítat x takové, že h(x)=c. (Hashovací funkce je jednosměrná.)
Odolnost vůči získání jiné předlohy. Pro daný vstup x je obtížné spočítat y takové, že h(x)=h(y).
Odolnost vůči nalezení kolize. Je obtížné systematicky najít dvojici vstupů (x,y), pro které h(x)=h(y).

Další obvyklé požadavky zahrnují:

Nekorelovatelnost vstupních a výstupních bitů, kvůli znemožnění statistické kryptoanalýzy.
Odolnost vůči skoro-kolizím. Je obtížné nalézt x a y taková, že h(x) a h(y) se liší jen v malém počtu bitů.
Lokální odolnost vůči získání předlohy. Je obtížné najít i jen část vstupu x ze znalosti h(x).

Známé hashovací funkce

MD5 – oblíbená, ale již kompromitovaná funkce. Od srpna 2004 je veřejně znám postup pro nalezení kolizního páru zpráv.^[1]
SHA-1 – oblíbená, ale již kompromitovaná funkce. V únoru 2005 byl zveřejněn objev algoritmu, který umožňuje nalézt kolizi podstatně rychleji než hrubou silou. Výpočetní náročnost je ale stále mimo současnou techniku.
SHA-2 – rodina 4 hashovacích funkcí (SHA-256, SHA-384, SHA-512 a SHA-224), které jsou součástí standardu FIPS 180-2^[2], a u kterých dosud nebyly nalezeny žádné bezpečnostní slabiny.

Podívejte se také

CRC

Externí odkazy

http://www.lupa.cz/clanek.php3?show=4090 – úvod do hashovacích funkcí
Kryptografická hašovací funkce v encyklopedii MathWorld (anglicky)

Reference

[hash_klima-1] Stránka věnovaná kolizím hashovacích funkcí, Vlastimil Klíma

[FIPS180-2] FIPS 180-2 (pdf)

[1]

[2]

@@ Řádek 20: / Řádek 20: @@
 == Známé hashovací funkce ==
-* [[MD5]] &ndash; oblíbená, ale již [[kompromitovaná funkce]]. Od srpna [[2004]] je veřejně znám postup pro nalezení kolizního páru zpráv. <ref name="hash_klima">[http://cryptography.hyperlink.cz/2004/kolize_hash.htm Stránka věnovaná kolizím hashovacích funkcí, Vlastimil Klíma]</ref>
+* [[MD5]] &ndash; oblíbená, ale již [[kompromitovaná funkce]]. Od srpna [[2004]] je veřejně znám postup pro nalezení kolizního páru zpráv.<ref name="hash_klima">[http://cryptography.hyperlink.cz/2004/kolize_hash.htm Stránka věnovaná kolizím hashovacích funkcí, Vlastimil Klíma]</ref>
 * [[SHA-1]] &ndash; oblíbená, ale již kompromitovaná funkce. V únoru [[2005]] byl zveřejněn objev [[algoritmus|algoritmu]], který umožňuje nalézt kolizi podstatně rychleji než hrubou silou. Výpočetní náročnost je ale stále mimo současnou techniku.
-* [[SHA-2]] &ndash; rodina 4 hashovacích funkcí (SHA-256, SHA-384, SHA-512 a SHA-224), které jsou součástí standardu FIPS 180-2 <ref name="FIPS180">[http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf FIPS 180-2 (pdf)]</ref>, a u kterých dosud nebyly nalezeny žádné bezpečnostní slabiny.
+* [[SHA-2]] &ndash; rodina 4 hashovacích funkcí (SHA-256, SHA-384, SHA-512 a SHA-224), které jsou součástí standardu FIPS 180-2<ref name="FIPS180">[http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf FIPS 180-2 (pdf)]</ref>, a u kterých dosud nebyly nalezeny žádné bezpečnostní slabiny.
 == Podívejte se také ==