Kryptograficke protokoly

1. arbitrovane protokoly - arbitrem rozumime neutralni treti stranu, zajistujici ferovost, nevyhodou pouziti arbitra jsou zvysene naklady na provoz, problemy s dostupnosti, casove prodlevy, potize s duveryhodnosti a vykonem
2. rozhodovane (adjudicated) protokoly - rozhodci (adjudicator) je treti strana, ktera je schopna rozhodnout, zda operace byla vykonana ferove, pripadne kdo z ucastniku porusuje pravidla, treti strana je tedy pouzivana pouze pri sporu
3. samozabezpecovaci (self-enforcing) protokoly - samotny protokol zajistuje vzajemnou ochranu ucastniku

Digitalni podpisy

musi byt nefalsovatelne, autenticke, nemenitelne, "nerecyklovatelne"

Protokol pro symetricke systemy

1. S zasle arbitrovi A zpravu E(M, K_S)
2. Arbiter verifikuje odesilatele a prijemci R zasle E((M, S, E(M, K_S)), K_R)
3. Prijemce uschova M a E(M, K_S) pro ucely pripadneho dokazovani prijeti

v pripade, ze nepozadujeme utajeni prenasenych dat, vystacime s pouzitim MAC namisto sifrovani

na obranu proti opakovanemu pouziti dosle zpravy lze pouzit vhodnou casovou znamku, proti sestavovani novych zprav z casti drive doslych poslouzi casova znamka v kazdem sifrovanem bloku.

Protokol pro asymetricke systemy

Poker

Necht A hraje s B, A rozdava

1. A vezme karty, nahodne je seradi a zasifruje svym klicem, vysledek zasle B
2. B vybere m balicku, zasifruje je svym klicem a spolecne s dalsimi m balicky zasle zpet.
3. A desifruje vsechny zasifrovane balicky. M z nich je dosud zasifrovano K_B , ty zasle zpet B.
4. B desifruje prijate balicky
5. oba hraci maji k dispozici sve karty

protokol je snadno rozsiritelny pro vetsi pocet hracu, dukaz korektnosti hry se provadi zverejnenim utajovanych skutecnosti tak, aby kazdy z hracu mohl provest opakovani cele hry

pro uspesne zvladnuti kroku 3. je nutne, aby sifra komutovala

popsanou implementaci pomoci symetrickych systemu lze velmi snadno prevest na systemy asymetricke

protokol ma prakticke vyuziti:

distribuce sifrovacich klicu

Casove znamky

Spojovane (linked) znamky

1. Odesilatel S zasle arbitrovi A hashkod zpravy H_n.
2. A vrati odesilateli
   T_n = S_k(n, s, H_n, Tm_n; ID_n-1, H_n-1, T_n-1; H(ID_n-1, H_n-1, T_n-1))
   kde n je poradi zpravy, Tm_n cas podpisu zpravy, Id_n-1 ... jsou informace o predesle zprave, kterou arbitr vyrizoval
3. po vyrizeni nasledujici zpravy arbitr zasle odesilateli identifikaci nasledujiciho odesilatele

Chce-li nekdo overit casovou znamku zpravy, kontaktuje odesilatele Id_n-1 a Id_n+1 a pomoci nich overit platnost T_n.

Pro zvyseni bezpecnosti je mozne pripojit informace o vice predchozich zpravach a drzet seznam stejneho poctu nasledujicich odesilatelu

Dalsi moznosti je tento protokol:

1. H_n uzijeme jako vstup vhodneho generatoru nahodnych cisel, m nejblizsich vysledku bereme jako identifikace uzivatelu V₁, ...,V_m
2. vsem V_i zasle S hashkod H_n
3. V_i pripoji informaci o casu, cely balicek elektronicky podepise a vrati S
4. S uschova vsechny odpovedi jakozto casovou znamku

pouziti generatoru nahodnych cisel v 1. kroku zajistuje, ze S nemuze podvadet, neb nevi predem, kdo bude jeho zpravu podepisovat, navic okruh verifikatoru se bude pokazde menit

Fixace bitu (Bit commitment)

necht strana A dokazuje strane B znalost skutecnosti b

