Asymetrické
Asymetrická kryptografie
Příklad asymetrického šifrování
Asymetrická kryptografie (kryptografie s
veřejným klíčem) je skupina kryptografických metod, ve kterých se pro šifrování
a dešifrování používají odlišné klíče. To je základní rozdíl oproti symetrické
kryptografii, která používá k šifrování i dešifrování jediný klíč.
Kromě očividné možnosti pro utajení komunikace se asymetrická kryptografie používá také pro elektronický podpis, tzn. možnost u dat prokázat jejich autora.
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[zdroj?].
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.
Na rozdíl od Vernamovy šifry (která by používala neovlivnitelný dokonalý generátor náhodných čísel a nikoli generátor pseudonáhodných čísel) se žádná metoda asymetrické kryptografie neukázala jako bezpečná při použití nekonečného výpočetního výkonu. Důkazy bezpečnosti těchto metod tedy počítají s omezeným výpočetním výkonem a říkají například že „metoda je nerozluštitelná pomocí osobního počítače za 1000 let“, nebo „tento algoritmus je bezpečný pokud nedojde k objevení lepší metody pro faktorizaci“.
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 potencioná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[1] č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ší potencioná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é sami 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 potencioná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.