╚ßst 33 - CW 46/97

KryptografickΘ protokoly

V²znam slova protokol (krom∞ jinΘho) je obvykle popsßnφ zp∙sobu umφst∞nφ a uspo°ßdßnφ ·Φastnφk∙ n∞jakΘ mezinßrodnφ (diplomatickΘ) konference, a to vΦetn∞ po°adφ jednotliv²ch vystoupenφ, p°φpadn∞ dalÜφch nßle₧itostφ (obleΦenφ apod.). ObΦas jsou jednßnφ o protokolu takovΘto akce delÜφ ne₧ akce sama.

Kryptografick² protokol je pak algoritmus (p°esn∞ specifikovanß posloupnost operacφ a v²m∞ny dat), urΦen² pro komunikaci mezi r∙zn²mi stranami a vyu₧φvajφcφ kryptografickΘ transformace. KonkrΘtnφ kryptografick² protokol vychßzφ z po₧adavk∙ komunikujφcφch stran a p°i jeho dodr₧enφ by m∞lo b²t spln∞nφ po₧adavk∙ zajiÜt∞no.

Kryptografick² protokol specifikuje, jak²m zp∙sobem ka₧dß strana vysφlß, p°ijφmß a odpovφdß na zprßvy, a to vΦetn∞ chybn²ch nebo ilegßlnφch zprßv. Protokol m∙₧e rovn∞₧ specifikovat po₧adavky na definici prost°edφ, jako je nap°. nastavenφ knihovny ve°ejn²ch klφΦ∙.

Strana, kterß se °φdφ protokolem, bude ochrßn∞na proti specifikovan²m nebezpeΦφm i v tom p°φpad∞, ₧e ostatnφ strany se protokolem ne°φdφ. ┌Φelem protokolu je nap°φklad v²m∞na kryptografick²ch klφΦ∙ pro nßsledn² p°enos Üifrovan²ch dat, autentizace ·Φastnφk∙ protokolu, generovßnφ kryptografick²ch klφΦ∙ apod.

K jednoduch²m p°φklad∙m po₧adavk∙ komunikujφcφch stran pat°φ to, ₧e n∞kterΘ komunikujφcφ strany mohou chtφt sdφlet svΘ utajenΘ informace, aby dosßhly spoleΦnΘho cφle, nebo cht∞jφ spojit svΘ mo₧nosti, ani₧ by ₧ßdnß z komunikujφcφch stran seznßmila ostatnφ se svou informacφ, nebo jedna ze stran chce p°esv∞dΦit ostatnφ, ₧e je jφ znßmß n∞jakß tajnß informace, ani₧ by ji zve°ejnila atd.

NejjednoduÜÜφm p°φkladem kryptografickΘho protokolu je nap°. p°enos elektronickΘ poÜty, kdy je odesφlanß zprßva zaÜifrovßna ve°ejn²m klφΦem p°φjemce, a proto ji m∙₧e deÜifrovat pouze on. OvÜem p°φjemce nevφ, zda mu tuto zprßvu zasφlß p°φtel Φi nep°φtel, kter² se za n∞j vydßvß. Proto je vhodnΘ na nezaÜifrovanou zprßvu pou₧φt soukrom² klφΦ odesilatele a pak ve°ejn² klφΦ p°φjemce. Pak p°φjemce nßsledovn∞ deÜifruje zprßvu sv²m soukrom²m klφΦem a ve°ejn²m klφΦem odesilatele.

Spolehlivost tΘto metody je zalo₧ena na d∙v∞ryhodnosti sprßvce ve°ejn²ch klφΦ∙. TotΘ₧ platφ samoz°ejm∞ u urΦenφ p°φjemce (faleÜn² p°φjemce, kter² by zφskal p°φstup na server d∙v∞ryhodnΘ instituce a zam∞nil by ve°ejn² klφΦ sprßvnΘho p°φjemce sv²m ve°ejn²m klφΦem, by mohl Φφst zprßvy

urΦenΘ sprßvnΘmu p°φjemci).

Protokol typu stßle uzav°enΘ truhly

Protokol typu stßle uzav°enΘ truhly vypadß takto (za p°edpokladu, ₧e operace Üifrovßnφ a deÜifrovßnφ jsou pro vÜechny ·Φastnφky protokolu vzßjemn∞ zßm∞nnΘ a ·Φastnφci se mohou p°esv∞dΦit o svΘ identit∞): odesilatel zaÜifruje zprßvu sv²m klφΦem a odeÜle ji p°φjemci, p°φjemce totΘ₧ provede se zaÜifrovanou zprßvou se sv²m klφΦem a odeÜle odesilateli. Odesilatel deÜifruje tuto zprßvu a obdr₧φ svou p∙vodnφ zprßvu zaÜifrovanou klφΦem p°φjemce. Takto zaÜifrovanou zprßvu odeÜle p°φjemci, kter² ji nßsledn∞

deÜifruje sv²m klφΦem a obdr₧φ p∙vodnφ zprßvu odesilatele.

