9.2. Digitális aláírás

9.2.1. Digitális aláírásokról általában

9.2.1.1. Hagyományos és digitális aláírások összehasonlítása

A hagyományos aláírási rendszer mindennapi életünk fontos részét képezi. Aláírásunkkal látjuk el a különböző szerződéseket, hivatalos dokumentumokat, kérvényeket, űrlapokat, valamint személyes leveleinket is. Az aláírt dokumentum igazolja az aláíró személyét vagy intézményét, valamint azt, hogy az adott személy/intézmény a dokumentum tartalmát ismeri, elfogadja, egyetért vele. Ezen kívül az aláírás igazolja, hogy a dokumentum tartalma nem változott meg; nem írtak bele új mondatokat és nem is töröltek belőle.

A 9.3 ábrán néhány neves magyar személyiség aláírása látható, amelyet a Magyar Nagylexikon aláírás címszavából kölcsönöztünk. Érdemes megfigyelni, hogy az aláírások képe milyen sokat egyszerűsödött az évszázadok alatt. A 9.4 ábra kilenc aradi vértanú aláírását mutatja21.

A hagyományos és digitális aláírások több szempontból is eltérnek egymástól. A hagyományos aláírás a fizikai dokumentum részét képezi, a fizikai hordozóhoz (pl. papírhoz) tartozik, ahhoz hozzáfűzött egyedi kézjegy. Módosítása és másolása csak az adathordozó (papír) manipulálásával érhető el. A digitális aláírás ezzel szemben az üzenthez csatlakozik, azaz az aláíró algoritmus hozzáfűzi az aláírást a konkrét elektronikus dokumentumhoz. Ha hagyományosan írunk alá egy hosszabb dokumentumot, akkor minden egyes oldalt kézjegyünkkel el kell látni, viszont mindössze egy digitális aláírást csatolunk bármilyen méretű elektronikus üzenethez.

Jelentős különbség van az aláírás ellenőrzésének folyamatában is. A hagyományos aláírást egy – szükség esetén grafológus segítségével – hitelesített, aláírási mintához hasonlítják. Digitális aláírás érvényessége ellenőrző algoritmus futtatásával igazolható, mely bárki számára elérhető. Aláírás hamisítási szempontból a digitális aláírások sokkal megbízhatóbbak.

9.3 ábra

[20]

A harmadik jelentős különbség a már aláírt dokumentum másolhatóságában van. A hagyományosan aláírt dokumentum fénymásolata megkülönböztethető az eredetitől. Digitálisan aláírt dokumentum könnyen másolható és a másolat megegyezik az eredetivel. Egy megoldás speciális digitális aláírási rendszerek használata, a letagadhatatlan aláírások alkalmazása, mikor az aláírás ellenőrzéséhez az aláíró személy részvétele is szükséges.

9.2.1.2. Az elektronikus aláírások kategóriái

Napjainkban mindennapi életünk lebonyolítása egyre inkább elektronikusan történik, így egyre több elektronikus dokumentumot használunk. Természetes igény a hagyományos aláírás eszközének megfelelő elektronikus megoldás alkalmazása.

Az elektronikus aláírásokat három különböző kategóriába sorolhatjuk, a normál elektronikus aláírás, a fokozott biztonságú, valamint a minősített elektronikus aláírások kategóriájába.

A normál elektronikus aláírás a legtágabb kör, bármely elektronikus formájú aláírás idesorolható. Példaként említhetjük az e-mailjeink végére begépelt nevünket, vagy a különböző digitális tollakkal írt aláírást is.

Az elektronikus aláírásokról szóló törvény alapján a fokozott biztonságú elektronikus aláírás olyan "elektronikus aláírás, amely megfelel a következő követelményeknek”:

  1. Alkalmas az aláíró azonosítására, és egyedülállóan hozzá köthető,

  2. Olyan eszközzel hozták létre, mely kizárólag az aláíró befolyása alatt áll,

  3. A dokumentum tartalmához olyan módon kapcsolódik, hogy minden - az aláírás elhelyezését követően az iraton, illetve dokumentumon tett - módosítás érzékelhető

A fokozott biztonságú elektronikus aláírás tehát a nyilvános kulcsú technológia, azaz a digitális aláírási technika felhasználásával készül. Amennyiben a fokozott biztonságú elektronikus aláírás minősített tanúsítványon alapul, akkor minősített elektronikus aláírásról beszélünk. A minősített tanúsítványokról a ????? fejezetben olvashatunk.

9.4 ábra

Egyes bírósági eljárásokban legalább fokozott biztonságú elektronikus aláírással ellátott elektronikus iratokat fogadnak el, a minősített elektronikus aláírással ellátott elektronikus dokumentum teljes bizonyító erejű magánokiratnak minősül.

9.2.2. Digitális aláírási séma

A digitális aláírási séma ismertetéséhez három algoritmust kell megadni. Szükség van egy olyan algoritmusra, mely az üzenet aláírására szolgál, és szükséges az üzenethez csatolt aláírás ellenőrzését végrehajtó eljárás is. A harmadik algoritmus a kulcsgeneráló algoritmus, mely során meghatározódnak az aláírás során, illetve az ellenőrzéshez használt kulcsok. Biztosítani kell, hogy az aláírás ellenőrzését bárki elvégezhesse, azaz az ellenőrző algoritmus és a szükséges paraméterek mindenki számára elérhetőek legyenek. Az aláíró entitás egy tetszőleges mЄP nyílt szöveghez – ahol P jelöli a lehetséges üzenetek halmazát – generál egy sЄA aláírást – ahol A jelöli az aláírások halmazát – az aláíró algoritmus segítségével úgy, hogy azt csak ő tudja kiszámítani. Ezt úgy lehet biztosítani, hogy felhasznál egy aláíró kulcsot, amit csak ő ismer. Következésképpen az sЄA aláírás értéke függ az mЄP nyílt szövegtől és a kulcsgeneráló algoritmus által létrehozott titkos aláíró kulcstól. Az így keletkezett aláírás a nyílt üzenethez csatolódik. Az aláírás tulajdonképpen egy a nyílt szöveghez csatolt bitsorozat. Az aláírást ellenőrző entitás, pedig a kapott (m,s)Є P×A elempár és a rendelkezésre álló nyilvános információk alapján lefuttatja az ellenőrző algoritmust, melynek visszatérési értéke igaz, amennyiben az aláírás érvényes, és hamis, ha nem. Az ellenőrző entitás tehát az sЄA aláírás érvényességét a kapott mЄP nyílt szöveg és egy nyilvános ellenőrző kulcs segítségével dönti el.