1. B zasle entite A nahodny retezec R
2. A spoji R se svoji informaci celou tuto zpravu zasifruje nahodny klicem K a vysledek zasle B E(K, R||b)
3. pri pozdejsim overovani A zasle B klic K, B desifruje prijatou zpravu, overi pritomnost R a prezkouma b

s pouzitim one-way funkci se muzeme omezit pouze na jednosmernou komunikaci

1. A vygeneruje dva nahodne retezce R₁ a R₂
2. A vytvori zpravu obsahujici R₁ , R₂ a b, spocita hashkod teto zpravy a B zasle H(R₁||R₂||b), R₁
3. v ramci dokazovani znalosti b zasle A puvodni zpravu (R₁||R₂||b)
4. B spocita hashkod a porovna R₁

Dukazy s nulovou informaci (zero-knowledge proofs)

• dokazovatel (prover) nesmi podvadet, pokud dukaz nezna, jeho sance presvedcit overovatele je miziva
• overovatel rovnez nesmi podvadet, o samotnem dukazu smi zjistit pouze to, ze jej dokazovatel zna. Zvlaste nesmi byt schopen cely dukaz rekonstruovat a sam provest.
• overovatel se nesmi dozvedet nic, co by nebyl schopen zjistit bez pomoci dokazovatele.

neni-li splnena posledni podminka, mluvime o dukazech s minimalnim vyzrazenim (minimum-disclosure proofs)

jeden z moznych dukazu zalozen na problematice Hamiltonovskych kruznic v grafu

1. Necht A zna Hamiltonovskou kruznici v grafu G
2. A provede nahodnou permutaci G. Puvodni graf a vznikly H jsou izomorfni.
3. Kopie grafu H je zaslan entite B
4. Overovatel B polozi dokazovateli A jednu z nasledujicich otazek:
   1. dokazat, ze G a H jsou izomorfni
   2. ukazat Hamiltonovskou kruznici v grafu H
5. opakovanim kroku 1. az 4. lze docilit potrebne jistoty

Oblivious transfer

A vygeneruje dva pary public-key klicu, oba verejne klice zasle B

B vytvori klic K pro symetricky algoritmus, tento klic zasifruje jednim z prijatych klicu a vysledek vrati A

A desifruje prijatou zpravu obema tajnymi klici, cimz ziska K₁ a K₂

Klicem K₁ zasifruje A jednu z posilanych zprav, klicem K₂ druhou a oba vysledky zasle B.

B se pokusi desifrovat prijate zpravy, pricemz v jednom pripade ziska smysluplny vysledek

Pripadne overeni se provede tak, ze A zverejni sve tajne klice.

Protokol sam o sobe lze pouzivat k distribuci sifrovacich klicu, pripadne jako obdobu hazeni korunou. Vetsi vyznam ma jako soucast nasledujiciho protokolu.

Podepisovani kontraktu (Contract signing)

nejjednodussim resenim je arbitrovany protokol, kde obe strany predaji centralni autorite sve podepsane kopie a tato treti strana zajisti vymenu po obdrzeni obou kopii

daleko lepsi je nasledujici distribuovany protokol:

1. A i B nahodne vygeneruji 200 konvencnich klicu, ktere rozdeli do dvouprvkovych mnozin
2. A i B vytvori 100 paru zprav L_n a R_n, zhruba ve tvaru "Toto je leva cast n-teho podpisu smlouvy "..., kazda ze zprav navic obsahuje polovinu elektronickeho popisu smlouvy, timestamp atd. Kontrakt povazujeme za podepsany druhou stranou, pokud se muzeme prokazat obema polovinami nektereho z podpisu.
3. A i B zasifruji i-ty par zprav i-tym parem klicu ("levou" zpravu jednim, "pravou" druhym z klicu)
4. obe strany si navzajem zaslou pary zasifrovanych zprav (200 zprav kazdy)
5. pouzitim protokolu pro Oblivious transfer si A a B navzajem zaslou vsechny sifrovaci klice - druha strana ma tedy z kazdeho paru jeden (ktery ?) klic
6. A i B provedou desifrovani tech zprav, ke kterym maji k dispozici odpovidajici klic
7. A zasle B prvni bit vsech 200 konvencnich klicu, obdobne B
8. predchozi krok opakujeme dokud nejsou preneseny vsechny bity klicu
9. obe smluvni strany mohou desifrovat vsechny zpravy -> kontrakt je podepsan

