Kriptográfiai protokollok intelligens kártyákon

Borbás Gergely Témavezető: Csirmaz László

Tartalomjegyzék

1. Bevezető 2 1.1. Osztályozási szempontok . . . . . . . . . . . . . . . . . . . . . 6

2. Kriptográfiai segédeszközök 10 2.1. Az RSA rendszer . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2. A Diszkrét Logaritmus Probléma . . . . . . . . . . . . . . . . 13 2.3. A hash függvény . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4. Személyazonosság igazolása . . . . . . . . . . . . . . . . . . . 16 2.5. A Schnorr-féle aláírás . . . . . . . . . . . . . . . . . . . . . . . 18

3. Protokollok 21 3.1. Chaum eredeti rendszere . . . . . . . . . . . . . . . . . . . . . 21 3.2. Brands változata . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.2.1. Az első próbálkozás . . . . . . . . . . . . . . . . . . . . 26 3.2.2. Párhuzamos támadás és az ellene való védekezés …. 38

4. Továbbíthatóság 43

1. fejezet

Bevezető

Az utóbbi időben a technika rohamos fejlődése sok tekintetben megváltoztatta, felgyorsította megszokott világunkat. Az új körülmények a kereskedelem területén is éreztetik hatásukat, egyre inkább terjed az otthonról, az interneten keresztüli vásárlás igénye, de persze még sok más példát is találhatnánk arra, hogy miért vált kényelmetlenné a készpénz használata. Erre a kényelmetlenségre jelent megoldást a bankkártyák megjelenése. Természetesen a váltás nem csupán a kártyák használóinak az érdekeit szolgálja (persze az sem lebecsülendő: egy jól megtervezett és kiépített rendszer készpénzhez közeli rugalmasságot kínál magsfokú biztonság mellett), a bankok is szorgalmazzák a chipkártyák elterjedését, ami nem is csoda, hiszen sokat számít, hogy az emberek elköltésre váró pénze a banknál forog, dolgozik, ahelyett, hogy otthon, a pénztárcákban lapulva tétlenül várja, hogy használják.

Több szempontból is szükség van tehát a váltásra, az elektronikus fizetőeszközök bevezetésére. Ez persze nem olyan egyszerű, az adódó problémákat meg kell oldani, hogy az igényeket minden oldalról kielégíthessük. Lássuk, melyek azok a feladatok, amelyekkel meg kell birkóznunk, mik az igazi pénznek illetve a fizetésnek, pénzcserének azok a tulajdonságai, amiket modelleznünk kell, ha egy jól működő rendszert szeretnénk tervezni:

• Atomosság, ami azt jelenti, hogy a tranzakciónak egészként kell viselkednie, vagy az összes lépésnek végre kell hajtódnia, vagy egynek sem. Pontosabban bármi is történik tranzakció közben, a rendszer végül két állapot közül lehet egyben: vagy úgy, mintha rendben lefolyt volna miden művelet, vagy pedig úgy, mintha el sem kezdődött volna semmi. Ez modellezi azt, hogy ne történhessen meg, hogy fizetéskor például csak a pénz kerül át az egyik oldalról a másikra, amiért fizettünk, az nem.

• Konzisztencia, azaz a rendszernek egy értelmes, jól definiált állapotban kell lennie a tranzakció elkezdése előtt, és hasonlónak igaznak kell lennie a folyamat befejeződése után, tehát nem szabad, hogy csak „félig” kerüljön át a pénz, illetve elvesszen közben valahogy (itt már, ott még nincs meg).

• Izoláció: követelmény, hogy párhuzamos folyamatok ne kommunikálhassanak egymással, egy érme ne vehessen részt egyszerre két külöböző tranzakcióban.

• Tartósság: lényeges, hogy egy sikeresen véghezvitt tranzakció végeredménye megmaradjon, a rendszer szereplő ne tudjanak önkényesen az előző állapothoz visszatérni, ha egyszer fizettünk egy érmével, akkor ne tudjuk megtartani, vagy tagadni a fizetés tényét.

Ezek a követelmények rögzítenek sok olyan fontos tulajdonságot, főleg biztonsági szempontból, amelyet egy elektronikus – vagy bármely egyéb – fizetési rendszertől elvárunk. A készpénznek azonban ezek mellett is vannak olyan ismérvei, amelyeket esetleg szeretnénk, ha az új rendszerek is teljesítenének. Ezek közül egy a pénz felhasználójának az anonimitása, azaz a fizetésnél nem történik meg a fizető azonosítása, az értéket az érme önmagában képviseli, garantálja; utólag nem bizonyítható – természetesen ideális fizetés esetén –, hogy kié volt eredetileg a pénz. Egy másik tulajdonság a pénz továbbadhatósága, azaz az egyik fizetéskor kapott érmét változtatás nélkül azonnal újra, ugyanolyan értékben ismét föl lehet használni az eredeti célra. Ezekre a fizetésekre igaz az is, hogy ha egyazon érmével kétszer fizettünk, akkor nem lehet megállapítani, hogy ugyanaz az érme vett részt a két tranzakcióban. Ugyanez az összekapcsolhatatlanság természetesen igaz az emberekre is, két különböző fizetésről nem lehet eldönteni, hogy azonos volt-e a két fizető személy.

Természetesen a valóságban ezeket a célokat sokkal könnyebb elérni: az állam sok tartós, egyforma, ám lemásolhatatlan érmét gyárt, és máris megoldódnak a biztonság illetve az anonimitás problémái is. Az elektronikus kereskedelemben kézenfekvő, hogy az értéket az információ képviselje, egy jelsorozat legyen az érme, ez azonban rögtön két gondot is okoz: információt generálni sem túl nehéz, lemásolni azonban mindennél egyszerűbb. Valahogy garantálni kell hát, hogy a felhasználó ne tudjon saját maga olyan adathalmazt készíteni, amely érvényes fizetőeszköznek számít, illetve meg kell akadályozni, hogy a bank által generált információt több alkalommal is felhasználhassa. A kettő közül az utóbbi probléma tűnik nagyobbnak, a két kínálkozó megoldás egyike, hogy a bank védi az információ másolását; olyan eszközzel szereli föl a felhasználót, amely szükséges a fizetéshez és megakadályozza, hogy egy érmét kétszer költsenek el, ebben az esetben azonban van valaki, illetve valami, ami a felhasználó minden tranzakcióját figyeli, tehát veszélyben a kívánt anonimitás. A másik lehetőség, hogy a bank személyre szabott érméket gyárt, így a duplán elköltött érme által a vétkes személyazonossága kideríthető. Itt azonban ismét ellentmondásgyanús helyzet előtt állunk, hiszen azt szeretnénk, hogy az érme egyszeri elköltése semmilyen információt ne hordozzon arról, aki fizetett vele, míg két elköltés esetén minden ismertté váljon.

Az ilyen és ehhez hasonló problémákra kínál megoldást a matematika, pontosabban a kriptográfia használata. Modelljeinkben egymás mellett fogjuk használni a modern nyilvános kulcsú, illetve a klasszikus, szimmetrikus rendszereket, amelyek bizonyítottan – illetve legtöbbször csak sejtetten, bizonyos, nem igazolt, ám régóta vizsgált és igaznak tűnő feltételezésekre alapozva – nehézzé teszik a hamisítást, megvédik a felhasználó anonimitását, garantálják a felsosrolt „ACID” tulajdonságok teljesülését.

Először áttekintjük a manapság használatos rendszereket, osztályozzuk őket különböző szempontok alapján, megvizsgáljuk, mikor melyiket érdemes alkalmazni. A második fejezetben bevezetésre kerülnek a segédeszközeink, megismerkedünk azokkal a problémákkal, melyek nehézsége, bonyolultsága segítséget nyújt, hogy bizonyos dolgokat nehézzé és bonyolulttá tegyünk egy átlagos ember számára, mégis könnyű maradjon annak, aki ismer bizonyos plusz információt. Ezekre alapozva készítünk néhány kriptográfiai makrót, alapalgoritmust, melyekből a harmadik fejezetben felépítjük azokat a protokollokat, amelyek megvalósíthatják az elektronikus kereskedelmet. A negyedik fejezetben az addigi leegyszerűsített rendszerek egy lehetséges kiterjesztésének problémájával foglalkozunk, az érmék továbbadásának, az újrafizetésnek a lehetőségét vizsgáljuk.

Elöljáróban még néhány megjegyzés: a vázolt rendszerek szereplői természetes módon három csoportba oszthatók: először is van egy bank (általában B-vel jelöljük), valaki (U), akinek számlája van a banknál és szeretne fizetni valaki másnak (S), aki szintén kapcsolatban van a bankkal. Ehhez a három szereplőhöz három protokoll tartozik, amely az elektronikus érme (C) életútja is egyben: C először B-től U-hoz kerül, mely művelet során U bankszámlája C ellenértékével csökken, majd U fizet S-nél C-vel, megkapja azt a szolgáltatást, amit szeretne, végül pedig S visszajuttatja C-t B-hez, amikor az érme értékének megfelelő összeg jóváíródik S számláján.

Természetesen mindig megköveteljük az említett biztonsági kritériumok teljesülését, gyakran ügyelünk a felhasználók és a fizetések párosíthatatlanságára, és csak utólag nézzük meg, hogy mi történik, ha szeretnénk, hogy C-fizetésre használhassa föl S, ne kelljen visszaküldenie B-nek és újat generáltatnia, ha ő is vásárolni akar.

Általában B-t becsületesnek tételezzük föl, mint akinek nagyobb kárt okoz a kipattanó botrány, mint amennyi pénzt egy-egy felhasználót, boltot becsapva nyerhet. Amennyiben ez ellen is be szeretnénk biztosítani magunkat, szükségünk van egy negyedik személyre, aki szavatolja a bankokat. Továbbá nem foglalkozunk azzal sem, hogy hogyan történik meg a felhasználók bankbeli regisztrációja, könnyen látható, hogy tisztán kriptográfiai eszközökkel nem lehet garantálni az első találkozás hitelességét, a rendszerbeli azonosítót és az igazi személyazonosságot valahogyan külső eszközökkel kell összekötni.

1.1. Osztályozási szempontok

Az elektronikus fizetési lehetőségeket, módszereket (1) nyomán az alábbiak szerint csoportosíthatjuk:

Előre kifizetett pénz - fizetés utasításra: Az előbbi eset valójában az elektronikus pénz megvalósítása. A felhasználó valamikor a vásárlás előtt valódi értékeit elektronikus érmékre konvertálja még a fizetési tranzakció előtt (ekkor a megfelelő összeggel csökken a számlája a banknál), majd a boltos a kapott információt a bankhoz elküldve hozzájut pénzéhez. A módszer biztonságtechnikai szempontból legkényesebb pontja annak megakadályozása, hogy a felhasználóhoz került könnyen másolható információt ne lehessen több alkalommal is felhasználni. Szintén életbevágóan fontos a hamisítás lehetetlenné tétele, ne lehessen a bank segítsége nélkül érvényes pénzt generálni. Esetünkre jó példát szolgáltatnak a telefonkártyák.

A második lehetőségnél a tranzakció folyamán a felhasználó engedélyezi a kereskedőnek, hogy a banknál megterhelhesse a számláját, tulajdonképpen kitölt egy csekket, ami később a banknál beváltható. A rendszer megvalósításánál arra kell legfőképp vigyázni, hogy a vásárló ne adhassa ki másnak magát, ne legyen hamisítható az aláírása. Ilyen elven működnek egyes külföldön elterjedt kreditkártyarendszerek.

