Kryptosystém s veřejným klíčem

Kryptografický systém s veřejným klíčem (druh asymetrického šifrování , asymetrická šifra ) - systém šifrování a/nebo elektronického podpisu (ES), ve kterém je veřejný klíč přenášen přes otevřený (tj. nechráněný, pozorovatelný) kanál a používá se k ověření ES a pro šifrované zprávy. Pro vygenerování ES a dešifrování zprávy se používá soukromý klíč [1] . Kryptografické systémy s veřejným klíčem jsou v současnosti široce používány v různých síťových protokolech , zejména v protokolech TLS a jeho předchůdci SSL (základníHTTPS ), na SSH . Používá se také v PGP , S/MIME .

Myšlenka kryptosystému veřejného klíče

Obecné zásady

Asymetrické šifrování veřejným klíčem je založeno na následujících principech:

• Je možné vygenerovat pár velmi velkých čísel (veřejný klíč a soukromý klíč), takže při znalosti veřejného klíče není možné vypočítat soukromý klíč v rozumném čase. V tomto případě je mechanismus generování dobře znám.
• K zašifrování zprávy pomocí veřejného klíče jsou k dispozici silné metody šifrování, takže ji lze dešifrovat pouze pomocí soukromého klíče. Šifrovací mechanismus je dobře známý.
• Vlastník dvou klíčů soukromý klíč nikomu nesděluje, ale sdílí veřejný klíč s protistranami nebo jej zveřejňuje.

Pokud je nutné předat zašifrovanou zprávu majiteli klíčů, musí odesílatel obdržet veřejný klíč. Odesílatel zašifruje svou zprávu veřejným klíčem příjemce a předá ji příjemci (vlastníkovi klíčů) přes otevřené kanály. Zprávu přitom nemůže dešifrovat nikdo kromě vlastníka soukromého klíče.

Výsledkem je, že zprávy mohou být bezpečně zašifrovány a zároveň uchovat dešifrovací klíč v tajnosti pro všechny – dokonce i pro odesílatele zpráv.

Tento princip lze vysvětlit každodenní analogií "zámek - klíč k zámku" pro odeslání balíku. Účastník A má osobní zámek a klíč k němu. Pokud chce účastník A obdržet tajný balíček od účastníka B, pak mu veřejně daruje svůj hrad. Účastník B uzamkne zámek na tajném balíčku a odešle jej účastníkovi A. Po obdržení balíčku účastník A otevře zámek klíčem a balíček obdrží.

Vědět o předání zámku a zachycení balíku potenciálnímu útočníkovi nic nedá: klíč od zámku má pouze účastník A, takže balík nelze otevřít.

Implementace pomocí jednosměrné funkce

Myšlenka kryptografie s veřejným klíčem velmi úzce souvisí s myšlenkou jednosměrných funkcí , tedy takových funkcí , u kterých je poměrně snadné najít hodnotu ze známé hodnoty , zatímco určení z rozumnou dobu.

Ale samotná jednosměrná funkce je v aplikaci k ničemu: umí zašifrovat zprávu, ale neumí ji dešifrovat. Proto kryptografie veřejného klíče používá jednosměrné funkce s mezerou. Skulinka je tajemství, které pomáhá rozluštit. To znamená, že existuje taková , že když víme a , můžeme vypočítat . Pokud například rozeberete hodiny na mnoho částí, je velmi obtížné znovu sestavit hodiny, které znovu fungují. Ale pokud existuje návod na sestavení (mezera), pak lze tento problém snadno vyřešit.

Příjemce informace vygeneruje veřejný klíč a „lapdoor“ (jinými slovy, veřejná a soukromá část klíče), poté předá veřejný klíč odesílateli a „trapdoor“ si ponechá pro sebe. Odesílatel zašifruje informace na základě veřejného klíče: takto zašifrované informace lze snadno dešifrovat, pokud máte veřejný klíč i „zadní vrátka“ současně. Pokud jde o funkci, přijímač se vytvoří se zadními vrátky , poté předá informace o parametrech funkce odesílateli (i když zná parametry funkce , není možné detekovat "zadní vrátka" v rozumném čase). Odesílatel poté vytvoří zašifrovanou zprávu a příjemce z ní extrahuje s vědomím .

Příklady