A digitális aláírási séma jellemzői alapján kézenfekvő, hogy a konkrét megoldások aszimmetrikus rendszereket alkalmaznak. Hiszen, mint ahogy azt a ???? fejezetben ismertettük, aszimmetrikus rendszerek esetén minden résztvevő egy kulcspárral rendelkezik, ami egy titkos és egy nyilvános kulcsból áll. Mivel a nyilvános kulcsból a titkos kulcs kiszámítására polinomiális algoritmus nem ismert, így nyugodtan – mint ahogy a nevében is szerepel – nyilvánosságra is hozható, a titkos kulcs titkossága nem sérül, biztonságosan alkalmazható. Digitális aláírási sémáknál a titkos kulcsot aláírásra használjuk, hiszen alapvető cél az aláíró entitás egyértelmű beazonosítása, a nyilvános kulcs pedig az aláírás ellenőrzésére szolgál, hiszen garantálni kell, hogy bárki képes legyen arra, hogy eldöntse az aláírás hitelességét.

A digitális aláírási séma definíciója a következő:

Definíció. Jelölje P a lehetséges üzenetek halmazát és A az aláírások halmazát. Az AS=(K, Sign, Ver) digitális aláírási séma három algoritmusból áll:

  • A K kulcsgeneráló algoritmus egy polinom idejű algoritmus, melynek inputja a k biztonsági paraméter, outputja egy véletlen (SK,PK) kulcspár, ahol SK jelöli a titkos kulcsot, PK pedig a nyilvános kulcsot. A generált kulcsok mérete függ a k biztonsági paramétertől, aminek értékét a konkrét rendszerrel szembeni sikeres támadások határozzák meg.

  • Az Sign aláíró algoritmus az mЄP szöveg és az SK titkos kulcs felhasználásával egy sЄA aláírást generál. Vannak olyan rendszerek, melyek az aláírás generálásánál további véletlen paramétereket is alkalmaznak, így a kapott aláírás randomizált.

  • A Ver ellenőrző algoritmus az (m,s)Є P×A elempárhoz, a PK nyilvános kulcs alkalmazásával igaz vagy hamis értéket rendel aszerint, hogy az s érvényes aláírása-e az m üzenetnek.

Az előbbi definícióban szereplő Sign algoritmus az SK titkos kulcs ismeretében egy adott m üzenethez polinomiális időn belül számítja ki a megfelelő s aláírást. Viszont, ha a titkos kulcs nem ismert, akkor fontos az, hogy egy adott m üzenethez ne lehessen érvényes s aláírást létrehozni polinomiális időn belül. Ez a kitétel azt is jelenti, hogy a PK nyilvános kulcsból ne lehessen polinomiális időn belül a hozzátartozó SK titkos kulcsot kiszámítani. Természetesen az is feltétel, hogy tetszőleges szabályosan generált aláírásra lefuttatott ellenőrző algoritmus visszatérési értékének igaznak kell lennie.

Amennyiben a Sign algoritmus randomizált, akkor ugyanazon mЄP üzenetnek, ugyanazon SK titkos kulcs esetén, különböző véletlen paraméter mellett különböző sЄA érvényes aláírása lesz. A különböző érvényes aláírások ellenőrzése mindegyike ugyanazon PK nyilvános kulccsal és ugyanazon m üzenet alapján történik, ahol az ellenőrző algoritmus determinisztikus.

Az ellenőrző algoritmus az (m,s)Є P×A elempár vizsgálatához a megfelelő PK nyilvános kulcsot használja fel. Csak abban az esetben lesz érvényes az s aláírás az adott m üzenettől függően, ha az aláíró entitás nyilvános kulcsával történik az ellenőrzés. Az aláíró entitás nyilvános kulcsát egy hitelesítés-szolgáltató által kibocsátott aláíró tanúsítvány tartalmazza. Mint ahogy ezt a ???? fejezetben ismertetjük, a megbízható hitelesítés-szolgáltató szigorú regisztrációs folyamat után egy adott személynek vagy cégnek kiállít egy aláíró tanúsítványt, mely a tulajdonos adatain kívül a nyilvános kulcsát is tartalmazza. Így a nyilvános tanúsítvány alapján biztosak lehetünk abban, hogy az aláírás ellenőrzése során alkalmazott nyilvános kulcs a megfelelő kulcs.

Az 1. ábra a digitális aláírás folyamatát mutatja be. Az ábrán is jól látható, hogy Kriszta, az aláíró entitás üzenetét titkos kulccsal írja alá, és az így kapott aláírást és az üzenetet is elküldi Aladárnak. Aladár, az aláírást ellenőrző személy az aláírásra Kriszta nyilvános kulcsát alkalmazza, majd az elküldött üzenetet is figyelembe véve ellenőrzést végez.

1. ábra - Digitális aláírás

A 2. ábra a digitális aláírás gyakorlatban való megvalósítását mutatja. Az alapvető különbség az egyirányú hash függvény használatában van. Itt az üzenetre egy egyirányú hash függvényt alkalmazunk, melynek eredménye egy fix hosszúságú bitsorozat lesz. Majd erre az üzenetkivonatra alkalmazza Kriszta a titkos kulcsát. Az aláírt üzenetkivonat és az üzenet kerül elküldésre. Aladár az aláírt üzenetkivonatra alkalmazza Kriszta nyilvános kulcsát, illetve kiszámítja az üzenet egyirányú hash értékét. Amennyiben az így kapott üzenetkivonatok megegyeznek, akkor az aláírás érvényes. Az egyirányú hash függvény alkalmazásával a folyamat jelentősen felgyorsul, hiszen tetszőleges hosszúságú üzenet esetén is ugyanolyan hosszú kivonat (kb. 160 bit) kerül aláírásra, ami egy hatékony, de lassú folyamat. Az egyirányú hash függvény nemcsak felgyorsítja a folyamatot, de a rendszer biztonságát is jelentősen növeli.

2. ábra: Digitális aláírás labormodellje

9.2.3. Digitális aláírás jellemzői

Amennyiben az aláírás érvényes, akkor a következő tulajdonságok teljesülnek:

1. Hitelesítés (authentication) (4): Hitelesítés során a fogadó félnek biztosítékot adunk arra, hogy az adott információ valamely támadó által nem lett megváltoztatva, vagy kicserélve. Ha a következő két tulajdonság egyszerre teljesül, akkor az adott üzenet hiteles.

  • Üzenet adatintegritása: A dokumentum aláírás után nem változtatható meg. Amennyiben az elküldött üzenet tartalmát egy támadó megváltoztatja, akkor annak lenyomata különbözni fog az eredetiétől, így ellenőrzésnél ez kiderül.

  • Üzenet eredetének igazolása: Az aláíró kiléte beazonosítható a kulcspárja segítségével, hiszen csak akkor lett szabályosan legenerálva az aláírás, ha az ellenőrzésnél felhasznált nyilvános kulcs titkos párjával lett aláírva. Azt hogy az adott nyilvános kulcs az aláíró személyéhez kötődik, valamely hitelesítés szolgáltató által hitelesített aláíró tanúsítvány igazolja. A digitális aláírás egy eszköz arra, hogy egy adott üzenet eredetét bárki ellenőrizhesse, azaz az ellenőrző entitás akár egy harmadik félnek is bizonyíthatja az üzenet küldőjének személyazonosságát (A MAC üzenethitelesítéssel ellentétben).