On-line - off-line: A megkülönböztetés alapja, hogy a fizetési protokoll két- vagy háromszemélyes-e, azaz szükség van-e a bank részéről a tranzakció hitelesítésére (ekkor nevezzük on-line rendszernek) avagy nincs (off-line fizetés). Az utóbbi eset nehézségei hasonlatosak az előző pontban említettekéhez, a bank segítsége mindenképpen megkönnyíti a csalások kiszűrését, ám nagy árat kell érte fizetni: egy harmadik, távoli, esetleg éppen nagyon elfoglalt szerverrel történő kapcsolat jelentősen megnöveli a tranzakció időigényét. On-line módon működnek a magyar pénzintézetek által kibocsátott bankkártyák.

Számláló - érmék: A rendszerek között az alapján is különbséget tehetünk, hogy a kártyán hogyan tárolódik a felhasználó pénze. Az első esetben egy számláló található a kártyán, aminek a pillanatnyi állása az éppen rendelkezésre álló mennyiséget jelzi, a pénz felvétele és a fizetés pedig ennek a számlálónak a megfelelő átállítását jelenti. Ez a módszer elegáns és hatásos: kevés tárolóhelyet igényel, bármekkora összeg kifizethető vele (természetesen a kártyán tárolt mennyiség behatárolja a lehetőségeket). A második lehetőség elektronikus pénzérmék gyártása. Amikor a felhasználó pénzt vesz föl a banktól, akkor előre meghatározott értékű „információcsomagokat kap”, ezek tárolódnak a kártyán, kerülnek át fizetéskor a kereskedőhöz, majd jutnak vissza végül a bankhoz.

Nyilvánvaló hátránya a rendszernek, hogy csak olyan fizetéseket lehet lebonyolítani, amelyek összegét pontosan elő lehet állítani a kártyán lévő érmékből, illetve a fizetés végén egy újabb fizetési procedúrával a kereskedő „visszaadhat”, azonban ez jelentősen elbonyolítja a helyzetet. Nagy előny viszont, hogy érméket csak a bank tud generálni, a hamisításhoz a bank digitális aláírását kellene föltörni, míg egy számláló jogosulatlan átállítását sokkal könnyebbnek tűnik megoldani. így a rendszer kijátszásának egyetlen módja a használatban lévő érvényes pénz lemásolása, ez azonban viszonylag könnyen kivédhető azáltal, ha az érmékbe elkódoljuk a jogosult felhasználó személyazonosságát. Továbbá egyedül az érmés rendszereknek van meg az a jó tulajdonságuk, hogy egyfelől biztonságot nyújtanak a banknak, másfelől képesek megőrizni a felhasználó anonimitását, azaz a kereskedőnek átadott érméről nem lehet eldönteni, hogy melyik alkalommal, kinek készítette a bank. Hogy ez ne mondjon ellent az előbb említett személyre szabott fizetőeszköznek, el kell érnünk, hogy a vásárló azonosítóját csak akkor lehessen dekódolni, ha megpróbálta kijátszani a rendszer szabályait.

Csak szoftveres - megfigyelőt is tartalmazó rendszerek: A modellek megvalósításában természetszerűleg a felhasználóknak szükségük van valamilyen speciális eszközre, bankkáryákra vagy számítógépekre, amiken keresztül kapcsolatba léphetnek a bankkal illetve a kereskedőkkel. Egy fontos szempont a rendszerek osztályozásánál, hogy a felhaszáló által használt eszköz tartalmaz-e speciális, a bank által készített hardvert, amely fizikailag védett a külső manipulációk ellen, vagy a rendszer biztonsága csupán a felhasznált kriptográfiai protokollok erején múlik. A speciális hardver (megfigyelő) használata mindenképpen megkönnyíti a hamisítás elleni védekezést: amennyiben a megfigyelő érvényesítése is szükséges egy tranzakciónál, úgy nem lehet egy adott érmét több alkalommal is elkölteni, hiszen másodszorra a megfigyelő egyszerűen megtagadja a pénz hitelesítését. Az említett változatok ezen előny mellett azonban rendelkeznek két jelentős hátránnyal is: lényegesen drágábbak, mint azok a rendszerek, ahol nincs szükség megfigyelőre, az utóbbiak szoftvere bármilyen számítógépen futtatható, a banknak nem kell ellátnia a klienseit fizikai eszközökkel. A másik hátrány, hogy a felhasználók anonimitása veszélybe kerülhet, ha a fizetési tranzakció közben a megfigyelő szabadon kommunikálhat a protokoll másik résztvevőjével. A csak kriptográfiai eszközöket használó rendszerek az olcsóság és az egyszerűség mellett egy nagy problémával is bírnak: az érméket többször is el lehet költeni, a bank csak abban bízhat, hogy utólag leleplezi a tettest. Ezért is fontos, hogy az ilyen érméknek, tranzakcióknak nem szabad nagy értéket képviselniük. Így elkerülhető, hogy egy különösen nagy értékű csalás után a bűnös a tett és a felfedezése közti időben külföldre meneküljön, személyazonosságot váltson.

Kriptográfiai segédeszközök

2.1. Az RSA rendszer

A modern kriptográfia egyik leggyakrabban alkalmazott eszköze a Rivest, Shamir és Adleman által kidolgozott nyilvános kulcsú rendszer, amelyet (2)- ban publikáltak. A szerzők a faktorizálás nehézségére építenek, miután nem ismeretesek gyors algoritmusok, amelyek egy megfelelően nagy (mondjuk 150 jegyű) számot gyorsan prímtényezőire bontanának. Fontos szerepet kap még, hogy ezzel ellentétben viszonylag könnyen meg tudjuk mondani nagy bizonyossággal egy hasonló nagyságú számról, hogy prím-e vagy sem (Rabin-Miller algoritmus).

Feltételezésünk tehát a következő:

• Az x ismeretlenű x^{e} ≡ y (mod n) egyenletet rögzített e, y és n számokra, ahol utóbbi összetett, n prímfelbontásának ismerete nélkül nem tudjuk hatékonyan megoldani.

Jelenleg ezt nem tudjuk bizonyítani, azonban a következő állítás teljesül, ami a faktorizálás és a gyökvonás kapcsolatát mutatja:

2.1.1. állítás. Legyenek p, q nem ismert prímek és n = pq. Ha létezik algoritmus, ami y bemenetre polinomiális idő alatt megad egy x-et, amire x^{2} ≡ y (mod n), akkor p és q polinomiális időben nagy valószínűséggel kiszámítható.

Bizonyítás. Elemi algebrai megfontolásokkal belátható, hogy egy a ∈ ℤ_{p} számnak mod p vagy pontosan két négyzetgyöke van vagy egy sincs. Valóban: b^{2} ≡ a (mod p)-ből (p − b)^{2} ≡ a (mod p) következik. b^{2} ≡ c^{2} (mod p)- ből pedig (b − c)(b + c) ≡ 0 (mod p), azaz vagy b ≡ c (mod p) vagy pedig b ≡ −c (mod p). Így a ∈ ℤ_{n}-re b^{2} ≡ a (mod n)-nek ha van megoldása ℤ_{n}-ben, akkor pontosan négy van. Hiszen b^{2} ≡ a (mod n) pontosan akkor, ha b^{2} ≡ a (mod p) és b^{2} ≡ a (mod q) egyszerre teljesül. A lehetséges négy megoldáspár mod n négy különböző maradékosztályt határoz meg.

Ezekután válasszunk x_{1}, x_{2}, ⋯, x_{k} ∈ ℤ_{n} számokat véletlenszerűen. Legyen y_{i} ≡ x_{i}^{2} (mod n). Tápláljuk be az algoritmusnak az y_{i} számokat. Miután az y_{i}-knek van gyökük ℤ_{n}-ben, ezért léteznek további gyökeik is: z_{1}, z_{2}, ⋯, z_{k} illetve ezek inverzei. Ha az x_{i}-ket véletlenül választottuk, akkor az algorimus \frac{1}{4} valószínűséggel fogja az x_{i}, −x_{i}, z_{i} és −z_{i} számok egyikét választani, azaz \frac{1}{2} valószínűséggel megkapjuk z_{i}-t. Összességében tehát (\frac{1}{2})^{k} valószínűséggel megismerünk egy z_{i}-t. Jelöljük ezt a továbbiakban z-vel, a hozzátarozó x_{i}-t pedig x-szel.

Mivel z^{2} ≡ x^{2} (mod n), ezért z^{2} ≡ x^{2} (mod p) és z^{2} ≡ x^{2} (mod q) is fönnáll. A z ≡ x (mod p) és z ≡ x (mod q) esetből z ≡ x (mod n) következik, a z ≡ −x (mod p), z ≡ −x (mod q)-ból pedig z ≡ −x (mod n). Azonban föltételezésünk szerint ezek a lehetőségek nem fordulhatnak elő, így az általánosság megszorítása nélkül föltehető, hogy z ≡ x (mod p), valamint z ≡ −x (mod q).

Ekkor

(z − x)(z + x) ≡ z^{2} − x^{2} ≡ 0 (mod n),

azaz

n | (z − x)(z + x),

úgy, hogy p | z − x, de q ∤ z − x, amiből az következik, hogy n és z − x legnagyobb közös osztója p, amit a polinomiális futási idejű euklideszi algoritmussal meghatározhatunk, azaz megállapítottuk n prímfelbontását. ■

Jelöljük a rendszer szereplőit szokás szerint A-val és B-vel. Inicializálásképpen A választ két nagy prímszámot p-t és q-t, a későbbiekben minden számítást mod n fogunk végezni, ahol n = pq. Természetesen ahhoz, hogy a rendszer biztonságos és jól használható legyen, szükséges, hogy bizonyos szempontokat figyelembe vegyünk p és q megválasztásakor, ilyen követelmény például, hogy φ(n)-nek ne legyen kicsi páratlan prímosztója, valamint, hogy p és q ne legyen túl közel egymáshoz.

A választ egy d számot ℤ_{φ(n)}^{∗}-ből – azaz d relatív prím kell, hogy legyen (p − 1)(q − 1)-hez –, ami a titkos kulcsa lesz. A nyilvános kulcsa az (n, e) pár lesz, ahol e-t az

e ≡ \frac{1}{d} (mod φ(n))

definiálja. Természetesen p-t, q-t, d-t illetve φ(n)-t A nem hozza nyilvánosságra. Itt is vigyázni kell azonban, hogy helyesen válasszuk meg az értékeket: ismeretes például, hogy d < n^{0.292} esetén a rendszer nem biztonságos (lásd (3)). d-vel ellentétben e értékét gyakran célszerű kicsinek választani, amivel a titkosítás sebességét növelhetjük meg.

A nyilvános kulcs segítségével B tud üzenetet küldeni A-nak, ahol az üzenet egy ℤ_{n}-beli m szám (amennyiben m túl hosszú lenne, akkor 0 és n közé eső darabokra vágjuk), B kiszámítja z ≡ m^{e} (mod n)-et és eljuttatja A-hoz. Az üzenet visszafejtése a kódoláshoz hasolóan történik:

m ≡ z^{d} ≡ (m^{e})^{d} (mod n),

hiszen

ed = 1 + rφ(n) = 1 + r(p − 1)(q − 1),

ahol r ∈ ℕ. Így p ∤ m-re a „kis” Fermat-tételből tudjuk, hogy m^{p−1} ≡ 1 (mod p), emiatt:

(m^{e})^{d} ≡ m^{ed} ≡ m(m^{p−1})^{r(q−1)} ≡ m (mod p),

míg p | m-re