Následující příklad pomáhá pochopit myšlenky a metody kryptografie veřejného klíče – ukládání hesel na vzdáleném počítači, ke kterému by se měli uživatelé připojit. Každý uživatel v síti má jiné heslo. U vchodu naznačí jméno a zadá tajné heslo. Pokud ale heslo uložíte na disk vzdáleného počítače, může si ho někdo přečíst (obzvlášť pro správce tohoto počítače to může udělat) a získat přístup k tajným informacím. K vyřešení problému se používá jednosměrná funkce. Při vytváření tajného hesla počítač neukládá heslo samotné, ale výsledek výpočtu funkce z tohoto hesla a uživatelského jména. Například uživatelka Alice přišla s heslem „Gladiolus“. Při ukládání těchto dat se vypočítá výsledek funkce ( ALICE_GLADIOLUS ), výsledkem nechť je řetězec CAMOMILE , který se uloží do systému. V důsledku toho bude mít soubor s hesly následující podobu:

název	(Jméno: Heslo)
ALICE	HEŘMÁNEK
FAZOLE	NARCIS

Přihlášení nyní vypadá takto:

Když Alice zadá „tajné“ heslo, počítač zkontroluje, zda funkce aplikovaná na ALICE_GLADIOLUS dává správný výsledek CAMOMILE uložený na disku počítače. Vyplatí se změnit alespoň jedno písmeno ve jméně nebo v hesle a výsledek funkce bude úplně jiný. „Tajné“ heslo není v počítači uloženo v žádné podobě. Soubor s hesly mohou nyní zobrazit ostatní uživatelé bez ztráty soukromí, protože funkce je téměř nevratná.

Předchozí příklad používá jednosměrnou funkci bez mezery, protože není nutné získat původní zprávu ze zašifrované zprávy. V následujícím příkladu je zvažováno schéma se schopností obnovit původní zprávu pomocí „zadních vrátek“, tedy informací, které je těžké najít. Chcete-li zašifrovat text, můžete si vzít velký adresář předplatitelů, který se skládá z několika tlustých svazků (je velmi snadné najít číslo jakéhokoli obyvatele města pomocí něj, ale je téměř nemožné najít předplatitele pomocí známého čísla) . Pro každé písmeno ze zašifrované zprávy je vybráno jméno začínající stejným písmenem. Dopis je tedy přiřazen k telefonnímu číslu účastníka. Odesílaná zpráva, například „ BOX “, bude zašifrována následovně:

Kryptotext bude řetězec čísel zapsaných v pořadí podle jejich výběru v adresáři. Aby bylo obtížné dešifrovat, měli byste zvolit náhodná jména, která začínají požadovaným písmenem. Původní zpráva tak může být zašifrována mnoha různými seznamy čísel (kryptotexty).

Příklady takových kryptotextů:

K rozluštění textu musíte mít referenční knihu sestavenou podle vzestupných čísel. Tento adresář je mezera (tajemství, které pomáhá získat počáteční text), kterou zná pouze příjemce. Bez dat z obou adresářů je obecně nemožné text dešifrovat, ale pro šifrování stačí pouze první adresář [2] . V tomto případě může příjemce snadno vytvořit oba adresáře předem, přičemž pouze první z nich přenese odesílateli k zašifrování.

Schéma šifrování veřejného klíče

Nechť  je klíčový prostor a a  je šifrovací a dešifrovací klíč, v tomto pořadí.  je funkce šifrování pro libovolný klíč tak, že . Zde , kde  je prostor šifrových textů a , kde  je prostor zpráv.

 je dešifrovací funkce, kterou lze použít k nalezení původní zprávy s daným šifrovaným textem : ,  je šifrovací sada a  je odpovídající dešifrovací sada. Každá dvojice má následující vlastnost: znalost , je nemožné vyřešit rovnici , to znamená, že pro daný libovolný šifrový text není možné najít zprávu . To znamená, že z daného klíče nelze určit odpovídající dešifrovací klíč . je jednosměrná funkce a  je mezerou [3] .

Níže je schéma předávání informací osobou A osobě B. Mohou to být jak jednotlivci, tak organizace a podobně. Pro snadnější vnímání je ale zvykem ztotožňovat účastníky programu s lidmi, nejčastěji označovanými jako Alice a Bob. Účastník, který se snaží zachytit a dešifrovat zprávy Alice a Boba, je nejčastěji označován jako Eva.

1. Bob vybere pár a pošle šifrovací klíč (veřejný klíč) Alici přes veřejný kanál a dešifrovací klíč (soukromý klíč) je chráněný a tajný (nesmí být přenášen přes veřejný kanál).
2. K odeslání zprávy Bobovi Alice používá šifrovací funkci definovanou veřejným klíčem : ,  přijatým šifrovaným textem.
3. Bob dešifruje šifrovaný text pomocí inverzní transformace , jednoznačně identifikované hodnotou .

