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