m^{ed} ≡ 0 ≡ m (mod p).

Tehát minden m-re igaz

m^{ed} ≡ m (mod p).

Teljesen hasonlóan láthatjuk, hogy

m^{ed} ≡ m (mod q)

is teljesül, azaz

m^{ed} ≡ m (mod pq = n).

2.2. A Diszkrét Logaritmus Probléma

Legyen q tetszőleges prím, jelölje G_{q} a q-ad rendű csoportot, amelyről így tudjuk, hogy izomorfia erejéig egyértelmű, továbbá azt is, hogy ciklikus, valamint minden eleme (az egység kivételével) generálja az egész csoportot. Jelöljük k-val q jegyeinek számát (k = ⌈ log_{10} q⌉).

2.2.1. definíció. Diszkrét Logaritmus Problémának nevezzük az egyértelmű log_{g} h ∈ ℤ kitevő megtalálását, amelyre g-t emelve h-t kapjuk. Egy (nem feltétlenül determinisztikus) algoritmus megoldja a Diszkrét Logaritmus Problémát, ha létezik g_{1}(x) és g_{2}(x) polinom, hogy G-n egyenletes eloszlás szerint generált g ≠ 1, h inputokra t idő alatt legalább p valószínűséggel megadja log_{g} h-t,ahol t < g_{1}(k) és p > \frac{1}{g_{2}(k)}.

2.2.2. állítás. Ha egy algoritmus megoldja a Diszkrét Logaritmus Problémát, akkor létezik olyan algoritmus is, ami tetszőlegesen nagy valószínűséggel számolja log_{g} h-t.

Bizonyítás. Az eredeti algoritmust (r_{1}-et és r_{2}-t véletlenül választva) a g^{r_{1}}, h^{r_{2}} páron n-szer futtatva legalább 1 − (1 − p)^{n} valószínűséggel kapunk egy helyes eredményt. Az eredmények helyességét könnyen ellenőrizhetjük, mindössze egy hatványozást kell hozzá elvégezni, amit általában gyorsan meg tudunk tenni. A helyes eredményt \frac{r_{1}}{r_{2}} mod q-val szorozva log_{g} h-t kapjuk. ■

2.2.3. állítás. Ha létezik egy olyan algorimus bármilyen rögzített g ≠ 1-re, aminek inputként h-t adva kiszámítja log_{g} h-t, akkor létezik olyan is, ami megteszi ezt tetszőleges g, h-ra.

Bizonyítás. Jelöljük g_{1}-gyel az eredeti algoritmusunk „alapszámát”. Ekkor r_{1} = log_{g_{1}} g és r_{2} = log_{g_{1}} h-val log_{g} h = \frac{r_{2}}{r_{1}} . ■

Természetesen a DLP megoldásának a nehézsége a csoport realizációján múlik, például ℤ_{q}^{+}-ban a feladat triviális, csupán egy q szerint vett osztási maradékot kell számolni, melyet az Euklideszi algoritmussal polinomális időben tehetünk meg. Azonban G_{q}-nak (egy p = nq+1 alakú prímre) ℤ_{p}^{∗} egy q elemű részcsoportját választva nem ismeretes hatékony algoritmus. (Amennyiben külön nem hangsúlyozzuk, a továbbiakban G_{q}-val ezt a csoportot jelöljük.) Ezzel kapcsolatos a következő

2.2.4. feltételezés. Nincs olyan algoritmus, amely tetszőleges, konkrét G_{q}- ra megoldaná a Diszkrét Logaritmus Problémát.

Feltételezésünk eddig ugyan nem nyert bizonyítást, így az előbbiekben vázolt speciális esetről sem mondhatunk semmi bizonyosat, ám az eddig fölfedezett algritmusok elegendően lassúak ahhoz, hogy a későbbiekben nyugodtan támaszkodhassunk a DLP nehézségére. Ahhoz, hogy G_{q}-t a későbbiekben sikeresen használhassuk, feltétlenül szükséges, hogy (a logaritmusszámítással ellentétben) hatékonyan tudjunk különböző manipulációkat végezni G_{q}-val kapcsolatban: egy számról eldönteni, hogy eleme-e a csoportnak; elem inverzét, adott hatványát, valamint két elem szorzatát számítani; a csoportból egyenletes vagy közel egyenletes eloszlás szerint egy elemet kiválasztani (közel egyenletes eloszlás alatt azt értjük, hogy néhány -polinomiális számú- elem választása nem megengedett, például, amikor garantáltan különböző elemekre van szükségünk), valamint megállapítani két elemről, hogy egyenlőek-e. Könnyen látszik, hogy ezekre a feladatokra léteznek gyors algoritmusok az említett G_{q}-ban.

Gyakorlati szempontokat figyelembe véve G_{q} definiálásánál p-t egy legalább 512, q-t pedig minimálisan 140 bit hosszúnak szokás választani. Az ilyen csoportoknál az említett műveletek ismert számítási módszereinek sebességei megfelelnek a kívánalmaknak.

2.3. A hash függvény

Az egyik alapvető kriptográfiai segédeszköz, amely szinte minden alkalmazásben jelentős szerephez jut, a továbbiakban H-val jelölt hash függvény. Formálisan {0, 1}^{∗}-ból {0, 1}^{n}-be képez valamilyen rögzített n-re. Legfőbb kritériuma, hogy egyirányú legyen, ezt kétféleképen is szokták definiálni:

2.3.1. definíció. (gyenge változat) Ne létezzen olyan n-ban polinomiális futási idejű algoritmus, ami x inputra talál olyan y ≠ x-t, hogy H(x) = H(y).

2.3.2. definíció. (erős változat) Ne létezzen olyan n-ban polinomiális futási idejű algoritmus, ami talál olyan x-et és y-t, hogy x ≠ y és H(x) = H(y).

A későbbiekben a második tipusú függvényeket nevezzük hash függvényeknek. Nyilvánvaló, hogy k-t elegendő nagyra kell megválasztanunk, hogy ne lehessen például egyszerű kereséssel gyorsan találnunk megfelelő (x, y) párt. A gyakorlatban általában ezért k-t legalább 160-ra szokták választani. Bizonyítás nélkül megemlítjük az alábbi lemmát:

2.3.3. lemma. (Születésnap-támadás) Egyenletesen véletlenül választva x, y párokat O(2^{\frac{k}{2}} ) próba után \frac{1}{2}-nél nagyobb eséllyel találunk x, y különböző számokat, amikre H(x) = H(y).

Bizonyítás. Az állítás a jól ismert Születésnap-paradoxonhoz kapcsolódik, mint a neve is mutatja; bizonyítása egyszerű, ám hosszas számolás. ■

Alkalmazásainkban gyakran a hash függvény értékkészlete gyakran nem a teljes {0, 1}^{n} lesz, hanem például G_{q}, valamint az argumentumok számát sem fogjuk egyben korlátozni, ezt a problémát könnyen megoldhatjuk az argumentumok konkatenálásával.

Bár léteznek „elméleti” hash függvények is, amelyek bizonyíthatóan jól viselkedek, ezeket a gyakorlatban ritkán használják viszonylagos lassúságuk miatt; bizonyos „bitkevergetésen” alapuló módszerek (például az SHA-1) a tapasztalatok alapján megfelelő eredményt adnak és nagyságrendekkel gyorsabbak.

2.4. Személyazonosság igazolása

Az eddig megismert módszerek segítségével könnyen gyárthatunk egy olyan protokollt, mely használatával az egyik szereplő (P) meggyőzheti a másikat (V) arról, hogy ő tényleg az, akinek állítja magát. Természetesen szükségünk van bizonyos előkészületekre: P és V először megállapodik egy bizonyos G_{q}- ban, a protokoll végrehajtása folyamán ezen G_{q} egyes elemei lesznek az egymáshoz intézett üzenetek. Második lépésként választanak egy g ∈ G_{q} \ {1} elemet; majd P legenerálja a titkos kulcsát, azaz véletlenül választ egy x ∈ ℤ_{q} számot, ami ismerete fogja őt azonosítani. Kiszámítja h = g^{x}-t (természetesen mod p), majd h-t ismerteti V-vel is, a (g, h) pár lesz az ő nyilvános kulcsa. A nyilvános kulcsot V eltárolja az adatbázisában azzal az információval, hogy P-hez tartozik. Az eddigi lépések nem tartoztak szorosan a protokollhoz. Természetesen annak az ellenőrzését is meg kell oldani – és erre nem vagyunk képesek tisztán matematikai eszközökkel –, hogy P tényleg az-e, akinek kiadja magát.

Az előkészületek után lássuk mi történik, amikor valamikor később a már regisztrált P kapcsolatba akar lépni V-vel, és meg akarja győzni arról, hogy ő tényleg P:

1. P választ egy véletlen számot: w ∈ ℤ_{q}, kiszámítja a = g^{w}-t és elküldi V-nek.

2. V generál egy c ∈ ℤ_{q}-t és elküldi P-nek.

3. P válasza r = cx + w (mod q).

V elfogadja P igazolását, ha g^{r} = h^{c}a. A fenti protokoll teljesíti azt a három kritérimot, amit elvárunk tőle:

• Ha P követi a protokoll szabályait, akkor V elhiszi, hogy valóban az, akinek állítja magát (tényleg tudja x-et).

• x ismerete nélkül P nem tudja meggyőzni V-t, csak elenyésző valószínűséggel.

• Tetszőleges megfigyelő a protokoll polinomiálisan sok végrehajtásából nem tud elegendő információt nyerni ahhoz, hogy nem elhanyagolható valószínűséggel el tudja játszani P szerepét.

Az első tulajdonság nyilvánvaló, hiszen így konstruáltuk meg a protokollt, a második kettő pedig a DLP föltételezésből következik.

2.5. A Schnorr-féle aláírás

A fönti személyazonosságot igazoló protokollból könnyen készítetünk digitális aláírást is.

Adott a következő szituáció: U szeretne hitelesíteni egy m adatsorozatot, azaz bizonyítékot szeretne arra kapni (amit majd később fölhasználhat), hogy az adott pillanatban m milyen értéket tartalmazott. Bizonyítékként elfogadjuk B állítását.

Első lépésként B generál egy nyilvános (g, h) kulcsot a hozzátartozó x = log_{g} h titkos kulccsal. A (g, h) párt nyilvánosságra hozza egy előre rögzített H hash-függvénnyel együtt.

Amikor U szeretne egy hitelességet igazoló aláírást kapni egy m számra, akkor ezt megteheti úgy, hogy a már ismert identifikációs protokollt játsza le B-vel, azzal a különbséggel, hogy c-t nem véletlenül választjuk:

1. B generál egy véletlen w ∈ ℤ_{q}-t, majd közli U-val a = g^{w}-t.

2. U elárulja B-nek c = H(m, a)-t.

3. B kiszámítja c^{x}-t és elküldi U-nak.

U hitelesnek tekinti az aláírást, ha g^{r} = h^{c}a.

A (c, r) pár az m üzenet Schnorr-aláírása, amennyiben c = H(m, g^{r}h^{−c}). H használata garantálja egy későbbi ellenőrző számára, hogy a protokoll lépései a megfelelő sorrendben hajtódtak végre, hiszen például c = H(m) választással r-et véletlenszerűen választva a = \frac{g^{r}}{h^{c}} -vel U „érvényes” alírást kaphatna.

Sajnos rossz szerkezetű H-val előfordulhat, hogy néhány m_{i} és a hozzájuk tartozó (c_{i}, r_{i})-k ismeretében U B közreműködése nélkül is tud valamely m-re algebrai úton egy helyes (c, r) aláírást produkálni. Ezért is fontos, hogy megbízható, alapos vizsgálatoknak alávetett hash-függvényeket alkalmazzunk, amelyek a lehetőségekhez képest ellenállnak az efféle támadásoknak.

