Asymetrická kryptografie
 
Matematické základy asymetrické kryptografie.
Přehled asymetrických algoritmů ve vztahu k NP složitým úlohám.
Protokol Diffie-Helmann. Algoritmus RSA. Algoritmus ElGamal. Kryptografie na eliptických křivkách.
Srovnání bezpečnosti symetrických a asymetrických šifer.
 

Asymetrická šifra
  • Šifra s veřejným klíčem
  • klíč pro dešifrování (privátní klíč) nelze výpočetně snadno získat z klíče pro zašifrování
  • klíč pro zašifrování (veřejný klíč) je různý od klíče pro dešifrování (odtud asymetrická šifra)
  • klíč pro zašifrování může být veřejně dostupný (odtud šifra s veřejným klíčem), aniž by se ohrozila bezpečnost zašifrovaného textu
  • Výhody asymetrických algoritmů
    • řeší problém s distribucí klíčů
    • možnost využití k podepisování
  • Nevýhody
    • pomalost
    • délky klíčů
    • obecně náchylné na Choosen-Plaintext Attack
  • Použití
    • šifrování dat (důvěrnost)
    • digitální podpis (nepopiratelnost)
    • výměna klíčů
  • pouze 3 známé algoritmy lze použít jak pro šifrování, tak podepisování
    • RSA (číselná faktorizace)
    • ELGamal (diskrétní logaritmus)
    • Rabinův (číselná faktorizace, druhá mocnina modulo složené n)
Matematické základy asymetrické kryptografie.
Přehled asymetrických algoritmů ve vztahu k NP složitým úlohám.

 
Diffie-Hellman
Diffie-Hellman představuje kryptografický protokol pro bezpečnou výměnu klíčů umožňující přes nezabezpečený kanál vytvořit mezi komunikujícími stranami šifrované spojení, bez předchozího dohodnutí šifrovacího klíče.
Výsledkem tohoto protokolu je vytvoření symetrického šifrovacího klíče, který může být následně použit pro šifrování zbytku komunikace.
Případný útočník může odposlouchávanou komunikaci zachytit, ovšem nerozluští ji.
Klíč je zkonstruován všemi účastníky komunikace a nikdy není poslán v otevřené formě.
Nevýhodou tohoto protokolu je bezbrannost proti útoku „Man in the Middle“2, protože neumožňuje autentizaci účastníků.
Tento protokol bez kombinace s jinými metodami je tedy vhodný pouze tam, kde útočník nemůže aktivně zasahovat do komunikace.
V dnešní době s rozvojem kryptografie pomocí eliptických křivek, vznikla nová verze protokolu Diffie-Hellman pod názvem ECDH, tedy Diffie-Hellman s podporou eliptických křivek.
Tento protokol je považován za bezpečný, neboť se nezveřejňuje nic kromě veřejných klíčů, které nejsou tajné a ani jedna strana nedokáže zjistit soukromý klíč té druhé, pokud by nevyřešila problém diskrétního logaritmu u eliptických křivek.
Veřejné klíče jsou buď neměnné (a shledané důvěryhodnými třeba pomocí certifikátů), nebo dočasné.
Dočasné klíče nejsou nutně ověřené, takže pokud je ověření vyžadováno, je třeba jej zajistit jinými způsoby.

 
RSA (Rivest, Shamir, Adleman)
Dnes zřejmě nejznámější a nejpoužívanější asymetrický kryptosystém, sloužící jak k šifrování, tak k tvorbě elektronického podpisu.
Algoritmus RSA se používá od roku 1977 drobnými úpravami dodnes a snad opravdu všude – u mobilních telefonů, bankomatů, elektronických podpisů atd.
Jedná se původně o patentovanou šifru, v roce 2000 byl uvolněn patentem chráněný algoritmus.
Princip RSA je založen na umocňování celých čísel modulo prvočíslo.
Bezpečnost tohoto kryptosystému je založena na faktu, že veřejný modulus je obtížné faktorizovat na prvočíselné faktory.
Nebylo dokázáno, že faktorizace N je nejjednodušší způsob prolomení RSA, je však nejjednodušší dosud nalezený způsob.
Proto tedy bezpečnost konkrétního RSA klíče vyžaduje, aby N bylo dostatečně velké a faktorizace N vyžadovala příliš mnoho výpočtů, aby byla proveditelná.
Na začátku roku 2010 bylo faktorizováno číslo s 231 dekadickými ciframi, což odpovídá 768bitů1.
Dnes je doporučováno používání velkých prvočísel 2048 bitů.

 
Princip algoritmu RSA

 
RSA a standardy PKCS
Pro implementaci algoritmu RSA a později i příbuzných šifrovacích byla vydána řada standardů, které přesně definují použití algoritmu RSA a související formáty datových struktur.
Tyto standardy známé jako PKCS (Public-key Cryptography Standards) začaly vznikat v roce 1991.
Dosud bylo vydáno 15 těchto standardů (PKCS#1 až PKCS#15).
PKCS se později staly základem mnoha jiných standardů, např. pro elektronickou poštu, internetové prohlížeče či pro oblasti bankovnictví.
Dnes jsou tyto standardy vytvářeny v širším kontextu, aby se dosáhlo co největší interoperability.
Tyto standardy jsou zahrnuty nebo jsou kompatibilní s dalšími formálními či neformálními standardy:
  • ANSI X9 (bankovní oblast),
  • PKIX (infrastruktura veřejných klíčů),
  • SET (platební transakce),
  • S/MIME (elektronická pošta),
  • SSL (internetové prohlížeče),
  • IEEE PI363 (skupina prestižního amerického institutu IEEE pracující na standardech různých kryptografických technik).
Algoritmus ElGamal
  • bezpečnost založena na NP-úplném problému získání diskrétního logaritmu v modulární celočíselné grupě.
  • Lze ho použít jak pro šifrování, tak pro podpis
  • není chráněn patenty
Kryptografie na eliptických křivkách

 
Eliptická křivka (EC)
  • množina bodů, která vyhovuje rovnici eliptické funkce
  • speciální podtřída kubických křivek
  • 1985 vynalezena možnost použití pro kryptosystém veřejného klíče
  • EC nad množinou reálných čísel je definována jako množina bodů (x,y) vyhovujících rovnici: y^2 = x^3 + ax + b
    • kde x, y, a, b jsou reálná čísla
    • jednoznačné určení křivky volbou koeficientů a, b
    • Př: a= -4, b= 0.67 dostaneme EC y^2 = x^3 -4x + 0.67 viz obrázek
  • EC může tvořit grupu, pokud člen x^3 + ax + b je nerozložitelný, neboli pokud platí 4a^3 + 27b^2 + b != 0
  • Grupa EC nad reálnými čísly se skládá:
    • z bodů odpovídajícím bodům na EC
    • z jednoho speciálního bodu O nazvaného "bod v nekonečnu"
  • Bod O plní funkci nulového prvku
  • Početní operace jsou definovány geometricky