Hod mincφ po telefonu

DalÜφm jednoduch²m p°φkladem protokolu je tzv. hod mincφ po telefonu. Dvojice man₧el∙ se chce po telefonu domluvit, kam pojedou na prßzdniny -- zda k babiΦce do Ji₧nφch ╚ech nebo na zßjezd do èpan∞lska. Man₧el preferuje èpan∞lsko, man₧elka babiΦku. Dohodnou se, ₧e man₧elka provede nßhodn² v²b∞r tak, ₧e man₧el (odesilatel) odeÜle dv∞ zprßvy zaÜifrovanΘ pomocφ symetrickΘho Üifrovacφho systΘmu (jedna je "hlava" -- jede se do èpan∞lska a druhß "orel" -- jede se k babiΦce). Man₧elka (p°φjemce) si z nich jednu vybere a pokraΦuje stejn∞ jako v p°edchozφm protokolu. Na konci protokolu man₧elka p°eΦte otev°enou zprßvu -- padla hlava a oba

man₧elΘ si pro kontrolu po telefonu sd∞lφ svΘ tajnΘ klφΦe.

Zero-knowledge protocol

V∞nujme se nynφ protokolu s nulov²m rozÜφ°enφm informacφ (angl. zero-knowledge protocol), co₧ je dvoustrann² protokol; jedna strana se naz²vß dokazovatel, druhß prov∞°ovatel. Dokazovatel znß n∞jakou skuteΦnost a p°eje si p°esv∞dΦit pomocφ protokolu prov∞°ovatele o tΘto skuteΦnosti. Prov∞°ovatel se chce pomocφ protokolu p°esv∞dΦit o platnosti tΘto skuteΦnosti prßv∞ tehdy, kdy₧ je tato skuteΦnost pravdivß. P°esn∞ji, dokazovatel (jestli₧e jednß podle protokolu) bude schopen p°esv∞dΦit prov∞°ovatele o platnosti skuteΦnosti, pokud je tato skuteΦnost pravdivß, ale dokazovatel (dokonce i kdy₧ se pokusφ podvßd∞t) nebude mφt ₧ßdnou podstatnou Üanci v p°esv∞dΦenφ prov∞°ovatele o platnosti skuteΦnosti, pokud tato neplatφ. P°itom si dokazovatel nep°eje podat ₧ßdnou informaci o podstat∞ skuteΦnosti (nap°. d∙vody, proΦ skuteΦnost platφ).

Zßkladnφmi p°φklady tohoto protokolu jsou schopnost faktorizovat n∞jakΘ p°irozenΘ Φφslo Φi schopnost nalezenφ °eÜenφ n∞jakΘho matematickΘho problΘmu v polynomißlnφm Φase.

Obvykl²m jednoduch²m p°φkladem protokolu s nulov²m rozÜφ°enφm informacφ je tzv. jesky≥ka -- dokazovatel mß p°esv∞dΦit ov∞°ovatele, ₧e znß heslo k tajn²m dve°φm rozd∞lujφcφ kruhovitou jeskyni na pravou a levou Φßst, p°iΦem₧ vchod pro ob∞ Φßsti je spoleΦn². Protokol pak vypadß nßsledovn∞: Dokazovatel vejde do nßhodnΘ Φßsti jeskyn∞ tak, ₧e prov∞°ovatel, kter² stojφ mimo jeskyni nevidφ, do kterΘ Φßsti veÜel. Prov∞°ovatel pak vejde do vchodu jeskyn∞ a zavolß na dokazovatele stojφcφho ji₧ u uzav°en²ch dve°φ, kterou Φßstφ mß k n∞mu p°ijφt. Znß-li dokazovatel tajnΘ heslo, m∙₧e v₧dy sprßvn∞ vyjφt. Neznß-li ho ale, mß pouze 50% Üanci, ₧e veÜel do sprßvnΘ Φßsti a po dostateΦnΘm poΦtu opakovßnφ v²Üe uvedenΘho postupu prov∞°ovatel zjistφ, ₧e klamal. Navφc prov∞°ovatel nem∙₧e ubezpeΦit nikoho jinΘho ne₧ sebe, ₧e dokazovatel tajnΘ heslo znß.

Z praktick²ch verzφ protokolu s nulov²m rozÜφ°enφm informacφ se jednß o pou₧itφ p°i identifikaci (identifikaΦnφ a kreditnφ karty, poΦφtaΦovß hesla). Toti₧ dokazovatel dokß₧e, ₧e je pov∞°enß osoba, ani₧ by prov∞°ovateli (kter² m∙₧e hrßt faleÜn∞) sd∞lil svΘ heslo Φi jinak p°enechal

informaci, jak za sebe vystupovat.

Volby