Problemem je, ma-li nekdo z podepisujicich vyrazne vetsi vypocetni kapacitu, v protokolu neni zlom, ve kterem by se vyrazne zmenila mira vazanosti ucastniku.

Elektronicka potvrzovana posta (digital certified mail)

1. A zasifruje posilanou zpravu nahodne zvolenym konvencnim klicem K
2. A vytvori 100 paru konvencnich klicu - prvni klic kazdeho paru je generovan nahodne, druhy je XOR prvniho klice a klice K
3. A zasifruje pomocnou zpravu kazdym ze 100 paru techto klicu (200 sifer)
4. vsechny vysledne pary sifer zasle B
5. B vygeneruje 100 paru nahodnych konvencnich klicu
6. B vytvori 100 paru zprav tvaru "Toto je leva cast meho potvrzeni cislo n". Opet potvrzeni o prjeti je platne, pokud se protejsi strana muze prokazat obema polovinami jednoho z exemplaru potvrzeni.
7. B zasifruje i-ty par zprav i-tym parem klicu ("levou" zpravu jednim, "pravou" druhym z klicu)
8. vysledne pary sifer zasle B protejsi strane
9. s pouzitim protokolu pro Oblivious transfer si A i B navzajem poslou vsech 100 paru svych klicu - zadna ze stran nevi, ktery klic z ktereho paru protejsek ma k dispozici
10. A i B desifruji vsechny zpravy, ke kterym maji klice a overi jejich smysluplnost
11. obe strany si zaslou prvni bit vsech 200 svych sifrovacich klicu
12. predchozi krok je opakovan dokud nejsou preeseny vsechny bity
13. A i B desifruji zbyvajici casti paru zprav, ktere v predchozich krocich obdrzeli - A ma k dispozici potvrzeni o prijeti zpravy od B a B muze provest XOR libovolneho paru klicu a desifrovat zpravu.

V ostatnich ohledech ma protokol obdobne vlastnosti jako protokol pro podepisovani kontraktu.

Bezpecne volby

• volit smi pouze opravneni volici
• kazdy smi hlasovat nejvyse jednou
• nikdo nesmi vedet, kdo jak volil
• nikdo nesmi menit volbu jinych
• kazdy hlas musi byt zapocitan
• je zjistitelne, kdo volil

Protokol se dvema centralnimi autoritami

1. vsichni volici zaslou RA zadost o validacni cislo
2. RA zasle kazdemu volici nahodne zvolene validacni cislo L, zaroven si ponecha seznam, kdo jake cislo dostal
3. RA zasle seznam validacnich cisel SA
4. kazdy z volicu si nahodne vybere svoje identifikacni cislo Id a SA zasle zpravu (L, Id, v) kde v je volba
5. SA porovna L se seznamem validacnich cisel z kroku 3. odpovidajici cislo skrtne a volicovo Id prida do seznamu asociovaneho s volenym kandidatem
6. po skonceni voleb SA zverejni vysledky voleb a seznamy identifikacnich cisel spojene se jmeny kandidatu

SA vsak muze registrovat neopravnene volice, pripadne nektere volice vicekrat. V pripade ze budou RA a SA spoupracovat, hrozi nebezpeci poruseni anonimity volicu.

Protokol bez centralni autority

1. vsichni volici zvazi sve rozhodnuti a
   1. ke sve volbe pripoji nahodny retezec
   2. zasifruji vysledek predchoziho kroku verejnym klicem volice D
   3. zasifruji vysledek predchoziho kroku verejnym klicem volice C
   4. zasifruji vysledek predchoziho kroku verejnym klicem volice B
   5. zasifruji vysledek predchoziho kroku verejnym klicem volice A
   6. pripoji k vysledku predchoziho kroku novy nahodny retezec, jehoz hodnotu uchovaji, a cele to zasifruji verejnym klicem volice D
   7. pripoji k vysledku predchoziho kroku novy nahodny retezec, jehoz hodnotu uchovaji, a celou zpravu zasifruji verejnym klicem volice C.
   8. pripoji k vysledku predchoziho kroku novy nahodny retezec, jehoz hodnotu uchovaji, a celou zpravu zasifruji verejnym klicem volice B.
   9. pripoji k vysledku predchoziho kroku novy nahodny retezec, jehoz hodnotu uchovaji, a celou zpravu zasifruji verejnym klicem volice A.
   vcelku tedy E_A(R₅, E_B(R₄, E_C(R₃, E_D(R₂, E_A(E_B(E_C(E_D(v, R₁)))))))) kde R_i je nahodny retezec a v volicovo rozhodnuti