2. Letagadhatatlan (non-repudiation):

Mivel az aláírás érvényességét bárki ellenőrizheti (az adott üzenet és a nyilvános kulcs felhasználásával), így bárki meggyőződhet arról, hogy az adott dokumentumot vagy üzenetet egy adott entitás aláírta. Következésképpen a digitálisan aláírt dokumentum nem letagadható. Ha a dokumentumon időpecsét is szerepel, akkor az aláírás időpontjáról is van információnk.

3. Hamisíthatatlan

Adott dokumentumhoz egy A entitás helyett egy B entitás nem képes olyan digitális aláírást készíteni, amelyet elfogadnának az A entitás aláírásaként. Hasonlóképpen a dokumentum sem hamisítható, hiszen két különböző dokumentum aláírásának különböznie kell. Az aszimmetrikus kriptográfiai rendszer jellemzői alapján a nyilvános információkból a titkos kulcs kiszámítása nehéz. Amennyiben csak a tulajdonos ismeri titkos kulcsát, akkor az aláírás nem hamisítható.

4. Az aláírás nem átruházható

Az aláírt üzenet kivonat egy adott üzenethez tartozik, más üzenethez nem csatolható, hiszen lenyomatuk különbözik.

9.2.4. Támadások

Áttérünk a digitális aláírási rendszer biztonsági fogalmaira. Elsőként a rendszerrel szembeni támadó lehetséges céljait adjuk meg, majd a támadásokat kategorizáljuk. Természetesen minden esetben a támadó alapvető célja az aláírás meghamisítása. Mégis a célokat négy fő kategóriába sorolhatjuk:

  • Teljes feltörés: ez a legkomolyabb támadási cél. A támadó képes meghatározni az aláíró fél titkos kulcsát. Következésképpen a támadó tetszőleges üzenetet tud aláírni a titkos kulcs tulajdonosa nevében.

  • Univerzális hamisítás: a támadó célja egy olyan hatékony algoritmus konstruálása, mely tetszőleges üzenetek aláírására képes az aláíró nevében a titkos aláíró kulcs ismerete nélkül.

  • Szelektív hamisítás: a támadó célja egy olyan hatékony algoritmus konstruálása, mely az általa kiválasztott üzenethez képes az aláíró fél nevében érvényes aláírást generálni.

  • Egzisztenciális hamisítás: a támadó célja egy olyan algoritmus generálása, mely segítségével egy üzenethez tud érvényes aláírást készíteni az aláíró fél nevében. Az alapvető különbség a szelektív és az egzisztenciális hamisítás között, hogy míg a szelektív esetén a támadó egy általa választott üzenet aláírására képes, addig itt a támadó valamely (nem feltétlen a számára legelőnyösebb) üzenethez tud aláírást konstruálni.

Sokszor az egzisztenciális hamisítás nem minősül veszélyes támadásnak, hiszen a hamisított aláírt szöveg nem értelmes, a támadó számára nem felhasználható üzenet lesz. Ennek ellenére mégis egy üzenethez érvényes aláírás tartozik, tehát az üzenet eredetét képes igazolni. Így az egzisztenciális hamisítás eredményeképpen létrejött aláírt bitsorozat magában igazolja az üzenet eredetét. Következésképpen az egzisztenciálisan hamisítható digitális aláírási sémák nem alkalmasak randomizált értékek – például kulcsok – aláírására. Tehát annak ellenére, hogy sok szituációban ez a támadástípus nem veszélyezteti a rendszer biztonságát, mégis ezzel a támadással a digitális aláírási sémák alapvető jellemzője, a hamisíthatatlanság nem teljesül, hiszen bárki generálhat érvényes aláírást az aláíró fél nevében.

Hasonlóan a kriptorendszerekhez, a digitális aláírási rendszerekkel szemben is többféle támadást különböztetünk meg. Passzív támadások esetén a támadó csak lehallgatja a csatornát, vagy esetleg valamilyen úton-módon (pl. aláíró mechanizmus, statisztikai elemzések futtatásával) hozzáfér további információkhoz és az így megszerzett adatok felhasználásával próbál aláírást hamisítani. Attól függően, hogy a támadónak milyen információk állhatnak rendelkezésére a támadásokat a következőképpen kategorizáljuk:

  • Csak a nyilvános kulcs ismert (key-only attack): a támadó rendelkezésére mindössze a nyilvános elérhető információk állnak, azaz az aláíró fél nyilvános kulcsa.

  • Ismert üzenet alapú támadás (known-message attack - KMA): a támadó rendelkezésére áll a nyilvános kulcson kívül egy üzenetekből és a hozzájuk tartozó aláírásokból álló lista. A listán szereplő üzeneteket nem a támadó választotta.

  • Választott üzenet alapú támadás (chosen-message attack - CMA): a támadó rendelkezésére áll egy az aláíró fél nevében aláíró mechanizmus, mely képes a támadó által választott üzenetek aláírására úgy, hogy a támadó nem fér hozzá a titkos aláíró kulcshoz. A támadó az aláíró mechanizmustól kéri az általa előre kiválasztott üzenetek aláírását. Az így generált üzenet-aláírás elempárokból álló lista és a nyilvános információk alapján a támadó próbál egy a listán nem lévő üzenet aláírását elkészíteni.

  • Adaptívan választott üzenet alapú támadás (adaptive chosen-message attack): ez a digitális aláírási séma elleni legerősebb támadási forma. Ebben az esetben a támadó hozzáférhet egy aláíró mechanizmushoz, amely az általa választott üzentekhez legenerálja az érvényes aláírásokat. A különbség a nem adaptívan és az adaptívan választott üzenet alapú támadás között, hogy adaptív esetben a támadó a már kapott aláírások alapján választja ki a következő üzenetet, melynek aláírását kéri. A támadó célja az így elkészült lista és a nyilvános kulcs ismeretében egy a listán nem szereplő üzenet érvényes aláírását kiszámítani az aláíró fél nevében.

Akkor fogunk egy digitális aláírási sémát biztonságosnak mondani, ha a leggyengébb támadási cél esetén a legerősebb támadással szemben is védett, azaz, ha az egzisztenciális hamisításra irányuló adaptívan választott üzenet alapú támadással szemben védettséget mutat. Egy digitális aláírási séma biztonsági elemzésének megadása azt jelenti, hogy azt vizsgáljuk, hogy egy adott típusú támadási cél elérhető –e egy kiválasztott támadási formával szemben.

Általában azt bebizonyítani nem tudjuk, hogy nem lehet sikeres támadást generálni egy adott digitális aláírási sémával szemben. Ehelyett a séma egy adott támadással szembeni védettségét egy nehéznek bizonyuló problémára vezetjük vissza, mint például a ??? fejezetben ismertetett prímfaktorizáció, illetve diszkrét logaritmus problémájára.

