Asymetrické, digit. podpis, certifikáty

Cite

Asymetrické kryptosystémy

  • Pro šifrování a dešifrování se používá pár rozdílných klíčů, řeší problém sdílení klíče v symetrických šifrách (Asymetrická schémata)
  • Veřejný klíč - zašifrování zprávy, ověření (autentizace) digitálního podpisu
  • Privátní (soukromý) klíč - dešifrování zprávy, vytvoření digitálního podpisu

../../Attachments/Pasted image 20230404152342.png

  • Privátní klíč nelze z veřejného odvodit v rozumném čase
  • Bezpečnost se neopírá o utajení algoritmu, ale o výpočetní náročnost (Kerckhoffsův princip)
    • Problém faktorizace velkých čísel
      • Jednoduché spočítat
      • Složité rozložit na původní prvočísla a
    • Problém diskrétního logaritmu
      • Klasický logaritmus: V reálných číslech umíme počítat velmi rychle
      • Diskrétní logaritmus:
        • Pracujeme v konečné cyklické grupě (typicky celé číslo modulo prvočíslo)
        • Pokud známe , spočítat (např. pomocí Square & Multiply) je jednoduché
        • Pokud známe , spočítat (tedy ) je pro velká čísla v rozumném čase nemožné
Poznámka značení

Místo rozepisování modula jako lze narazit také na

Šifra RSA

RSA

Princip RSA

  • Zvolíme dvě velká prvočísla a (k testování prvočíselnosti lze zvolit Rabin-Millerův test)

  • Spočítáme modul

  • Spočítáme Eulerovu funkci *(počet nesoudělných přirozených kladných celých čísel menších než )

  • Zvolíme veřejný exponent takový, že

    • (aby existovala modulární inverze)
    • a větší než a (aby šifrování i dešifrování muselo používat redukci modulo a nešlo pouze odmocnit)

  • Spočítáme soukromý exponent jako modulární inverzi:

  • Dvojice je veřejný klíč ( - modul, - veřejný exponent,)

  • Dvojice je soukromý klíč ( - modul, - modulární inverze )

Šifrování a dešifrování

  • Předpis totožný s exponenciální šifrou

  • Šifrování zprávy

  • Dešifrování zprávy

  • (m = plain text message, c = cipher text)

  • Pro urychlení dešifrování lze použít RSA-CRT

    • Využívá Čínskou věta o zbytcích
    • Dešifrovací proces rozkládá do více paralelních výpočtů (více vláken)
    • Veřejný klíč je stejný jako u RSA -
    • Soukromý klíč je složitější -

Bezpečnost

  • Založeno na modulárním umocňování a faktorizaci velkých čísel
  • Se znalostí lze pomocí Eukleidova algoritmu spočítat dešifrovací klíč
  • Bez znalosti je nalezení složité jako faktorizace modulu
  • Ochrana proti speciálním technikám faktorizace:
    • Obě hodnoty by měly mít malé
    • A zároveň se dostatečně lišit, tedy rozdíl co největší

Digitální podpis s využitím RSA

  • Podpis zprávy odesílatelem a zároveň zašifrování pro příjemce
  • Odesílatel má jistotu, že zprávu vidí jen příjemce
  • Příjemce má jistotu, že odesílatel je opravdu autorem
  1. Odesílatel (1) podepíše otevřený text svým soukromým klíčem ( - decrypt with soukromý klíč 1)
  2. Odesílatel (1) zašifruje podepsaný text veřejným klíčem příjemce (2) ( - encrypt with veřejný klíč 2)
  3. Příjemce (2) dešifruje text svým soukromým klíčem *( - decrypt with soukromý klíč 1)
  4. Příjemce (2) ověří podpis veřejným klíčem odesílatele ( - encrypt with veřejný klíč 1)

../../Attachments/Pasted image 20260610204629.png

Diffie-Hellman

Diffie-Hellman, Diffie-Hellman na ECC

  • Protokol pro ustanovení společného klíče (Key Exchange) nad nezabezpečeným kanálem
  • Založen na problému diskrétního logaritmu
  • Délka klíče je přímo úměrná kvalitě šifry
  • Pro dva a více subjektů

Algoritmus

  • = velké prvočíslo, vhodné kde je prvočíslo
  • = generátor grupy
  • jsou veřejné prvky
  1. Subjekt A generuje parametr klíče
    1. Zvolí klíč tak, že
    2. Spočítá
    3. Odešle a subjektu B
  2. Subjekt B generuje parametr klíče
    1. Zvolí klíč tak, že
    2. Spočítá
    3. Odešle subjektu A
  3. Oba subjekty spočítají sdílený klíč

Bezpečnost

  • Problém diskrétního logaritmu
  • Útočník nemůže z a spočítat

Jeho nástavbou/úpravou je El Gamal

