Kryptografické protokoly

Tonda Beneš

Ochrana informace – jaro 2011

Kryptografické protokoly použijeme-li p i tvorb systému k ešení n jakého problému odpovídající protokol, sta í pouze ov it korektnost implementace vzhledem k tomuto protokolu 1. arbitrované protokoly - arbitrem rozumíme neutrální t etí stranu, zajiš ující férovost, nevýhodou použití arbitra jsou zvýšené náklady na provoz, problémy s dostupností, asové prodlevy, potíže s d ryhodností a výkonem 2. rozhodované (adjudicated) protokoly - rozhod í (adjudicator) je t etí strana, která je schopna rozhodnout, zda operace byla vykonána férov , p ípadn kdo z astník porušuje pravidla, t etí strana je tedy používána pouze p i sporu 3. samozabezpe ovací (self-enforcing) protokoly - samotný protokol zajiš uje vzájemnou ochranu ú astník

Digitální podpisy musí být nefalšovatelné, autentické, nem nitelné, “nerecyklovatelné”, ov itelné

Protokol pro symetrické systémy Nech odesílatel S zasílá p íjemci R zprávu M. 1. S zašle arbitrovi A zprávu E(M, KS) 2. Arbiter verifikuje odesílatele a p íjemci R zašle E((M, S, E(M, KS)), KR) 3. íjemce uschová M a E(M, KS) pro ú ely p ípadného dokazování p ijetí v p ípad , že nepožadujeme utajení p enášených dat, vysta íme s použitím MAC namísto šifrování na obranu proti opakovanému použití došlé zprávy lze použít vhodnou asovou známku, proti sestavování nových zpráv z ástí d íve došlých poslouží asová známka v každém šifrovaném bloku.

Protokol pro asymetrické systémy velice jednoduché, provede se

D M , KS dnes vzhledem k výkonu asymetrických šifer probíhá výpo et:

Materiál slouží výhradn jako pom cka pro absolvování p ednášky Ochrana Informací II na MFF UK V Praze. Není ur en k samostudiu problematiky. Jeho obsah se nemusí shodovat s rozsahem látky p ednášené v konkrétním semestru

1 / 16

Tonda Beneš


Sign

1

M

KS

takto vzniká tzv. odd lený (detached) podpis, obvykle je tento podpis p ipojen k vlastním podepisovaný dat m ov ení podpisu: ?

M'

M

1 KS K P

kde M‘ je p ijatá zpráva v praxi je ovšem t eba zajistit fixaci aktu podpisu v ase, aby bylo možno zp tn ov it platnost podpisu vzhledem k platnosti certifikátu p íslušného ve ejného klí e. To se eší asovými razítky: uvnit podepisovaných dat (nejd íve) vn podpisu (nejpozd ji)


2 / 16

Tonda Beneš


Poker Nech A hraje s B, A rozdává 1. A vezme karty, náhodn je se adí a zašifruje svým klí em, výsledek zašle B 2. B vybere m balí zašle zp t.

, zašifruje je svým klí em a spole

s dalšími m balí ky

3. A dešifruje všechny zašifrované balí ky. M z nich je dosud zašifrováno KB , ty zašle zp t B. 4. B dešifruje p ijaté balí ky 5. oba hrá i mají k dispozici své karty protokol je snadno rozši itelný pro v tší po et hrá , d kaz korektnosti hry se provádí zve ejn ním utajovaných skute ností tak, aby každý z hrá mohl provést opakování celé hry pro úsp šné zvládnutí kroku 3. je nutné, aby šifra komutovala popsanou implementaci pomocí symetrických systém lze velmi snadno p evést na systémy asymetrické protokol má praktické využití:

distribuce šifrovacích klí - n kdy je žádoucí, aby ani klí -server neznal uživatel v tajný klí . Server tedy vytvo í množství balí s klí i, žadatel si jeden vybere a postupem shodným s edchozím protokolem získá ukrytý klí .

asové známky nejjednodušší metodou je zasílat kopie zpráv d ryhodnému arbitrovi, problémy s množstvím uchovávaných dat lze vy ešit použitím hašovacích funkcí

Spojované (linked) známky - aby odesílatel (adresát) spole

s arbitrem nemohli podvád t


3 / 16

Tonda Beneš


