Algoritm pentru Semnături Digitale

De la Wikipedia, enciclopedia liberă

Digital Signature Algorithm ("Algoritm pentru Semnături Digitale"), cunoscut şi sub acronimul DSA, este un standard al Guvernului Statelor Unite ale Americii pentru semnăturile digitale. A fost propus de National Institute of Standards and Technology (NIST) în august 1991 pentru utilizare în Digital Signature Standard (DSS), adoptat în 1993. O revizie minoră a fost emisă în 1996 sub numele de FIPS 186-1 [1], iar standardul a fost extins în 2000 sub numele FIPS 186-2 [2].

Algoritmul este format din trei etape.

[modifică] Generarea cheii

Se alege q, astfel încât el este prim şi are o dimensiune de 160 de biţi (2¹⁵⁹ < q < 2¹⁶⁰).
Se alege p, astfel încât el este prim şi p = 2qz+1 (2⁵¹² < p < 2¹⁰²⁴).

Ultimele reglementări specifică faptul că p ar trebui să fie pe fix 1024 de biţi, ceea ce înseamnă că z trebuie să fie pe 864 de biţi.

Se alege $h \in \mathbb{Z}_{p}^{*}$ , unde h este o rădăcină primitivă în $\mathbb{Z}_{p}^{*}$ .
$\alpha = h^{z'}\mod p\,$ , unde $z'=\frac{p-1}{q}$ .
Se alege arbitrar $a \in \mathbb{Z}_{q}^{*}$ .
Se calculează $\beta = \alpha^a \mod p\,$ .
Cheia publică este $(p,q,\alpha,\beta)\,$ .
Cheia privată este $a\,$ .

[modifică] Semnarea

Se alege arbitrar $k \in \mathbb{Z}_{q}^{*}$ .
Se calculează x=SHA-1(mesaj), cu x pe 160 de biţi; SHA-1 este funcţia de hash, care realizează rezumatul mesajului (returnează un număr în funcţie de conţinutul mesajului).
Se calculează $\gamma = (\alpha ^k \mod p)\mod q\,$ .
Se calculează $\delta = (k^{-1}(x + a\gamma))\mod q\,$ .

Dacă vreuna dintre cele două valori ( $\gamma\,$ sau $\delta\,$ ) este egală cu zero, atunci se reia calculul cu generarea unui alt k.

Cheia de semnare este $(\gamma,\delta)\,$ .

[modifică] Verificarea

Se calculează $w=\delta^{-1} \mod q\,$ .
Se calculează $e_1=(xw) \mod q\,$ .
Se calculează $e_2=(\gamma w) \mod q\,$ .
Se calculează $v=((\alpha^{e_1}\beta^{e_2})\mod p) \mod q\,$ .
Semnătura este validă dacă şi numai dacă $v=\gamma\,$ .

Algoritmul Semnăturii Digitale este similar Schemei de semnătură ElGamal.

[modifică] Corectitudine

Algoritmul este corect în sensul că destinatarul va accepta întotdeauna doar semnături originale. Acest lucru poate fi demonstrat după cum urmează:

Din $\alpha = h^{z'} \mod p\,$ rezultă $\alpha^q \equiv h^{qz'} \equiv h^{p-1} \equiv 1 \pmod p\,$ din Teorema lui Fermat. Deoarece $\alpha>1\,$ şi q este prim, $\alpha\,$ are ordinul q.

Expeditorul calculează

$\delta=(k^{-1}(x+a\gamma)) \mod{q}.$

Deci

$\begin{matrix} k & \equiv & x\delta^{-1}+a\gamma\delta^{-1}\\ & \equiv & xw + a\gamma w \pmod{q}.\\ \end{matrix}$

Deoarece $\alpha\,$ are ordinul q

$\begin{matrix} \alpha^k & \equiv & \alpha^{xw}\alpha^{a\gamma w}\\ & \equiv & \alpha^{xw}\beta^{\gamma w}\\ & \equiv & \alpha^{e_1}\beta^{e_2} \pmod{p}.\\ \end{matrix}$

În sfârşit, corectitudinea algoritmului vine din

$\gamma=(\alpha^k \mod p) \mod q = (\alpha^{e_1}\beta^{e_2} \mod p) \mod q = v.$

[modifică] Securitate

Acest algoritm este considerat imposibil de spart, datorită siguranţei mari asigurate de câteva puncte, cum ar fi generarea aleatoare a lui p, q, a şi k. Pentru a se afla k, de exemplu, ar trebui rezolvată o problemă de tipul logaritmilor discreţi, care este o problemă "dificilă", în sensul că ajungerea la o soluţie poate dura câteva luni.

Adus de la "http://ro.wikipedia.org../../../a/l/g/Algoritm_pentru_Semn%C4%83turi_Digitale_b878.html"

Categorii: Algoritmi | Programare