Randomizált aláírások esetén, mivel az aláíró algoritmus nem determinisztikus ugyanannak az aláírásnak több érvényes aláírása is van. Az ilyen aláírásoknál a fent ismertetett biztonsági fogalmak könnyen félreérthetőek. Adaptívan és nem adaptívan választott üzenet alapú támadás esetén a szigorúbb megközelítés a cél, azaz az elvárás az, hogy a támadó egy a listán nem szereplő üzenet aláírását hamisítsa. Az engedékenyebb megközelítés az, hogy akár a listán szereplő üzenet aláírását is hamisíthatja, csak egy, a listán nem szereplő érvényes aláírást kell megadnia. Amennyiben a támadó képes egy a listán szereplő üzenethez egy új aláírást hamisítani, akkor azt mondjuk, hogy a digitális aláírás alakítható (malleable). A megfelelő biztonsági cél nem-alakíthatóság (non-malleability). Adaptív esetben még azt is megengedhető, hogy a támadó ugyanazt az üzenetet többször kiválasztja és kéri a hozzátartozó érvényes aláírás legenerálását.

Digitális aláírási séma kialakítható aszimmetrikus titkosító eljárásokból abban az esetben, ha egy tetszőleges m üzenetre vonatkozóan az EncPK(DecSK(m))=m teljesül. Nyilvánvalóan titkosító rendszereknél az alapvető elvárás az, hogy DecSK(EncPK(m))=m, amennyiben bármely üzenet esetén a titkosító és visszafejtő algoritmus tetszőleges sorrendben vett egymás utáni végrehajtásával az eredeti üzenetet kapjuk vissza, akkor alkalmazható digitális aláírásra is. Ilyen rendszer például az RSA titkosító eljárás, hiszen EncPK(DecSK(m))=(md)e=m (mod n). Viszont az ElGamal rendszer esetén ez a tulajdonság nem teljesül, hiszen a titkosító és a visszafejtő algoritmus nem ugyanazon a halmazon van értelmezve.

Mint azt az ??? fejezetben kifejtettük az aszimmetrikus titkosításhoz szükséges kulcsok nagy bináris számok, ezért azokat nem lehet úgy memorizálni, mint a mindennapos PIN kódokat. A digitális aláíráshoz is ilyen kulcsokat használunk. Az ellenőrzéskor használt nyilvános kulcs elhelyezhető egy hitelesítő szervezet adatbázisában, tehát ugyanúgy, mint az aszimmetrikus titkosító rendszereknél, itt is szükséges a PKI (nyilvános kulcsú infrastruktúra) használata. A PKI-ről részletesen a ???? fejezetben olvashatunk. Az aláíró, titkos kulcsot azonban a tulajdonosának kell olyan könnyen kezelhető adathordozón tárolni és őrizni, amelyik egyszerűen felhasználható. Ezeknek a feltételeknek a smart kártyák vagy penndrive-ok felelnek meg. Normál biztonsági szintű digitális aláíráshoz használhatunk szoftkulcsot (softkey) is, amelyet a számítógép memóriájában, PIN kóddal védett állományban tárolunk.

A következő alfejezetek konkrét aláírási rendszereket részleteznek. Az itt megadott aláírási sémák mind aszimmetrikus kriptográfián alapulnak. Először a faktorizáció problémáján alapuló RSA aláírási sémával, majd a diszkrét logaritmus problémáján alapuló ElGamal és DSA sémát részletezzük.

9.2.5. RSA aláírási séma

Az algebrai struktúrája miatt az RSA kriptorendszer könnyen alakítható digitális aláírási sémává (5). Az RSA aláírási sémát a definíció szerinti három algoritmussal adjuk meg, a kulcsgeneráló, az aláíró és az ellenőrző algoritmussal.

A kulcsgenerálás teljesen megegyezik az RSA titkosításnál tanultakkal. A következő négy lépést kell végrehajtani:

  1. véletlenül választunk két nagy prímet, jelöljük p-vel és q-val, majd kiszámítjuk az n = p∙q értéket, amit RSA modulusnak hívunk.

  2. kiszámítjuk φ(n) = (p-1)(q-1), ahol φ, az Euler-féle φ függvény

  3. választunk véletlenül egy e számot, mely 1 < e < φ(n) és (e, φ(n))=1

  4. meghatározzuk d-t, ahol 1 < d < φ(n) és e•d ≡ 1 (mod φ(n))

A kulcsgenerálás során kapott (n,e) értékek nyilvánosak, az e-t nyilvános exponensnek hívjuk, a d, p, q, φ(n) számok titkosak, ahol d az aláíró titkos kulcs. Azaz SK=d és PK=(n,e) és p, q, φ(n) titkos paraméterek.

Az aláíró algoritmus egy tetszőleges mЄP üzenethez a d titkos aláíró kulcs segítségével egy sЄA aláírást számít ki, azaz Signd(m)=s, ahol s ≡ md (mod n).

Az ellenőrző algoritmus az (m,s)Є P×A elempárhoz igaz vagy hamis értéket rendel aszerint, hogy m≡se (mod n) teljesül-e, ahol e a generált nyilvános kulcs.

Az alap RSA aláírási séma több szempontból sem tekintjük biztonságosnak. Egy lehetséges támadás az egzisztenciális hamisítás, ha a támadó véletlenül választ egy s értéket és kiszámítja az m≡se (mod n) értéket, ahol az e és n nyilvánosak. Így a támadó generált egy érvényes (m,s) aláírt üzenetet a titkos d aláíró kulcs ismerete nélkül. Természetesen az így generált m üzenet nem egy a támadó által kiválasztott üzenet, hanem egy olyan bitsorozat, melynek értelme bármi – akár értelmetlen is – lehet, a támadó által nem szabályozható.

Az alap RSA egy másik gyengesége az, hogy alakítható (malleable), azaz a támadó a rendelkezésére álló (m1,s1) és (m2,s2) aláírt üzenetek alapján egy új aláírt üzenetet tud kialakítani, kiszámítani. Ugyanis az m3≡ m1m2 (mod n) üzenet szabályos aláírása az s3≡ s1 s2 (mod n), hiszen s3≡ m1 d m2 d≡(m1m2)d (mod n).

A fent részletezett támadások kriptográfiai hash függvény alkalmazásával kivédhetőek.

9.2.5.1. RSA-FDH

1996-ban Bellare és Rogaway (31) javasolt egy lehetséges digitális aláírási sémát, mely során az üzenet lenyomata kerül aláírásra. Ez a „hash-and-sign” paradigma, RSA esetén az RSA-FDH (Full-Domain Hash) digitális aláírási séma. A kulcsgeneráló algoritmus megegyezik az alap RSA rendszernél megadottakkal. Az m üzenet aláírásához választunk egy nyilvános, H: {0,1}*→Z* n egyirányú ütközésmentes hash függvényt és

  • elkészítjük a H(m) lenyomatot,

  • kiszámítjuk az s≡H(m)d (mod n) aláírást