1. Odesílatel S zašle arbitrovi A hashkód zprávy Hn. 2. A vrátí odesílateli

Tn

S K n, S , Hn , Tmn ; IDn 1 , Hn 1 , Tn 1 , H IDn 1 , Hn 1 , Tn

1

kde n je po adí zprávy, Tmn as podpisu zprávy, Idn-1 … jsou informace o edešlé zpráv , kterou arbitr vy izoval 3. po vy ízení následující zprávy arbitr zašle odesílateli identifikaci následujícího odesílatele Chce-li n kdo ov it asovou známku zprávy, kontaktuje odesílatele Idn-1 a Idn+1 a pomocí nich ov it platnost Tn. Pro zvýšení bezpe nosti je možné p ipojit informace o více p edchozích zprávách a držet seznam stejného po tu následujících odesílatel Další možností je tento protokol: 1. Hn užijeme jako vstup vhodného generátoru náhodných ísel, m nejbližších výsledk bereme jako identifikace uživatel V1, …,Vm 2. všem Vi zašle S hashkód Hn 3. Vi p ipojí informaci o asu, celý balí ek elektronicky podepíše a vrátí S 4. S uschová všechny odpov di jakožto asovou známku použití generátoru náhodných ísel v 1. kroku zajiš uje, že S nem že podvád t, neb neví p edem, kdo bude jeho zprávu podepisovat, navíc okruh verifikátor se bude pokaždé m nit

Fixace bitu (Bit commitment) ob as je pot eba mít možnost v budoucnu protistran dokázat znalost jisté informace bez jejího p ed asného vyzrazení nech strana A dokazuje stran B znalost skute nosti b 1. B zašle entit A náhodný et zec R 2. A spojí R se svojí informací celou tuto zprávu zašifruje náhodný klí em K a výsledek zašle B

E K, R b Materiál slouží výhradn jako pom cka pro absolvování p ednášky Ochrana Informací II na MFF UK V Praze. Není ur en k samostudiu problematiky. Jeho obsah se nemusí shodovat s rozsahem látky p ednášené v konkrétním semestru

4 / 16

Tonda Beneš


3. i pozd jším ov ování A zašle B klí K, B dešifruje p ijatou zprávu, ov í ítomnost R a p ezkoumá b s použitím one-way funkcí se m žeme omezit pouze na jednosm rnou komunikaci 1. A vygeneruje dva náhodné et zce R1 a R2 2. A vytvo í zprávu obsahující R1 , R2 a b, spo ítá hashkód této zprávy a B zašle

H R1 R2 b , R1 3. v rámci dokazování znalosti b zašle A p vodní zprávu

R1 R2 b 4. B spo ítá hashkód a porovná R1

kazy s nulovou informací (zero-knowledge proofs) dokazovatel (prover) nesmí podvád t, pokud d kaz nezná, jeho šance p esv it ov ovatele je mizivá ov ovatel rovn ž nesmí podvád t, o samotném d kazu smí zjistit pouze to, že jej dokazovatel zná. Zvlášt nesmí být schopen celý d kaz rekonstruovat a sám provést. ov ovatel se nesmí dozv t nic, co by nebyl schopen zjistit bez pomoci dokazovatele. není-li spln na poslední podmínka, mluvíme o kazech s minimálním vyzrazením (minimum-disclosure proofs) jeden z možných d kaz založen na problematice Hamiltonovských kružnic v grafu 1. Nech A zná Hamiltonovskou kružnici v grafu G 2. A provede náhodnou permutaci G. P vodní graf a vzniklý H jsou izomorfní. 3. Kopie grafu H je zaslán entit B 4. Ove ovatel B položí dokazovateli A jednu z následujících otázek: a)dokázat, že G a H jsou izomorfní b)ukázat Hamiltonovskou kružnici v grafu H 5. opakováním krok 1. až 4. lze docílit pot ebné jistoty


5 / 16

Tonda Beneš


