Hašovacia funkcia
Z Wikipédie
Hašovacia funkcia je funkcia, predpis pre transformáciu ľubovoľného vstupu na fixne dlhý výstup, akúsi jeho "jedinečnú" skratku. Pre rovnaký vstup zakaždým rovnakú. Vstupom je ľubovoľný konečný tok dát. Výstup má fixnú dĺžku. Tento reťazec sa označuje ako haš, charakteristika, odtlačok. Jeho dĺžka závisí od použitej hašovacej funkcie.
Toto zobrazenie väčšej množiny vstupov x, do menšej množiny výsupov H(x) nie je prosté. Preto existujú dva rôzne vstupy, ktoré dávajú rovnaký výstup. Hovorí sa o kolízii.
Obsah |
[upraviť] Vlastnosti
- Jednocestnosť - funkcia musí byť jednocestná, tj. inverznú funkciu ťažko nájsť. Teda iba znalosť výstupu nijak nevedie k znalosti vstupného textu. Pre dané x ľahko spočítať H(x), pre dané H(y) ťažko spočítať y.
- Silná bezkolíznosť - ak nie je možné v rozumnom čase nájsť akýkoľvek pár vstupov tak, aby nastala kolízia. Nájsť ľubovoľné x1, x2, aby platilo H(x1) = H(x2).
- Slabá bezkolíznosť - ak nie je možné v rozumnom čase k danému vstupu nájsť vstup iný tak, aby nastala kolízia. Pre dané x1 nájsť také x2, x1 ≠ x2, aby platilo H(x1) = H(x2).
- Lavínovitosť - vytvorený hash musí natoľko závisieť na každom bite vstupu, že aj jeho malá zmena rapídne ovplyvní výstup.
- Rozloženie výstupov - funkcia distribuuje výstupy rovnomerne v celom obore hodnôt, teda produkuje málo kolízii.
[upraviť] Implementácie
Medzi najrozšírenejšie skupiny hašovacích funkcií patria:
- Message-Digest algorithm
- Secure Hash Algorithm
- RACE Integrity Primitives Evaluation Message Digest
vstup: Prehlasujem, že ti dlžím 100 výstup: MD5 fbe8e3408311811c0d182d0193a03a62 SHA-1 68741d0244e8ce0989af154977ce037c7c75a32e SHA-256 da3292bf01f1a5a37ffd1c8650430c3a65766205bad2faac1e1a7ab1d23ccc88 RIPEMD160 01b5e2da3697a5759d7848e697b1415aeb6e082d
Ďalšími implementáciami hašovacích funkcií sú napr.: Whirlpool, HAVAL, PANAMA, Tiger.
[upraviť] Použitie
Bezpečnosť hašovacích funkcií je pri správnom algoritme závislá na dĺžke výstupného reťazca. Od neho sa odvádza doba nutná na tzv. útok hrubou silou, skúšanie všetkých kombinácii. Správny algoritmus je založený na nejakom v súčasnosti ťažkom matematickom probléme (faktorizácia, diskrétne logaritmy).
Implementácie MDx sa už nepovažujú za bezpečné, kvôli možnosti nájsť kolízie v rádoch minút z dôvodu chyby v algoritme. Po nájdení slabých kolízii aj v skupine SHA sa doporučuje používať minimálne SHA-256, teda funkciu s dlhším výstupným reťazcom.
Hašovacie funkcie majú v informatike rozmanité použitie, od indexovania a vyhľadávania (vtedy hovoríme o transformácii kľúča) cez rýchle porovnávanie súborov až po zaistenie dátovej integrity a autentifikácie napr. pomocou elektronického podpisu.
[upraviť] Externé odkazy
- HashCalc - freeware nástroj na výpočet viacerých hašovacích funkcií
- Crypto-world - detailný článok o rôznych hašovacích funkciách