A módszer egyik hiányossága az, hogy B – ugyan m-et nem, de – m aláírását megismeri a protokoll végrehajtásakor. Ez a későbbiekben ott kap szerepet, hogy bizonyos rendszerekben m fogja játszani az érme szerepét, és mivel említettük, hogy egyik célunk az, hogy a pénzt anonim módon költhessük el, B könnyedén kikeresheti az adatbázisából, hogy az adott tranzakcióban szereplő aláírást melyik felhasználó számára készítette, a fönti célt ez teljesen meghiúsítja. Szükség van tehát egy olyan algoritmusra, amellyel B vakon tudja aláírni m-et, azaz később ne tudja eldöneni, hogy egy adott (c, r) párt a protokoll melyik végrehajtásánál szolgáltatta.

Az ehhez megfelelő módozatot Schnorr publikálta (5)-ben.

1. B generál egy véletlen w ∈ ℤ_{q}-t, majd közli U-val a = g^{w}-t.

2. U véletlenül választja az u, v ∈ ℤ_{q} számokat. a′-t a′ = ag^{v}h^{−u}, míg c′-t c′ = H(m, a′) definiálja. U elküldi B-nek c = c′ − v-t.

3. B c-re a szokásos r = w + xc-et válaszolja.

4. r′ = r + v és U ellenőriz, amennyiben B helyesen hajtotta végre a számításokat g^{r′} = a′h^{c′}-nek kell teljesülnie.

2.5.1. állítás. (c′, r′) hiteles aláírás m-en.

Bizonyítás. Könnyen látható, hogy:

g^{r′} = g^{r+v} = ah^{c}g^{v} = ah^{c′}h^{−u}g^{v} = a′h^{c′},

azaz a′ = h^{−c′}g^{r′}, vagyis c′ = H(m, h^{−c′}g^{r′}), tehát (c′, r′) tényleg m aláírása. ■ 2.5.2. állítás. B egy (m, c′, r′) hármasból nem tud következtetni, hogy mely alkalommal készült.

Bizonyítás. A protokollok során B a w_{i}, a_{i}, c_{i}, r_{i} számokat látja. Bármelyik (c_{i}, r_{i}) párhoz pontosan egy (u_{i}, v_{i}) pár található, amire c′ = c_{i} − u_{i} illetve r′ = r_{i} + v_{i}. Mivel a_{i} = h^{−c_{i}}g^{r_{i}} és w_{i} = log_{g} a, ezért igaz, hogy bármely (w_{i}, a_{i}, c_{i}, r_{i}) olyan négyeshez, amit B a protokoll egy helyes végrehajtása során eltárolhat, létezik egy megfelelő (u_{i}, v_{i}) pár. Tehát (m, c′, r′) nem tartalmaz olyan információt, ami megkülönböztetné az ő generálását a többiétől. ■

A Schnorr-féle aláírással kapcsolatban a következő feltételezéssel élünk:

2.5.3. feltételezés. Tetszőleges n > 0-ra, ha U (polinomiálisan limitált számítási kapacitással) B-vel n alkalommal végrehajtja a protokollt – és természetesen B követi az előírásokat –, akkor U csak elhanyagolhatóan kis valószínűséggel tud legalább n + 1 különböző üzenet – helyes aláírás pár birtokába jutni.

A feltételezés ezidáig még nem nyert bizonyítást, ám az eddig fölfedezett támadási módszerek sikertelennek bizonyultak a Schnorr-aláírás ellen.

Protokollok

3.1. Chaum eredeti rendszere

Az elektronikus fizetési rendszer egyik első megvalósítását (4)-ben olvashatjuk, ahol a közimert RSA titkosírás adja az alapokat. Lássuk, hogyan épül föl a rendszer:

Az előkészületi szakaszban a bank generál egy RSA rendszert (ahol n = pq, p és q prímek, de ≡ 1 (mod φ(n))) az (n, e) nyilvános kulccsal. Természetesen p, q és d titokban marad. Gyakorlati okokból, mivel általában a felhaszálók számítási kapacitására vannak erősebb felső korlátok, érdemes e-t kicsinek választani, legyen például 3, ekkor d-t \frac{1}{3}-dal jelöljük. A bank választ még egy f : ℤ_{n} → ℤ_{n} -fel jelölt egyirányú (hash) függvényt is.

Az egységnyi értékű érme egy, a bank által aláírt, (m, f(m)^{\frac{1}{3}} ) pár lesz, ahol m ∈ ℤ_{n}. A felhasználó (a továbbiakban U) tehát választ egy tetszőleges m-et, elküldi a banknak (akit B-vel jelölünk), aki kiszámítja f(m)^{\frac{1}{3}} -t, amiről bárki könnyedén ellenőrizheti, hogy f(m)^{\frac{1}{3}} ^{3} = f(m), azaz a bank valóban hitelesítette a pénzt. A hamisítás lehetősége kizárt, hiszen f egyirányú függvény, azaz nem lehet visszafelé, f(m)^{\frac{1}{3}} -t választva először, hozzá megfelelő m-et generálni.

Azonban ez az ötlet segít abban, hogy U anonimitását megőrizzük a fizetési protokoll folyamán: U nem f(m)-et küldi el aláírásra a banknak, hanem r^{3}f(m)-et, ahol r ∈ ℤ_{n}. A kapott rf(m)^{\frac{1}{3}} -ból pedig könnyen számíthatja f(m)^{\frac{1}{3}} -t. Így viszont fölmerül a probléma, hogy U a kapott érmét újra elköltheti (már amennyiben nem akarunk on-line ellenőrzést a fizetési protokoll közben), tehát valahogyan el kell kódolni U személyazonosságát az érmékben, úgy, hogy az csak a második elköltésnél derüljön ki.

Ezt a következőképpen oldhatjuk meg:

Először B választ egy k biztonsági paramétert, illetve f mellett egy másik, hasonlóan egyirányú függvényt, g-t. U azonosítóját a banknál u-val, a neki generált érme sorszámát pedig v-vel fogjuk jelölni, ezeket B eltárolja a protokoll során.

1. U véletlenül kiválasztja ℤ_{n}-ből az a_{i}, c_{i}, d_{i} és r_{i} értékeket, 1 ≤ i ≤ k-ra. Ezekből képzi az

x_{i} = g(a_{i}, c_{i})  (3.1)
y_{i} = g(a_{i} ⊕ (u ∥ (v + i)), d_{i})  (3.2)

számokat, ahol ⊕ a bitenkénti összeadás (XOR) művelete, ∥ pedig a konkatenációé. Majd elküldi a

B_{i} = r_{i}^{3}f(x_{i}, y_{i})  (3.3)

sorozatot a banknak.

2. B kiválaszt az \{1, …, k\} halmazból \frac{k}{2} elemet, amiket közöl U-val. Az egyszerűség kedvéért tegyük föl, hogy B a \{\frac{k}{2} + 1, …, k\} számokat választotta.

3. U elküldi a kapott indexhalmaznak megfelelő a_{i}, c_{i}, d_{i}, r_{i} értékeket Bnek.

4. B ellenőrzi, hogy az általa kért négyesek teljesítik-e az (3.1), (3.2) és (3.3) egyenleteket, megjegyezzük, hogy B birtokában van u-nak és vnek. Amennyiben az ellenőrzés sikeres, úgy B föltételezi, hogy a meg nem vizsgált B_{i}-k is helyesen lettek generálva.

5. 1 ≤ i ≤ \frac{k}{2}-re B kiszámítja Bi^{\frac{1}{3}} -t és elküldi a

B ≡ ∏_{1≤i≤ \frac{k}{2}} Bi^{\frac{1}{3}} (mod n)

számot U-nak, valamint megnöveli v-t k-val.

6. Az U által a későbbiekben felhasználható érme

C ≡ B ∏_{1≤i≤ \frac{k}{2}} r_{i} ≡ ∏_{1≤i≤ \frac{k}{2}} f(x_{i}, y_{i})^{\frac{1}{3}}  (3.4)

lesz, azzal a változtatással, hogy U átindexeli a változóit, úgy, hogy az f(x_{i}, y_{i}) értékek monoton növő sorozatot alkossanak. Természetesen ő is megnöveli a számlálóját – v-t – k-val.

A fizetési protokoll a következőképpen alakul:

1. U elküldi C-t a kereskedőnek – S-nek.

2. S véletlenszerűen kiválasztja a z_{i} ∈ \{0, 1\} számokat, 1 ≤ i ≤ \frac{k}{2}-re, és elküldi őket U-nak.

3. (a) Amennyiben z_{i} = 0, U elárulja a_{i}-t és c_{i}-t, valamint y_{i}-t, (b) míg z_{i} = 1-re a_{i} ⊕ (u ∥ (v + i)), d_{i}, illetve x_{i} lesz U válasza.

4. S ellenőrzi, hogy teljesülnek-e az (3.1), (3.2) valamint (3.4) egyenlőségek. Pozitív eredmény esetén elfogadja U pénzérméjét. A kapott C érme mellett eltárolja a protokollban szereplő z_{i} értékeket, valamint U előző lépésbeli válaszát.

Egy bizonyos, előre meghatározott időpontban S visszaküldi az összes addig begyűjtött C érmét B-nek a hozzájuk tartozó tárolt segédinformációkkal együtt. B a szokásos ellenőrzési lépések végrehajtása után jóváírja S számláján a megfelelő összeget.

3.1.1. lemma. B és S együttes erővel sem tudják párosítani a pénzfelvételi és a fizetési protokollokat úgy, hogy a használt érmék (és ezáltal a felhasználók) megegyezzenek. U anonimitása garantált amennyiben követte a protokoll szabályait.

Bizonyítás. A B által megfigyelt a_{i}, c_{i}, d_{i}, r_{i} számok nem szerepelnek később a protokollban. Ezeken kívül B még B_{i} = r_{i}^{3}f(x_{i}, y_{i})-t ismeri 1 ≤ i ≤ \frac{k}{2}-re, azonban az érmében szereplő f(x_{i}, y_{i})-k csak elhanyagolható valószínűséggel nem invertálhatók (ha f megfelelően van megválasztva), így minden n-nel relatív B_{i}-re létezik pontosan egy r_{i}, amivel B_{i} = r_{i}^{3}f(x_{i}, y_{i}) teljesül. Tehát B nem tud segíteni, hogy egy fizetésnél U-t felismerjék. S-nek pedig a meglévő információk g egyirányúsága miatt nem elegendőek ahhoz, hogy x_{i}-ből a_{i}-t, s így a_{i} ⊕ a_{i} ⊕ (u ∥ (v + i)) = u ∥ (v + i)-t kiszámítsa. ■

A felhasználó anonimitásánál is fontosabb kérdés a rendszer biztonsága, azaz U ne tudjon úgy vásárolni, hogy nem fizeti ki érte a kívánt összeget. Ezt U kétféleképpen valósíthatná meg: pénzhamisítással illetve a meglévő érme két- esetleg többszörös elköltésével. Így az alábbi biztonsági kritériumok teljsítését követeljük meg a rendszertől:

• U (esetelegesen más felhasználókkal vagy boltokkal együttműködve) ne tudjon B segítsége nélkül érvényes érmét készíteni.

• B vegye észre, ha U ugyanazt az érmét többször is elkölti és ekkor kinyomozhassa U azonosítóját, még akkor is, ha ez lehetetlen lenne, ha U csak egyszer használja föl az érmét.