Neur itý p enos (Oblivious transfer) protokol umož uje, aby si adresát vybral z n kolika nabízených možností aniž by odesílatel p edem znal jeho volbu, možné dopln ní o následnou vzájemnou kontrolu A vygeneruje dva páry public-key klí , oba ve ejné klí e zašle B B vytvo í klí K pro symetrický algoritmus, tento klí zašifruje jedním z p ijatých klí a výsledek vrátí A A dešifruje p ijatou zprávu ob ma tajnými klí i, ímž získá K1 a K2 Klí em K1 zašifruje A jednu z posílaných zpráv, klí em K2 druhou a oba výsledky zašle B. B se pokusí dešifrovat p ijaté zprávy, p emž v jednom p ípad získá smysluplný výsledek ípadné ov ení se provede tak, že A zve ejní své tajné klí e. Protokol sám o sob lze používat k distribuci šifrovacích klí , p ípadn jako obdobu házení korunou. V tší význam má jako sou ást následujícího protokolu.

Podepisování kontrakt (Contract signing) V každém okamžiku musí být ob smluvní strany vázány stejn moc nejjednodušším ešením je arbitrovaný protokol, kde ob strany p edají centrální autorit své podepsané kopie a tato t etí strana zajistí vým nu po obdržení obou kopií daleko lepší je následující distribuovaný protokol: 1. A i B náhodn vygenerují 200 konven ních klí , které rozd lí do dvouprvkových množin 2. A i B vytvo í 100 pár zpráv Ln a Rn, zhruba ve tvaru “Toto je levá ást n-tého podpisu smlouvy ”…, každá ze zpráv navíc obsahuje polovinu elektronického popisu smlouvy, timestamp atd. Kontrakt považujeme za podepsaný druhou stranou, pokud se m žeme prokázat ob ma polovinami n kterého z podpis . 3. A i B zašifrují i-tý pár zpráv i-tým párem klí (“levou” zprávu jedním, “pravou” druhým z klí ) 4. ob strany si navzájem zašlou páry zašifrovaných zpráv (200 zpráv každý) 5. použitím protokolu pro Oblivious transfer si A a B navzájem zašlou všechny šifrovací klí e - druhá strana má tedy z každého páru jeden (který ?) klí


6 / 16

Tonda Beneš


6. A i B provedou dešifrování t ch zpráv, ke kterým mají k dispozici odpovídající klí 7. A zašle B první bit všech 200 konven ních klí , obdobn B 8. edchozí krok opakujeme dokud nejsou p eneseny všechny bity klí 9. ob smluvní strany mohou dešifrovat všechny zprávy -> kontrakt je podepsán Pokud by se n která ze stran pokusila o podvod v kroku 4. nebo 5., bude podvod odhalen v kroku 6. Podvod v kroku 7. bude s velkou pravd podobností objeven okamžit . Ukon í-li jeden z ú astník protokol p ed zasláním všech bit klí , mají oba stejnou šanci dopo ítat n který z klí a získat elektronický podpis druhého. Problémem je, má-li n kdo z podepisujících výrazn v tší výpo etní kapacitu, v protokolu není zlom, ve kterém by se výrazn zm nila míra vázanosti ú astník .

Elektronická potvrzovaná pošta (digital certified mail) chceme, aby adresát mohl p íst naši zprávu až poté, co získáme potvrzení o tom, že ji obdržel (elektronický doporu ený dopis) 1. A zašifruje posílanou zprávu náhodn zvoleným konven ním klí em K 2. A vytvo í 100 pár konven ních klí - první klí každého páru je generován náhodn , druhý je XOR prvního klí e a klí e K 3. A zašifruje pomocnou zprávu každým ze 100 pár t chto klí (200 šifer) 4. všechny výsledné páry šifer zašle B 5. B vygeneruje 100 pár náhodných konven ních klí 6. B vytvo í 100 pár zpráv tvaru “Toto je levá ást mého potvrzení íslo n”. Op t potvrzení o p jetí je platné, pokud se prot jší strana m že prokázat ob ma polovinami jednoho z exemplá potvrzení. 7. B zašifruje i-tý pár zpráv i-tým párem klí (“levou” zprávu jedním, “pravou” druhým z klí ) 8. výsledné páry šifer zašle B prot jší stran 9. s použitím protokolu pro Oblivious transfer si A i B navzájem pošlou všech 100 pár svých klí - žádná ze stran neví, který klí z kterého páru prot jšek má k dispozici 10.A i B dešifrují všechny zprávy, ke kterým mají klí e a ov í jejich smysluplnost 11.ob strany si zašlou první bit všech 200 svých šifrovacích klí 12.p edchozí krok je opakován dokud nejsou p eneseny všechny bity


