Matematika | Logika » Titokmegosztás

TITOKMEGOSZTÁS A kriptográfia egy fontos részterülete a titokmegosztás, amelynek során egy titkot úgy osztunk meg k résztvevő között, hogy a titokhoz egymagában senki ne tudjon hozzáférni, viszont bármely t ≤ k játékos együtt már meg tudja fejteni azt. Kalasszikus példa titokmegosztásra az, amikor egy páncélszekrényhez két különböző zár van, és az ezekhez tartozó két különböző kulcs két embernél van. Külön-külön egyik sem tudja kivenni a pénzt a páncélszekrényből, együtt viszont ki tudják nyitni azt. Definı́ció. Egy titkos w adatból bizonyos wi részeket, úgynevezett árnyékokat készı́tünk Az árnyékok egy W = {w1 , w2 , . , wk } halmazát t-küszöb sémának nevezzük, ha W bármely t eleméből w rekonstruálható, de semelyik t − 1 elemből még nem. Egy optikai titokmegosztási séma Tekintsünk egy nagyon egyszerű esetet: két

játékosunk van, Alı́z és Bob. Együtt festegetnek egy bitkép-rajzoló programmal, és egyszercsak születik egy remekművük, ami dollármilliókat ér. Megegyeznek, hogy a másik háta mögött egyikük sem adja el a képet De nem bı́znak egymásban, és garantálni akarják, hogy a másik ne is tudja eladni a képet egyedül. Tegyük fel, hogy a kép fekete-fehér. Ez lesz a w titok, amelyet két részre fognak osztani: az üzenet egyik része Alı́znál lesz, a másik Bobnál. (Vagyis két árnyék lesz) A saját darabjával sem Alı́z, sem Bob nem megy majd semmire: az árnyékok semmilyen információt nem fognak tartalmazni az eredeti üzenetre vonatkozóan. Ha viszont megegyeznek abban, hogy közösen eladják a képet, akkor együtt már vissza tudják állı́tani az eredeti mesterművet. (Tehát ez egy 2-küszöb séma.) Az egyszerűség kedvéért induljunk ki abból, hogy a kép egyetlen E

betűből áll, és képzeljünk fölé egy négyzetrácsot (1. fólia) Most vegyünk egy üres fóliát, és sűrı́tsük a rácsozást: minden oszlopot osszunk fel két részre. Ezzel az eredeti rácsozás minden cellája két cellára bomlott: egy bal- és egy jobboldalira. Válasszuk ki ezek közül véletlenszerűen az egyiket, és töltsük ki! Tegyük ezt meg minden cellára: ez lesz a w1 árnyék (2. fólia) 1. fólia 2. fólia Vegyünk még egy üres fóliát, amin szintén a sűrűbb rácsozás van (3. fólia) Ezen is töltsük ki minden cella bal vagy a jobb felét a következő szerint: ha w-ben egy mező ki 1 volt töltve, és w1 -ben a bal felét satı́roztuk be, akkor most a jobb felét fessük feketére (vagy fordı́tva)! Ha w-ben egy mező üres volt, akkor a neki megfelelő mezőt ugyanúgy töltsük ki, mint ahogy azt w1 -ben tettük! Az ı́gy nyert fólia lesz a w2 árnyék.

Alı́z megkapja w1 -et, Bob megkapja w2 -t, az eredeti bitképet pedig megsemmisı́tik. Az ı́gy kapott árnéykok semmilyen információt nem tartalmaznak magáról w-ről, mert w1 egy véletlenszerűen satı́rozott fólia, w2 -re pedig nyugodtan tekinthetünk úgy, mint a w és w1 ,,(mod 2) vett összegére”. (Gondoljunk csak vissza a One Time Pad-re, ami ugyanezen az elven működött.) Így tehát lehetetlen belőlük visszaállı́tani w-t, de a kettő együtt éppen w-vé egészı́ti ki egymást. Ha a két fóliát egymásra helyezzük, és úgy hunyorı́tunk, hogy a ritkább rácsozást érzékeljük, akkor kétféle mezőt látunk majd: lesznek szürke mezők (amelyeknek csak az egyik fele van kitöltve), és lesznek fekete mezők (amelyek teljesen ki vannak töltve). Így tehát visszanyerhető az eredeti üzenet. A 2. és a 3 fólia együtt Kérdés. Miért volt szükség a rácsozás