Co nßs mo₧nß Φekß v p°φÜtφm roce, jsou p°edΦasnΘ volby. Jak² je ideßlnφ zp∙sob jejich realizace, aby byly bezpeΦnΘ a odpovφdaly po₧adavk∙m na n∞ kladen²m? Protokol tradiΦnφho volebnφho systΘmu je velmi jednoduch². Korektnost voleb je zajiÜt∞na tφm, ₧e ka₧d² voliΦ je p°i p°φchodu do volebnφ mφstnosti pozitivn∞ identifikovßn (na zßklad∞ obΦanskΘho pr∙kazu, resp. znalostφ Φlena volebnφ komise) a v pr∙b∞hu voleb je vytvß°en zßznam t∞ch voliΦ∙, kte°φ ji₧ odvolili. TajnΘ hlasovßnφ je zajiÜt∞no volebnφ plentou -- nikdo nem∙₧e vid∞t, jak kter² voliΦ volφ (a₧ na specißlnφ, zßkonem p°edem stanovenΘ p°φpady -- invalidΘ aj.).

Prov∞°itelnost v²sledku voleb by m∞la b²t zajiÜt∞na op∞tovn²m seΦtenφm volebnφch lφstk∙, kterΘ by m∞ly b²t do konce urΦitΘho obdobφ uschovßny a nep°φstupnΘ. Spojenφ mezi voliΦem a volebnφ obßlkou je ukonΦeno po vlo₧enφ obßlky do urny. Volebnφ obßlky jsou otvφrßny jako celek -- jedin²m spojenφm s voliΦem je tedy lokßlnφ volebnφ mφstnost a poΦet hlas∙, kterΘ byly na zßklad∞ p°φsluÜnΘ komise seΦteny.

Bohu₧el, je dob°e znßmo, ₧e se b∞hem existence tohoto protokolu vyskytly r∙znΘ typy podvod∙. Nap°φklad sd∞lenφ volebnφch komisφ p°i sΦφtßnφ neodpovφdala skuteΦnosti. Jinß, inteligentn∞jÜφ mo₧nost spoΦφvß v tom, ₧e volebnφ lφstky se poΦtem a jmΘny kandidßt∙ neliÜφ, zato ale jejich po°adφm. Lze tedy na zßklad∞ volebnφho lφstku identifikovat p°φsluÜnΘho voliΦe.

P°edpoklßdejme, ₧e se naÜe volby budou realizovat pomocφ poΦφtaΦovΘ sφt∞. Pak zde jako hlavnφ po₧adavky vystupujφ zßrove≥ po₧adavek legitimity a po₧adavek utajenφ, co₧ jsou zdßnliv∞ dva zcela nesourodΘ po₧adavky, proto₧e jak m∙₧e b²t zajiÜt∞no utajenφ, kdy₧ se voliΦ musφ prokßzat? PopiÜme ve zkratce dv∞ hlavnφ metody.

V metod∞ zaÜifrovßnφ volby voliΦ provede svou volbu ve°ejn∞, ale v zaÜifrovanΘm tvaru. JednotlivΘ volby pak nesmφ b²t deÜifrovatelnΘ, ale musφ b²t mo₧nΘ provΘst celkovΘ spoΦφtßnφ volebnφch hlas∙. Druhß mo₧nost je provΘst volby anonymn∞, ale spoleΦn∞ s d∙kazem oprßvn∞nφ volit, co₧ je informace obdr₧enß od volebnφ komise dop°edu, p°iΦem₧ nesmφ b²t mo₧nΘ rozpoznat z d∙kazu oprßvn∞nφ, o jakΘho voliΦe se jednß. Zßrove≥ voliΦi nesmφ b²t schopni samostatn∞ vytvo°it d∙kaz oprßvn∞nφ.

Na zßv∞r poznamenejme, ₧e je obvykle velmi obtφ₧nΘ p°edlo₧it matematick² d∙kaz bezpeΦnosti protokolu samotnΘho nebo v zßvislosti na pou₧itφ Üifrovacφho systΘmu, co₧ je dob°e znßmo p°i anal²ze obvykl²ch algoritm∙. Navφc p°φpad kryptografick²ch protokol∙ navφc v sob∞ zahrnuje to, ₧e ka₧d² z ·Φastnφk∙ mß jistou v²poΦetnφ sφlu a usuzovacφ schopnosti, zßvisejφcφ na p°edtφm obdr₧en²ch informacφch, Φφm₧ se cel² proces dokazovßnφ stßvß jeÜt∞ nßroΦn∞jÜφm. P°itom je pot°ebnΘ, aby ka₧d² navr₧en² protokol byl zkoumßn co nejpodrobn∞ji, aby byla nalezena jeho p°φpadnß slabß mφsta, kterß by umo₧nila jeho obchßzenφ Φi zneu₧itφ. Za tφmto ·Φelem byly vypracovßny specißlnφ metody dokazovßnφ sprßvnosti a sφly protokolu. To vÜe vÜak nem∞nφ nic na tom, ₧e vhodn∞ utvo°enΘ protokoly, z nich₧ n∞kterΘ budou pojednßvßny v dalÜφch Φßstech serißlu, nßm zajistφ bezpeΦn∞jÜφ a d∙v∞ryhodn∞jÜφ sv∞t.