7 / 16

Tonda Beneš


13.A i B dešifrují zbývající ásti pár zpráv, které v p edchozích krocích obdrželi A má k dispozici potvrzení o p ijetí zprávy od B a B m že provést XOR libovolného páru klí a dešifrovat zprávu. Použití pomocné zprávy dává stran B možnost odhalení podvodu v kroku 10. V ostatních ohledech má protokol obdobné vlastnosti jako protokol pro podepisování kontrakt .

Bezpe né volby nikdo nesmí m nit volbu jiných každý hlas musí být zapo ítán je zjistitelné, kdo volil

volit smí pouze oprávn ní voli i každý smí hlasovat nejvýše jednou nikdo nesmí v t, kdo jak volil Poslední podmínka již není nutná.

Protokol se dv ma centrálními autoritami používá registra ní autoritu RA provád jící registraci voli která s ítá hlasovací lístky a zve ej uje výsledky voleb

a s ítací autority SA,

1. všichni voli i zašlou RA žádost o valida ní íslo 2. RA zašle každému voli i náhodn zvolené valida ní íslo L, zárove si ponechá seznam, kdo jaké íslo dostal 3. RA zašle seznam valida ních ísel SA 4. každý z voli si náhodn vybere svoje identifika ní íslo Id a SA zašle zprávu

L , Id , v kde v je volba 5. SA porovná L se seznamem valida ních ísel z kroku 3. odpovídající íslo škrtne a voli ovo Id p idá do seznamu asociovaného s voleným kandidátem 6. po skon ení voleb SA zve ejní výsledky voleb a seznamy identifika ních ísel spojené se jmény kandidát Každý z voli si m že ov it zda byl jeho hlas správn zapo ítán, RA zjistí ípadné falešné hlasy.


8 / 16

Tonda Beneš


SA však m že registrovat neoprávn né voli e, p ípadn n které voli e vícekrát. V ípad že budou RA a SA spolupracovat, hrozí nebezpe í porušení anonymity voli .

Protokol bez centrální autority voli i A, B, C, D se rozhodují ano i ne 1. všichni voli i zváží své rozhodnutí a (a) ke své volb p ipojí náhodný et zec (b) zašifrují výsledek kroku (a) ve ejným klí em voli e D (c) zašifrují výsledek kroku (b) ve ejným klí em voli e C (d) zašifrují výsledek kroku (c) ve ejným klí em voli e B (e) zašifrují výsledek kroku (d) ve ejným klí em voli e A (f) ipojí k výsledku kroku (e) nový náhodný et zec, jehož hodnotu uchovají, a celé to zašifrují ve ejným klí em voli e D (g) ipojí k výsledku kroku (f) nový náhodný et zec, jehož hodnotu uchovají, a celou zprávu zašifrují ve ejným klí em voli e C. (h) ipojí k výsledku kroku (g) nový náhodný et zec, jehož hodnotu uchovají, a celou zprávu zašifrují ve ejným klí em voli e B. (i) ipojí k výsledku kroku (h) nový náhodný et zec, jehož hodnotu uchovají, a celou zprávu zašifrují ve ejným klí em voli e A. vcelku tedy

E A R5 , E B R4 , EC R3 , E D R2 , E A E B E C E D v , R1 kde Ri je náhodný et zec a v voli ovo rozhodnutí 2. všichni voli i pošlou výsledky svých výpo voli i A 3. A dešifruje všechny p ijaté zprávy svým tajným klí em, otestuje p ítomnost svého hlasu a ze všech zpráv odd lí R5 . 4. A zamíchá po adím zpráv a všechny pošle voli i B. Zprávy mají tvar

E B R4 , EC R3 , E D R2 , E A E B E C E D v , R1 5. B dešifruje všechny p ijaté zprávy svým tajným klí em, otestuje p ítomnost svého hlasu a ze všech zpráv odd lí R4 . Materiál slouží výhradn jako pom cka pro absolvování p ednášky Ochrana Informací II na MFF UK V Praze. Není ur en k samostudiu problematiky. Jeho obsah se nemusí shodovat s rozsahem látky p ednášené v konkrétním semestru

9 / 16

Tonda Beneš


6. B zamíchá po adím zpráv a všechny pošle voli i C. Zprávy mají tvar