sűrı́tésére, amikor a véletlen satı́rozást készı́tettük? Ha jobban belegondolunk, láthatjuk, hogy ez a séma szinte egy az egyben a One Time Pad elvére épül: van egy m ∈ {0, 1}n titkos üzenet, amelyhez választunk egy k ∈ {0, 1}n véletlen kulcsot, majd képezzük a sifrı́rozott üzenetet: c = m ⊕ k. A One Time Padnél c-t küldjük el, és a partnerünk (k ismeretében könnyen visszafejti az eredeti üzenetet: m = c ⊕ k.) A fenti eljárásnál azonban Alı́z megkapja a k kulcsot, Bob pedig c-t, és m-et megsemmisı́tik. Egyikük sem tudja kitalálni m-et, de a ketten együtt vissza tudják fejteni. (Az optikai sémában m, k, c nem vektor, hanem egy-egy 0-1 mátrix.) Shamir titokmegosztási módszere Adott egy w titok, és van n játékos. Mindegyiknek adunk egy-egy árnyékot: w1 , w2 , , wn A cél itt is az lesz, hogy bármely t játékos együttesen ki tudja találni w-t, de ha csak eggyel is

kevesebben vannak mint t, akkor legyen lehetetlen visszafejteniük w-t. Legyen p nagy prı́mszám, és 0 < w < p teljesüljön az üzenetre. Válasszunk egy (t − 1)edfokú véletlen polinomot, amelynek a konstans tagja maga a w titok legyen A polinom 1, 2, . , n helyen vett helyettesı́tési értékei lesznek a wi árnyékok, ı́gy bármely t játékos összeállva interpolálni tudja a polinomot, és ı́gy megkapják w-t is, mint a polinom konstans tagját. 2 Legyen tehát a0 = w, és válasszunk t − 1 véletlen együtthatót a p elemű testből: a1 , a2 , . , at−1 ∈ Fp A (t − 1)-edfokú polinomunk tehát ı́gy fest: f (x) ≡ at−1 · xt−1 + at−2 · xt−2 + . + a1 · x + a0 = t−1 X ai · xi (mod p) i=0 Az árnyékok pedig: wi ≡ f (i) (mod p) i = 1, . , n Állı́tás. Bármely t játékos együttesen ki tudja találni a w titkot Bizonyı́tás. Tegyük fel, hogy az első t játékos

szövetkezett, tehát ismert f (1) = w1 f (2) = w2 . f (t) = wt . A célunk az, hogy felı́rjuk f -et, vagyis hogy meghatározzuk az ai együtthatókat. Tudjuk, hogy degf = t − 1, és rendelkezésünkre áll t darab helyettesı́tési érték Lagrangeinterpolációval ezekből az adatokból egyértelműen meghatározható f , és ı́gy az f konstans tagja is (a0 ), ami pedig maga a w titok. Állı́tás. Semelyik t − 1 játékos nem tudja kitatlálni a w titkot Bizonyı́tás. Nem meglepő módon ez annak köszönhető, hogy t − 1 helyettesı́tési értékből nem lehet egyértelműen interpolálni egy (t − 1)-edfokú polinomot. Tegyük fel, hogy az első t − 1 játkos állt össze, tehát ismert w1 , . , wt−1 Belátjuk, hogy tetszőleges w titok esetén tudunk mutatni olyan wt árnyékot, amely a w1 , . , wt−1 árnyékokkal együtt éppen a w-t adja vissza. Magyarán a titok még bármi lehet, a t