Vědecký základ

Asymetrické šifry začaly v New Directions in Modern Cryptography od Whitfielda Diffieho a Martina Hellmana , vydaném v roce 1976 . Ovlivněni prací Ralpha Merkla na distribuci veřejných klíčů navrhli metodu pro získání soukromých klíčů pomocí veřejného kanálu. Tato metoda exponenciální výměny klíčů, která se stala známou jako výměna klíčů Diffie-Hellman , byla první publikovanou praktickou metodou pro zavedení sdílení tajných klíčů mezi ověřenými uživateli kanálu. V roce 2002 Hellman navrhl nazvat algoritmus „Diffie-Hellman-Merkle“, čímž uznal Merkleův příspěvek k vynálezu kryptografie s veřejným klíčem. Stejné schéma vyvinul Malcolm Williamson ( angl.  Malcolm J. Williamson ) v 70. letech 20. století, ale bylo drženo v tajnosti až do roku 1997 . Metoda distribuce veřejného klíče Merkle byla vynalezena v roce 1974 a publikována v roce 1978 a nazývá se také Merkleova hádanka.

V roce 1977 vyvinuli vědci z MIT Ronald Rivest , Adi Shamir a Leonard Adleman šifrovací algoritmus založený na problému faktorizace. Systém byl pojmenován podle prvních písmen jejich příjmení ( RSA  - Rivest, Shamir, Adleman). Stejný systém vynalezl v roce 1973 Clifford Cocks , který pracoval ve Government Communications Center ( GCHQ ), ale tato práce byla vedena pouze v interních dokumentech centra, takže o její existenci se nevědělo až do roku 1977 . RSA byl první algoritmus vhodný pro šifrování i digitální podpis.  

Obecně jsou známé asymetrické kryptosystémy založeny na jednom ze složitých matematických problémů, který umožňuje budovat jednosměrné funkce a funkce zadních vrátek. Například kryptosystémy Merkle-Hellman a Hoare-Rivest spoléhají na takzvaný problém s batohem na zádech .

Základní principy budování kryptosystémů s veřejným klíčem

1. Začněme těžkým úkolem . Mělo by být obtížné to vyřešit ve smyslu teorie: neměl by existovat algoritmus, který by mohl být použit k třídění všech možností řešení problému v polynomiálním čase vzhledem k velikosti problému. Správnější je říci: neměl by existovat známý polynomiální algoritmus, který by tento problém vyřešil – protože dosud nebylo pro žádný problém prokázáno, že pro něj v zásadě neexistuje vhodný algoritmus.
2. Můžete vybrat lehký dílčí úkol z . Musí se řešit v polynomiálním čase a lépe, když v lineárním čase.
3. „Zamíchejte a protřepejte“ , abyste získali úkol , který je zcela odlišný od původního. Problém by měl alespoň vypadat jako původní neřešitelný problém .
4. otevře s popisem, jak jej lze použít jako šifrovací klíč. Jak ho získat , je drženo v tajnosti jako tajná mezera.
5. Kryptosystém je organizován tak, že dešifrovací algoritmy pro legálního uživatele a kryptoanalytika jsou výrazně odlišné. Zatímco druhý řeší -problém, první využívá tajnou mezeru a řeší -problém.

Kryptografie s více veřejnými klíči

• Následující příklad ukazuje schéma, ve kterém Alice zašifruje zprávu, aby si ji mohl přečíst pouze Bob, a naopak Bob zašifruje zprávu, aby ji mohla dešifrovat pouze Alice.

Nechť jsou 3 klíče , , , rozmístěné tak, jak je uvedeno v tabulce.

Tvář	Klíč
Alice
Fazole
Koleda
Dave	,
Ellen	,
Frank	,

Pak může Alice zašifrovat zprávu pomocí klíče a Ellen může dešifrovat pomocí klíčů , Carol může šifrovat pomocí klíče a Dave může dešifrovat pomocí klíčů , . Pokud Dave zašifruje zprávu pomocí klíče , pak Ellen může zprávu přečíst, pokud pomocí klíče , pak si ji může přečíst Frank, pokud pomocí obou klíčů a , pak zprávu přečte Carol. Ostatní účastníci jednají podobně. Pokud je tedy pro šifrování použita jedna podmnožina klíčů, pak jsou pro dešifrování vyžadovány zbývající klíče sady. Takové schéma lze použít pro n klíčů.

