ELLIPTIC CURVE DIGITAL SIGNATURE ALGORITHM
ALGORITAM:
E je eliptička krivulja nad Fp, a P je točka prostog reda n na E(). Svaki korisnik napravi sljedeće:
1. ECDSA Generiranje ključeva.
a) Izabere slučajan broj d iz skupa {1, ... , n - 1};
b) Izračuna Q = [d] P;
c) Q je javni, a d privatni 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 Verifikacija 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) .
SIGURNOST:
Sigurnost ECDSA algoritma leži u diskretnom logaritmu na eliptičkoj krivulji (engl. Elliptic Curve Discrete Algorithm Problem ECDLP). Ako je poznata eliptička krivulja E definirana na polju Zp, točka na toj krivulji P reda n i točka na krivulji matematički je teško pronaći cijeli broj x koji zadovoljava jednadžbu Q=xP 0 =< x =< n-1.
Ako uzmemo u obzir da je MIPS (engl. Million Instructions Per Second) računalo koje može ostvariti 4x104 operacija zbrajanja na eliptičkoj krivulji po sekundi. Tada u jednoj godini možemo obaviti približno 240 operacija zbrajanja.
Gornja tablica pokazuje potrebno vrijeme za izračunavanje diskretnog logaritma na eliptičkoj krivulji Pollard rho metodom.
PROGRAMSKA REALIZACIJA:
ECDSA algoritam je u potpunosti ostvaren u programskom jeziku Java uz pomoc biblioteke jBorZoi za rad s eliptičkim krivuljama. Prilažem source ostvarenog algoritma kao projekt za razvojnu okolinu Eclipse:
1. ECDSA SOURCE
PRIMJER IZVOĐENJA PROGRAMA:
DSA Key Generation:
d = 5513305110423971922434886460879474618752101263263
Q = x:0x2c6359688ab238ab75c5db0972e43389413a098bd y:0x14affb89ba671318a805dd870240f67e99e55ad8f
DSA Signature Generation:
r = 4059733733948186980289121998606762355783486022337
s = 1115874851196254538728215092686955342007379214422
DSA Signature Verification:
w = 5022649221492098595419628589378350962516463202350
u1 = 2347555803598797944988121520097929739890393039198115579626548252456018644540345043887804215124450
u2 = 1895636595203509408579001834299418953282078829144
v = 4059733733948186980289121998606762355783486022337
v = r POTPIS PRIHVAĆEN!