− 1 játékos semmivel sem került közelebb a megfejtéshez. Tudjuk, hogy f (x) ≡ t−1 X ai · xi (mod p) , és i=0 f (i) = wi (i = 1, . , t − 1) A t − 1 ismert árnyékból ı́gy felı́rható egy t ismeretlenes, t − 1 egyenletből álló lineáris egyenletrendszer, amelyben az ai együtthatók az ismeretlenek. Vegyünk hozzá még egy sort, amely arra utal, hogy a wt árnyékot változónak tekintjük: f (1) = a0 f (2) = a0 . . + a1 · 1 + a1 · 2 + . + . + at−1 · 1 + at−1 · 2t−1 = w1 = w2 f (t − 1) = a0 + a1 · (t − 1) + . + at−1 · (t − 1)t−1 = wt−1 f (t) = a0 + a1 · t + . + at−1 · tt−1 = x = wt 3 Azt állı́tjuk, hogy a t − 1 játékos f egyetlen együtthatóját sem tudja. Sőt, f bármelyik ai együtthatója tetszőlegesen előı́rható, azaz bármelyik Fp -beli értéket felveheti. (Természetesen egyszerre csak egy együttható ı́rható elő Az nem igaz,

hogy az (a0 , , at−1 ) t-es minden Fpt -beli értéket felvehet.) A Cramer-szabály szerint a következő összefüggés adódik: ai = detAi , detA ahol A az együtthatómátrix, Ai -t pedig úgy kapjuk A-ból, hogy A i. oszlopát kicseréljük a (w1 , w2 , . , wt−1 , x)T oszloppal:     A=   1 1 1 . . 1 2 3 . . 1 22 32 . . . . . 1 t t2 . 1   2t−1 3t−1 . .          Ai =    tt−1 1 1 . 1 2 . 1 3 . . . 1 t . w1 w2 w3 . . . . . x . 1  2t−1 3t−1 . .       tt−1 Az Ai determinánsát kifejtve egy elsőfokú polinomot kapunk: detAi = Ui + Vi · x, ahol Ui , Vi konstansok. A Carmer-szabály miatt ai · detA = Ui + Vi · x, és ebből: x = ai · detA − Ui . Vi (1) Az (1) egyenletből pedig már könnyen látható, hogy az ai együttható tetszőlegesen előı́rható: mindig lesz megfelelő x = wt árnyék, amellyel az

egyenlőség teljesül. Így tehát az egyenletrendszer összes egyenlete kielégı́thető, és a w1 , , wt−1 , wt = x árnyékokkal interpolált f polinom ai gyütthatója éppen az előı́rt értéket fogja felvenni. Az előző két állı́tás együttesen pontosan azt bizonyı́tja, hogy a Shamir-féle séma t-küszöb séma. Vegyük észre, hogy a t − 1 játékosnak a titok sikeres megfejtésére nincs több esélye, mint annak, aki egyetlen árnyékot sem ismer. Ugyanis a t − 1 darab árnyék rögzı́tése után f bármelyik együtthatója még tetszőlegesen rögzı́thető. Így speciálisan maga az a0 is, ami éppen a w titokkal egyezik meg. Vagyis annak ellenére, hogy t − 1 árnyék áll rendelkezésre, maga a titok még bármelyi Fp -beli elem lehet. Tehát a megfejtés valószı́nűsége 1/p, ami p növelésével tetszőlegesen kicsivé tehető. Összefoglalva: amı́g az árnyékok

száma nem éri el a t küszöböt, addig nincs jobb módszer a titok feltörésére, mint a tippelés. A titokmegosztási sémák ezen tulajdonságát rögzı́ti a következő definı́ció. Definı́ció. Egy titokmegosztási sémát perfektnek nevezünk, ha igaz rá, hogy a titok megfejtésének az esélye ugyanaz az érték, ha az ismert árnyékok mennyı́sége nem éri el a biztos megfejtéshez szükséges mennyiséget. Ez a definı́ció tökéletesen illik az optikai sémára is, hiszen ott sem lehet semmilyen módszerrel kitalálni a titkot egyetlen árnyékból. (Minthogy x ⊕ y = z esetén sem y-ból, sem z-ből nem lehet kitalálni x-et.) 4 Blakley titokmegosztási sémája A következő egy geometriai jellegű séma: véges projektı́v terekkel operálva osztja el a titkot több résztvevő között. Az itt leı́rtak a Kiss-Szőnyi féle Véges geometriák c könyvből származnak.