Šifrováno klíčem	Dešifrováno klíčem
a
a
a
	,
	,
	,

• Nyní můžete posílat zprávy skupinám agentů, aniž byste předem znali složení skupiny.

Nejprve si představte sadu sestávající ze tří agentů: Alice, Bob a Carol. Alice dostane klíče a , Bob - a , Carol - a . Nyní, pokud je odesílaná zpráva zašifrována klíčem , může ji přečíst pouze Alice postupným použitím klíčů a . Pokud chcete poslat zprávu Bobovi, bude zpráva zašifrována klíčem , Carol - klíčem . Pokud chcete poslat zprávu Alici i Carol, pak klíče a slouží k šifrování .

Výhodou tohoto schématu je, že k jeho implementaci je potřeba pouze jedna zpráva a n klíčů (ve schématu s n agenty). Pokud jsou odesílány jednotlivé zprávy, to znamená, že se pro každého agenta (celkem n klíčů) a každou zprávu používají samostatné klíče, pak jsou klíče vyžadovány pro odesílání zpráv všem různým podmnožinám.

Nevýhodou tohoto schématu je, že je potřeba vysílat také podmnožinu agentů (seznam jmen může být dlouhý), kterým chcete zprávu vysílat. V opačném případě bude muset každý z nich projít všemi kombinacemi kláves při hledání vhodného. Agenti také budou muset uchovávat značné množství informací o klíčích [4] .

Kryptoanalýza algoritmů veřejného klíče

Zdá se, že kryptosystém s veřejným klíčem je ideálním systémem, který nevyžaduje zabezpečený kanál pro přenos šifrovacího klíče. To by znamenalo, že dva legitimní uživatelé by mohli komunikovat přes otevřený kanál, aniž by se museli setkat, aby si vyměnili klíče. Bohužel není. Obrázek ilustruje, jak Eve, působící jako aktivní zachycovač, může převzít kontrolu nad systémem (dešifrovat zprávu určenou pro Boba), aniž by prolomila šifrovací systém.

V tomto modelu Eva zachytí veřejný klíč , který Bob poslal Alici. Poté vygeneruje pár klíčů a „maskuje se“ jako Bob tím, že Alici pošle veřejný klíč , o kterém si Alice myslí, že je veřejný klíč, který jí poslal Bob. Eva zachytí zašifrované zprávy od Alice Bobovi, dešifruje je tajným klíčem , znovu je zašifruje Bobovým veřejným klíčem a pošle zprávu Bobovi. Nikdo z účastníků si tedy neuvědomuje, že existuje třetí strana, která může zprávu buď jednoduše zachytit, nebo ji nahradit falešnou zprávou . To zdůrazňuje potřebu autentizace veřejným klíčem . K tomu se obvykle používají certifikáty . Distribuovaná správa klíčů v PGP řeší problém s pomocí garantů [5] .

Další formou útoku je výpočet soukromého klíče z veřejného klíče (obrázek níže). Kryptanalytik zná šifrovací algoritmus , analyzuje ho a snaží se najít . Tento proces je zjednodušen, pokud kryptoanalytik zachytil několik kryptotextů c zaslaných osobou A osobě B.

Většina kryptosystémů s veřejným klíčem je založena na problému faktorizace velkého počtu. Například RSA používá jako veřejný klíč n součin dvou velkých čísel. Složitost rozluštění takového algoritmu spočívá v obtížnosti faktorizace čísla n. Ale tento problém lze reálně vyřešit. A každým rokem je proces rozkladu rychlejší a rychlejší. Níže jsou uvedena data faktorizace pomocí algoritmu "Quadratic Sieve".

Také problém rozkladu může být potenciálně vyřešen pomocí algoritmu Shor při použití dostatečně výkonného kvantového počítače .

U mnoha metod asymetrického šifrování se kryptografická síla získaná v důsledku kryptoanalýzy výrazně liší od hodnot deklarovaných vývojáři algoritmů na základě teoretických odhadů. Proto je v mnoha zemích problematika používání algoritmů šifrování dat v oblasti legislativní regulace. Zejména v Rusku jsou ve státních a komerčních organizacích povoleny pouze ty softwarové nástroje pro šifrování dat, které prošly státní certifikací ve správních orgánech, zejména ve FSB , FSTEC [6] .

