Asymetrická šifra

Šifrovanie verejným kľúčom alebo asymetrické šifrovanie je oblasť kryptografických systémov, ktoré používajú páry súvislých kľúčov. Každý kľúčový pár pozostáva z verejného kľúča a príslušného privátneho kľúča. Páry sú generované kryptografickým algoritmom založeným na matematických problémoch nazývaných jednosmerné funkcie. Zabezpečenie kryptografie verejného kľúča závisí na bezpečnej úschove privátneho kľúča, verejný kľúč môže byť verejne distribuovaný a zabezpečenie nebude narušené.
V šifrovacom systéme verejného kľúča vie ktokoľvek s verejným kľúčom zašifrovať správu, čím sa získa zašifrovaný text, ale iba tí ktorí majú zodpovedajúci privátny kľúč vedia odšifrovať zašifrovaný text aby získali pôvodnú správu.   
Napríklad, novinár vie publikovať verejný kľúč z páru šifrovacích kľúčov na webovej stránke aby zdroje mohli posielať tajné správy do novinárskych organizácií v zašifrovanej forme. Iba novinár, ktorý vlastní príslušný privátny kľúč vie odšifrovať šifry aby získal zdrojové správy – ak by útočník odchytil zašifrovaný email na ceste ku novinárovi, nevie dešifrovať zašifrovaný text. Avšak, šifrovanie verejným kľúčom neskryje metadáta - akým počítačom alebo z akej adresy sa posielali správy, kedy ich posielali alebo ako dlho to trvalo. Šifrovanie verejným kľúčom tiež samé o sebe nepovie príjemcovi čokoľvek o odosielateľovi správy – skrýva obsah v šifrovaných správach ktoré môžu byť dešifrované privátnym kľúčom.
V systéme digitálneho podpisu, odosielateľ vie použiť privátny kľúč spolu so správou aby vytvoril podpis. Ktokoľvek so zodpovedajúcim verejným kľúčom si vie overiť či sa podpis zhoduje so správou, ale falšovateľ, ktorý nepozná privátny kľúč, nemôže vygenerovať akýkoľvek pár správ/podpisov ktoré by prešli overením s verejným kľúčom.
Napríklad, vydavateľ softvéru môže vytvoriť pár podpisových kľúčov a zahrnúť verejný kľúč do softvéru inštalovaného na počítačoch. Neskôr, vydavateľ vie distribuovať aktualizáciu softwaru  podpísanú pomocou privátneho kľúča a akýkoľvek počítač prijímajúci aktualizáciu vie potvrdiť, že je pravá overením podpisu pomocou verejného kľúča. Dovtedy pokiaľ vydavateľ softvéru udrží svoj privátny kľúč v tajnosti, falšovateľ softvéru, ktorý by chcel distribuovať škodlivé aktualizácie do počítačov, by tieto počítače nepresvedčili, že akákoľvek škodlivá aktualizácia je pravá.
Algoritmy verejného kľúča sú základné bezpečnostné prvky v moderných kryptosystémoch, vrátene aplikácií a protokolov, ktoré poskytujú zabezpečenie dôvernosti, autentickosti a nepopierateľnosti elektronického komunikovania a dátového úložiska. Sú obsiahnuté v mnohých internetových štandardoch ako sú TLS, SSH, S/MIME a PGP. Niektoré algoritmy verejných kľúčov poskytujú distribúciu kľúčov a utajenia (napr., Diffieho-Hellmanova výmena kľúčov), niektoré poskytujú digitálny podpis (napr., Algoritmus digitálneho podpisu (DSA)) a niektoré poskytujú oboje (napr., RSA). V porovnaní so symetrickým šifrovaním je asymetrické šifrovanie pomalšie než dobré symetrické šifrovanie, a na mnoho účelov až príliš pomalé. Dnešné kryptosystémy (napr., TLS, Secure Shell) používajú obe - symetrické šifrovanie a asymetrické šifrovanie, často používajú asymetrické šifrovanie pre bezpečnú výmenu tajného kľúča, ktorý je potom použitý na symetrické šifrovanie. 
Popis.
Pred prvou polovicou 70-tych rokov, všetky šifrovacie systémy využívali algoritmus symetrického kľúča, v ktorom ten istý kryptografický kľúč bol použitý spolu so šifrovacím algoritmom na strane odosielateľa aj prijímateľa a tieto údaje obaja museli držať v tajnosti. Z tohoto dôvodu musel byť kľúč v každom takomto symetrickom systéme vymenený medzi účastníkmi komunikácie nejakým bezpečným spôsobom pred samotným začatím šifrovania – napríklad, cez iný zabezpečený kanál (telefón, bezpečnostná schránka, osobné stretnutie...). Táto požiadavka nie je nikdy jednoduchá a s rastúcim počtom účastníkov sa stáva nezvládnuteľnou, alebo keď zabezpečené kanály nie sú k dispozícii, alebo keď sa kľúče často menia. Najmä, pokiaľ správy majú byť oddelené od ostatných používateľov, pre každý možný pár používateľov je potrebný samostatný kľúč.
V asymetrickej krypotgrafii môžu byť verejné kľúče otvorene šírené a iba zodpovedajúce privátne kľúče potrebujú byť držané v tajnosti.
Dve z najznámejších spôsobov použitia verejného kľúču v kryptografii sú:
Jeden z dôležitých problémov je dôvera/dôkaz, či je konkrétny verejný kľúč pravý, t.j. že je správny a patrí danej osobe alebo subjektu a nebol sfalšovaný alebo vymenený nejakou (možno škodlivou) treťou stranou. Tu je niekoľko možných prístupov :
Infraštruktúra verejného kľúča (PKI), pri ktorej jedna alebo viac tretích strán – známych ako aj certifikačné autority – certifikujú vlastníctvo kľúčových párov. Na tomto je založený protokol TLS. To znamená že PKI systém (software, hardware a riadenie) je považovaný za dôveryhodný všetkými zapojenými.
„Sieť dôvery“ umožňuje decentralizovať overenie kľúčov a nespoliehať sa výlučne na certifikačné autority. Funguje to tak, že ak si napr. Alica overila platnosť Braňovho kľúča cez bezpečný kanál (napr. telefónom) a Cyril si podobne overil platnosť Alicinho kľúča, tak aj Cyril bude dôverovať kľúčom, ktoré overila Alica, teda aj Braňovmu kľúču. PGP používa tento prístup v súčinnosti s vyhľadávaním v DNS. DKIM systém, ktorý digitálne podpisuje e-maily taktiež používa tento prístup. 
Aplikácie.
Najviac zrejmá aplikácia šifrovacieho systému verejného kľúča je šifrovanie komunikácie pre poskytnutie dôvernosti – správa ktorú odosielateľ zašifroval pomocou prijímateľovho verejného kľúča, môže byť odšifrovaná iba prijímateľovým privátnym kľúčom.
Ďalšia aplikácia v kryptografii verejného kľúča je digitálny podpis. Schéma digitálneho podpisu môže byť použitá pre potvrdenie totožnosti odosielateľa.
Systémy „nepopierateľnosti“ používajú digitálne podpisy na ubezpečenie, že nejaká strana v komunikácii nemôže úspešne spochybniť svoje autorstvo na dokumente alebo komunikácii.
Ďalšie aplikácie postavené na tomto základe zahŕňajú: digitálnu hotovosť, heslom overenú výmenu kľúča, služby časovej pečiatky a protokoly nepopierateľnosti.
Hybridné kryptosystémy.
Pretože algoritmy asymetrického kľúča sú skoro vždy oveľa viac výpočtovo náročnejšie než tie symetrické, je bežné použiť algoritmus výmeny verejného/privátneho "asymetrického" kľúča na zašifrovanie a výmenu "symetrického" kľúča, ktorý je potom použitý kryptografiou symetrického kľúča pre prenášanie dát pomocou dohodnutéhp "symetrického" kľúča pre šifrovací algoritmus verejného kľúča. PGP, SSH a SSL/TLS skupina schém používajú túto procedúru; volajú sa hybridné kryptosystémy. Počiatočná výmena kľúčov založená na asymetrickej kryptografii na zdieľanie serverom vygenerovaného symetrického kľúča zo servera ku klientovi má tú výhodu, že nevyžaduje aby sa symetrický kľúč vopred zdieľal manuálne, napr. vytlačený na papieri alebo cez disky prepravované kuriérom, pričom poskytuje väčšiu dátovú priepustnosť kryptografie symetrického kľúča oproti kryptografie asymetrického kľúča pre zvyšok zdieľaného pripojenia. 
Zraniteľnosti.
Pre všetky systémy súvisiace s bezpečnosťou, je dôležité identifikovať potencionálne slabiny a zraniteľnosti. Okrem zlého výberu algoritmu asymetrického kľúča (je tu viacero, ktoré sú široko považované za uspokojivé) alebo pri použití príliš krátkeho kľúča, hlavným bezpečnostným rizikom je to, že privátny kľúč kľúčového páru sa stane známym. Všetka bezpečnosť správ, autentifikácia, atď. ..., by bola stratená.
Algoritmy.
Všetky schémy verejného kľúča sú teoreticky náchylné na hľadanie kľúča hrubou silou. Avšak, takýto útok je nepraktický pokiaľ množstvo výpočtov potrebných na úspech – Claude Shannon to pomenoval ako „pracovný faktor“ – je mimo možností všetkých potenciálnych útočníkov. U mnohých prípadov, pracovný faktor môže byť jednoducho zvýšený pomocou voľby dlhšieho kľúča. Ale ostatné algoritmy môžu mať oveľa nižšie pracovné faktory, takže odolnosť voči útoku hrubou silou (napr. z dlhších kľúčov) je nepodstatná. Niektoré špeciálne a špecifické algoritmy boli vyvíjané, aby pomohli pri napadnutí šifrovacích algoritmov verejného kľúča; obe RSA a EIGamal šifrovania majú známe  útoky, ktoré sú omnoho rýchlejšie než prístup hrubou silou. Žiadny z nich však nie je dostatočne vylepšený aby boli skutočne praktické.
Závažnejšie problémy sa našli na dovtedy sľubných algoritmoch asymetrického kľúča. Algoritmus „knapsack packing“ prestal poskytovať zabezpečenie správ po tom, čo boli vyvinuté nové útoky. Ako so všetkými kryptografickými funkciami, implementácie verejného kľúča môžu byť zraniteľné voči útokom vedľajšieho kanálu, ktoré zneužíva informačné úniky aby zjednodušili hľadanie tajného kľúča. Tie sú často nezávislé od použitého algoritmu. Prebieha výskum zameraný na objavenie a aj ochranu pred novými útokmi.
Podvrhnutie verejných kľúčov.
Ďalšia potenciálna bezpečnostná zraniteľnosť je používanie asymetrických kľúčov pri ktorých je možnosť man-in-the-middle útoku (MITM), je to zachytávanie komunikácie pri ktorej sa vymieňajú verejné kľúče treťou stranou („man-in-the-middle“) a potom upravovanie tak, aby namiesto toho príjemca dostal iné verejné kľúče. Zašifrované správy a odpovede musí útočník vo všetkých prípadoch – zachytiť, dešifrovať a znovu zašifrovať aby nevzbudil podozrenie, pričom používa správny verejný kľúč pre rôzne komunikačné segmenty.
Komunikácia nie je bezpečná tam, kde sa dáta prenášajú spôsobom, ktorý by umožňoval odpočúvanie. Komunikácia je obzvlášť nebezpečná keď odpočúvaniam sa nedá zabrániť alebo monitorovať odosielateľom.    
Útok MITM môže byť ťažko realizovateľný kvôli moderným bezpečnostným protokolom. Avšak, úloha sa stane jednoduchšia keď odosielateľ využíva médiá, ktoré neposkytujú vysokú bezpečnosť, napr.: verejné siete, internet alebo bezdrôtovú komunikáciu. Pri týchto prípadoch útočník dokáže kompromitovať komunikačnú infraštruktúru skôr než samotné dáta. Hypoteticky, ľstivý zamestnanec poskytovateľa internetových služieb (ISP) môže považovať tento útok za relatívne jednoduchý. Zachytenie verejného kľúča by vyžadovalo iba vyhľadanie kľúča pri jeho odoslaní cez komunikačný hardware poskytovateľa internetových služieb; v správne realizovaných schémach asymetrického kľúča to nie je významné riziko.
Pri niektorých pokročilých útokoch MITM, jedna strana komunikácie uvidí originálne dáta zatiaľ čo druhá strana príjme pozmenený variant. Asymetrické útoky MITM dokážu zabrániť používateľom zistiť, že ich pripojenie je kompromitované. To platí aj vtedy, keď je známe že údaje jedného užívateľa boli kompromitované, pretože druhému používateľovi sa tieto údaje zdajú byť v poriadku. Toto môže viesť ku zmätočným situáciám v zmysle „musí to byť chyba na tvojej strane!“ aj keď to nie je chyba ani jedného z používateľov. Teda, MITM útokom sa dá úplne zabrániť iba vtedy, ak je komunikačná infraštruktúra fyzicky ovládaná jednou alebo oboma stranami; napríklad prostredníctvom káblovej trasy vo vlastnej budove odosielateľa. Stručne povedané, verejné kľúče sú jednoduchšie na zmenenie, ak je odosielateľom používaný komunikačný hardware kontrolovaný útočníkom. 
Infraštruktúra verejného kľúča.
Jedným zo spôsobov ako zabrániť takýmto útokom je použitie infraštruktúry verejného kľúča (PKI); je to súbor rolí, politík a procedúr potrebných na vytvorenie, spravovanie, distribuovanie, využívanie, uloženie a odvolávanie digitálny certifikátov a spravovanie šifrovania verejným kľúčom. Avšak, má to potenciálne slabosti.  
Napríklad, certifikačnej autorite, ktorá vydáva certifikáty musia dôverovať všetky zúčastnené strany, aby sa riadne skontrolovala identita držiteľa kľúča, aby bolo možné sa uistiť o správnosti verejného kľúča keď sa vydáva certifikát, aby sme zabránili počítačovému pirátstvu a aby sme dosiahli vytvorenie dohody so všetkými zúčastnenými na skontrolovaní všetkých ich certifikátov predtým, ako sa môže začať chránená komunikácia. Napríklad, webové prehliadače sú zásobované s dlhým zoznamom certifikátov dôveryhodných certifikačných autorít, ktoré potom certifikujú buď kľúče koncových používateľov alebo kľúče sprostredkujúcich certifikačných autorít. Útočník, ktorý by dokázal podviesť jednu z týchto certifikačných autorít, aby mu vydala certifikát pre falošný verejný kľúč sprostredkujúcej certifikačnej autority, by potom mohol spustiť MITM útok tak jednoducho ako keby certifikačná schéma vôbec nebola použitá. V alternatívnom scenári o ktorom sa hovorí len zriedka, útočník ktorý by prenikol do serverov CA a získal ich úložisko certifikátov a kľúčov (verejných a privátnych), by dokázal dešifrovať a falšovať výmenu informácií bez obmedzení.
Napriek teoretickým a potenciálnym problémom, tento prístup je široko používaný. Príklady zahŕňajú TLS a jeho predchodcu SSL, ktorý je sa bežne používa pre poskytovanie bezpečnosti pre transakcie na webových stránkach (napr., pre bezpečné odoslanie údajov o kreditnej karte do internetového obchodu).
Okrem odolnosti konkrétneho kľúčového páru od útokov, musí byť zvážená bezpečnosť certifikačnej hierarchie keď sa nasadzujú systémy verejného kľúča. Nejaká certifikačná autorita – zvyčajne  účelovo postavený program bežiaci na serverovom počítači – ručí za identity priradené ku špecifickým privátnym kľúčom vytvorením digitálneho certifikátu. Digitálne certifikáty verejného kľúča sú zvyčajne platné niekoľko rokov, takže súvisiace privátne kľúče sa musia držať za ten čas v bezpečí. Ak privátny kľúč (používaný pre vytvorenie certifikátu vo vyššej časti serverovej hierarchie PKI) je komprimovaný alebo náhodne zverejnený, umožní to vykonanie MITM útoku a necháva všetky takéto certifikáty neúčinné. Na zrušenie platnosti certifikátu ešte pred riadnym vypršaním jeho platnosti, napríklad pri uniknutí verejného kľúča, sú používané zoznamy zneplatnených certifikátov (CRL - certificate revocation list).
Príklady.
Príklady dobre uznávaných techník asymetrického kľúča pre rôzne účely:
Príklady algoritmov asymetrického kľúča, ktoré sa ešte široko neadoptovali:
Príklady pozoruhodných – ale nezabezpečených – algoritmov asymetrického kľúča:
Príklady protokolov používajúcich algoritmus asymetrického kľúča:
História.
Počas ranej histórie kryptografie, sa dve strany spoliehali na kľúč, ktorý by si bezpečne vymenili, ale nie kryptograficky, napríklad osobným stretnutím alebo dôverným kuriérom. Tento kľúč, ktorý si obe strany museli nechať v bezpečí, by potom mohol slúžiť na šifrovanú výmenu správ. S týmto prístupom rástlo aj množstvo vzniknutých problémov. 
Očakávania.
William Stanley Jevons v roku 1874, napísal do jeho knihy „Princípy vedy“ (The Principles of Science) toto:
Dokáže čitateľ povedať, ktoré dve vynásobené čísla vytvorili číslo 8616460799? Myslím si, že je nepravdepodobné, aby to ktokoľvek, okrem mňa, vedel.
Tu opisuje vzťah jednosmerných funkcií ku kryptografii a pokračoval v diskusii o probléme faktorizácie použitej pre vytvorenie funkcie padacích dverí (funkcia, ktorá sa jedným smerom počíta veľmi ľahko, ale výpočet inverznej funkcie ide veľmi ťažko). V júli 1996, matematik Solomon W. Golomb povedal: „Jevons predpokladal kľúčovú funkciu algoritmu RSA pre asymetrickú kryptografiu i keď sám o sebe určite nevytvoril koncept kryptografie verejného kľúča."
Utajený objav.
V roku 1970, Britský kryptograf James H. Ellis, na Vládnom Komunikačnom Ústredí v spojenom kráľovstve (GCHQ), prišiel s možnosťou „bezheslového šifrovania“ (dnes už ako kryptografia verejného kľúča), ale nevidel spôsob ako ju implementovať. V roku 1973, jeho kolega Clifford Cocks implementoval niečo, čo sa stálo známe ako šifrovací algoritmus RSA, poskytujúci praktickú metódu „bezheslového šifrovania“ a v roku 1974 ďalší GCHQ matematik a kryptograf, Malcolm J. Williamson, vyvinul výmenu kľúčov Diffieho-Hellmana. Schéma bola taktiež odovzdaná americkej Národnej Bezpečnostnej agentúre. Obe organizácie mali vojenské zameranie a k dispozícií bol iba obmedzený výpočtový výkon; potenciál kryptografie verejného kľúča ostal nevyužitý oboma organizáciami: Usúdil som, že najdôležitejšie je to využiť pre vojenské účely ... pokiaľ dokážete zdieľať váš kľúč rýchlo a elektronicky, máte veľkú výhodu nad vaším oponentom. Až na konci vývoja od Berners-Lee, keď sa jeho otvorená internetová architektúra prispôsobila a prijala pre Arpanet ... až vtedy kryptografia verejným kľúčom využila svoj pravý potenciál. - Ralph BenjaminTieto zistenia neboli verejne uznané po 27 rokov, až do doby, keď sa odtajnili výskumy britskou vládou v roku 1997. 
Verejný objav.
V roku 1976, Whitfield Diffie a Martin Hellman publikovali kryptosystém asymetrického kľúča, ktorý bol inšpirovaný prácou o distribúcii verejných kľúčov od Ralpha Merkleho, odhalili metódu dohody verejného kľúča. Táto metóda výmeny kľúčov, ktorá využíva umocnenie v konečnom poli, sa stála známa ako Diffieho-Hellmanova výmena kľúčov. Toto bola prvá publikovaná praktická metóda pre vytvorenie zdieľaného tajného kľúča cez overený (ale nie dôverný) komunikačný kanál bez použitia predchádzajúceho zdieľaného kľúča. Merkleho technika „dohody verejným kľúčom“ sa stala známa ako Merkleho hlavolam a bola vytvorená v roku 1974 a publikovaná až v roku 1978. Toto asymetrické šifrovanie vytvára pomerne novú oblasť kryptografie aj napriek tomu, že samotná kryptografia má viac ako 2000 rokov.
V roku 1977, zovšeobecnenie Cocksovej schémy nezávisle vytvorili Ron Rivest, Adi Shamir a Leonard Adleman. Títo autori publikovali svoju prácu v roku 1978 vo vedeckom magazíne „Scientific American“ a algoritmus sa stál známym ako RSA, podľa iniciálov autorov. RSA používa umocňovanie s využitím modula n, kde "n" výsledkom súčinu dvoch veľmi veľkých prvočísiel. Táto operácia sa využíva na šifrovanie a dešifrovanie, pričom vykonáva šifrovanie verejným kľúčom a digitálny podpis verejným kľúčom. Jeho bezpečnosť je spojená s extrémnou obtiažnosťou faktorizácie veľkých celých čísiel, problém pre ktorý neexistuje všeobecná efektívna technika (hoci prvotnú faktorizáciu možno dosiahnuť útokmi hrubou silou; obtiažnosť rastie spolu rastúcou faktorizáciou prvočísiel). Popis algoritmu bol publikovaný v Auguste 1977 v magazíne „Scientific American“.
Od 70. rokov 20. storočia sa vyvinulo veľké množstvo šifrovania, digitálnych podpisov, algoritmov pre výmenu kľúča a mnoho ďalších techník, vrátene Rabinovho kryptosystému, šifrovania EIGamal, DSA a kryptografie eliptickej krivky.