Ennek tükrében:

3.1.2. lemma. Az érméket nem lehet hamisítani.

Bizonyítás. Az aláírt érme (m, f(m)^{\frac{1}{3}} ) alakú. f egyirányúsága miatt egy ilyen generálásához először m-et kell rögzíteni, azaz rögzített f(m)-re kellene kiszámolni f(m)^{\frac{1}{3}} értékét, ami pedig ellentmond annak a feltételezésünknek, miszerint az RSA rendszer biztonságos. ■

3.1.3. lemma. Ha U az érme készítésénél a k darab B_{i} szám ϵ-ad részét rosszul adja meg a banknak (azaz nem kódoja bele személyazonosságát), ezt a bank 1 − e^{ckϵ} valószínűséggel észleli valamilyen c pozitív konstanssal.

Bizonyítás. A lemma bizonyítása elemi számolás, melynek részletezésétől eltekintünk. ■

3.1.4. lemma. Ha S ugyanazt az érmét kétszer költi el, akkor nagy valószínűséggel tette bizonyítható.

Bizonyítás. Amikor a boltok a kapott érméket visszaküldik a banknak, B ellenőrzi, hogy nem kapott-e olyan érmét, amit egyszer már elköltöttek valahol. Amennyiben ez az eset állna fönn – föltéve, hogy S_{1} és S_{2} követték a fizetési protokoll szabályait –, a két alkalommal használt z_{1} és z_{2} bináris sorozatok 1 − \frac{1}{2^{\frac{k}{2}}} valószínűséggel legalább egy j indexű helyen megegyeznek. Ez azt jelenti, hogy erre a j-re az egyik fizetésnél a_{j}, a másodiknál a_{j} ⊕ (u ∥ (v + j)) került B birtokába, amikből könnyen kiszámíthatja u ∥ (v + j) = a_{j} ⊕ a_{j} ⊕ (u ∥ (v + j))-t. Amennyiben a z_{i}-k megegyeznének, a bolt(ok) hibájának gyanúja merül föl, például, hogy S_{2} U-val összejátszva lemásolta az S_{1} és U közti fizetést, ekkor B nem tudja eldönteni, melyik boltos mond igazat. Ezt megelőzheti az a változtatás, ha a boltok a z-t nem teljesen véletlenül választják, hanem úgy, hogy valamilyen módon tartalmazza az azonosítóikat. Például lehet z = H(S, spec, rand), ahol H egy alkalmas hash-függvény, S S azonosítója, rand egy véletlenül választott érték, specben pedig esetlegesen egyéb adatokat lehet eltárolni, mint mondjuk a fizetés időpontja. ■

A rendszer jelenlegi formájában azonban még B-nek lehetősége nyílik, hogy U nevében generáljon érméket. Szükséges tehát, hogy egy érméről U bizonyíthassa, hogy tényleg az ő közreműködésével készült.

Ennek biztosítására U-nak rendelkeznie kell egy külső, megbízható szervezet által garantált digitális aláírással. Az érmék generálása a következőképpen módosul: a folyamat első lépésében U az a_{i}, c_{i}, d_{i}, r_{i} számok mellett még a véletlen z_{i}, z′_{i}-ket is megválasztja. A pénzérmébe U az eddigi u helyett (y_{i} definiálásánál) u_{i} = (u ∥ z_{i} ∥ z′_{i})-t kódolja bele. A későbbiekben a B_{i} értékek mellett U elküldi még B-nek F = g(z_{1}, z′_{1}) ∥ g(z_{2}, z′_{2}) ∥ … ∥ g(z_{k}, z′_{k})-t, amit hitelesít a digitális aláírásával. Az ellenőrzés folyamán B a kért i indexekre z_{i}-t és z′_{i} is megkapja, így megbizonyosodhat róla, hogy F tényleg a megfelelő adatok felhasználásával készült.

B akkor állíthatja bizonyosan, hogy U ugyanazt az érmét többször költötte el, ha legalább \frac{k}{2} + 1 darab z_{i}-t és z′_{i}-t ismer.

A rendszer legfőbb hibája a „cut-and-choose” technika használata, a protokollok során a résztvevő feleknek túl sok információt kell kicserélniük, az érme „túl nagy” ahhoz, hogy praktikus legyen.

3.2. Brands változata

3.2.1. Az első próbálkozás

Az alábbiakban egy olyan rendszert vázolunk illetve vizsgálunk meg közelebbről, amely többszempontból is újdonságot jelent: a szóban forgó pénzmennyiséget nem egységnyi értékű érmék alkotják, hanem egy számláló állása jelöli a felhasználó rendelkezésére álló összeget, valamint a kártyán taláható egy olyan – bontásvédett – rész (megfigyelő), amely nem esik a birtokos ellenőrzése alá. Utóbbi jelenléte már a számláló miatt is szükségszerű, hiszen nélküle a felhasználó szabadon változtathatná a kártyán lévő pénz mennyiségét. Továbbá sikerül megszabadulni az előző rendszer cut-and-choose technikájától, ezt arra használtuk, hogy meggyőződjünk róla, hogy a felhasználó személyazonossága ténylegesen bele van írva az érmébe. Itt valami olyasmi történik, hogy a felhasználó érméjét egy egyenesnek képzelhetjük a síkon – az egyenes meredeksége lesz a felhasználó azonosítója –, erről az egyenesről fog a bolt egy pontot kérdezni. Azt, hogy a pont eleme-e az egyenesnek, könnyedén ellenőrizhető, míg egy pont ismeretéből nem következik az egyenes meredeksége. Amennyiben azonban kétszer költi el az érmét a felhasználó, a két ismert pontból a személyazonosság kiszámítható. Látni fogjuk majd, hogy nem lesz szükség a cut-and-choose-ra, az felhasználó csak olyan érmét tud készíteni, amelyben el van tárolva az azonosítója.

Az eddigiekhez képest a protokollok is lényeges változásokon mennek keresztül: a pénzfelvételi eljárás két részre bomlik, itt is található egy – a pénzfelvételihez hasonló – protokoll, amely során a felhasználó a banktól egy egyedi adatsorozatot kap, ezeket az érmékhez hasonlóan csak egyszer szabad fölhasználni, fontos különbség azonban, hogy itt az egyes aláírásokhoz nem tartozik konkrét pénzmennyiség. Ennek következtében szükség van egy metódusra, amely során a bank utasítja a megfigyelőt, hogy növelje a számláló állását. A fizetésbe be kell vonni a megfigyelőt, ami itt is a számláló pontos változtatásáért felelős. A boltos számlájára való jóváírás gyakorlatilag nem változik: a fizetéskor megismert adatok a bankhoz kerülnek, aki az ellenőrzés sikeressége esetén átutalja a megfelelő összeget.

A felhasználó anonimitása védelmével kapcsolatban is új problémák merülnek föl: a megfigyelő, amit valójában a bank képviselőjének tekinthetünk, részt vesz mind a pénzkivételi, mind a fizetési protokollban, így óvakodni kell, nehogy kompromittálhassa a felhasználót. Biztonsági szempontból két folyamatot kell figyelemmel kisérni: a be- illetve kiáramlást, amelyek a protokollok során a megfigyelő által megfigyelt illetve kiadott olyan adatokat jelentik, amelyek segítségével a felhasználó tranzakcói összeköthetőekké válnak. Ezért az ehhez hasonló rendszerek egyik lényeges vonása, hogy nem szabad a megfigyelőnek – a továbbiakban O-val jelöljük – közvetlenül kommunikálnia a külvilággal, az összes O által érintett adatcsere a felhasználón keresztül kell, hogy megtörténjen, így védve az illetéktelen információátadást. A két probléma közül a beáramlást tekinthetjük a kevésbé veszélyesnek, hiszen a megfigyelő tudomására jutott adatokat addig nem lehet felhasználni, amíg az a felhasználó birtokában van; tehát csak a kártya elvesztése, ellopása esetén sérülhet a vásárló inkognitója, illetve természetesen, ha a bank a érvényességi idő letelte után megköveteli a lejárt kártya visszaszolgáltatását.

A rendszerben használt számok ismét egy olyan G_{q} csoport elemei, amelyben a DLP teljesül. A számok összeszorzása pedig a csoportművelet végrehajtását jelenti.

Inicializálásképpen B kiválaszt véletlenül két elemet – x-et és y-t – ℤ_{n}- ből, ezek a titkos kulcsai lesznek; illetve egy nyilvános kulcsot – g_{0}-t – G_{q}- ból, természetesen úgy, hogy g_{0} ne legyen G_{q} egységeleme. Az x-hez és y-hoz tartozó nyilvános kulcsok másik fele h = g_{0}^{x} és g_{1} = g_{0}^{y} lesz. Továbbá rögzítésre kerül egy hash függvény is, amelyet H-val jelölünk.

Amikor egy fölhasználó – U – számlát nyit a banknál, B generál egy titkosan kezelt x_{u} ∈ ℤ_{q} számot, melyet az U rendelkezésére bocsátott O-ban eltárol. U bankbeli azonosítóját I_{u} ≡ x + yx_{u} (mod q) jelöli. Az I_{u} értéket a bank U való életbeli azonosítójával és számlája állásával együtt eltárolja. O x_{u} mellett g_{1}-et ismeri, természetesen a számlálót, amit C_{u}-val jelölünk, ez jelképezi U pénzét, valamint egy másik számlálót, T_{u}-t, ami a pénzkivételek számát méri (B ezt is tárolja). U megkapja h_{u} = g_{1}^{x_{u}}-t, a (g_{0}, g_{1}, h) hármassal egyetemben.

Bizonyos esetekben U-nak szüksége van pénzre, azaz szeretné, ha a kártyán lévő számláló értéke megnövelődne, hiszen különben nem tud vásárolni. Ekkor kapcsolatba lép a bankkal és a következő protokoll játszódik le:

1. U közli O-val azt a t összeget, amit ki szeretne venni a bankból.

2. O kiszámítja v = H(x_{u}, T_{u}, t)-t, és v′ = H(v)-t, utóbbit megmondja U-nak.

3. U fölveszi a kapcsolatot B-vel, azonosítja magát, és bejelenti azt a t összeget, amit ki szeretne venni a bankból.

4. B kiszámítja v = H(x_{u}, T_{u}, t)-t és közli U-val.

5. U ellenőrzi, hogy v′ = H(v), és átadja v-t O-nak.

6. Amennyiben U a helyes v értéket küldte, O hozzáad C_{u}-hoz t-t, T_{u}-hoz pedig egyet.

7. B is elvégzi a szükséges számlálómódosításokat.

Megjegyzésre érdemes, hogy a protokoll során csak klasszikus kriptográfiai eszközöket alkalmaztunk, nyilvános kulcsú módszerek alkalmazására nem is volt szükség, hiszen O-nak és B-nek volt egy közös titkos kulcsa (x_{u}), aminek segítségével tudtak megbízhatóan kommunikálni. A protokoll kezdő és befejező lépései tulajdnképpen off-line módon futhatnak, nincs szükség kapcsolatra B és U között, így összességében nagyon kevés on-line adatforgalomra van szükség. O és B szerepét értelemszerűen felcserélve a számáló csökkentésére is lehetőség nyílik, így a kártyáról be is lehet tenni pénzt a bankba, nem csak kivenni.

3.2.1. állítás. Az O által tárolt T_{u} érték nem lehet magasabb a B által tároltnál, ha követték a protokoll szabályait.

