Univerzita Karlova v Praze Matematicko-fyzikální fakulta. Interaktivní důkazy. Katedra algebry

Univerzita Karlova v Praze Matematicko-fyzikáln´ı fakulta

´ RSK ˇ ´ PRACE ´ BAKALA A

Jana Kuˇcerová Interaktivn´ı d˚ ukazy Katedra algebry

Vedouc´ı bakaláˇrské práce: Doc. RNDr. Jiˇr´ı T˚ uma, DrSc. Studijn´ı program: Matematika Studijn´ı obor: Matematické metody informaˇcn´ı bezpeˇcnosti

2006

Dˇekuji doc. RNDr. Jiˇr´ımu T˚ umovi, DrSc. za veden´ı mé práce a za jeho cenné pˇripom´ınky.

Prohlaˇsuji, ˇze jsem svou bakaláˇrskou práci napsala samostatnˇe a v´ yhradnˇe s pouˇzit´ım citovan´ ych pramen˚ u. Souhlas´ım se zap˚ ujˇcován´ım práce a jej´ım zveˇrejˇ nován´ım. V Praze dne 2. 8. 2006

Jana Kuˇcerová

2

Obsah ´ 1 Uvod

5

2 Protokol

6

3 Matematick´ e z´ aklady 3.1 Problémy z teorie ˇc´ısel, jednosmˇerné funkce 3.1.1 Faktorizace . . . . . . . . . . . . . . 3.1.2 Modulárn´ı odmocnina . . . . . . . . 3.1.3 Problém diskrétn´ıho logaritmu . . . . 3.2 Problémy z teorie sloˇzitosti . . . . . . . . . . 3.3 Prokazatelná bezpeˇcnost . . . . . . . . . . . 3.4 Pouˇzitá tvrzen´ı a algoritmy . . . . . . . . . 4 Stavebn´ı prvky protokol˚ u 4.1 Haˇsovac´ı funkce . . . . . 4.2 Digitáln´ı podpis . . . . . 4.3 RSA . . . . . . . . . . . 4.4 Rabin˚ uv kryptosystém .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . . . . .

. . . .

. . . . . . .

. . . .

. . . . . . .

. . . .

. . . . . . .

. . . .

. . . . . . .

. . . .

. . . . . . .

. . . .

. . . . . . .

. . . .

. . . . . . .

. . . .

. . . . . . .

. . . .

. . . . . . .

. . . .

. . . . . . .

. . . .

. . . . . . .

7 7 7 8 8 9 9 10

. . . .

14 14 15 15 16

5 Turingovy stroje

19

6 Interaktivn´ı d˚ ukazy 6.1 Identifikace zaloˇzená na kryptografii s veˇrejn´ ym kl´ıˇcem . . . . . . 6.2 Fiat-Shamirovo identifikaˇcn´ı schéma . . . . . . . . . . . . . . . . . 6.3 Faktorizace n = pq pomoc´ı algoritmu na hledán´ı druhé odmocniny z kvadratického rezidua . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Rozˇs´ıˇrené Fiat-Shamirovo identifikaˇcn´ı schéma . . . . . . . . . . . 6.5 Schnorr-Okamotovo identifikaˇcn´ı schéma . . . . . . . . . . . . . .

23 26 27

Literatura

34

3

30 30 31

Název práce: Interaktivn´ı d˚ ukazy Autor: Jana Kuˇcerová Katedra (´ ustav): Katedra algebry Vedouc´ı bakaláˇrské práce: Doc.RNDr. Jiˇr´ı T˚ uma,DrSc. e-mail vedouc´ıho: [email protected] Abstrakt: Pˇredloˇzená práce se vˇenuje kryptografick´ ym protokol˚ um pro interaktivn´ı d˚ ukazy. Protoˇze tyto protokoly jsou jedny ze sloˇzitˇejˇs´ıch, jsou v prvn´ı ˇca´sti práce popsána nˇekterá jednoduˇsˇs´ı kryptografická schémata, která jsou pozdˇeji vyuˇzita jako stavebn´ı prvky tˇechto protokol˚ u. V této práci jsou interaktivn´ı d˚ ukazy nejprve definovány jako v´ ypoˇcet spojené dvojice interaktivn´ıch Turingov´ ych stroj˚ u. Pozdˇeji je uvedena souvislost takto definovaného interaktivn´ıho d˚ ukazu s interaktivn´ım d˚ ukazem znalosti dokazovatelova tajemstv´ı v identifikaˇcn´ıch protokolech. Na pˇr´ıkladu nˇekolika identifikaˇcn´ıch protokol˚ u je ukázáno, jak´ ym zp˚ usobem lze rozhodnout, zda se jedná o d˚ ukaz s nulovou znalost´ı nebo zda je dan´ y protokol prokazatelnˇe bezpeˇcn´ y. Kl´ıˇcová slova: kryptografick´ y protokol, Turing˚ uv stroj, prokazatelná bezpeˇcnost, d˚ ukaz s nulovou znalost´ı

Title: Interactive proofs Author: Jana Kuˇcerová Department: Department of Algebra Supervisor: Doc.RNDr. Jiˇr´ı T˚ uma,DrSc. Supervisor’s e-mail address: [email protected] Abstract: The main topic of the present work is cryptographic protocols for interactive proofs. Because of complexity of these protocols, at first we describe some cryptographic elements, which we will use later as building blocs of interactive proof protocols. In this work, we define interactive proofs as a joint computation of a linked pair of two interactive Turing machines. Later, we explain the relation between this definition and an interactive proof of knowledge of a prover’s secret in identification protocols. We present examples of several identification protocols and demonstrate how we can determine, if the given protocol is provably secure or if it is a zero-knowledge proof. Keywords: cryptographic protocol, Turing machine, provable security, zero-knowledge proof

4

Kapitola 1 ´ Uvod Kryptografické protokoly se pouˇz´ıvaj´ı k ˇreˇsen´ı r˚ uzn´ ych problém˚ u, jako je napˇr. v´ ymˇena kl´ıˇce pro symetrické ˇsifrovac´ı schéma, autentizace uˇzivatele nebo elektronické volby. Tato práce se zab´ yvá protokoly pro interaktivn´ı d˚ ukazy, zejména pro d˚ ukazy identity uˇzivatele (neboli autentizaci). Identita se v identifikaˇcn´ıch protokolech prokazuje d˚ ukazem znalosti urˇcitého tajemstv´ı, které zná pouze dan´ y uˇzivatel. Aby tomu tak z˚ ustalo i po probˇehnut´ı protokolu, je vhodné, aby o tomto tajemstv´ı neunikla ˇza´dná netriviáln´ı informace, která by mohla vést k jeho odhalen´ı. To zajiˇst’uj´ı tzv. d˚ ukazy s nulovou znalost´ı. Jak se ale ukáˇze, nˇekteré d˚ ukazy s nulovou znalost´ı jsou nevhodné z jin´ ych d˚ uvod˚ u — neposkytuj´ı sice ˇza´dnou netriviáln´ı informaci o uˇzivatelovˇe tajemstv´ı, ale nezaruˇcuj´ı bezpeˇcnost z jiného hlediska. V této práci nejprve uvedeme matematické základy nutné k pochopen´ı dalˇs´ıho textu. Dále uvedeme jednoduchá kryptografická schémata, která pozdˇeji pouˇzijeme jako stavebn´ı prvky identifikaˇcn´ıch protokol˚ u. Pˇres definici interaktivn´ıch d˚ ukaz˚ u pomoc´ı interaktivn´ıch Turingov´ ych stroj˚ u se dopracujeme k identifikaˇcn´ım protokol˚ um, které zhodnot´ıme z hlediska prokazatelné bezpeˇcnosti a také u nich rozhodneme, zda se jedná o d˚ ukazy s nulovou znalost´ı.

5

Kapitola 2 Protokol Protokol je pˇresnˇe definovaná posloupnost krok˚ u, zahrnuj´ıc´ı dva nebo v´ıce u ´ˇcastn´ık˚ u navrˇzená k vykonán´ı urˇcité u ´lohy, napˇr. v´ ymˇeny kl´ıˇce pro symetrickou ˇsifru, autentizaci uˇzivatele, apod. Kaˇzd´ y krok protokolu mus´ı b´ yt vykonan´ y a poˇrad´ı krok˚ u mus´ı b´ yt dodrˇzené. Dals´ı poˇzadavky na protokol jsou: • vzájemné odsouhlasen´ı — kaˇzd´ y u ´ˇcastn´ık mus´ı b´ yt obeznámen´ y s cel´ ym protokolem a mus´ı s n´ım souhlasit, • jednoznaˇcnost — kaˇzd´ y krok mus´ı b´ yt dobˇre definovan´ y, aby nemohlo doj´ıt k nedorozumˇen´ı, • u ´plnost — mus´ı b´ yt pˇresnˇe vymezené chován´ı kaˇzdého u ´ˇcastn´ıka v kaˇzdé situaci. ´ Kryptografický protokol je protokol vyuˇz´ıvaj´ıc´ı kryptografii. Ulohou kryptografie v protokolech je zabránit nebo odhalit pˇr´ıpadn´ y podvod a zabránit u ´ˇcastn´ık˚ um ´ nebo tˇret´ı stranˇe z´ıskat v´ıc informac´ı, neˇz protokol vymezuje. Uroveˇ n bezpeˇcnosti kryptografického protokolu je maximálnˇe tak velká, jako je bezpeˇcnost j´ım pouˇzitého kryptosystému, m˚ uˇze vˇsak b´ yt mnohem niˇzˇs´ı. V této práci se budeme zab´ yvat zejména indentifikaˇcn´ımi protokoly. Ve ˇctvrté kapitole uvedeme nekterá jednoduˇsˇs´ı schémata, která budeme pouˇz´ıvat v dalˇs´ıch kapitolách pˇri konstrukci sloˇzitˇejˇs´ıch schémat.

6

Kapitola 3 Matematick´ e z´ aklady V dalˇs´ım textu budeme pouˇz´ıvat následuj´ıc´ı oznaˇcen´ı: m otevˇren´ y text c ˇsifrov´ y text GCD(a, b) nejvˇetˇs´ı spoleˇcn´ y dˇelitel ˇc´ısel a a b P(A) pravdˇepodobnost jevu A Symbolem Zn budeme oznaˇcovat aditivn´ı Abelovu grupu pˇrirozen´ ych ˇc´ısel modulo n a symbolem Z∗n budeme oznaˇcovat multiplikativn´ı Abelovu grupu vˇsech prvk˚ u Zn , které jsou s n nesoudˇelné. ˇ ıkáme, ˇze funkce f : N → R m´ Definice 3.1. Necht’ g je funkce g : N → R. R´ a sloˇzitost O(g) (nebo ˇze leˇz´ı v O(g)), pokud existuje c > 0 takové, ˇze pro vˇsechna n ∈ N plat´ı f (n) < c · g(n).

3.1

Probl´ emy z teorie ˇ c´ısel, jednosmˇ ern´ e funkce

Bezpeˇcnost mnoh´ ych kryptografick´ ych protokol˚ u je zaloˇzena na v´ ypoˇcetn´ı nezvládnutelnosti nˇekter´ ych matematick´ ych problém˚ u. Pojem v´ ypoˇcetn´ı nezvládnutelnost znamená, ˇze v souˇcasnosti nen´ı znám ˇzádn´ y algoritmus, kter´ y by dokázal dan´ y problém vyˇreˇsit v polynomiáln´ım ˇcase. O v´ ypoˇcetnˇe nezvládnuteln´ ych problémech ˇr´ıkáme, ˇze jsou tˇeˇzké. Jsou to napˇr´ıklad problém faktorizace sloˇzen´ ych ˇc´ısel, problém nalezen´ı diskrétn´ıho logaritmu nebo problém nalezen´ı druhé odmocniny v modulárn´ı aritmetice. Tyto problémy nyn´ı pˇribl´ıˇz´ıme.

3.1.1

Faktorizace

Definice 3.2. Problém faktorizace pˇrirozených ˇc´ısel je následuj´ıc´ı: Pro dané n ∈ N naleznˇete jeho prvoˇc´ıseln´ y rozklad, tj. vyjádˇren´ı n = pe11 pe22 . . . pekk , kde pi jsou po dvou r˚ uzná prvoˇc´ısla a ei ≥ 1 pro vˇsechna i = 1, . . . , k. Zat´ımco vynásoben´ı dvou cel´ ych ˇc´ısel a a b má ˇcasovou sloˇzitost O(|a| · |b|), faktorizace sloˇzeného ˇc´ısla je povaˇzována za tˇeˇzk´ y problém. Mezi nejlepˇs´ı známé faktorizaˇcn´ı algoritmy patˇr´ı kvadratické s´ıto, ˇc´ıselné s´ıto a algoritmy zaloˇzené na teorii o eliptick´ ych kˇrivkách.

7

Poznámka 3.3 (D˚ uleˇzitá). V kryptologii se omezujeme na faktorizaci ˇc´ısel, která jsou souˇcinem dvou r˚ uzn´ ych náhodn´ ych (a ve vˇetˇsinˇe pˇr´ıpad˚ u pˇribliˇznˇe stejnˇe velk´ ych) prvoˇc´ısel. V celém následuj´ıc´ım textu budou p a q znaˇcit prvoˇc´ısla a n bude znaˇcit souˇcin dvou r˚ uzn´ ych pˇribliˇznˇe stejnˇe velk´ ych lich´ ych prvoˇc´ısel, n = pq. Souˇcasn´ y rekord ve faktorizaci ˇc´ısla, které je souˇcinem dvou pˇribliˇznˇe stejnˇe velk´ ych prvoˇc´ısel, pocház´ı z kvˇetna roku 2005, kdy bylo pomoc´ı nˇekolika paralelnˇe zapojen´ ych poˇc´ıtaˇc˚ u faktorizováno 200-ciferné (663-bitové) ˇc´ıslo. Tato faktorizace trvala 18 mˇes´ıc˚ u a pˇredpokládá se, ˇze na jednom poˇc´ıtaˇci by trvala 55 let. Pro asymetrické ˇsifry (viz. odd´ıl 3.3) vyuˇz´ıvaj´ıc´ı obt´ıˇznosti faktorizace je proto nejˇcastˇejˇs´ı doporuˇcovanou délkou modulu n 1024 bit˚ u, coˇz odpov´ıdá 308-cifernému ˇc´ıslu v dekadickém zápise.

3.1.2

Modul´ arn´ı odmocnina