E C R3 , E D R2 , E A E B E C E D v , R1 C dešifruje všechny p ijaté zprávy svým tajným klí em, otestuje p ítomnost svého hlasu a ze všech zpráv odd lí R3 . 7. C zamíchá po adím zpráv a všechny pošle voli i D. Zprávy mají tvar

E D R2 , E A E B E C E D v , R1 D dešifruje všechny p ijaté zprávy svým tajným klí em, otestuje p ítomnost svého hlasu a ze všech zpráv odd lí R2 . 8. D zamíchá po adím zpráv a všechny pošle voli i A. Zprávy mají tvar

E A E B E C E D v , R1 A dešifruje všechny p ijaté zprávy svým tajným klí em, ov í p ítomnost svého hlasu, všechny zprávy elektronicky podepíše a zašle všem ostatním.

DA E B E C E D v , R1 9. B ov í a smaže elektronický podpis voli e A, dešifruje všechny p ijaté zprávy svým tajným klí em, ov í p ítomnost svého hlasu, všechny zprávy elektronicky podepíše a zašle všem ostatním.

DB EC E D v , R1 10.C ov í a smaže elektronický podpis voli e B, dešifruje všechny p ijaté zprávy svým tajným klí em, ov í p ítomnost svého hlasu, všechny zprávy elektronicky podepíše a zašle všem ostatním.

DC E D v , R1 11. D ov í a smaže elektronický podpis voli e C, dešifruje všechny p ijaté zprávy svým tajným klí em, ov í p ítomnost svého hlasu, všechny zprávy elektronicky podepíše a zašle všem ostatním.

DD v , R1 12. Všichni verifikují a odstraní elektronický podpis voli e D a ov í, že jejich hlas je stále p ítomen. 13. Každý m že sám spo ítat výsledky voleb. Materiál slouží výhradn jako pom cka pro absolvování p ednášky Ochrana Informací II na MFF UK V Praze. Není ur en k samostudiu problematiky. Jeho obsah se nemusí shodovat s rozsahem látky p ednášené v konkrétním semestru

10 / 16

Tonda Beneš


Protokol zabra uje tomu, aby libovolná ze zú astn ných stran neoprávn manipulovala s rozhodnutíni ostatních voli , rovn ž anonymita všech voli je zajišt na. Slabinou protokolu je zna ná komplikovanost, navíc voli D má výsledky voleb k dispozici d ív než ostatní.

Bezpe né spolupo ítání (secure multiparty computation) Protokol umož uje skupin uživatel po ítat funkci nad vstupními daty tak, aby všichni znali výsledek ale ne vstup ostatních.

Po ítání pr

rné hodnoty

1. A p te ke své hodnot tajné náhodné íslo, výsledek zašifruje ve ejným klí em astníka B a p edá výsledek B. 2. B dešifruje zprávu, p te svoji hodnotu, zašifruje a pošle dalšímu ú astníku. 3. Poslední z ú astník dešifruje p ijatou zprávu, p idá svoji hodnotu, výsledek zašle A. 4. A po dešifrování ode te své náhodné íslo, spo ítá výsledek a zve ejní jej. Protokol nezabrání ú astníku A podvád t, ani nezajiš uje, aby ostatní zadali správné hodnoty.

Porovnávání ísel Nech A má tajné íslo i a B má tajné íslo j. Nech i a j jsou celá ísla mezi 1 a 100 1. A náhodn zvolí velké íslo x zašifuje je ve ejným klí em entity B a zašle:

c i

E KB, x

i

2. B spo ítá t chto 100 ísel:

yu

D K B , c i u , 1 u 100

vybere náhodn prvo íslo p o málo menší než x a spo ítá všechna

zu

yu mod p , 1 u 100


11 / 16

Tonda Beneš


3. B ov í, že pro všechna u

v:

zu

zv

2

0 zu p a pro všechna u V p ípad neúsp chu opakuje p edchozí bod. 4. B zašle A následující sekvenci:

z1 , z 2 ,..., z j , z j

1

1, z j

2

1

1,..., z100 1, p

5. A zjistí, zda i-tý prvek posloupnosti je kongruentní s x mod p. Tehdy a jen tehdy je i j. A oznámí výsledek. Vadou protokolu je fakt, že v posledním kroku m že A zastavit výpo et, nebo podvád t. ešením paralelní provád ní protokolu ob ma stranami v kombinaci s vhodným protokolem pro vým nu zpráv.

