Asymetrická kryptografie

Asymetrická kryptografie (anglicky public-key cryptography) se od té symetrické liší tím, že k šifrování i dešifrování zprávy jsou použity odlišné klíče a není mezi nimi triviální vztah, který by ze znalosti jednoho umožnil rychle vypočítat druhý. Tato vlastnost je zvláště výhodná při síťové komunikaci. Adresát si vygeneruje dva klíče: veřejný a privátní. Klíč veřejný dá k dispozici všem účastníkům, ti jej mohou využívat, pokud chtějí zaslat zprávu adresátovi. Pokud si přijatou zprávu zašifrovanou pomocí svého veřejného klíče chce adresát přečíst, musí ji dešifrovat pomocí svého klíče privátního (který již má k dispozici pouze adresát).

Možné útoky

Prvním možným útokem je vydávání se za jiného odesílatele. Příjemce nemá možnost jednoduše zjistit, od koho zpráva skutečně přišla (veřejný klíč je k dispozici všem). Tomu se dá předejít podepisováním zprávy.

Dalším možným útokem je útok přes prostředníka. Pokud někdo je schopen zcela ovládnout komunikační kanál, může jej rozpojit a tváří se sám jako příjemce. Případně na druhé straně vysílá původnímu příjemci. Tomuto se dá předejít přes zabezpečenou distribuci klíčů.

Základní principy

Většina moderních asymetrických kryptosystémů je postavena primárně na dvou principech. Prvním je časová obtížnost řešení diskrétního logaritmu a druhým je časová obtížnost řešení faktorizace celých čísel (tj. hledání rozkladu čísla na součin prvočísel).

Problém faktorizace celých čísel

Problém faktorizace celých čísel spočívá v nalezení prvočíselného rozkladu daného čísla n ve tvaru:

n = ∏_∀i p_i^a_i = p₁^a₁ · p₂^a₂... p_r^a_r

kde a_i představuje přirozená čísla (mocniny daného prvočísla) a p_i jsou prvočísla (platí pro všechna i, pro která má výraz smysl). Takový rozklad je dle základní věty aritmetiky definován jednoznačně (až na pořadí prvočísel, které nehraje roli).

Pro malá čísla je hledání tohoto rozkladu triviální záležitost. Pro větší čísla zabírá enormní množství času. Přičemž je charakteristické, že ověření, zdali jsou daná prvočísla skutečně rozkladem daného čísla je velmi rychlá záležitost. Právě na těchto dvou tvrzeních stojí určitá asymetrické šifry postavené na problému faktorizace čísel (typicky RSA). Existují některé numerické metody, které hledání rozkladu urychlují, základní metoda se nazívá kvadratické síto (Quadratic Sieve), další známá metoda se nazývá GNFS. Výpočet faktorizace je rychlý na kvantových počítačích, kde existuje tzv. Shorův algoritmus, problém je, že nejsou k dispozici dostatečně výkonné kvantové počítače.

Problém diskrétního logaritmu

Je trochu složitější, nežli problém faktorizace celých čísel. Předpokládejme, že máme zadaná přirozená čísla g, b a p. Hledáme přirozené číslo k takové, že platí následující výraz:

g^k mod p = b

Platí opět to, co bylo řečeno o problému faktorizace čísel. Ověřit, zdali číslo k řeší tuto rovnici je triviální (a hlavně rychlá) záležitost, ale nalézt jeho konkrétní hodnotu (pro velká a vhodně zvolená čísla g, b a p) je velmi časově náročná záležitost. Oba problémy jsou do určité míry propojeny. Nejefektivnější numerická metoda pro řešení tohoto problému se nazývá index calculus. Stejně jako faktorizaci čísel lze i tento problém vyřešit rychle na kvantových počítačích pomocí Shorova algoritmu (jen je stále potíž s tím, že existující kvantové počítače stále nejsou dostatečně efektivní, platí při psaní tohoto textu v roce 2018).

Základní kryptosystémy a kryptoanalytické metody