ISSN 0351-6652 Letnik 29 (2001/2002) Številka 6 Strani 358-364
Aleksandar Jurišic: KAKO DELITI SKRIVNOSTI?
Ključne besede: računalništvo, matematika, informacijski sistemi, kri-pografija, Blakley, Shamir.
Elektronska verzija: http://www.presek.si/29/1495-Jurisic.pdf
© 2002 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo
KAKO DELITI SKRIVNOSTI?
Danes že vsi vemo, da imajo informacije enako, včasih celo večjo vrednost kot denar. Zato moramo hiti pri dodeljevanju dostopa do informacij samih skrajno previdni. Iz izkušenj vemo, da ni dobro povsem zaupati nobenemu posamezniku, še posebej, če je v njegovih rokah usoda mnogih. Vedno se tudi lahko zgodi, daje uporabnik neupravičeno izključen iz sistema (npr. če izgubi ključe) ah da nepooblaščeni uporabnik uspe vdreti v sistem.
V prispevku bomo predstavili nekaj splošnih postopkov za deljenje skrivnosti. Le-ti sodijo med osnovne prijeme za povečanje zaupanja v delovanje informacijskih sistemov. To področje predstavlja enega izmed stebrov moderne kriptografije in je tesno povezano s skrbjo za varno in odgovorno ravnanje s ključi.
Za začetek si oglejmo nekaj zanimivih primerov deljenja skrivnosti.
Na tajnem projektu dela n oseb, materiali o projektu pa so spravljeni v trezorju z več ključavnicami. Dostop do materialov je dovoljen le tedaj, kadar se zbere večina, t.j. več kot polovica oseb. Vsak sodelavce dobi enako število kiju če v. Koliko najmanj ključavnic je potrebno in koliko ključev mora dobiti vsak?
Predno si pogledate rešitev, poskusite rešiti nalogo za n = 2,3.4,..nato pa tvegajte z napovedjo, ka j bi utegnila biti dobra spodnja meja za število ključavnic.
Rešitev. Predpostavimo najprej, da nam je ključe uspelo razdeliti tako, kot zahteva naloga, in poglejmo, kaj znamo ugotoviti o številu ključev. Naj bo k — L(n+l)/2j >n s = {£). Potem obstaja natanko s različnih k-elementnih podmnožic G i, G->,... ,GS oseb, ki delajo na tajnem projektu. Vsaka skupina G,; vsebuje vsaj n/2 oseb, zato osebe zunaj te skupine nimajo vseh ključev. Naj bo Ki množica ključev, ki jim manjkajo. Potem nobena izmed množic Kj, i G {1,..., s}, ni prazna. Skupaj s katerimkoli članom skupine G, pa imajo vse ključe, torej ima vsaka, oseba, iz G, vse ključe iz K^ Naj bo i ^ j. V množici G,; obstaja, oseba, ki ni v G j. Ta oseba nima nobenega izmed ključev iz K j, torej je Kj O Kj — Si. Ker sta bila i in j poljubna, od tod sledi, da je različnih kl jučev vsaj s.
Sedaj pa pokažimo, da je s ključev ki,..., ka vedno tudi dovolj za rešitev zastavljene naloge. Ključe razdelimo tako, da dobijo ključ k, natanko vse osebe iz skupine Gj. Tako dobi vsaka oseba	ključev.
Le večinska skupina ima neprazen presek z vsemi pod množicami G,, tako da lahko le taka. skupina odpre trezor.
Najprej smo ugotovili, da mora biti ključavnic vsaj s, nato pa smo našli način, kako dodeliti vsaki osebi	ključev, tako da bodo lahko le
večinske skupine odklenile vse ključavnice.
V banki morajo trije direktorji vsak dan odpreti trezor. vendar pa kombinacije ne želijo zaupati nobenemu posamezniku. Zato bi radi imeli sistem, po katerem lahko odpreta trezor poljubna dva med njimi.
Zgornja rešitev nam svetuje (n = 3, fc = 2, 8 = (¡¡) =■ 3), da nastavimo na trezor tri ključavnice in damo vsakemu direktorju dva ključa (seveda pa nobenemu istega para). Vendar pa. lahko v tem primeru vsak direktor odklene dve ključavnic: in že s tem bistveno oslabi varnost, npr. za trikrat skrajša čas, potreben za odstranitev ključavnic.
Želimo najti rešitev, pri kateri ne bo imel nihče večjih možnosti kot zunanji vlomilec. Ta problem lahko rešimo z (2,3)-stopenjsko shemo za deljenje skrivnosti (glej sliko 1). Takšne sheme sta leta 1979 neodvisno odkrila Blakley in Shamir.
Slika 1. (2, 71)-stopenjska sli eni a za deljenje skrivnosti, T» £ IN. Deiivec si v ravnini izbere premico t. ki ni navpična, in za vsako tjsebo na tej premici izbere svojo točko, ki ne leži na osi y. Za zgornji sliki si izberemo ti — 3,
(a)	Vsaka oseba dobi le koordinato y svoje točke, ki jo shrani, npr. na pametni kartici. Program v trezorjn pozna še ustrezne od (J različne koordinate x, zato lahko izračuna ključ 1/(0), ki je enak odseku, kjer premica ( seka os y. Vsaki dve točki natanko določata premico in s tem ključ.
(b)	Ce imamo eno samo točko, ne moremo ugotoviti, kateri ključ je pravi, saj so vsi videti enako dobri.
V Rusiji so v 90-ih letih prejšnjega stoletja uporabljali (2,3)-stopenjsko shemo za kontrolo jedrskega orožja (predsednik, obrambni minister, vrhovni vojaški poveljnik).
V splošnem je (t.n)-stopenjska shema za deljenje skrivnosti K med 71 oseb, 2 < t < n, metoda, za katero velja:
•	poljubnih i oseb lahko izračuna skrivnost K.
•	nobena skupina s t — 1 (ali manj) osebami ne more izračunati prav nobene informacije o skrivnosti K.
Sheme za deljenje skrivnosti so vsestransko uporabne. Lahko jih uporabimo povsod, kjer do podatkov dostopamo hierarhično. Tak način dostopa je pogost v velikih podjetjih, bankah in vojski.
Če računamo z običajnimi tipi števil, ki so na voljo v standardnih programskih jezikih, moramo rezultate izračunov zaradi omejene velikosti teh tipov nenehno zaokrožati (posebno ko postajajo števila vse večja in večja ali pa jih delimo). V kriptografiji pa približki ne zadoščajo, zato si za računanje raje omislimo končne množice kot pri številčnici na uri. Tak zgled so kolobarji n £ IN, v katerih računamo po modulu števila ri. Za elemente vzamemo {0,1,... ,n — 1}, računamo pa tako, da seštejemo ali zmnožimo dve števili tako, da pravi rezultat nadomestimo z njegovim ostankom pri deljenju z modulom n. Za ji = 7 npr. velja 4-1-5 (mod 7) = = 2 in 5 ■ 4 (mod 7) = 6, saj ima vsota 9 ostanek 2 pri deljenju s 7. produkt 20 pa ostanek 6 (glej sliko 2).
Videli smo že, kako z geometrijskim argumentom zasnujemo (2,n)-stopenjsko shemo za deljenje skrivnosti. Poglejmo sedaj, kako skonstruiramo (i, t)-stopenjsko shemo za deljenje skrivnosti.
'2=4+5
Slika 2. Računanje po modulu 7.
(1)	Naj bo m dovolj veliko naravno število (m > t + 1), K E Sm (skrivnost) in 'P — [P^..... Pt} množica oseb, ki jim želimo razdeliti skrivnost.
(2)	Delivec D 'P neodvisno izbere naključna števila yi, ■ • ■ i yt— i £ £ 7Lm in izračuna
yt = K - (a/i -1- ■ ■ • + yf-i) (mod m).
(3)	Oseba P, dobi del y,, 1 <i<t.
Osebe P\...., Pi-i, Pi+i, •.., Pt lahko izračunajo samo K — y,. kar pa jim nič ne pomaga, saj je bilo število y, naključno izbrano, medtem ko vsi skupaj samo seštejejo svoje dele in razkrijejo skrivnost K.
Shamir je skonstruiral splošno (i, ??,)-stopenjsko shemo za deljenje skrivnosti za poljubili naravni števili t iti n, 2 < t < n. Za tako shemo je dovolj, da v (2,n)-stopenjski shemi za deljenje skrivnosti nadomestimo premico s polinomom stopnje t — 1. saj je tak polinom določen s t točkami.
Spomnimo se, da je polinom spremenljivke x definiran s predpisom
f(x) — a0 + H-----1- , ^ E O
kjer je O neki obseg (npr. IR ali pa p praštevilo). Ničla polinoma f je taka vrednost a E O, za katero je f(a) = 0.
V praštevilskih kolobarjih 7Lp, kjer je p praštevilo, je možno tudi deljenje z vsakim od 0 različnim elementom a 6 Zato ti kolobarji tudi sodijo med obsege, deljenje je namreč kar množenje z recipročnim elementom. Ce le-tega označimo z potem velja a ■ x (mod p) = 1, zato ga lahko poiščemo kot rešitev diofantske enačbe ax + py = 1 z razširjenim Evklidovim algoritmom (glej članek M, Juvana, O Evklidovem algoritmu. Presek21 (1993-94), str. LIC 121). Ta enačba je vedno rešljiva, saj sta si a in p tuja.
Izrek 1. Od nič različen polinom stopnje n ima v obsegu največ n ničel.
Zgornji izrek ne velja vedno, če koeficienti polinoma niso iz obsega. V kolobarju npr, zgornja trditev ne drži, saj ima kvadratni polinom f(x) — (x — l)x kar štiri ničle: 0,1,3,4. Za prvi dve ničli potrebujemo prisotnost le po enega faktorja, za zadnji dve pa potrebujemo hkrati oba faktorja. V obsegih je produkt lahko nič le tedaj, ko je vsaj en izmed faktorjev enak nič. Ce je a ničla polinoma /, potem nam razcep
xi — a' = (x —	H-----1- n'-1) zagotavlja, da lahko zapišemo f(x) =
— f(x) ~ /(a) = — a)q(x)1 kjer je tj polinom stopnje n — 1. Torej se nam za vsako ničlo, ki jo izpostavimo, zmanjša stopnja preostanka za 1 in zato število ničel res ne more preseči stopnje polinoma.
(1)	Naj bo p dovolj veliko praštevilo (p > n + 1), K 6 7LV (skrivnost) in V — {Pi,... ,Pn} množica oseb. ki jim želimo razdeliti skrivnost.
(2)	Delivec D ^ V izbere n različnih elementovxi,x2i. ■ ■ ,xn S Sp\{0} in dodeli del x7 osebi f\ £ V (vrednosti so lahko javne).
(3)	Za delitev ključa K delivec D naključno in neodvisno izbere t — 1 elementov C],..., a(_j 6 ter za i = 1,..., n izračuna y{ — a(Xi), kjer je
u(^) — K \ a\x H-----f- di_ia;t_1 (mod p),
in da del y, osebi P,.
Primer. Naj bo p = 17. t = 3 in n = 5. Za javne koordinate x izberimo Xi —i, 1 <, i < S. Predpostavimo, da osebe P\, P3 in združijo svoje dele, ki so zaporedoma enaki 8, 10 in 11, Če vzamemo a (2) = ou + a 1 z + + a2x2 in izračunamo fi(l), a(3) ter a(5), dobimo sistem treh linearnih enačb v ¿Z17:
QQ + 01+ a,2 — 8, ao + 3«i + 9a2 — 10, «d + 5ai + 8a2 = 11,
ki ima v 2217 enolično rešitev «o = 13, <ti — 10 in a2 = 2. Ključ je torej enak K = = 13,
V primeru splošne Shamirjeve sheme osebe Pi, P2, ■ ■ ■, Pt določijo ključ K iz enačb
yi — «(^i) = £io + a%Xi + . . . +	za 1 < i < t .
S pomočjo metod, ki močno presegajo srednješolsko matematiko, lahko z matrikami in determinantami pokažemo, da ima ta sistem enolično rešitev v 1Drugi način pa je, da si pomagamo s polinomom p(x) stopnje največ i—1, ki ga zna izračunati vsaka skupina t oseb iz svojih delov. Poznamo ga pod imenom interpolacijski polinom (glej sliko 3) in ga vpeljemo preko polinomov /><(£) = (x — ^(a; — 12) • ■ * (x —	— Xi+i) • ■ ■ (x — xt),
t.j. produktov faktorjev (1 — Xj) za j ^ i:
, \ Pi(x) p(x) = y m + Pl(zi)
+ Vt
Pt(x)
Pt(xt)
Slika 3. Interpolacijski polinom.
Faktor v ¿-tem sumando oh yt zavzame vrednost J za i — x, in 0 za vsak drug Xj. Z neposrednim računom ugotovimo, da velja p(x,) = u(x.¡), i = 1,... .t. Od tod sledi, da ima polinom p(:r) — u(:t:), ki je stopnje kvečjemu t — 1, vsaj t ničel. Izrek 1 nam potem zagotovi, daje to možno le, kadar sta polinoma a(x) in p(x) enaka. Zato je K = p(0).
Da se prepričamo, da je to res (i, n)-stopenjska shema za deljenje skrivnosti, moramo utemeljiti še, da i — 1 oseb ne more izključiti nobenega ključa. Ce k i — 1 osebam (te poznajo t — 1 delov skrivnosti) dodamo za poljubni no t 22p še del yo = «o. ki predstavlja vrednost polinoma n(x) v točki — 0, potem z zgornjo formulo zopet dobimo polinom a (x). ki ustreza vsem podatkom, ki so trenutno na voljo.
Ko želi skupina t oseb izračunati ključ K iz svojih delov, pravzaprav ne potrebuje celotnega polinoma p{x). pač pa samo vrednost
A — Vi—,—T -I-----bjft
Pl(Xl)	Pt(Zf)
Od tod se lepo vidi, da je iskani ključ linearna kombinacija delov y,. A' = biyi + b2y2 H-----1- btyt, kjer je
J, -	_X\X2 ' • ' Xj_il¿+i ■ ■ -xt_
PiC*i)	- 2	- Wi)(xi+1 - Xi) • ■ ■ {xt ~ Xi) '
torej je bila (i. i)-stopenjska shema za deljenje skrivnost i le poseben primer splošne sheme. Se več, za samo uporabo splošne sheme za deljenje skrivnosti v resnici ne potrebujemo ne računanja interpolacijskih polinomov ne reševanja sistemov enačb, temveč le seštevanje, množenje in deljenje v končnem obsegu.
Nadaljevanje primera. Osebe jPi, in lahko izračunajo b \, 65 po zgornji formuli. Če izračunamo recipročne elemente z razširjenim Evklidovim algoritmom, dobimo
bj = ---- (mod 17) = 3 * 5 • 2"1 - 4"1 (mod 17) = 4.
Podobno izračunamo tudi 63 = 3 in = 11 ter za dele S, 10 in 11 dobimo K= 4 • 8 -f 3 • 10 + 11« 11 (mod 17) = 13.
Za konec poudarimoT da. je varnost Shamirjeve sheme za deljenje skrivnosti brezpogojna, t.j. noben ključ ni na podlagi informacij, ki jih imajo nepooblaščene množice, bolj verjeten od drugega. Možne so seveda še razne posplošitve, kot je dodelitev različnih prioritet različnim osebam (npr. za dostop do vojaške skrivnosti sta. potrebna dva generala ali pet majorjev), a to je že druga zgodba. Prav tako spadajo v posebno zgodbo tudi kriptosistemi, ki so odvisni od računsko zahtevnih problemov, kot je na primer faktorizacija števil (šifrirne sheme RSA) ali pa diskretni logaritem (ElGamalovi kriptosistemi in digitalni podpis DSA). Več o deljenju skrivnosti si radovedni bralec laliko poišče v učbeniku D.R. Stinsona, Cryptography Theory and Practice, CR.C Press, 1995 ali pa na moji domači strani (http://valjhun.fmf .uni-lj . si/^ajurisic/).
Alekscindar Jurišič