Podpisy naslepo (blind signatures) ob as pot ebujem ov it dokument, aniž by ov ující znal jeho obsah Možným ešením je následující protokol. Nech B má šifrovací klí e, dešifrovací d. S A sdílejí modul n. A chce od B ov it dokument m. 1. A náhodn zvolí k mezi 1 a n. Entit B zašle:

t

m( k ) e

mod n

2. B p ijatou zprávu podepíše a zašle zp t:

td

m(k )e

d

mod n

3. A odkryje p vodní zprávu:

s

t d k mod n

md mod n

íslu k íkáme oslepující faktor (blind faktor). Protokol lze rozší it tak, aby ov ující neznal pouze ást zprávy. V kroku 1. posíláme i zpráv, které obsahují prom nné pole. V kroku 2. navíc B požádá o oslepující faktor i - 1 náhodn zvolených zpráv, které si tak m že prohlédnout celé. Materiál slouží výhradn jako pom cka pro absolvování p ednášky Ochrana Informací II na MFF UK V Praze. Není ur en k samostudiu problematiky. Jeho obsah se nemusí shodovat s rozsahem látky p ednášené v konkrétním semestru

12 / 16

Tonda Beneš


Podepíše zbývající zprávu a vrátí ji. B tedy nezná obsah prom nného pole podepsané zprávy.

Elektronické platby (digital cash) problém kreditních karet spo ívá v sledovatelnosti toku pen z. Hledáme protokol pro tvorbu autentizovaných ale nesledovatelných zpráv. 1. Zákazník A p ipraví 100 anonymních p íkaz k platb na stejnou ástku. Každý z p íkaz vypadá následovn : Množství: Jednozn. et zec: Identifika ní et zce:

1,X I 1 L , I 1R I2

I2 L , I2R ...

I100

I100 L , I100 R

Každý p íkaz obsahuje 100 r zných pár identifika ních et zc , každý vzniklý z et zce obsahujícího úplnou identifikaci zákazníka vhodným algoritmem pro secrets splitting. Nap . každý pár m že být tvo en párem paket podobn jako v protokolu pro bit commitment tak, aby se dalo kontrolovat rozkrytí paketu. Známeli ob poloviny, m žeme sestavit p vodní et zec. 2. A “zaslepí” všechny p íkazy protokolem pro podpisy naslepo a odešle je do banky B. 3. B požádá A o “odslepení” náhodn zvolených 99 p íkaz a rozkrytí všech identifika ních et zc 4. Je-li vše v po ádku, banka B podpisem potvrdí zbylý p íkaz a vrátí jej A. 5. A “odslepí” potvrzený p íkaz a p edá jej obchodníkovi. 6. Obchodník ov í podpis banky a tím legitimnost p íkazu. 7. Obchodník požádá A náhodn o rozkrytí jedné poloviny každého páru identifika ních et zc . + 8. A splní požadavek. Materiál slouží výhradn jako pom cka pro absolvování p ednášky Ochrana Informací II na MFF UK V Praze. Není ur en k samostudiu problematiky. Jeho obsah se nemusí shodovat s rozsahem látky p ednášené v konkrétním semestru

13 / 16

Tonda Beneš


9. B ov í sv j podpis a zjistí, zda již nep ijala p íkaz se stejným Jednozn. et zcem. Pokud je vše v po ádku, vyplatí B peníze a p íkaz archivuje. 10.Pokud p íkaz se stejným Jednozn. et zcem již banka p ijala provede zkoumání rozkrytých identifika ních et zc . Jsou-li v obou p ípadech stejný, podvádí obchodník, jinak podvádí A. Protokol zajiš uje, že obchodník ani A nemohou podvád t. Musí však v it bance, že s jejich ú ty nakládá korektn . Na druhou stranu pokud se oba chovají korektn , banka nemá k dispozici žádnou informaci o tom, jak nakládají se svými finan ními prost edky.

Prahová schémata (treshold schemes) protokol, k jehož úsp šnému provedení musí spojit síly více (nap . t) ú astník t nazýváme prahem (threshold value) pokud t – 1 a mén ú astník nem že získat ani áste ný výsledek, mluvíme o perfektním schématu

