Kryptograficke protokoly

pouzijeme-li pri tvorbe systemu k reseni nejakeho problemu odpovidajici protokol, staci pouze overit korektnost implementace vzhledem k tomuto protokolu
  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

Necht odesilatel S zasila prijemci R zpravu M.
  1. S zasle arbitrovi A zpravu E(M, KS)
  2. Arbiter verifikuje odesilatele a prijemci R zasle E((M, S, E(M, KS)), KR)
  3. Prijemce uschova M a E(M, KS) 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

velice jednoduche, provede se
E(D(M, KS), KR)

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 KB , 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

- nekdy je zadouci, aby ani klic-server neznal uzivateluv tajny klic. Server tedy vytvori mnozstvi balicku s klici, zadatel si jeden vybere a postupem shodnym s predchozim protokolem ziska ukryty klic.

Casove znamky

nejjednodussi metodou je zasilat kopie zprav duveryhodnemu arbitrovi, problemy s mnozstvim uchovavanych dat lze vyresit pouzitim hasovacich funkci

Spojovane (linked) znamky

- aby odesilatel (adresat) spolecne s arbitrem nemohli podvadet
  1. Odesilatel S zasle arbitrovi A hashkod zpravy Hn.
  2. A vrati odesilateli
    Tn = Sk(n, s, Hn, Tmn; IDn-1, Hn-1, Tn-1; H(IDn-1, Hn-1, Tn-1))

    kde n je poradi zpravy, Tmn cas podpisu zpravy, Idn-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 Idn-1 a Idn+1 a pomoci nich overit platnost Tn.

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

Dalsi moznosti je tento protokol:

  1. Hn uzijeme jako vstup vhodneho generatoru nahodnych cisel, m nejblizsich vysledku bereme jako identifikace uzivatelu V1, ...,Vm
  2. vsem Vi zasle S hashkod Hn
  3. Vi 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)

obcas je potreba mit moznost v budoucnu protistrane dokazat znalost jiste informace bez jejiho predcasneho vyzrazeni

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 R1 a R2
  2. A vytvori zpravu obsahujici R1 , R2 a b, spocita hashkod teto zpravy a B zasle
    H(R1||R2||b), R1
  3. v ramci dokazovani znalosti b zasle A puvodni zpravu
    (R1||R2||b)
  4. B spocita hashkod a porovna R1

Dukazy s nulovou informaci (zero-knowledge proofs)

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

protokol umoznuje, aby si adresat vybral z nekolika nabizenych moznosti aniz by odesilatel predem znal jeho volbu, mozne doplneni o naslednou vzajemnou kontrolu

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 K1 a K2

Klicem K1 zasifruje A jednu z posilanych zprav, klicem K2 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)

V kazdem okamziku musi byt obe smluvni strany vazany stejne moc

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 Ln a Rn, 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
Pokud by se nektera ze stran pokusila o podvod v kroku 4. nebo 5., bude podvod odhalen v kroku 6. Podvod v kroku 7. bude s velkou pravdepodobnosti objeven okamzite. Ukonci-li jeden z ucastniku protokol pred zaslanim vsech bitu klicu, maji oba stejnou sanci dopocitat nektery z klicu a ziskat elektronicky podpis druheho.

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)

chceme, aby adresat mohl precist nasi zpravu az pote, co ziskame potvrzeni o tom, ze ji obdrzel (elektronicky doporuceny dopis)
  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.
Pouziti pomocne zpravy dava strane B moznost odhaleni podvodu v kroku 10.

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

Bezpecne volby

Posledni podminka jiz neni nutna.

Protokol se dvema centralnimi autoritami

pouziva registracni autoritu RA provadejici registraci volicu a scitaci autority SA, ktera scita hlasovaci listky a zverejnuje vysledky voleb
  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
Kazdy z volicu si muze overit zda byl jeho hlas spravne zapocitan, RA zjisti pripadne falesne hlasy.

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

volici A, B, C, D se rozhoduji ano ci ne
  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
    EA(R5, EB(R4, EC(R3, ED(R2, EA(EB(EC(ED(v, R1))))))))
    kde Ri 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 R5.
  4. A zamicha poradim zprav a vsechny posle volici B. Zpravy maji tvar
    EB(R4, EC(R3, ED(R2, EA(EB(EC(ED(v, R1)))))))
  5. B desifruje vsechny prijate zpravy svym tajnym klicem, otestuje pritomnost sveho hlasu a ze vsech zprav oddeli R4.
  6. B zamicha poradim zprav a vsechny posle volici C. Zpravy maji tvar
    EC(R3, ED(R2, EA(EB(EC(ED(v, R1))))))
    C desifruje vsechny prijate zpravy svym tajnym klicem, otestuje pritomnost sveho hlasu a ze vsech zprav oddeli R3.
  7. C zamicha poradim zprav a vsechny posle volici D. Zpravy maji tvar
    ED(R2, EA(EB(EC(ED(v, R1)))))
    D desifruje vsechny prijate zpravy svym tajnym klicem, otestuje pritomnost sveho hlasu a ze vsech zprav oddeli R2.
  8. D zamicha poradim zprav a vsechny posle volici A. Zpravy maji tvar
    EA(EB(EC(ED(v, R1))))
    A desifruje vsechny prijate zpravy svym tajnym klicem, overi pritomnost sveho hlasu, vsechny zpravy elektronicky podepise a zasle vsem ostatnim.
    DA(EB(EC(ED(v, R1))))
  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.
    DB(EC(ED(v, R1)))
  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.
    DC(ED(v, R1))
  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.
    DD(v, R1)
  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)

Protokol umoznuje skupine uzivatelu pocitat funkci nad vstupnimi daty tak, aby vsichni znali vysledek ale ne vstup ostatnich.

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

Necht A ma tajne cislo i a B ma tajne cislo j. Necht i a j jsou cela cisla mezi 1 a 100
  1. A nahodne zvoli velke cislo x zasifuje je verejnym klicem entity B a zasle:
    c - iE(KBx) - i

  2. B spocita techto 100 cisel: (u = 1..100)
    yuD(KBc - i + u)
    vybere nahodne prvocislo p o malo mensi nez x a spocita vsechna
    zu = (yu mod p)

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

  4. B zasle A nasledujici sekvenci:
    z1, z1, ..., zj, zj+1+1, zj+2+1, ..., z100+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)

obcas potrebujem overit dokument, aniz by overujici znal jeho obsah Moznym resenim je nasledujici protokol.
Necht B ma sifrovaci klic e, desifrovaci d. S A sdileji modul n. A chce od B overit dokument m.
  1. A nahodne zvoli k mezi 1 a n. Entite B zasle:
    tmke mod n

  2. B prijatou zpravu podepise a zasle zpet:
    td = (mke)d mod n

  3. A odkryje puvodni zpravu:
    std/k mod nmd 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)

problem kreditnich karet spociva v sledovatelnosti toku penez. Hledame protokol pro tvorbu autentizovanych ale nesledovatelnych zprav.
  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.


© Tonda Benes, 1995, 96
S prevodem tohoto dokumentu do HTML pomahal ©Dan Lukes, 1995, 96
Toto je revision 2.0, 28.2.96
Tuto stranku shledlo jiz <pocet navstevniku> zvedavcu ...