Az ellenőrző algoritmus az (m,s) értékek alapján kiszámítja a H(m) lenyomatot, valamint az se (mod n) értéket. Amennyiben a H(m)≡se (mod n) kongruencia áll, akkor az aláírás érvényes, ha nem teljesül, akkor az aláírás nem érvényes.

Bizonyítható, hogy az RSA-FDH séma az egzisztenciális hamisításra irányuló adaptívan választott üzenetekre épülő támadással szemben biztonságos a véletlen orákulum modellben 22 (random oracle model). A bizonyítással, illetve a modell ismertetésével itt nem foglalkozunk, további ismereteket a (3) könyvben találhatunk.

Azon kívül, hogy az alap RSA digitális aláírási sémánál megadott támadásokkal szemben az RSA-FDH védettséget biztosít, jelentős gyakorlati előnye is van. Ugyanis a tetszőleges méretű üzenet helyett az üzenet fix hosszúságú (kb. 160 bit) hash értéke kerül aláírásra. Következésképpen a lassú aszimmetrikus számításokat mindössze csak néhány bit hosszú sztringre kell alkalmazni, ezzel jelentősen felgyorsítva az aláírás generálásának és az ellenőrzésének folyamatát.

Természetesen az is fontos, hogy a hash függvény használata nehogy csökkentse az RSA aláírási séma biztonságát. Következésképpen megfelelő tulajdonságú hash függvényeket alkalmazunk.

Tegyük fel, hogy a támadó rendelkezésére áll egy (m,s) aláírt üzenet, ahol s≡H(m)d (mod n). Például a támadó megtudott egy korábban, ugyanazzal titkos kulccsal aláírt üzenetet. Ekkor kiszámítja a H(m) lenyomatot és keres egy m’≠m üzenetet, melyre H(m)=H(m’). Ha talál ilyen m’ üzenetet, akkor az (m’,s) egy érvényes aláírt üzenet lesz. Így egy egzisztenciális hamisításra irányuló ismert üzenet alapú támadást végeztünk. Azért, hogy ezt hamisítást megelőzzük elvárjuk, hogy a hash függvény gyengén ütközésmentes legyen.

Másik lehetséges támadás, ha a támadó talál két üzenetet, melynek hash értéke megegyezik, azaz m és m’, ahol H(m)=H(m’). A támadó megkéri az aláíró személyt, hogy az m üzenetet írja alá titkos kulcsával. Jelölje (m,s) az így aláírt üzenetet. Ekkor a támadó rendelkezésére áll egy érvényes aláírt üzenet az (m’,s). Ez egy egzisztenciális hamisításra irányuló választott üzenet alapú támadás. Ez a támadás is megelőzhető, amennyiben az alkalmazott hash függvény (erősen) ütközésmentes.

A harmadik lehetséges támadás, ha a támadó csak a nyilvános kulcsot ismeri. Ekkor választ egy tetszőleges véletlen s értéket, alkalmazza rá a nyilvános kulcsot: se≡y (mod n). Amennyiben a támadó az y lenyomathoz meg tud adni egy m üzenetet, hogy y=H(m), akkor az (m,s) egy érvényes aláírt üzenet lesz. Ez egy egzisztenciális hamisítás, ahol csak a nyilvános kulcs ismert a támadó számára. Ez a támadás megelőzhető, ha a hash függvény egyirányú.

Az előbbiek alapján is láthatjuk, hogy a digitális aláírási sémáknál alkalmazott hash függvényeknek ütközésmentesnek és egyirányúnak kell lenniük.[21]

9.2.6. ElGamal aláírási séma

Taher ElGamal 1985-ben PhD dolgozatában (32) a diszkrét logaritmus alkalmazási lehetőségeit tanulmányozta kriptográfiai rendszerekben. Az ElGamal aláírási séma egy egész digitális aláírási séma család alapjául szolgál.

A következőkben az ElGamal aláírási séma kulcsgeneráló, aláíró és ellenőrző algoritmusát ismertetjük.

A kulcsgeneráló algoritmus lépései:

  1. Választunk egy nagy p prímet és egy Z* p primitív gyököt

  2. Véletlenül választunk egy Zp-1 értéket és kiszámítjuk A≡ga (mod p)

A kulcsgenerálás során kapott Zp-1 érték a titkos kulcs, azaz SK=a, az A érték a nyilvános kulcs, tehát PK=A. A p prím és a g primitív gyök pedig nyilvános paraméterek.

Az aláírandó üzenetek halmaza: Z* p , és az aláírások halmaza: Z* p×Zp-1 .

Az aláíró algoritmus lépései:

  1. Véletlenül választunk egy Z* p-1 értéket, amit titokban tartunk.

  2. Kiszámítjuk: r≡gk (mod p)

  3. Meghatározzuk: t≡(m-ar)k-1 (mod p-1), ahol Z* p az üzenet, melyet aláírunk.

  4. Az m üzenet aláírása: s=(r,t)

Az ellenőrző algoritmus lépése:

1. Ellenőrizzük, hogy az Arrt≡gm (mod p) kongruencia és 0<r<p teljesül-e. Amennyiben teljesülnek, akkor az aláírás érvényes, ellenkező esetben nem.

Vegyük észre, hogy az alap ElGamal aláírási séma az aláírandó üzeneteit a Z* p halmazból veszi. Az aláírások halmaza pedig Z* p×Zp-1 elempárjai. Ennek következtében az aláírás mérete duplája az aláírandó üzenet méretének. Ha például tekintünk egy 1024 bit méretű p prímet, akkor az 1024 bites üzenethez tartozó aláírás mérete 2048 bit, ami elég nagy.

Ennél a sémánál is alkalmazunk hash függvényeket. A gyakorlatban előforduló változata csak néhány lépésben különbözik. A kulcsgenerálás algoritmusa változatlan, az aláíró algoritmus során meghatározzuk az m üzenet lenyomatát: h=H(m), ahol H:{0,1}*→Zp-1 .hash függvény. Majd az így kapott h lenyomat aláírása történik meg, azaz t≡(h-ar)k-1 (mod p-1). Az aláírás továbbra is az s=(r,t) elempár lesz. Az ellenőrző algoritmus során az ellenőrző fél kiszámítja a kapott m üzenet h lenyomatát, majd ellenőrzi, hogy a Arrt≡gh (mod p) kongruencia és 0<r<p teljesül-e.

Az ElGamal digitális aláírási séma nemdeterminisztikus (a ??? fejezetben már említettük, hogy az ElGamal titkosítás is nemdeterminisztikus), azaz ugyanannak az üzenetnek több érvényes aláírása is lehetséges, és az ellenőrző algoritmus valamennyi szabályosan generált aláírást érvényesnek fog tekinteni.

