DIGITAL SIGNATURE ALGORITHM

DSA je prvi algoritam za digitalni potpis koji je izabran kao autentifikacijski standard u vladi. Sam algoritam je varijant ElGamal-ovog algoritma za digitalni potpis.


ALGORITAM:

p i q su prim brojevi, gdje q dijeli p-1. Svaki korisnik napravi slijedeće:
1. ECDSA Generiranje ključeva.
a) Izabere slučajan broj x iz skupa {1, ... , p - 1};
b) Izračuna y = gx mod p;
c) (p, q, g, y) je javni, a x 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 r = (gx mod p) mod q;
c) Izračuna k-1 mod q;
d) Izračuna s = k-1(H(m) + xr) mod q, 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č (p, q, g, y);
b) Provjeriti da su r i s cijeli brojevi iz skupa {1, ... , q - 1};
c) Izračunati w = s-1 mod q i H(m);
d) Izračunati u1 = H(m)w mod q i u2 = rw mod q;
e) Izračunati v = (gu1yu2 mod p) mod q;
f) Prihvatiti potpis kao vjerodostojan ako i samo ako je v = r.


PROGRAMSKA REALIZACIJA:

Algoritam je programski ostvaren u programskom jeziku c uz pomoć biblioteka za rad s velikim brojevima GMP. Prilažem cijeli source ostvarenog algoritma i source ostvarenog Hash algoritma SHA-1.


SOURCE

1. dsa.c
2. dsa.h
3. sha1.c
4. sha1.h
5. Makefile

PRIMJER IZVOĐENJA PROGRAMA:

DSA Key Generation
x = b9e8f6bee415a6ae52f653b97bb3a0121c441cecb95e74f8c8aff53cefa00d1b60010ac9c29fec6f7cedbeeac6903e369569dde7e79dc4fb32a2989751091f6
g = 626d027839ea0a13413163a55b4cb500299d5522956cefcb3bff10f399ce2c2e71cb9de5fa24babf58e5b79521925c9cc42e9f6f464b088cc572af53e6d78802
y = 92521230c4a4ff8da25d26ccc898ba3187e91526b79e0c9467c61f88821f6fd7bdd28f29164b400ce253f2a32ae8daf142c29bf86b4cf6a6b533b08ba3c2ad7
DSA Sign Message
r = 5c8c9039a24ef1b6d7553dbd3ef9f0aebb3c75ad
s = 8feb9e86830cc8f818651a7e160cd9fb49d52894
DSA Verify Signature
w = 51a2a12f5fbf95c65aa65385a37375a1957349b2
u1 = 436be57ab859d79f80e951320726e9b8b1fe4005
u2 = 4982171a98b08667268d771a077d6e6fee3ab3ab
v = 5c8c9039a24ef1b6d7553dbd3ef9f0aebb3c75ad

v = r POTPIS JE PRIHVAĆEN!