ˇ ıslo v nazveme kvadratickým reziduem modulo n, jestliˇze existuje Definice 3.4. C´ ˇc´ıslo u ∈ Z∗n , pro které plat´ı v = u2 mod n. Mnoˇzinu vˇsech kvadratick´ ych rezidu´ı modulo n oznaˇcujeme QRn . Lze snadno dokázat, ˇze mnoˇzina QRn je multiplikativn´ı Abelova grupa. Definice 3.5. Problém nalezen´ı modulárn´ı odmocniny je následuj´ıc´ı: Pro dané kvadratické reziduum v modulo n naleznˇete u ∈ Z∗n takové, ˇze plat´ı v = u2 mod n. Problém nalezen´ı druhé odmocniny modulo ˇc´ıslo n, které je souˇcinem dvou prvoˇc´ısel, n = pq, u ´zce souvis´ı s v´ yˇse uveden´ ym problémem faktorizace ˇc´ısla n; pˇresnˇeji ˇreˇceno, je s n´ım ekvivalentn´ı. Pojem ekvivalentn´ı“ zde znamená, ” ˇze jsme-li schopni vyˇreˇsit jeden z tˇechto problém˚ u se sloˇzitost´ı O(g), pak jsme schopni (s pomoc´ı algoritmu na ˇreˇsen´ı prvn´ıho problému) se sloˇzitost´ı O(g) vyˇreˇsit i druh´ y z nich. Algoritmus na faktorizaci n pomoc´ı algoritmu na hledán´ı odmocniny modulo n najdeme v odd´ılu 6.3. Na poˇc´ıtán´ı odmocniny z kvadratického rezidua modulo prvoˇc´ıslo p existuj´ı rychlé algoritmy (nejlepˇs´ı z nich má ˇcasovou nároˇcnost O((log p)3 )); nalézt je m˚ uˇzeme napˇr. v knize [7] na stranˇe 100. Ve stejné knize na stranˇe 102 nalezneme algoritmus na hledán´ı druhé odmocniny modulo ˇc´ıslo n, známe-li jeho rozklad.

3.1.3

Probl´ em diskr´ etn´ıho logaritmu

Definice 3.6. Necht’ G je cyklická grupa ˇra´du n. Necht’ α je generátor grupy G a necht’ β ∈ G. Diskrétn´ı logaritmus β o základu α, oznaˇcovan´ y logα β, je x pˇrirozené ˇc´ıslo x, 0 ≤ x ≤ n − 1 takové, ˇze β = α mod n. Definice 3.7. Problém nalezen´ı diskrétn´ıho logaritmu (DLP) je následuj´ıc´ı: Pro dané prvoˇc´ıslo p, generátor α grupy Z∗p a prvek β ∈ Z∗p naleznˇete celé ˇc´ıslo x, 0≤x≤p−2 takové, ˇze plat´ı αx ≡ β (mod p). 8

Problém nalezen´ı diskrétn´ıho logaritmu je, podobnˇe jako pˇredchoz´ı dva problémy, povaˇzován za tˇeˇzk´ y. V´ıce se o tomto problému m˚ uˇzeme doˇc´ıst napˇr. opˇet v knize [7] na stranˇe 103; najdeme v n´ı také dalˇs´ı tˇeˇzké matematické problémy. Uvedené problémy souvis´ı s jednosmˇernými funkcemi (je-li správn´ y pˇredpoklad o jejich v´ ypoˇcetn´ı nezvládnutelnosti). Tuto nepˇresnou formulaci objasn´ıme v následuj´ıc´ım odstavci. Jednosmˇerná funkce f : X → Y je taková, ˇze je snadné spoˇc´ıtat jej´ı hodnotu f (x) pro libovoln´ y vstup x ∈ X (t.j. existuje polynomiáln´ı algoritmus, kter´ y má pro vstup x v´ ystup f (x)), ale známe-li pouze hodnotu y ∈ Y , pak nejsme schopni v polynomiáln´ım ˇcase naj´ıt prvek x ∈ X takov´ y, ˇze f (x) = y. Následuje formáln´ı definice obt´ıˇznosti invertovatelnosti funkce. ˇ ıkáme, ˇze funkce f : X → Y je obt´ıˇznˇe invertovatelná, jestliˇze Definice 3.8. R´ kaˇzd´ y pravdˇepodobnostn´ı polynomiáln´ı algoritmus (t.j. program pravdˇepodobnostn´ıho polynomiáln´ıho Turingova stroje (viz. definici 5.6)) na hledán´ı inverze hodnoty y = f (x), x ∈ X, m˚ uˇze uspˇet pouze se zanedbatelnou (v |y|) pravdˇepodobnost´ı. Posloupnost {sn }n∈N se naz´ yvá zanedbatelná v n, jestliˇze pro kaˇzd´ y polynom p(·) a kaˇzdé dostateˇcnˇe velké n plat´ı sn < 1/p(n). Nyn´ı objasn´ıme souvislost jednosmˇern´ ych funkc´ı s uveden´ ymi tˇeˇzk´ ymi problémy. V pˇr´ıpadˇe problému faktorizace ˇc´ısla n = pq je funkc´ı f : N × N → N násoben´ı, které má polynomiáln´ı ˇcasovou sloˇzitost vzhledem k velikosti souˇcinitel˚ u p a q. Inverzn´ı funkc´ı f −1 je nalezen´ı prvoˇc´ıselného rozkladu ˇc´ısla n. V pˇr´ıpadˇe problému nalezen´ı modulárn´ı odmocniny z ˇc´ısla v = u2 mod n je funkc´ı f : Z∗n → QRn umocnˇen´ı prvku u ∈ Z∗n na druhou modulo n a inverzn´ı funkc´ı f −1 je pˇri znalosti rezidua v nalezen´ı u. Koneˇcnˇe v pˇr´ıpadˇe problému nalezen´ı diskrétn´ıho logaritmu x = logα β v grupˇe Z∗p je funkc´ı fα : Z∗p → Z∗p umocnˇen´ı generátoru α grupy Z∗p na x-tou modulo p a funkc´ı fα−1 je pˇri znalosti β nalezen´ı ˇc´ısla x.

3.2

Probl´ emy z teorie sloˇ zitosti

Zde uvedeme problém grafového izomorfismu. Definice 3.9. Dva grafy G1 = (V1 , E1 ) a G2 = (V2 , E2 ) se naz´ yvaj´ı izomorfn´ı, pokud existuje bijekce π z mnoˇziny vrchol˚ u V1 do mnoˇziny vrchol˚ u V2 taková, ˇze pro kaˇzdé dva vrcholy u, v ∈ V1 plat´ı (u, v) ∈ V1 , právˇe kdyˇz (π(u), π(v)) ∈ V2 . Definice 3.10. Problém grafového izomorfismu je následuj´ıc´ı: Rozhodnˇete, zda jsou dva dané grafy G1 a G2 izomorfn´ı. Vygenerovat dva izomorfn´ı grafy je snadné (staˇc´ı pˇrejmenovat“ vrcholy). ” O rozhodován´ı, zda jsou dva dané grafy izomorfn´ı se vˇsak pˇredpokládá, ˇze jde o tˇeˇzk´ y problém. V pˇr´ıpadˇe grafového izomorfismu nejde o jednosmˇernou funkci. Proto jej nelze pouˇz´ıt jako základ asymetrick´ ych ˇsifer (viz. odd´ıl 3.3). Ale lze jej pouˇz´ıt napˇr. v identifikaˇcn´ıch schématech (viz. kapitolu 6), kde dokazovatelov´ ym tajemstv´ım je bijekce π z definice 3.9.

3.3

Prokazateln´ a bezpeˇ cnost

ˇ Sifry zaloˇzené na obt´ıˇznosti matematick´ ych problém˚ u, z nichˇz nˇekteré jsme zm´ınili v pˇredchoz´ı ˇca´sti, se naz´ yvaj´ı asymetrické nebo ˇsifry s veˇrejným kl´ıˇcem. Zat´ımco 9

u symetrick´ ych ˇsifer1 mus´ı odes´ılatel i pˇr´ıjemce své kl´ıˇce chránit, aby je nez´ıskala neoprávnˇená osoba, u asymetrick´ ych ˇsifer se nechává v tajnosti pouze deˇsifrovac´ı kl´ıˇc a ˇsifrovac´ı kl´ıˇc se zveˇrejˇ nuje. Deˇsifrovac´ımu kl´ıˇci se ˇr´ıká soukromý nebo tajný kl´ıˇc a ˇsifrovac´ımu kl´ıˇci se ˇr´ıká veˇrejný kl´ıˇc. Kdokoliv pak m˚ uˇze zaˇsifrovat zprávu pˇr´ıjemcov´ ym veˇrejn´ ym kl´ıˇcem a m˚ uˇze si b´ yt (témˇeˇr) jist´ y, ˇze si ji bude schopen pˇreˇc´ıst pouze jej´ı oprávnˇen´ y pˇr´ıjemce. Soukrom´ y a veˇrejn´ y kl´ıˇc tvoˇr´ı tzv. kl´ıˇcový pár. Pˇri hodnocen´ı bezpeˇcnosti asymetrick´ ych schémat vˇsak nejde jen o neinvertovatelnost pˇr´ısluˇsné jednosmˇerné funkce. K nˇekter´ ym ˇsifrám totiˇz byly nalezeny u ´toky s menˇs´ı ˇcasovou sloˇzitost´ı, neˇz jakou má invertován´ı dané jednosmˇerné funkce. Chceme-li tedy ukázat, ˇze u ´tok na ˇsifru má sloˇzitost alespoˇ n takovou jako v´ ypoˇcet inverze pˇr´ısluˇsné jednosmˇerné funkce, m˚ uˇzeme pouˇz´ıt nˇekterou z metod tzv. prokazatelné bezpeˇcnosti (provable security). Jednou z nich je redukcionistick´ a 2 bezpeˇcnost (reductionist security). Budeme ji pouˇz´ıvat v následuj´ıc´ım tvaru : Definice 3.11 (Redukcionistická bezpeˇcnost asymetrick´ ych ˇsifrovac´ıch schémat). Kdokoliv, kdo je schopen v daném kryptosystému v polynomiáln´ım ˇcase k ˇsifrovému textu c naj´ıt otevˇren´ y text m (pomoc´ı algoritmu A), je schopen s vyuˇzit´ım algoritmu A v polynomiáln´ım ˇcase vyˇreˇsit pˇr´ısluˇsn´ y matematick´ y problém. Je ovˇsem tˇreba si uvˇedomit, ˇze tato metoda zaruˇcuje pouze odolnost v˚ uˇci u ´tok˚ um urˇcitého typu (kter´ y si v kaˇzdém konkrétn´ım pˇr´ıpadˇe pokusu o d˚ ukaz prokazatelné bezpeˇcnosti mus´ıme stanovit) a nebere v u ´vahu moˇzné nedostatky ´ fyzické implementace. Utoky na fyzickou implementaci kryptografick´ ych protokol˚ u se naz´ yvaj´ı u ´toky pomoc´ı postrann´ıch kanál˚ u (side-channel attacks). Pˇri nich se vyuˇz´ıvá napˇr. v´ ypoˇcetn´ı ˇcas, elektromagnetické záˇren´ı, vnucené chyby nebo chybová hláˇsen´ı. To, ˇze je protokol redukcionisticky bezpeˇcn´ y, m˚ uˇze paradoxnˇe znamenat snadnou prolomitelnost systému. Napˇr. Rabin˚ uv kryptosystém (viz. odd´ıl 4.4) lze takto prolomit pomoc´ı tzv. u ´toku s výbˇerem zprávy (chosen-ciphertext attack), kter´ y je rovnˇeˇz uveden v odd´ılu 4.4.

3.4

Pouˇ zit´ a tvrzen´ı a algoritmy