Amennyiben az aláírás szabályosan generált, akkor az ElGamal digitális aláírási séma ellenőrző algoritmusa elfogadja azt. Mivel az (r,t) aláírás szabályosan generált az m üzenethez, így 0<r<p teljesül és mivel A≡ga (mod p) és r≡gk (mod p), akkor Arrt≡gargkt≡gkt+ar (mod p). Mivel g primitív gyök a gkt+ar≡gm (mod p) kongruencia teljesül, ha az exponensek kongruensek modulo p-1, azaz m≡kt+ar (mod p-1), ami áll akkor és csak akkor, ha t≡(m-ar)k-1 (mod p-1).

Az aláíró személy két titkos érték segítségével írja alá az üzenetet, az egyik maga az a titkos kulcs, a másik pedig a k titkos paraméter. Az ellenőrzés viszont a A nyilvános kulcs és a g, p nyilvános paraméterek felhasználásával történik.

Vizsgáljuk az ElGamal aláírási séma biztonsági kérdéseit. Elsőként tekintsük azt az esetet, mikor a támadó szelektív hamisítást kezdeményez, azaz egy érvényes aláírást akar hamisítani egy adott m üzenethez az a titkos kulcs ismerete nélkül. A támadó választ egy r értéket és keresi a megfelelő t-t, azaz rt≡gmA-r (mod p) ismeretében keresi t-t. Ehhez diszkrét logarimust kell számolnia, mégpedig a gmA-r érték r alapú diszkrét logaritmust mod p, ami nehéz probléma.

Egy másik lehetséges támadás, ha véletlen (r,t) elempárhoz megkeressük az m üzenetet. Ebben az esetben is diszkrét logaritmust kell számolni, azaz az Arrt≡gm (mod p) ismeretében az Arrt érték g alapú diszkrét logaritmusát kell megadni a p modulusra nézve. Ez a típusú támadás már egzisztenciális.

Az alap ElGamal aláírási séma esetén sikeres egzisztenciális hamisítást tudunk generálni, ha csak a nyilvános kulcsot ismeri a támadó, vagy ha választott üzeneten alapuló támadást hajt végre. Ezeket a támadásokat itt nem ismertetjük, a (27) könyvben részletesen megtalálhatóak. Mindezen egzisztenciális támadásokkal szemben hash függvények alkalmazásával védekezhetünk.

Sikeres támadásokat lehet végrehajtani akkor is, ha a k véletlen paraméter nem megfelelően alkalmazzuk. Komoly probléma, ha nem tartjuk titokban, azaz a támadó a t≡(m-ar)k-1 (mod p-1) kongruenciában ismeri t,m,r,p és k értékeket, így egyedül a az ismeretlen. A a meghatározása könnyű: a≡(m-kt)r-1 (mod p-1). Tehát ekkor a rendszert teljesen feltörtük, hiszen meghatároztuk a titkos kulcsot. Hasonlóan támadást lehet intézni a rendszerrel szemben a titkos kulcs meghatározására akkor is, ha kétszer ugyanazt a k értéket használjuk különböző üzenetek aláírására.

9.2.7. DSA

Az ElGamal digitális aláírási séma egyik hátránya, hogy az aláírás mértéke kétszerese az üzenetnek (pl. 2048 bit). A Digital Signature Algorithm (DSA) esetén az aláírás mérete jelentősen lecsökken. A DSA az ElGamal rendszer egy módosított változata. A DSA 1994-ben lett szabvány.

A kulcsgeneráló algoritmus a következő lépésekből áll:

  1. Véletlenül választunk egy q prímet,

  2. Megadunk egy p prímet, melyre q|p-1.

  3. Választunk egy gЄZ* p elemet, melynek rendje q.

  4. Választunk egy véletlen Zq értéket.

  5. Kiszámítjuk az A≡ga (mod p) számot.

Az Zq érték lesz a titkos kulcs (SK=a), Z* p a nyilvános kulcs (PK=A), valamint a p,q prímek és Z* p nyilvános paraméterek.

Az aláíró algoritmus a következő lépésekből áll:

  1. Választunk egy H:{0,1}*→Zq hash függvényt.

  2. Veszünk egy véletlen Z* q értéket, amit titokban tartunk.

  3. Kiszámítjuk: r≡(gk mod p) mod q

  4. Meghatározzuk: t≡(H(m)+ar)k-1 (mod q), ahol Z* p az üzenet, melynek lenyomatát aláírjuk.

  5. Az m üzenet aláírása: s=(r,t)

Az ellenőrző algoritmus lépései:

  1. Ellenőrizzük, hogy 0<r<q és 0<t<q teljesül-e

  2. Jelölje e≡H(m)t-1 (mod q) és

  3. f≡rt-1 (mod q)

  4. Amennyiben (r≡geAf mod p) mod q teljesülnek, akkor az aláírás érvényes, ellenkező esetben nem.

1991-ben a szabvány első verziójában a q hossza 160 bit, p hossza 512 és 1024 bit közötti, valamint 64-gyel osztható. Későbbiekben a javasolt értékpárok: (1024,160), (2048,224), (2048,256) és (3072,256).

Az ElGamal aláírási sémához képest az aláírás mérete kisebb, a q méretének kétszerese, azaz például, ha p mérete 1024 bit nagyságú, akkor az ElGamal aláírás 2048 bit nagyságú, míg a DSA aláírás csak 320 bit méretű.

9.2.8. A digitális aláírás fajtái és alkalmazása

Mindennapi életünkben az elektronikus szolgáltatások egyre nagyobb teret hódítanak, mely természetes módon a biztonságos elektronikus aláírás egyre gyakoribb használatát is eredményezi. Több területen is lehet hivatalos okiratainkat elektronikusan benyújtani, tárolni és digitális aláírással hitelessé tenni, ilyen területek napjainkban például az adóbevallás, cégeljárás, ügyvédi ellenjegyzés, közigazgatási hatósági eljárás, elektronikus számlázás és vizsgajelentések.

A digitális aláírási technika egy alkalmazásának tekinthetjük az időbélyeg-szolgáltatást is, mely során az adott elektronikus dokumentum lenyomatát egy Időbélyegző Szolgáltató digitális aláírásával hitelesít. Az időbélyegzésről részletesebben később lesz szó.

Digitális aláírást alkalmazhatunk minden olyan szituációban, amikor valamely információ hitelességét, érvényességét kívánjuk biztosítani, akár valamely másik fél által. Úgynevezett vak aláírási technikához folyamodhatunk, a digitális aláírás egy módosított változatához, ha a másik féllel nem akarjuk tudatni, hogy mit ír alá. Tipikus alkalmazási területe az elektronikus szavazások és az elektronikus pénz. Elektronikus szavazás esetén úgy kell érvényesíteni egy szavazatot, hogy a hitelesítő szervezet ne tudja meg, hogy az adott szavazó kire voksolt. Vak aláírási technikát a ??? alfejezetben részletezzük.