Jednoduché autentiza ní schéma (2, 2) nejprve „normální“ algoritmus: odesílatel a p íjemce sdílejí tajný klí (a, b) autentiza ní kód zprávy m získáme:

c

am b mod p

íjemce p ijme m’ , spo ítá

c

am

b mod p

a ov í, zda c = c’

totéž jako prahové schéma (2, 2) a nahradíme dv ma stíny (shadow) s1, s2 tak, že s1= a – s2 mod p, náhodn zvoleno tak, že 0 s2 p , obdobn b nahradíme dvojicí s’1, s’2 zatímco p íjemce si ponechá dvojici a, b, odesíletelé dostanou dvojici s1, s’1 resp. s2, s’2. na vytvo ení autentiza ního kódu c nyní musí spolupracovat:

c1

s1m s1 mod p

resp.

c2

s2 m s2 mod p


14 / 16

Tonda Beneš


íjemce se te ob hodnoty (mod p) a dále je protokol stejný, jako p edchozí. uvedené schéma slouží pouze jako ilustra ní p ípad, není bezpe né p i vícenásobném použití

Sun a Shieh (t, n) prahové schéma vedoucí zve ejní velké prvo íslo p a generátor t lesa T mod p každý ú astník (shadowholder) Hi náhodn zvolí tajný stín si a spo ítá sv j ve ejný parametr

pi

si

mod p

vedoucí následn zvolí (a uchová v tajnosti) náhodný polynom stupn f0(X) stupn t – 1 nad T takový, že jeho konstantní len je roven sdílené informaci I0 a náhodný prvek k0 lesa T. Na záv r publikuje parametr

R0

k0

mod p

a hodnoty

C0i

f0 i

pi

k0

mod p

Tím je schéma hotovo. Pokud dojde k R-té zm sdílené informace, vedoucí zvolí nový náhodný prvek kR lesa T a nový polynom fR(X) a znovu vypo ítá parametr RR a hodnoty CRi. nech ú astníci H1 až Ht cht jí sestavit informaci IR každý z nich spo ítá sv j opravdový stín (true shadow)

fR i

C Ri

RR

si

mod p

a zve ejní jej. tím získáme t bod (i, fR(i)) a Lagrangeovou interpolací m žeme spo ítat p vodní polynom fR(X) vodní Sun a Shieh schéma navíc obsahuje mechanismus pro detekci úto ník , kte í by se pokoušeli podsouvat vadný opravdový stín. Tento mechanismus jsme pro jednoduchost vypustili, ostatn stejn za jistých okolností zp sobuje snížení prahu schématu. Materiál slouží výhradn jako pom cka pro absolvování p ednášky Ochrana Informací II na MFF UK V Praze. Není ur en k samostudiu problematiky. Jeho obsah se nemusí shodovat s rozsahem látky p ednášené v konkrétním semestru

15 / 16

Tonda Beneš


11 dob e mín ných rad 1) Jasn definovat p edpoklady o bezpe nosti 2) Osv tlit ú el použité kryptografie: utajení, autentizace, binding, náhodná ísla – nezam ovat použití kryptografie s bezpe ností i utajením 3) Postarat se o vzájemnou vazbu a po adí jednotlivých zpráv 4) Je-li identita principála (pojmenovatelná entita = subjekt) podstatná pro interpretaci obsahu zprávy, musí být explicitn uvedena 5) Použijte dostatek redundance 6) Protokol by nem l využívat neov ené p edpoklady o vlastnostech kryptograf. algoritm , na nichž je založen 7) Je-li podpis po ítán na základ zašifrovaných dat, nem že sloužit k ov ení, že druhá strana zná jejich obsah 8) Nev te v bezpe nost tajných informací druhých 9) Když podepisujete nebo dešifrujete data, pozor aby vás oponent nemohl používat jako orákulum (n kdo kdo zná odpov di) 10) Nemíchat dešifrování s podpisem 11) Zajist te rozlišení r zných instancí téhož protokolu Princip explicitnosti Robustnost bezpe nosti spo ívá v explicitnosti - jména, typy, asové známky - v návrhu po áte ních p edpoklad , cíl , seznamu vlastností využitelných pro útok


16 / 16

Kryptografické protokoly

Recommend Documents