Bizonyítás. Nyilvánvaló, hiszen U nem tudja x_{u}-t, azaz nem képes a H(x_{u}, x, y) függvény értékét kiszámítani egyetlen (x, y) pontban sem. H hash függvény, ezért x_{u}-ra sem tud következtetni v-ből, valamint T_{u} használata megakadályozza, hogy egy régebben megismert v értéket újra felhasználva kétszer növeltethesse O-val C_{u}-t. (Természetesen az lehetséges, hogy U csak a protokoll B-vel zajló szakaszát hajtja végre, ekkor sikerül úgy pénzt kivennie a bankból, hogy nem kapja meg. Ebben az esetben ráadásul még a T_{u} számlálók is elcsúsznak és U nem tud több pénzt kivenni.)

3.2.2. állítás. A protokoll sikeresen kiszűri a B-től O-ba áramló nemkívánatos információt.

Bizonyítás. B-től csak a v szám jut el O-ba, azonban az első két lépés során U megbizonyosodik róla, hogy O ezt a rendelkezésére álló adatok alapján egyedül is ki tudta számítani. (A protokoll alatt O-ból nem jut ki semmilyen információ, így a kiáramlás nem okoz problémát.)

A fizetéshez szükség van még „fizetési engedélyek” beszerzésére a banktól, ami tulajdonképpen a bank által hitelesített tikos-nyilvános kulcspár lesz azzal a tulajdonsággal, hogy a használatához szükséges információ egy részét O fogja tárolni, így O-t föl kell törni ahhoz, hogy kétszer lehessen ugyanazt az összeget elkölteni. Azonban még ha ez be is következne, U azonosítható a tett elkövetése után.

Lássuk tehát a protokollt:

1. O generál egy véletlen w_{u} ∈ ℤ_{q} számot, tárolja, és az a_{u} = g_{1}^{w_{u}}-t elküldi U-nak.

2. U kiválasztja az (α_{1}, α_{2}, α_{3}, α_{4}, α_{5}) véletlen elemeket ℤ_{q}-ből, majd kiszámítja a h′_{u} = h_{u}g_{0}^{α_{1}}, a′_{u} = a_{u}g_{1}^{α_{2}}g_{0}^{α_{3}} értékeket. A h′_{u}, a′_{u}, α_{1···3} számok hosszú távon tárolódnak, használatukra a fizetés során is sor kerül majd, α_{4} és α_{5} csak ebben a protokollban kerül felhasználásra.

3. U kapcsolatba lép B-vel, azonosítja magát

4. B meghatároz egy véletlen w ∈ ℤ_{q}-t, és a = g_{0}^{w}-t elküldi U-nak.

5. U kiszámítja c′ = H(h′_{u}, a′_{u}, ag_{0}^{α_{4}}(hh_{u})^{α_{5}})-et, tárolja, és c ≡ c′ + α_{5} (mod q)-öt eljuttatja B-nek.

6. B válasza r ≡ cI_{u} + w (mod q) lesz.

7. U ellenőrzi, hogy g_{0}^{r}(hh_{u})^{−c} = a fennáll-e, amennyiben igen, eltárolja r′ ≡ r + c′α_{1} + α_{4} (mod q)-t.

Természetesen a protokoll elején és végén itt sincs szükség on-line kapcsolatra B és U között. B és O között nincs kapcsolat, így információáramlás sem léphet föl.

A Schnorr-féle aláíráshoz hasonlóan itt is belátható, hogy a fizetési protokollban ténylegesen használt „vesszőzött” értékekről B nem szerez információt.

A fizetés a következő forgatókönyv szerint zajlik:

1. spec egy olyan sorozatot jelöl, amiben a tranzakció bizonyos adatai tárolódnak, például a számla összege, az idő, valamint S egyedi azonosítója B-nél. U elküldi a h′_{u}, a′_{u} számokat, valamint spec-et O-nak.

2. O ellenőrzi, hogy a kifizetendő pénzre van-e elég keret, valamint, hogy tárolja-e a w_{u} értéket. Amennyiben a feltételek teljesülnek, kiszámolja d = H(h′_{u}, a′_{u}, spec)-t és r_{u1} ≡ dx_{u} + w_{u} (mod q)-t. Elküldi r_{u1}-et Unak, majd csökkenti C_{u}-t a megfelelő összeggel és törli a memóriából w_{u}-t.

3. U is kiszámolja d = H(h′_{u}, a′_{u}, spec)-t, ellenőrzi, hogy tényleg igaz-e g_{1}^{r_{u1}}(h′_{u})^{−d} = a_{u}. r′_{u1} ≡ r_{u1} + α_{2} (mod q) lesz, illetve r_{u2} ≡ dα_{1} + α_{3} (mod q).

4. U elküldi a h′_{u}, c′, r′, a′_{u}, r′_{u1}, r_{u2} adatokat S-nek.

5. S kiszámítja d = H(h′_{u}, a′_{u}, spec)-t, és ellenőrzi, hogy teljesül-e c′ = H(h′_{u}, a′_{u}, g_{0}^{r′}(hh′_{u})^{−c′}) és g_{1}^{r′_{u1}}g_{0}^{r_{u2}}(h′_{u})^{−d} = a′_{u}. Ha az egyenlőségek igazak, elfogadja a fizetést.

Befejezésképpen S jóváíratja B-nél a beérkezett pénzt, ezt szokás szerint teheti valamilyen rendszerességgel, egy csomagban elküldve a még elintézetlen vásárlások anyagát.

1. S elküldi B-nek a fizetéskor használt (h′_{u}, c′, r′, a′_{u}, r′_{u1}, r_{u2}, spec) hetest.

2. B ellenőrzi, hogy szerepel-e az adatbázisában a (h′_{u}, c′, r′) hármas:

(a) Nem: ezt az igazolást még nem használták; B is megvizsgálja az S által is ellenőrzött egyenlőségeket, ha teljesülnek, akkor elfogadja S adatait, jóváírja a számláján a megfelelő összeget és eltárolja a kapott információt.

(b) Igen: ez azt jelenti, hogy ugyanezzel a kulccsal már fizettek egyszer. Ekkor két lehetőség adódik: i. spec értéke is megegyezik a két esetben. Ekkor B S-et te-

szi felelőssé a problémáért, hiszen a spec-ek egyenlőségéből adódóan mindkétszer S fogadta el az érmét, ráadásul a specbe nyomtatot időpecsét hibakorlátján belül. B természetesen nem utalja át S számlájára a fizetés összegét.

ii. Ha spec értéke különböző a bizonyítvány két felhaszálásakor (spec_{1} ≠ spec_{2}), akkor – nagy valószínűséggel – d_{1} = H(h′_{u}, a′_{u}, spec_{1}) és d_{2} = H(h′_{u}, a′_{u}, spec_{2}) értéke is különböző lesz, így

r′_{u1_{1}} ≡ d_{1}x_{u} + w_{u} + α_{2} (mod q)
r′_{u1_{2}} ≡ d_{2}x_{u} + w_{u} + α_{2} (mod q)

miatt

x_{u} ≡ \frac{r_{u1_{1}} − r_{u1_{2}}}{d_{1} − d_{2}} (mod q),

azaz

I_{u} ≡ x + yx_{u} (mod q),

vagyis U azonosítója kiszámítható a két tranzakció adataiból.

Sajnos a protokoll a kitűzött céljaink egyikét nem valósítja meg, nevezetesen O fizetéskor megkapja – többek közt – spec-et, így, ha valakinek O a birtokába jut és ki tudja nyerni belőle az esetlegesen eltárolt adatokat, akkor máris tudomást szerezhet U vásárlásairól.

A rendszer ezen hibáján azon az áron javíthatunk, hogy feladjuk a számláló kényelmes használatát és áttérünk az elektronikus érmékre. Ez azt jelenti, hogy egy-egy B által hitelesített kulcspár nem csupán a fizetés érvényességének igazolására szolgál, hanem maga hordozza az értéket, minden egyes (h′_{u}, c′, r′, a′_{u}, r′_{u1}, r_{u2}) hatos előre rögzített értéket képvisel.

Ez a következőkben változtatja meg protokolljainkat. Először is nyilván feleslegessé válik az O-ban lévő T_{u} számláló, ezáltal maga az a módszer is, amellyel T_{u} értékét lehet növelni. Másodszor pedig: immár – mivel minden érme illetve igazolás ugyanannyit ér – nem szükséges, hogy O tudomást szerezzen a fizetés részleteiről, anélkül is hitelesítheti az érmét. Így tehát:

Érmegenerálás:

1. O kitalál egy véletlen w_{u} ∈ ℤ_{q} számot, tárolja, és az a_{u} = g_{1}^{w_{u}}-t elküldi U-nak.

2. U kiválasztja az (α_{1}, α_{2}, α_{3}, α_{4}, α_{5}, α_{6}) véletlen elemeket ℤ_{q}-ből, majd kiszámítja a h′_{u} = h_{u}g_{0}^{α_{1}}, a′_{u} = a_{u}g_{1}^{α_{2}}g_{0}^{α_{3}}h_{u}^{α_{6}} értékeket. h′_{u}, a′_{u}, α_{1···3} mellett most az új α_{6} számot is megjegyzi U későbbi használatra. α_{4} és α_{5} továbbra is csak ebben a protokollban kerül felhasználásra. A számlálós változathoz képest itt a′_{u} definiálásánál lép be egy h_{u}^{α_{6}}-os szorzótényező.

3. U kapcsolatba lép B-vel, azonosítja magát

4. B meghatároz egy véletlen w ∈ ℤ_{q}-t, és a = g_{0}^{w}-t elküldi U-nak.

5. U kiszámítja c′ = H(h′_{u}, a′_{u}, ag_{0}^{α_{4}}(hh_{u})^{α_{5}})-et, tárolja, és c ≡ c′ + α_{5} (mod q)-t eljuttatja B-nek.

6. B válasza r ≡ cI_{u} + w (mod q) lesz.

7. U ellenőrzi, hogy g_{0}^{r}(hh_{u})^{−c} = a fennáll-e, amennyiben igen, eltárolja r′ ≡ r + c′α_{1} + α_{4} (mod q)-t.

Illetve a fizetés:

1. spec itt is a tranzakció tulajdonságait írja le: S azonosítója B-nél, egy egyedi szám, mely megkülönbözteti a többi S-et érintő kifizetéstől (mint például az időpecsét), stb. U kiszámolja d = H(h′_{u}, a′_{u}, spec)-t, és most csak ennek az eltranszformált változatát d′ ≡ d + α_{6} (mod q)-t küldi el O-nak, H argumentumait nem.

2. O ellenőrzi, hogy tárolja-e a w_{u} értéket. Amennyiben igen, kiszámolja r_{u1}^{+} ≡ d′x_{u} + w_{u} (mod q)-t, elküldi U-nak, majd törli a memóriából w_{u}-t.

3. U ellenőrzi, hogy tényleg igaz-e g_{1}^{r_{u1}^{+}}(h′_{u})^{−d′} = a_{u}. r′_{u1} ≡ r_{u1}^{+} + α_{2} (mod q) lesz, illetve r_{u2} ≡ dα_{1} + α_{3} (mod q).

4. U elküldi a h′_{u}, c′, r′, a′_{u}, r′_{u1}, r_{u2} adatokat S-nek.

5. S kiszámítja d = H(h′_{u}, a′_{u}, spec)-t, és ellenőrzi, hogy teljesül-e c′ = H(h′_{u}, a′_{u}, g_{0}^{r′}(hh′_{u})^{−c′}) és g_{1}^{r′_{u1}}g_{0}^{r_{u2}}(h′_{u})^{−d} = a′_{u}. Ha az egyenlőségek igazak, elfogadja a fizetést.

