Algoritm pentru Semnături Digitale

Algoritmul pentru semnături digitale (engleză: "Digital Signature Algorithm"), 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 cadrul standardului Digital Signature Standard (DSS), specificat în FIPS 186 și adoptat în 1993. O revizie minoră a fost emisă în 1996 sub numele de FIPS 186-1 [1]. Standardul a fost extins în 2000 ca FIPS 186-2 [2] și în 2009 ca FIPS 186-3 [3].

Algoritmul este format din trei proceduri: generarea cheii, semnarea, verificarea semnăturii.

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\,$.

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)\,$.

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.

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.$

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.