náhled|upright=1.5|Příklad asymetrického šifrování Asymetrická kryptografie (kryptografie s veřejným klíčem) je v informatice typ kryptografických algoritmů, ve kterých se používá dvojice kryptografických klíčů. Algoritmus využívá jednosměrnou funkci, která znemožňuje použití stejného klíče pro šifrování i dešifrování. Tím se odlišuje od symetrické kryptografie, která používá jediný klíč. V asymetrické kryptografii je jeden klíč soukromý (privátní, „tajný“) a druhý veřejný, jehož pravost může být ověřitelná pomocí digitálního certifikátu.
Asymetrická kryptografie umožňuje zajistit nejen důvěrnost (znemožnit čtení nepovolané osobě), ale též autenticitu (identifikaci autora zprávy pomocí veřejného klíče) a integritu zprávy (zprávu nemohl nikdo pozměnit). Praktickými příklady použití je zabezpečená webová stránka HTTPS, např. internetové bankovnictví, nebo elektronický podpis.
Asymetrická kryptografie se začala používat od poloviny 70. let 20. století v souvislosti s rozvojem výpočetní techniky.
Základní principy Šifrovací klíč pro asymetrickou kryptografii sestává z dvou částí: jedna část se používá pro šifrování zpráv (a příjemce zprávy ani tuto část nemusí znát), druhá pro dešifrování (a odesilatel šifrovaných zpráv ji zpravidla nezná). Je vidět, že ten, kdo šifruje, nemusí s dešifrujícím příjemcem zprávy sdílet žádné tajemství, čímž eliminují potřebu výměny klíčů; tato vlastnost je základní výhodou asymetrické kryptografie.
Nejběžnější verzí asymetrické kryptografie je využívání tzv. veřejného a soukromého klíče: šifrovací klíč je veřejný, majitel klíče ho volně uveřejní, a kdokoli jím může šifrovat jemu určené zprávy; dešifrovací klíč je privátní (tj. soukromý), majitel jej drží v tajnosti a pomocí něj může tyto zprávy dešifrovat (existují i další metody asymetrické kryptografie, ve kterých je třeba i šifrovací klíč udržovat v tajnosti).
Je zřejmé, že šifrovací klíč e a dešifrovací klíč d spolu musí být matematicky svázány, avšak nezbytnou podmínkou pro užitečnost šifry je praktická nemožnost ze znalosti šifrovacího klíče spočítat dešifrovací.
Matematicky tedy asymetrická kryptografie postupuje následujícím způsobem: Šifrování c = f(m, e) Dešifrování m = g(c, d) V principu se mohou šifrovací a dešifrovací funkce lišit, zpravidla jsou však matematicky přinejmenším velmi podobné.
Mechanismy funkce Asymetrická kryptografie je založena na tzv. jednocestných funkcích, což jsou operace, které lze snadno provést pouze v jednom směru: ze vstupu lze snadno spočítat výstup, z výstupu však je velmi obtížné nalézt vstup. Nejběžnějším příkladem je například násobení: je velmi snadné vynásobit dvě i velmi velká čísla, avšak rozklad součinu na činitele (tzv. faktorizace) je velmi obtížný. (Na tomto problému je založen např. algoritmus RSA.) Dalšími podobnými problémy jsou výpočet diskrétního logaritmu či problém batohu.
Bezpečnost Některé kryptografické metody mohou být označeny za bezpečné na základě složitosti matematického problému jako prvočíselný rozklad násobku dvou velkých prvočísel nebo počítání diskrétního logaritmu. Toto je pouze matematický smysl bezpečnosti a existuje více různých definicí, dle kterých se může kryptografická metoda označit za bezpečnou.
Žádná metoda asymetrické kryptografie nemůže být bezpečná při použití nekonečného výpočetního výkonu (vždy je prolomitelná hrubou silou, tedy vyzkoušením všech potenciálních zpráv). Důkazy bezpečnosti spoléhají na existenci tzv. jednocestných funkcí (jejich existence je však nezodpovězenou otázkou), tedy funkcí, které lze snadno vyčíslit pro daný vstup (tedy s nízkou algoritmickou složitostí), ale je algoritmicky velmi složité pro daný výstup najít původní vstup. Tedy zašifrovat zprávu lze za zlomek sekundy, ale prolomit toto šifrování by na soućasných počítačích trvalo stovky let.
Jednou z aplikací asymetrické kryptografie je elektronický podpis. Uživatel, který chce poslat zprávu, tak spočítá její digitální podpis a ten pošle spolu se zprávou příjemci. Digitální podpis může být spočítán jedině pomocí odesílatelova privátního klíče, ale pro ověření stačí pouze veřejný klíč. V některých případech (např. RSA) jsou metody elektronického podpisu velmi podobné kryptografickým metodám. V jiných případech (např. DSA) algoritmus nepřipomíná žádnou kryptografickou metodu.
Pro dosažení ověřitelnosti a utajení odesílatel zprávu podepíše svým privátním klíčem, potom ji zašifruje veřejným klíčem příjemce.
Praktické úvahy
Poštovní analogie Analogie pro pochopení výhod asymetrického šifrování ve které si Alice a Bob posílají zprávy pomocí veřejné pošty. V tomto příkladu Alice posílá utajenou zprávu Bobovi a očekává utajenou odpověď od Boba.
Při použití symetrické kryptografie Alice vloží zprávu do schránky a zamkne pomocí visacího zámku, ke kterému má klíč. Schránku poté pošle poštou Bobovi, ten ji otevře použitím kopie Alicina klíče a přečte si zprávu. Bob pak může použít stejný zámek pro odeslání jeho odpovědi.
U asymetrické kryptografie má každý svůj visací zámek. Nejdříve Alice požádá Boba, aby jí poslal otevřený zámek bez klíče poštou. Poté jím Alice zamkne zprávu do schránky a tu pošle Bobovi. Bob potom může otevřít zámek svým klíčem a přečíst si zprávu od Alice. K poslání odpovědi musí mít Alicin otevřený zámek, kterým zamkne schránku a pošle ji zpátky Alici.
Největší výhodou tak je, že Alice ani Bob nepotřebují posílat kopii jejich klíče. Tímto se zamezí vytvoření kopie klíče někým třetím během přenosu a odposlouchávání všech následně poslaných zpráv mezi Alicí a Bobem. Nepotřebují tedy věřit poště tolik jako v prvním případě. Navíc, pokud by Bob někomu dovolil si zkopírovat jeho klíč, tak by byly kompromitovány pouze zprávy pro Boba, ale všechny zprávy pro Alici by zůstaly utajené.
V dalším případě mají Bob a Alice každý svůj zámek. Nejdříve Alice vloží zprávu do schránky a zamkne ji svým klíčem, který má jen ona. Potom schránku poštou pošle Bobovi. Ten schránku zamkne i svým zámkem a pošle ji zpátky Alici. Alice odebere svůj zámek a schránku s jedním zámkem pošle Bobovi, který tento svůj zámek otevře svým klíčem. Toto je ovšem možné pouze tehdy, pokud je použitá šifra komutativní, což je taková šifra, ve které můžeme zaměnit pořadí šifrování a dešifrování: A*B*C = A*C*B = C*B*A. Například, nechť E1() a E2() jsou dvě šifrovací funkce a M je zpráva. Alice ji zašifruje použitím E1() a pošle E1(M) Bobovi. Bob pak zašifruje zprávu, vznikne E2(E1(M)) a výsledek pošle Alici. Nyní Alice dešifruje E2(E1(M)) použitím E1(). Teď má E2(M), takže když toto pošle Bobovi, bude schopen to dešifrovat použitím E2() a výsledek bude M. Tento protokol může být použit například pro zabezpečenou výměnu klíčů.
Dva propojené klíče Ne všechny asymetrické klíčové algoritmy pracují přesně způsobem uvedeným výše v analogii. Nejčastěji mají tu vlastnost, že Alice i Bob vlastní dva klíče, jeden pro šifrování a jeden pro dešifrování. V bezpečném asymetrickém šifrovacím schématu by neměl být privátní klíč odvoditelný z veřejného klíče. Toto je známé jako šifrování veřejného klíče, protože šifrovací klíč může být publikován, aniž by byla ohrožena bezpečnost zpráv zašifrovaných tímto klíčem.
V analogii výše Bob může zveřejnit pokyny jak vytvořit veřejný klíč. Nicméně je známo, že z pokynů je nemožné vyvodit, jakým způsobem přesně vytvořit privátní klíč. Ti, kteří chtějí posílat zprávy Bobovi, musí použít veřejný klíč k zašifrování zprávy. Poté může Bob použít svůj privátní klíč k rozšifrování této zprávy.
Jiná situace může nastat, pokud si Alice i Bob vygenerují klíč náhodně a poté se navzájem kontaktují a porovnávají „hloubky zářezů“ na jejich klíčích. Poté, co zjistí rozdíly, se vytvoří „prostor“ se speciálním zámkem, který má každý pin uvnitř rozdělen na dva další piny, které odpovídají číslům jejich klíčů. Nyní může být tento „prostor“ odemčen kterýmkoli z těchto klíčů a Alice a Bob si mohou vzájemně posílat zprávy zabezpečeným způsobem v rámci tohoto „prostoru“.
Slabiny Samozřejmě, že je zde možnost, že by někdo mohl ukradnout Alici nebo Bobovi jejich privátní klíč. Mezi symetrickými klíčovými šifrovacími algoritmy je Vernamova šifra jediná, u které lze prokázat, že je bezpečná proti útočníkovi – bez ohledu na to, jak velký výpočetní výkon má k dispozici. Nicméně není zde žádné schéma veřejného klíče s touto vlastností, protože všechna schémata veřejných klíčů jsou náchylná k nalezení klíče pomocí útoku hrubou silou. Takovéto útoky jsou nepraktické, pokud množství výpočtů potřebných k úspěchu (jenž Claude Shannon nazval work factor) je mimo dosah všech potenciálních útočníků. V mnoha případech může být work factor jednoduše zvětšen vybráním delšího klíče. Naproti tomu jiné algoritmy mohou mít mnohem menší work factor, tudíž je odpor k útoku hrubou silou irelevantní. Některé speciální a specifické algoritmy byly vyvinuty jako obrana proti útokům na některé šifrovací algoritmy veřejných klíčů – jak RSA, tak ElGamal šifrování znají útoky, které jsou mnohem rychlejší než útoky hrubou silou. Tyto faktory se v posledních desetiletích dramaticky změnily, a to jak s klesající cenou výpočetního výkonu, tak s novými matematickými objevy.
V praxi se lze často těmto rizikům vyhnout volbou dostatečně dlouhého klíče, aby doposud nejlepší algoritmus trval tak dlouho, aby neměl rozumnou šanci na úspěšné prolomení kódu.
Ovšem neexistuje matematický důkaz o bezpečnosti asymetrické kryptografie založené na faktorizaci či diskrétním logaritmu. Navíc existuje možnost, že šifry prolomí kvantový počítač. Proto se někteří odborníci obávají, že může přijít "kryptokalypsa" (náhlé zneplatnění digitálních podpisů, digitálních měn, odtajnění dokumentů). Tudíž se pozornost obrací k algoritmům s matematicky dokázanou bezpečností, které neprolomí ani kvantový počítač (post-quantum cryptography). Patří sem například kryptografie na celočíselných mřížích – např. algoritmy NTRUhttp://crypto-world.info/news/index.php?prispevek=22518&sekce=s - Kryptografie NTRU je nyní dostupná jako open source či GGH.
Kromě odolnosti proti útoku konkrétní dvojice klíčů musí být zvážena bezpečnost certifikační hierarchie při rozmisťování systémů veřejných klíčů. Některé certifikační autority, obvykle účelový program běžící na serveru, ručí za identity přidělené ke specifickým privátním klíčům poskytnutím digitálního certifikátu. Digitální certifikáty veřejných klíčů platí obvykle po dobu několika let, takže související privátní klíče musí být v průběhu této doby uchovány v bezpečí. Pokud je privátní klíč využitý k vytvoření certifikátu v PKI hierarchii serveru ohrožen nebo náhodně zveřejněn, pak je možný Man in the middle útok, čímž činí každý podřízený certifikát zcela nechráněný.
Hlavní slabiny byly odhaleny pro několik dříve slibných asymetrických klíčových algoritmů. U algoritmu Problém batohu bylo nedávno zjištěno, že může být prolomen (po vývoji nového útoku). Nedávno byly také některé útoky založené na pečlivém měření přesného množství času, za který určitý hardware zašifruje prostý text, který byl použit na zjednodušení hledání pravděpodobných dešifrovacích klíčů (viz útok postranním kanálem). Pouhé užívání asymetrických klíčových algoritmů nezajistí bezpečnost. Velká část aktivního výzkumu, který v současné době probíhá, se zabývá tím, jak objevit a jak se chránit před novými útočnými algoritmy.