A jóváírás a boltos számlájára nem változik.

Az előbbiekhez hasonló módon itt is csak akkor lehet kétszer fizetni egy igazolással, ha O védelmét U-nak sikerül föltörnie, azonban ugyanúgy kiszámítható a személyazonossága, mint a számlálós változatban.

3.2.3. állítás. Ha U és S követi a protokollok szabályait illetve U elfogadta B és O válaszait az érmegenerálás és a hitelesítés folyamán, akkor S elfogadja az érmét függetlenül attól, hogy B és O esetleg nem követte az előírásokat pontosan.

Bizonyítás. S pontosan akkor fogadja el U fizetését, ha

c′ = H(h′_{u}, a′_{u}, g_{0}^{r′}(hh′_{i})^{−c′}),

valamint

a′_{u} = g_{1}^{r′_{u1}}g_{0}^{r_{u2}}(h′_{u})^{−d}.

Fölhasználva az

a′_{u} = a_{u}g_{1}^{α_{2}}g_{0}^{α_{3}}h_{u}^{α_{6}}
c′ = H(h′_{u}, a′_{u}, as)
s = g_{0}^{α_{4}}(hh_{u})^{α_{5}}

definíciókat

g_{0}^{r′}(hh′_{u})^{−c′} = ag_{0}^{α_{4}}(hh_{u})^{α_{5}}
a_{u}g_{1}^{α_{2}}g_{0}^{α_{3}}h_{u}^{α_{6}} = g_{1}^{r′_{u1}}g_{0}^{r_{u2}}(h′_{u})^{−d}

teljesülése elégséges.

r′ ≡ r + c′α_{1} + α_{4} (mod q)
c′ ≡ c − α_{5} (mod q)
h′ = h_{u}g_{0}^{α_{1}}

felhasználásával az egyszerűsítések elvégzése után

g_{0}^{r}(hh_{u})^{−c} = a  (3.5)

adódik, ez pedig azért teljesül, mert a feltétel szerint az érmegeneráláskor U elfogadta B válaszát, ami pedig pont (3.5) ellenőrzését jelentette. Hasonlóan

r_{u2} ≡ dα_{1} + α_{3} (mod q)
d ≡ d′ − α_{6} (mod q)
r′_{u1} ≡ r_{u1}^{+} + α_{2} (mod q)
h′ = h_{u}g_{0}^{α_{1}}

miatt

a_{u} = g_{1}^{r_{u1}^{+}}(h′_{u})^{−d′},

ez pedig ekvivalens azzal, hogy U elfogadta O válaszát fizetéskor. ■

Belátható, hogy a számlálós változattal ellentétben itt már U pénzfelvételét és a fizetést nem lehet kapcsolatba hozni, azaz a vásárlás anonimitása nem sérül. Nevezzük B által megfigyelhető adatoknak az olyan (a, c, r) hármasokat, amikre g_{0}^{r}(hh_{u})^{−c} = a teljesül. Hasonlóképpen definiáljuk az O illetve S által megfigyelhető információt is (a_{u}, d′, r_{u1}^{+}) és (h′_{u}, c′, r′, a′_{u}, r′_{u1}, r_{u2}) formájában, O hármasaira g_{1}^{r_{u1}^{+}}h_{u}^{−d′} = a_{u}-nak, S hatosaira pedig g_{1}^{r′_{u1}}g_{0}^{r_{u2}}(h′_{u})^{−d} = a′_{u}-nek és c′ = H(h′_{u}, a′_{u}, g_{0}^{r′}(hh′_{u})^{−c′})-nek kell teljesülnie. Ezek a megkötések szükségesek ahhoz, hogy az említett adatokat a megfelelő személyek a protokoll egy-egy sikeres végrehajtása során rögzíthessék.

3.2.4. állítás. Bármely ((a, c, r), (a_{u}, d′, r_{u1}^{+}), (h′_{u}, c′, r′, a′_{u}, r′_{u1}, r_{u2})) B, O és S által megfigyelhető adatokra és U-ra létezik pontosan egy olyan (α_{1}, …, α_{6}) hatos, amely felhasználásával B, O és S megfigyelései összhangba hozhatók, azaz nem lehet megállapítani, hogy egy adott igazoláshoz melyik fizetés tartozik.

Bizonyítás. Tetszőleges ((a, c, r), (a_{u}, d′, r_{u1}^{+}), (h′_{u}, c′, r′, a′_{u}, r′_{u1}, r_{u2}), h_{u}) esetén legyen

α_{1} = log_{g_{0}} \frac{h′_{u}}{h_{u}}
α_{2} ≡ r′_{u1} − r_{u1}^{+} (mod q)
α_{3} ≡ r_{u2} − dα_{1} (mod q)
α_{4} ≡ r′ − r − c′α_{1} (mod q)
α_{5} ≡ c − c′ (mod q)
α_{6} ≡ d′ − d (mod q).

Ezek a választások mind a két protokollban teljesítik az összes megkövetelt kapcsolatot a változók között, legtöbbjüket azért, mert az α_{i}-ket így definiáltuk. Ellenőrizni csak a

c′ = H(h′_{u}, a′_{u}, g_{0}^{r′}(hh′_{u})^{−c′})
a′_{u} = g_{1}^{r′_{u1}}g_{0}^{r_{u2}}(h′_{u})^{−d}

egyenleteket kell, ezek teljesülése azonban könnyen belátható a megfigyelhető adatokra vonatkozó feltételeink segítségével. ■

A rendszer biztonságára itt egy új követelményt is bevezetünk a korábban említettek mellett:

• Érmét többször csak abban az esetben lehessen elkölteni, ha U-nak sikerül föltörnie O-t.

Belátható, hogy a eddigi föltételezéseink mellett (DLP, a Schorr-féle aláírás megbízhatósága) a rendszer biztonságos, amennyiben B nem engedélyezi a két különböző U-nak, hogy egyszerre, párhuzamosan futtassák az érmegenerálási protokollt.

3.2.2. Párhuzamos támadás és az ellene való védekezés

Az előbbiekben említettük, hogy Brands rendszerének biztonságához szükséges, hogy egyszerre csak egy felhasználó vehessen pénzt ki a bankból. Lássuk, hogy az első ránézésre biztonságos rendszert hogyan lehet kijátszani, ha megengedjük a párhuzamos érmegenerálást, a protokollok szereplőit U_{1}-gyel és U_{2}-vel jelölve (a megfelelő megfigyelők O_{1} és O_{2} lesznek). U_{1} és U_{2} képesek lesznek egy olyan érmét szerezni a banktól, amely többszörös elköltéséből egyikük személyazonosságát sem lehet kiszámítani, bár ehhez szükségük lesz O_{1} és O_{2} föltörésére.

A támadást lehetőségét csak vázoljuk, azaz a protokollban nem törődünk az U_{1} és U_{2} által a B-nek átadott adatok védelmével, torzításával. Föltesszük, hogy O_{1}-t és O_{2}-t sikerült föltörni, azaz az ő szerepüket is U_{1} illetve U_{2} fogja játszani:

1. B a véletlenül választott w_{1} és w_{2} számokra a_{1} = g_{0}^{w_{1}}-t és a_{2} = g_{0}^{w_{2}}-t küldi U_{1}-nek illetve U_{2}-nak.

2. U_{1} és U_{2} közösen választanak tetszőleges x_{u}-t, h′_{u} = g_{1}^{x_{u}} lesz. A véletlenül választott w_{u1} és w_{u2} értékekkel a′_{u} = g_{0}^{w_{u1}}g_{1}^{w_{u2}}, c′ = H(h′_{u}, a′_{u}, a_{1}a_{2}).

3. U_{1} kiszámítja

c_{u1} ≡ c′ \frac{x_{u2} − x_{u}}{x_{u2} − x_{u1}} (mod q)

értékét, és elküldi B-nek. Hasonlóan tesz U_{2} a

c_{u2} ≡ c′ \frac{x_{u} − x_{u1}}{x_{u2} − x_{u1}} (mod q)

számmal.

4. B válasza természetesen r′_{u1} ≡ c_{u1}I_{u1} + w_{1} (mod q) és r′_{u2} ≡ c_{u2}I_{u2} + w_{2} (mod q) lesz.

5. U_{1} és U_{2} elfogadják B válaszát, ha a_{1} = g_{0}^{r′_{u1}}(hh_{u1})^{−c_{u1}} és a_{2} = g_{0}^{r′_{u2}}(hh_{u2})^{−c_{u2}}. Ekkor r′ ≡ r′_{u1}+r′_{u2} (mod q) lesz a megfelelő válasz a közös érméjükhöz.

3.2.5. lemma. A kapott (h′_{u}, a′_{u}, c′, r′) érme „érvényes”.

Bizonyítás. Könnyen látszik, hogy

c_{u1} + c_{u2} ≡ c′ (mod q)
c_{u1}x_{u1} + c_{u2}x_{u2} ≡ c′x_{u} (mod q).

Ezért

a_{1}a_{2} = g_{0}^{r′_{u1}}(hh_{u1})^{−c_{u1}}g_{0}^{r′_{u2}}(hh_{u2})^{−c_{u2}} = g_{0}^{r′}(hh′_{u})^{−c′},

azaz

c′ = H(h′_{u}, a′_{u}, g_{0}^{r′}(hh′_{u})^{−c′}).

Az S-fel folytatott protokollokban O_{1} és O_{2} feltörése miatt U_{1} és U_{2} könnyen érvényesítheti a hamis érmét, az ott használt (r′_{u1}, r_{u2}) párnak (w_{u2}+x_{u}d, w_{u1}) párt megadva teljesül, amit S ellenőriz:

g_{1}^{w_{u2}+x_{u}d}g_{0}^{w_{u1}}h_{u}^{−d} = a′_{u}

Amikor B észleli, hogy az érmét többször költötték el, és megpróbálja leleplezni a tettest, a kapott adatokból

\frac{r′_{u1_{1}} − r′_{u1_{2}}}{d_{1} − d_{2}} ≡ x_{u} (mod q)

segítségével x_{u}-t tudja meghatározni, így U_{1} és U_{2} személyazonossága rejtve marad. ■

Ez – és más párhuzamos támadások – ellen nyújt védelmet (6) ötlete, mely fölcseréli g és h szerepét, azaz a bank rögzített nyilvános kulcsa lesz h és a felhasználók egyedi kulcsai lesznek g_{u} alakúak. Azaz: B nyilvános kulcsai: (g_{0}, g_{1}, h), ahol g_{0} = h^{y}, g_{1} = h^{x}. Egy tetszőleges U felhasználó titkos azonosítószáma x_{u}, ezt fogja majd O haszálni, B pedig az I_{u} = yx_{u} + x-et. U nyilvános kulcsa g_{u} = h^{I_{u}} = g_{0}^{x_{u}}g_{1} lesz.

A pénzfelvétel:

1. O egy véletlen w_{u}-ra (∈ ℤ_{q}) a_{u} = g_{0}^{w_{u}}-t közli U-val.

2. B egy hasonlóan véletlen w ∈ ℤ_{q}-ra a = g_{u}^{w}-nel teszi ugyanezt.

3. U vesz egy véletlen (α_{1}, …, α_{6}) ∈ ℤ_{q}^{6} hatost. Új nyilvános kulcsa g′_{u} = g_{u}^{α_{5}}-lesz, majd kiszámítja a′ = g_{u}^{α_{3}}h^{α_{4}}a-t, a′_{u} = g_{0}^{α_{1}}g_{1}^{α_{2}}g′_{u}^{α_{6}}a_{u}-t és c′ = H(g′_{u}, a′_{u}, a′)-t. c ≡ c′ + α_{4} (mod q)-t közli a bankkal.