Definı́ció. Ívnek nevezzük PG(n, q) olyan legalább n + 1 elemű ponthalmazát, amelynek nincs n + 1 pontja egy hipersı́kban. Legyen Π = PG(t, q) egy t-dimenziós projektı́v tér. Rögzı́tsünk Π-ben egy e egyenest A titkos adat legyen e egy P pontja. Legyen H egy olyan hipersı́k Π-ben, amely nem tartalmazza az e egyenest, de átmegy P -n. G legyen egy olyan (q + 1)-ı́v H-ban, amelyik átmegy P -n, az árnyékok pedig legyenek G-nek P -től különböző pontjai. Állı́tás. Az ı́gy megadott árnyékhalmaz egy t-küszöb séma Bizonyı́tás. Először, ha t darab árnyékot ismerünk, akkor ismerjük magát a H hipersı́kot is, mert t általános helyzetű pont egyértelműen meghatároz egy (t − 1) dimenziós alteret Π-ben. A hipersı́k ismeretében pedig a P = H ∩ e pont is egyértelműen meghatározható Másrészt viszont, ha csak k < t árnyékot ismerünk, akkor a titkot megfejtésére

ugyanannyi esélyünk van, mintha egyet sem ismernénk. Ugyanis a G ı́v k darab pontja egy olyan k-dimenziós U alteret határoz meg, amelyik nem metszi e-t. Viszont bármely e-n lévő E pontra igaz, hogy az U altér és az E pontok által együttesen generált altér már metszi e-t. Ezért k < t árnyék ismeretében a titok megfejtésének esélye 1/(q + 1) Mivel ez a valószı́nűség független k-tól, ezért ez is egy perfekt séma. Tehát ez egy olyan perfekt küszöbséma, amelynél a titok illegális megfejtésének valószı́nűsége a tér rendjének, q-nak növelésével tetszőlegesen kicsivé tehető. Többszintű sémák A titokmegosztási sémák egy másik fajtáját a többszintű titkomegosztási sémák alkotják. Ezekben a sémákban az árnyékok különböző súlyúak lehetnek. Általában azt követeljük meg, hogy ha az árnyékok egy részhalmazának az

összesı́tett súlya elér egy határt, akkor azokból a titok megfejthető legyen. A többszintű sémák legegyszerűbb esete az úgynevezett (2, s)-séma . Egy ilyen sémában az árnyékokat két csoportba soroljuk, jelöljük ezeket T -vel és S-sel. Azt várjuk el, hogy a titok rekonstruálható legyen T bármely két eleméből, vagy S bármely s eleméből, valamint abban az esetben is, ha egy T -beli és s − 1 darab S-beli árnyék áll rendelkezésre; más esetekben viszont legyen lehetetlen visszaállı́tani a titkot. Nézzünk egy példát az s = 3 esetre, amely a Blakley-sémára épül. Legyen e a PG(3,q) tér egy egyenese, a titkos adat pedig legyen e valamely P pontja. Legyen H egy olyan sı́k PG(3, q)-ban, amely nem tartalmazza az e egyenest, de átmegy P -n. G legyen olyan (q + 1)-ı́v H-ban, amelyik átmegy P -n, az f egyenes pedig legyen a G ı́v P -beli érintője. A T -beli árnyékok az f egyenes ponjai

közül kerüljenek ki, az Sbeli árnyékok pedig legyenek G-nek P -től különböző pontjai azzal a megkötéssel, hogy két különböző S-beli pont összekötő egyenesének és f -nek a metszésponja ne legyen T -beli pont. Állı́tás. A ı́gy létrehozott T és S árnyékhalmazok (2,3)-sémát alkotnak 5 Bizonyı́tás. A titkot akkor lehet megfejteni, ha ismerjük vagy az f egyenest, vagy pedig a H sı́kot, mert ezek e-vel alkotott metszéspontja P . Az f egyenest bármely két különböző pontja, a H sı́kot pedig bármely három nem kollineáris pontja egyértelműen meghatározza. Ezért a titok rekonstruálható T bármely két eleméből, valamint S bármely három eleméből is. Mivel az S-beli pontokat összekötő egyenesek f -et nem T -beli pontokban metszik, ezért két S-beli és egy T -beli pont is egyértelműen meghatározza a H sı́kot. Ha viszont kevesebb árnyékot ismerünk,

akkor a titok sikeres megfejtésére most sincs több esélyünk, mint ha egyetlen árnyékot sem ismernénk. Ugyanis az f egyenes egyetlen pontjának, vagy a H sı́k bármely két pontjának ismeretében semmit sem tudunk az e-vel alkotott metszéspontjukról. Ezért a titok megféjtésének esélye most is 1/(q + 1), tehát ez a séma is perfekt. 6