BANKOVNÍ INSTITUT VYSOKÁ ŠKOLA PRAHA Katedra matematiky, statistiky a informačních technologií
BUDOUCNOST A TRENDY KRYPTOGRAFIE KRYPTOGRAFIE A KVANTOVÉ POČÍTAČE Bakalářská práce
Autor:
Jan Mandík Informační technologie - MIPS
Vedoucí práce: Praha
Ing. Vladimír Beneš Duben 2013
Prohlášení: Prohlašuji, že jsem bakalářskou práci zpracoval samostatně a v seznamu uvedl veškerou použitou literaturu. Svým podpisem stvrzuji, že odevzdaná elektronická podoba práce je identická s její tištěnou verzí, a jsem seznámen se skutečností, že se práce bude archivovat v knihovně BIVŠ a dále bude zpřístupněna třetím osobám prostřednictvím interní databáze elektronických vysokoškolských prací. V Praze, dne 15. 4 2013
Jan Mandík
Poděkování: Chtěl bych poděkovat panu Ing. Vladimíru Benešovi za možnost užít si zábavu ve světě fyziky a kryptografie i při psaní bakalářské práce. Jan Mandík
Anotace Cílem bakalářské práce je seznámit čtenáře se základními pojmy v oblasti kvantové teorie, teorie složitosti a kryptografie. V dalších kapitolách si klade za cíl přiblížit, co se může stát se současnou kryptografií v návaznosti na vývoj v oblasti kvantových počítačů a teorie složitosti. Klíčová slova:
kvantová teorie, kryptografie, teorie složitosti, kvantové počítače
Annotation The goal of a bachelor’s degree is understanding the reader with basic primitives and principles of quantum theory, complexity theory and cryptography and to characterize this convergence of cryptography and quantum computation. Keywords:
quantum theory, cryptography, complexity theory, quantum computation
Obsah 1.
Úvod ....................................................................................................................... 8
2.
Přehled ................................................................................................................... 9
3.
Kvantová teorie a kvantové počítače ................................................................ 10 3.1.
Úvod do kvantové teorie ...................................................................................................... 10
3.2.
Kvantové bity ....................................................................................................................... 11
3.3.
Paradox výpočtu pomocí qubitu........................................................................................... 13
3.4.
Vlnová interference a světlo................................................................................................. 14
3.5.
Existence kvantového počítače v superpozici stavů ............................................................. 14
3.6.
Kvantová provázanost (entanglement, nonlokalita) ............................................................. 15
3.7.
Spin a kvantová provázanost ................................................................................................ 15
3.8.
Heisenbergův princip neurčitosti ......................................................................................... 16
3.9.
Dekoherence a interakce kvantových počítačů s okolním prostředím ................................. 16
3.10.
Potenciál kvantových počítačů ............................................................................................. 17
3.11.
Shorův algoritmus ................................................................................................................ 17
3.11.1.
4.
5.
Hledání periody funkce pomocí kvantového počítače. ................................................... 18
Úvod do základních pojmů kryptografie. ........................................................ 20 4.1.
Základy kryptografie a použitá terminologie ....................................................................... 20
4.2.
Symetrické šifrování ............................................................................................................ 20
4.3.
Jednosměrné funkce ............................................................................................................. 22
4.4.
Funkce s padacími dveřmi a kryptografie veřejných klíčů................................................... 22
4.4.1.
Diffie-Hellmanova výměna klíčů .................................................................................... 23
4.4.2.
RSA (Rivest, Shamir, Adleman) ..................................................................................... 23
4.4.3.
ElGamal algoritmus......................................................................................................... 24
4.4.4.
DSA ................................................................................................................................. 24
4.5.
Kryptografie na bázi eliptických křivek - algoritmus digitálního podpisu (ECDSA) .......... 24
4.6.
Digitální podpis .................................................................................................................... 25
4.7.
Problematika generování „náhodných“ čísel ....................................................................... 25
Teorie složitosti ................................................................................................... 27 5.1.
Přehled tříd složitosti a základních teorémů......................................................................... 27
5.1.1.
Deterministický Turingův stroj a třída složitosti P .......................................................... 28
5.1.2.
Nedeterministický Turingův stroj.................................................................................... 29
5.1.3.
Pravděpodobnostní Turingův stroj a třída složitosti BPP ................................................ 29
5.1.4.
Jednoznačný Turingův stroj a třída složitosti UP ............................................................ 30
5.1.5.
Kvantový Turingův stroj a třída složitosti BQP .............................................................. 30
5.1.6.
Kvantové třídy složitosti ................................................................................................. 31
6.
5.1.7.
Univerzálnost Turingova stroje ....................................................................................... 31
5.1.8.
Zázračný Turingův stroj .................................................................................................. 32
5.2.
Názvosloví tříd složitosti...................................................................................................... 32
5.3.
Jednoduché úlohy a komplikované úlohy ............................................................................ 32
Teorie složitosti a základní kryptografické koncepty ..................................... 34 6.1.
Aplikace Teorie složitosti v kryptografii.............................................................................. 34
6.2.
Definice základních kryptografických pojmů a postulátů .................................................... 35
6.3.
Kryptografie symetrického klíče .......................................................................................... 35
6.3.1.
Definice symetrického klíče ............................................................................................ 35
6.3.2.
Definice zprávy šifrované podle symetrického klíče....................................................... 35
6.3.3.
Definice funkce nalezení klíče - symetrické šifrování .................................................... 36
6.3.4.
Prolomení symetrického šifrování................................................................................... 37
6.4. 6.4.1.
Definice jednosměrné hashovaní funkce ......................................................................... 38
6.4.2.
Prolomení jednosměrné hashovaní funkce ...................................................................... 38
6.5.
Kryptografie veřejných klíčů ............................................................................................... 39
6.5.1.
Definice funkce se zadními vrátky .................................................................................. 39
6.5.2.
Definice kryptosystému používajícího funkce se zadními vrátky ................................... 40
6.5.3.
Prolomení kryptosystému s veřejným klíčem ................................................................. 41
6.6.
Digitální podpis .................................................................................................................... 41
6.6.1.
Definice digitálního podpisu ........................................................................................... 41
6.6.2.
Prolomení digitálního podpisu ........................................................................................ 42
6.7.
Generování náhodných čísel ................................................................................................ 43
6.7.1.
Definice náhodných čísel ................................................................................................ 43
6.7.2.
Určení hodnoty dalšího bitu ............................................................................................ 44
6.8.
7.
Jednosměrná hashovací funkce ............................................................................................ 38
Požadavky na složitost z hlediska bezpečnosti a proveditelnosti ......................................... 44
6.8.1.
Požadavky na složitost pro symetrické šifry ................................................................... 45
6.8.2.
Požadavky na jednosměrné hashovací funkce................................................................. 45
6.8.3.
Požadavky na složitost pro veřejné klíče......................................................................... 45
6.8.4.
Požadavky na digitální podpis ......................................................................................... 46
6.8.5.
Požadavky při generování náhodných čísel..................................................................... 46
Kvantové počítače a kryptografie ..................................................................... 47 7.1.
Teorie složitosti ve vztahu ke kvantovým počítačům .......................................................... 47
7.1.1.
Známé vztahy mezi klasickými a kvantovými třídami složitosti..................................... 48
7.1.2.
Aplikace kvantových tříd složitosti v kryptografických konceptech............................... 48
7.1.3.
Aplikace varianty schématu tříd složitosti - ⊂ ................................. 49
7.1.4. 7.1.5.
Aplikace varianty schématu tříd složitosti ve znění ⊂ ................................ 49
Aplikace varianty schématu tříd složitosti ⊆ .................................................. 49
8.
Závěry .................................................................................................................. 51 8.1.
Očekávaný posun v paradigmatech kryptografie v důsledku nástupu kvantových počítačů 51
8.2.
Žijeme v době kvantových počítačů..................................................................................... 52
8.3.
Pohled do budoucna ............................................................................................................. 53
9.
SEZNAM POUŽITÉ LITERATURY .............................................................. 55
10.
INTERNETOVÉ STRÁNKY ........................................................................ 58
11.
BIBLIOGRAFICKÉ ODKAZY A CITACE DOKUMENTŮ ................... 59
1.
Úvod Od počátku existence lidstva mají příslušníci lidské rasy neustálé nutkání před sebou
navzájem tajit informace. Je lhostejné, jedná-li se o prostou informaci o nevěře, počtu vojáků, nebo vědecký objev. Ve starověku se situace vyhrotila natolik, že vznikl prostor pro nový druh umění, které dostalo příznačný název - kryptografie. Po létech používání jednoduchých písemných substitucí a rozvojem kryptoanalýzy došlo na složitější polyalfabetické šifrování1. Díky vývoji jemné mechaniky se ke slovu dostaly rotorové stroje a s nástupem diskrétních součástek a rozvojem binárního světa též digitální šifry založené na matematických postulátech. Historicky prodělala kryptografie několik revolucí, zejména období napjatých vztahů přinesla nejedno krásné technické řešení. Pro zajímavost můžeme zmínit Vigenèrovou symetrickou substituční šifru, nebo známou Enigmu, která rozhodovala o průběhu druhé světové války. [28] S nebývalým rozvojem fyziky v průběhu minulého století a objevem kvantových jevů přišly na řadu zajímavé otázky, které možná v budoucnu mohou znamenat konec kariéry kryptografie tak, jak ji dnes známe. V této práci se seznámíme se základy kvantové teorie, které jsou nutné pro pochopení možností kvantových počítačů a možného využití kvantových počítačů. Seznámíme se také se základními kryptografickými koncepty a probereme i několik kapitol z teorie složitosti. Na první pohled podivné možnosti kvantových počítačů mohou změnit paradigmata současné kryptografie a učinit z některých rozšířených šifrovacích metod část historie popisující vytrvalý boj mezi kryptografy a kryptoanalytiky2. Seznámíme se s několika konkrétními šifrovacími algoritmy, které tvoří část moderní kryptografie. Některé z nich se pomocí teorie složitosti pokusíme spojit s potenciálem kvantových počítačů.
1 Polyalfabetická šifra vylepšuje monoalfabetickou šifra přidáním dalších abeced, podle kterých můžeme šifrovat. Podle nějakého klíče poté vybíráme, podle které konkrétní abecedy budeme zrovna šifrovat. 2 Kryptograf – ten kdo vytváří kryptografické systémy, kryptoanalitik – ten kdo se zabývá analýzou a prolomením kryptografických systémů.
8
2.
Přehled V následujících kapitolách si postupně představíme teorie a objekty, které
budeme v rámci této práce diskutovat. Nejprve se seznámíme se základy kvantové fyziky a absolvujeme stručný úvod do teorie kvantových počítačů. Poté bude následovat úvod a seznámení se základy kryptografie v případech, kdy bude možné aplikovat kvantové výpočty. Projdeme základy teorie složitosti. V další kapitole se pokusíme definitivně dohromady spojit kvantovou fyziku s kryptografií a charakterizovat hlavní prvky a důsledky tohoto spojení. Shrneme důsledky, které mohou díky kvantovým počítačům pro vybrané kryptografické koncepty vzniknout.
9
3.
Kvantová teorie a kvantové počítače
3.1.
Úvod do kvantové teorie V
devatenáctém
století
bylo
možné
závidět
fyzikům
jejich
dokonale
organizovaný a matematicky popsatelný svět. Pohyby planet se řídí Newtonovými zákony o pohybu a gravitaci, takřka vše lze předpovědět nebo vypočítat, chtělo by se skoro říci - určit. V tomto termínu je cítit nepatrný záchvěv touhy umět předpovědět i věci budoucí. Části poznání, ve které bylo možné vše vypočítat a určit se dnes říká klasická fyzika. Formálně v této části fyziky hovoříme o popisu stavu systému v daném čase a prostoru pomocí hodnot vybraných měřitelných veličin. Například stav hmotného bodu je úplně určen pomocí polohového vektoru a vektoru hybnosti. [11] Pojem stavu v kvantové teorii je složitější. Kvantová teorie je založena na neurčitosti, pouze předpovídá, co se za daných okolností může stát. Mohli bychom konstatovat, že je to oproti předcházejícímu stavu, reprezentovaném měřitelností a vypočítatelností, zásadní změna. Hezký příklad uvádí ve své knize Marcus Chown. Hraje v něm klíčovou roli obyčejné světlo a skleněná tabule: Při průchodu světla skleněnou tabulí má foton 95 procentní šanci, že projde skrz skleněnou tabuli a 5 procentní šanci, že se od skleněné tabule odrazí. Pokud se zamyslíme, možná nás začne zajímat mechanismus, podle kterého se světlo rozhodne, co vlastně udělá. Jinými slovy mechanismus určení pravděpodobnosti odrazu fotonu od skleněné tabule a jeho řízení. V případě vlnového i částicového obrazu světla tak, jak je známe z klasické fyziky, musí být na konci stejný výsledek. Pokud bychom chtěli, aby polovina vln skleněnou tabulí prošla a druhá polovina vln se odrazila, musí mít každá částice světla padesátiprocentní pravděpodobnost, že sklem projde, a padesátiprocentní pravděpodobnost, že se odrazí. Stejně tak má-li projít 95 procent vlny a 5 procent se odrazit, odpovídající pravděpodobnosti pro průchod či odraz jednotlivých fotonů musí být 95 a 5 procent. Jen tak lze dosáhnout souladu mezi vlnovým a částicovým pojetím světla.[37] Z uvedeného příkladu, pokud přehlédneme hraní si s procenty, se můžeme dovědět důležitou
informaci.
V jednu
chvíli
veličiny
přestávají
pracovat
s
konkrétními
hodnotami a začínají pracovat s pravděpodobností. Ve spojitém prostoru bychom měli správně hovořit o hustotě rozdělení pravděpodobnosti, ale bez hlubšího teoretického základu 10
je těžké si pod tímto termínem něco představit. V případě fotonů by mělo dojít ke shodě. Částicová stránka světla by měla od vlnové části světla dostat přesnou informaci o tom, jak se má při průchodu skleněnou tabulí zachovat. O světle lze uvažovat jako o proudu částic, nebo jako o vlně. Částice se chovají jako vlny a vlny se chovají jako částice. Jestliže pozorujeme světlo jako proud částic, neexistuje žádná vlna, která by mohla informovat částice o tom, jak se mají chovat. A tady bychom mohli naše úvahy skončit a dál se světlem nezabývat. Naštěstí v roce 1925 přišel rakouský fyzik Erwin Schrödinger3 s představou abstraktní matematické vlny, která se rozlévá prostorem a pohybuje se stejně jako vodní vlna na hladině moře nebo rybníka. Rovnice pana Schrödingera popisuje časový a prostorový vývoj vlnové funkce částice, která se pohybuje v poli sil. Největší pravděpodobnost výskytu částice je v místech, kde pomyslné vlny dosahují největší velikosti, nejmenší pravděpodobnost výskytu částice je tam, kde je vlna nejnižší. Pravděpodobnostní vlna tak představuje spojení mezi vlnovým charakterem hmoty a vlněním obecně, ať již jde o vlny zvukové, nebo vodní. Všechny vlny se v reálném světě řídí vlnovou rovnicí. Ta popisuje jejich šíření prostorem a umožňuje předpovědět výšku vlny v jakémkoli místě i čase. Další příklady pojednávající úvod do kvantové fyziky nalezne laskavý čtenář, který má o tématiku zájem v knize přednášek profesora Feynmanna. [10] [11]
3.2.
Kvantové bity Kvantové počítače používají jako svoji základní jednotku pro vyjádření podstaty
informace kvantový bit. V anglické literatuře se můžeme setkat s pojmem qubits. Pro snadnější pochopení můžeme použít analogii - klasický počítačový bit je roven kvantovému bitu.
Můžeme
tuto
analogii
použít,
pokud
budeme
hovořit
o
kvantitativním
vyjádření.V kvalitativním slova smyslu tato analogie neplatí. Díky kvantovým jevům získává kvantový bit, na rozdíl od svého tranzistorového kolegy, celou řadu zajímavých a na první pohled zdánlivě nepochopitelných vlastností. Chování kvantového bitu může ostře kontrastovat se zkušenostmi z každodenního života. První z nich by se dala charakterizovat
3 Erwin Rudolf Josef Alexander Schrödinger (12. srpna 1887 Vídeň – 4. ledna 1961 Vídeň) byl rakouský teoretický fyzik, jeden ze zakladatelů kvantové mechaniky, který se proslavil především formulací nerelativistické vlnové rovnice pro popis hmotných částic, kterou na jeho počest nazýváme Schrödingerova rovnice
11
jako schopnost existovat v jednu chvíli na několika místech zároveň. V reálném světě by se dalo uvažovat o situaci, kdy učitel matematiky existuje při zkoušce ve stavu superpozice4 a stojí za zády dvěma zúčastněným studentům na různých koncích třídy zároveň a hlídá, zda neopisují. Druhá vlastnost je příznačná pro každou těžko pochopitelnou fyzikální teorii a to je praktická nemožnost zjistit pomocí měření zda se příslušné kvantum, nachází ve stavu superpozice či nikoliv. Pokud se pokusíme, pomocí měření, zjistit stav kvanta dojde k okamžitému narušení stavu superpozice. Následkem toho je, že jsme schopni zjistit pouze jeden stav a hovoříme o kolapsu vlnové funkce kvanta. Pro úplnost uvedeme ještě část definice základních principů kvantové mechaniky a ideálního experimentu tak, jak ho popsal profesor Feynmann ve svých přednáškách z fyziky: Budeme zcela přesní, když řekneme: „Ideální experiment je ten experiment, v kterém jsou všechny počáteční i konečné podmínky přesně definovány." „Událostí" budeme obecně nazývat určitou množinu počátečních a konečných podmínek. (Například: „Elektron vyletí z elektronového děla, dopadne na detektor a nic jiného se nestane.") Pravděpodobnost toho, že v ideálním experimentu nastane nějaká událost, je dána
druhou mocninou absolutní hodnoty komplexního čísla , jež se nazývá amplitudou
pravděpodobnosti .
| | Může-li nějaká událost nastat několika způsoby, je amplituda pravděpodobnosti takové události rovna součtu amplitud pravděpodobností pro každý způsob uvažovaný zvlášť. Nastává interference. P | | Lze-li v experimentu určit, která z možností skutečně nastala, je pravděpodobnost události rovna součtu pravděpodobnosti pro každou alternativu. Interference se ztrácí.
4 Princip superpozice stavů – Kvantový objekt může být ve více různých stavech současně – tomu odpovídá spektrum možných hodnot dané veličiny, každá charakterizovaná určitou pravděpodobností.
12
Můžeme se stále ptát: „Jak to funguje? Jaký se za tímto zákonem skrývá mechanizmus?" Nikdo zatím za tímto zákonem nenašel žádny mechanizmus. Nikdo neumí víc „vysvětlit" než jsme si právě „vysvětlili". Nikdo neumí dát nějaký hlubší pohled na tuto situaci. Nemáme ani nejmenší potuchu o existenci nějakého fundamentálnějšího mechanizmu, z něhož by bylo možné odvodit tyto výsledky. Rádi bychom zdůraznili velmi důležitý rozdíl, který je mezi klasickou a kvantovou mechanikou. Mluvili jsme o pravděpodobnosti toho, že za daných okolností přiletí elektron. Předpokládali jsme, že v našem experimentu (nebo třeba v tom nejdokonalejším), by bylo nemožné exaktně předpovědět, co se stane. Můžeme předpovídat jen pravděpodobnosti. To by znamenalo, je-li to opravdu tak, že fyzika se vzdala možnosti pokusit se exaktně předpovědět, co se stane za daných okolností. Ano, fyzika se toho vzdala! „. [38]
3.3.
Paradox výpočtu pomocí qubitu Zdánlivý paradox spočívá v tom, že pomocí vhodně navrženého algoritmu je možné
pomocí jediného qubitu provést dva výpočty zároveň. Pomocí dvou qubitů jsou to čtyři výpočty, se třemi osm výpočtů a tak můžeme dál pokračovat. Z hlediska stavů můžeme říci, že klasický bit reprezentuje v danou chvíli jeden stav (0,1). Jeden qubit se může nacházet ve dvou stavech (0 nebo 1), dva qubity ve čtyřech (00 nebo 01 nebo 10 nebo 11), tři qubity v osmi atd. Pomocí jediného qubitu můžete provést dva výpočty zároveň, tři qubity osm výpočtů atd. Pokud budeme mít k dispozici kvantový počítač s 10 qubity můžeme provést1 024 výpočtů zároveň, se 100 qubity už je to nepředstavitelné množství výpočtů. Pro fungování kvantového počítače ovšem samotná vlnová superpozice nestačí. Je třeba přidat druhou základní vlastnost vln a tou je interference. [24]
13
3.4.
Vlnová interference a světlo Roku 1801 objevil britský lékař, fyzik a egyptolog Thomas Young5 jev dnes známý
jako vlnová interference světla. Experiment byl založen na průchodu paprsku světla dvěma rovnoběžnými štěrbinami, za kterými je umístěno stínítko. Vlivem difrakce světla je možné na stínítku pozorovat interferenční proužky. Z tohoto pozorování Young usoudil, že světlo má charakter vlnění. Pokud se na Youngův experiment pokusíme podívat optikou moderní fyziky,
lze
jej
charakterizovat
jako
uměle
generovaný
svazek
rovnoběžného
monochromatického záření dopadající na dvojici paralelních, úzkých a velmi blízko u sebe ležících otvorů. Světelná vlna se při průchodu otvory rozdělí na dvě vlny, jejichž dráhový rozdíl je dán násobkem jejich vlnových délek. Tyto vlny následně interferují na stínítku umístěném za otvory a dochází tak k vytvoření interferenčních obrazců.[14] Předpokládá se použití velmi slabého světelného zdroje, který generuje v jednom okamžiku pouze jediný foton. Stínítko tvoří citlivé detektory fotonů. Vzniká interferenční obrazec, to znamená, že foton prochází oběma štěrbinami současně a interferuje sám se sebou. Foton se při průchodu štěrbinami nachází v superpozici dvou stavů. Jednotlivé vlny tvořící superpozici nejsou pasivní a mohou jedna s druhou interferovat.
3.5.
Existence kvantového počítače v superpozici stavů Kvantový počítač využívá existenci výpočtů v superpozici stavů. Pokud budeme mít
kvantový počítač skládající se z 10 prvků, můžeme současně zaznamenat, že se nachází v 1024 stavech, a může tedy provádět 1024 výpočtů zároveň. Díky interferenci se tyto paralelní výpočty opět spojí dohromady a získáme tak jediný výsledek. Představme si projekt rozdělený na 1024 dílčích úkolů, přičemž na každém pracuje jeden člověk. Aby projekt zdárně dokončili, musí mezi sebou 1 024 lidí komunikovat a seznamovat se navzájem s výsledky. Právě to umožňuje kvantovému počítači interference. Lze si představit nárůst paralelně existujících výpočtů do řádu bilionů, trilionů nebo kvadrilionů. Teoreticky se lze dostat na počty paralelních výpočtů, které přesáhnou počet částic ve vesmíru.[8]
5 Thomas Young (13. červen 1773 Milverton – 10. květen 1829 Londýn), byl britský polyhistor vynikal mj. jako fyzik, lékař a egyptolog.
14
Nemusí to však nutně znamenat, že kvantovému počítači dojdou qubity. S pozoruhodnou myšlenkou přišel v roce 1957 absolvent univerzity v Princetownu pan Hugh Everet III. Jeho úvahy o nemožnosti zachycení stavu superpozice v reálném světě vedly k myšlence, že každý stav superpozice existuje v oddělené realitě, kde se kvantové události odehrávají. Podle teorie pana Evereta by se kvantový počítač měl po zadání úkolu rozdělit do mnoha vlastních identických existencí, kdy každá existuje v oddělené realitě. Interference zde hraje klíčovou úlohu komunikačního kanálu mezi jednotlivými realitami.
3.6.
Kvantová provázanost (entanglement, nonlokalita) Jedná se o další velmi důležitý kvantový jev, který zde musíme zmínit. Obecně ho lze
definovat jako stav, ve kterém jsou jednotlivé podsystémy systému navzájem korelovány. Díky této korelaci mají jakékoliv zásahy do tohoto systému okamžitý efekt na systému druhém. Tento efekt není závislý na rychlosti světla. V literatuře je možné setkat se s termínem“ nonlokalita“. Jeho příčinou je schopnost interagujících částic se dohromady „provázat“ tak, že vlastnosti jedné budou záviset na vlastnostech druhé. V elektronovém páru jsou na sobě závislé elektronové spiny (o spinu pojednává jedna z následujících kapitol). Provázané částice přestávají samostatně existovat, zůstávají propojeny bez ohledu na vzdálenost. [10]
3.7.
Spin a kvantová provázanost Spin částic nemá v klasické fyzice žádnou přímou analogii. Elementární částice
mohou mít různé množství spinů, jde o vnitřní moment hybnosti částice. Jednotlivé částice přispívají k celkovému momentu hybnosti soustavy. Nejjednodušší spin nalezneme v případě elektronů, které mohou rotovat jen dvěma různými způsoby. Představme si dva elektrony, první z nich se spinem po směru hodinových ručiček, druhý naopak tak, že jejich celkový spin se rovná nule. Zákon zachování úhlové hybnosti určuje, že celkový spin systému musí zůstat nezměněn. V roce 1982 nositel Wolfovy ceny za fyziku
6
Alain Aspect a jeho
kolegové z École Polytechnique vyslali v rámci pokusu pár fotonů a každý z nich směřoval do
6 Wolfova cena za matematiku, fyziku a chemii je často považována za nejprestižnější cenu hned po Nobelově ceně nebo Fieldsově medaili.
15
detektorů vzdálených od sebe 13 metrů. Detektory měřily polarizaci fotonů, která souvisí s jejich spinem. Aspectův tým prokázal, že změření polarizace fotonů v jednom z detektorů ovlivnilo polarizaci změřenou na druhém detektoru. Stalo se tak v čase kratším než 10 nanosekund, což je jen čtvrtina času, kterou by k překonání třináctimetrové vzdálenosti potřeboval světelný paprsek. Tento pokus vzhledem k svému výsledku dodnes vyvolává ve vědeckých kruzích emoce a jeho hodnocení i výklady jsou různé.
3.8.
Heisenbergův princip neurčitosti V podstatě jde o to, co se stane, pokud se během Youngova experimentu pokusíme
určit, kterým otvorem elektron prochází. Pokud se nám to podaří, povede to ke ztrátě interferenčních obrazců. Pokus o zjištění polohy elementární částice nebo změření její hybnosti vede k tomu, že čím přesněji změříme jednu vlastnost, tím méně přesně můžeme určit tu druhou. Jako první tuto matematickou vlastnost dvou vzájemně souvisejících veličin objevil a popsal německý fyzik Werner Heisenberg. Původní vyjádření Heisenbergova principu neurčitosti uvádí ve své knize profesor Feynmann takto: Měříme-li nějaký objekt a přitom dokážeme určit jeho složku hybnosti ve směru osy s nepřesností ∆, nemůžeme současně poznat složku jeho polohy s větší přesností než ∆
∆
Součin neurčitosti polohy a hybnosti v kterémkoliv okamžiku musí být větší než Planckova konstanta. Je to vyjádření zvláštního případu principu neurčitosti: Nelze zkonstruovat zařízení, jež by určilo, která ze dvou možností vznikla, aniž by současně nedošlo k porušení interferenčního obrazu. [40]
3.9.
Dekoherence a interakce kvantových počítačů s okolním prostředím V kvantové mechanice se setkáváme s kolapsem vlnové funkce, redukcí ze
superpozice několika stavů měřených veličin na jeden z těchto stavů. Okolní prostředí, každý foton okolo nás narušuje nebo zcela ruší interferenční schopnost jednotlivých stavů kvantové superpozice. V odborných kruzích nepanuje ještě úplná shoda, zda je kolaps vlnové funkce základním fyzikálním jevem, nebo se jedná o důsledek vzniku korelace mezi kvantovým 16
stavem pozorovatele a pozorovaného objektu. Právě proces přirozeného měření se nazývá dekoherence. Pokud tedy chceme hovořit o kvantovém počítači, je zde nutné zdůraznit, že musí být dokonale izolován od okolního prostředí. A to je základní problém. Udržet kvantový počítač v izolaci od okolí je pro vědce hlavní překážka, které musí při konstrukci takového zařízení čelit.
3.10. Potenciál kvantových počítačů Kvantové počítače mohou ze své podstaty zpracovávat jen přesně definovaný typ úloh, vedoucí na paralelní kalkulace, které se na konci spojí v jedinou odpověď. Právě proto se budou hodit k řešení přesně specifikovaných úloh. Pokud budeme schopni definovat úlohu vyhovující povaze kvantového počítače, bude ji schopen vyřešit v nesrovnatelně kratším čase v porovnání se počítači pracujícími na známých principech v konvenčním prostředí. Jednou z možností je nasazení kvantového počítače v oblasti kryptoanalýzy. V následujících kapitolách
se
soustředíme
na
možnou
implementaci
možností
kvantového
počítače a představíme některé algoritmy, které nativně využívají paralelní potenciál vlastní právě kvantovým počítačům.
3.11. Shorův algoritmus V průběhu roku 1994 Peter Shor pracující pro společnost AT&T, navrhl algoritmus provádějící rozklad celého čísla na prvočinitele. Klasické algoritmy řeší úlohu rozkladu celého čísla na prvočinitele v čase exponenciálně rostoucím s velikostí vstupu. Shorův algoritmus pracuje v polynomiálním čase. Stojí za to se zde zmínit podrobněji o vlastnostech tohoto algoritmu, neboť jeho využití ve spolupráci s kvantovým počítačem, může mít na kryptografické koncepty vliv (konkrétně na metodu RSA, o které budeme hovořit v některé z následujících kapitol). Algoritmus využívá paralelního potencionálu kvantového počítače kde je jeho běh definován v asymptotickém čase. Algoritmus nehledá jednotlivé součinitele, ale převádí řešení do dvou kroků. Prvním z nich je hledání periody určité periodické funkce , na kvantovém počítači a druhou hledání dvou společných dělitelů na klasickém počítači. Detailní popis nalezneme v práci pana Shora. [27]
17
3.11.1.
Hledání periody funkce pomocí kvantového počítače.
Příklad je sestaven na základě práce P. Shora. [27] Pro pochopení souvislostí v dalším výkladu není plné pochopení algoritmu nezbytně nutné, ale jeho uvedení v této práci považuji za přínosné, neboť tento algoritmus hraje klíčovou roli při nasazení současných kvantových počítačů. Definujme následující: ,
!
"#$ %
kde je náhodné celé číslo nesoudělné s %. Perioda funkce je definována jako "#$ % &. Všechny hodnoty funkce odpovídající & jsou stejné:
, , & platí: '
≡ 1 "#$ %
upraveno:
'/
+ 1
'/
1 ≡ 0 "#$ %
Poslední krok je převodem funkce na algoritmus hledání největšího společného dělitele. Pro výpočet periody - dané funkce použil Peter Shor paralelní potenciál kvantového počítače a ve své práci uvádí příklad s použitím kvantových registrů Q1, Q2. Z důvodu různého počátečního ofsetu periody u každého výsledku měření a z důvodu správného určení periody a její nezávislosti na počátečním ofsetu používá Fourierovu kvantovou transformaci na Q1 s návratem výsledku na Q1. Fourierova transformace mapuje funkce v časové doméně na funkce frekvenčního spektra. Na začátek je nutné zvolit y nesoudělné s n a q, pro které platí 2% / 0 / 3% Registr Q1 |ψ} – kvantový registr se superpozicí čísel 0 až q-1, Registr Q2 obsahuje nuly. Registr Q1 přejde do stavu:
|ψ3
1
4q
89
6 |a, 03 :;<
Z hodnoty - budou paralelně vypočteny hodnoty funkce , Vypočtené hodnoty budou uloženy do Registru Q2 18
|ψ3
1
4q
89
6 |a, y : mod n3 :;<
Následuje měření části registru Q2 – výsledek je hodnota k. Registr Q2 je uveden do superpozice čísel s funkční hodnotou k a má představovat projekci registru, ve kterém byly zastoupeny všechny hodnoty funkce ,
|ψ3
1
4|A|
6 | a′, k3 :C∈E
Zavedení kvantové Fourierovy transformace na registru Q1 z důvodu závislosti na počátečním offsetu:
|ψ3
1
1
89
IJ:K L 6e M
6 4|A| :C∈E 4q N;<
|c, k3
Díky Fourierově transformaci získáváme převod stavu registru | ′3 na registr
|P3 s různými amplitudami. Stavy, které se vyskytují v okolí násobků 1/& mohou být naměřeny s vyšší pravděpodobností. Stav | ′3, který obsahuje ofset, se přesunul do fázového
faktoru. Postup je nutné opakovat do doby, než dostaneme dostatečný počet vzorků z okolí násobků převrácené periody a tento postup nám umožní periodu jednoznačně určit. Dostáváme: M
c′ Q , '
kde λ jsou násobky s vysokou pravděpodobností z okolí převrácené
periody a pomohou ji jednoznačně určit, c' je jedním násobkem λ výrazu
M '
.
Výraz je možné upravit takto pro λ S T: P′ Q Q & Odhad naměřeného násobku λ je proveden rozvojem
LC M
do řetězcového zlomku. Je-li známá
hodnota &, lze Eukleidovým algoritmem vypočítat největšího společného dělitele: U V
U V
+ 1, %
1, %
Zajímavý a dostupný rozbor Shorova algoritmu můžeme také nalézt v práci pana Bashara.[34] 19
4.
Úvod do základních pojmů kryptografie.
4.1.
Základy kryptografie a použitá terminologie Kryptologie
je
naukou
o
šifrách.
Kryptografie
je
uměním
a
vědou
o
vytváření a navrhování šifer neboli kryptosystémů. Její hlavní úlohou je skrýt obsah komunikace mezi dvěma zainteresovanými stranami před další, nezainteresovanou stranou. Kryptosystém je mechanismus nebo schéma, jehož hlavním cílem je udržet obsah komunikace nečitelný pro nezainteresované strany. Kryptografové jsou částí komunity, která šifry a šifrovací standardy vytváří. Kryptoanalýza je uměním a vědou o zdolávání nebo dokonce prolamování šifer. Kryptoanalytici, jsou druhá část komunity, která se zabývá vývojem systémů a postupů sloužících k prolomení šifer. Kryptologie zastřešuje obě komunity. Kryptografie je dobře zavedený vědní obor, který má na historii vliv již bezmála dva tisíce let. Snaha skrývat význam a obsah zpráv je tak stará jako písmo samo. První příklady šifrování lze nalézt v Egyptě, kde byly některé nápisy v hrobkách tesány tak, aby skrývaly
svůj
skutečný
význam.
Mezi
první
příklady
šifer
patří
hliněné
tabulky z Mezopotámie, na nichž byl zašifrován recept na hrnčířskou glazuru. [28] V roce 2002 byl přijat nový americký šifrovací standard AES. Jeho nejkratší klíč má 3.10XY možných hodnot a jeho rozluštění pomocí veškerého současného výpočetního potenciálu je v reálném čase nemožné. [17] V této kapitole se blíže seznámíme se základy kryptografie. Přiblížíme si termíny a postupy, se kterými se budeme dále v této práci setkávat. Rozsah práce bohužel neumožní detailní seznámení s probíranou tématikou a proto pro podrobnější a ucelené informace o tématice doporučuji velmi zdařilé kurzy profesora Dana Boneha ze Stanfordovy University, dostupné on-line. [35]
4.2.
Symetrické šifrování Symetrické šifrování, v literatuře se můžeme setkat s termínem kryptografie podle
symetrického klíče, je charakterizováno použitím jednoho tajného klíče. Tento tajný klíč je uchováván takovým způsobem, aby bylo zabráněno jeho vyzrazení stranám, které nemají v komunikaci participovat a znát její obsah. Tajný klíč je použit pro zašifrování a dešifrování komunikace mezi dvěma zainteresovanými stranami. Moderní kryptografické 20
systémy pracující se symetrickým klíčem můžeme rozdělit do dvou základních kategorií a to blokové šifry (block ciphers) a proudové šifry (stream ciphers). Bloková šifra pracuje obvykle s velkým textovým polem (velikosti 64 – 128 bitů). Původní text v bloku je transformován pomocí šifrovacího algoritmu řízeného klíčem do nového bloku dat označovaném jako bloková šifra. Šifrovaný text je distribuován a jeho dešifrování probíhá pomocí stejného klíče a algoritmu. Pokud celkový objem dat přesáhne velikost definovaného bloku, je generován blok další a prostor v posledním neúplně zaplněném bloku je doplněn daty, která se zprávou nesouvisí. Slabinou symetrické blokové šifry je opakované používání stejného klíče i algoritmu na po sobě jdoucí bloky textu, nebo dokonce na všechny bloky textu. Pro odstranění této slabiny je v praxi použit další vstup, který má za úkol snížit pravděpodobnost zachycení opakujících se částí blokové šifry a vnést do celé komunikace prvek náhodné sekvence. Typickým příkladem blokové šifry je DES (Data Encryption Standard) ustanovený v roce 1977 jako standard pro šifrování dat v civilních státních organizacích USA. Pro úplnost dodejme, že tato šifra používá klíč o délce 64 bitů rozdělený na dvě části, 56 bitů tvoří efektivní část klíče a 8 bitů je kontrolních. Nástupcem DES je v dnešní době hojně používaný standard AES (Advanced Encryption Standard) přijatý v roce 2001. Na rozdíl od DES má pevně danou velikost bloku na 128 bitů. Velikost klíče šifry AES může být 128, 192 nebo 256 bitů. Můžeme se s ním setkat například v zabezpečení WPA2 pro bezdrátové sítě Wi-Fi. [22] Na rozdíl od blokové šifry používá proudová šifra, malé bloky dat. Setkat se můžeme i s blokem obsahujícím jeden bit nebo byte. Šifrování každého bloku proudové šifry může být přímo závislé na obsahu a sledu předcházejících bloků. Datový tok je kombinován s proudem bitů generovaných deterministickým algoritmem7 (pseudonáhodný proud bitů) často pomocí funkce XOR. Výsledný datový tok je kontinuálně ovlivňován neustále se měnící transformací vytvořenou pomocí šifrovacího klíče a šifrovacího algoritmu. V důsledku platí, že pokud je stejný text šifrován v různém časovém okamžiku pomocí stejné proudové šifry, vytvoří rozdílný šifrovaný kód. Proudová šifra je koncepčně velmi podobná generátoru pseudonáhodných čísel.
7 Deterministický algoritmus je algoritmus, který na stejný vstup (resp. na stejné výchozí podmínky) reaguje vždy stejně (tedy předvídatelně) a v každém jeho kroku je vždy jednoznačně definován i krok následující.
21
Účelem každého kryptosystému, je zabránit nechtěné třetí straně v narušení nebo zachycení obsahu komunikace mezi dvěma zainteresovanými stranami. Ani jedna ze stran zúčastněných v šifrované komunikaci nemůže mít spolehlivé a ucelené informace.nebo znalosti o možnostech této třetí strany, pro jednoduchost jí můžeme nazývat „útočník“. Je nutné vždy předpokládat, že „útočník“ má vždy částečnou nebo také úplnou znalost algoritmů a postupů použitých v konkrétním kryptosystému.
4.3.
Jednosměrné funkce Jednosměrná funkce tvoří základ většiny konceptů moderní asymetrické kryptografie.
Obecně lze hovořit o takové funkci, kterou lze snadno vyčíslit, ale je velmi obtížné v reálném čase odvodit její vstupní hodnoty. Důvodem je obvykle velké množství potencionálních řešení, které je nutné ověřit8. Pro kryptografii jsou zásadní dvě kategorie jednosměrných funkcí - hašovací funkce a jednosměrné funkce se zadními vrátky (v anglické literatuře známé jako trapdoor functions). S konceptem jednosměrných hašovacích funkcí jsou často spjaté další vlastnosti, například pro každé v rámci domény Z nesmí být mnohočlen
menší než . Příkladem jednosměrných hašovacích funkcí používaných v kryptografii jsou koncepty MD5 (Message Digest Algorithm) a SHA (Secure Hash Algorithm). Obecně se
jedná o aplikaci funkce, která z libovolného vstupu dat bez ohledu na jeho kvalitu a velikost vytváří výstup s předem danou délkou. Hlavní výhodou algoritmu je, že i velmi malá změna na vstupu vede k velké změně dat na výstupu. [22]
4.4.
Funkce s padacími dveřmi a kryptografie veřejných klíčů. Funkce s padacími dveřmi je jednosměrná funkce s odpovídající částí informace
určené pro snadnější výpočet inverzní funkce. Funkce s padacími dveřmi jsou zásadní pro kryptografii veřejného klíče (Public Key Cryptography). Myšlenka kryptografie veřejného klíče a její aplikace v praxi umožnila zveřejnění šifrovacího algoritmu, šifrovacího klíče a šifrovací metody. To vše je možné realizovat, aniž by byla ohrožena bezpečnost šifrovaného obsahu. Zásadní vlastností asymetrických algoritmů je paralelní existence
8 Matematický důkaz existence jednosměrných funkcí v současné době chybí.
22
soukromého klíče (Private Key) a veřejného klíče (Public Key). Asymetrické algoritmy jsou navrženy tak, aby veřejný klíč používaný pro šifrování, byl rozdílný od soukromého klíče používaného pro dešifrování. Veřejný klíč, jak už název napovídá, může být zveřejněn. Je zde tedy možnost, že libovolná osoba může použitím veřejného klíče zprávu zašifrovat. Pouze přesně definovaná osoba vlastnící soukromý klíč může zprávu dešifrovat. V porovnání s mechanismy symetrické kryptografie, kde efektivitu a bezpečnost celého systému tvoří především vlastní návrh příslušného algoritmu, je u asymetrické kryptografie zásadní především použitá algebraická platforma. Jednou z možností realizace kryptografického systému je využití eliptických křivek realizované prostřednictvím ECDSA (Elliptic Curve Digital Signature Algorithm). [21]
4.4.1. Diffie-Hellmanova výměna klíčů V roce 1976 publikovali pánové Whitfield Diffie a Martin Hellman ve vlastním časopise "New Directions in Cryptography" zásadní článek o nových možnostech kryptografie. Jednalo se o radikálně nový způsob distribuce kryptografického klíče, který řeší jeden ze základních problémů kryptografie a to je překvapivě distribuce kryptografických klíčů. Tento způsob distribuce je známý jako Diffie-Hellmanova výměna klíčů. Článek téměř okamžitě podnítil vývoj nové třídy šifrovacích algoritmů a mimo jiné byly položeny základy asymetrických kryptografických metod. V návaznosti na tuto práci v roce 1978 vzniká první asymetrický šifrový systém - RSA.
4.4.2. RSA (Rivest, Shamir, Adleman) Metoda RSA (podle iniciál autorů Rivest, Shamir, Adleman) je příkladem šifry s veřejným klíčem. Je jí obvykle přisuzováno prvenství mezi algoritmy, vhodnými jak pro podepisování, tak šifrování. Při dostatečné délce klíče je považován za bezpečný. RSA se pokouší odstranit problémy a nedostatky symetrické kryptografie. Principiálně je nutné před začátkem komunikace předat veřejné klíče. Tyto klíče mohou být distribuovány libovolnou cestou, na jejich utajení nezáleží. Důležité je ověřit autenticitu a integritu přijatého klíče. Jediný pár klíčů je možno bezpečně použít pro komunikaci s neomezeným počtem uživatelů. Síla kvalitní asymetrické šifry závisí na délce klíče.
23
4.4.3. ElGamal algoritmus ElGamal je aplikací asymetrického šifrovacího algoritmu a veřejného klíče, který je založen na Diffie-Hellmanově výměně klíčů. Tuto metodu popsal Taher ElGamal v roce 1984. ElGamal šifrování je použito například ve svobodném softwaru GNU Privacy Guard a poslední verzi PGP. Známé jsou i aplikace v dalších kryptografických systémech. Algoritmus ElGamal pro digitální podpis by neměl být zaměňován s ElGamal šifrováním.
4.4.4. DSA Digital Signature Algorithm je standardem americké vlády pro digitální podpis. Byl navržen americkým institutem NIST (National Institute of Standards and Technology) v roce 1991. Specifikován je v dokumentu National Institute of Standards and Technology FEDERAL INFORMATION PROCESSING STANDARDS FIPS 186 , který byl přijat v roce 1993. Minoritní úprava standardu byla vydána v roce 1996 jako FIPS 186-1. Standard byl dále rozšířen v roce 2000 jako FIPS 186-2 a v roce 2009 jako FIPS 186-3.9 Jeho autorství je připsáno Davidovi W. Kravitzovi, zaměstnanci Národní bezpečnostní agentury Spojených států amerických. Národní institut standardů a technologie tento patent dal celosvětové veřejnosti k volnému použití bez poplatků. Algoritmus DSA je založen na výpočtu diskrétního logaritmu, podobně jako algoritmus ElGamal. Je využíván jako standard pro elektronický podpis například v USA. Algoritmus DSA může používat klíč libovolné délky, obvykle se dle doporučení tvoří klíč dlouhý 512 bitů a 1024 bitů. [30]
4.5.
Kryptografie na bázi eliptických křivek - algoritmus digitálního podpisu (ECDSA) Protokol digitálního podpisu s využitím eliptických křivek (The Elliptic Curve Digital
Signature Algorithm, ECDSA) je varianta DSA protokolu, která využívá eliptických křivek. Standard byl přijat v roce 1999 jako ANSI standard a v roce 2000 jako IEEE a NIST standard. Byl také přijat v roce 1998 jako ISO standard, a v současné době je zvažováno jeho zahrnutí
9 DSA je patentováno pod číslem 5231668.Inventors:Kravitz; David W. (Owings Mills, MD) Assignee: The United States of America, as represented by the Secretary of Commerce (Washington, DC)
24
do některých jiných norem ISO. Kryptografie na bázi eliptických křivek (Elliptic Curve Cryptography, ECC) je moderní směr, který v současné době přináší lepší výsledky než ostatní používané kryptografické systémy. Užití eliptických křivek pro návrh asymetrických kryptografických systémů poprvé navrhli v roce 1985 pánové Victor Miller a Neal Koblitz . Jde o aplikaci známého systému s veřejným klíčem, ve kterém je modulární aritmetika nahrazena aritmetikou budovanou na základě operací s body na eliptické křivce. [21] [18]
4.6.
Digitální podpis Hlavním přínosem a důvodem zavedení digitálního podpisu, je zajistit možnost
ověření pravosti elektronického dokumentu. Každý elektronický podpis by měl být asociován právě s jednou entitou, osobou nebo institucí a jediným konkrétním dokumentem. Digitální podpis může často zastávat funkci garanta identity, neboť pouze entita, která je schopná použít konkrétní privátní klíč, může generovat konkrétní klíč ověřitelný prostřednictvím veřejného klíče. Digitální podpis je klasickou ukázkou kryptografie veřejného klíče. Celý proces digitálního podepisování lze popsat následovně, začíná se vypočtením hashe, což je číslo typicky obsahující několik stovek bitů. Výsledek je zašifrován pomocí autorova privátního klíče. Proces ověřování podpisu začíná opětovným vypočtením hashe zprávy. Následně je pomocí veřejného klíče autorova podpisu dešifrován obsah elektronického podpisu a výsledek je porovnán s vypočteným hashem přijaté zprávy. Pokud jsou obě hodnoty hashe stejné, lze považovat dokument za původní originál. Otázkou zůstává, kdo je majitelem veřejného klíče, pomocí kterého došlo k ověření podpisu v ověřovacím procesu. V praxi se uplatňuje přenos důvěry na třetí stranu pomocí údajů a o majiteli veřejného klíče, takzvaná certifikační autorita, která vydává digitální certifikát. Aby se předešlo cyklickému ověřování pravosti certifikátu a certifikační autority, je vytvořeno v každém počítači takzvané úložiště digitálních certifikátů, kde jsou uloženy kořenové certifikáty, veřejné klíče certifikačních autorit.
4.7.
Problematika generování „náhodných“ čísel Pro mnohé kryptografické koncepty je zásadní otázkou generování náhodných čísel,
které úzce souvisí s náhodnými jevy obecně. Kauzální vysvětlení náhodných jevů definuje vztah mezi příčinou a následkem, nic se neděje bez příčiny. Podle determinismu neexistují skutečně náhodné jevy, stav “náhodnosti“ navozuje pouze neznalost konkrétních příčin. 25
Generátory náhodných čísel jsou tedy vyvinuty za účelem dosažení co nejpřesvědčivějšího výsledku při vytvoření pseudonáhodného čísla. Jedná se o proceduru nebo komplexní zařízení, které je schopné na základě vstupních hodnot a nastavených parametrů generovat „náhodná“ čísla. V praxi lze vycházet například z fyzikálního jevu, který je považován za náhodný, nebo spoléhat na výpočetní algoritmus. Generování náhodného čísla naráží na nedostatek v oblasti klasických algoritmů, v podstatě neexistuje žádný, o kterém by se dalo říci, že by v této oblasti mohl hrát zásadní roli. Není možné generovat opravdu náhodné číslo, všechny klasické generátory jsou založeny na výpočtu podle daného algoritmu.
26
5.
Teorie složitosti V roce 1965 pánové Juris Hartmanis a Richard E. Stearns položili základy teorie
složitosti. Teorie složitosti si od počátku klade řadu otázek ohledně řešitelnosti a klasifikace složitosti algoritmů a jejich řešitelnosti pomocí výpočetní techniky. Nejedná se jen o časovou náročnost algoritmů, roli zde hraje i náročnost prostorová, respektive nároky na operační paměť zamýšleného počítače a potažmo finanční náročnost celého projektu. Teorie složitosti také bezprostředně zasahuje do oblasti analýzy algoritmů a teorie vyčíslitelnosti. Na otázku, je-li zadání algoritmicky řešitelné, dokáže odpovědět i teorie vyčíslitelnosti. Na doplňující otázku, jak dlouho bude řešení trvat pro vstup dlouhý n, umí odpovědět až teorie složitosti. Pro názornost můžeme uvést následující příklady, trvání komprese bezeztrátovým kompresním algoritmem LZMA10 pro řetězec o délce n znaků, výpočet hodnoty Ackermannovy funkce [%, % a výpočet délky n podle formule Presburger logiky. Teorie vyčíslitelnosti nám pomůže vybrat vhodné řešení pro výpočet příslušných úloh (v těchto případech postačí Turingův stroj – bude probráno dále). Díky teorii složitosti budeme znát dobu komprese LZMA která s rostoucím n roste polynomiálně (%X %, doba \ ]
výpočtu % podle Presburger logiky v řádu 2
pro konstantní P , kde n je délka Presburger
formule). Oproti těmto příkladům hodnota Ackermannovy funkce [%, % roste velmi rychle také pro malá čísla, tedy i doba výpočtu je rychlosti nárůstu ekvivalentní (už pro % ^ 4 je
hodnota této funkce nepředstavitelná). V praxi to znamená, že LZMA se běžně používá (7zip), Presburger logika a Ackermanovy funkce jsou teoretický koncept bez praktického využití. [7] [3]
5.1.
Přehled tříd složitosti a základních teorémů V roce 1936 se teoretici Alan Turing, Alonso Church a Kurt Gödel zabývali
teoretickými základy a modely výpočetní techniky, pomocí kterých byla později definována moderní výpočetní věda. Tito pánové, nezávisle na sobě, hledali model, který by bez ohledu na fyzikální vlastnosti popsal chování libovolného výpočtu. Dnes nejčastěji zmiňovaným
10 LZMA (zkratka pro Lempel-Ziv-Markov-Chain Algorithm), je bezeztrátový kompresní algoritmus, vyvinutý programátorem Igorem Pavlovem, pro jeho archivační program 7-Zip
27
modelem je matematická abstrakce výpočetního stroje na bázi modelu Alana Turinga. V této kapitole se tedy budeme zabývat matematickými modely počítačů a provedeme i úvod do teorie složitosti. Při debatě o časové náročnosti algoritmů, bude pro přehlednost užitečné soustředit je do přehledných tříd složitosti, nebo do tříd sdílejících stejné limity nebo čas výpočtu pro příslušné výpočetní modely. Příkladem těchto limitů jsou: -
konstantní čas `1,
-
lineární čas `%,
-
polynomiální O%b pro k ^ 0,
-
exponenciální čas O2 pro k ^ 0.
e
Pomyslnou dělicí čáru mezi řešitelnou a neřešitelnou otázkou v oblasti složitosti tvoří hranice mezi polynomiálním a exponenciálním časem výpočtu, tedy pokud se zatím budeme pohybovat v oblastech klasické výpočetní techniky.
5.1.1. Deterministický Turingův stroj a třída složitosti P V roce 1900 německý matematik David Hilbert formuloval otázku, zda existuje mechanický stroj, kterým by bylo možné rozhodovat o pravdivosti libovolného matematického výroku. Alan Turinga tato otázka zaujala a na teoretické úrovni zpracoval návrh přístroje, který napodoboval postup matematika při hledání a vytváření matematického důkazu. Přístroj nahrazoval složitou symboliku matematických kroků pouze dvěma symboly (velmi podobné dnešnímu binárnímu vyjádření) a oddělovačem. K zápisu záznamů používal Turingův stroj nekonečnou pásku. Pro další funkce přístroje byly definovány ještě operace zápisu a posunu pásky, celkem tedy čtyři operace read, write, shift-left, shift-right. Turingův stroj má ještě jednu velmi důležitou vlastnost a to je vnitřní stav, při kterém jednotlivé operace provádíme. Čtený symbol spolu s vnitřním stavem tak určují další možnou akci a přechod do dalšího stavu. Chování Turingova stroje se plně řídí tabulkou přechodů, každý následující stav lze tedy jednoznačně určit například na základě čteného symbolu a aktuálního stavu. Chování Turingova stroje proto můžeme označit podle definice jako deterministické. Odpověď na Hilbertovu otázku tedy zní: neexistuje mechanický stroj, který by rozhodl pravdivost libovolného matematického výroku. Dokázáno právě díky Turingovu stroji, který může být s lehkou nadsázkou považován za ekvivalent moderního počítače. [16] 28
Definice Turingova stroje f g, h, i, j, , k: g – konečná množina vnitřních stavů, h – konečná abeceda symbolů a znaků, i ∈ g – počáteční stav Turingova stroje, j ∈ h – prázdný symbol – oddělovač, ⊆ g – množina koncových stavů, k ∶ g y h → g y h y {, | – přechodové funkce – posun čtecí hlavy vlevo, vpravo. První třídou složitosti, kterou se si zde představíme, je třída P reprezentující úlohy řešitelné právě pomocí deterministického Turingova stroje v polynomiálním čase. Třída P bývá považována za třídu obsahující „efektivně řešitelné“ úlohy. Do této třídy spadá například úloha nalezení největšího společného dělitele, rozhodnutí prvočíselnosti nebo nalezení maxima lineární funkce vzhledem k zadaným podmínkám. [16]
5.1.2. Nedeterministický Turingův stroj Nedeterministický
Turingův
stroj
může
během
výpočtu
podlehnout
nedeterministickým podnětům, respektive se jeho chování může stát nedeterministickým. Během svého běhu je schopen akceptovat vstup na bázi náhodného jevu pokud ten je veden v logické konfiguraci, který rozdělí probíhající výpočet na dvě nebo více samostatných vláken.
5.1.3. Pravděpodobnostní Turingův stroj a třída složitosti BPP Pravděpodobnostní Turingův stroj, je ekvivalentní svému deterministickému protějšku, ale na rozdíl od něj je schopen během „výpočtu“ provádět nedeterministické operace, tedy vývoj mezi jednotlivými stavy, se může řídit podle nějakého náhodného jevu. Následující stav Turingova stroje je určen stochasticky například hodem mincí nebo hrací kostkou. Výsledek náhodného jevu je ale v tomto teoretickém modelu možné ovlivnit pomocí váhových koeficientů. Pravděpodobnostní Turingův stroj je schopen řešit veškeré úlohy deterministického Turingova stroje s výhodou možnosti nalezení řešení rychleji. Stojíme tedy před volbou – jistota řešení u deterministického Turingova stroje a možnost nalezení správného řešení rychleji u pravděpodobnostního Turingova stroje. V obou případech 29
předpokládáme, že řešení úlohy existuje. Se znalostmi kvantové mechaniky bylo možné upravit pravděpodobnostní Turingův stroj tak, aby se zbavil zátěže klasické fyziky a popsat model kvantového výpočtu. Třída složitosti obvykle definovaná pro tento typ matematického stroje je označována BPP (v originále Bounded-Error Probablistic Polynomial-Time) a jde tedy o úlohy řešitelné v polynomiálním čase právě pomocí tohoto matematického stroje. [1] Důležité je uvědomit si, že se zde pracuje s pravděpodobností a je nutné vzít v úvahu pravděpodobnost chyby, v tomto případě je pravděpodobnost chyby maximálně 1/3. Jak popsal ve své práci již v roce 1977 John Gill [12] BPP ~
kde 0,1/2 Pravděpodobnost chyby klesá exponenciálně s počtem spuštěných běhů úlohy.
5.1.4. Jednoznačný Turingův stroj a třída složitosti UP Je definován pro přijetí pouze jedné konfigurační informace na jeden vstupní řetězec. Třída složitosti spojená s tímto matematickým strojem je UP (Unambiguous Nondeterministic Polynomial-time) a je úzce svázána s jednosměrnými funkcemi. Řeší se opět úlohy řešitelné v polynomiálním čase.
5.1.5. Kvantový Turingův stroj a třída složitosti BQP Kvantový Turingův stroj (Quantum Turing Machine dále jen QTM) je klasický Turingův stroj, který požívá k výpočtům kvantové operace. Na začátku byla myšlenka Paula Benioffa z roku 1974 o napodobení vývoje reverzibilního kvantového systému na Turingově stroji. Na práce Paula Benioffa a Richarda Feynmana navázal David Deutsch v roce 1985. Z jeho pera vzešel popis prvního opravdového kvantového počítače, jehož základní postuláty jsou podobné klasickému počítači. Čtení, zápis a posun pásky by měl probíhat pomocí kvantově-mechanických interakcí. Místo klasické reprezentace stavu pomocí 0-1 a mezery je použita superpozice stavů 0 a 1. Superpozice zde umožňuje využít kvantový paralelismus (viz kapitola 3.). David Deutsch otevřel svoji myšlenkou cestu pro úvahy o otázkách vypočítatelnosti, složitosti a potenciálu v oblasti kvantových počítačů. Jak jsme naznačili v kapitole 4.7, pro generování náhodného čísla v podstatě neexistuje žádný klasický algoritmus. Ve světě kvantových počítačů je tomu naopak. Využívá 30
přitom kolaps vlnové funkce (kapitola 3.5) o kterém si zatím myslíme, že je náhodný, při pokusu o zjištění stavu kvantového systému.
5.1.6. Kvantové třídy složitosti Stejně jako je možné roztřídit algoritmy u klasické verze Turingových strojů, je možné definovat kvantové třídy složitosti. Zde je příklad [32] [33]: Klasická třída složitosti: P
schůdné algoritmy běžící v polynomiálním čase,
NP
neschůdné algoritmy; pouze správnost řešení lze ověřit v polynomiálním čase,
NP-úplný
problémy vzájemně mapovatelné v polynomiálním čase.
Pravděpodobnostní třídy složitosti: ZPP
problémy řešitelné s jistotou v průměrně polynomiálním čase na PTS,
BPP
problémy řešitelné (p > 2/3) v nejhůře polynomiálním čase na PTS.
Kvantové třídy složitosti: QP
problémy řešitelné s jistotou v nejhůře polynomiálním čase,
ZQP
problémy řešitelné s jistotou v průměrném polynomiálním čase,
BQP
problémy řešitelné s (p > 2/3) v nejhůře polynomiálním čase.
5.1.7. Univerzálnost Turingova stroje Okrajově bude nutné zmínit se o termínu univerzálnost Turingova stroje. Tento termín vyjadřuje schopnost efektivně nahrazovat (simulovat) jeden Turingův stroj jiným Turingovým strojem. Pokud budou vytvořena transformační pravidla pro první Turingův stroj jako program pro jiný Turingův stroj, bude tento druhý stroj schopen simulovat práci a výpočty stroje prvního. Seth Lloyd a Christof Zalka potvrdily v roce 1996, že kvantové systémy mohou efektivně simulovat práci jiných kvantových systému. A tím se dostáváme znovu opakovaně k paralele s klasickou výpočetní technikou.
31
5.1.8. Zázračný Turingův stroj Jedná se o abstraktní stroj, který se používá ke studiu v problematice rozhodování (Oracle Turning Machine). Stroj je vybaven páskou, na které se po zápisu otázky po uplynutí určitého časového úseku objeví odpověď, respektive otázka je vystřídána odpovědí, respektive problém rozhodnutí je vyřešen během jediného kroku. Zázrak je v tomto ohledu chápán jako entita schopná v jediném kroku rozhodnout problém na úrovni odpovědi ano nebo ne. Úlohy předkládané tomuto teoretickému stroji by neměli být na úrovni úloh pro klasické výpočetní stroje. Zázračný Turingův stroj je příkladem relativizované složitosti. [16]
5.2.
Názvosloví tříd složitosti V současnosti jsou již poměrně dobře zmapované různé kategorie a třídy složitosti a
do jejich názvosloví je vnesena určitá konvence: [31] (N)SPACE[log(n)] = (N)L, (N)TIME[poly(n)] = (N)P, (N)SPACE[poly(n)] = (N)PSPACE, (N)TIME[2n] = (N)EXPTIME, (N)SPACE[2n] = (N)EXPSPACE, (N)TIME[22n] = (N)EXP2TIME. (N) – nedeterministický přístup. Poly – polynomiální.
5.3.
Jednoduché úlohy a komplikované úlohy Pokud se budeme zabývat složitostí, po čase se jistě dostaví otázka co je snadné a co je
složité, nebo které úlohy jsou jednoduché a které budeme považovat za komplikované. Hranici mohou tvořit polynomiální třídy složitosti a exponenciální třídy složitosti. V souvislosti s kryptografií může být určení hranice mezi složitými a jednoduchými úlohami zásadní, stejně jako možnost posouvání této hranice s aktuálním stavem poznání a možnostmi výpočetní techniky. Už pouhá záměna třídy obtížnosti P za BPP (která je dnes považována za 32
hlavní třídu složitosti pro úlohy řešitelné v polynomiálním čase) může zásadním způsobem změnit pohled na obtížnost jednotlivých úloh. [20] Klasifikace obtížnosti samozřejmě může záviset i na tom, zda nahradíme klasické třídy složitosti kvantovými a klasické počítače kvantovými počítači. Pro naše úvahy o kryptografii a teorii složitosti bude užitečné definovat nějaké základní postuláty, které musí být zároveň schopny flexibilně reagovat na případný vývoj v oblasti teorie složitosti a potažmo také kvantových počítačů. Hranice mezi složitými a jednoduchými úlohami se může každým dnem posouvat, nebo měnit. Obvyklým řešením v diskuzi o této hranici je její stanovení do míst kde končí úlohy vypočitatelné algoritmy v čase `%b pro konstantní hodnotu parametru . Některé třídy složitosti ale balancují na hraně mezi polynomiálním a exponenciálním výpočetním časem. Klasifikace mezi těžkými a snadnými úlohami v případě úloh, kde je třeba se rozhodnout mezi možnostmi je závislá i na způsobu, který pro řešení úlohy použijeme. Pro naše potřeby definujeme dvě nestandardní třídy složitosti a to třídu % $%% pro úlohy, které jsou řešitelné snadno i pro % dosahujících vysokých hodnot a % pro
% dosahujících vysokých hodnot. V dalších kapitolách použijeme toto rozdělení pro klasifikaci úloh pro klasické i kvantové počítače. [19] [2]
33
6.
Teorie složitosti a základní kryptografické koncepty
6.1.
Aplikace Teorie složitosti v kryptografii Předtím než se pustíme do analýzy vlivu kvantových počítačů na kryptografii, bude
užitečné definovat a objasnit některé detaily kryptografických konceptů. Seznámíme se s několika základními faktory, které ovlivňují bezpečnost vybraných kryptografických konceptů. Je nutné zdůraznit, že bezpečnost zde zmiňovaných konceptů úzce souvisí s výpočetní náročností, tedy v přeneseném významu se složitostí a výpočetními možnostmi použité hardwarové platformy. Nebudeme se tedy zabývat koncepty kryptosystémů, které patří do kategorie informačně-teoreticky bezpečné (information-theoretically secure). Sem patří systémy, kde případná třetí strana nezainteresovaná v komunikaci nemůže mít dostatek informací pro dešifrování šifrované komunikace, bez ohledu na znalost použitého algoritmu. Typickým příkladem takového systému je jednorázová šifrovací pomůcka založená na jednorázové tabulce. Klíče se používají jako bezpečnostní prvek tak, že pouze správný klíč může dešifrovat šifrovaný text do prostého textu. Mnoho šifer je založeno na veřejně známých algoritmech, nebo na otevřených zdrojích a tak je jen obtížné získat klíč, který je správný, za předpokladu, že neexistuje žádný analytický útok a také, že klíč není jinak dostupný (například pomocí krádeže, vydírání, či ohrožení počítačových systémů). Představa, že by bezpečnost systému měla záviset na klíči samotném, byla formulována Augustem Kerckhoffsem (v roce 1880) a Claude Shannonem (v roce 1940), tyto zákony jsou známé jako Kerckhoffs 'a Shannon Maxim principy. Klíč by měl být dostatečně dlouhý, aby útok hrubou silou nemohl být proveden. Shannonovy práce na informační teorii ukázaly, že k dosažení tzv. dokonalého utajení, je nezbytné, aby délka klíče byla alespoň tak dlouhá jako je zpráva a klíč se použil pouze jednou (One-time pad). S ohledem na to, a na praktickou potíž takových dlouhých klíčů, moderní kryptografická praxe vyřazuje pojem dokonalé utajení jako požadavek na šifrování, a místo toho se zaměřuje na výpočetní bezpečnost, v jejímž rámci výpočetní požadavky prolomit šifrovaný text musí být pro útočníka nemožné. [28] Pro nás je důležité si z této stati zapamatovat, že úspěšnost kryptografických konceptů je možné měřit jednoduchostí jejich nasazení v praxi a obtížností jejich případného prolomení.
34
6.2.
Definice základních kryptografických pojmů a postulátů Pokud budeme v následujícím textu používat označení f budeme mít na mysli, že
jde o prostor pro zprávu. Pokud bude použito
půjde o prostor pro šifrovaný text.
6.3.
Kryptografie symetrického klíče Každá instance symetrického kryptosystému obsahuje šifrovací a dešifrovací funkce.
Tyto funkce mohou být ekvivalentní, respektive jejich algoritmy mohou být totožné. Dále je zde prostor pro zprávu, prostor pro klíč a prostor pro zašifrovaný text.
6.3.1. Definice symetrického klíče Pokud budeme hovořit o kryptografii symetrického klíče, můžeme definovat následující: "&P Z& Z, , f, ,
3 Pro toto vyjádření dále platí, že funkce Z: f y →
je vyjádřením šifrovací funkce
symetrického klíče a funkce :
y → f je vyjádřením dešifrovací funkce symetrického
klíče, – je prostor pro klíč respektive sadu znaků z libovolné abecedy tak aby byla splněna následující podmínka: Z", , " &# ž$é ∈ , " ∈ f Abychom mohli zahájit diskuzi o případných možnostech a náročnosti prolomení tohoto kryptografického konceptu, bude nutné seznámit se s dalšími definicemi.
6.3.2. Definice zprávy šifrované podle symetrického klíče Pro každou zprávu f platí, f∅ f ∪ ∅ Můžeme zavést, že f∅ je potenciální prostor pro zprávu rozšířený o ∅, tj. o prázdný
prostor pro zprávu. Znamená to, že entita m ∈ f∅ může být nějaká zpráva nebo jen prázdný prostor pro zprávu. Pokud bychom zvažovali, že případná třetí strana participující na prolomení zašifrované komunikace dvou zainteresovaných stran, má zaznamenat úspěch, 35
bude schopna přečíst obsah zašifrované zprávy v jeho původní podobě bez znalosti příslušného dešifrovacího klíče. Aby něco takového bylo vůbec možné, je nutné, aby třetí strana byla schopná identifikovat klíč použitý k zašifrování původní zprávy nebo dešifrovací klíč. Jak už jsme zmínili, šifrovací a dešifrovací algoritmy mohou být ekvivalentní. Pokud chceme hovořit o tom, že kryptosystém je prolomen, znamená to, že třetí strana je schopna číst původní obsah zpráv zašifrovaných pomocí tohoto kryptosystému bez předchozí znalosti dešifrovacího klíče. Pokud dojde k pokusu o prolomení kryptosystému a třetí strana nemá k dispozici správný dešifrovací klíč, nemůže být odhalen obsah původní zprávy. Abychom se vyhnuli detailům a diskusi o možnostech získání tohoto klíče definujeme pro zjednodušení funkci „nalezení klíče“ pomocí Turingova zázračného stroje. [16]
6.3.3. Definice funkce nalezení klíče - symetrické šifrování V případě symetrického šifrování funkce „nalezení klíče“ I může mít za výsledek informaci o pravdivosti nebo nepravdivosti nalezeného klíče nebo obsahu zprávy (v případě jednosměrných hashovacích funkcí). Turingův zázračný stroj (viz kapitola 4.9.8) nám může v tomto případě poskytnout odpověď ve stylu „Pravda – Nepravda“ pokud bude dosaženo správného obsahu zprávy, nebo korektního dešifrovacího klíče. V průběhu této práce se omezíme pouze na velmi stručný výklad a nebudeme se
zabývat detaily. Důležité je, že definovaný model může posloužit jako test. V případě, že třetí strana má k dispozici dostatek zašifrovaného textu a nějaké znalosti o obsahu
původní zprávy, vrátí tento test hodnotu „Pravda“ pokud zamýšlená kompozice
prolomené zprávy bude ekvivalentní původní zprávě, nebo struktura dešifrovacího klíče povede na sestavení původní zprávy. Pokud bychom byli na chvíli v roli třetí strany usilující o prolomení komunikace a naší jedinou znalostí o obsahu zprávy by bylo to, že
je napsána v českém jazyce, mohli bychom se spokojit i s tím, že pokus o dešifrování zašifrované zprávy skončí s výsledkem, který bude možné identifikovat obsahově jako zpráva psaná v českém jazyce.
Pokud má případná třetí strana k dispozici dostatek šifrovaného materiálu, lze
použít například metodiku frekvenční analýzy, která byla vyvinuta už ve středověku. To bychom ale odbočili příliš do minulosti.
36
6.3.4. Prolomení symetrického šifrování Prolomení symetrického šifrování za pomoci Turingova zázračného stroje lze popsat jako následující funkci:
&##"% "&P Z& :
y f∅ ¡ → ¢. Jak jsme v předchozím textu této kapitoly uvedli 5.4.3, budeme používat teoretický koncept Turingova zázračného stroje pro testování výsledku a úspěšnosti potencionálního útoku, reprezentováno v entitě:
&##"% "&P Z& parametrem ¦,, která prověří polynomiální množství kombinací dvojic zašifrovaného a dešifrovaného textu a vytvoří výstup funkce ´ ∈ ¨ ∶ © → ª pomocí které lze dešifrovat zašifrovaný text (tím nejsložitějším možným způsobem, ale to v tomto případě není důležité). Nejdůležitější moment a zásadní bod v případě symetrické šifry je spočítat a analyzovat množství kombinací dané předpisem:
&##"% "&P Z& ∶ «P, ", P , " ….. P, " ´ kde platí: ∃ ∈ ∀P ∈
∃" ∈ f: ¦ &° ∧ " P, ∧ " ^´ P V tuto chvíli se trošku vzdalujeme od reálného pojetí kryptografie, protože v praxi
je kryptosystém považován za ohrožený už v případě, že je možné přečíst polovinu původně zašifrovaného textu. Případ definovaný v této kapitole spadá do kategorie,
všechno nebo nic. To znamená, že splnění podmínek nastane až v případě úplné shody dešifrovaného textu s původním zněním zprávy. [2] [25]
37
6.4.
Jednosměrná hashovací funkce Jednosměrné hashovací funkce Z vypočítávají hodnotu i ze vstupní
hodnoty . Výstup může mít fixní délku bez závislosti na délce vstupu, ale není to nutným
pravidlem. Hodnota je v podstatě předobrazem hodnoty pokud definujeme následující
Z . Hodnota – výsledný hash, má široké uplatnění v praxi. Jednosměrné hashovaní funkce jsou známé svým takřka nedeterministickým chováním, protože je velmi těžké nalézt dvojici a pro kterou by platilo: Z Z
6.4.1. Definice jednosměrné hashovaní funkce ³$%#i"&% ´ i °%P Z, µ, |, 3 pro kterou můžeme definovat Z: D y ¶ ¡ → je samotná hashovací funkce, D je doména funkce Z, R je rozsah funkce
Z, ∈ ¶ ¡ je délka definovaná pro konečný výstup h |Z, | . Pro prolomení jednosměrné
hashovaní funkce je nutné nalézt původní „předobraz“ jehož výsledná hodnota h vznikla po použití hashovací funkce. Funkce použitá k prolomení hashovaní funkce bude také pracovat s polynomiálním množstvím dvojic zpráv-vstupů a následně generovaných hashů.
6.4.2. Prolomení jednosměrné hashovaní funkce Prolomení jednosměrné hashovací funkce můžeme definovat následovně: &##"%·³$%#i"&% ´ i °%P¸ : ¶ ¡ y µ y |∗ → ¢ Opět použijeme vazbu na Turingův zázračný stroj I a vezmeme v úvahu veškeré
možné kombinace polynomiálního množství dvojic hashů a původních zpráv, kde hashe disponují omezením délky na konkrétní zadanou hodnotu. Výsledkem bude funkce: C ∈ ¢ ∶ | → D která vrátí „předobraz“ respektive původní znění zprávy o správné délce. Problém prolomení hashe můžeme definovat následovně: &##"%·³$%#i"&% ´ i °%P¸ «, $, & , $ , & , … … , $ , & C můžeme definovat 38
∀& ∈ » $ || &∃ $, $C , ∈ µ ∶ ¦$ &° ∧ «& Z$C , ∧ $ C C & Pro zjednodušení se nebudeme zabývat variantou výpočtu, která vezme v úvahu
skutečnost, že některé hashovaní funkce mohou pro rozdílné zadání textu zprávy vytvořit stejný výstupní řetězec – hash. ·2¸
6.5.
Kryptografie veřejných klíčů Jak už jsme zmínili ve čtvrté kapitole (4.4) v kryptografii veřejných klíčů mají dnes
zásadní úlohu jednosměrné funkce známé pod názvy „funkce s padacími dveřmi“ nebo „funkce se zadními vrátky“ (trapdoor function). Jde o to, že při znalosti určitých informací je snadné vytvořit k těmto funkcím funkci inverzní. V případě šifrování s použitím „funkce se zadními vrátky“ jde tedy o rychlé a snadné získání původního textu zašifrované zprávy. Bez příslušných znalostí je nalezení převrácené funkce velmi náročné na čas a použitý výpočetní výkon. Ještě jednou bychom si měli připomenout, že existence jednosměrných funkcí není v tuto chvíli exaktně matematicky dokázána, ale pro kryptografickou praxi je postačující tvrzení, že pravděpodobně existují. To je jeden z krásných paradoxů matematiky, která i přes to, že jednosměrné funkce jsou dnes jednou z nejpoužívanějších metod v šifrované komunikaci, stále pochybuje o jejich existenci, nemaje exaktního teoretického důkazu.
6.5.1. Definice funkce se zadními vrátky Nejprve bychom se měli zmínit o páru, který tvoří základ kryptosystému používajícího funkce se zadními vrátky. První část páru je funkce, která umožní zašifrování textu a obvykle ji označujeme jako veřejný klíč. Druhou část páru tvoří ona „zadní vrátka“, která umožňují snadno vytvořit funkci inverzní, umožňující zpětné získání původního textu ze zašifrovaného textu. Druhá část páru je označována jako soukromý nebo tajný klíč. Můžeme definovat následující vyjádření všech klíčových párů kde ·Z, ¸ - jsou funkce šifrování a dešifrování obsahující parametry podle příslušných klíčů: ·Z, ¸ ¼ ∈ ¼ , ½ ∈ ½ 3 pro funkce
Z: µ¼ y ¼ → |¼ : µ½ y ½ → |½
kde µ¼ µ½ definují doménu a |¼ |½ definují rozsah platnosti Z, . Parametry ¼ ½ reprezentují v tomto vyjádření šifrovací a dešifrovací algoritmus. ·25¸ 39
6.5.2. Definice kryptosystému používajícího funkce se zadními vrátky Pro veřejný klíč kryptosystému můžeme definovat následující ¾&¿% P ÀZ, , f,
, ·Z, ¸Á platí následující: Z: f y ¼ →
:
y ½ → f jsou funkce pro zašifrování v rámci veřejného klíče. ·Z, ¸ můžeme chápat jako prostor, ve kterém existují správné dvojice tvořící pár
pro šifrování a dešifrování tak že  ∈ ¼ , à ∈ ½ . Samotné  reprezentuje v této chvíli
veřejný algoritmus pro zašifrování zprávy. Entita à reprezentuje privátní klíč, sloužící
pro dešifrování zprávy. O tom, že klíčový pár je opravdu validní pro funkce Z a můžeme hovořit pouze v takovém případě, je-li zachována jeho jedinečnost a správnost. Obě tyto podmínky můžeme definovat následovně: ∀" ∈ f: Z", Â , Ã " ∀P ∈
: ZP, à  P Toto vyjádření může být považováno za definici správnosti klíčového páru. ∀«" ∈ f, ô Ä Ã ∈ ½ : ««Z",  , ô Ä " ∀«P ∈
, ´ Ä Â ∈ ¼ : «Z«P, à , ´ Ä P Toto vyjádření považováno za definici jedinečnosti klíčového páru. Už jsme zmínili, že jádrem každého kryptografického systému je funkce se zadními vrátky. Nyní můžeme zdůraznit, že tato funkce nemusí být nutně jedna neboť Z a nemusí
být stejné funkce. V naší definici tedy ¼ a ½ mohou být funkce a Z a může být také považováno za aplikaci těchto funkcí pro vytvoření zašifrovaného textu nebo dešifrování textu. Kritéria, obecně stanovená pro klíčový pár, nám naznačují, že zašifrování zprávy pomocí funkce Z a její opětovné dešifrování pomocí funkce bude reprodukovat původní
zprávu. Mělo by tomu tak být i v případě, že k šifrování textu použijeme funkci a k jeho dešifrování funkci Z. Podle definice by nemělo dojít k tomu, aby dva různé klíče šifrovaly zprávu do shodné šifry, nebo byly schopny dešifrovat zprávu šifrovanou klíčem jiného klíčového páru. ·2¸ ·25¸ 40
6.5.3. Prolomení kryptosystému s veřejným klíčem Prolomení kryptosystému s veřejným klíčem můžeme definovat následovně: &##"%·¾&¿% P¸ : ¼ → ¢ Vezmeme-li nějakou entitu generovanou veřejným klíčem a pokusíme-li se aplikovat funkci například C ∈ ¢:
→ f, která bude použita pro dešifrování zašifrované zprávy, dostaneme následují úlohu, vedoucí na výpočet, který můžeme definovat následovně &##"%·¾&¿% P¸ : «¼ C tak aby platilo: ∃«½ ∈ ½ ∀P ∈
∃" ∈ f: «¦«½ & Å$ ∧ Æ" «P, ½ Ç ∧ «" C P Identifikace správně dešifrované zprávy bude v případě systémů s veřejným klíčem jednodušší, vzhledem ke skutečnosti, že šifrovací klíč je veřejný, je tedy možné ho obstarat a vyzkoušet zda námi zašifrovaná zpráva, dešifrovaná podle námi vyvinutého algoritmu souhlasí s původním vstupem. [9] [25]
6.6.
Digitální podpis Problematika digitálního podpisu úzce souvisí s otázkou a definicemi kryptografie
veřejných klíčů. I zde vystupují zainteresované strany disponující veřejným a privátním klíčem a důležité je aby každá z nich mohla vytvořit digitální podpis, který by jí jednoznačně identifikoval jako autora původního dokumentu.
6.6.1. Definice digitálního podpisu Pro definici digitálního podpisu můžeme stanovit následující: µ % #$iÀZ, , f, , ·Z, ¸Á kde platí Z: f y y ½ → & Å$ , È& Å$ 3, dále můžeme definovat funkci která bude v tomto případě veřejným podpisovým klíčem : f → ¼ →
41
kde f je prostor pro zprávu, je prostor pro digitální podpis, ·Z, ¸ je prostor
obsahující správný podepsaný klíčový pár pro který můžeme definovat É ∈ ¼ , Ê ∈ ½ , É
je veřejný ověřovací klíč a Ê privátní podpisový klíč. I v tomto případě můžeme definovat
požadavky na správnost použitých funkcí tak že klíčový pár É , Ê je validním klíčovým párem pro funkce Z a právě když pro každé ", " ∈ f, i ∈ , Ê´ ∈ ½ : Z", ", Ê , É & Å$ Můžeme také uvést požadavky na unikátnost vyjádřené vztahy: " Ä " ∨ «Ê´ Ä Ê ⇒ Æ«" , Ê´ Ä ", Ê Ça «i Ä ", Ê ⇒ Z", i, É
È& Å$ U všech ověřovacích klíčů je podle výše uvedených pravidel požadováno, aby správně ověřily podpisy u všech dokumentů podepsaných s pomocí odpovídajícího podpisového klíče. Požadavky na jedinečnost přesně specifikují, že ověřovací klíč nemá provést pravdivé ověření podpisu pro zprávy, které byly podepsány jiným než odpovídajícím podpisovým klíčem.
6.6.2. Prolomení digitálního podpisu Prolomení digitálního podpisu můžeme definovat následovně:
&##"%·µ % #$i¸ : ¼ → ¢ pro danou entitu digitálního podpisu, při znalosti veřejného klíče hledáme funkci ´ ∈ ¢: f → která bude použita pro sestavení digitálního podpisu. Prolomení je závislé na schopnosti výpočtu:
&##"%·µ % #$i¸ : É ´ tak aby byly splněny následující podmínky: ∃«½ ∈ ½ ∀f ∈ ": «¦«½ & Å$ ∧ «Z«", «", ½ , É & Å$ ∧ «Z«", ´", É & Å$ O tom, že je digitální podpis prolomen, můžeme hovořit ve chvíli, kdy případná třetí strana participující
na
neautorizovaném
podpisu
dokumentu,
nebo
jeho
neautorizované
změně s podvrženým podpisem, dosáhne takového stavu věci, kdy nově vytvořený digitální podpis lze bez pochybností vydávat za správný a originální. Pokud nejsou dodržena kritéria 42
jedinečnosti je možné nalézt více variant digitálního podpisu, které se budou po ověření zdát jako jedinečné a správné. ·2¸
6.7.
Generování náhodných čísel Pokud se zde pokusíme definovat generátor náhodných čísel, bude užitečné uvažovat
především v rovině použitelné ve výpočetním prostředí, tedy v rovině binární. Použití výstupů dílčích součástí kryptosystémů v binárním stavu je v moderní kryptografii široce rozšířené. Pokud budeme v této podkapitole hovořit o náhodných číslech, půjde o ekvivalent náhodných čísel a to jsou čísla pseudonáhodná (viz kapitola 4.7) této práce.
6.7.1. Definice náhodných čísel Základní definici náhodných čísel můžeme pro naše potřeby provést takto: È #$%
i Z, 3 kde v naší definici Z: y È → 0,13 bude funkce generující náhodná čísla v binární podobě, È je množina všech přirozených čísel, je prostor reprezentovaný znaky z konkrétní abecedy. Dále by mělo platit že: Z, X … &# ž$é ∈ , ∈ , Í ∈ 0,13 Klíč v případě generátoru náhodných čísel můžeme chápat jako základní kámen pro proces generování náhodných čísel. Výstupem funkce Z je řetězec bitů, kde je charakteristickým rysem poměrná náročnost predikování hodnoty bitu Í bez znalosti
původního klíče. Setkáváme se s potřebou schopnosti na základě vstupních informací předpovědět, jaká bude hodnota následujícího bitu.
43
6.7.2. Určení hodnoty dalšího bitu V tomto případě je poněkud těžké hovořit o prolomení generátoru náhodných čísel, jedná se spíš o odhalení jeho algoritmů a schopnost určit hodnotu jím generovaných bitů. Tuto úlohu můžeme definovat následovně:
&##"%·È #$%
i ¸ : 0,13 y È → ¢ Vezmeme-li v teoretické rovině generátor náhodných čísel, jím vygenerovanou řadu bitů o celkovém množství , dále budeme potřebovat funkci ´ která nám pomůže vytvořit predikci pro hodnotu následujících bitů + Í9 pro každou hodnotu bitu 1 ve znění ´ ∈ ¢: È → 0,13. Problém odhalení algoritmu generátoru náhodného čísla můžeme definovat takto:
&##"%·È #$%
i ¸ 0,13 , ´ Je nutné splnit následující podmínku s pravděpodobností větší než malý přírůstek S
S pro velmi
∃ ∈ ∀, 0 / ∈ È: ¦ & Å$ ∧ Æ0 / 1 ⇒ «Z, M ´0Ç Parametr ¦ v tomto případě reprezentuje možnost identifikace základního kamene algoritmu generátoru náhodných čísel pomocí Turingova zázračného stroje na úrovni
& Å$ + È& Å$ . ·2¸
6.8.
Požadavky na složitost z hlediska bezpečnosti a proveditelnosti Nyní se pokusíme definovat požadavky na složitost v rámci kryptografických
systémů a operací, které během šifrování a dešifrování probíhají. Pro každý subjekt zmíněný v předcházející podkapitole definujeme požadavek na složitost, vezmeme v úvahu jeho bezpečnost a proveditelnost, to znamená možnost jeho implementace v praxi v návaznosti na potenciál současné výpočetní techniky. V rámci další diskuse zároveň definujeme parametr % který bude reprezentovat požadavky na složitost v přeneseném slova smyslu i na bezpečnost. Pokud chceme, aby kryptosystém byl bezpečný tak úloha, kterou musí případná nezainteresovaná třetí strana řešit při prolomení kryptografického konceptu, byla definována v oblasti složitosti jako %. Naopak z hlediska použitelnosti a proveditelnosti 44
kryptografického konceptu je důležité, aby zainteresované strany během komunikaci řešili problém definovatelný v oblasti složitosti jako % $%%. V dalším textu tedy definujeme
pro jednoduchost dvě vlastí „třídy složitosti“ a budeme je označovat jako % versus
% $%%. V praxi je snadnější vytvořit kryptosystém, který vyhoví požadavku na
proveditelnost. Požadavky na bezpečnost a jejich prověření jsou ovšem úplně jinou kapitolou.
6.8.1. Požadavky na složitost pro symetrické šifry Velikost parametru n v případě symetrické šifry bude dána vztahem % ||.
Požadavek na proveditelnost bude v pořádku pokud Z a budou reprezentovány z hlediska složitosti jako % $%%. Z hlediska bezpečnosti musí symetrické šifrování splňovat
podmínku, že &##"% "&P Z& je reprezentováno složitostí %. V případě symetrického šifrování bude při úvahách o celkovém výpočetním času velmi záležet na délce zašifrované zprávy a délce šifrovacího klíče.
6.8.2. Požadavky na jednosměrné hashovací funkce Velikost parametru pro jednosměrné hashovací funkce je dána vztahem % .
Proveditelnost je definována vztahem Z" který by měl být reprezentován z hlediska
složitosti jako % $%%. Požadavky na bezpečnost jednosměrné hashovací funkce jsou
definovány z hlediska složitosti jako &##"%·³$%#i"&% ´ i °%P¸ což může
být z hlediska naší definice reprezentováno složitostí %.
6.8.3. Požadavky na složitost pro veřejné klíče Velikost parametru pro veřejný klíč je dána vztahem % |Â | za předpokladu že platí
|Â | `|Ã | . Požadavek na proveditelnost je splněn pokud Z, náleží do třídy složitosti
% $%% stejně jako generování příslušného klíčového páru ¼ , ½ . Veřejný klíč můžeme
považovat za bezpečný, pokud případné prolomení &##"%·¾&¿% P¸ bude definováno složitostí %.
45
6.8.4. Požadavky na digitální podpis Velikost parametru pro digitální podpis je dána vztahem % |É | za předpokladu, že
|É | `|Ê |. Digitální podpis je proveditelný ve chvíli kdy můžeme konstatovat, že Z,
náleží do třídy složitosti % $%%. Digitální podpis bude bezpečný v následujícím případě,
pokud &##"%·µ % #$i¸ bude náležet do třídy %.
6.8.5. Požadavky při generování náhodných čísel Připomeňme si, jak vzhledem k deterministické povaze algoritmů generující náhodná čísla půjde v této definici jen o „pseudonáhodná“ čísla. Velikost parametru % definujeme
vztahem % ||. Proveditelnost je v tomto případě splněna pokud Z bude náležet do třídy % $%%. Bezpečnost bude zaručena, pokud prolomení &##"%·È #$%
i ¸
bude náležet do třídy %.
46
7.
Kvantové počítače a kryptografie V této kapitole si blíže představíme třídy složitosti, které jsou relevantní pro kvantové
počítače. Pokusíme se také vytvořit paralelu mezi kvantovými a klasickými třídami složitosti.
7.1.
Teorie složitosti ve vztahu ke kvantovým počítačům V roce 1997 pánové Ethan Bernstein a Umesh Vazirani vytvořili ve své práci
„Quantum komplexity theory“ definici kvantového Turingova stroje (v originále Quantum Turing Machine – QTM, nadále bude v této práci použita počeštěná varianta KTS – kvantový Turingův stroj).[6] Vznikl také široký prostor k diskuzi o výpočetních možnostech kvantových počítačů. Byla představena třída složitosti BQP, která tvoří analogii ke klasické třídě složitost BPP používané pro tranzistorovou výpočetní techniku. Třída složitosti BQP reprezentuje úlohy, které lze efektivně řešit pomocí kvantového počítače, respektive jsou určeny pro kvantový Turingův stroj. Akceptovaná pravděpodobnost je
X
v polynomiálním čase KTS. V teorii
složitosti relativně často dochází k situaci, kdy neznáme přesné vztahy mezi jednotlivými třídami složitosti. V případě kvantových počítačů je situace ještě o něco komplikovanější, protože samotná kvantová teorie svou podstatou a výkladovou složitostí nedává příliš prostoru pro snadné a rychlé závěry. Vztahy mezi kvantovou třídou složitosti BQP a ostatními třídami složitosti nejsou v tomto případě žádnou výjimkou. Probereme zde pouze známé možnosti a jejich případné následky.
47
7.1.1. Známé vztahy mezi klasickými a kvantovými třídami složitosti Jak navrhl ve své práci v roce 1977 John Gill [12], třída složitosti BPP (v předchozím textu popsána v podkapitole 4.9.3) vykazuje souvislosti s dalšími třídami složitosti následovně:
⊆ ~
⊆ [
Î Bohužel není dokázáno, zda třída složitosti ~
plně obsahuje (je podmnožinou) nebo
je shodná s třídou È tak aby platilo ~
⊆ È . Ethan Bernstein a Umesh Vazirani ve své
práci [6] prokázali skutečnost, že třída složitosti ~
souvisí s třídami BQP a PSPACE takto: ~
⊆ ~g ⊆ [
Î
Z práce David S. Johnsona [20] dostáváme vztah pro třídy složitosti P, UP, NP v následujícím znění:
⊆ Ï ⊆ È
Dalším známým vztahem v třídách složitosti aplikovanými do kryptografických konceptů je poznatek, že jednosměrné hashovací funkce existují pouze, pokud třída složitosti
není podmnožinou třídy Ï . [15]
Ä È
7.1.2. Aplikace kvantových tříd složitosti v kryptografických konceptech Předtím, než se pustíme do dalšího pátrání ve spletité teorii složitosti, je nutné vyslovit jisté předpoklady, o kterých v současné době neexistuje jasný teoreticky podložený důkaz. Je možné, že v budoucnu bude dokázáno, že È nebo [
Î, přesto, že se v současné době domníváme, že rovnost v tomto případě neexistuje. Jednou z možností je následující umístění kvantové třídy složitosti ~g v hierarchii tříd složitosti s dopadem na téměř všechny zmíněné kryptografické koncepty: ~
~g ⊂ È za předpokladu, že Ï Ä ~g
Další možností je vztah vyjádřený následující definicí È ⊂ ~g . [5] [23]
48
7.1.3. Aplikace varianty schématu tříd složitosti - ⊂ Nejdříve slovně vyjádříme informaci v nadpisu této podkapitoly. Kvantová třída složitosti ~g je ekvivalentní s klasickou třídou složitosti ~
a obě tyto třídy jsou
podmnožinou třídy složitosti È . Toto vyjádření nepřináší do kryptografických konceptů nic nového, veškeré možnosti jsou v této chvíli obsaženy již v třídě ~
. Tato možnost bude
platit v případě, že neexistuje varianta Shorova algoritmu, která by byla schopná po implementaci použít k výpočtům klasický (nikoliv kvantový) počítač. [5]
7.1.4. Aplikace varianty schématu tříd složitosti ve znění ⊂ V tomto případě je klasická třídy složitosti ~
vlastní podmnožinou kvantové třídy
složitosti ~g . Některé výpočetní úlohy jsou součástí třídy složitosti ~g , ale zároveň
nejsou součástí třídy složitosti ~
. Tím se dostáváme ke kryptografickým konceptům, které používají k šifrování faktorizaci čísel a výpočet diskrétního logaritmu. Tento koncept se dnes
běžně používá u veřejných klíčů a digitálního podpisu. Nemáme důvod nevěřit, že tato situace v případě úspěšného zkonstruování a provozování kvantového počítače nepovede ve všech ohledech ke konci kryptosystémů založených na předpokladu složitosti faktorizace velkých čísel a výpočtu diskrétního logaritmu.
7.1.5. Aplikace varianty schématu tříd složitosti ⊆ Tato varianta existence tříd složitosti je podle všech dosavadních poznatků velmi nepravděpodobná, ale pokud by se potvrdila její pravdivost, mělo by to pro kryptografické koncepty nedozírné následky. Jde v podstatě o variantu, kdy připouštíme existenci Turingova zázračného stroje, který je schopen správně identifikovat příslušný klíč ke zprávě nebo správný obsah zprávy v případě jednosměrných hashovacích funkcí. Na základě výše uvedeného bychom mohli definovat, že třída složitosti È je vlastní podmnožinou kvantové třídy složitosti ~g . Úkol zmiňovaný v podkapitole 5.3.4 &##"% "&P Z&
by bylo možné vyjádřit pomocí třídy složitosti % $%%. Možný důkaz pro toto zařazení můžeme najít v práci Marco A. Barrena [2] a je popsán takto: Na začátku je nutné rozlišit třídy složitosti È a È . Dále je nutné upřesnit, co se
stane s třídami ~g a ~g , která je obvykle uváděna jako analogická k třídě È . Je nutné dokázat, že platí následující předpoklad: 49
~g
È ⊆ ~g znamená, že úkol definovaný jako &##"% "&P Z& ∈ Důkaz je podán takto. Definujme proměnnou nad klíčem , … … … ∈ kde %
je délkou klíče. Nechť f je Èf přijímající dvě celá čísla " a %, pro která platí že " Ð % jako vstup. Nyní nechme probíhat následující algoritmus:
QUESS KEY Ñ >> IF ¿ Ð " #& % Ð ¿ THEN REJECT>> ELSE IF ¦«Ñ = True >> THEN ACCEPT >> ELSE REJECT Protože předpokládáme že f je Èf bude pokaždé akceptovat klíč Ñ v rozsahu Ò , Ò¡ … … právě tehdy pokud dojde k nalezení schody tak že ¦«Ñ Pravda. Protože ¦ je stále definováno jako rozhodovací úkol pro Turingův zázračný stroj, zabere tento
algoritmus konstantní čas. Pokud bychom uvažovali o převedení tohoto teoretického stroje do reálného světa, je nutné nahradit ¦ ekvivalentním testem, který bude odpovídat třídě složitosti % $%%.
Dalším příkladem je následující algoritmus
, který bude mít za úkol vyřešení úlohy
&##"% "&P Z& :
úkol je definován následovně – provést vyhledání binárního klíče nad definovaným klíčovým prostorem
za
účelem
nalezení
správného
klíče
,respektive
vyřešení
úlohy
&##"% "&P Z& . Nejprve zavoláme funkci f s argumenty " 1, %
2 9 . Pokud f přijme tak je ve spodní polovině tedy hledání se bude opakovat s argumentem " 1, % 2 9 . Pokud f zamítne, se nachází v horní polovině a hledání se bude opakovat s argumenty " 2 9 1, % 2 9 2 9 . Binární vyhledávání
proběhne normálně a nalezne klíč v rozsahu `#2 `% opakování. Algoritmus
bude prováděn opakovaně až do dosažení stavu ¦ Pravda. Kvantový počítač provede `% kroků v rámci f a protože je implementován jako nedeterministický Turingův
stroj a bude schopen rozpoznat jazyk, bude možné je zařadit do třídy složitosti È , která
podle naší předcházející definice může být součástí třídy ~g . Algoritmus
je možné
zpracovat v polynomiálním čase a bude spadat do třídy % $%%. Z toho můžeme vyvodit, že pokud je náš předpoklad správný, bude úloha &##"% "&P Z& spadat do kategorie složitosti % $%%. [5]
50
8.
Závěry
8.1.
Očekávaný posun v paradigmatech kryptografie v důsledku nástupu kvantových počítačů Pokud budeme v budoucnu mít možnost v praxi použít kvantové počítače. To je věta,
která byla posledních dvacet let uváděna na konci každé rozsáhlejší úvahy o kvantových počítačích. Ale tím, že je hned na začátku, je vlastně řečeno skoro vše a nic dalšího už bychom nemuseli dodávat. V posledních dvaceti letech jsme často mohli číst články končící slovy: „pokud někdy dojde k tomu, že kvantový počítač bude schopen pracovat s více než několika málo qubity a technologie bude dostupná v rozumné míře třeba na úrovni jednotlivých států, zcela jistě dojde i k velmi rychlému vývoji na poli algoritmů použitelných právě pro použití na kvantovém počítači“. Dnes už můžeme říci, že pro kryptografická paradigmata je opravdu za pět minut dvanáct a jejich posun můžeme očekávat každým dnem. Uvedení nových konceptů do praxe je bohužel už úplně jinou kapitolou. Překážkou stále zůstává dostupnost kvantové výpočetní techniky a do jisté míry můžeme doufat, že to tak nějakou dobu ještě zůstane. Problematikou spojenou s implementací nových kryptografických konceptů se blíže stručně zabýváme v následující kapitole. Další otázkou je vývoj v oblasti mapování a důkazů tříd složitosti. Neznáme přesně návaznosti třídy BQP na další jako jsou NP, UP, BPP. Je možné, že posun v této oblasti bude do budoucna znamenat konec pro některé populární veřejně používané kryptosystémy jako je například RSA (stručně kapitola 4.4.2) vzhledem k neustále se zvyšujícímu výkonu klasické výpočetní techniky i bez použití kvantového počítače. Otázkou z hlediska filozofického zůstává, zda vůbec má smysl v mnohých případech data šifrovat a následně se pokoušet o prolomení této šifry. Kryptografie je v dnešní době dostupná ve formě programových komponent a „instantně“ použitelných knihoven v rámci takřka všech vyšších programovacích jazyků a pro jistotu se šifruje všechno a všude. Etickou stránku věci dokumentuje výrok amerického ministra zahraničí Henryho Stimsona, právníka a politika s velmi konzervativními názory, který údajně prohlásil tváří v tvář otázce směřující na další existenci kryptoanalytického oddělení: „Gentlemani si navzájem poštu nečtou“. Tento výrok je i dnes velmi zajímavým tématem k zamyšlení. 51
8.2.
Žijeme v době kvantových počítačů Kvantové počítače jsou zde, ale k posunu v paradigmatech kryptografie zatím nedošlo.
V listopadu roku 2011 spustila americká společnost Lockheed Martin první 128-qubitový počítač vyrobený firmou D-Wave Systems. Její CTO Geordie Rose prohlásil, že výpočetní schopnost jejich kvantového počítače neroste exponenciálně a ale ještě o něco rychleji. Společnosti D-Wave Systems se podařilo překročit hranice Mooreova zákona11 a její kvantové počítače mají údajně dvojnásobný výpočetní výkon každý rok. V roce 2008 se řada expertů v oblasti kvantové výpočetní techniky a kryptografie domnívala, že nástup prvních kvantových
počítačů,
schopných
praktického
nasazení
v
oblasti
„prolamování
kryptosystémů“můžeme očekávat nejdřív v roce 2018. Velký kvantový počítač vybavený příslušným algoritmem (zatím stále vede Shorův algoritmus popsaný v kapitole 3.1.11) by mohl být schopen prolomit všechny prakticky používané kryptosystémy v oblasti ICT, včetně on-line bankingu, E-commerce. V tuto chvíli neexistuje z globálního úhlu pohledu žádný precedens pro takto překotný vývoj v oblasti kvantových počítačů a nejsou k dispozici ani nové nástroje, bezpečnostní standardy nebo návrhy kryptosystémů v oblasti kryptografie veřejného klíče, které by nahradily současná paradigmata a schválené standardy. Vzhledem k dlouhodobému schvalovacímu procesu na úrovni státní správy v této oblasti, který trvá v průměru 6 až 10 let, nelze očekávat v dohledné době rychlý pokrok, navíc řešení v podobě nového kryptografického konceptu je v tuto chvíli v nedohlednu. Navíc implementace nových bezpečnostních standardů v komerční sféře a průmyslu trvá obvykle celou dekádu. Zástupci evropských karetních asociací Eurocard, Mastercard, Visa Co prohlašují, že migrace veškeré jejich současné infrastruktury tak, aby podporovala nové technologie, bude možná až v horizontu patnácti let. Velkou otázkou je v tuto chvíli skutečnost, že všechna v současnosti produkovaná data, zabezpečená pomocí standardních kryptografických konceptů, jsou v této podobě ukládána a nadále budou ukládána. Existence internetu a provázanost s telefonními sítěmi umožňují v současné době záznam a nahrávání dat v neuvěřitelném měřítku. Tato data mohou být uschována pro pozdější dešifrování pomocí
11 Mooreův zákon je empirické pravidlo, které roku 1965 vyslovil chemik a spoluzakladatel firmy Intel Gordon Moore. Původní znění bylo: „počet tranzistorů, které mohou být umístěny na integrovaný obvod se při zachování stejné ceny zhruba každých 18 měsíců zdvojnásobí.“ Takovýto růst se nazývá exponenciální.
52
kvantového počítače. V současné době jsou již vyvíjeny technologie, které používají pokročilé protokoly a kryptografické systémy všeobecně uznávané jako bezpečné proti případnému pokusu o prolomení kryptografického systému pomocí kvantového počítače. Nicméně v této fázi a vzhledem k výše uvedenému nejsou vyhlídky komerčního sektoru zrovna nejlepší. Pokud bychom se znovu pokusili opřít o citace, můžeme vzít v úvahu například výrok profesora Johannese Buchmanna, vedoucího katedry Computer Science and Mathematics Department of Technische Universität v Darmstadtu: „Celá tato situace může být noční můrou pro bezpečnost IT“ V roce 2004 bylo registrováno 155 projektů v oblasti kvantové výpočetní techniky ve veřejném sektoru. Ještě v roce 2008 panoval všeobecně názor, že použití kvantových počítačů v komerční sféře je reálné v horizontu nejméně deseti let.“ [40] Mimo společnosti Lockheed Martin také společnost Google a Harwardova Univerzita v současné době využívají 128 qbitový počítač od společnosti D-Wawe. A jak to ještě nedávno vypadalo v akademické sféře? V roce 2004 Quantum Information Science and Technology Experts Panel of the U.S. Advanced Research and Development Activity (ARDA) pod záštitou United States Army, Air Force, Navy, and the US National Science Foundation vydalo obsáhlou studii ve které je nástup velkých kvantových počítačů předpovídán během nadcházejících deseti let. Jisté je, že kvantové počítače již k dispozici jsou a je jen otázkou času, kdy budou i dostatečně výkonné pro řešení úloh z oblasti prolomení všeobecně používaných kryptografických konceptů.[36]
8.3.
Pohled do budoucna Pro další práci, která by mohla navázat na tento stručný přehled, je zde spousta
zajímavých témat a námětů. Určitě by bylo zajímavé blíže se soustředit na přesnější definici úloh prolomení jednotlivých kryptografických konceptů, včetně přesnější definice nutných kroků a algoritmů pro veřejně používané kryptosystémy. Další prostor je určitě v oblasti algoritmů určených pro zpracování informací na kvantových počítačích. Obrovský prostor je v oblasti mapování tříd složitosti, kde poznatky o vztazích jednotlivých tříd mohou způsobit malý převrat v kryptografických konceptech i bez kvantových počítačů.
53
Na závěr ještě citace profesora Gillese Brassarda, z Université de Montréal z roku 2006: „Prolomení RSA na kvantovém počítači netrvá déle, než šifrování pomocí RSA na obyčejném počítači.“ Plyne z toho, že tyto algoritmy veřejných klíčů nejsou bezpečné, a to v jakékoli délce klíče, pokud je dostupné dostatečné množství počítačů využívajících Shorův algoritmus. Důsledek tohoto útoku je, že všechna data šifrována pomocí současných norem bezpečnostních systémů, jako jsou SSL používané k ochraně elektronických obchodů a internetového bankovnictví a SSH používané k zabezpečení přístupu k citlivým počítačovým systémům, jsou v ohrožení. Šifrovaná data, která jsou chráněná pomocí algoritmů s veřejnými klíči, mohou být archivována a prolomena později.[40]
54
9. [1]
SEZNAM POUŽITÉ LITERATURY AARONSON, Joel. Limits on Efficient Computation in the Physical World. Bachelor of Science (Cornell University) 2000 GRADUATE DIVISION. UNIVERSITY of CALIFORNIA, BERKELEY, podzim 2004. Dostupné také z: http://arxiv.org/pdf/quant-ph/0412143.pdf
[2]
BARRENO, Marco. The Future of Cryptography Under Quantum Computers. Dartmouth College Computer Science Technical Report TR2002 – 425, květen 2002. Dostupné také z: http://www.cs.dartmouth.edu/~sws/theses/marco.pdf
[3]
BARTCH, Hans Jochen. Matematické vzorce a metody. Mladá Fronta Praha, 2002. ISBN 80-204-0607-7. Dotisk třetího vydání
[4]
BENJAMIN, Eric. Kenny Huang, Amir Kamil, Jimmy Kittiyachavalit. Quantum Computability and Complexity and the Limits of Quantum Computation. University of California. Berkeley, prosinec 2003. Dostupné také z: http://www.cs.berkeley.edu/~kamil/classes/cs191_qc4.pdf
[5]
BENNET, Charles. Ethan Bernstein, Gilles Brassard, Umesh Vazirani. Strengths and weaknesses of quantum computing. Cornell University, SIAM J. Computation ,
září
1997,
strana 1510-1523.
Dostupné
také
z:
arxiv.org/pdf/quant-ph/9701001 [6]
BERNSTEIN, Ethan. Vazirani. Quantum complexity theory. SIAM J. Comput, září 1997. Proc. 25th Annual ACM Symposium on Theory of Computing, ACM. Dostupné také z: http://dl.acm.org/citation.cfm?id=167097
[7]
CORMEN, Thomas. Charles Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms 3rd Edition. The MIT Press Cambridge, Massachusetts London, England. ISBN 978-0-262-53305-8. Dostupné také z: http://strycore.com/ebooks/Introduction%20to%20Algorithms%203rd%20Editi on.pdf
[8]
DEUTCH, David. Quantum theory the Church-Turing principle and the universal quantum computer. Appeared in Proceedings of the Royal Society of London A 400, pp. 97-117 (1985) (Communicated by R. Penrose, F.R.S. Received 13 July 1984). Dostupné také z: http://www.ceid.upatras.gr/tech_news/papers/quantum_theory.pdf
55
[9]
ELGAMAL, Taher. A public key cryptosystem and a signature scheme based on
discrete
logarithms.
Advances
in
cryptology:
Proceedings
of
CRYPTO 84. Dostupné také z: http://groups.csail.mit.edu/cis/crypto/classes/6.857/papers/elgamal.pdf [10]
FEYNMANN, Richard Phillips. R. Leighton, B. Sands. Feynmanovy přednášky
z fyziky 2/3. Nakladatelství: FRAGMENT, ISBN 80-7200-420-4,
EAN 9788072004201 [11]
FEYNMANN, Richard Phillips. R. Leighton, B. Sands. Feynmanovy přednášky z fyziky 1/3. Nakladatelství: FRAGMENT, ISBN 80-7200-420-4, EAN 9788072004201
[12]
GILL, John. Computational complexity of probabilistic Turing machines. SIAM J. Comput., Vol:6 No:4, Prosinec 1977. Dostupné také z: http://www.informatik.unitrier.de/~ley/db/journals/siamcomp/siamcomp6.html
[13]
GISIN, Nicolas. Gregoire Ribordy, Wolfgang Tittel and Hugo Zbinden. Quantum cryptography Group of Applied Physics. University of Geneva, 1211 Geneva 4, Switzerland. Publikováno 8. března 2002. REVIEWS OF MODERN PHYSICS, VOLUME 74, leden 2002. Dostupné také z: http://prl.aps.org/files/RevModPhys.74.145.pdf
[14]
GREENBERGER, D.M. M. Horne, A . Zeilinger. Multiparticle interferometry and the superposition principle. Physics Today, srpen 1993. 46 (8),strana 22–29.
[15]
GROLLMANN, Joachim. Alan L. Selman. Complexity measures forpublickey cryptosystems. SIAM J. Comput. duben 1998. Dostupné také z: http://www.researchgate.net/publication/220618351_Complexity_Measures_fo r_Public-Key_Cryptosystems
[16]
HAZEWINKEL, Michiel, ed. (2001), "Turing machine", Encyclopedia of Mathematics. Springer, ISBN 978-1-55608-010-4
[17]
CHOWN, Marcus. Quantum Theory Can not Hurt You. Publisher: Faber and Faber (2007). ISBN-10 057123545X
[18]
JOHNSON, Don. Alfred Menezes, Scott Vanstone. The Elliptic Curve Digital, Signature Algorithm (ECDSA). Certicom Research, Canada Dept. of Combinatorics & Optimization, University of Waterloo, Canada. Dostupné také z: http://cs.ucsb.edu/~koc/ccs130h/notes/ecdsa-cert.pdf 56
[19]
JOHNSON, David S. A Catalog of Complexity Classes. AT&T Bell Laboratories, Murray Hill, NJ 07974, USA. Dostupný také z: http://www.dbai.tuwien.ac.at/staff/pichler/complexity/johnson1990.pdf
[20]
JOHNSON, David S. A catalog of complexity classes - Handbook of Theoretical Computer Science. Editor J. van Leeuwen. Nakladatel: Elsevier Science Publishers. Amsterdam, The Netherlands 1990. ISBN-10:0444880712 ISBN-13: 9780444880710. strana 69-161
[21]
MILLER, Victor . Elliptic Curves - Cryptography and Computation. IDA Center for Communications Research, Princeton, NJ 08540 USA, 18. září 2010. Dostupné také z: http://2010.eccworkshop.org/slides/Miller.pdf
[22]
MURPHY, Sean. Fred Piper. Kryptografie. Dokořán 2006. Překlad Pavel Mondschein. ISBN 80-7363-074-5, EAN 9788073630744
[23]
NIELSEN, Michael. Isaac Chuang. Quantum Computation and Quantum Information. Cambridge University Press. Rok vydání 2000. ISBN-10: 0521635039, ISBN-13: 978-0521635035, Edice: 1
[24]
RIEFFEL,
Eleanor.
Wolfgang
Polak.
An
introduction
to
quantum
computingfor non-physicists. FX Palo Alto Laboratory, 3400 Hillview Avenue, Palo Alto, CA 94304. Dostupné také z: http://arxiv.org/pdf/quantph/9809016.pdf [25]
RIVEST, Ronald L. Cryptography. Editor J. van Leeuwen, Handbook of Theoretical Computer Science, Nakaldatel: Elsevier Science Publishers B.V.: Amsterdam, The Netherlands, 1990. Kapitola 13, strana 718-755.
[26]
SCARANI, Valerio a kolektiv. The Security of Practical Quantum Key Distribution. (Submitted on 28. Února 2008 (v1), poslední úprava 30. září 2009 (verze v3)). Dostupné také z: http://arxiv.org/pdf/0802.4155v3.pdf90.
[27]
SHOR, Peter W. Algorithms for quantum computation - Discrete logarithms and factoring. In Proceedings of the 35th Annual IEEE Symposiumon Foundations of Computer Science, strana 124-134. IEEEComputer Society Press, 1994. aktualizováno 1996. Dostupné také z: http://arxiv.org/pdf/quant-ph/9508027.pdf, pod titulem: "Polynomial-Time Algorithms for Prime Factorizationand Discrete Logarithms on a Quantum Computer".
[28]
SINGH, Simon. The Code Book, Fourt Estate Limited. 1999 ISBN-10: 0385495323 57
[29]
SIPSER, Michael. Introduction to the Theory of Computation. PWS Publishing
Company.1996.
ISBN-10:
053494728X,
ISBN-13: 978-
0534947286, Edice: 1 [30]
U.S. Department of Commerce, FEDERAL INFORMATION PROCESSING STANDARDS PUBLICATION, FIPS PUB 186-3, Digital Signature Standard (DSS),
CATEGORY:
COMPUTER
SECURITY
SUBCATEGORY:
CRYPTOGRAPHY, Information Technology Laboratory , National Institute of Standards and Technology, Gaithersburg, MD 20899-8900 , vydáno v květnu 2009. Dostupné také z: http://www.pdfio.com/k-1419228.html
10. INTERNETOVÉ STRÁNKY [31]
LOS ALAMOS NATIONAL LABORATORY http://xxx.lanl.gov/archive/quant-ph "arXiv"
[32]
THE COMPLEXITY ZOO http://www.complexityzoo.com
[33]
COMPLEXITY AND OTHER SOFTWARE METRICS http://web.cs.mun.ca/˜ulf/gloss/complex.html
[34]
BASHAR, J.. Kvantové teorie [online]. 2001 [cit. 2006-04-20]. Dostupný z WWW:
.
[35]
BOHEN Dan, Cryptography Courses, Professor Computer Science Stanford University [online] https://www.coursera.org/course/crypto
[36]
SYNAPTICS LABORATORIES. Článek : "How does the quantum computing timeline interact with the search for a new security solution?" Dostupný na adrese: http://synaptic-labs.com/ecosystem/context-qc-relevanttoday.html
58
11. BIBLIOGRAFICKÉ ODKAZY A CITACE DOKUMENTŮ [37]
CHOWN, Marcus. Quantum Theory Can not Hurt You. Nakladatelství: Faber and Faber (2007), ISBN-10: 057123545X ISBN-13: 978-0571235452, strana 49.
[38]
FEYNMANN, Richard Phillips. R. Leighton, B. Sands. Feynmanovy přednášky z fyziky 1/3. Nakladatelství: FRAGMENT, ISBN: 80-7200-420-4, EAN:9788072004201,(1.vydání 2000), strana 506 – 507.
[39]
FEYNMANN, Richard Phillips. R. Leighton, B. Sands. Feynmanovy přednášky z fyziky 1/3. Nakladatelství: FRAGMENT, ISBN: 80-7200-420-4, EAN:9788072004201, (1.vydání 2000), strana 507 – 508.
[40]
SYNAPTICS
LABORATORIES. Článek: "How
does
the
quantum
computing timeline interact with the search for a new security solution?" (citováno
04.04.2010)
Článek
dostupný
na
labs.com/ecosystem/context-qc-relevant-today.html
59
aderse:
http://synaptic-
