Kryptograficke protokoly
pouzijeme-li pri tvorbe systemu k reseni
nejakeho problemu odpovidajici
protokol, staci pouze overit korektnost
implementace vzhledem k tomuto protokolu
- 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
- 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
- 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.
- S zasle arbitrovi A zpravu E(M,
KS)
- Arbiter verifikuje odesilatele a prijemci
R zasle E((M, S, E(M, KS)), KR)
- 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
- A vezme karty, nahodne je seradi
a zasifruje svym klicem, vysledek
zasle B
- B vybere m balicku, zasifruje
je svym klicem a spolecne s
dalsimi m balicky zasle
zpet.
- A desifruje vsechny zasifrovane
balicky. M z nich je dosud zasifrovano
KB , ty zasle zpet B.
- B desifruje prijate balicky
- 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
- Odesilatel S zasle arbitrovi A hashkod
zpravy Hn.
- 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
- 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:
- Hn uzijeme jako vstup vhodneho generatoru
nahodnych cisel, m nejblizsich
vysledku bereme jako identifikace uzivatelu
V1, ...,Vm
- vsem Vi zasle S hashkod Hn
- Vi pripoji informaci o casu, cely
balicek elektronicky podepise a vrati
S
- 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
- B zasle entite A nahodny
retezec R
- A spoji R se svoji informaci
celou tuto zpravu zasifruje nahodny
klicem K a vysledek zasle B
E(K, R||b)
- 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
- A vygeneruje dva nahodne retezce
R1 a R2
- A vytvori zpravu obsahujici
R1 , R2 a b, spocita
hashkod teto zpravy a B zasle
H(R1||R2||b), R1
- v ramci dokazovani znalosti b
zasle A puvodni zpravu
(R1||R2||b)
- B spocita hashkod a porovna
R1
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
- Necht A zna Hamiltonovskou kruznici
v grafu G
- A provede nahodnou permutaci G. Puvodni
graf a vznikly H jsou izomorfni.
- Kopie grafu H je zaslan entite B
- Overovatel B polozi dokazovateli
A jednu z nasledujicich otazek:
- dokazat, ze G a H jsou izomorfni
- ukazat Hamiltonovskou kruznici v grafu H
- 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:
- A i B nahodne vygeneruji
200 konvencnich klicu, ktere
rozdeli do dvouprvkovych mnozin
- 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.
- A i B zasifruji i-ty
par zprav i-tym parem klicu
("levou" zpravu jednim, "pravou"
druhym z klicu)
- obe strany si navzajem zaslou pary
zasifrovanych zprav (200 zprav kazdy)
- pouzitim protokolu pro Oblivious transfer si A
a B navzajem zaslou vsechny sifrovaci
klice - druha strana ma tedy z kazdeho
paru jeden (ktery ?) klic
- A i B provedou desifrovani
tech zprav, ke kterym maji k dispozici
odpovidajici klic
- A zasle B prvni bit vsech 200
konvencnich klicu, obdobne
B
- predchozi krok opakujeme dokud nejsou preneseny
vsechny bity klicu
- 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)
- A zasifruje posilanou zpravu nahodne
zvolenym konvencnim klicem
K
- A vytvori 100 paru konvencnich
klicu - prvni klic kazdeho
paru je generovan nahodne, druhy
je XOR prvniho klice a klice
K
- A zasifruje pomocnou zpravu kazdym
ze 100 paru techto klicu
(200 sifer)
- vsechny vysledne pary sifer
zasle B
- B vygeneruje 100 paru nahodnych
konvencnich klicu
- 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.
- B zasifruje i-ty par zprav
i-tym parem klicu ("levou"
zpravu jednim, "pravou" druhym
z klicu)
- vysledne pary sifer zasle B
protejsi strane
- 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
- A i B desifruji vsechny zpravy,
ke kterym maji klice a overi
jejich smysluplnost
- obe strany si zaslou prvni bit vsech
200 svych sifrovacich klicu
- predchozi krok je opakovan dokud nejsou
preeseny vsechny bity
- 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
- 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
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
- vsichni volici zaslou RA zadost
o validacni cislo
- RA zasle kazdemu volici nahodne
zvolene validacni cislo L,
zaroven si ponecha seznam, kdo jake
cislo dostal
- RA zasle seznam validacnich cisel
SA
- kazdy z volicu si nahodne
vybere svoje identifikacni cislo Id
a SA zasle zpravu
(L, Id, v)
kde v je volba
- SA porovna L se seznamem validacnich
cisel z kroku 3. odpovidajici
cislo skrtne a volicovo Id prida
do seznamu asociovaneho s volenym kandidatem
- 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
- vsichni volici zvazi sve
rozhodnuti a
- ke sve volbe pripoji nahodny
retezec
- zasifruji vysledek predchoziho kroku verejnym
klicem volice D
- zasifruji vysledek predchoziho kroku verejnym
klicem volice C
- zasifruji vysledek predchoziho kroku verejnym
klicem volice B
- zasifruji vysledek predchoziho kroku verejnym
klicem volice A
- pripoji k vysledku predchoziho kroku novy
nahodny retezec, jehoz hodnotu
uchovaji, a cele to zasifruji verejnym
klicem volice D
- pripoji k vysledku predchoziho kroku novy
nahodny retezec, jehoz hodnotu
uchovaji, a celou zpravu zasifruji verejnym
klicem volice C.
- pripoji k vysledku predchoziho kroku novy
nahodny retezec, jehoz hodnotu
uchovaji, a celou zpravu zasifruji verejnym
klicem volice B.
- 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
- vsichni volici poslou vysledky svych
vypoctu volici A
- A desifruje vsechny prijate
zpravy svym tajnym klicem,
otestuje pritomnost sveho hlasu a ze vsech
zprav oddeli R5.
- A zamicha poradim zprav
a vsechny posle volici B. Zpravy
maji tvar
EB(R4, EC(R3, ED(R2, EA(EB(EC(ED(v, R1)))))))
- B desifruje vsechny prijate
zpravy svym tajnym klicem,
otestuje pritomnost sveho hlasu a ze vsech
zprav oddeli R4.
- 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.
- 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.
- 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))))
- 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)))
- 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))
- 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)
- Vsichni verifikuji a odstrani elektronicky
podpis volice D a overi, ze
jejich hlas je stale pritomen.
- 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
- A pricte
ke sve hodnote tajne nahodne
cislo, vysledek zasifruje verejnym
klicem ucastnika B a
preda vysledek B.
- B desifruje zpravu,
pricte svoji hodnotu, zasifruje a posle
dalsimu ucastniku.
- Posledni z ucastniku
desifruje prijatou zpravu, prida
svoji hodnotu, vysledek zasle A.
- 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
- A nahodne
zvoli velke cislo x zasifuje
je verejnym klicem entity B
a zasle:
c - i = E(KB, x) - i
- B spocita
techto 100 cisel: (u = 1..100)
yu = D(KB, c - i + u)
vybere nahodne prvocislo p
o malo mensi nez x a spocita
vsechna
zu = (yu mod p)
- 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.
- B zasle A
nasledujici sekvenci:
z1, z1, ..., zj, zj+1+1, zj+2+1, ..., z100+1, p
- 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.
- A nahodne zvoli k mezi 1 a n. Entite B zasle:
t = mke mod n
- B prijatou zpravu podepise a zasle zpet:
td = (mke)d mod n
- A odkryje puvodni zpravu:
s = td/k mod n = md 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.
- 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.
- A "zaslepi" vsechny prikazy
protokolem pro podpisy naslepo a odesle je do banky B.
- B pozada A o "odslepeni"
nahodne zvolenych 99 prikazu
a rozkryti vsech identifikacnich retezcu.
- Je-li vse v poradku, banka B podpisem
potvrdi zbyly prikaz a vrati jej A.
- A "odslepi" potvrzeny prikaz
a preda jej obchodnikovi.
- Obchodnik overi podpis banky a
tim legitimnost prikazu.
- Obchodnik pozada A nahodne
o rozkryti jedne poloviny kazdeho paru
identifikacnich retezcu.
- A splni pozadavek.
- 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.
- 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
zvedavcu ...