2. vsichni volici poslou vysledky svych vypoctu volici A
3. A desifruje vsechny prijate zpravy svym tajnym klicem, otestuje pritomnost sveho hlasu a ze vsech zprav oddeli R₅.
4. A zamicha poradim zprav a vsechny posle volici B. Zpravy maji tvar E_B(R₄, E_C(R₃, E_D(R₂, E_A(E_B(E_C(E_D(v, R₁)))))))
5. B desifruje vsechny prijate zpravy svym tajnym klicem, otestuje pritomnost sveho hlasu a ze vsech zprav oddeli R₄.
6. B zamicha poradim zprav a vsechny posle volici C. Zpravy maji tvar E_C(R₃, E_D(R₂, E_A(E_B(E_C(E_D(v, R₁)))))) C desifruje vsechny prijate zpravy svym tajnym klicem, otestuje pritomnost sveho hlasu a ze vsech zprav oddeli R₃.
7. C zamicha poradim zprav a vsechny posle volici D. Zpravy maji tvar E_D(R₂, E_A(E_B(E_C(E_D(v, R₁))))) D desifruje vsechny prijate zpravy svym tajnym klicem, otestuje pritomnost sveho hlasu a ze vsech zprav oddeli R₂.
8. D zamicha poradim zprav a vsechny posle volici A. Zpravy maji tvar E_A(E_B(E_C(E_D(v, R₁)))) A desifruje vsechny prijate zpravy svym tajnym klicem, overi pritomnost sveho hlasu, vsechny zpravy elektronicky podepise a zasle vsem ostatnim. D_A(E_B(E_C(E_D(v, R₁))))
9. B overi a smaze elektronicky podpis volice A, desifruje vsechny prijate zpravy svym tajnym klicem, overi pritomnost sveho hlasu, vsechny zpravy elektronicky podepise a zasle vsem ostatnim. D_B(E_C(E_D(v, R₁)))
10. C overi a smaze elektronicky podpis volice B, desifruje vsechny prijate zpravy svym tajnym klicem, overi pritomnost sveho hlasu, vsechny zpravy elektronicky podepise a zasle vsem ostatnim. D_C(E_D(v, R₁))
11. D overi a smaze elektronicky podpis volice C, desifruje vsechny prijate zpravy svym tajnym klicem, overi pritomnost sveho hlasu, vsechny zpravy elektronicky podepise a zasle vsem ostatnim. D_D(v, R₁)
12. Vsichni verifikuji a odstrani elektronicky podpis volice D a overi, ze jejich hlas je stale pritomen.
13. Kazdy muze sam spocitat vysledky voleb.
    

Protokol zabranuje tomu, aby libovolna ze zucastnenych stran neopravnene manipulovala s rozhodnutini ostatnich volicu, rovnez anonymita vsech volicu je zajistena.

Slabinou protokolu je znacna komplikovanost, navic volic D ma vysledky voleb k dispozici driv nez ostatni.

Bezpecne spolupocitani
(secure multiparty computation)

Pocitani prumerne hodnoty

1. A pricte ke sve hodnote tajne nahodne cislo, vysledek zasifruje verejnym klicem ucastnika B a preda vysledek B.
2. B desifruje zpravu, pricte svoji hodnotu, zasifruje a posle dalsimu ucastniku.
3. Posledni z ucastniku desifruje prijatou zpravu, prida svoji hodnotu, vysledek zasle A.
4. A po desifrovani odecte sve nahodne cislo, spocita vysledek a zverejni jej.

Protokol nezabrani ucastniku A podvadet, ani nezajistuje, aby ostatni zadali spravne hodnoty.

