[Prethodna tema]   [Sljedeća tema]

6.2. Elliptic Curve Digital Signature Algorithm

Jedno od pitanja koje se može postaviti prilikom komunikacije pomoću kriptosustava s javnim ključem jest pitanje vjerodostojnosti ili autentičnosti poruke. Naime, osoba B ne može biti sigurna da joj je upravo osoba A poslala poruku. Zaista, svatko ima pristup funkciji za šifriranje Be, pa se može lažno predstaviti kao osoba A. Dakle, htjeli bi imati nešto što bi bilo analogon potpisa na dokumentu. Diffie i Hellman su 1976. opisali ideju digitalnog potpisa poruke. Ideja se sastoji u tome da se pomoću originalne poruke i tajnog ključa osobe A generira digitalni potpis za osobu A. Imajući na raspolaganju poruku, digitalni potpis i javni ključ osobe A, osoba B može verificirati da je potpis autentičan.

Korištenje originalne poruke u generiranju digitalnog potpisa često rezultira vrlo dugačkim potpisom. Stoga se umjesto originalne poruke često koristi "sažetak poruke" (message digest) koji se dobije primjenom neke hash funkcije. U kriptografiji, hash funkcija je jednosmjerna funkcija koja za ulazni podatak proizvoljne duljine daje izlazni podatak fiksne duljine. Među najpoznatije hash funkcije spadaju MD5 (output od 128 bitova), RIPEMD-160 (output od 160 bitova) i SHA-1 (output od 160 bitova).

Neki kriptosustavi s javnim ključem (npr. RSA) mogu se direktno iskoristiti za potpisivanje poruke. Ipak, najpoznatije metode za generiranje digitalnih potpisa su Digital Signature Algorithm (DSA/DSS) i Elliptic Curve Digital Signature Algorithm (ECDSA). DSA je zasnovan na problemu diskretnog logaritma u multiplikativnoj grupi konačnog polja, dok ECDSA predstavlja njegov analogon i koristi eliptičke krivulje. U siječnju 1999. ECDSA je prihvaćen kao ANSI standard.

Opisat ćemo tri etape od ECDSA.

1. ECDSA generiranje ključeva.
E je eliptička krivulja nad Fp, a P je točka prostog reda n na E(Fp). Svaki korisnik napravi sljedeće:

a) Izabere slučajan broj d iz skupa {1, ... , n - 1};
b) Izračuna Q = [d] P;
c) Q je javni, a d tajni ključ.
2. ECDSA generiranje potpisa.
Kad želi potpisati poruku m, Alice radi sljedeće:
a) Izabere slučajan broj k iz skupa {1, ... , n - 1};
b) Izračuna [k] P = (x1, y1) i r = x1 mod n. Ako je r = 0, onda se vrati na korak a);
c) Izračuna k-1 mod n;
d) Izračuna s = k-1(H(m) + dr) mod n, gdje je H hash funkcija. Ako je s = 0, onda se vrati na korak a);
e) Potpis poruke m je uređeni par prirodnih brojeva (r, s).
3. ECDSA provjera potpisa.
Da bi verificirao Alicein potpis (r, s) poruke m, Bob treba napraviti sljedeće:
a) Dobiti Alicein javni ključ Q;
b) Provjeriti da su r i s cijeli brojevi iz skupa {1, ... , n - 1};
c) Izračunati w = s-1 mod n i H(m);
d) Izračunati u1 = H(m)w mod n i u2 = rw mod n;
e) Izračunati [u1] P + [u2] Q = (x0, y0) i v = x0 mod n;
f) Prihvatiti potpis kao vjerodostojan ako i samo ako je v = r.
Uvjet r <> 0 osigurava da se u potpisivanju stvarno koristi Alicein tajni ključ d, dok se uvjet s <> 0 pojavljuje zbog koraka 3.c).


Zadatci:

  1. Eliptička krivulja E nad poljem Z199 zadana je jednadžbom y2 = x3 + x + 3. Dokažite da je E(Z199) ciklička grupa s n = 197 elemenata i generatorom P = (1,76).

  2. Pomoću ECDSA definiranog pomoću eliptičke krivulje E iz 1. zadatka, digitalno potpišite poruku čija je hash vrijednost H(m) = 68, uz pretpostavku da je Vaš tajni ključ d = 29, a jednokratni ključ k = 153.

[Prethodna tema]   [Sljedeća tema]
Web stranica seminara Andrej Dujella - osobna stranica