Vlastnosti systému

Aplikace

Lze použít kryptosystémové algoritmy s veřejným klíčem [7] :

• jako nezávislý prostředek pro ochranu přenášených a uchovávaných informací,
• jako prostředek distribuce klíčů (obvykle pomocí algoritmů kryptosystémů s veřejným klíčem jsou distribuovány klíče malé velikosti a přenos velkých informačních toků se provádí pomocí jiných algoritmů),
• jako prostředek pro autentizaci uživatele.

Výhody

Výhody asymetrických šifer oproti symetrickým :

• není třeba nejprve přenášet tajný klíč přes spolehlivý kanál;
• pouze jedna strana zná dešifrovací klíč, který musí být uchován v tajnosti (v symetrické kryptografii je takový klíč znám oběma stranám a musí být oběma držen v tajnosti);
• ve velkých sítích je počet klíčů v asymetrickém kryptosystému mnohem menší než v symetrickém.

Nevýhody

Nevýhody asymetrického šifrovacího algoritmu ve srovnání se symetrickým:

• je obtížnější provádět změny v algoritmu;
• delší klíče – níže je tabulka porovnávající délku klíče symetrického algoritmu s délkou klíče RSA s podobnou kryptografickou silou:

• šifrování-dešifrování pomocí páru klíčů je o dva až tři řády pomalejší než šifrování-dešifrování stejného textu pomocí symetrického algoritmu;
• je zapotřebí podstatně více výpočetních zdrojů, proto se v praxi používají asymetrické kryptosystémy v kombinaci s dalšími algoritmy:
  1. pro EDS je zpráva předem zahashována a pomocí asymetrického klíče je podepsán pouze relativně malý výsledek hashovací funkce ;
  2. pro šifrování se používají ve formě hybridních kryptosystémů , kde jsou velká množství dat šifrována symetrickou šifrou na klíči relace a pomocí asymetrické šifry se přenáší pouze samotný klíč relace.

Typy asymetrických šifer

• RSA (Rivest-Shamir-Adleman)
• DSA (Algoritmus digitálního podpisu)
• Elgamal (ElGamal Cipher System)
• Diffie-Hellman (výměna klíčů Diffie-Hellman)
• ECDSA (Elliptic Curve Digital Signature Algorithm) je algoritmus veřejného klíče pro vytváření digitálního podpisu.
• GOST R 34.10-2012
• Rabin
• Luc
• McEliece
• Williamsův kryptosystém

Viz také

• Bloková šifra
• Streamová šifra
• Infrastruktura veřejného klíče (PKI)
• CEILIDH
• Složitost hesla
• Hushmail  je webová e-mailová služba založená na šifrování veřejným klíčem.

Poznámky

1. ↑ Bruce Schneier. Aplikovaná kryptografie. 2. vyd. Protokoly, algoritmy a zdrojové texty v jazyce C. Kapitola 2.7 Digitální podpisy a šifrování.
2. ↑ Salomaa A. Kryptografie veřejného klíče. S. 74-75
3. ↑ Handbook of Applied Cryptography, Menezes AJ, Oorschot PC, Vanstone SA str. 25-26
4. ↑ Bruce Schneier. Aplikovaná kryptografie. 2. vyd. Protokoly, algoritmy a zdrojové texty v jazyce C. Kapitola 3.5
5. ↑ PGP. Distribuce klíčů. . Archivováno z originálu 26. července 2013. (neurčitý)
6. ↑ Zásada dostatečné ochrany (nepřístupný odkaz) . Získáno 4. prosince 2008. Archivováno z originálu 24. května 2010. (neurčitý) 
7. ↑ Barichev S. Kryptografie bez tajemství. S. dvacet

Literatura

• Salomaa A. Kryptografie veřejného klíče. — M .: Mir, 1995. — 318 s. — ISBN 5-03-001991-X .
• AJ Menezes, PC van Oorschot, SA Vanstone. Příručka aplikované kryptografie . - 1997. - ISBN 0-8493-8523-7 .
• Schneier B. Aplikovaná kryptografie. Protokoly, algoritmy, zdrojový kód v jazyce C = Aplikovaná kryptografie. Protocols, Algorithms and Source Code in C. - M. : Triumph, 2002. - 816 s. - 3000 výtisků.  - ISBN 5-89392-055-4 .

Odkazy

• Třicet let veřejného klíče | Computerworld Rusko | Nakladatelství "Otevřené systémy"  (ruština)