Porovnavani cisel

1. A nahodne zvoli velke cislo x zasifuje je verejnym klicem entity B a zasle:
   c - i = E(K_B, x) - i

2. B spocita techto 100 cisel: (u = 1..100)
   y_u = D(K_B, c - i + u) vybere nahodne prvocislo p o malo mensi nez x a spocita vsechna
   z_u = (y_u mod p)

3. B overi, ze pro vsechna u ruzne od v plati: |z_u - z_v| > 1
   a pro vsechna u plati: 0 < z_u < p - 1
   V pripade neuspechu opakuje predchozi bod.

4. B zasle A nasledujici sekvenci:
   z₁, z₁, ..., z_j, z_j+1+1, z_j+2+1, ..., z₁₀₀+1, p

5. A zjisti, zda i-ty prvek posloupnosti je kongruentni s x mod p. Tehdy a jen tehdy je i mensi nebo rovno j. A oznami vysledek.

Vadou protokolu je fakt, ze v poslednim kroku muze A zastavit vypocet, nebo podvadet. Resenim paralelni provadeni protokolu obema stranami v kombinaci s vhodnym protokolem pro vymenu zprav.

Podpisy naslepo (blind signatures)

1. A nahodne zvoli k mezi 1 a n. Entite B zasle: t = mk^e mod n

2. B prijatou zpravu podepise a zasle zpet: t^d = (mk^e)^d mod n

3. A odkryje puvodni zpravu:
   s = t^d/k mod n = m^d mod n

cislu k rikame oslepujici faktor (blind faktor).

Protokol lze rozsirit tak, aby overujici neznal pouze cast zpravy. V kroku 1. posilame i zprav, ktere obsahuji promenne pole. V kroku 2. navic B pozada o oslepujici faktor i - 1 nahodne zvolenych zprav, ktere si tak muze prohlednout cele. Podepise zbyvajici zpravu a vrati ji. B tedy nezna obsah promenneho pole podepsane zpravy.

Elektronicke platby (digital cash)

1. Zakaznik A pripravi 100 anonymnich prikazu k platbe na stejnou castku. Kazdy z prikazu vypada nasledovne:

   Mnozstvi:	Kc 1,-
   Jednozn. retezec:	X
   Identifikacni retezce:	I1 = (I1L, I1R) I2 = (I2L, I2R) ... I100 = (I100L, I100R)

   Kazdy prikaz obsahuje 100 ruznych paru identifikacnich retezcu, kazdy vznikly z retezce obsahujiciho uplnou identifikaci zakaznika vhodnym algoritmem pro secrets splitting. Napr. kazdy par muze byt tvoren parem paketu podobne jako v protokolu pro bit commitment tak, aby se dalo kontrolovat rozkryti paketu. Zname-li obe poloviny, muzeme sestavit puvodni retezec.

2. A "zaslepi" vsechny prikazy protokolem pro podpisy naslepo a odesle je do banky B.
3. B pozada A o "odslepeni" nahodne zvolenych 99 prikazu a rozkryti vsech identifikacnich retezcu.
4. Je-li vse v poradku, banka B podpisem potvrdi zbyly prikaz a vrati jej A.
5. A "odslepi" potvrzeny prikaz a preda jej obchodnikovi.
6. Obchodnik overi podpis banky a tim legitimnost prikazu.
7. Obchodnik pozada A nahodne o rozkryti jedne poloviny kazdeho paru identifikacnich retezcu.
8. A splni pozadavek.
9. B overi svuj podpis a zjisti, zda jiz neprijala prikaz se stejnym Jednozn. retezcem. Pokud je vse v poradku, vyplati B penize a prikaz archivuje.
10. Pokud prikaz se stejnym Jednozn. retezcem jiz banka prijala provede zkoumani rozkrytych identifikacnich retezcu. Jsou-li v obou pripadech stejne, podvadi obchodnik, jinak podvadi A.

Protokol zajistuje, ze obchodnik ani A nemohou podvadet. Musi vsak verit bance, ze s jejich ucty naklada korektne. Na druhou stranu, pokud se oba chovaji korektne, banka nema k dispozici zadnou informaci o tom, jak nakladaji se svymi financnimi prostredky.