Asymetrická kryptografie je kryptografický systém, ve kterém se používá k šifrování místo jednoho klíče dva klíče. Prvním je klíč veřejný e, který můžeme zveřejnit a slouží pro zašifrování zprávy a druhý klíč d je soukromý, známý pouze adresátovi zprávy a používá se pro rozšifrování zprávy.
| Šifrování $$c = encrypt(m, e)$$ |
Dešifrování $$m = decrypt(c, d)$$ |
Asymetrická kryptografie poskytuje celou řadu schémat, ale bezpečnost většiny implementací je postavena na třech matematických problémech, které nejsou na klasickém (ne kvantovém) počítači vypočítatelné v polynomiálním časem. Jde o problém faktorizace čísel, problém diskrétního logaritmu a problém diskrétního logaritmu eliptických křivek. Použitá knihovna LibreSSL podporuje RSA, DSA a pro eliptické křivky pak ECDSA a ECDH.
Jednosměrná funkce (one-way)
První aplikace jednosměrné funkce v kryptografii byla představena v roce 1976 Diffie a Hellmanem.
Definice:
Funkce f : X → Y, pro kterou je snadné z jakékoli hodnoty x ∈ X vypočítat hodnotu y = h(x). Avšak nalézt vstupní vzor x je bez znalosti klíče výpočetně nemožné (∈ NP), ale teoretický možné.
Problém faktorizace čísel
Máme dvě velká čísla p a q, vypočítáme jejich součin n = p⋅q Pokud však známe pouze složené číslo n, pak je výpočetně náročné nalézt oba jeho faktory p a q.
Na tomto principu funguje kryptosystém RSA.
Problém diskrétního logaritmu
Pokud známe kladná čísla x, g ∈ ℤ a velké prvočíslo p, pak můžeme snadno vypočítat mocninu y ≡ gx mod p. Avšak pokud známe pouze čísla y, g a p, pak nalezení exponentu x ≡ loggy mod p je výpočetně náročné a je v obecném případě prakticky nemožné v polynomiálním čase.