Az online nyereményjátékoknál, például a Puttónál, időbélyeg-szolgáltatással hitelesítik egy adott időpontban beérkezett tippeket. A játék lényege, hogy 5 percenként 8+1 nyerőszámot sorsolnak ki, így a játék adatai egy minősített szolgáltató által kibocsátott időbélyegzővel hitelesített állományba kerülnek, tehát egy külső megbízható szervezet igazolja a beérkezett tippek időpontját.

A digitális aláírások egy gyakori alkalmazása a programkódok aláírása. A kód aláírása egyértelműen igazolja az adott szoftver készítőjét, illetve garantálja, hogy a programkód a kibocsátás óta nem módosult. Ha a felhasználó bármely, a szoftver által generált rosszindulatú működést azonosít be, akkor feltételezhető, hogy az adott szoftver kódját senki más nem változtatta meg, egyértelműen a szerző a felelős.

Az azonosítás terén jelentős mérföldkő a digitális aláírás alkalmazása. A digitális aláírás segítségével egyértelműen meg tudjuk határozni a másik fél identitását. Ez a technika sokkal nagyobb biztonságot nyújt, mint a gyakran használt felhasználói név-jelszó alapú azonosítás. Ilyen technika például nagyon jól használható védett virtuális terekbe való belépésre. Konkrét azonosító rendszereket később ismertetünk.

9.2.8.1. Időbélyegzés

Általában a hagyományos, sajátkezű aláírással ellátott dokumentumokon az aktuális dátum feltüntetésével igazoljuk a dokumentum készítésének időpontját. Elektronikus dokumentumok esetén az időbélyeg-szolgáltatás hitelesíti a dokumentum létrejöttének idejét. Ennek megfelelően az elektronikus aláírásokhoz szorosan kapcsolódik az időbélyeg-szolgáltatás.

Az időbélyegzés egy olyan elektronikus igazolás, mely bizonyítja, hogy egy elektronikus dokumentum egy adott időpontban már létezett, és annak tartalma az időbélyegzés óta nem változott meg. Az időbélyeg általában az elektronikus aláírás létrehozásának időpontját igazolja, de használatos akkor is, ha valamely dokumentum vagy állomány adott időben való létezésének későbbi bizonyítása a cél.

Az időbélyeget Időbélyegző Szolgáltató állítja ki. Az időbélyeg tartalmazza az adott dokumentum kivonatát (hash értékét), valamint a bélyegzés időpontját, melyet az Időbélyegző Szolgáltató elektronikus aláírásával hitelesít. Minősített időbélyegzés csak Internet hozzáféréssel valósítható meg, általában az alkalmazás automatikusan kapcsolatba lép a megadott időbélyegzés szolgáltatóval.

Az időbélyegzés folyamata:

  1. Véglegesítjük az adott dokumentumot.

  2. Megfelelő program segítségével elkészül az adott dokumentum lenyomata.

  3. A lenyomatot a program elküldi az Időbélyegző Szolgáltatónak.

  4. Az Időbélyegző Szolgáltató elkészíti az időbélyeget, aláírásával hitelesíti azt, és visszaküldi a programnak.

  5. A program csatolja a dokumentumhoz az időbélyeget.

Az Időbélyegző Szolgáltató nem ismeri a dokumentum tartalmát, hiszen annak csak a lenyomatát kapja meg, melyből a dokumentumot visszaállítani nem tudja. Elektronikus aláírások esetén az időbélyeg azt az időpontot igazolja, amikor az adott aláírás már megtörtént. Amennyiben pontos időpontot, vagy időintervallumot kívánunk megadni, akkor összesen két időbélyegre van szükség. Az első igazolja azt az időpontot, amitől korábban nem keletkezhetett, a másik pedig azt az időpontot, ami előtt már megtörtént az aláírás.

9.2.8.2. Vak aláírások

A vak aláírás a digitális aláírás egy módosított változata, melynek ötlete David Chaumtól ered az 1980-as évek elején (33). A „vak” jelző arra utal, hogy az aláíró úgy hitelesíti a dokumentumot, hogy nem ismeri annak tartalmát. Tipikusan olyan alkalmazásoknál használatos, ahol valamilyen bizalmas információt kell hitelesíttetni. Gyakorlati alkalmazása általában az elektronikus szavazásoknál és a digitális pénznél fordul elő.

A vak aláírás egy interaktív algoritmus, két résztvevővel. Az egyik résztvevő, nevezzük Aladárnak, a másik résztvevővel, mely általában egy szervezet (pl. bank), aláírattat valamely bizalmas dokumentumot. Tehát az algoritmus során Aladár a „vakított” üzenetet elküldi a szervezetnek aláírásra, miután a szervezet hitelesítette a dokumentumot, visszaküldi Aladárnak, aki a „vakítás” megszüntetésével visszanyeri az aláírt, eredeti dokumentumot.

A vak aláírás technikája szemléletesen egy indigós boríték aláírásához hasonlítható. Aladár a dokumentumát belehelyezi egy átlátszatlan, indigós bevonatú borítékba, és lezárja azt. A lezárt borítékot elküldi a szervezetnek, aki kézjegyével látja el a boríték külső oldalát. Mivel a boríték indigós felületű, az aláírás megjelenik a borítékban levő dokumentumon is. Az aláíró személy nem ismeri a dokumentum tartalmát, hiszen a boríték átlátszatlan és sértetlen. Aladár miután kiveszi a dokumentumot, ellenőrizheti a hiteles aláírást.

Vak aláírási rendszerek esetén is minden egyes aláíró fél rendelkezik titkos-nyilvános kulcspárral, ahol a titkos kulcsot természetesen csak az aláíró ismeri, a nyilvános kulcsot pedig egy megbízható hitelesítés-szolgáltató által hitelesített aláíró tanúsítvány tartalmazza. A vak aláírással hitelesített dokumentumot, üzenetet bárki a nyilvános kulcs felhasználásával ellenőrizheti. Ugyanúgy, mint ahogy a digitális aláírásoknál is történik, az üzenet és a nyilvános kulcs ismeretében bárki ellenőrizheti az aláírás érvényességét.

A különbség a digitális aláírások és a vak aláírások között, hogy az utóbbinál aláíró fél az aláírás időpontjában nem ismeri az üzenet tartalmát, míg az előbbinél igen. Viszont az aláírás ellenőrzése mindkét esetben ugyanúgy történik, tehát akkor már akár az aláíró fél is, aki eddig „vak” volt, megtekintheti az üzenet tartalmát.

