Asymetrická kryptografie

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éž autentizaci, identifikaci autora zprávy pomocí veřejného klíče, a autentičnost zprávy, zprávu nemohl nikdo vytvořit ani pozměnit bez vlastnictví privátního klíče. 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 NTRU č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.

Další potenciálně slabé místo zabezpečení při použití asymetrických klíčů je možnost Man in the middle útoku, při kterém je komunikace veřejných klíčů zachycena třetí osobou (prostředníkem), a poté upravena tak, aby místo nich produkovala odlišné veřejné klíče. Šifrované zprávy a odpovědi musí být také zachyceny, dešifrovány a znovu zašifrovány útočníkem, který ve všech případech používá správné veřejné klíče pro různé komunikační segmenty, aby se zamezilo podezření. Může se zdát být obtížné implementovat tento útok v praxi, ale není to nemožné, pokud používáte nezabezpečené médium (např. veřejné sítě, jako je Internet či bezdrátové formy komunikace). Útok může velice snadno provést například zlomyslný zaměstnanec u poskytovatele Internetu. V poštovní analogii by Alice znala způsob, kterým by se ujistila, že klíč na vráceném paketu skutečně patří Bobovi, než se odstraní její klíč a odešle paket. V odlišném případě by klíč vložený na paket mohl pocházet od zaměstnance poskytovatele internetu a mohl by předstírat, že je Bob, aby oklamal Alici.

Jedním ze způsobů, jak předejít takovýmto útokům, je použití certifikační autority. Tento orgán poskytuje uživatelům digitální certifikát, který je odolný proti násilnému otevření. Tyto certifikáty jsou podepsány datovými bloky tak, že veřejný klíč patří k určité osobě, společnosti, nebo jinému subjektu. Tento přístup má také své slabiny. Certifikační autoritě vydávající certifikát musíme věřit, že správně zkontrolovala identitu držitele klíče a zajistila správnost veřejného klíče v době vydání. Také musí být provedena opatření se všemi účastníky, aby zkontrolovali všechny své certifikáty před chráněným začátkem komunikace. Například webové prohlížeče jsou dodávány s dlouhým seznamem certifikátů, které jsou podepsané samy sebou od poskytovatelů PKI. Útočník, který by zkorumpoval byť jedinou z těchto certifikačních autorit do vydání certifikátu pod falešným veřejným klíčem, by pak mohl využít Man in the middle útok tak snadno, jako kdyby se certifikát nepoužil vůbec. Přes tyto teoretické a potenciální problémy je tento přístup široce používán. Například SSL protokol a jeho nástupce TLS protokol, které se běžně používají pro zajištění bezpečnosti pro webové prohlížeče tak, aby mohly být bezpečně odeslány podrobnosti o kreditní kartě do internetového obchodu.

Výpočetní náročnost

Známé algoritmy pro asymetrické šifrování jsou poměrně náročnější než symetrické algoritmy podobné úrovně bezpečnosti. Hlavní rozdíl je užívání podstatně delších klíčů což má vážné důsledky pro jejich praktické užití. Většinou se z důvodu efektivnosti používají v Hybridním šifrování. V hybridním šifrování nejdříve jedna strana vygeneruje společný klíč a tento o poznání kratší klíč je zašifrován veřejným klíčem příjemce. Každý příjemce pak použije vlastní privátní klíč k rozšifrování společného klíče. Jakmile mají všechny strany společný klíč, pro šifrování a dešifrování zpráv mohou používat rychlejší symetrické algoritmy. 

Spojení veřejného klíče s vlastníkem