ˇ ınská vˇeta o zbytc´ıch). Necht’ n1 , n2 , . . . , nk jsou kladná po dvou Vˇ eta 3.12 (C´ nesoudˇelná celá ˇc´ısla a necht’ r1 , r2 , . . . , rk jsou libovolná celá ˇc´ısla. Pak existuje právˇe jedno N (mod n1 n2 . . . nk ) takové, ˇze N ≡ ri (mod ni ),

∀i = 1, . . . , k.

D˚ ukaz nalezneme napˇr. v knize [1] na stranˇe 255. 1

Symetrické ˇsifry jsou takové, ˇze funkˇcn´ı vztah f algoritmu pro ˇsifrován´ı EK a algoritmu pro deˇsifrov´ an´ı DK , DK = f (EK ), i jeho inverze f −1 jsou snadno odvoditelné. U symetrick´ ych ˇsifer se pro ˇsifrov´ an´ı i deˇsifrov´ an´ı pouˇz´ıvá stejn´ y kl´ıˇc K. 2 Idea redukce spoˇc´ıv´ a v tom, ˇze m˚ uˇzeme ukázat, ˇze ze sloˇzitosti jednoho problému P1 plyne sloˇzitost jiného problému P2 (nebo ekvivalentnˇe z jednoduchosti problému P2 plyne jednoduchost problému P1 ) tak, ˇze kdokoliv, kdo má algoritmus na ˇreˇsen´ı P2 (s ˇcasovou sloˇzitost´ı O(g)) jej m˚ uˇze pouˇz´ıt k ˇreˇsen´ı P1 s relativnˇe mal´ ym zvˇetˇsen´ım u ´sil´ı (tedy opˇet s ˇcasovou sloˇzitost´ı O(g)). V takovém pˇr´ıpadˇe ˇr´ık´ ame, ˇze se P1 redukuje na P2 .

10

Následuj´ıc´ı jednoduch´ y d˚ usledek ˇc´ınské vˇety o zbytc´ıch pouˇzijeme v odd´ılu 4.4 vˇenovaném Rabinovu kryptosystému. D˚ usledek 3.13. Necht’ n je souˇcin dvou r˚ uzných lichých prvoˇc´ısel, n = pq, a necht’ v ∈ QRn . Pak existuj´ı právˇe ˇctyˇri navzájem r˚ uzné druhé odmocniny z v modulo n. D˚ ukaz. Z pˇredpokladu vˇety, ˇze v ∈ QRn , je zajiˇstˇena existence u ∈ Z∗n takového, ˇze v = u2 mod n. Oznaˇcme vp := v mod p a vq := v mod q a ukaˇzme, ˇze existuj´ı právˇe dvˇe r˚ uzné opdmocniny z vp modulo p a právˇe dvˇe r˚ uzné odmocniny z vq modulo q. Postaˇc´ı, kdyˇz se zamˇeˇr´ıme na pˇr´ıpad odmocniny z vp modulo p; v pˇr´ıpadˇe odmocniny z vq modulo q by byl postup obdobn´ y. Vyuˇzijeme známého faktu, ˇze polynom stupnˇe s nad tˇelesem T má v T nejv´ yˇse s koˇren˚ u. Na hledán´ı kvadratického rezidua z vp modulo p m˚ uˇzeme totiˇz nahl´ıˇzet jako na hledán´ı koˇren˚ u 2 ˇ polynomu up − vp nad tˇelesem Zp . C´ısla up , p − up , kde up := u mod p, jsou zˇrejmˇe koˇreny tohoto polynomu. Kdyby platilo up = p − up , pak by bylo p = 2up , coˇz by byl spor s lichost´ı prvoˇc´ısla p. T´ım jsme dokázali existenci právˇe dvou odmocnin z vp modulo p a právˇe dvou odmocnin z vq modulo q (oznaˇcme uq := u mod q). Jejich vzájemnou kom” binac´ı“ z´ıskáme ˇctyˇri ˇc´ısla, která oznaˇc´ıme u1 , u2 , u3 , u4 . Plat´ı pro nˇe následuj´ıc´ı kongruence: u1 u2 u3 u4

≡ up (mod p), ≡ up (mod p), ≡ −up (mod p), ≡ −up (mod p),

u1 u2 u3 u4

≡ uq (mod q), ≡ −uq (mod q), ≡ uq (mod q), ≡ −uq (mod q).

(3.1)

Podle ˇc´ınské vˇety o zbytc´ıch (3.12) je kaˇzdé z ˇc´ısel u1 , u2 , u3 , u4 jednoznaˇcnˇe urˇcené modulo n. Zb´ yvá ukázat, ˇze ˇc´ısla u1 , u2 , u3 , u4 jsou navzájem r˚ uzná modulo n a ˇze se jedná o druhé odmocniny z u modulo n. Pokud by nˇekterá z ˇc´ısel u1 , u2 , u3 , u4 byla shodná modulo n, byla by shodná také modulo p a modulo q, coˇz zˇrejmˇe neplat´ı. Nyn´ı ukáˇzeme, jak´ ym zp˚ usobem lze spoˇc´ıtat ˇc´ısla u1 , u2 , u3 , u4 a ˇze se jedná o druhé odmocniny z v modulo n. Aby byly splnˇeny vztahy (3.1), mus´ı existovat celá ˇc´ısla c1 , d1 , x1 , y1 , . . . , c4 , d4 , x4 , y4 taková, ˇze u1 u2 u3 u4

= (up (1 − c1 p) + uq (1 − d1 q)) mod n = (up x1 q + uq y1 p) mod n, = (up (1 − c2 p) − uq (1 − d2 q)) mod n = (up x2 q − uq y2 p) mod n, = (−up (1 − c3 p) + uq (1 − d3 q)) mod n = (−up x3 q + uq y3 p) mod n, = (−up (1 − c4 p) − uq (1 − d4 q)) mod n = (−up x4 q − uq y4 p) mod n.

(3.2)

Tedy ci p + xi q = 1 a yi p + di q = 1 pro vˇsechna i = 1, . . . , 4. Tato ˇc´ısla z´ıskáme napˇr. pomoc´ı rozˇs´ıˇreného Euklidova algoritmu 3.21. Je tedy zˇrejmé, ˇze m˚ uˇzeme poloˇzit c1 = c2 = c3 = c4 = y1 = y2 = y3 = y4 =: c a d1 = d2 = d3 = d4 = x1 = x2 = x3 = x4 =: d. Pak se vztahy (3.2) zjednoduˇs´ı na 11

u1 = (up dq + uq cp) mod n, u2 = (up dq − uq cp) mod n, u3 = (−up dq + uq cp) mod n, u4 = (−up dq − uq cp) mod n.

(3.3)

Nyn´ı ukáˇzeme, ˇze ˇc´ıslo u1 je druhá odmocnina z v modulo n. Pro u2 , u3 a u4 by byl postup obdobn´ y. Zˇrejmˇe existuj´ı celá ˇc´ısla l1 , l2 , l3 taková, ˇze u1 = (up dq + uq cp) mod n = (u + l1 p)dq + (u + l2 q)cp + l3 pq. Umocn´ıme-li ˇc´ıslo u1 na druhou modulo n, po snadn´ ych u ´pravách z´ıskáme rovnost u21 mod n = ((u + l1 p)dq + (u + l2 q)cp + l3 pq) mod n = u2 (c2 p2 + d2 q 2 ) mod n = = u2 (1 − 2cdpq) mod n = u2 mod n = v, kde jsme vyuˇzili vztahu cp + dq = 1, z kterého plyne 1 = (cp + dq)2 = c2 p2 + +2cdpq + d2 q 2 . Poznámka 3.14. Pˇredchoz´ı d˚ ukaz dává návod, jak nálezt vˇsechny ˇctyˇri druhé odmocniny z kvadratického rezidua modulo n, známe-li druhé odmocniny z vp modulo p a z vq modulo q (jak uˇz je uvedeno v´ yˇse, algoritmus na jejich hledán´ı nalezneme v knize [7] na stranˇe 100), a to pomoc´ı vztah˚ u (3.3). Algoritmus 3.22 je speciáln´ım pˇr´ıpadem algoritmu odvozeného z tohoto d˚ ukazu. Poznámka 3.15. Vˇsimnˇeme si, ˇze v d˚ usledku 3.13 pˇredpokládáme v ∈ QRn , ∗ z ˇcehoˇz plyne u ∈ Zn , a tedy GCD(u, n) = 1. Kdyby u ∈ Zn \ {0} bylo soudˇelné s n, pak by bez u ´jmy na obecnosti GCD(u, n) = p. Potom by z d˚ ukazu pˇredchoz´ıho d˚ usledku plynula existence pouze dvou r˚ uzn´ ych druh´ ych odmocnin z v = u2 modulo n, nebot’ by bylo up = 0. Definice 3.16. Eulerova funkce ϕ : N → N je zobrazen´ı, které pro n ∈ N udává poˇcet pˇrirozen´ ych ˇc´ısel menˇs´ıch neˇz n, která jsou s n nesoudˇelná. K v´ ypoˇctu hodnoty Eulerovy funkce lze pouˇz´ıt následuj´ıc´ı vztah: Y 1 ϕ(n) = n (1 − ), p p|n

kde souˇcin bereme pˇres vˇsechna navzájem r˚ uzná prvoˇc´ısla, která dˇel´ı n. Pˇ r´ıklad 3.17. Pouˇzit´ım pˇredchoz´ı formule spoˇctˇeme hodnotu Eulerovy funkce ˇc´ısla 36: 1 1 ϕ(36) = ϕ(22 32 ) = 36(1 − )(1 − ) = 12. 2 3 Vˇ eta 3.18 (Malá Fermatova vˇeta). Necht’ n je libovolné pˇrirozené ˇc´ıslo a necht’ a je pˇrirozené ˇc´ıslo nesoudˇelné s n. Pak plat´ı aϕ(n) ≡ 1 (mod n). D˚ ukaz této vˇety nalezneme napˇr. v knize [1] na stranˇe 254. Poznámka 3.19. Pˇredchoz´ı vˇetˇe se také nˇekdy ˇr´ıká Fermat-Eulerova vˇeta. Algoritmus 3.20 (Euklid˚ uv algoritmus). k VSTUP: Dvˇe nezáporná celá ˇc´ısla a a b, a ≥ b. ´ VYSTUP: Nejvˇetˇs´ı spoleˇcn´ y dˇelitel ˇc´ısel a a b. POSTUP: 12

1. Dokud b > 0, dˇelej následuj´ıc´ı: Poloˇz r := a mod b, a := b, b := r. 2. Vrat’ a. Algoritmus 3.21 (Rozˇs´ıˇren´ y Euklid˚ uv algoritmus). k VSTUP: Dvˇe nezáporná celá ˇc´ısla a a b, a ≥ b. ´ VYSTUP: d = GCD(a, b) a ˇc´ısla x, y ∈ Z splˇ nuj´ıc´ı ax + by = d. POSTUP: 1. Poloˇz x1 := 0, x2 := 1, y1 := 1, y2 := 0. 2. Dokud b > 0, dˇelej následuj´ıc´ı: (a) Poloˇz q := a div b, r := a − qb, x := x2 − qx1 , y := y2 − qy1 . (b) Poloˇz a := b, b := r, x2 := x1 , x1 := x, y2 := y1 , y1 := y. 3. Poloˇz d := a, x := x2 , y := y2 a vrat’ (d, x, y). Algoritmus 3.22 (V´ ypoˇcet druh´ ych odmocnin modulo n = pq, kde p a q jsou prvoˇc´ısla taková, ˇze p ≡ 3 (mod 4) a q ≡ 3 (mod 4)). k VSTUP: Pˇrirozené ˇc´ıslo c ∈ Zn . ´ ˇ ri druhé odmocniny z c modulo n. VYSTUP: Ctyˇ POSTUP: 1. Pouˇzit´ım rozˇs´ıˇreného Euklidova algortimu (3.21) najdi ˇc´ısla a, b ∈ Z, pro která plat´ı ap + bq = 1. 2. Poloˇz r := c(p+1)/4 mod p. 3. Poloˇz s := c(q+1)/4 mod q. 4. Poloˇz x := (aps + bqr) mod n. 5. Poloˇz y := (aps − bqr) mod n. 6. Vrat’ (±x mod n, ±y mod n). Poznámka 3.23. Algoritmy 3.20 a 3.21 maj´ı ˇcasovou sloˇzitost O(log2 (max{a, b})), algoritmus 3.22 má ˇcasovou sloˇzitost O(log3 (max{a, b})).

13

Kapitola 4 Stavebn´ı prvky protokol˚ u ˇ U symetrick´ ych ˇsifer se pro ˇsifrován´ı i deˇsifrován´ı pouˇz´ıvá jeden kl´ıˇc K. Sifrovac´ ı transformaci u symetrické ˇsifry proto oznaˇcujeme EK (.) a deˇsifrovac´ı transformaci DK (.). U asymetrick´ ych ˇsifer se pouˇz´ıvá kl´ıˇcov´ y pár — veˇrejn´ y kl´ıˇc K1 a soukrom´ y ˇ kl´ıˇc K2 . Sifrovac´ ı transformaci u asymterické ˇsifry oznaˇcujeme EK1 (.) a deˇsifrovac´ı transformaci DK2 (.).

4.1

Haˇ sovac´ı funkce

Definice 4.1. Haˇsovac´ı funkce (hash function) H : M → {0, 1}k (kde k ∈ N je pevnˇe dané) je funkce, která pro libovoln´ y vstup m ∈ M vrac´ı v´ ystup h zvan´ y hodnota haˇse (hash value) (nebo krátce haˇs ), t.j. h = H(m), splˇ nuj´ıc´ı následuj´ıc´ı podm´ınky: 1. pro libvolné m ∈ M je snadné spoˇc´ıtat H(m), 2. pro dané h je v´ ypoˇcetnˇe nároˇcné naj´ıt m takové, ˇze h = H(m), 3. je v´ ypoˇcetnˇe nároˇcné naj´ıt dvˇe zprávy m a m0 takové, ˇze H(m) = H(m0 ). Vlastnost 2. z pˇredchoz´ı definice se naz´ yvá jednosmˇernost a vlastnosti 3. 1 ˇr´ıkáme bezkoliznost . ´ Ulohou haˇsovac´ı funkce je vytvoˇrit jak´ ysi otisk zprávy. V kryptografii se nejˇcastˇeji pouˇz´ıvá u digitáln´ıch podpis˚ u a k zajiˇstˇen´ı integrity zpráv. Zajiˇstˇen´ı integrity zprávy znamená, ˇze pokud s ˇsifrovou zprávou c = Ek1 (m) poˇsleme pˇr´ıjemci také haˇs h = H(m), pak v pˇr´ıpadˇe, ˇze nˇejak´ y u ´toˇcn´ık zprávu c modifikuje na 0 zprávu c , pˇr´ıjemce tuto skuteˇcnost pozná, pokud si po deˇsifrován´ı Dk2 (c0 ) = m0 spoˇc´ıtá H(m0 ) = h0 6= h. 1

Rozliˇsujeme dva druhy koliz´ı. Zm´ınˇená kolize se naz´ yvá kolize prvn´ıho ˇr´ adu. Schopnost hledat kolize druhého ˇr´ adu znamená, ˇze k libovolné dané zprávˇe m jsme schopni nalézt zprávu m0 takovou, ˇze H(m) = H(m0 ).

14

4.2

Digit´ aln´ı podpis

Definice 4.2. Digitáln´ı podpisové schéma (digital signature scheme) je schéma pouˇz´ıvaj´ıc´ı metody asymetrické kryptografie urˇcené k autentizaci zprávy. Jedná se o dva komplementárn´ı algoritmy — jeden pro podpis a jeden pro ovˇeˇren´ı jeho pravosti. Podepisovac´ı algoritmus (ve kterém se pouˇz´ıvá soukrom´ y kl´ıˇc) budeme znaˇcit Sig a ovˇeˇrovac´ı Ver (v nˇem se pouˇz´ıvá veˇrejn´ y kl´ıˇc). Digitáln´ı podpis mus´ı m´ıt následuj´ıc´ı vlastnosti: • Autentizace (authenticity): Lze prokázat, ˇze dokument skuteˇcnˇe podepsal jeho autor. • Integrita (integrity): Zpráva nem˚ uˇze b´ yt zmˇenˇená se zachován´ım platnosti podpisu. • Nepopiratelnost (non-repudiation): Osoba, která dokument podepsala, to nem˚ uˇze pozdˇeji popˇr´ıt. Digitáln´ım podpisem naz´ yváme v´ yslednou posloupnost bit˚ u. Digitáln´ı podpisové schéma se vˇetˇsinou pouˇz´ıvá ve spojen´ı s haˇsovac´ı funkc´ı2 . D˚ uvodem je to, ˇze v´ ypoˇcet podpisu pro rozsáhlé dokumenty trvá (oproti v´ ypoˇctu haˇse) pˇr´ıliˇs dlouho. Algoritmus Sig digitáln´ıho podpisu se aplikuje na v´ yslednou haˇs. V´ ystup ovˇeˇrovac´ıho algoritmu pro podpis s = Sig(m) zprávy m oznaˇc´ıme Ver(s, m) = 1, je-li podpis v poˇrádku, a Ver(s, m) = 0, jde-li o podvrˇzen´ y podpis.

4.3

RSA

RSA je asymetrická ˇsifra. Popis ˇsifry: Zvol´ıme náhodnˇe dvˇe r˚ uzná pˇribliˇznˇe stejnˇe velká prvoˇc´ısla p a q. Poloˇz´ıme n := pq, zvol´ıme celé e takové, ˇze 1 < e < ϕ(n) a GCD(e, ϕ(n)) = 1, a pomoc´ı rozˇs´ıˇreného Euklidova algoritmu (3.21) spoˇcteme d = e−1 mod ϕ(n). GCD znaˇc´ı funkci nejvˇetˇs´ı spoleˇcn´ y dˇelitel“ a ϕ je Eulerova funkce (viz. definici (3.16)), ” ϕ(n) = (p − 1)(q − 1). Veˇrejn´ ym kl´ıˇcem je pár (n, e) a soukrom´ ym kl´ıˇcem je ˇc´ıslo d (pˇr´ıpadnˇe trojice (p, q, d)). ˇ Sifrov´ an´ı je umocˇ nován´ı otevˇrené zprávy m ∈ Zn na veˇrejn´ y exponent e modulo n: c = me mod n. Deˇsifrován´ı je umocˇ nován´ı ˇsifrového textu c na soukrom´ y exponent d modulo n: m = cd mod n. Ukáˇzeme platnost posledn´ı rovnosti: cd mod n = (me mod n)d mod n = med mod n = m1 =m

k·ϕ(n)+1

mod n = m · m

k·ϕ(n)

mod n

2

(V3.18)

=

mod ϕ(n)

mod n =

m · 1 mod n = m.

Existuje i tzv. schéma s obnovou zpr´ avy (neboli RSA podepisovac´ı schéma), kde se podepisuje cel´ y dokument, ale to nebudeme uvaˇzovat

15

Máme-li dáno n, y a e a hledáme x takové, ˇze y = xe mod n, ˇr´ıkáme, ˇze ˇreˇs´ıme tzv. RSA problém. Pˇredpokládá se, ˇze RSA problém je ekvivalentn´ı problému faktorizace modulu n, a tedy ˇze jde o tˇeˇzk´ y problém.

4.4

Rabin˚ uv kryptosyst´ em

Rabin˚ uv kryptosystém je podobn´ y systému RSA. Jedin´ y rozd´ıl je ten, ˇze nam´ısto ˇc´ısla e nesoudˇelného s ϕ(n) je veˇrejn´ ym exponentem ˇc´ıslo 2. Pˇresnˇeji, zvol´ıme náhodnˇe dvˇe r˚ uzná pˇribliˇznˇe stejnˇe velká prvoˇc´ısla p a q, p ≡ 3 (mod 4), q ≡ 3 (mod 4), a poloˇz´ıme n := pq. Veˇrejn´ ym kl´ıˇcem je modulus n a soukrom´ ym kl´ıˇcem je dvojice (p, q). Pˇri ˇsifrován´ı umocˇ nujeme otevˇren´ y text m ∈ Zn na druhou modulo n, c = m2 mod n.

(4.1)

Pˇri deˇsifrován´ı najdeme pomoc´ı algoritmu 3.22 vˇsechny ˇctyˇri druhé odmocniny z c modulo n (viz. d˚ usledek 3.13). Ve velmi málo pravdˇepodobném pˇr´ıpadˇe, ˇze by GCD(m, n) > 1, by existovaly pouze dvˇe druhé odmocniny z c modulo n (viz. poznámku 3.15). Takto z´ıskané zprávy oznaˇc´ıme m1 , m2 , m3 a m4 . Jako zprávu m vybereme tu, která dává smysl. Jednoznaˇcnosti otevˇreného textu m˚ uˇzeme doc´ılit také t´ım, ˇze pˇred zaˇsifrován´ım pˇripoj´ıme na konec zprávy m nˇejak´ y konstantn´ı ˇretˇezec znak˚ u. Po deˇsifrován´ı potom vybereme tu zprávu mi , která konˇc´ı t´ımto ˇretˇezcem. Zat´ımco o RSA problému se pouze pˇredpokládá, ˇze je ekvivalentn´ı faktorizaci modulu, o invertován´ı Rabinovy funkce (4.1) to lze dokázat. Tvrzen´ı 4.3. Jsme-li schopni faktorizovat modulus n v polynomiáln´ım ˇcase, jsme schopni (pomoc´ı algoritmu na faktorizaci modulu n) v polynomiáln´ım ˇcase invertovat Rabinovu funkci, a naopak, jsme-li schopni v polynomiáln´ım ˇcase invertovat Rabinovu funkci, jsme schopni (pomoc´ı algoritmu na invertován´ı Rabinovy funkce) v polynomiáln´ım ˇcase faktorizovat modulus n. D˚ ukaz. Zp˚ usob, jak´ ym lze pˇri znalosti faktor˚ u p, q modulu n invertovat Rabinovu funkci, dává napˇr. algoritmus 3.22, kter´ y bˇeˇz´ı v ˇcase O(log3 (.)). Zb´ yvá dokázat druhou implikaci, totiˇz ˇze kdokoliv, kdo je schopen z ˇsifrového textu c naj´ıt otevˇren´ y text m v polynomiáln´ım ˇcase, je také schopen v polynomiáln´ım ˇcase faktorizovat n. Invertovat Rabinovu funkci znamená nalézt nˇekterou ze ˇctyˇr odmocnin z c modulo n. Jsou to ±m (mod n), ±αm (mod n), kde α ≡ 1 (mod p) a α ≡ −1 (mod q). D˚ uvodem platnosti tˇechto kongruenc´ı je to, ˇze c = m2 mod n

a

c = α2 m2 mod n,

a tedy m2 ≡ α2 m2 (mod n), z ˇcehoˇz plyne α2 ≡ 1 (mod n)

α2 − 1 ≡ 0 (mod n).

⇒

Tedy existuje nˇejaké γ ∈ Z takové, ˇze 16

(α − 1)(α + 1) = γpq. Nyn´ı mohou nastat dva pˇr´ıpady: 1. Bud’ α − 1 = σp a α + 1 = %q, kde γ = σ%, σ, % ∈ Z, a tedy plat´ı α ≡ 1 (mod p) a α ≡ −1 (mod q), 2. nebo α − 1 = τ pq (resp. α + 1 = τ pq), kde τ dˇel´ı γ, coˇz znamená, ˇze α ≡ 1 (mod n) (resp. α ≡ −1 (mod n)), ale odsud plyne, ˇze existuj´ı pouze dvˇe druhé odmocniny z kvadratického rezidua x modulo n, coˇz je ve sporu s d˚ usledkem 3.13. S pravdˇepodobnost´ı 1/2 bude inverz´ı Rabinovy funkce ±αm (mod n). V tom pˇr´ıpadˇe vydˇelen´ım spoˇc´ıtáme ±α mod n a pak rychle (se sloˇzitost´ı O(log2 (.))) faktorizujeme n pomoc´ı Euklidova algoritmu (3.20), nebot’ GCD(n, α − 1) = p. Pokud je inverz´ı Rabinovy funkce ±m, provedeme tento postup s jin´ ym m. Pravdˇepodobnost, ˇze po k kroc´ıch se nám nepodaˇr´ı faktorizovat n je 2−k , coˇz se limitnˇe bl´ıˇz´ı k nule. Nyn´ı dokáˇzeme redukcionistickou bezpeˇcnost (viz. odd´ıl 3.3) Rabinova kryptosystému. Tvrzen´ı 4.4 (Redukcionistická bezpeˇcnost Rabinova ryptosystému). Kdokoliv, kdo je schopen v polynomiáln´ım ˇcase (vzhledem k velikosti modulu n) k ˇsifrovému textu c naj´ıt otevˇrený text m (c = m2 mod n), je schopen (pomoc´ı algoritmu na hledán´ı otevˇreného textu m) v polynomiáln´ım ˇcase faktorizovat n. D˚ ukaz. Ten, kdo je schopen naj´ıt otevˇren´ y text m k ˇsifrovému textu c, mus´ı b´ yt schopen naj´ıt vˇsechny ˇctyˇri odmocniny z c modulo n, protoˇze kterákoliv z nich m˚ uˇze b´ yt hledan´ ym otevˇren´ ym textem m. To znamená, ˇze zná pˇr´ısluˇsné α (viz. d˚ ukaz pˇredchoz´ıho tvrzen´ı), a tedy je schopen faktorizovat n v ˇcase O(log2 (n)). T´ım je tedy dokázaná redukcionistická bezpeˇcnost Rabinova systému. Jak jsme ale uvedli v odd´ıle 3.3, plyne odsud jeho zranitelnost u ´tokem s v´ ybˇerem zprávy. V ˇclánku [5] je uveden následuj´ıc´ı u ´tok: Pˇredpokládejme, ˇze by u ´toˇcn´ık (Eva) nˇejak´ ym zp˚ usobem pˇrimˇel vlastn´ıka soukromého kl´ıˇce (p, q) (Alici), aby pro nˇej deˇsifroval nˇejakou ˇsifrovou zprávu, kterou si u ´toˇcn´ık vybere. Eva si vybere zprávu m ∈ Zn a poˇsle Alici ˇsifrov´ y text c = m2 mod n. Alice poˇsle Evˇe (nˇejakou3 ) druhou odmocninu z c. S pravdˇepodobnost´ı 1/2 to bude ±αm. V takovém pˇr´ıpadˇe Eva snadno faktorizuje n (viz. d˚ ukaz pˇredchoz´ıho tvrzen´ı) a bude schopná deˇsifrovat vˇsechny zprávy v tomto systému. Pokud j´ı Alice poˇsle ±m, pak Eva provede stejn´ yu ´tok s jin´ ym m. Po −k k pokusech je pravdˇepodobnost u ´spˇeˇsného u ´toku 1 − 2 . Jak m˚ uˇze Eva doc´ılit toho, aby j´ı Alice poslala deˇsifrované zprávy? Jedn´ım z takov´ ych pˇr´ıpad˚ u m˚ uˇze b´ yt zhroucen´ı systému, kdy se Eva jev´ı jako oprávnˇen´ y uˇzivatel, kter´ y se snaˇz´ı obnovit ztracená data. Je tedy vidˇet, ˇze stejná vlastnost, která dává Rabinovu systému redukcionistickou bezpeˇcnost, vede k jeho totáln´ımu kolapsu pˇri konfrontaci s jin´ ym typem 3

Zde je tˇreba si uvˇedomit, ˇze m nen´ı smyslupln´ y text, ale (vˇetˇsinou binárn´ı) ˇc´ıslo, které vznikne zak´ odov´ an´ım daného otevˇreného textu. Proto Alice nepoˇsle Evˇe nutnˇe ˇc´ıslo m. Dek´ odov´ an´ı z´ıskan´ ych odmocnin z ˇsifrového textu by totiˇz pro ni bylo zbyteˇcnˇe ˇcasovˇe nároˇcné.

17

u ´toˇcn´ıka. V praxi je ovˇsem takov´ yu ´tok obt´ıˇznˇe realizovateln´ y. Ze strany Alice by vyˇzadoval velkou m´ıru spolupráce a hlouposti.

18

Kapitola 5 Turingovy stroje Definice t´ ykaj´ıc´ı se Turingov´ ych stroj˚ u v této a pˇr´ıˇst´ı kapitole jsou pˇrevzaty z text˚ u [2] a [4]. Základn´ı model (jednopáskového) Turingova stroje (TM) se skládá z hlavy a oboustrannˇe nekoneˇcné pásky rozdˇelené na pol´ıˇcka. Pol´ıˇcka mohou b´ yt prázdná, nebo nést symboly z nˇejaké koneˇcné mnoˇziny. Hlava m˚ uˇze ˇc´ıst a pˇrepisovat obsah pol´ıˇcka, na kterém se nacház´ı a pohybovat se po pásce vlevo a vpravo. Dále Turing˚ uv stroj obsahuje vnitˇrn´ı pamˇet’, která m˚ uˇze nab´ yvat koneˇcného poˇctu stav˚ u. Na zaˇca´tku v´ ypoˇctu je páska prázdná aˇz na koneˇcnou souvislou posloupnost pol´ıˇcek. Jejich obsahu ˇr´ıkáme vstup. Matematicky je Turing˚ uv stroj definován takto: Definice 5.1. Turing˚ uv stroj je ˇctveˇrice T = (Σ, Q, P, qs ), kde • Σ je neprázdná koneˇcná mnoˇzina symbol˚ u, • Q je neprázdná koneˇcná mnoˇzina stav˚ u, • P je libovolná mnoˇzina P ⊆ Q × Σ × Q × Σ × M zvaná program Turingova stroje. M je mnoˇzina pohyb˚ u {←, →, −}, kde ← znamená pohyb o jedno pol´ıˇcko doleva, → o jedno pol´ıˇcko doprava a − znamená, ˇze hlava z˚ ustane na aktuáln´ım pol´ıˇcku, • qs ∈ Q je poˇcáteˇcn´ı stav stroje. Libovoln´ y prvek (q, s, q 0 , s0 , m) ∈ P se naz´ yvá instrukce. Instrukci Turingova stroje m˚ uˇzeme interpretovat takto: Pokud jsi ve stavu q a ˇcteˇs symbol s, zmˇen ˇ ho na symbol s0 , pˇrejdi do stavu q 0 a proved’ pohyb m. Má-li stroj pro kaˇzd´ y vnitˇrn´ı stav (kombinaci stavu q a symbolu s) jedinou instrukci, naz´ yvá se deterministický. V opaˇcném pˇr´ıpadˇe se naz´ yvá nedeterministický. Definice 5.2. Mnoˇzinu symbol˚ u Σ naz´ yváme abeceda. Mnoˇzinu koneˇcn´ ych po∗ ∗ sloupnost´ı symbol˚ u z abecedy Σ znaˇc´ıme Σ . Prvky mnoˇziny Σ naz´ yváme slova. Libovolnou mnoˇzinu slov naz´ yváme jazyk.

19

Pro teorii interaktivn´ıch d˚ ukaz˚ u budeme potˇrebovat také definici v´ıcepáskového Turingova stroje. V´ıcepáskov´ y Turing˚ uv stroj je podobn´ y jednopáskovému, ale má k nezávisl´ ych pásek, kde k je konstanta. Kaˇzdá z pásek má svoji vlastn´ı ˇctec´ı a zapisovac´ı hlavu. Instrukce stroje jsou závislé na vˇsech k symbolech ˇcten´ ych hlavami na jednotliv´ ych páskách. k-páskov´ y TM má vˇsak pouze jeden stav. Protoˇze mnoˇzina stav˚ u Q m˚ uˇze b´ yt libovolná, m˚ uˇzeme ji chápat napˇr´ıklad jako Q = Q1 ×Q2 ×· · ·×Qk . V´ıcepáskové Turingovy stroje lze nahradit jednopáskov´ ymi. D˚ uvod pouˇz´ıván´ı v´ıcepáskov´ ych TM je zejména ten, ˇze oproti jednopáskov´ ym TM umoˇzn ˇuj´ı pˇrehlednˇejˇs´ı a rychlejˇs´ı v´ ypoˇcet. Formálnˇe definujeme k-páskov´ y Turing˚ uv stroj takto: Definice 5.3. k-páskový Turing˚ uv stroj je ˇctveˇrice T = (Σ, Q, P, qs ), kde • Σ je neprázdná koneˇcná mnoˇzina symbol˚ u, • Q je neprázdná koneˇcná mnoˇzina stav˚ u, • program P je libovolná mnoˇzina P ⊆ Q × Σk × Q × Σk × Mk , kde M je mnoˇzina pohyb˚ u {←, →, −}, • qs ∈ Q je poˇcáteˇcn´ı stav stroje. Neobejdeme se ani bez definice interaktivn´ıho Turingova stroje: Definice 5.4 (Interaktivn´ı Turing˚ uv stroj). Interaktivn´ım Turingovým strojem (ITM) naz´ yváme deterministick´ y sedmipáskov´ y Turing˚ uv stroj s následuj´ıc´ımi páskami: • jedna veˇrejná vstupn´ı páska pouze ke ˇcten´ı, • jedna soukromá vstupn´ı páska pouze ke ˇcten´ı, • jedna pracovn´ı páska pro ˇcten´ı i zápis, • jedna výstupn´ı páska pouze pro zápis, • dvojice komunikaˇcn´ıch pásek — jedna pouze pro zápis (tu naz´ yváme výstupn´ı komunikaˇcn´ı páska) a druhá pouze ke ˇcten´ı (tu naz´ yváme vstupn´ı komunikaˇcn´ı páska), • a jedna stavová páska pro ˇcten´ı i zápis sestávaj´ı z jediného pol´ıˇcka, které m˚ uˇze obsahovat 0 nebo 1 a na zaˇca´tku obsahuje 0. Kaˇzdému ITM je pˇriˇrazen samostatn´ y bit σ ∈ {0, 1} naz´ yvan´ y jeho identitou. O ITM ˇrekneme, ˇze je aktivn´ı, pokud je obsah jeho stavové pásky roven jeho identitˇe. V opaˇcném pˇr´ıpadˇe ˇr´ıkáme, ˇze je neˇcinný. Je-li stroj neˇcinn´ y, nemˇen´ı se jeho stav, polohy hlav na jednotliv´ ych páskách, ani obsah jeho pˇrepisovateln´ ych pásek. Obsah veˇrejné vstupn´ı pásky se naz´ yvá veˇrejný vstup, obsah soukromé vstupn´ı pásky se naz´ yvá náhodný vstup a obsahu v´ ystupn´ı pásky po skonˇcen´ı v´ ypoˇctu stroje ˇr´ıkáme výstup. Obsah napsan´ y na pˇrepisovatelnou komunikaˇcn´ı pásku bˇehem ˇcasového u ´seku, kdy je stroj aktivn´ı, se naz´ yvá zpráva poslaná v tomto ˇcasovém u ´seku. Obsah pˇreˇcten´ y ze ˇctec´ı komunikaˇcn´ı pásky bˇehem aktivn´ıho u ´seku se naz´ yvá zpráva pˇrijatá v tomto ˇcasovém u ´seku. 20

Pˇri v´ ypoˇctu nikdy neuvaˇzujeme jedin´ y interaktivn´ı stroj, ale dvojici ITM, které spolu sd´ılej´ı nˇekteré pásky. Zpráva poslaná jedn´ım strojem je pˇrijatou zprávou druhého stroje. Aktivn´ı stroj se stane neˇcinn´ ym pˇrepsán´ım obsahu stavové pásky a t´ım se druh´ y stroj (s opaˇcnou identitou) stane aktivn´ım. V´ ypoˇcet takové dvojice stroj˚ u sestává ze zpráv, které stroje stˇr´ıdavˇe pos´ılaj´ı jeden druhému v závislosti na jejich poˇcáteˇcn´ım (veˇrejném) vstupu, náhodn´ ych vstupech a na dosavadn´ıch pˇrijat´ ych zprávách. ˇ ıkáme, ˇze dva interaktivn´ı stroje Definice 5.5 (Spojen´ y v´ ypoˇcet dvou ITM). R´ jsou spojené, pokud • maj´ı opaˇcnou identitu, • sd´ılej´ı veˇrejnou vstupn´ı pásku, • sd´ılej´ı stavovou pásku, • vstupn´ı komunikaˇcn´ı páska jednoho stroje je v´ ystupn´ı komunikaˇcn´ı páskou druhého stroje a naopak. Zd˚ uraznˇeme, ˇze zbylé pásky tˇechto stroj˚ u (t.j. soukromá vstupn´ı, pracovn´ı a v´ ystupn´ı páska) jsou r˚ uzné. Spojený výpoˇcet spojené dvojice ITM na veˇrejném vstupu x je posloupnost pár˚ u lokáln´ıch konfigurac´ı kaˇzdého ze stroj˚ u. V kaˇzdém páru lokáln´ı konfigurace je jeden stroj aktivn´ı a druh´ y neˇcinn´ y. Jak uˇz bylo uvedeno, kdyˇz aktivn´ı stroj dokonˇc´ı sv˚ uj d´ılˇc´ı v´ ypoˇcet, pˇrep´ıˇse obsah stavové pásky na opaˇcnou hodnotu. T´ım se stane neˇcinn´ ym a druh´ y stroj se stane aktivn´ım. Jestliˇze jeden ze stroj˚ u dokonˇc´ı sv˚ uj v´ ypoˇcet, kdyˇz je obsah stavové pásky roven jeho identitˇe, pak ˇr´ıkáme, ˇze oba stroje dokonˇcily v´ ypoˇcet. Definice 5.6. Pravdˇepodobnostn´ı Turing˚ uv stroj je nedeterministick´ y Turing˚ uv stroj spolu s funkc´ı P : (Q × Σ × Q × Σ × M ) → [0, 1] takovou, ˇze pro kaˇzdé (q, s) ∈ Q × Σ plat´ı X P(q, s, q 0 , s0 , m) = 1, (q 0 ,s0 ,m)∈Q×Σ×M

kde Q je mnoˇzina stav˚ u, Σ mnoˇzina symbol˚ u a M mnoˇzina pohyb˚ u. Pˇredpokládejme, ˇze vˇsechny moˇzné interakce spojen´ ych stroj˚ u A a B na kaˇzdém veˇrejném vstupu skonˇc´ı po koneˇcném poˇctu krok˚ u. Symbolem (A, B)(x) oznaˇcujeme v´ ystup stroje B pˇri interakci se strojem A na veˇrejném vstupu x, kde náhodn´ y vstup na soukromé vstupn´ı pásce kaˇzdého ze stroj˚ u je vybrán rovnomˇernˇe a nezávisle z mnoˇziny vˇsech nekoneˇcn´ ych posloupnost´ı bit˚ u. Z této nekoneˇcné posloupnosti je pˇri (koneˇcném) v´ ypoˇctu pˇreˇcten (a má v´ yznam) pouze koneˇcn´ y prefix. V´ yznam soukromé vstupn´ı pásky m˚ uˇzeme chápat tak, ˇze dan´ y stroj má pro kaˇzdou dvojici (q, s) ∈ Q × Σ dvˇe moˇzné instrukce (q, s, q10 , s01 , m1 ) a (q, s, q20 , s02 , m2 ) a kaˇzdou z nich provede s pravdˇepodobnost´ı 1/2 (v závislosti na bitu ˇcteném ze soukromé vstupn´ı pásky). Interaktivn´ı Turing˚ uv stroj je tedy pravdˇepodobnostn´ı.

21

ˇ ıkáme, ˇze interaktivn´ı Definice 5.7 (Sloˇzitost v´ ypoˇctu interaktivn´ıho stroje). R´ stroj B má ˇcasovou sloˇzitost t : N → N, jestliˇze pro kaˇzd´ y interaktivn´ı stroj A a kaˇzd´ y vstup x plat´ı, ˇze stroj B pˇri interakci se strojem A na vstupu x vˇzdy (t.j. nezávisle na obsahu jeho soukromé vstupn´ı pásky a soukromé vstupn´ı pásky stroje A) skonˇc´ı v´ ypoˇcet bˇehem t(|x|) krok˚ u. Zd˚ uraznˇeme, ˇze právˇe definovaná ˇcasová sloˇzitost je funkc´ı pouze vstupu x a je tedy nezávislá na zprávách, které stroj B pˇrij´ımá.

22

Kapitola 6 Interaktivn´ı d˚ ukazy Interaktivn´ı d˚ ukaz zahrnuje dvˇe v´ ypoˇcetn´ı u ´lohy — tvorbu d˚ ukazu a ovˇeˇrován´ı jeho správnosti. Tyto u ´lohy vykonávaj´ı dva r˚ uzn´ı u ´ˇcastn´ıci zvan´ı dokazovatel (prover) a ovˇeˇrovatel (verifier). Tˇemito u ´ˇcstn´ıky jsou dva spojené interaktivn´ı Turingovy stroje. Dokazovatele oznaˇcujeme P a ovˇeˇrovatele V . Jejich interakce je parametrizovaná jejich spoleˇcn´ ym veˇrejn´ ym vstupem, kter´ y reprezentuje dokazované tvrzen´ı. V následuj´ıc´ı definici je v´ ystupem ovˇeˇrovatele jeho rozhodnut´ı, zda d˚ ukaz pˇrijme, nebo ne. V´ ystup 1 znamená pˇrijet´ı d˚ ukazu a v´ ystup 0 znamená jeho odm´ıtnut´ı. Definice 6.1. Dvojici spojen´ ych interaktivn´ıch Turingov´ ych stroj˚ u (P, V ) ˇr´ıkáme interaktivn´ı d˚ ukazový systém jazyka L, jestliˇze jsou splnˇeny následuj´ıc´ı tˇri podm´ınky: • Efektivita: stroj V pracuje v polymoniáln´ım ˇcase (vzhledem k délce vstupu x), ´ • Uplnost: P[(P, V )(x) = 1 | x ∈ L] ≥ ε, • Spolehlivost: pro kaˇzd´ y interaktivn´ı stroj P ∗ plat´ı P[(P ∗ , V )(x) = 1 | x ∈ / L] ≤ δ, kde ε a δ jsou konstanty splˇ nuj´ıc´ı 1 δ ∈ [0, ). 2

1 ε ∈ ( , 1], 2

Poznámka 6.2. Vˇsimnˇeme si, ˇze v definici (6.1) neklademe ˇzádné omezuj´ıc´ı podm´ınky na ˇcasovou sloˇzitost v´ ypoˇctu stroje P . Dále zd˚ uraznˇeme, ˇze podm´ınka pro spolehlivost se vztahuje ke vˇsem moˇzn´ ym dokazovatel˚ um P ∗ , zat´ımco podm´ınka pro u ´plnost pouze k danému dokazovateli P . Poznámka 6.3. Pro u ´ˇcely protokol˚ u pro interaktivn´ı d˚ ukazy pˇridáme kaˇzdému ITM jednu soukromou pomocnou vstupn´ı pásku pouze ke ˇcten´ı. Obsah kaˇzdé z nich bude souviset s vnitˇrn´ı konfigurac´ı pˇr´ısluˇsného stroje pˇred zaˇca´tkem bˇehu protokolu. Dokazovateli tato páska umoˇzn´ı efektivn´ı implementaci jeho u ´kolu. 23

Pod pojmem jazyk si m˚ uˇzeme pˇredstavit napˇr. grafov´ y izomorfismus. Vrát´ıme-li se k definici jazyka (5.2), pak v tomto pˇr´ıpadˇe bude abecedou grafy, slovy budou dvojice izomorfn´ıch graf˚ u a veˇrejn´ ym vstupem bude dvojice graf˚ u, o kter´ ych chceme rozhodnout, zda jsou izomorfn´ı. Dále rozebereme nˇekolik protokol˚ u pro interaktivn´ı d˚ ukazy z hlediska definice (6.1) a z hlediska dokazatelné bezpeˇcnosti (viz. odd´ıl 3.3). V protokolech se dokazovateli zpravidla ˇr´ıká Peggy a ovˇeˇrovateli Viktor. Toho se budeme drˇzet i my. ´ castn´ıky protokolu pro interaktivn´ı d˚ Uˇ ukaz mohou b´ yt dvˇe osoby, osoba a stroj nebo dva stroje. Typicky jsou od sebe fyzicky vzdáleni, takˇze v´ ypoˇcet na sd´ılen´ ych páskách spojen´ ych interaktivn´ıch stroj˚ u z definice (5.5) mus´ıme chápat tak, ˇze si vzájemnˇe pos´ılaj´ı v´ ysledky jednotliv´ ych v´ ypoˇct˚ u. Veˇrejn´ ym vstupem x b´ yvá v protokolech ˇc´ıslo (nebo mnoˇzina ˇc´ısel), o kterém dokazovatel tvrd´ı, ˇze pro nˇe zná ˇreˇsen´ı nˇejakého tˇeˇzkého matematického problému, z nichˇz nˇekteré jsme uvedli v kapitole 3. Tomuto ˇreˇsen´ı ˇr´ıkáme dokazovatelovo tajemstv´ı. Jazykem L b´ yvá mnoˇzina vˇsech ˇc´ısel, pro které dokazovatel zná ˇreˇsen´ı pˇr´ısluˇsného problému. Dokazovatel tedy dokazuje, ˇze pro veˇrejn´ y vstup x zná ˇreˇsen´ı nˇejakého tˇeˇzkého matematického problému; nemus´ı to ovˇsem znamenat, ˇze má algoritmus na ˇreˇsen´ı tohoto problému. Napˇr´ıklad pokud je protokol zaloˇzen na obt´ıˇznosti hledán´ı diskrétn´ıho logaritmu v grupˇe Z∗p s generátorem α, pak dokazovatel dokazuje, ˇze pro konkrétn´ı veˇrejn´ y vstup x ∈ Z∗p zná diskrétn´ı logaritmus logα x (ne vˇsak, ˇze tento logaritmus um´ı obecnˇe spoˇc´ıtat pro libovolné x), tedy ˇze x patˇr´ı do jazyka, j´ımˇz je mnoˇzina vˇsech ˇc´ısel z grupy Z∗p , pro nˇeˇz dokazovatel zná diskrétn´ı logaritmus. Dokazovatel z´ıská veˇrejné x tak, ˇze si zvol´ı y ∈ {0, 1, . . . , p − 2} a umocn´ı generátor α na y-tou modulo p; x := αy mod p. Ovˇeˇrovateli potom poskytne x a snaˇz´ı se mu dokázat, ˇze zná diskrétn´ı logaritmus y = logα x. Dokazovatel si m˚ uˇze zvolit libovoln´ y poˇcet (kter´ y oznaˇc´ıme k) ˇc´ısel yi ∈ {0, 1, . . . , p − 2}, i = 1, 2, . . . , k, a na kaˇzdé z nich umocnit generátor α; oznaˇcme xi := αyi mod p, i = 1, 2, . . . , k. Ke kaˇzdému takto z´ıskanému xi dokazovatel zná jeho diskrétn´ı logaritmus yi — tato xi tedy tvoˇr´ı jazyk L. Interaktivn´ı protokoly jsou obvykle formy výzva-opovˇed’ (challenge-response), coˇz znamená, ˇze oveˇrovatel pos´ılá dokazovateli v´ yzvy a ten na nˇe reaguje odpovˇed’mi. Komunikace u ´ˇcastn´ık˚ u (pos´ılán´ı zpráv) prob´ıhá pomoc´ı veˇrejného komunikaˇcn´ıho kanálu. Pˇredpokládáme, ˇze tento kanál je nezabezpeˇcen´ y, coˇz znamená, ˇze pˇr´ıpadn´ y u ´toˇcn´ık m˚ uˇze zachytit (odposlechnout) pos´ılané zprávy, ˇc´ıst si je a pˇr´ıpadnˇe je i pozmˇen ˇovat. Tˇemto u ´tok˚ um nelze zabránit. Pomoc´ı r˚ uzn´ ych kryptografick´ ych metod lze vˇsak sn´ıˇzit jejich u ´spˇeˇsnost. Dalˇs´ım problémem je to, ˇze se Viktor m˚ uˇze z komunikace s Peggy dozvˇedˇet nˇejakou netriváln´ı informaci o jej´ım tajemstv´ı — nˇeco nav´ıc, co nepotˇrebuje ke svému pˇresvˇedˇcen´ı, ˇze Peggy skuteˇcnˇe zná dokazovatelovo tajemstv´ı. Tento problém ˇreˇs´ı protokoly s nulovou znalost´ı (viz. definici (6.4)). Také dokazovatel m˚ uˇze cht´ıt z´ıskat nˇejakou v´ yhodu. Napˇr´ıklad se m˚ uˇze snaˇzit o to, aby s co nejvˇetˇs´ı pravdˇepodobnost´ı bylo v´ ysledkem protokolu (P, V )(x) = 1, i kdyby ve skuteˇcnosti x ∈ / L. Takov´ y dokazovatel se naz´ yvá podvádˇej´ıc´ı dokae zovatel (cheating prover) a oznaˇcuje se P ; v protokolech mu budeme ˇr´ıkat Eva. Ovˇeˇrovateli, kter´ y se snaˇz´ı z´ıskat nˇejaké netriviáln´ı informace o dokazovatelovˇe tajemstv´ı, ˇr´ıkáme neˇcestný ovˇeˇrovatel (dishonest verifier) a oznaˇcujeme jej Ve . Dokazovatel, resp. ovˇeˇrovatel, kter´ y dodrˇzuje chován´ı specifikované v protokolu, 24

se naz´ yvá ˇcestný (honest) dokazovatel, resp. ˇcestný ovˇeˇrovatel. Kaˇzd´ y dokazovatel i ovˇeˇrovatel, at’ uˇz ˇcestn´ y, nebo ne, mus´ı dodrˇzovat syntax komunikaˇcn´ıho rozhran´ı, protoˇze jej´ı nedodrˇzován´ı by bylo bezprostˇrednˇe odhaleno druhou stranou. Mohou tedy podvádˇet pouze ve sv´ ych soukrom´ ych v´ ypoˇctech a v tom, jaká data pos´ılaj´ı. Dalˇs´ı uˇziteˇcnou vlastnost´ı interaktivn´ıch d˚ ukaz˚ u (která ovˇsem nen´ı podm´ınkou pro interaktivnost d˚ ukazu) je nulov´ a znalost (zero-knowledge), coˇz v podstatˇe znamená, ˇze cokoliv, co je ovˇeˇrovatel schopen efektivnˇe spoˇc´ıtat po probˇehnut´ı protokolu, byl schopen efektivnˇe spoˇc´ıtat i pˇred n´ım. Pravdˇepodobnostn´ı polynomiáln´ı Turing˚ uv stroj je pravdˇepodobnostn´ı Turing˚ uv stroj (viz. definici 5.6), kter´ y vˇzdy skonˇc´ı sv˚ uj v´ ypoˇcet po polynomiáln´ım poˇctu krok˚ u (vzhledem k délce vstupu). Definice 6.4. Interaktivn´ı d˚ ukazov´ y systém (P, V ) jazyka L se naz´ yvá d˚ ukaz s dokonale nulovou znalost´ı (perfect zero-knowledge proof ) pro jazyk L, jestliˇze pro kaˇzd´ y interaktivn´ı pravdˇepodobnostn´ı polynomiáln´ı Turing˚ uv stroj V ∗ existuje (obyˇcejn´ y) pravdˇepodobnostn´ı polynomiáln´ı Turing˚ uv stroj M ∗ takov´ y, ˇze pro kaˇzdé x ∈ L plat´ı: • S pravdˇepodobnost´ı nejv´ yˇse 1/2 bude v´ ystupem stroje M ∗ speciáln´ı symbol ⊥. V tom pˇr´ıpadˇe ˇrekneme, ˇze v´ ypoˇcet stroje M ∗ selhal. • Plat´ı {M ∗ (x) | M ∗ (x) 6=⊥}x∈L ∼ {(P, V ∗ )(x)}x∈L , kde M ∗ (x) je v´ ystup stroje M ∗ na vstupu x, (P, V ∗ )(x) je v´ ystup stroje ∗ V po interakci se strojem P na vstupu x. Symbol ∼ oznaˇcuje stejné rozdˇelen´ı náhodn´ ych veliˇcin. Stroj M ∗ se naz´ yvá dokonalý simulátor pro interakci stroje V ∗ se strojem P . Pˇredchoz´ı definice ˇr´ıká, ˇze pro kaˇzdý stroj V ∗ (nejen pro V ) interaguj´ıc´ı se strojem P existuje dokonal´ y simulátor M ∗ . Tento simulátor dokáˇze simulovat interakci V ∗ s P , i kdyˇz nemá pˇr´ıstup ke stroji P . Z toho je vidˇet, ˇze stroj V ∗ nez´ıská od stroje P ˇza´dnou informaci o dokazovatelovˇe tajemstv´ı (aˇz na to, ˇze x ∈ L), protoˇze stejn´ y v´ ystup m˚ uˇze b´ yt vygenerován bez pˇr´ıstupu k P . Uvˇedomme si, ˇze zde jiˇz nen´ı v´ ystupem ovˇeˇrovatele pouze jeho rozhodnut´ı o pˇrijet´ı nebo nepˇrijet´ı d˚ ukazu. V´ ystupem (stroje V ∗ po interakci se strojem P a stroje M ∗ ) m˚ uˇze b´ yt ∗ napˇr´ıklad celá komunikace (tedy odeslané a pˇrijaté zprávy) stroj˚ uP aV . Zd˚ uraznˇeme, ˇze stroj M ∗ dokáˇze simulovat interakci stroj˚ u P a V ∗ pouze na vstupech x ∈ L (na vstupech x ∈ / L se m˚ uˇze chovat libovolnˇe). Nejbˇeˇznˇejˇs´ı pouˇzit´ı interaktivn´ıch d˚ ukazov´ ych systém˚ u je v identifikaˇcn´ıch schématech k prokázán´ı dokazovatelovy identity, neboli autentizaci. Pˇredpokládáme totiˇz, ˇze pouze dokazovatel zná dokazovatelovo tajemstv´ı. Nejjednoduˇsˇs´ı identifikaˇcn´ı schéma je následuj´ıc´ı: Peggy prokazuje svou identitu tajn´ ym heslem. Jediná zpráva v tomto protokolu je toto heslo, které Peggy poˇsle Viktorovi. Viktor má uloˇzenou haˇs Peggyina hesla (pokud by mˇel heslo v otevˇrené podobˇe, mohl by je pouˇz´ıt k vydáván´ı se za Peggy), kterou srovná s haˇs´ı doruˇceného hesla a pˇrijme Peggyinu identitu, právˇe kdyˇz se tyto dvˇe haˇse shoduj´ı. Toto schéma zˇrejmˇe splˇ nuje poˇzadavky pro interaktivn´ı d˚ ukaz, 25

ale má tu nev´ yhodu, ˇze kdokoliv, kdo bˇehem komunikace z´ıskal Peggyino heslo (odposlechem nebo jako oprávnˇen´ y pˇr´ıjemce), je m˚ uˇze pouˇz´ıt a vydávat se za Peggy.

6.1

Identifikace zaloˇ zen´ a na kryptografii s veˇ rejn´ ym kl´ıˇ cem

Oznaˇcme Peggyin tajn´ y kl´ıˇc sk a veˇrejn´ y kl´ıˇc pk. Zde je veˇrejn´ ym vstupem kl´ıˇc pk, jazykem mnoˇzina vˇsech veˇrejn´ ych kl´ıˇc˚ u pˇr´ısluˇsn´ ych k Peggyinu soukromému ” kl´ıˇci“ a dokazovatelov´ ym tajemstv´ım kl´ıˇc sk. Peggy prokazuje svoji identitu následovnˇe: 1. Viktor náhodnˇe vybere zprávu m, zaˇsifruje ji veˇrejn´ ym kl´ıˇcem pk a ˇsifrov´ y text (v´ yzvu) c = Epk (m) poˇsle Peggy. 2. Peggy deˇsifruje c tajn´ ym kl´ıˇcem sk a v´ ysledek (odpovˇed’) m0 = Dsk (c) poˇsle Viktorovi. 3. Viktor pˇrijme Peggyinu identitu, právˇe kdyˇz m = m0 . Tento protokol je efektivn´ı, protoˇze veˇsker´ y Viktor˚ uv v´ ypoˇcet spoˇc´ıvá ve vygenerován´ı a zaˇsifrován´ı zprávy m (sloˇzitost tohoto v´ ypoˇctu závis´ı na konkrétn´ı pouˇzité asymetrické ˇsifˇre, ale jistˇe je polynomiáln´ı, protoˇze jinak by byla daná ? ˇsifra prakticky nepouˇzitelná) a jednoduchém porovnán´ı m = m0 (které má konstantn´ı sloˇzitost O(1)). ´ Uplnost tohoto protokolu je splnˇena s ε = 1 (pˇredpokládáme-li, ˇze nedoˇslo k chybˇe pˇri pˇrenosu zpráv). Spolehlivost plyne z toho, ˇze podvádˇej´ıc´ı dokazovatel, kter´ y zná pouze veˇrejn´ y kl´ıˇc a ˇsifrov´ y text, by musel uhodnout otevˇren´ y text. To vˇsak nastane s pravdˇepodobnost´ı δ = 1/|M |, kde M je prostor vˇsech otevˇren´ ych zpráv. Toto schéma má vˇsak následuj´ıc´ı nedostatek: kdyby podvádˇej´ıc´ı Viktor m´ısto zaˇsifrované náhodné zprávy poslal zprávu urˇcenou Peggy, kterou dˇr´ıve zachytil v jej´ı komunikaci s jin´ ym u ´ˇcastn´ıkem a kterou nemohl deˇsifrovat, protoˇze nezná jej´ı soukrom´ y kl´ıˇc, Peggy by mu zprávu deˇsifrovala a Viktor by z´ıskal pˇr´ısluˇsn´ y otevˇren´ y text. Pˇridán´ım jednoho kroku na zaˇcátek tohoto protokolu lze zabránit právˇe zm´ınˇenému u ´toku s opakován´ım zprávy, a to pomoc´ı tzv. jednorázového ˇc´ısla (v anglické literatuˇre se pouˇz´ıvá název nonce jako zkratka number used once“). Jednorázové ” ˇc´ıslo NP je ˇc´ıslo, které si Peggy na zaˇcátku bˇehu protokolu náhodnˇe zvol´ı a poˇsle je Viktorovi. Stejnˇe jako v základn´ı verzi protokolu, Viktor vybere náhodnou zprávu m, za kterou pˇripoj´ı obdrˇzené jednorázové ˇc´ıslo NP , toto spojen´ı zaˇsifruje a poˇsle Peggy v´ ysledn´ y ˇsifrov´ y text Epk (m||NP ). Peggy zprávu deˇsifruje a zkontroluje, jestli je na konci jej´ı jednorázové ˇc´ıslo. Pokud ano, poˇsle Viktorovi zprávu, kterou z´ıskala deˇsifrac´ı (ale uˇz bez NP ); pokud ne, ukonˇc´ı komunikaci s Viktorem. Viktor opˇet Peggyin d˚ ukaz pˇrijme právˇe kdyˇz se zpráva, kterou od Peggy obdrˇzel, shoduje se zprávou m. Pokud Peggy vyb´ırá svoje jednorázové ˇc´ıslo z dostateˇcnˇe velkého rozmez´ı, pak je pravdˇepodobnost toho, ˇze by je Viktor uhodl, zanedbatelná. Protoˇze Peggy vol´ı na zaˇcátku kaˇzdého protokolu vˇzdy nové náhodné jednorázové ˇc´ıslo, m˚ uˇze si b´ yt 26

jistá, ˇze ˇsifrov´ y text, kter´ y j´ı Viktor poslal, byl vytvoˇren aˇz po tom, co mu poslala ˇc´ıslo NP . Dalˇs´ı zp˚ usob obrany proti u ´toku s reprodukc´ı zprávy je ten, ˇze Viktor pˇripoj´ı ke své zprávˇe m aktuáln´ı ˇcasov´ y u ´daj a poˇsle Peggy zaˇsifrované toto spojen´ı. Peggy text deˇsifruje a z´ıskanou zprávu poˇsle Viktorovi zpˇet pouze v pˇr´ıpadˇe, ˇze rozd´ıl jej´ıho systémového ˇcasu a ˇcasu, kter´ y j´ı poslal Viktor, je menˇs´ı neˇz pˇredem zvolená konstanta κ. K tomu je vˇsak nutná synchronizace jejich systémov´ ych ˇcas˚ u. Pˇri hodnocen´ı tohoto schématu z hlediska prokazatelné bezpeˇcnosti je tˇreba brát ohled na konkrétn´ı pouˇzitou asymetrickou ˇsifru. Lze pouˇz´ıt napˇr. ˇsifru RSA uvedenou v kapitole 4. Rabin˚ uv systém lze pouˇz´ıt pouze v pˇr´ıpadˇe zajiˇstˇen´ı jednoznaˇcnosti deˇsifrován´ı, coˇz lze napˇr´ıklad i pouˇzit´ım zm´ınˇeného jednorázového ˇc´ısla. Pˇri pouˇzit´ı ˇsifry RSA nem˚ uˇze b´ yt o redukcionistické bezpeˇcnosti tohoto pro’ tokolu ˇreˇc, nebot se zat´ım nepodaˇrilo prokázat ekvivalenci mezi RSA problémem a problémem faktorizace modulu n. Pˇri pouˇzit´ı Rabinova kryptosystému se zajiˇstˇen´ım jednoznaˇcnosti deˇsifrován´ı jde o redukcionisticky bezpeˇcn´ y protokol. Aby byl podvádˇej´ıc´ı dokazovatel schopen správnˇe odpovˇedˇet na Viktorovu v´ yzvu, musel by bud’ uhodnout m (coˇz je pro dostateˇcnˇe velk´ y prostor otevˇren´ ych zpráv M prakticky nemoˇzné), nebo by musel b´ yt schopen m spoˇc´ıtat, neboli prolomit Rabin˚ uv kryptosystém. Ten je ale, jak jsme uvedli v odd´ılu 4.4 redukcionisticky bezpeˇcn´ y. Odsud plyne redukcionistická bezpeˇcnost identifikaˇcn´ıho protokolu zaloˇzeného na Rabinovˇe kryptosystému. Tvrzen´ı 6.5. Identifikaˇcn´ı protokol zaloˇzený na kryptografii s veˇrejným kl´ıˇcem je (nezávisle na konkrétn´ı pouˇzité asymetrické ˇsifˇre) d˚ ukaz s dokonale nulovou znalost´ı. D˚ ukaz. V´ yˇse jsme ukázali, ˇze jde o interaktivn´ı d˚ ukaz. Dále je tˇreba popsat ∗ ˇcinnost simulátoru M . Jediné, ˇc´ım m˚ uˇze ovˇeˇrovatel ovlivnit podobu pos´ılan´ ych zpráv, je volba zprávy m. Simulátor M ∗ si na zaˇca´tku zvol´ı zprávu m (náhodnˇe, pokud simuluje komunikaci dokazovatele P s ˇcestn´ ym ovˇeˇrovatelem V ∗ , a speciálnˇe, pokud simuluje komunikaci s podvádˇej´ıc´ım dokazovatelem V ∗ ). Komunikace simulovaná strojem M ∗ má následuj´ıc´ı podobu: 1. Ovˇeˇrovatel poˇsle dokazovateli ˇsifrovou zprávu c = Epk (m). 2. Dokazovatel poˇsle ovˇeˇrovateli zprávu m (aniˇz by musel deˇsifrovat c). Simulátor M ∗ nikdy neselˇze a vzhledem k tomu, ˇze podoba zpráv pos´ılan´ ych stroji P a V ∗ závis´ı pouze na volbˇe zprávy m, v´ ystup stroje M ∗ jistˇe bude patˇrit do stejného rozdˇelen´ı jako v´ ystup stroje P po interakci se strojem V ∗ .

6.2

Fiat-Shamirovo identifikaˇ cn´ı sch´ ema

Toto schéma je zaloˇzeno na obt´ıˇznosti hledán´ı odmocniny modulo n, které je souˇcinem dvou prvoˇc´ısel. Mˇejme uzavˇrenou spoleˇcnost u ´ˇcastn´ık˚ u, v jejichˇz stˇredu je d˚ uvˇeryhodná autorita (trusted party), které budeme ˇr´ıkat Trent. Trent vygeneruje dvˇe r˚ uzná pˇribliˇznˇe stejnˇe velká prvoˇc´ısla p a q a poloˇz´ı n := pq. Faktory p a q si ponechá 27

v tajnosti a modulus n poskytne vˇsem u ´ˇcastn´ık˚ um (zveˇrejn´ı). Kaˇzdému u ´ˇcastn´ıkovi také pˇridˇel´ı jedineˇcné identifikaˇcn´ı ˇc´ıslo Id. Kaˇzd´ y u ´ˇcastn´ık si zvol´ı tajné v ∈ Z∗n , spoˇc´ıtá u := v 2 mod n a poˇsle u Trentovi. Trent ovˇeˇr´ı, jestli plat´ı GCD(u, n) = 1, coˇz je ekvivalentn´ı GCD(v, n) = 11 . Pokud ˇc´ısla u vˇsech u ´ˇcastn´ık˚ u spln´ı tuto podm´ınku, Trent ke kaˇzdému Id zveˇrejn´ı pˇr´ısluˇsné u a dále uˇz se procesu nez´ uˇcastˇ nuje. Pokud se Peggy chce autentizovat v˚ uˇci Viktorovi, poˇsle mu svoje Id a Viktor si k nˇemu najde pˇr´ısluˇsné u. Veˇrejn´ ym vstupem jsou v tomto schématu modulus n a ˇc´ıslo u, dokazovatelov´ ym tajemstv´ım je ˇc´ıslo v a jazykem je mnoˇzina vˇsech ˇc´ısel z QRn (viz. definici 3.4), jejichˇz modulárn´ı odmocninu Peggy zná. Protokol prob´ıhá následovnˇe: 1. Peggy náhodnˇe zvol´ı r ∈ Z∗n , poloˇz´ı a := r2 mod n a poˇsle a Viktorovi. 2. Viktor náhodnˇe zvol´ı e ∈ {0, 1} a poˇsle e Peggy. 3. Peggy spoˇc´ıtá b := rv e mod n a poˇsle b Viktorovi. 4. Viktor pˇrijme Peggyinu identitu, právˇe kdyˇz b2 ≡ aue (mod n). V tomto protokolu jsou poslány tˇri zprávy. Prvn´ı zprávou je závazek (commitment) Peggy, ˇze zná druhou odmocninu z a, druhou zprávou je Viktorova v´ yzva ’ e a tˇret´ı zpráva je Peggyina odpovˇed na Viktorovu v´ yzvu. Vˇsimnˇeme si, ˇze kdyby Peggy dvakrát zvolila stejné r ∈ Z∗n , at’ uˇz v komunikaci s Viktorem nebo s jin´ ym u ´ˇcastn´ıkem, hrozilo by j´ı prozrazen´ı tajemstv´ı v. Pokud by se tak stalo v komunikaci s Viktorem, kter´ y by si zaznamenával hodnoty a, které mu Peggy poslala a pˇr´ısluˇsné v´ yzvy e, které on poslal j´ı, pak by j´ı jako v´ yzvu poslal to druhé e” a poté jednoduˇse vydˇelen´ım pˇr´ısluˇsn´ ych b z´ıskal ” v. Kdyby poslala stejné a jinému u ´ˇcastn´ıkovi a t´ımto u ´ˇcastn´ıkem byl u ´toˇcn´ık, kter´ y zachytil dˇr´ıvˇejˇs´ı komunikaci Peggy s Viktorem, pak by podobnˇe jako Viktor zvolil komplementárn´ı e a spoˇc´ıtal by si v. Pokud by druh´ ym u ´ˇcastn´ıkem nebyl u ´toˇcn´ık, pak by s pravdˇepodobnost´ı 1/2 zvolil komplementárn´ı e a odposlouchávaj´ıc´ı u ´toˇcn´ık by opˇet snadno spoˇc´ıtal Peggyino tajemstv´ı. Fiat-Shamirovo schéma je zˇrejmˇe efektivn´ı, nebot’ veˇsker´ y Viktor˚ uv v´ ypoˇcet spoˇc´ıvá ve volbˇe ˇc´ısla e ∈ {0, 1} (se sloˇzitost´ı O(1)) a v´ ypoˇctu b2 (se sloˇzitost´ı ? O(|b|2 )), v´ ypoˇctu aue (se sloˇzitost´ı O(|a| · |u|)) a porovnán´ı b2 = aue (se sloˇzitost´ı O(1)). ´ Uplnost Fiat-Shamirova schématu je splnˇena, nebot’ pokud b = rv e , pak 2 e b = au , a stejnˇe jako u pˇredchoz´ıho schématu ε = 1. Spolehlivost: Podvádˇej´ıc´ı dokazovatel Eva m˚ uˇze pˇresvˇedˇcit Viktora o znalosti v, pokud udˇelá toto: 1. Eva náhodnˇe zvol´ı r ∈ Z∗n a e˜ ∈ {0, 1}, poloˇz´ı a := r2 u−˜e mod n a poˇsle a Viktorovi. 2. Viktor zvol´ı e ∈ {0, 1} a poˇsle e Evˇe. 1

Pokud by to neplatilo, pak by se nejvˇetˇs´ı spoleˇcn´ y dˇelitel u a n rovnal nˇekterému z faktor˚ u p nebo q, a t´ım by byla ohroˇzena spolehlivost schématu, protoˇze u ´ˇcastn´ık, kter´ y by znal faktory modulu, by si umˇel spoˇc´ıtat tajemstv´ı v kaˇzdého jiného u ´ˇcastn´ıka. V tom pˇr´ıpadˇe by musel Trent zvolit jiné n a u ´ˇcastn´ıci jiná u.

28

3. Eva poˇsle r Viktorovi. Jestliˇze e = e˜, pak Viktor pˇrijme Evin d˚ ukaz. To nastane s pravdˇepodobnost´ı 1/2. Tato pravdˇepodobnst je nejvyˇsˇs´ı moˇzná. Pokud by totiˇz pravdˇepodobnost Evina u ´spˇechu byla > 1/2, neboli P[(Pe, V )(v) = 1 | v ∈ / L] > 1/2 (jazykem L je zde mnoˇzina vˇsech ˇc´ısel z QRn , k nimˇz Eva zná druhou odmocninu modulo n), znamenalo by to, ˇze Eva zná nˇejaké a, pro které dokáˇze správnˇe zodpovˇedˇet obˇe v´ yzvy (pro e = 0 i e = 1). V následuj´ıc´ım tvrzen´ı ukáˇzeme, ˇze Fiat-shamirovo schéma je redukcionisticky bezpeˇcné (viz. odd´ıl 3.3). Tvrzen´ı 6.6. Kdokoliv, kdo je schopen pro alespoˇ n jeden závazek ve Fiat-Shamirovˇe schématu správnˇe odpovˇedˇet na obˇe výzvy, je schopen faktorizovat n. D˚ ukaz. Necht’ tedy Eva dokáˇze pro závazek a správnˇe odpovˇedˇet na obˇe v´ yzvy e = 0 i e = 1. Znamená to, ˇze um´ı spoˇc´ıtat b1 , b2 taková, ˇze b21 ≡ a (mod n) a b22 ≡ au (mod n). Z toho plyne, ˇze um´ı spoˇc´ıtat druhou odmocninu v z kvadratického rezidua u, v = b2 /b1 mod n. Tedy má algoritmus A, jehoˇz v´ ystupem pˇri vstupu u ∈ QRn je druhá odmocnina z u. Algoritmus A pak m˚ uˇze pouˇz´ıt k faktorizaci n (viz. odd´ıl 6.3). Toto schéma nen´ı spolehlivé, nebot’ neexistuje ˇza´dné δ ∈ [0, 12 ), pro které by byla splnˇena 3. podm´ınka z definice 6.1. t-násobn´ ym opakovan´ım protokolu sn´ıˇz´ıme pravdˇepodobnost u ´spˇeˇsného pod−t vodu ze strany dokazovatele na δ = 2 . Takové schéma uˇz tedy podm´ınku spolehlivosti splˇ nuje. Pˇri pouˇz´ıván´ı tohoto protokolu nehroz´ı ˇcestnému dokazovateli nebezpeˇc´ı podvrhnut´ı zprávy jako u pˇredchoz´ıho protokolu zaloˇzeného na kryptografii s veˇrejn´ ym kl´ıˇcem, protoˇze Viktor vyb´ırá svoje v´ yzvy z malé mnoˇziny {0, 1}. Jediná informace, kterou Viktor od Peggy z´ıská, je, ˇze Peggy zná druhou odmocninu z u. Tvrzen´ı 6.7. Fiat-Shamirovo identifikaˇcn´ı schéma je d˚ ukaz s dokonale nulovou znalost´ı (viz. definici 6.4). D˚ ukaz. V´ yˇse jsme ukázali, ˇze jde o interaktivn´ı d˚ ukaz. Je tˇreba popsat ˇcinnost ∗ simulátoru M . Jediné, ˇc´ım m˚ uˇze ovˇeˇrovatel ovlivnit bˇeh protokolu, je volba bitu e. Simulátor si na zaˇca´tku zvol´ı ˇc´ısla r a e (ˇc´ıslo r vol´ı náhodnˇe a bit e vol´ı v závislosti na tom, simuluje-li komunikaci ovˇeˇrovatele P s ˇcestn´ ym nebo ∗ s podvádˇej´ıc´ım ovˇeˇrovatelem V — náhodnˇe pro ˇcestného ovˇeˇrovatele a v pˇr´ıpadˇe podvádˇej´ıc´ıho dokazovatele zvol´ı stejn´ y bit jako stroj V ∗ ). V simulaci stroje M ∗ má komunikace dokazovatele s oveˇrovatelem následuj´ıc´ı pr˚ ubˇeh: 1. Dokazovatel poˇsle ovˇeˇrovateli ˇc´ıslo a := r2 u−e mod n. 2. Ovˇeˇrovatel poˇsle dokazovateli ˇc´ıslo e zvolené na zaˇca´tku. 3. Dokazovatel poˇsle ovˇeˇrovateli ˇc´ıslo r. Simulátor M ∗ nikdy neselˇze a vzhledem k tomu, ˇze podoba zpráv pos´ılan´ ych ∗ ∗ stroji P a V závis´ı pouze na volbˇe ˇc´ısel r a e, v´ ystup stroje M jistˇe bude patˇrit do stejného rozdˇelen´ı jako v´ ystup stroje P po interakci se strojem V ∗ .

29

6.3

Faktorizace n = pq pomoc´ı algoritmu na hled´ an´ı druh´ e odmocniny z kvadratick´ eho rezidua

Jak jsem jiˇz uvedli v ˇca´sti 4.4, jednoduch´ ym d˚ usledkem ˇc´ınské vˇety o zbytc´ıch (vˇeta 3.12) je toto tvrzen´ı: Je-li n rovno souˇcinu dvou lich´ ych prvoˇc´ısel p a q, pak existuj´ı ˇctyˇri druhé odmocniny z kvadratického rezidua x modulo n. Jsou to ±y, ±αy (mod n), kde α ≡ 1 (mod p) a α ≡ −1 (mod q). Zd˚ uvodnˇen´ı najdeme opˇet v ˇca´sti 4.4. Eva m˚ uˇze faktorizat n následuj´ıc´ım zp˚ usobem: Zvol´ı náhodné y ∈ Z∗n , poloˇz´ı x := y 2 mod n a hodnotu x pouˇzije jako vstup algoritmu A. Jeho v´ ystupem bude 0 druhá odmocnina y z kvadratického rezidua x. S pravdˇepodobnost´ı 1/2 bude y 0 = ±αy. V tom pˇr´ıpadˇe Eva napˇr. pomoc´ı rozˇs´ıˇreného Euklidova algoritmu 3.21 spoˇc´ıtá α = ±y/y 0 a pouˇzit´ım Euklidova algoritmu 3.20 faktorizuje n, nebot’ plat´ı GCD(n, α − 1) = p. V pˇr´ıpadˇe, ˇze y 0 = ±y, opakuje stejn´ y postup s jin´ ym y. Pravdˇepodobnost, ˇze po k opakován´ıch právˇe popsaného algoritmu se Evˇe nepodaˇr´ı faktorizovat n, je rovna 1/2k , coˇz se pro rostouc´ı k bl´ıˇz´ı k nule.

6.4

Rozˇ s´ıˇ ren´ e Fiat-Shamirovo identifikaˇ cn´ı sch´ ema

Chceme-li zmenˇsit poˇcet opakován´ı Fiat-Shamirova protokolu (napˇr. je-li komunikace ˇcasovˇe nebo finanˇcnˇe nároˇcná) se zachován´ım parametru δ, m˚ uˇzeme pouˇz´ıt tzv. rozˇs´ıˇrené Fiat-Shamirovo identifikaˇcn´ı schéma. V nˇem si kaˇzd´ y u ´ˇcastn´ık ∗ u této grupy. Dalˇs´ım m´ısto jednoho v ∈ Zn zvol´ı vektor v = (v1 , . . . , vk ) prvk˚ rozd´ılem oproti základn´ı verzi Fiat-Shamirova identifikaˇcn´ıho schématu je to, ˇze je základn´ı schéma t-krát zopakováno. Obdobnˇe jako v pˇredchoz´ım schématu, ym modulus n = pq a vektor u = (v12 , . . . , vk2 ) jsou zveˇrejnˇeny a v je dokazovatelov´ tajemstv´ım. Na zaˇca´tku protokolu d˚ uvˇeryhodná autorita Trent vygeneruje dvˇe r˚ uzná pˇribliˇznˇe stejnˇe velká prvoˇc´ısla p a q, která utaj´ı, a zveˇrejn´ı modulus n = pq. Dále kaˇzdému u ´ˇcastn´ıkovi pˇridˇel´ı jedineˇcné identifikaˇcn´ı ˇc´ıslo Id. Kaˇzd´ yzu ´ˇcastn´ık˚ u si 2 zvol´ı k náhodn´ ych ˇc´ısel v1 , v2 , . . . , vk ∈ Zn a poloˇz´ı u = (u1 , . . . , uk ) := (v1 , . . . , vk2 ). Vektor u poté odeˇsle Trentovi, kter´ y ovˇeˇr´ı, jestli GCD(ui , n) = 1 pro vˇsechna i = 1, . . . , k (vysvˇetlen´ı nalezneme u pˇredchoz´ıho protokolu). Stejnˇe jako u základn´ıho Fiat-Shamirova schématu, pokud vektory u vˇsech u ´ˇcastn´ık˚ u spln´ı tuto podm´ınku, Trent ke kaˇzdému Id zveˇrejn´ı pˇr´ısluˇsné u a dále uˇz se procesu nez´ uˇcastˇ nuje. Autentizace Peggy v˚ uˇci Viktorovi prob´ıhá následovnˇe: Zopakuj následuj´ıc´ı t-krát: 1. Peggy náhodnˇe zvol´ı r ∈ Z∗n , poloˇz´ı a := r2 a poˇsle a Viktorovi. 2. Viktor náhodnˇe zvol´ı e := (e1 , . . . , ek ) ∈ {0, 1}k a poˇsle e Peggy. Q 3. Peggy spoˇc´ıtá b := r ki=1 viei mod n a poˇsle b Viktorovi.

30

Q 4. Pokud b2 6≡ a ki=1 uei i (mod n), pak Viktor odm´ıtne Peggyinu identitu a ukonˇc´ı bˇeh protokolu. Toto sch´ ym nejnároˇcnˇejˇs´ım v´ ypoˇctem je Qema je efektivn´ı, protoˇze Viktorov´ v´ ypoˇcet a ki=1 uei i , kter´ y má sloˇzitost O(|a| · |u1 | · . . . · |uk |). ´ Uplnost: Pokud prav´ y dokazovatel Peggy i Viktor dodrˇzuj´ı protokol, pak Viktor pˇrijme Peggyin d˚ ukaz. Spolehlivost: Podvádˇej´ıc´ı dokazovatel Eva pˇresvˇedˇc´ı Viktora o tom, ˇze je Peggy, pokud správnˇe uhádne Viktorovu v´ yzvu e pro kaˇzdou iteraci, t.j. pokud se kt j´ı podaˇr´ı vybrat správn´ y prvek z {0, 1} , coˇz nastane s pravdˇepodobnost´ı 2−kt . Kdyby pravdˇepodobnost jej´ıho u ´spˇechu byla vˇetˇs´ı neˇz 2−kt (pravdˇepodobnost bereme pˇres vˇsechny v´ yzvy e), znamenalo by to, ˇze zná vektor A = (a1 , . . . , at ) j závazk˚ u a (jeden pro kaˇzdou iteraci j, 1 ≤ j ≤ t), pro kter´ y je schopna správnˇe odpovˇedˇet na dvˇe r˚ uzné Viktorovy v´ yzvy E = (e1 , . . . , et ) a F = (f 1 , . . . , f t ), E 6= F . Protoˇze jsou vektory E a F r˚ uzné, existuje iterace j taková, ˇze ej 6= f j . Eva um´ı správnˇe odpovˇedˇet na obˇe v´ yzvy e := ej a f := f j pro závazek a := aj . To znamená, ˇze dokáˇze spoˇc´ıtat b1 a b2 takové, ˇze Q Q b21 ≡ a ki=1 uei i (mod n) a b22 ≡ a ki=1 ufi i (mod n). Stejnˇe jako u pˇredeˇslého schématu z toho plyne, ˇze Eva dokáQ ˇze spoˇc´ıtat druhou odmocninu v = b2 /b1 náhodného kvadratického rezidua u = ki=1 ufi i −ei . A to je spor s naˇs´ım pˇredpokladem, ˇze poˇc´ıtán´ı druh´ ych odmocnin je nezvládnutelné bez znalosti faktor˚ u p a q modulu n.

6.5

Schnorr-Okamotovo identifikaˇ cn´ı sch´ ema

Na závˇer uvedeme identifikaˇcn´ı schéma (které je vylepˇsen´ım“ Schnorrova sché” matu zaloˇzeného na obt´ıˇznosti hledán´ı diskrétn´ıho logaritmu; viz. napˇr. [7], str. 414), k jehoˇz prolomen´ı by u ´toˇcn´ıkovi nestaˇcila ani pˇr´ıpadná znalost ˇreˇsen´ı problému diskrétn´ıho logaritmu. D˚ uvˇeryhodná autorita Trent pˇridˇel´ı kaˇzdému u ´ˇcastn´ıkovi P jedineˇcné identifikaˇcn´ı ˇc´ıslo IdP . Dále vygeneruje dvˇe prvoˇc´ısla p a q taková, aby problém nalezen´ı diskrétn´ıho logaritmu byl tˇeˇzk´ y v grupˇe Z∗p (tedy aby velikost p byla pˇribliˇznˇe 1024 bit˚ u) a aby q | (p − 1) a q mˇelo zhruba 160 bit˚ u. Trent dále vygeneruje (p−1)/q ∗ ∗ , kde βi jsou veˇrejné parametry α1 , α2 ∈ Zp ˇra´du q v grupˇe Zp (napˇr. αi = βi generátory Z∗p ), a koneˇcnˇe zvol´ı tzv. bezpeˇcnostn´ı parametr t takov´ y, aby platilo 2t < q, napˇr. t ≥ 40. Kaˇzd´ yu ´ˇcastn´ık P si zvol´ı jako sv˚ uj tajn´ y kl´ıˇc dvojici a1 , a2 ∈ Zq a spoˇc´ıtá si sv˚ uj veˇrejn´ y kl´ıˇc v := α1−a1 α2−a2 mod p. P se identifikuje Trentovi nekryp” tografick´ ym“ zp˚ usobem a poˇsle mu ˇc´ıslo v. Trent k sobˇe sváˇze“ v a IdP sv´ ym ” podpisem s := SigKTS (IdP , v), kde KTS je Trent˚ uv soukrom´ y podepisovac´ı kl´ıˇc ´ castn´ık pˇr´ısluˇsn´ y k veˇrejnému kl´ıˇci pro ovˇeˇrován´ı podpis˚ u, kter´ y oznaˇc´ıme KTV . Uˇ P obdrˇz´ı od Trenta certifikát certP = (IdP , v, s). Protokol pro autentizaci Peggy v˚ uˇci Viktorovi: 1. Peggy si náhodnˇe zvol´ı (závazek) k1 , k2 , 1 < k1 , k2 < q − 1, poloˇz´ı γ := α1k1 α2k2 mod p a poˇsle Viktorovi certP , γ. 31

?

2. Viktor ovˇeˇr´ı Trent˚ uv podpis na certifikátu certP , VerKTV (IdP , v, s) = 1 a poté poˇsle Peggy náhodné r (v´ yzvu), 1 < r < 2t . 3. Peggy zkontroluje, jestli 1 < r < 2t , spoˇc´ıtá y1 := k1 + a1 r mod q, y2 := k2 + a2 r mod q a poˇsle Viktorovi (odpovˇed’) y1 , y2 . 4. Viktor pˇrijme Peggyinu identitu, právˇe kdyˇz γ = α1y1 α2y2 v r mod p. Veˇsker´ y Viktor˚ uv v´ ypoˇcet zˇrejmˇe probˇehne v polynomiáln´ım ˇcase. Schéma je tedy efektivn´ı. Schéma je i u ´plné (s ε = 1), nebot’ α1y1 α2y2 v r mod p = α1k1 +a1 r

mod q

α2k2 +a2 r

mod q

(α1−a1 α2−a2 )r mod p =

= α1k1 α2k2 mod p = γ, protoˇze α1 , α2 jsou ˇra´du q v Z∗p . Nyn´ı ukáˇzeme, ˇze protokol je i spolehliv´ y. Jediná moˇznost, jak by se mohl podvádˇej´ıc´ı dokazovatel, kter´ y nezná tajemstv´ı (a1 , a2 ), pokusit pˇredvˇeˇcit Viktora o jeho znalosti, je ta, ˇze by se pokusil uhodnout r, a pak by ovˇeˇrovateli poslal γ = α1y1 α2y2 v r mod p s libovoln´ ymi y1 , y2 . To vˇsak nastane s pravdˇepodobnost´ı 1/2t , která se pro rostouc´ı bezpeˇcnostn´ı parametr t bl´ıˇz´ı k nule. Protokol je tedy spolehliv´ y s δ = 1/2t . Nyn´ı dokáˇzeme, ˇze toto schéma má vlastnost zero-knowledge. Tvrzen´ı 6.8. Schnorr-Okamotovo schéma je d˚ ukaz s dokonale nulovou znalost´ı. D˚ ukaz. Skuteˇcnost, ˇze se jedná o interaktivn´ı d˚ ukaz, jsem ukázali v´ yˇse. Nyn´ı pop´ıˇseme ˇcinnost simulátoru M ∗ . Ovˇeˇrovatel ovlivˇ nuje bˇeh protokolu pouze volbou ˇc´ısla r. Simulátor M ∗ si na zaˇca´tku svého v´ ypoˇctu zvol´ı ˇc´ısla r ∈ [2, 2t − 1] a y1 , y2 ∈ [0, q − 1] (ˇc´ısla y1 , y2 náhodnˇe, ˇc´ıslo r v závislosti na tom, jestli simuluje komunikaci dokazovatele P a ˇcestného nebo podvádˇej´ıc´ıho ovˇeˇrovatele V ∗ — pro ˇcestného ovˇeˇrovatele náhodnˇe, pro podvádˇej´ıc´ıho dokazovatele stejnˇe jako simulovan´ y dokazovatel V ∗ ). Komunikace simulovaná strojem M ∗ má následuj´ıc´ı podobu: 1. Dokazovatel poˇsle ovˇeˇrovateli ˇc´ıslo γ := α1y1 α2y2 v r mod p. 2. Ovˇeˇrovatel poˇsle dokazovateli ˇc´ıslo r. 3. Dokazovatel poˇsle ovˇeˇrovateli ˇc´ısla y1 , y2 . Simulátor M ∗ nikdy neselˇze a protoˇze podoba zpráv pos´ılan´ ych stroji P a V ∗ závis´ı pouze na volbˇe ˇc´ısel r, y1 a y2 , v´ ystup stroje M ∗ jistˇe bude patˇrit do stejného rozdˇelen´ı jako v´ ystup stroje P po interakci se strojem V ∗ .

32

Na závˇer ukáˇzeme zm´ınˇenou zaj´ımavou vlastnost tohoto protokolu, totiˇz ˇze u ´toˇcn´ıkovi, kter´ y by se snaˇzil z veˇrejného kl´ıˇce v z´ıskat soukrom´ y kl´ıˇc (a1 , a2 ), by nepomohla ani znalost ˇreˇsen´ı problému diskrétn´ıho logaritmu. Jistˇe existuje ˇc´ıslo l ∈ {1, 2, . . . , q} takové, ˇze plat´ı α2 = α1l mod p. Pak m˚ uˇzeme vztah pro v vyjádˇrit jako v = α1−a1 (α1l )−a2 mod p = α1−a1 −la2 mod p. Pˇredpokládáme, ˇze u ´toˇcn´ık dokáˇze ˇreˇsit problém diskrétn´ıho logaritmu, a tedy ´ cn´ık tak dokáˇze naj´ıt ˇc´ıslo x ∈ {0, 1, . . . , p − 2}, pro které plat´ı x = − logα1 v. Utoˇ z´ıská modulárn´ı rovnici x = a1 + la2 mod q s neznám´ ymi a1 , a2 , jej´ımˇz ˇreˇsen´ım je nekoneˇcnˇe mnoho dvojic (a1 , a2 ). Dalˇs´ı rovnice, které má u ´toˇcn´ık k dispozici jsou y1 = k1 + a1 r mod q, y2 = k2 + a2 r mod q s neznám´ ymi a1 , a2 , k1 , k2 . Lze si snadno rozmyslet, ˇze vˇsechny dalˇs´ı rovnice, které je u ´toˇcn´ık schopen z´ıskat, jsou lineárn´ı kombinac´ı uveden´ ych tˇr´ı rovnic. Pˇri dalˇs´ım probˇehnut´ı protokolu se pˇri správné volbˇe ˇc´ısel k1 , k2 poˇcet rovnic zv´ yˇs´ı o dvˇe, stejnˇe jako poˇcet neznám´ ych. Poˇcet rovnic, které bude m´ıt u ´toˇcn´ık k dispozici bude tedy stále o jedna menˇs´ı neˇz poˇcet neznám´ ych v tˇechto rovnic´ıch. Jejich soustava bude tedy m´ıt stále nekoneˇcnˇe mnoho ˇreˇsen´ı.

33

Literatura [1] Delfs H., Knebl H., Introduction to Cryptography — Principles and Applications, Springer, Berlin, 2002, ISBN 3-540-42278-1 [2] Goldreich O., Foundations of Cryptography, Cambridge University Press, Cambridge, 2001, ISBN 0-521-79172-3 [3] Hojs´ık M., Kryptografické protokoly pro elektronické volby, bakaláˇrská práce, Karlova Univerzita, Praha, 2004 ˇ texty k pˇrednáˇsce Sloˇzitost pro kryptografii na MFF UK, [4] Holub S., http://www.karlin.mff.cuni.cz/∼holub/texty.htm [5] Koblitz N., Menezes A. J., Another Look at Provable Security“, ” http://eprint.iacr.org/2004/152.pdf, 2004 [6] Mao W., Modern Cryptography — Theory and Practise, Prentice Hall PTR, Prentice-Hall, Inc., New Jersey, 2004, ISBN 0-13-066943-1 [7] Menezes A., van Oorschot P., Vanstone S., Handbook of Applied Cryptography, CRC Press, Boca Raton, 1997, ISBN 0-8493-8523-7

34

Univerzita Karlova v Praze Matematicko-fyzikální fakulta. Interaktivní důkazy. Katedra algebry

Recommend Documents