Az RSA vak aláírás kulcsgenerálása teljesen megegyezik az alap RSA aláíráséval. Nyilvános kulcs lesz az e exponens, és jelölje n az RSA modulust. A titkos kulcsot jelöljük d-vel, és legyen a titkos két nagy prím p és q. Először az üzenet „vakítása” történik meg, majd az így elfedett üzenetet a szervezet aláírja:

  1. A kliens választ egy bЄZn véletlen „vakító” faktort.

  2. A kliens kiszámítja az m≡be•H(m’) (mod n) üzenetet, ahol m’ az eredeti üzenet, H pedig egy megfelelő hash függvény.

  3. A kliens elküldi az m „vakított” üzenetet a szervezetnek.

  4. A szervezet kiszámítja s≡md (mod n) aláírást, és visszaküldi a feladónak.

    A kliens a kapott aláírásról „leveszi a vakítást”, azaz megszorozza a vakító faktor multiplikatív inverzével, így megkapja az eredeti m’ üzenet érvényes aláírását.

  5. A kliens a kapott s aláírásból kiszámítja az eredeti üzenet aláírását az s’ ≡ sb-1 (mod n) kongruenciával, ahol s’ az eredeti üzenet hiteles aláírása. Az aláírás ellenőrzését a már ismert módon végezhetjük el:

  6. A rendelkezésre álló (m’, s’) üzenet és aláírás alapján az ellenőrző fél kiszámítja H(m’) és (s’)e (mod n) értékeket, és ellenőrzi, hogy kongruensek-e modulo n.

Amennyiben a fenti lépések szabályosan hajtódnak végre a H(m’)≡(s’)e (mod n) kongruencia teljesül:

(s’)e ≡ (sb-1)e ≡ (mdb-1)e≡ mdeb-e≡ mb-e ≡ beH(m’)b-e ≡ H(m’) (mod n)

9.2.8.3. Letagadhatatlan aláírások

A letagadhatatlan aláírások fogalmát 1989-ben Chaum és van Antwerpen vezette be. Az ilyen aláírások több jó tulajdonsággal is rendelkeznek. Közülük a legjelentősebb, hogy egy aláírást csak az aláíró fél közbenjárásával lehet ellenőrizni. Ez lehetővé teszi, hogy az aláíró fél védje az aláírt üzenetet attól, hogy bárki elektronikusan lemásolhassa, illetve szétküldhesse. Az aláírás ellenőrzése az úgynevezett kihívás-és-válasz technika alkalmazásával végezhető el.

Jogos a kérdés, ha az aláírás ellenőrzése nem történhet meg az aláíró fél nélkül, mi akadályozza meg őt attól, hogy későbbiekben letagadja azt. Az aláíró fél irányíthatja úgy a protokoll lefutását, hogy egy érvényes aláírást hamisítványnak állítja be, illetve az ellenőrzés nem történik meg. Ennek kiküszöbölése miatt minden letagadhatatlan aláírás része a tagadó protokoll, mely segítségével bizonyítani tudja, hogy egy aláírás hamisítvány.

A letagadhatatlan aláírási séma négy algoritmusból áll, a kulcsgeneráló, az aláíró, az ellenőrző és a tagadó algoritmusból. A Chaum-van Antwerpen letagadhatatlan aláírási séma négy algoritmusa a következő: Kulcsgeneráló algoritmus:

  1. Választunk két nagy, véletlen prímet jelöljük őket p-vel és q-val úgy, hogy p=2q+1.

  2. Választunk véletlenül egy Z* p elemet, melynek rendje q.

  3. Véletlenül generálunk egy 1≤ a ≤ q-1 értéket.

  4. Kiszámítjuk h ≡ ga (mod p).

A p, g és h értékek nyilvánosak, speciálisan a h-t hívjuk nyilvános kulcsnak, míg az a szám a titkos kulcs.

Aláíró algoritmus:

Jelöljük G-vel a Z* p multiplikatív részcsoportját, melynek rendje q.

  1. 1.Jelölje mЄG az aláírandó üzenetet.

  2. 2.Az aláíró fél kiszámítja az m üzenet aláírását: s≡ma (mod p)

Ellenőrző algoritmus:

  1. Az ellenőrző fél választ két véletlen értéket: e1, e2ЄZq

  2. Az ellenőrző fél kiszámítja c≡se1he2 (mod p) és elküldi az aláíró félnek. (kihívás)

  3. Az aláíró fél kiszámítja: d≡ca-1mod q (mod p) és elküldi az ellenőrzőnek. (válasz)

  4. Az ellenőrző fél pontosan akkor tekinti az s értéket m érvényes aláírásnak, ha d≡me1ge2 (mod p).

Tagadó algoritmus:

  1. Az ellenőrző fél választ két véletlen értéket: e1, e2ЄZ* q

  2. Az ellenőrző fél kiszámítja c≡se1he2 (mod p) és elküldi az aláíró félnek. (kihívás)

  3. Az aláíró fél kiszámítja: d≡ca-1mod q (mod p) és elküldi az ellenőrzőnek. (válasz)

  4. Az ellenőrző fél megkapja, hogy d ≢ me1ge2 (mod p).

  5. Az ellenőrző fél választ két másik véletlen értéket: f1, f2ЄZ* q

  6. Az ellenőrző fél kiszámítja C≡sf1hf2 (mod p) és elküldi az aláíró félnek. (kihívás)

  7. Az aláíró fél kiszámítja: D≡ca-1mod q (mod p) és elküldi az ellenőrzőnek. (válasz)

  8. Az ellenőrző fél megkapja, hogy D ≢ mf1gf2 (mod p).

  9. Az ellenőrző fél az s aláírást hamisítványnak tekinti pontosan akkor, ha (dg-e2)f1≡(Dg-f2)e1 (mod p).

A Chaum-van Antwerpen letagadhatatlan aláírási séma biztonsága a diszkrét logaritmus problémáján alapszik, hiszen a h ≡ ga (mod p) alapján h,g és p alapján az a titkos kulcs kiszámítása nehéz.

A fentiek alapján, tehát tagadó protokoll segítségével az „elvileg aláíró fél” meg tudja győzni az ellenőrző felet, hogy az aláírás hamisítvány. Ugyanakkor az érvényes aláírást nem tudja letagadni. Ebben az esetben feltételezzük, hogy az aláíró fél nem követi a protokoll lépéseit, azaz a d és D értékeit nem az adott módon számítja ki. A következő tétel szerint egy érvényes aláírás nem letagadható.

Tétel. Feltételezve, hogy s≡ma (mod p) és az ellenőrző fél követi a tagadó protokoll lépéseit, valamint d ≢ me1ge2 (mod p) és D ≢ mf1gf2 (mod p), akkor annak valószínűsége, hogy (dg-e2)f1 ≢ (Dg-f2)e1 (mod p) az 1-1/q.

A tétel bizonyítását itt nem adjuk meg, megtalálható a (27) könyvben.



[20] 21 - Forrás: Aradi Vértanúk Albuma, Szerkesztette: Varga Ottó, Lampel R. (Wodianer F. és fia) könyvkiadása, Budapest, 1890.

[21] 22 - Véletlen orákulum alatt olyan véletlen függvényt értünk, mely nyilvánosan hozzáférhető, ugyanazon inputra ugyanazon outputot ad, és különböző inputokra viszont az output térben egyenletesen választott outputot ad.