Propojení veřejného klíče s jeho vlastníkem musí být korektní, jinak může dojít k tomu, že i kdyby algoritmus fungoval perfektně, není ve svém použití bezpečný. Jako ve většině užití šifrování, jsou kryptografické protokoly použité pro vytvoření a ověření tohoto propojení velice důležité. Propojení veřejného klíče s jeho majitelem je obvykle provedeno pomocí protokolu implementujícího PKI. Tyto protokoly umožňují, aby platnost propojení byla potvrzena důvěryhodnou třetí stranou a to ve formě hierarchie certifikačních autorit (např. X.509), místního modelu důvěry (např. SPKI) nebo sítě důvěry, jako té, která je původně použita v PGP a GPG a stále je s nimi do jisté míry použitelná. Nehledě na kryptografickou důvěru v protokoly samotné, propojení mezi veřejným klíčem a jeho majitelem je ve finále subjektivním hodnocením na straně důvěryhodné třetí strany, jelikož veřejný klíč je matematická entita a majitel a propojení mezi klíčem a majitelem matematické entity nejsou. Z tohoto důvodu, formalismus infrastruktury privátních klíčů musí jasně uvést protokoly použité pro toto hodnocení. Například komplexní standard X.509, který nebyl nikdy plně implementován, dovoluje certifikační autoritě identifikovat své protokoly pomocí identifikátoru objektů který pak slouží jako rejstřík katalogu protokolů. Protokoly mohou existovat z různých důvodů od anonymity až po vojenské utajení.

Spojení s událostmi reálného světa

Veřejný klíč bude znám velkému a v podstatě neznámému počtu uživatelů. Může tak trvat poměrně dlouho než všechny události vyžadující odvolání nebo nahrazení veřejného klíče dorazí ke všem uživatelům, kteří musí být informováni (tj. všem uživatelům vlastnícím již neplatný klíč). Z tohoto důvodu systémy, které musí reagovat na události v reálném čase (např. systémy zabývající se národní bezpečností), by neměly používat asymetrické šifrování bez důkladné údržby.

Odvolání klíče

Chybné (nebo úmyslně škodlivé) odvolání několika (nebo všech) klíčů pravděpodobně (v druhém případě jistě) způsobí kompletní selhání systému. Toto se může stát, pokud mohou být klíče odvolány jednotlivě, ale existují přístupy, které mohou snížit reálnou šanci, že tento problém nastane. Například u certifikátů můžeme použít takzvaný "princip sloučení". Takový princip může být "Alice a Bob mají možnost odvolat certifikát". Teď jen Alice a Bob (společně) mohou certifikát odvolat, a ani Alice, ani Bob nemohou odvolat certifikát sami. Na druhou stranu, odvolání certifikátu teď vyžaduje, aby byli Alice i Bob k dispozici, což vytváří problém spolehlivosti. Z pohledu bezpečnosti to vytváří slabé místo v systému odvolání klíče. Úspěšný DoS útok na Alici nebo Boba (nebo oba) zablokuje možnost odvolání. Ve skutečnosti jakékoli rozdělení autority mezi Alici a Boba bude mít stejný účinek.

Protože princip dovolující odvolání klíče je silný, mechanismus kontroly by měl mít zároveň co nejvíce účastníků (aby se bránil proti jakémukoli útoku) a zároveň co nejméně účastníků (aby mohl být klíč odvolán bez nebezpečných průtahů). Certifikáty s veřejným klíčem s dobou platnosti jsou nedostatečné z důvodu toho, že datum ukončení platnosti nemusí korespondovat s potřebou odvolání certifikátu kvůli událostem reálného světa, ale takovéto certifikáty není nutné shánět po celém systému a ani uživatelé nemusí být v neustálém kontaktu mezi sebou.  

Zástupci

• RSA
• ElGamal
• Kryptografie nad eliptickými křivkami
• Kryptografie s Lucasovými funkcemi
• Diffie-Hellman
• Digital Signature Algorithm
• Merkle-Hellman (už zastaralý)

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Public-key cryptography na anglické Wikipedii.

Externí odkazy

• Obrázky, zvuky či videa k tématu asymetrická kryptografie na Wikimedia Commons
• Asymetrická kryptografie v České terminologické databázi knihovnictví a informační vědy (TDKIV)
• [1] – názorné video

Autoritní data	TDKIV: 000000668 BNF: cb13554544f (data) GND: 4209133-0 LCCN: sh00004804 NDL: 00966793 NLI: 987007290951705171