Hashovací funkce

  • Funkce, která libovolně dlouhému vstupu přiřadí krátký hashovací kód o pevně definované délce

  • Musí být jednosměrná a bezkolizní

  • Jednosměrnost

    • Je snadné z jakékoliv hodnoty spočítat
    • Je výpočetně náročné pro náhodný obraz najít vzor
    • 1. typu - Dána složitostí operace a její inverze (např. násobení dvou čísel a jejich zpětná faktorizace)
    • 2. typu - Dána (ne)znalostí "padacích vrátek" (např. u asymetrické kryptografie znalost klíče)

  • Náhodné orákulum

    • Stroj, který na nový vstup odpovídá náhodným výběrem z množiny výstupů
    • Na stejný vstup odpovídá stejným výstupem
    • Požadované chování hashovací funkce

  • Bezkoliznost

    • 1. řádu
      • Hashovací funkce je odolná proti kolizím 1. řádu, jestliže je výpočetně nezvládnutelné nalézt 2 různé vstupy, které produkují stejný výstup
      • (můžu si zvolit oba vstupy)
      • Složitost nalezení kolize s 50% pravděpodobností je (narozeninový paradox)
    • 2. řádu
      • Hashovací funkce je odolná proti kolizím 2. řádu, jestliže pro zadaný vstup nelze najít jiný, který produkuje stejný výstup
      • (jeden vstup mám, hledám druhý)
      • Složitost nalezení kolize s 50% pravděpodobností je

Konstrukce hashovacích funkcí

  • Zpráva se typicky rozdělí na bloky
  • Poslední blok je potřeba doplnit (zarovnat) na požadovanou délku (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
    • Damgard-Merklovo zesílení - na konci obsahuje ještě 64 bitů s informací o délce původní zprávy

SHA-2

Algoritmus SHA-x

HMAC

Algoritmus HMAC

  • Slouží k ověření integrity i autentizovanosti zprávy pomocí sdíleného tajného klíče
  • Konstrukce hashování zprávy spolu s tajným klíčem
  • Využití
    • Nepadělatelný integritní kód
      • Bez znalosti klíče nelze vypočítat HMAC odpovídající pozměněné zprávě
      • HMAC tedy autentizuje autora zprávy
    • Průkaz znalosti tajného klíče při autentizaci
      • Dotazovatel pošle challenge
      • Prokazovatel vrátí

Digitální podpis

  • Digitální podpis musí garantovat tři základní pilíře bezpečnosti:

    • Autentizace (Původ): Příjemce si může být jistý, že zprávu poslal skutečně držitel soukromého klíče
    • Integrita: Zaručuje, že zpráva nebyla od okamžiku podpisu změněna (i změna jediného bitu způsobí neplatnost podpisu)
    • Nepopiratelnost: Odesílatel nemůže tvrdit, že zprávu neposlal, protože nikdo jiný jeho soukromý klíč nemá

  • Princip

    • Původní zpráva se zahashuje
    • Hash se zašifruje soukromým klíčem odesílatele (vznikne podpis)
    • Příjemce hash dešifruje veřejným klíčem odesílatele a porovná ho s vlastním hashem přijaté zprávy

Infrastruktura veřejného klíče

Infrastruktura veřejného klíče

  • Odpověď na ten největší problém asymetrické kryptografie: „Jak vím, že ten veřejný klíč na internetu opravdu patří Alici a ne útočníkovi (MitM)?“
  • Máme několik možných způsobů

1. Zveřejnění veřejných klíčů

  • Zasílání veřejných klíčů přímo

  • Výhody: Rychlé a extrémně jednoduché, decentralizované, nevyžaduje žádnou třetí stranu

  • Nevýhody: Neodolné proti podvržení

2. Veřejně dostupný adresář

  • Distribuci zajišťuje důvěryhodná třetí strana (autorita/správce adresáře)

  • Výhody: Vyšší zabezpečení, adresář garantuje, že daný klíč byl zaregistrován pro konkrétního člověka

  • Nevýhody: Kompromitace serveru a podvržení klíčů všem uživatelům, nutné kontaktovat server (bottleneck)

../../Attachments/Pasted image 20230606220711.png

3. Autorita pro veřejné klíče

  • Vylepšená, dynamická verze adresáře

  • Každý účastník zná veřejný klíč autority, která vlastní odpovídající soukromý klíč

  • Když chce Alice komunikovat s Bobem, pošle autoritě zabezpečený dotaz. Autorita jí pošle Bobův veřejný klíč zabalený do zprávy, kterou podepíše svým soukromým klíčem

  • Výhody: Data z adresáře jsou podepsaná autoritou, takže je útočník nemůže po cestě upravit

  • Nevýhody: Autorita musí být stále dostupná online v reálném čase, dotazy autoritě se posílají při každém pokusu o komunikaci

../../Attachments/Pasted image 20230606220726.png

4. Certifikace veřejných klíčů

Digitální certifikát

  • Digitální dokument, který závazně spojuje identitu subjektu s jeho veřejným klíčem
  • Je podepsán soukromým klíčem certifikační autority, každý účastník může verifikovat obsah pomocí veřejného klíče certifikační autority
  • Nejčastěji obsahuje:
    • Identifikační údaje subjektu
    • Veřejný klíč subjektu
    • Informace o vydavateli (certifikační autoritě)
    • Dobu platnosti

Certifikační autorita

  • Důvěryhodná třetí strana, které věří jak odesílatel, tak příjemce

    • (Kořenové certifikáty musí být distribuovány jinak - typicky např. operačním systémem)

  • Na základě žádostí vydává a aktualizuje certifikáty

  • Výhody: Offline ověření, vysoká bezpečnost

  • Nevýhody: Komplexní na správu, nutné řešit distribuci kořenových klíčů CA

Vytvořeno: 27. 5. 2026, 11:57
Poslední aktualizace: 11. 6. 2026, 15:08