Hashovací funkce

  • Silný nástroj moderní kryptologie
  • Jednosměrnost, bezkoliznost
Definice
  • Mějme přirozené číslo a množinu všech binárních řetězců délky až .
  • Funkci nazveme hashovací, jestliže je jednosměrná 1. typu a bezkolizní.
  • Každému binárnímu řetězci z množiny přiřadí binární hashovací kód (hash) délky bitu.

../Attachments/Pasted image 20230321151830.png

Kryptografická hashovací funkce

  • Libovolně velkému vstupu přiřazuje kód pevné délky
  • Například
    • SHA-1 = hash 160 bitů
    • SHA-256 = hash 256 bitů
    • SHA-512 = hash 512 bitů
  • Z hlediska bezpečnosti požadujeme, aby se hashovací funkce chovala jako náhodné orákulum

Orákulum

  • Libovolný stroj "podivuhodných vlastností", který na základě vstupu odpovídá nějakým výstupem
  • Na tentýž vstup odpovídá stejným výstupem

Náhodné orákulum

  • Na nový vstup odpovídá náhodným výběrem z množiny výstupů

Bezkoliznost

  • Bezkoliznost 1. řádu

    • Hashovací funkce je odolná, jestliže je výpočetně nezvládnutelné nalezení 2 různých vstupů tak, aby měly stejný výstup
    • (můžu si zvolit oba vstupy)
    • Počet hashovacích operací (pro 50% pravděpodobnost) je zhruba
      (vychází z narozeninového paradoxu)

  • Bezkoliznost 2. řádu

    • Hashovací funkce je odolná, jestliže pro jakýkoliv vzor je výpočetně nezvládnutelné nalézt vzor tak, že
    • (jeden vstup mám, hledám druhý)
    • Počet hashovacích operací (pro 50% pravděpodobnost) je zhruba
      (vychází z narozeninového paradoxu)

  • Když víme, jak vzory nalézat jednodušeji, hovoříme o prolomení hashovací funkce

  • Bezkoliznost ve běžně využívá u digitálních podpisů - nepodepisujeme přímo zprávu (často dlouhá), ale pouze její hash

Konstrukce hash. funkcí

  • Zpracování po částech (bloky stejné délky)
  • Nutnost zarovnání vstupu na celistvý počet bloků (padding)
  • Zarovnání musí být bezkolizní, musí umožňovat jednoznačné odejmutí
    • Doplnění bitem 1 a poté potřebným počtem bitů 0
    • Demgard-Merklovo zesílení - na konci obsahuje ještě 64 bitů s informací o délce původní zprávy

Příklad špatného zarovnání zprávy

Mějme zprávu

Byla původní zpráva
nebo
nebo
nebo
nebo

?

Všechny by vedly ke kolizi a měly stejný hash.

Damgard-Merklova konstrukce

  • Damgard-Merklovo zesílení

  • Doplnění hashe

  • Zpráva je doplněna bitem a poté bity tak, aby do celistvého násobku 512 bitů zbývalo ještě 64 bitů

  • Posledních 64b je vyplněno hodnotou počtu bitů původní zprávy

  • Funkce zpracovává aktuální blok zprávy a výsledkem je tzv. kontext

  • Ten poté tvoří vstup v dalším kroku

../Attachments/Pasted image 20230610230316.png

  • Iterativní konstrukce
  • Zahashováním posledního boku dostáváme , z něhož bereme buď část nebo celou délku jako výslednou hash

Davies-Meyerova konstrukce

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25