4. B válasza r ≡ \frac{c}{I_{u}} + w (mod q) lesz.

5. U elfogad, ha g_{u}^{r}h^{−c} = a. Ebben az esetben r′ ≡ \frac{r+α_{3}}{α_{5}} (mod q).

A fizetés protokollja pedig a következő:

1. U kiszámítja d = H(spec, g′_{u}, a′_{u})-t, d′ ≡ t(d+α_{6}) (mod q)-t megmondja O-nak.

2. O kiszámítja r^{+} ≡ d′x_{u} + w_{u}-t, ha w_{u}-t megtalálja a memóriában és átadja U-nak, majd elfelejti w_{u}-t.

3. Ha g_{0}^{r^{+}}(\frac{g_{u}}{g_{1}} )^{−d′} = a_{u}, akkor U elfogadja O válaszát, kiszámítja r_{0} ≡ r^{+} + α_{1} (mod q)-et. r_{1} ≡ td + α_{6} + α_{2} (mod q) lesz. Az S-nek átadott érme a (g′_{u}, c′, r′, r_{0}, r_{1}, a′_{u}) hatos.

4. S is kiszámítja d = H(spec, g′_{u}, a′_{u})-t. Amennyiben

c′ = H(g′_{u}, a′_{u}, g′_{u}^{r′}h^{−c′})

és

a′_{u} = g_{0}^{r_{0}}g_{1}^{r_{1}}g′_{u}^{−d}

teljesül, a fizetés sikeres.

Ha bankhoz visszajuttatott érmék között lenne kettő, amelyekben (g′_{u}, c′, r′) megegyezik, akkor B a szokásos módon

α_{5} ≡ \frac{r_{1_{0}} − r_{1_{1}}}{d_{0} − d_{1}} (mod q)

és

x_{u}α_{5} ≡ \frac{r_{0_{0}} − r_{0_{1}}}{d_{0} − d_{1}} (mod q)

segítségével U azonosítója visszafejthető.

Erről a verzióról is az eddigiekhez hasonló módon beláthatjuk, hogy teljesül rá az eredeti verzió anonimitás-védelme, valamint a biztonsági tulajdonságai is, sőt, még az említett párhuzamos támadás ellen is védelmet nyújt.

Az előző változatban aláírásánál B válasza r ≡ cI_{u} + w (mod q) volt, amire g_{0}-t emelve I_{u} ≡ yx_{u} + x (mod q) miatt egy g_{0}^{I_{u}} = hh_{u} tagot kaptunk, az ellenőrzésnél g_{0}^{r}(hh_{u})^{−c} = a-nak kellett teljesülnie. Így amikor összeszoroztuk a két ellenőrző egyenletet,

g_{0}^{r_{1}}(hh_{u1})^{−c1}g_{0}^{r_{2}}(hh_{u2})^{−c2} = a_{1}a_{2}

teljesüléséhez a keresett közös c′-nek a

h^{−c_{1}}h^{−c_{2}} = h^{−c′}

és

h_{u1}^{−c_{1}}h_{u2}^{−c_{2}} = h′_{u}^{−c′}

egyenletek mindegyikét ki kellett elégíteni, a két független egyenletből meg tudtuk határozni c_{1}-et és c_{2}-t.

Most ugyanezzel a módszerrel g_{u}^{r}h^{−c} = a teljesülését várjuk el, így

g_{u1}^{r_{1}}h^{−c1}g_{u2}^{r_{2}}h^{−c2} = a_{1}a_{2}

kell, ami

g_{u1}^{r_{1}}g_{u2}^{r_{2}}h^{−c1−c2} = a_{1}a_{2},

tehát c′ ≡ c_{1} + c_{2} (mod q) kellene ismét, újabb egyenletet azonban nem nyerünk c_{1}-re és c_{2}-re, azaz az egyiket bárhogy megválaszthatjuk. Ez azonban azt jelenti, hogy nem tudjuk kihasználni a párhuzamosságot, támadásunk tehát hatástalan, hiszen az egyfelhasználós támadások elleni biztonságot már beláttuk.

Továbbíthatóság

Természetes követelményként merülhet föl, hogy az eddigi modellünkön változtassunk: miért is kellene az érméket rögtön fölhasználás után visszajuttatni a bankhoz, sokkal célszerűbb lenne, ha lehetne velük fizetni is, ezzel első ránézésre elég sok számítási kapacitást lehetne megspórolni.

Az új modellben tehát U_{1} készít egy C_{1} érmét B-vel együttműködve, B-nél lévő számlája csökken az érme értékével. Fizetéskor C_{1}-ből legyártja C_{2}-t, hogy anonimitása sértetlen maradjon a vásárláskor, majd a C_{2} érmét U_{2}-nek adja. U_{2} a kapott érméből C_{3}-at csinál, amivel U_{3}-nál fizethet, stb. Végül U_{n} úgy dönt, hogy nem akarja a kapott C_{n} érmét fölhasználni, ekkor C_{n+1}-et B-hez visszajuttatva B jóváírja a számláján a megfelelő összeget.

A rendszerrel szemben azt a követelményt támasztjuk, hogy a B-hez kerülő C_{n+1} érméből B ne legyen képes egyik U_{i} személyazonosságát sem kideríteni 1 ≤ i ≤ n − 1-re, akik előzőleg C_{n+1} elődeit használták. Természetesen U_{n} személyazonossága nem maradhat rejtve, hiszen az ő számlájára át kell utalni az érme értékét.

Az alábbiakban az előző fejezetben ismertetett rendszerből készítünk egy megfelelőt (7) általános módszere nyomán.

Kezdeti lépésként B két rendszert hoz létre, ugyanazt a G_{q}-t és H-t használja, csak két különböző nyilvános kulcshármasa lesz: (g_{0}, g_{1}, h) illetve (g′_{0}, g′_{1}, h′). A rendszer felhasználói mindegyikének minkét helyen készít azonosítókat, ezek (x_{u}, I_{u}) és (x′_{u}, I′_{u}). Az első rendszerben készített szokásos (g′_{u}, a′_{u}, c′, r′) érmét C, a másodikbelit C′ jelöli. Látható, hogy egy érméről könnyű eldönteni, hogy melyik rendszerben készült, hiszen az érvényességhez c′ = H(g′, a′_{u}, g′_{u}^{r′}h^{−c′})-nek vagy c′ = H(g′, a′_{u}, g′_{u}^{r′}h′^{−c′})-nek teljesülnie kell, a másik egyenlőség nagy valószínűsséggel nem lesz igaz. A C érmék értéke a szokásos, míg a C′ érmék önmagukban értéktelenek. A felhasználók tetszőleges időpontban készíthetnek C′ érméket a bankkal, föltételezzük, hogy mindegyik U_{i}-nek elegendően sok van a birtokában.

Amikor U_{1} szeretne egy valódi érmét kapni a banktól, teljesen hasonlóan jár el, mint az eredeti rendszerben, megkapja a C_{1} érmét. Fizetéskor eddig U_{2} ellenőrizte c′ = H(g′_{u}, a′_{u}, g′_{u}^{r′}h^{−c′})-t, majd a d = H(spec, g′_{u}, a′_{u}) kérdésre az r = (r_{0}, r_{1}) feleletet kapva ellenőrizte g_{0}^{r_{0}}g_{1}^{r_{1}} = g′_{u}^{d}a′_{u}-t, teljesülés esetén pedig elfogadta az érmét. Lássuk hogyan változik most mindez:

1. U_{1} átadja a C_{1} = (g′_{u}, a′_{u}, c′, r′) érmét U_{2}-nak.

2. U_{2} ellenőrzi c′ = H(g′_{u}, a′_{u}, g′_{u}^{r′}h^{−c′})-t, majd választ egy B-től régebben kért C′_{2} érmét. Az U_{1}-nek küldendő d pedig d_{2} = H(C′_{2}, C, spec_{2}) lesz. spec_{2} most nem tartalmazza U_{2} azonosítóját, szerepe az, hogy U_{1} – ha esetleg kétszer próbálná elkölteni C-t – ne kaphassa kétszer ugyanazt a d_{2}-t.

3. U_{1} d_{2}-re a már megszokott formájú r_{2}-t küldi válaszként.

4. U_{2} ellenőrzi, hogy helyes-e r_{2}, ha igen, akkor elfogadja az érmét.

Amikor uuk fizetni akar U_{3}-nak a kapott érmével:

1. U_{2} elküldi U_{3}-nak a C_{2} = (C_{1}, spec_{2}, r_{2}, C′_{2}) érmét.

2. U_{3} spec_{2} és r_{2} segítségével ellenőrzi, hogy helyes-e a C érme, majd egy C′_{3} érme választása után a d_{3} = H(C′_{3}, C′_{2}, spec_{3}) kérdésre

3. az r_{3} feleletet kapja U_{2}-tól, amivel

4. ellenőrzi C′_{2} helyességét.

U_{n} pedig visszajuttatja a kapott

C_{n−1} = (C_{1}, spec_{2}, r_{2}, C′_{2}, …, spec_{n−1}, r_{n−1}, C′_{n−1})

érmét kiegészítve (spec_{n}, r_{n}, C′_{n})-nel. Amennyiben U_{n} az érme megszerzésénél már tudja, hogy nem fogja továbbadni azt, akkor C′_{n} használata értelemszerűen elhagyható.

B ellenőrzi, hogy bármely két visszakapott érmében szerepel-e valahol megegyező C_{1} vagy C′_{i}, ha nem, akkor nem történt probléma, egyébként pedig a szokásos módon a tettes személyazonossága visszafejthető.

A rendszer egyik feltűnő problémája, hogy az érme minden lépésnél növekszik, ezzel arányosan nő az érvényesség ellenőrzésének ideje is. Chaum és Pedersen (8)-ban bizonyították, hogy sajnos ez szükségszerű következménye annak a követelménynek, hogy C_{n}-ből ne lehessen U_{1}, …, U_{n−1} személyazonosságát meghatározni.

Irodalomjegyzék

[1] B. Schoenmakers, „Basic Security of the ecash Payment System”, Computer Security and Industrial Cryptography: State of Art and Evolution, ESAT Course, Leuven, Belgium. LNCS series, 1997.

[2] R.L. Rivest, A. Shamir, L. Adleman, „A Method for Obtaining Digital Signatures and Public-key Cryptosystems”, Communications of the ACM, Vol. 21, No. 2, pp. 120-126, 1978.

[3] D. Boneh, G. Durfee, „Cryptanalysis of RSA with Private Key d Less than N^{0}.292”, Eurocrypt ’99, LNCS 1592, pp. 1-11, 1999.

[4] D. Chaum, A. Fiat, M. Naor, „Untraceable Electronic Cash”, Crypto ’88, LNCS 403, pp. 319-327, 1990.

[5] C.P. Schnorr, „Efficient Signature Generation by Smart Cards”, Journal of Cryptology, pp. 161-174, 1991.

[6] B. Schoenmakers, „An Efficient Payment System Withstanding Parallel Attacks”, Report CS-R9522, Centrum voor Wiskunde en Informatica, 1995.

[7] H. van Antwerpen, „Electronic Cash”, Master’s thesis, CWI, 1990.

[8] D. Chaum, T. B. Pedersen, „Transferred Cash Grows in Size”, EuroCrypt ’92, LNCS 658, pp. 390-417, 1993.